CF近题层刷

CF近题层刷

UPD:CF修改了评分规则,以下分数都是旧的,不过强行改成新的似乎没有太大必要,大家适度参考即可

Codeforces 2000pt

CF1294E Obtain a Permutation会做

请先思考后再展开

对每列独立做,就是最小化$偏移量+n-匹配个数$,注意到每个数被匹配成功的偏移量只有一个,更新那个偏移量,最后扫一次即可,$O(nm)$

CF1288D Minimax Problem会做

题意:给出$n \le 3e5$个长度为$m \le 8$的数组$a_i$,选择$A,B \in [1,n]$,最大化$min_{k=1}^m\ max(a_{A,k},a_{B,k})$

请先思考后再展开

先二分答案不小于T,则选出两个数,使得二进制或能得到全集。值域为$2^8$故直接枚举两种数即可,$O(nmlog)$

*太水跑路*

Codeforces 2100pt

CF1294F Three Paths on a Tree会做

题意:给出$n \le 2e5$点的树,选出三个不同的点,使得他们的虚树(包含他们的最小联通块)最大,输出任意一个方案

请先思考后再展开

强化版是cojR8F 黄金体验,总之三个点的方案可以从直径增量得到

当然不知道结论也是随便做,设个dp背包子树内选了多少个点就好了,这个更好写

CF1288E Messenger Simulator会做

题意:初始为1..n的排列,m次输入一个数后将他移动到最前面得到一个新排列,最后对于每个数输出他历史上到过的最左和最右的位置,$n \le 3e5$

请先思考后再展开

独立考虑最左和最右,对于数字num稍作讨论

最左:如果被操作过就是1,否则就是num

最右:先把开始和结束判掉,只需要在操作这个数的时候更新他的答案即可

查询排名写个树状数组即可,$O(nlogn)$

CF1284D New Year and Conference会做

题意:给出$n\le 1e5$个元素为区间的二元组,判断是否存在一个子集,同时选左边和同时选右边, 命题「存在重叠区间」的真伪不一致

请先思考后再展开

唯一难点就是注意到,对于一个$|S|>2的集合S$,$[S不重]=[\forall_{T \subset S} T不重]$,于是完全不用判这类集合,只要每对二元组满足即可

判断集合相同可以用随机异或hash,求出每个区间的「不与之重叠二元组」即可,除了排序是线性的

CF1278D Segment Tree不够简洁

题意:给出$n \le 5e5$个区间,保证端点是2n个不同的整数;两点有边当且仅当区间重叠且互不包含,问建出的是否是树

请先思考后再展开

我的较复杂做法:和一个区间连边的范围就是两个矩形,离线下来扫描线,碰到一个点的时候,较好写的线段树得出所有覆盖该点的矩形,dsu连边

一种稍有技巧性的简短做法:直接从左到右枚举每个端点,如果是左端点就把右端点丢到set里,并且枚举set中与自己连边的前缀,dsu连接

1
2
3
4
5
6
7
8
9
10
11
12
int n=qread();fo(i,1,n) {int l=qread(),r=qread();R[l]=r;id[l]=id[r]=i;a[l]={0,i};a[r]={1,i};fa[i]=i;}
int cnt=0;fo(i,1,n+n) if(a[i].FR==1) right.erase(i);
else
{
for(set<int>::iterator it=right.begin();it!=right.end();it++)
{
int go=id[*it];if(*it>R[i]) break;
cnt++;int fx=findfa(id[i]),fy=findfa(go);
if(cnt>n-1 or fx==fy) {puts("NO");return;} fa[fx]=fy;
}
right.insert(R[i]);
}puts(cnt!=n-1?"NO":"YES");

*太水跑路*

Codeforces 2200pt

CF1278E Tests for problem D会做

题意:给出一棵树,写一个CF1278D的数据生成器

请先思考后再展开

这种题关键就是构造一种分形

1
2
3
4
5
void solve(int x,int fa)
{
int m=sz(to[x])-(fa>0);ret[x].SE=rmx+m+1;rmx+=m+1;
int id=rmx;for(auto y:to[x]) if(y!=fa) ret[y].FR=--id,solve(y,x);
}

CF1267K Key Storage会做

请先思考后再展开

套路集锦:两次整除与直接整除其乘积,结果一样;这个多重集的大小<20

容易发现一个余数序列(不是多重集)唯一对应一个数,且序列最后一项一定不是0

于是求出多重集求合法的排列即可,从大到小考虑每种数怎么放,把最后一项是0的方案容斥掉即可,$O(20T)$

1
2
3
4
mem(ct,0);fo(i,2,20) {ct[num%i]++,sum++,num/=i;if(num==0)break;}
ll ans1=1;int used=0;fd(i,sum,1) ans1*=C[sum-i+1-used][ct[i]],used+=ct[i];
ll ans2=1;used=1;fd(i,sum,1) {if(sum-i+1-used<0){ans2=0;break;}ans2*=C[sum-i+1-used][ct[i]],used+=ct[i];}
write2(ans1-ans2-1);

CF1253E Antenna Coverage会做

请先思考后再展开

