正文

Codeforces 1110 简要题解

IP云
IP云V管理员/3 阅读
10/01
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

文章目录

  • A题
  • B题
  • C题
  • D题
  • E题
  • F题
  • G题

传送门

众所周知ldxoildxoildxoi这种菜鸡选手是不会写HHH题的，因此该篇博客只有AAA题至GGG题的题解，实在抱歉。

A题

传送门

题意简述：给出b,kb,kb,k和a1,a2,...,aka_1,a_2,...,a_ka1​,a2​,...,ak​问bk−1a1+bk−2a2+...+akb^{k-1}a_1+b^{k-2}a_2+...+a_kbk−1a1​+bk−2a2​+...+ak​的奇偶性。

思路：分bbb的奇偶性讨论下就好。

代码：

#include<bits/stdc++.h>#define ri register int#define fi first#define se secondusing namespace std;typedef long long ll;typedef pair<int,int> pii;const int mod=998244353;inline int add(const int&a,const int&b){return a+b>=mod?a+b-mod:a+b;}inline int dec(const int&a,const int&b){return a>=b?a-b:a-b+mod;}inline int mul(const int&a,const int&b){return (ll)a*b%mod;}inline int ksm(int a,int p){int ret=1;for(;p;p>>=1,a=mul(a,a))if(p&1)ret=mul(ret,a);return ret;}const int N=1e5+5;int b,k,a[N];inline int read(){int ans=0;char ch=getchar();while(!isdigit(ch))ch=getchar();while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();return ans;}int main(){b=read(),k=read();int ans=0;bool f=b&1;if(!f){int x;while(k--)x=read();cout<<(x&1?"odd":"even");}else{for(ri i=k-1;~i;--i)ans+=read()&1;cout<<(ans&1?"odd":"even");}return 0;}

B题

传送门

题意简述：给出一条长为mmm的木板，上面有nnn个洞，你可以用不超过kkk段木板去补洞问覆盖的最小长度。

思路：

如果k≥nk\ge nk≥n直接输出nnn。

否则先把所有的用一根木板补。

然后可以抠掉中间k−1k-1k−1段，于是我们把所有连续的两个洞的距离放进堆里取前k−1k-1k−1大减掉即可。

代码：

#include<bits/stdc++.h>#define ri register int#define fi first#define se secondusing namespace std;typedef long long ll;typedef pair<int,int> pii;const int mod=998244353;inline int add(const int&a,const int&b){return a+b>=mod?a+b-mod:a+b;}inline int dec(const int&a,const int&b){return a>=b?a-b:a-b+mod;}inline int mul(const int&a,const int&b){return (ll)a*b%mod;}inline int ksm(int a,int p){int ret=1;for(;p;p>>=1,a=mul(a,a))if(p&1)ret=mul(ret,a);return ret;}const int N=1e5+5;int n,m,k,a[N];inline int read(){int ans=0;char ch=getchar();while(!isdigit(ch))ch=getchar();while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();return ans;}int main(){n=read(),m=read(),k=read();priority_queue<int>q;for(ri i=1;i<=n;++i)a[i]=read();sort(a+1,a+n+1);for(ri i=2;i<=n;++i)q.push(a[i]-a[i-1]-1);int delta=a[n]-a[1]+1;for(ri i=1;i<k;++i)delta-=q.top(),q.pop();cout<<delta;return 0;}

C题

传送门

题意简述：nnn次询问（n≤2000n\le2000n≤2000），每次给一个a(2≤a≤225−1)a(2\le a\le2^{25}-1)a(2≤a≤225−1)，问对于所有满足0&lt;b&lt;a0&lt;b&lt;a0<b<a的bbb，gcd(a&amp;b,agcd(a\&amp;b,agcd(a&b,a^b)b)b)的最大值是多少。

思路：

  1. 打表

    打表代码：

#include<bits/stdc++.h>using namespace std;int q,a,ans1[55]={0,2,3,4,7,8,15,16,31,32,63,64,127,128,255,256,511,512,1023,1024,2047,2048,4095,4096,8191,8192,16383,16384,32767,32768,65535,65536,131071,131072,262143,262144,524287,524288,1048575,1048576,2097151,2097152,4194303,4194304,8388607,8388608,16777215,16777216,33554431,33554432,67108863};int ans2[55]={0,3,1,7,1,15,5,31,1,63,21,127,1,255,85,511,73,1023,341,2047,89,4095,1365,8191,1,16383,5461,32767,4681,65535,21845,131071,1,262143,87381,524287,1,1048575,349525,2097151,299593,4194303,1398101,8388607,178481,16777215,5592405,33554431,1082401,67108863,22369621};inline int read(){int ans=0;char ch=getchar();while(!isdigit(ch))ch=getchar();while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();return ans;}int main(){q=read();while(q--) {a=read();int loc=upper_bound(ans1+1,ans1+51,a)-ans1;cout<<ans2[loc-1]<<endl;}return 0;}

  1. 考虑到分aaa的情况讨论
    1. a̸=2k−1a\not=2^k-1a̸​=2k−1那么取b=(2k−1)ab=(2^k-1)^ab=(2k−1)a即可，答案为2k−12^k-12k−1
    2. a=2k−1a=2^k-1a=2k−1，那么直接枚举其最大质因子，如果没有就输出111

