CFR631

CFR631 div1

当1038个人过A,860个人过B的时候,我还在和A的test4奋战(13min交的),陷入深深的绝望

可能40min左右放弃了,看B,很快会做但调了一会,过的时候是1h,不敢看榜

既然没什么好失去的了,就不敢A了,看C,玩了好一会发现一个奇妙的瞎jb贪能过样例,果断写

过的时候真的觉得这也太tm曲折了,然后上了现在看来至关重要的50pt

CF1329A Dreamoon Likes Coloring

请先思考后再展开

如果总长不够,或者$n-len_i<i-1$肯定非法,否则只要先把右端点放在上一个人往左一格,然后拉长以覆盖所有格子即可

code

CF1329B Dreamoon Likes Sequences

请先思考后再展开

因为a是递增的,$a_i和a_{i+1}$的最高位一定不同,此时已经能满足b的限制,所以不用管b

考虑最高位集合S(除了b的最高位$A=2^{lg}$外),贡献就是$\prod_{i \in S} 2^i$,可以用个dp求,最后乘上最高位的方案数即可,注意空的情况

1
2
3
ll lg=log2(d);
dp[0]=2;fo(i,1,30) dp[i]=dp[i-1]*(bin(i)+1)%m;
ll A=bin(lg),ans=(lg==0?1:dp[lg-1])*(d-A+2)%m+m-1;write2(ans%m);

CF1329C Drazil Likes Heap

请先思考后再展开

瞎jb猜的结论:能选根就选,否则递归两侧,code

myh的证明很靠谱

CF1329D Dreamoon Likes Strings

题意:给出字符串$|S| \le 2e5$,求最少步数的方案(注意要输出动态的下标)将其删为空串,每次选一个相邻字符不同的子串并将其移除

请先思考后再展开

显然每次端点一定满足不可延伸,所以直接取出所有矛盾,每次可以删除相邻两个不同字符,或删掉一个字符(显然先做最多次前者后,剩下都是后者),答案就是次数+1

见套路集锦-经典问题-2(注意是找次数而非度数最多的字符),因为方案输出需要当前下标,可以用bit维护存活字符,$O(nlogn)$

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
BIT bit;
set<int> live;void del(int l,int r){ while(1){ set<int>::iterator z=live.lower_bound(l);if(z==live.end() or *z>r)break;bit.ad(*z,-1),live.erase(z); } }
//------------------FIXED------------------
char str[N];int pos[N],ct[30],gl[N],gr[N];
queue<pii> go[30];bool tg[N];
void main()
{
fo(T,1,qread())
{
scanf("%s",str+1);int n=strlen(str+1),m=0;fo(i,1,n) bit.ad(i,1),live.insert(i);
fo(c,0,25) {ct[c]=0;while(sz(go[c])) go[c].pop();}
fo(i,1,n-1) if(str[i]==str[i+1]) pos[++m]=i,ct[str[i]-'a']++,gl[m]=m-1,gr[m]=m+1,tg[m]=1;
fo(i,1,m-1) if(str[pos[i]]!=str[pos[i+1]]) go[str[pos[i]]-'a'].push({i,i+1}),go[str[pos[i+1]]-'a'].push({i,i+1});
vc<pii> ans;
while(1)
{
int mx=0;fo(i,1,25) if(ct[i]>ct[mx]) mx=i;if(!sz(go[mx])) break;
int x=go[mx].front().FR,y=go[mx].front().SE;go[mx].pop();assert(str[pos[x]]!=str[pos[y]] and x<y);
if(!tg[x] or !tg[y]) continue;tg[x]=tg[y]=0;ct[str[pos[x]]-'a']--,ct[str[pos[y]]-'a']--;
int a=gl[x],b=gr[y];gl[b]=a,gr[a]=b;if(a>0 and b<=m and str[pos[a]]!=str[pos[b]]) go[str[pos[a]]-'a'].push({a,b}),go[str[pos[b]]-'a'].push({a,b});
x=pos[x]+1,y=pos[y];ans.PB({bit.ask(x),bit.ask(y)}),del(x,y);
}
int lst=n;fd(i,m,1) if(tg[i]){ int l=pos[i]+1,r=lst;ans.PB({bit.ask(l),bit.ask(r)}),del(l,r);lst=pos[i]; } ans.PB({1,bit.ask(lst)}),del(1,lst);
write2(sz(ans));for(auto in:ans) write1(in.FR),write2(in.SE);
}
}

CF1329E Dreamoon Loves AA

咕咕咕

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