zz题,$dp(pos)$=后缀pos被处理完的最小代价,直接枚举哪个人覆盖pos即可,$O(nm)$

1
2
3
4
5
6
fd(i,m,1) dp[i]=m-i+1;
fd(i,m,1) fo(lst,1,n)
{
int ned=max(0,a[lst].FR-a[lst].SE-i);
chmin(dp[i], ned+dp[a[lst].FR+a[lst].SE+ned+1] );
}write(dp[1]);

*太水跑路*

Codeforces 2300pt

CF1311E Construct the Binary Tree会做

题意:给出n和d,构造二叉树满足节点dep之和=d

请先思考后再展开

显然其实是求一个序列,$\sum a_i=n,\sum i*a_i=d$

想了挺久的,感受一下应该每个n能得到的d是一个区间。思考了几种方案最后发现从链开始,把每个点往上拉就是对的

1
2
3
4
5
6
7
8
9
int n=qread(),D=qread();fo(i,0,n-1) a[i]=1,D-=i,son[i+1]=0;int lst=n-1;
while(D<0)
{
int ok=lst;fo(i,1,lst-1) if(a[i]<a[i-1]*2 and D+lst-i<=0) {ok=i;break;}
if(ok==lst) break;D+=lst-ok;a[lst]--,a[ok]++;
while(!a[lst]) lst--;
}
if(D!=0){ puts("NO");continue; }puts("YES");
int cur=2;fo(i,1,lst)while(a[i]--){ int wt=0;fo(j,1,cur-1)if(son[j]<2 and dep[j]==i-1)wt=j;assert(wt>0); son[wt]++,write1(wt),dep[cur++]=i; }puts("");

CF1292C Xenon’s Attack on the Gangs会做

题意:给出一棵$n \le 3e3$个点的树,$将[0,n-2]排列到边上,最大化\sum_{x<y} mex(x \to y的路径边权集)$

请先思考后再展开

md某luogu题解上写求最小,那么特判掉单链的情况后,可以在两条叶子边上填0和1,于是答案为$(n-1)*1+1*2$

最大的话一开始想错了还是花了一会时间,整理一下其实也很清晰自然:没有经过0的路径不用管,经过0的路径至少为1,然后增量地考虑同时经过0和1的路径个数……发现有贡献的就是一条路径,上面是从0开始的连续数字。如果已知是哪条路径考虑怎么分配数字,那么很容易发现最优方案应该是0在中间,递增加入1到len,每次可以放在链的左边或右边

于是dp这个链就得了,不带脑子枚举链再区间dp就是$O(n^2*n^2)$,但显然太zz,写成树上路径dp就是$O(n^2)$,路径更短的端点或子树大小都可以枚举根预处理

1
2
3
4
5
6
ll dp(int x,int y)
{
if(DP[x][y]) return DP[x][y];
int xx=pre[y][x],yy=pre[x][y];
return DP[x][y]=(xx==y?0:max( dp(xx,y),dp(x,yy) ))+siz[y][x]*siz[x][y];
}

CF1285E Delete a Segment会做

题意:给出$n \le 2e5$个数轴上线段$[l_i,r_i]$,问如果只没有第i个线段,剩下线段并的个数(连续被覆盖的数),注意$[1,3]和[4,6]$算是两个

请先思考后再展开

为了符合正常人理解且考虑到线段可能退化为点,先离散化,然后给整数点和实数区都编号,具体而言就是将$[l,r] \to [2l,2r]$。

发现恰没有第i个线段答案就是,全集数+只由第i个线段覆盖的(将连续的只被第i个线段覆盖的部分缩成一,忽略在每段最左边和右边的块;这部分肯定都是实数区)-自己独立组成了一个段。

看了几个代码感觉可能差不多长甚至自己会更长些,有点不爽,不停想怎么更简洁,结果真正写完的时候发现巨短,写完就过了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int n=qread();nums.clear();fo(i,0,n*5) on[i].clear(),ct[i]=0;
fo(i,1,n){ int l=qread(),r=qread();a[i]={l,r};nums.PB(l),nums.PB(r);ans[i]=cnt[i]=0; }
sort(all(nums));
fo(i,1,n)
search(a[i].FR),search(a[i].SE),a[i].FR*=2,a[i].SE*=2,
on[a[i].FR].PB(i),on[a[i].SE+1].PB(i),ct[a[i].FR]++,ct[a[i].SE+1]--;
fo(i,1,n*5) ct[i]+=ct[i-1];
int real=0;
fo(pos,1,n*5)
{
for(auto i:on[pos]) if(now.count(i)) now.erase(i); else now.insert(i);//工具人,可以写成线性队列
if(ct[pos-1]==0 and ct[pos]>0) real++;
if(ct[pos-1]!=1 and ct[pos]==1) ans[*now.begin()]++;
if(ct[pos-1]==0 and ct[pos]==1) ans[*now.begin()]--;
if(ct[pos]==1 and ct[pos+1]==0) ans[*now.begin()]--;
}int ret=-INF;fo(i,1,n) chmax(ret,ans[i]);write2(ret+real);

CF1282D Enchanted Artifact不会做

