CF#545题解

Source

CF#545

参考了神仙们的博客
yyb
myh

B

请先思考后再展开

kmp+贪心即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const int MAX_N=5e5+10;
int nxt[MAX_N],ct[2];
char a[MAX_N],b[MAX_N];
void main()
{
scanf("%s%s",a+1,b+1);
int n=strlen(a+1),m=strlen(b+1);for(int i=1;i<=n;i++) ct[a[i]=='1']++;
nxt[1]=0;
for(int i=2;i<=m;i++)
{
int j=nxt[i-1];while(j>0 and b[j+1]!=b[i]) j=nxt[j];
nxt[i]=j+(b[j+1]==b[i]);
}
int now=0;
for(int i=1;i<=n;i++)
{
int t=(b[now+1]-'0');
if(ct[t]>0) now++,ct[t]--,putchar('0'+t);
else now=nxt[now],putchar('0'+(t^1)),ct[t^1]--;
if(now==m) now=nxt[now];
}
}

C

请先思考后再展开

按余数拆点,tarjan一下转化为求dag上某点出发,能经过多少个不同而且开着的博物馆
然后有个性质,就是如果某条路径上来自某个点的造成了多个贡献,也就是有个能贡献i->j的环,那么一定也能回到i,所以他们不会同时在一条路径上而且还不在同一个强连通里面
于是可以跑以点为贡献的最长路,50n

D

请先思考后再展开

有个叫floyd判环法,就是两个人一个走一步一个走两步
$2(T+x)=T+x+kC$ (而且x<=C,没想清楚这里) ,那么他们同时再走T步就会到终点
复杂度为3T+2C,实现的话分两队即可

E

请先思考后再展开

显然每次加入多个,只有第一个是有意义的
把整体的操作暗处理,那么加点就是常规的变换
考虑询问(kk和bb为当前和): $ai+(kki+bb)->ai-(-kki-bb)$
那么每次塞一个-kk的直线进去询问,这个斜率是递减的,所以维护好斜率递增的凸壳,就是线性的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int INF=0x3f3f3f3f;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void writeln(int num){write(num);puts("");}
#define FR first
#define SE second
#define MP make_pair
#define pr pair<int,ll>
#define PB push_back
inline void chmax(int &x,int y) {x=x>y?x:y;}
inline void chmin(int &x,int y) {x=x<y?x:y;}
const int MAX_N=310000;
pr q[MAX_N];int top=0;
void insert(pr now)
{
while(top>1 and (double)(q[top].SE-q[top-1].SE)*(now.FR-q[top].FR)>=(double)(now.SE-q[top].SE)*(q[top].FR-q[top-1].FR) ) top--;
q[++top]=now;
}
pr ask(ll k)
{
while(top>1 and (q[top].SE-q[top-1].SE)>=k*(q[top].FR-q[top-1].FR) ) top--;
return q[top];
}
void main()
{
int n,m;scanf("%d%d",&n,&m);
int cnt=n;ll kk=0,bb=0;top=1;q[1]=MP(1,0);
while(m--)
{
int op=qread();
if(op==1) kk=bb=0,top=1,q[1]=MP(1,0),cnt+=qread();
else if(op==2) insert(MP(cnt+1,-kk*(cnt+1)-bb)),cnt+=qread();
else {ll b=qread(),k=qread();b-=k;kk+=k;bb+=b;}
pr ans=ask(-kk);printf("%d %lld\n",ans.FR,ans.SE+kk*ans.FR+bb);
}
}
};
int main()
{
srand(time(0));
mine::main();
}

F

请先思考后再展开

