CFR633

CFR633 div1

终于到达2300啦!明明这周没做过cf和atc,每天胡策被迫早起还被按在地上摩擦,手感下降了挺多的还很困,大概这就是lucky

CF1338A Powered Addition

请先思考后再展开

每次一定操作一段后缀

1
2
3
4
5
int ans=0,mx=a[1];
fo(i,2,n)
if(a[i]<mx){ int wt=mx-a[i];chmax(ans, (int)log2(wt)+1 ); }
else mx=a[i];
write2(ans);

CF1338B Edge Weight Assignment

题意:给一棵树$n \le 1e5$,可以给每条边分配任意正整数权值,要求任意两个叶子路径异或和=0,求最小和最大的不同权值个数

请先思考后再展开

以某个叶子为根肯定方便考虑,则要求所有叶子到根路径异或和相等

最少的话,如果所有叶子深度都是偶就是1,否则让最后一条边去调整就是3;

最多的话,可以给每条非叶子边编号,然后第i条边上就是$2^i$,这样数量就是$n-1-\sum (x上挂着的叶子数-1)$

1
2
3
4
5
6
7
8
9
10
11
vc<int> to[N];int mi=1,mx=0;set<int> FA;
void solve(int x,int fa,int dep=0)
{
bool out=0;for(auto y:to[x]) if(y!=fa) solve(y,x,dep+1),out=1;
if(!out){ if(dep&1) mi=3;if(dep!=2) FA.insert(fa); } else if(fa>0) mx++;
}
void main()
{
int n=qread();fo(i,2,n){ int x=qread(),y=qread();to[x].PB(y),to[y].PB(x); }
int rt;fo(i,1,n) if(sz(to[i])==1) rt=i;solve(rt,0);write1(mi),write(sz(FA)+mx);
}

CF1338C Perfect Triples

请先思考后再展开

首先是OEIS,发现没有

以3个为单位打个表,发现第一个好像有点规律,异或嘛用二进制以三个一组输出看看,发现每组是$2^0,2^2,2^4..$个,然后每组第一个可以直接求($2^i$开头),第二个去掉开头的$2^{i+1}$后,是个四进制

写起来看上去不短,实际上规律特别好找,而且也没啥细节,挺优美的

1
2
3
4
const int To[2][2]={{0,2},{3,1}};
ll n=qread()-1,m=n;n=n/3;int z=0;while(n>=bin(z+1)-bin(z)) n-=bin(z+1)-bin(z),z+=2;
ll A=bin(z)+n,B=bin(z+1);fo(i,0,30) B+=bin(i*2)*To[(n&bin(i*2+1))>0][(n&bin(i*2))>0];ll C=A^B;
if((m)%3==0) write2(A);if((m)%3==1) write2(B);if((m)%3==2) write2(C);

CF1338D Nested Rubber Bands

题意:给出一棵$n \le 1e5$的树,将每个点搞成一个封闭几何图形,要求两个图形相交当且仅当原本有边相连,求最大嵌套深度(i被i+1严格包含)

请先思考后再展开

经过手玩发现,相当于在树上找到一条路径,然后在路径以及距离路径为1的点中选最多的,不相邻的点(设选为1,不选为0,显然只需要考虑两个端点都是0的情况)。构造大概是一个端点在里面,然后0就是两个1中间的环,一个环上可以套多个,每个0的时候优先把不在路径上的那些1挂上,然后再继续沿着路径走

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int ans;
vc<int> to[N];int dp[N][2];
void solve(int x,int fa)
{
int pre[2]={0,0},sons=sz(to[x])-(fa>0);
for(auto y:to[x]) if(y!=fa)
{
solve(y,x);chmax(ans, pre[0]+dp[y][0]+1 );//i am 1
fo(op1,0,1) fo(op2,0,1) chmax(ans, pre[op1]+dp[y][op2]+sz(to[x])-2 );//i am 0
fo(op,0,1) chmax(pre[op],dp[y][op]);
}
fo(op,0,1) chmax(dp[x][0],pre[op]+sons-1);dp[x][1]=pre[0]+1;
chmax(dp[x][0],sons);chmax(ans,dp[x][0]+(fa>0));
}
void main()
{
int n=qread();fo(i,2,n){ int x=qread(),y=qread();to[x].PB(y),to[y].PB(x); }
solve(1,0);write(ans);
}//好像比很多人做法简洁

CF1338E JYPnation

咕咕咕

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