题意:交互题,不给出长度猜字符串S($|S| \le 300$,字符集为ab),每次询问字符串T,返回Edit distance,定义为每次做单字符的插入、替换、删除的最下次数,要求询问次数不超过$|S|+2$

请先思考后再展开

首先很容易求出字符串的长度:

询问 全a 全b 都有
“a” n-1 n-1 n
“b” n n-1 n-1

如果只有替换就是zz,但直接考虑这个代价不太好求。注意到如果是且仅当是子序列的时候,编辑代价就是n-长度,于是我们得到一个询问次数=$2n^2$的做法。然而并不会优化qwq

hint:输入n个a得到a、b的个数aa、bb

于是直接枚举每个间隔插入b就好了,次数=2+1+aa+bb。这个很好解决,改成输入300个a、b,次数变为n+2

code

CF1270E Divide Points不会做

题意:给出$n \le 1e3$个二维平面上整点,建完全图后分为两个集合A、B,边分为跨集合边和集合内边,要求相同长度的边是相同的种类,构造集合划分方案,保证输入有解

请先思考后再展开

很妙啊

注意到是整点,距离只需考虑欧几里得距离的平方

hint:一个很容易验证的小结论:$奇^2+奇^2=2 \pmod 4,偶^2+偶^2=0 \pmod 4,奇^2+偶^2=1 \pmod 4$

于是很容易想到以某点为原点,按照两维奇偶性分成00,01,10,11四类

如果全部是00显然可以把所有坐标/2,无需考虑

如果01和10都没有,$A={00},B={11}$;如果有,$A={00,11},B={01,10}$

CF1268C K Integers不会做

题意:给出排列p,每次可以交换相邻两个元素,对于所有k回答搞出$1,2,3…k$这样的连续段所需最小时间

请先思考后再展开

核心观察:一定是先把1到k拼成连续一段且原顺序不变,然后再内部排序(只能说玩一玩感觉挺对的),容易发现两过程独立

得出式子就随便做了,逆序对部分显然随便求,移动部分就是个中位数(尽管和常见的“移动到相同位置”不完全相同,推推式子就是比常规的少$\frac{k^2-[k\&1]}{4}$),建议写树状数组

1
2
3
4
5
6
7
fo(i,1,n) pos[qread()]=i;
fo(k,1,n)
{
b0.ad(pos[k],1),b1.ad(pos[k],pos[k]);int mid=b0.findk(k/2+1);
sum+=pos[k];ans+=k-b0.ask(pos[k]);
write1( ans+sum-2*b1.ask(mid-1)+(k&1?-mid:0)-(1ll*k*k-k%2)/4 );
}

CF1254C Point Ordering会做

题意:交互题,平面上有$n \le 1e3$个整点形成凸多边形且给出n,没有三点共线,询问最多3n次,每次可以询问$\overrightarrow{a_ia_j}与\overrightarrow{a_ia_k}$叉积的绝对值或符号,最后逆时针从点1开始逆时针输出该多边形

请先思考后再展开

很容易发现可以直接给2到n排序,$a_i<a_j当且仅当ask2(a_1,a_i,a_j)>0$,然而需要nlogn次,试图化叉积的式子或者割补法,无果,遂自闭30min。忽然想起有种东西叫三角形面积等底看高,所以可以找出逆时针第一个作为底,找到最高那个(可能是两个),然后枚举其他人判断是在左侧还是右侧,两侧内部就能直接根据高排序,询问次数为$3n$

1
2
3
4
5
6
7
8
9
10
11
12
bool small(int x,int y){ printf("2 1 %d %d\n",x,y);fflush(stdout);return qread()>0; }
ll val[N];bool cmp(int x,int y){return val[x]<val[y];}
void main()
{
int n=qread();int mi=2;fo(i,3,n) if(small(i,mi)) mi=i;
fo(i,2,n) if(i!=mi) { printf("1 1 %d %d\n",mi,i);fflush(stdout);val[i]=qread(); }
int top=0;fo(i,2,n) if(i!=mi and val[i]>val[top]) top=i;
fo(i,2,n) if(i!=mi and i!=top and val[i]==val[top] and small(i,top)) top=i;
vc<int> left,right;fo(i,2,n) if(i==top or small(i,top)) left.PB(i); else right.PB(i);
sort(all(left),cmp);sort(all(right),cmp);reverse(all(right));
printf("0 1 ");for(auto in:left) write1(in);for(auto in:right) write1(in);fflush(stdout);
}

CF1252E Songwriter不会做

题意:给出一个长度为$n \le 1e5$的序列,问能否保证大小关系($<,=,>$)不变的前提下,使相邻的差不超过K且所有数$\in [L,R]$,若有解输出最小字典序方案

请先思考后再展开