正解代码：

#include<bits/stdc++.h>#define ri register int#define fi first#define se secondusing namespace std;typedef long long ll;typedef pair<int,int> pii;const int mod=998244353;inline int add(const int&a,const int&b){return a+b>=mod?a+b-mod:a+b;}inline int dec(const int&a,const int&b){return a>=b?a-b:a-b+mod;}inline int mul(const int&a,const int&b){return (ll)a*b%mod;}inline int ksm(int a,int p){int ret=1;for(;p;p>>=1,a=mul(a,a))if(p&1)ret=mul(ret,a);return ret;}const int N=1e5+5;inline int read(){int ans=0;char ch=getchar();while(!isdigit(ch))ch=getchar();while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();return ans;}inline int lowbit(const int&x){return x&-x;}inline void solve1(const int&x){int up=1;while(up<=x)up<<=1;cout<<up-1<<'\n';}inline void solve2(const int&x){for(ri i=2;i*i<=x;++i)if(x%i==0){cout<<x/i<<'\n';return;}puts("1");}int main(){for(ri x,tt=read();tt;--tt){x=read();if(lowbit(x+1)!=x+1)solve1(x);else solve2(x);}return 0;}

D题

传送门

题意简述：给nnn张大小不超过mmm的纸牌(n,m≤1000000)(n,m\le1000000)(n,m≤1000000)。

现在允许把满足任意一种条件的三张牌分为一组：

  1. 三张牌为连续自然数
  2. 三张牌相同

问分出来的最多的组数。

思路：

比赛的时候想了半天贪心发现是错的？手动滑稽233

然后就凉了。

考虑dpdpdp。

对于连续的三个数x,x+1,x+2x,x+1,x+2x,x+1,x+2，如果我们分成三次(x,x+1,x+2)(x,x+1,x+2)(x,x+1,x+2)消耗的牌和分成(x,x,x),(x+1,x+1,x+1),(x+2,x+2,x+2)(x,x,x),(x+1,x+1,x+1),(x+2,x+2,x+2)(x,x,x),(x+1,x+1,x+1),(x+2,x+2,x+2)是等价的。

于是对于连续的三张牌最多只用分两次(x,x+1,x+2)(x,x+1,x+2)(x,x+1,x+2)

于是我们定义状态fi,t1,t2f_{i,t1,t2}fi,t1,t2​表示对于值为1 i1~i1 i的牌，我们分t1t1t1次(i−1,i,i+1)(i-1,i,i+1)(i−1,i,i+1)，分t2t2t2次(i,i+1,i+2)(i,i+1,i+2)(i,i+1,i+2)，然后枚举fi+1,t2,t3f_{i+1,t2,t3}fi+1,t2,t3​转移一下就行了，注意转移的时候如果值为i+1i+1i+1的牌有剩的需要全部分成(i+1,i+1,i+1)(i+1,i+1,i+1)(i+1,i+1,i+1)

代码：

#include<bits/stdc++.h>#define ri register intusing namespace std;inline int read(){int ans=0;char ch=getchar();while(!isdigit(ch))ch=getchar();while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();return ans;}const int N=1e6+5;int f[N][3][3],a[N],n,m;int main(){n=read(),m=read();for(ri i=1;i<=n;++i)++a[read()];memset(f,-1,sizeof(f));f[0][0][0]=0;for(ri i=0;i<m+2;++i){for(ri t1=0;t1<=2;++t1){for(ri t2=0;t2<=2;++t2){if(~f[i][t1][t2]){for(ri t3=0;t3<=2;++t3){if(t1+t2+t3>a[i+1])continue;f[i+1][t2][t3]=max(f[i+1][t2][t3],f[i][t1][t2]+t3+(a[i+1]-t1-t2-t3)/3);}}}}}cout<<f[m+2][0][0];return 0;}

E题

传送门

