因为没A/改几道题，就一起写了
题目在LOJ上都能找到
2019.2.28
100+20+12
前两个小时一直在睡觉+想题也没思路，我太菜了
T1 洗衣服
分开处理出洗衣服和烘干的时间，然后一边正着排序一边倒着排序，依次匹配(小的配大的)
正确性......不会证，意会
1 #pragma GCC optimize(2)
2 #include<queue>
3 #include<cstdio>
4 #include<cstring>
5 #include<algorithm>
6 using namespace std;
7 const int N=1000005;
8 int n,m1,m2,a[N],b[N];
9 long long fin[N],edp[N],ans;
10 struct c
11 {
12 long long st,rt;
13 long long Endt()
14 {
15 return st+rt;
16 }
17 };
18 bool operator < (c x,c y)
19 {
20 return x.Endt()>y.Endt();
21 }
22 priority_queue<c> hp1,hp2;
23 int main()
24 {
25 scanf("%d%d%d",&n,&m1,&m2);
26 for(int i=1;i<=m1;i++)
27 scanf("%d",&a[i]),hp1.push((c){0,a[i]});
28 for(int i=1;i<=m2;i++)
29 scanf("%d",&b[i]),hp2.push((c){0,b[i]});
30 for(int i=1;i<=n;i++)
31 {
32 c f=hp1.top(); hp1.pop();
33 fin[i]=f.st=f.Endt(); hp1.push(f);
34 }
35 // for(int i=1;i<=n;i++) printf("%d ",fin[i]);
36 for(int i=n;i;i--)
37 {
38 c f=hp2.top(); hp2.pop();
39 long long ed=fin[i]+f.Endt();
40 if(ed>ans) ans=ed; f.st=f.Endt();
41 hp2.push(f);
42 }
43 printf("%lld",ans);
44 return 0;
45 }
View Code
T2 编码
已经忘掉有2-sat这个东西了，想起来好歹还能写个$n^2$暴力=。=
$n^2$暴力就是枚举每对串之间的关系，优化的话我们就插出一棵Trie，边走边判断：从根到叶子的每一条链上都只能有一个填1的‘？’，记录前后缀来优化
(说的简单，你又没写
T3 猜数列
题 解 人
2019.3.1
咕计得分：100+20+10
实际得分：100+20+10
睡了一个半小时，花了半个小时切了T1，咸鱼了一个半小时没想出来T2,T3，然后跑了
T1 远行
LCT+并查集维护联通块直径，由直径性质可知每次答案一定有直径的一个端点
1 #include<cstdio>
2 #include<cctype>
3 #include<cstring>
4 #include<algorithm>
5 using namespace std;
6 const int N=300005;
7 int rev[N],stk[N],aset[N],pts[N][2];
8 int fth[N],son[N][2],len[N];
9 int n,m,t1,t2,t3,top,typ,ans;
10 void Read(int &x)
11 {
12 x=0; char ch=getchar();
13 while(!isdigit(ch))
14 ch=getchar();
15 while(isdigit(ch))
16 x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
17 }
18 int Finda(int x)
19 {
20 return x==aset[x]?x:aset[x]=Finda(aset[x]);
21 }
22 void Pushup(int nde)
23 {
24 len[nde]=len[son[nde][0]]+len[son[nde][1]]+1;
25 }
26 void Release(int nde)
27 {
28 if(rev[nde])
29 {
30 int &lson=son[nde][0],&rson=son[nde][1];
31 rev[lson]^=1,rev[rson]^=1,rev[nde]^=1;
32 swap(lson,rson);
33 }
34 }
35 bool Nottop(int nde)
36 {
37 int fa=fth[nde];
38 return son[fa][0]==nde||son[fa][1]==nde;
39 }
40 void Rotate(int nde)
41 {
42 int fa=fth[nde],gr=fth[fa],isl=nde==son[fa][0];
43 if(Nottop(fa)) son[gr][fa==son[gr][1]]=nde;
44 fth[nde]=gr,fth[fa]=nde,fth[son[nde][isl]]=fa;
45 son[fa][isl^1]=son[nde][isl],son[nde][isl]=fa;
46 Pushup(fa),Pushup(nde);
47 }
48 void Splay(int nde)
49 {
50 stk[top=1]=nde;
51 for(int i=nde;Nottop(i);i=fth[i])
52 stk[++top]=fth[i];
53 while(top) Release(stk[top--]);
54 while(Nottop(nde))
55 {
56 int fa=fth[nde],gr=fth[fa];
57 if(Nottop(fa))
58 Rotate(((son[fa][0]==nde)==(son[gr][0]==fa))?fa:nde);
59 Rotate(nde);
60 }
61 Pushup(nde);
62 }
63 void Access(int nde)
64 {
65 int lst=0,mem=nde;
66 while(nde)
67 {
68 Splay(nde),son[nde][1]=lst;
69 Pushup(nde),lst=nde,nde=fth[nde];
70 }
71 Splay(mem);
72 }
73 void Turnroot(int nde)
74 {
75 Access(nde),rev[nde]^=1;
76 }
77 int Getroot(int nde)
78 {
79 Access(nde);
80 while(son[nde][0])
81 nde=son[nde][0];
82 Splay(nde);
83 return nde;
84 }
85 void Split(int x,int y)
86 {
87 Turnroot(x),Access(y);
88 }
89 int Query(int x,int y)
90 {
91 Split(x,y);
92 return len[y];
93 }
94 void Link(int x,int y)
95 {
96 Split(x,y);
97 if(Getroot(y)!=x) fth[x]=y;
98 }
99 pair<int,int> Longest(int x)
100 {
101 int f=Finda(x),l1=Query(x,pts[f][0]),l2=Query(x,pts[f][1]);
102 // printf("%d belong to %d,two points are %d and %d\n",x,f,pts[f][0],pts[f][1]);
103 if(l1>l2) return make_pair(l1-1,pts[f][0]);
104 else return make_pair(l2-1,pts[f][1]);
105 }
106 void Road(int x,int y)
107 {
108 int fx=Finda(x),fy=Finda(y);
109 int ori=Query(pts[fy][0],pts[fy][1])-1;
110 int add=Query(pts[fx][0],pts[fx][1])-1;//printf("two parts's di are %d and %d\n",ori,add);
111 pair<int,int> p1=Longest(x),p2=Longest(y); //printf("Di of %d is %d\n",x,p1);printf("Di of %d is %d\n",y,p2);
112 if(p1.first+p2.first+1>ori)
113 pts[fy][0]=p1.second,pts[fy][1]=p2.second,ori=p1.first+p2.first+1;
114 //if(fy==3) printf("%d===%d\n",p1.second,p2.second);
115 Link(x,y),aset[fx]=fy;
116 if(add>ori)
117 {
118 pts[fy][0]=pts[fx][0];
119 pts[fy][1]=pts[fx][1],ori=add;
120 }
121 // printf("Link %d with %d,noww they belong to %d,two points are %d and %d\n",x,y,fy,pts[fy][0],pts[fy][1]);
122 }
123 int main()
124 {//freopen("hike2.in","r",stdin);
125 //freopen("myans.txt","w",stdout);
126 Read(typ),Read(n),Read(m);
127 for(int i=1;i<=n;i++)
128 len[i]=1,aset[i]=pts[i][0]=pts[i][1]=i;
129 while(m--)
130 {
131 Read(t1);
132 if(t1==1)
133 {
134 Read(t2),Read(t3);
135 if(typ) t2^=ans,t3^=ans; Road(t2,t3);
136 }
137 else
138 {
139 Read(t2); if(typ) t2^=ans;
140 printf("%d\n",ans=Longest(t2).first);
141 }
142 }
143 return 0;
144 }
View Code
T2 珠宝
决策单调性优化DP，是没写过的东西呢
T3 矩阵
线性代数那一套.jpg