这是一棵无根树,但我们可以把当前最大值作为根,这样就是有根树
考虑x早于y,当且仅当 子树mx(x)<=mx(y)且x不是y的祖先
然后我们从大到小枚举每个位置access一下(理解为染色),这样形成的链就是和它的子树mx相同的链
如果没有修改,我们的答案就是 比当前颜色小的+当前颜色的孩子+1
修改的话就是一个makeroot,每个颜色用树状数组维护前缀大小
复杂度为 $O(nlog^2n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int INF=0x3f3f3f3f;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void writeln(int num){write(num);puts("");}
#define FR first
#define SE second
#define MP make_pair
#define pr pair<int,ll>
#define PB push_back
inline void chmax(int &x,int y) {x=x>y?x:y;}
inline void chmin(int &x,int y) {x=x<y?x:y;}
const int MAX_N=2e5+10;
struct BIT
{
int bit[MAX_N*2];
BIT(){memset(bit,0,sizeof bit);}
int lowbit(int x) {return x&-x;}
void add(int x,int c) {while(x<MAX_N*2) bit[x]+=c,x+=lowbit(x);}
int sum(int x) {int ans=0;while(x>=1) ans+=bit[x],x-=lowbit(x);return ans;}
}bit;
struct LCT
{
struct Nod{int son[2],fa,col,siz;bool fz,lz;}p[MAX_N];
LCT(){memset(p,0,sizeof p);}
void pushdown(int x)
{
int lc=p[x].son[0],rc=p[x].son[1];
if(p[x].lz)
{
p[x].lz=0;
p[lc].lz=1;p[lc].col=p[x].col;
p[rc].lz=1;p[rc].col=p[x].col;
}
if(p[x].fz)
{
p[lc].fz^=1;swap(p[lc].son[0],p[lc].son[1]);
p[rc].fz^=1;swap(p[rc].son[0],p[rc].son[1]);
p[x].fz=0;
}
}
void pushup(int x)
{
p[x].siz=1;
if(p[x].son[0]) p[x].siz+=p[p[x].son[0]].siz;
if(p[x].son[1]) p[x].siz+=p[p[x].son[1]].siz;
}
bool son(int x) {return p[p[x].fa].son[1]==x;}
void rotate(int x)
{
int f=p[x].fa,ff=p[f].fa;if(p[ff].son[son(f)]==f) p[ff].son[son(f)]=x;
int w=son(x),t=p[x].son[w^1];p[f].son[w]=t;p[x].son[w^1]=f;
p[x].fa=ff;p[t].fa=f;p[f].fa=x;
pushup(f);pushup(x);
}
bool isrt(int x) {return p[x].fa==0 or (p[p[x].fa].son[0]!=x and p[p[x].fa].son[1]!=x);}
int tmp[MAX_N];
void splay(int x)
{
int tot=0,now=x;while(!isrt(now)) tmp[++tot]=now,now=p[now].fa;
pushdown(now);for(int i=tot;i>=1;i--) pushdown(tmp[i]);
for(int f=p[x].fa;!isrt(x);rotate(x),f=p[x].fa)
if(!isrt(f)) son(x)^son(f)?rotate(x):rotate(f);
}
void access(int x,int id)
{
int lst=0,cnt=0;
while(x>0)
{
splay(x);
int now=p[p[x].son[0]].siz+1;cnt+=now;if(p[x].col) bit.add(p[x].col,-now);
p[x].son[1]=lst;p[lst].fa=x;pushup(x);
lst=x;x=p[x].fa;
}
if(id) bit.add(id,cnt);
p[lst].col=id;p[lst].lz=1;
}
void makeroot(int x,int id)
{
access(x,id);splay(x);
p[x].fz=1;swap(p[x].son[0],p[x].son[1]);
}
void link(int x,int y)
{
makeroot(x,0);p[x].fa=y;
}
int getc(int x)
{
splay(x);p[0].siz=0;
//printf("col=%d\n",p[x].col);
return bit.sum(p[x].col-1)+p[p[x].son[1]].siz+1;
}
}lct;
void main()
{
int n,q;scanf("%d%d",&n,&q);
for(int i=1;i<=n-1;i++)
{
int x,y;scanf("%d%d",&x,&y);
lct.link(x,y);
}
lct.makeroot(n,n);for(int i=1;i<=n;i++) lct.access(i,i);
int cnt=n;
while(q--)
{
char s[10];scanf("%s",s);
if(s[0]=='u') lct.makeroot(qread(),++cnt);
else if(s[0]=='w') printf("%d\n",lct.getc( qread() ));
else
{
int x=qread(),y=qread();
printf("%d\n",lct.getc(x)<lct.getc(y)?x:y);
}
}
}
};
int main()
{
srand(time(0));
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/9fc9.html
转载请注明出处,谢谢!