惭愧啊……从后往前得到合法范围(即这里这样选后面都能合法,显然是连续一段区间),从前往后取值就好了啊

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int n=qread(),L=qread(),R=qread(),K=qread();
fo(i,1,n) a[i]=qread(); ok[n]={L,R};
fd(i,n-1,1)
{
ok[i]=ok[i+1];
if(a[i]<a[i+1]) ok[i].FR-=K,ok[i].SE--;
if(a[i]>a[i+1]) ok[i].FR++,ok[i].SE+=K;
chmax(ok[i].FR,L),chmin(ok[i].SE,R);
if(ok[i].FR>ok[i].SE) {puts("-1");return;}
}
int lst=ok[1].FR;write1(lst);
fo(i,2,n)
{
if(a[i-1]<a[i]) lst=max(lst+1,ok[i].FR);
if(a[i-1]>a[i]) lst=max(min(lst-K,ok[i].SE),ok[i].FR);
write1(lst);
}

CF1252G Performance Review会做

题意:给出n个数,经过m天,每天会删除最小的$R_i$个数并加入给定的$R_i$个数,保证所有输入中数字都互不重复,q次修改某天$R_i$个数中某个数,并回答按现在的表格模拟m天后最开始的第一个数是否还没有被删除,$n,m,q \le 1e5,\sum r_i \le 1e6$

请先思考后再展开

回答的只是第一个数是否活着。于是就很容易了,只关心$<a_i$​的数的个数,每次先加后减(最后一次显然没用),那等价于m个数,看是否存在一段前缀和<0,线段树上直接维护前缀和,后缀修改,找最小值即可

CF1251E Voting会做

题意:要说服$n \le 2e5$个人投票,要么花$p_i$收买他,要么让其他投票的人达到$m_i$,求最小代价

请先思考后再展开

按照m从小到大排序,发现即使前一个满足(前面的人都满足)了后一个也不一定满足,此时需要在后面收买若干个人,从后往前贪心即可

1
2
3
4
5
6
7
int n=qread();fo(i,1,n) a[i].FR=qread(),a[i].SE=qread();sort(a+1,a+n+1);
priority_queue< int,vc<int>,greater<int> > que;int have=0;ll ans=0;
fd(i,n,1)
{
while(sz(que) and i-1+have<a[i].FR) ans+=que.top(),que.pop(),have++;//mi<n
que.push(a[i].SE);
}write2(ans);

CF1250C Trip to Saint Petersburg会做

题意:给出K和$n \le 2e5$个区间,选出集合S最大化$\sum \limits_{i \in S} p_i - K(R - L + 1),L=\min_ \limits{i \in S} l_i,R=\max \limits_{i \in S} R_i$,多解输出任意一种

请先思考后再展开

只要计算出最优的$[L,R]$,于是枚举L,如果离开区间的左端点就删除该区间,线段树维护每个右端点此时的贡献,那么就是后缀加K,后缀减val,后缀求最大值的位置,$O(nlogn)$

CF1245E Hyakugoku and Ladders会做

题意:给出一个$10*10$的表格,上面的数字大小表示有个向上多少行的梯子(起点一定没有)。现在从左下角出发到达左上角,每次摇一个6面的骰子,走上面数字步(按照题中图片一样蛇形走,如果距离终点少于该步数则不移动),然后此时的格子如果有梯子可以选择上爬(必须从起点完整爬到梯子终点,且到达后不能立刻再爬梯子),问期望摇骰子次数

请先思考后再展开

$$
记终点为0,dp(i,0/1=是否刚爬过梯子) \\
对于i \le 6,dp(i,0)=dp(i,1)= \sum \frac{dp(ii,0)+1}{6}+(dp(i,0)+1)*\frac{max(0,6-i)}{6} \\
otherwise,dp(i,1)= \sum \frac{dp(ii,0)+1}{6},dp(i,0)=min{ dp(i,1),1+dp(ii,1) }
$$
code

CF1245F Daniel and Spring Cleaning会做

题意:$T \le 100$组数据,每次求$\sum_{L \le a,b \le R} [a\&b=0]$,$0 \le L,R \le 1e9$

请先思考后再展开

这种二进制连续段的题,先考虑形如$Axxxx$,其中xxx任填的方案数(记录为$[A,A+2^a-1]$)自己内部做,根据经典的$\sum_{s \subseteq S} s的补集的子集数=3^n$即可。现在不规则,容斥,设计函数$solve(<R1,<R2)$,那么$ans=solve(R+1,R+1)-solve(L,R+1)-solve(R+1,L)+solve(L,L)$(当然不想容斥可以用线段树划分法)

考虑$[A,A+2^a-1]与[B,B+2^b-1],a \le b$的答案,显然首先要求$A \& B=0$,然后a多出来的那部分会有一定限制,$3^a*2^{多出来部分多少个0}$,复杂度为$O(Tlog^2)或O(Tlog^3)$

code

CF1244F Chips会做

题意:给出一个环形的01序列,做k次,每次对于一个位置考虑相邻及自己三个位置,值就变成出现最多的那种数,$n \le 2e5$

请先思考后再展开

AGC006D Median Pyramid Hard很像,不过因为很简单问题不大。就很容易发现连续同色如果长度>1一定永远不变,于是可以把序列分割成若干个独立的段(特判整个串01交替,看k奇偶性即可)。每个段讨论两边01情况,无论怎样每做一次就会变短2,且如果两边数字不同要01反转。

CF1238F The Maximum Subtree会做