题意简述：给出两个数列ana_nan​和bn(n≤100000)b_n(n\le100000)bn​(n≤100000)，可以对ai(2≤i≤n−1)a_i(2\le i\le n-1)ai​(2≤i≤n−1)进行如下操作：ai=ai−1+ai+1−aia_i=a_{i-1}+a_{i+1}-a_{i}ai​=ai−1​+ai+1​−ai​

问能否通过若干次操作使得a,ba,ba,b完全一样。

思路：

定义ci=ai−ai−1(i≤2),c1=a1c_i=a_i-a_{i-1}(i\le2),c_1=a_1ci​=ai​−ai−1​(i≤2),c1​=a1​

即ccc是aaa的差分数组。

发现每次操作就是交换cic_ici​和ci+1c_{i+1}ci+1​

于是把两个数列的差分数列排序看是否一样即可。

注意特判两个数的情况，这个时候并不能移动

代码：

#include<bits/stdc++.h>#define ri register int#define fi first#define se secondusing namespace std;typedef long long ll;typedef pair<int,int> pii;const int mod=998244353;inline int add(const int&a,const int&b){return a+b>=mod?a+b-mod:a+b;}inline int dec(const int&a,const int&b){return a>=b?a-b:a-b+mod;}inline int mul(const int&a,const int&b){return (ll)a*b%mod;}inline int ksm(int a,int p){int ret=1;for(;p;p>>=1,a=mul(a,a))if(p&1)ret=mul(ret,a);return ret;}const int N=1e6+5;inline int read(){int ans=0;char ch=getchar();while(!isdigit(ch))ch=getchar();while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();return ans;}int n,m,a[N],b[N],c[N],d[N];int main(){n=read();for(ri i=1;i<=n;++i)a[i]=read();for(ri i=1;i<=n;++i)c[i]=read();if(a[1]!=c[1]||a[n]!=c[n])puts("No"),exit(0);for(ri i=1;i<=n;++i)b[i]=a[i]-a[i-1],d[i]=c[i]-c[i-1];sort(b+1,b+n+1),sort(d+1,d+n+1);bool f=1;for(ri i=1;i<=n;++i)if(b[i]^d[i])f=0;if(f)puts("Yes");else puts("No");return 0;}

F题

传送门

题意简述：给一棵nnn个点的带边权树,有qqq次询问(n,q≤500000)(n,q\le500000)(n,q≤500000)，每次问你在所有dfsdfsdfs序在[l,r][l,r][l,r]之间的叶子结点跟xxx的最短距离。

思路：

考虑离线处理询问，把所有询问按照xxx归类，于是只需动态维护在dfsdfsdfs到某个节点的时候知道dfsdfsdfs序在一段区间的叶子到当前点的距离最小值。

我们先按照题目中说的顺序遍历处理出dfsdfsdfs序（其实就是用vectorvectorvector存边）以及每个点到根的distdistdist，然后把叶子结点的distdistdist放入线段树里，这样就处理出了所有点到根节点的答案，然后考虑一个点向儿子节点移动的时候所有叶子结点到自己距离的变化，即儿子的子树里的叶子整体减掉当前边边权，其余的叶子加上当前边边权即可。

代码：