题意:给出一棵$n \le 3e5$个点的树,要求选出最大的连通子图G,使得能够构造出一组方案,每个点分配一条一维线段,断开原先的边后给所有线段相交的点对连边,得到的图与G一致(带标号)

请先思考后再展开

显然每个点最多连向两个非叶节点,这是个必要条件。很容易通过构造发现这也是个充要条件(叶子直接包含在里面),那么将ans=2判掉后,与非叶相邻的点构成一条链,贪心地选每个点旁边的边(这东西或许应该叫毛毛虫——HAOI2009

直接dp这条链,code,当然化式子写成带权直径也是资瓷的

CF1228E Another Filling the Grid会做

题意:计数,给大小为$n \le 250$的方阵填数,值域为K,要求每行每列最小值都是1

请先思考后再展开
1
fo(i,0,n) fo(j,0,n) { int S=(n-i)*(n-j);add(ans, 1ll*C[n][i]*C[n][j]%MOD*((i+j)&1?MOD-1:1)%MOD*qpower(K,S)%MOD*qpower(K-1,n*n-S)%MOD ); }write(ans);

CF1217E Sum Queries不会做

题意:给出n个数m次操作,每次修改一个数或询问区间内的好的多重子集中和最小的,不存在输出-1,定义好为没法通过 「 每个十进制数位独立从集合内某个元素中选出」来得到集合的和,$n,m \le 2e5$

请先思考后再展开

因为是求最小可以考虑枚举某个数位,固定它没法选出

核心观察:为了满足这一位的限制,选最小两个「这一位非0」的数一定是最优的,因为任何合法方案肯定需要选至少两个这种数

无地自容啊……怪不得还附带了这么多花里胡哨的操作,性质过于优美,直接建10个线段树就好了,$O(nlog^2)$

CF1216E Numerical Sequence会做

题意:存在一个无穷大的十进制数形如”1|12|123|1234|12345|123456|….”(分隔符实际不存在),$q \le 500$次询问第$k \le 1e18$高数位上的$digit \in [0,9]$

请先思考后再展开
1
2
ll F(ll R){ ll ret=0;fo(t,0,9){ ll tt=R-dec[t]+1;if(tt>0) ret+=tt; }return ret; }
ll S(ll R){ ll ret=0;fo(t,0,9){ ll tt=R-dec[t]+1;if(tt>0) ret+=tt*(tt+1)/2; }return ret; }

然后直接两次二分,$O(Tlg^2)$

完整code

Codeforces 2400pt

CF1283F DIY Garland不会做

题意:定义一个从带标号有根树到序列的映射为,点x点权$2^x$,边权为子树内点权和,按边权从大到小枚举边并写下这条边深度较小的那个节点编号,现在给出这个序列,构造一棵能映射到该序列的有根树,$n \le 2e5$

请先思考后再展开

可小到大处理每条边,那么这时候只要知道深度较大那个点,其实本质上就是要对子树点权和排序,只要能排序就能告诉你其父亲是什么,将一开始的叶子塞到堆中,得到父亲的时候类似拓扑处理即可

无解是瞎判的,貌似没有这种数据(即-1的意思好像是还原的条件不够充足?总之当构造做问题不大)

1
2
3
4
5
6
7
8
9
10
int n=qread();fo(i,1,n-1) a[i]=qread(),cnt[a[i]]++;
fo(i,1,n) if(!cnt[i]) q.push({i,i});
fo(i,1,n) mx[i]=i;
fd(now,n-1,1)
{
if(!sz(q)){ puts("-1");return; }
int x=a[now],y=q.top().SE;chmax(mx[x],q.top().FR);q.pop();
ans.PB({x,y});cnt[x]--;done[y]=1;if(!cnt[x]) q.push({mx[x],x});
}int rt=0;fo(i,1,n) if(!done[i]){ if(rt){puts("-1");return;}else rt=i; }
write2(rt);for(auto t:ans) write1(t.FR),write2(t.SE);

CF1282E The Cake Is a Lie会做

题意:存在一个未知编号排列的正n边形,给出一种三角剖分(形式为n-2个三角形的三点),依次求出一个表示编号顺序的排列,以及满足该编号的一个n-2的排列表示三角形被切割出来的顺序,要求按照这个顺序依次删掉的那个三角形是在边上的(即剩下的还是一个凸多边形),输入和输出都不保证顺逆时针,$n \le 1e5$

请先思考后再展开
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
struct S{int x,y,z;}a[N];set<int> on[N],go[N];
bool vis[N];void dfs(int x){ vis[x]=1;write1(x);for(auto y:go[x]) if(!vis[y]) dfs(y); }
int n;queue<int> q;vc<int> ans;
void solve(int cnt)
{
int now=q.front();q.pop();int id=*on[now].begin();ans.PB(id);
int x=a[id].x,y=a[id].y,z=a[id].z;if(y==now) swap(y,x);if(z==now) swap(z,x);
#define upd(pt) on[pt].erase(id);if(sz(on[pt])==1) q.push(pt);
#define ins(x,y) go[x].insert(y),go[y].insert(x)
#define del(x,y) go[x].erase(y),go[y].erase(x)
upd(y);upd(z);
if(cnt==n-2) ins(x,y),ins(x,z),ins(y,z);
else solve(cnt+1),del(y,z),ins(x,y),ins(x,z);
}
void main()
{
int T=qread();
while(T--)
{
n=qread();fo(i,1,n) on[i].clear(),go[i].clear(),vis[i]=0;
fo(i,1,n-2) on[a[i].x=qread()].insert(i),on[a[i].y=qread()].insert(i),on[a[i].z=qread()].insert(i);
while(sz(q)) q.pop();ans.clear();fo(i,1,n) if(sz(on[i])==1) q.push(i);solve(1);
dfs(1);puts("");for(auto in:ans) write1(in);puts("");
}
}

CF1272F Two Bracket Sequences会做

题意:给出两个不一定合法的括号串A和B($|A|,|B| \le 200$),构造一个最短的合法括号串,使得A和B都是其子序列

请先思考后再展开

直接dp,代码是随便写的

CF1260E Tournament会做

题意:$2^n(n \le 18)$个人打淘汰赛,收买第i个人的代价为$a_i$,其中$a_i=-1$的是你,任意决定分组方案(要做n-1次两两分组)去最小化你会遇到的每个原本其实打不过的对手,两人对战总是编号大的人获胜,但你总是获胜

请先思考后再展开

$收买n来负责大小为n/2的子树,收买[\ge n/2]来负责大小为n/4的子树……$

1
2
priority_queue<int,vc<int>,greater<int>> q;ll ans=0;
fd(i,n,1){ if(a[i]<0)break;q.push(a[i]);if(bin((int)log2(i))==i) ans+=q.top(),q.pop(); }write(ans);

CF1239D Catowice City会做

请先思考后再展开

因为要选出n个,猫的编号一定是人的补集,则边$(x \to y)$等价于选了x必须选y做人,没必要无脑2-sat,实际上就是要找这个dag中出度为0且不是整个图的强联通分量,code

CF1221E Game With String不会做

请先思考后再展开

核心观察:只要存在A类线段($ln \in [b,a)$),bob必胜

于是,只要轮到bob操作时存在B类线段($ln \ge 2b$),就能制造出A类线段,所以Alice的首要目标是去掉B类线段,接下来只要考虑能去掉。此时bob先手且只存在C类线段($ln \in [a,2b)$),无论是谁都只能操作一次,直接看奇偶性即可

CF1183F Topforces Strikes Back不会做

题意:多组数据,给出n个数,选出最多三个数,要求互不为倍数,最大化其和,$\sum n,a_i \le 2e5$

题解,只想到了一个最多三个小log的不优美做法

CF1179C Serge and Dining Room会做

题意:m男找n女,依次处理每个男,记权值为$a_i$,在剩女中找最大的$b_j \le a_i$并娶走,没有就放弃。q次修改a或b,要求快速模拟这个过程后回答剩女中最大的a,$n,m \le 3e5$

请先思考后再展开

很容易发现,我们其实就是要知道是否最大的若干个女孩都有主了,其实就是$\forall i,\sum_{j} [b_j \ge a_i] \ge n-i+1$

那么b的顺序是没有意义的,直接写个权值线段树维护最小值即可,求答案就在上面二分,$O(nlogn)$,code

CF1120D Power Tree会做

题意:给出一棵$n \le 2e5$点有根树,控制点x的代价为$w_x$,控制后可以给子树内叶子加任意整数,花最小的代价使得无论初始叶子上有什么数,都能操作为0

请先思考后再展开

容易发现其实就是要保证每个叶子向上跳第一个碰到的控制节点存在且互不同,可以随便写个线性dp,类似这样

但这并不是我想说的重点,题解给出的做法很有趣:问题丢到序列上,然后就是要能让差分数组变成0。我们发现建图$(l_i,r_i+1)$的话,只要形成一棵树,就能以cnt+1那个虚点为根,从下往上处理叶子,所以转化成了最小生成树。

Codeforces 2500pt

CF1284E New Year and Castle Construction不会做

题意:给出n个二维平面点,没有三点共线,求$\sum_{x} 选4个点构成四边形严格enclose\ x$

请先思考后再展开

核心观察:考虑五个点形成三点凸包、四点凸包、五点凸包的方案数分别为x3、x4、x5,则$ans=2x3+x4=5(x3+x4+x5)-(3x3+4x4+5x5)=2x3+x4=5C_n^5-(3x3+4x4+5x5)$

问题转化为统计每条边是5-set形成的凸包上一条边的方案数,直接以每个点为原点做极角排序后2-point即可

CF1263F Economic Difficulties会做

题意:看题图,上下两棵树大小分别为A和B,叶子数都是n,每棵树都存在一种dfs顺序使得遍历到的排气扇编号从1到n,排气扇连接那两个叶子给定且不重,然后删除最多的边(图中为红色)使得每个排气扇至少能访问到一个树根。$n \le 1e3,A,B \le 2e3$

请先思考后再展开

决策题优先考虑网络流,二选一试图最小割,与S连通表示选择A,记割掉表示保留这条边,排气扇与叶子间、树边流量为INF,去留由叶子与父亲那条边反映,则A树某条边必须被割当且仅当子树有人与S连通,故$(A_x \to ed,1)$,B树则是$(st \to B_x,1)$

1
2
3
4
int n=qread();using namespace MF;st=0,ed=MAX_N-1;
int A=qread();fo(x,2,A) ins(x,qread(),INF),ins(x,ed,1);fo(i,1,n) ins(A+i,qread(),INF);
int B=qread();fo(x,2,B) ins(A+n+qread(),A+n+x,INF),ins(st,A+n+x,1);fo(i,1,n) ins(A+n+qread(),A+i,INF);
int ans=0;while(bfs()) ans+=dfs(st,INF);write(A-1+B-1-ans);

CF1239B The World Is Just a Programming Task不会做

题意:给出一个长度为$n \le 3e5$的括号序列,交换两个不一定不同的位置,最大化$\sum_i [将序列shift\ i后是合法括号序列]$

请先思考后再展开

我的思路:首先转化为-1和1,则位置i作为结尾的条件为$\min S[1..i]\ge S_i-S_n且\min S[i+1..n] \ge S_i$,然后如果从

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
正解:其实括号对于+1-1有个优势,就是哪两个括号匹配是确定的。因此对于合法括号序列,可行位置数就是一级括号数+1。
对于本题,先把序列调整为一个合法括号序列(一定存在),然后容易发现如果交换一个一级括号两端,答案为内部二级+1,如果交换一个二级括号两端,答案为内部三级+整体一级+1,显然交换三级括号没有意义
```cpp
int n=qread();scanf("%s",str+1);fo(i,n+1,n+n) str[i]=str[i-n];
fo(i,1,n) S[i]=S[i-1]+(str[i]=='('?1:-1);
pre[0]=INF;fo(i,1,n) pre[i]=min(pre[i-1],S[i]);suf[n+1]=INF;fd(i,n,1) suf[i]=min(suf[i+1],S[i]);
if(S[n]!=0) {printf("0\n1 1");return;}
int st=0;fo(i,0,n-1) if(suf[i+1]>=S[i] and pre[i]>=S[i]-S[n]) st=i+1;deb(st);
int sum=0,one=0;
fo(i,st,st+n-1)
{
if(str[i]=='(') sum++,cnt[sum]++;
else{ if(sum==1) one++;cnt[sum+1]=0;sum--; }
}
pair<int,pii> ans={one,{1,1}};
fo(i,st,st+n-1)
{
if(str[i]=='(') sum++,cnt[sum]++,lst[sum]=i;
else{ if(sum==1) chmax(ans,{cnt[2]+1,{lst[1],i}});if(sum==2) chmax(ans,{cnt[3]+one+1,{lst[2],i}});cnt[sum+1]=0;sum--;}
}printf("%d\n%d %d",ans.FR,(ans.SE.FR>n?ans.SE.FR-n:ans.SE.FR),(ans.SE.SE>n?ans.SE.SE-n:ans.SE.SE));

CF1221F Choose a Square不会做

题意:给出$n \le 5e5$个带权点,有负权,选择$a<b得到正方形(a,a)-(b,b)$,最大化$被其包含的点权和-(b-a)$

请先思考后再展开

发现是个切比雪夫距离,化成曼哈顿距离后发现了一些优美的性质,但没能优化复杂度

事实上直接按题意说的考虑就好了,点$(x,y)被覆盖当且仅当a \le min(x,y),b \ge max(x,y)$,那直接扫描线整体改权即可

CF1218E Product Tuples会做

题意:给出长度为$n \le 2e4$的序列A和常数K,$Q \le 10$次独立操作,每次对A单点修改或区间加,然后对给定值q定义序列$B_i=q-A_i$,输出$\sum_{ T \in {1,2..n},|T|-K} \prod_{x \in T} B_x$

请先思考后再展开

又是国人擅长的多项式套路题,$ans=[x^k]\prod(1+a_ix)$,看到Q这么小就感觉不对劲,直接重新做就好了,$O(Qnlog^2)$,code

CF1202E You Are Given Some Strings会做

题意:给出字符串T和n个字符串si,输出$\sum_{i=1}^n \sum_{j=1}^n 「s_i和s_j的拼接」在T中出现次数$,$|T|,n,\sum s_i \le 2e5$

请先思考后再展开

计算$\sum_{i} 以i结尾的s个数*以i+1开头的s个数$,就是个sam子树加,code

*日,好像目前会做的2500都是因为过于套路……*

CF1197F Coloring Game不会做

题意:给出n个纸条,第i条有ai个格子,在最后一格放一枚棋子,每次可以选一个棋子往前移动1、2、3格,但不能移出去,alice先手,不能移动的输。同时格子有3种颜色,给出大小为3的矩阵,$M_{i,j}=能否从颜色i的格子移动j步$,初始只有m个位置有颜色,其他由bob染色,对bob必胜的染色方案计数,$n,m \le 1e3,a_i \le 1e9$

请先思考后再展开

很容易想到把三个状态压成64做矩乘,复杂度为$O((n+m)64^3loga)$,仔细思考了半天,成功想到了分块压复杂度,从30变成了5,高兴地打开计算器,粗言秽语

核心观察:$ans=A[1*4^2+2*4+3*4^0][S]$,只关心这一行,所以不要快速幂,预处理下二进制幂后,每次向量右乘矩阵就完事了,$O((n+m)64^2loga+64^3loga)$,小技巧get

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int n=qread();fo(i,1,n) a[i]=qread();
int m=qread();while(m--){ int x=qread(),y=qread();in[x].PB({y,qread()}); }
fo(i,1,n) in[i].PB({a[i]+1,0}),sort(all(in[i]));
fo(i,0,2) fo(j,0,2) ok[i][j]=qread();
fo(i,0,3) fo(j,0,3) fo(k,0,3) go[i][j][k]=i*16+j*4+k;
fo(col,0,2) fo(a,0,3) fo(b,0,3) fo(c,0,3)
{
bool use[4];mem(use,0);
if(ok[col][0]) use[c]=1;if(ok[col][1]) use[b]=1;if(ok[col][2]) use[a]=1;
int sg=3;fd(i,2,0) if(!use[i]) sg=i;
add(A[col].a[go[a][b][c]][go[b][c][sg]],1),add(B[0].a[go[a][b][c]][go[b][c][sg]],1);
}
fo(i,1,30) B[i]=B[i-1]*B[i-1];f[0]=1;
fo(i,1,n)
{
Mat now;now.n=1;now.a[0][go[1][2][3]]=1;int lst=0;
for(auto t:in[i])
{
int ln=t.FR-lst-1;lst=t.FR;
fo(j,0,30) if(ln&bin(j)) now=now*B[j];
if(lst<=a[i]) now=now*A[t.SE-1];
}
mem(g,0);fo(lst,0,3) fo(a,0,3) fo(b,0,3) fo(c,0,3) add(g[lst^c],f[lst]*now.a[0][go[a][b][c]]%MOD );swap(f,g);
}write(f[0]);

CF1194F Crossword Expert会做

题意:依次做n道题,第i道题需要花$t_i$的时间,另外有$50\%的概率多花1$,问T秒末时完整做完的题目数量,$n \le 2e5,t_i \le 1e9$

请先思考后再展开

直接枚举恰完成了第i个任务,不等式得到在前i+1个+1次数的范围,发现形如$(T-S-t_{i+1}-ad_{i+1},T-S]$,每个i的范围不重,暴力求复杂度就是对的

1
2
3
4
5
6
7
8
9
10
11
int n=qread();ll T=qread();fo(i,1,n) t[i]=qread();t[n+1]=T;
fo(i,1,n)
{
ll l=0,r=i;S+=t[i];chmin(r,T-S);ll P=qpower(2,MOD-1-i-(i<n));
if(i<n)//ad[i+1]=1
{
ll l2=l;chmax(l2,T-S-t[i+1]-1+1);
if(l2<=r) fo(t,l2,r) add(ans, C(i,t)*i%MOD*P%MOD );//debug 爆int
}
chmax(l,T-S-t[i+1]+1);if(l<=r) fo(t,l,r) add(ans, C(i,t)*i%MOD*P%MOD ); //ad[i+1]=0
}write(ans);

CF1188A Add on a Tree不会做

题意1:给出一棵$n \le 2e5$个点的无根树,每次可以选两个叶子和任意实数,然后给路径上的边加该实数,问是否能得到任何样子的边带权树

题意2:给出一棵$n \le 1e3$个点的无根树,边权初始为0,每次可以选两个叶子和任意整数,然后给路径上的边加该整数,问是否能得到给定的边权方案,边带偶权且互不相同

请先思考后再展开

先给出第二题的构造方法:选一个叶子为根rt方便操作,然后从上到下处理每条边$(fa \to x)$,使其加X,那么x子树内的边不用管,只要保证其他边没有变化就行。此时如果你考虑“找子树内两个叶子”,这显然是不可行的,因为可能x是叶子;事实上应该考虑“找x某个兄弟内的叶子”,这个只要保证所有点度不是2就行了。

设x内是a,另一个是b,则$(rt,a)+=X/2,(a,b)+=X/2,(rt,b)-=X/2$即可,实现只要预处理叶子后dfs,暴力改边权即可

那现在“所有点度不是2”这种情况已经解决,如果没有这个条件,发现一定有两条边始终相同,而题目保证不同,所以一定无解。

code

树状数组容易做到nlogn,已经不好卡,顺手编了个没写的线性做法:钦定每个子树的偏爱叶子节点,这样只需要把那个路径加传递给和自己偏爱叶子相同的那个孩子

此时再讲第一题是显然的,当然实际做题时比较适合先用第一题验证结论

1156F

题意

请先思考后再展开

1152E

题意

请先思考后再展开

1148F

题意

请先思考后再展开

1141G

题意

请先思考后再展开

1137D

题意

请先思考后再展开

1136E

题意

请先思考后再展开

1117G

题意

请先思考后再展开

1114F

题意

请先思考后再展开

1111D

题意

请先思考后再展开

1101F

题意

请先思考后再展开

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