#include<bits/stdc++.h>#define ri register int#define fi first#define se secondusing namespace std;inline int read(){int ans=0;char ch=getchar();while(!isdigit(ch))ch=getchar();while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();return ans;}typedef pair<int,int> pii;typedef long long ll;const int N=5e5+5;int n,m,fa[N],in[N],out[N],top=0,tot=0,q[N];ll dis[N],ans[N];vector<pii>e[N];struct Node{int l,r,id;};vector<Node>qry[N];namespace SGT{#define lc (p<<1)#define rc (p<<1|1)#define mid (l+r>>1)ll mn[N<<2],add[N<<2];inline void pushup(int p){mn[p]=min(mn[lc],mn[rc]);}inline void pushnow(int p,ll v){mn[p]+=v,add[p]+=v;}inline void pushdown(int p){if(add[p])pushnow(lc,add[p]),pushnow(rc,add[p]),add[p]=0;}inline void build(int p,int l,int r){add[p]=0;if(l==r){mn[p]=dis[q[l]];return;}build(lc,l,mid),build(rc,mid+1,r),pushup(p);}inline ll query(int p,int l,int r,int ql,int qr){if(ql<=l&&r<=qr)return mn[p];pushdown(p);if(qr<=mid)return query(lc,l,mid,ql,qr);if(ql>mid)return query(rc,mid+1,r,ql,qr);return min(query(lc,l,mid,ql,mid),query(rc,mid+1,r,mid+1,qr));}inline void update(int p,int l,int r,int ql,int qr,ll v){if(ql>r||qr<l)return;if(ql<=l&&r<=qr)return pushnow(p,v);pushdown(p);if(qr<=mid)update(lc,l,mid,ql,qr,v);else if(ql>mid)update(rc,mid+1,r,ql,qr,v);else update(lc,l,mid,ql,mid,v),update(rc,mid+1,r,mid+1,qr,v);pushup(p);}}inline int findl(const int&x){return lower_bound(q+1,q+top+1,x)-q;}inline int findr(const int&x){int ret=lower_bound(q+1,q+top+1,x)-q;return q[ret]>x?ret-1:ret;}void dfs1(int p){in[p]=++tot;for(ri i=0,v;i<e[p].size();++i)dis[v=e[p][i].fi]=dis[p]+e[p][i].se,dfs1(v);out[p]=tot;if(!e[p].size())q[++top]=p;}void dfs2(int p){for(ri i=0,l,r;i<qry[p].size();++i)ans[qry[p][i].id]=SGT::query(1,1,top,qry[p][i].l,qry[p][i].r);for(ri i=0,l,r,v,w;i<e[p].size();++i){v=e[p][i].fi,l=findl(in[v]),r=findr(out[v]),w=e[p][i].se;SGT::update(1,1,top,l,r,-w),SGT::update(1,1,top,1,l-1,w),SGT::update(1,1,top,r+1,top,w);dfs2(v);SGT::update(1,1,top,l,r,w),SGT::update(1,1,top,1,l-1,-w),SGT::update(1,1,top,r+1,top,-w);}}int main(){n=read(),m=read();for(ri i=2;i<=n;++i)fa[i]=read(),e[fa[i]].push_back(pii(i,read()));dfs1(1),SGT::build(1,1,top);for(ri i=1;i<=top;++i)q[i]=in[q[i]];for(ri i=1,x,l,r;i<=m;++i){x=read(),l=findl(read()),r=findr(read());qry[x].push_back((Node){l,r,i});}dfs2(1);for(ri i=1;i<=m;++i)cout<<ans[i]<<'\n';return 0;}

G题

传送门

题意简述：给出一棵树，上面有的点是白色的有的没有涂色，现在两个人轮流涂色，先手涂白色，后手涂黑色，当某一方涂出了一条长度为333的路径时宣告胜利，如果全部涂完都没有满足条件即是和局，问双方都采取最优策略的最终结果。

思路：显然后手赢是不可能的 ，这辈子都不可能的

那么只需判断先手能不能赢了。

这个初始局的白色很烦人，因此我们改改条件，对于一个初始为白色的点AAA，把它拓展成444个点：

然后其余的边还是连向AAA点，这个时候我们假如涂AAA后手一定会涂BBB，就回到了跟初始是白色等价的情况。

于是我们成功把问题转化成为了初始没有涂色的情况。

现在考虑先手胜利的条件：

第一种：



第二种：



第三种：



这种注意，方法是放最靠中间的两个：



这样子先手必胜。

注意这种情况中间的直链的长度必须要是奇数才行（大家可以手玩感受一下）

代码：

#include<bits/stdc++.h>#define ri register intusing namespace std;inline int read(){int ans=0;char ch=getchar();while(!isdigit(ch))ch=getchar();while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();return ans;}const int N=5e5+5;int n=0,du[N*4],cnt[2];vector<int>e[N*4];char s[N];void dfs(int p,int fa,int dist){if(e[p].size()>=3)++cnt[dist];for(ri i=0,v;i<e[p].size();++i)if((v=e[p][i])^fa)dfs(v,p,dist^1);}inline bool solve(const int&p){if(du[p]>=4)return 1;if(du[p]<=2)return 0;int cnt=0;for(ri i=0;i<e[p].size();++i)if(du[e[p][i]]>1)++cnt;return cnt>=2;}inline void add(int u,int v){e[u].push_back(v),++du[u];e[v].push_back(u),++du[v];}int main(){for(ri tt=read(),tot;tt;--tt){for(ri i=1;i<=n;++i)e[i].clear(),du[i]=0;n=read(),cnt[0]=cnt[1]=0;for(ri i=1,u,v;i<n;++i)u=read(),v=read(),add(u,v);scanf("%s",s+1),tot=n;for(ri i=1;i<=n;++i)if(s[i]=='W'){++tot;add(i,tot),add(tot,tot+1),add(tot,tot+2),tot+=2;}n=tot,dfs(1,0,0);if(cnt[0]>1||cnt[1]>1){puts("White");continue;}bool flag=0;for(ri i=1;i<=n;++i)flag|=solve(i);puts(flag?"White":"Draw");}return 0;}