【超好懂的比赛题解】CodeforcesRound#747(Div.2)

title :Codeforces Round #747 (Div. 2)
date : 2021-10-9
tags : ACM,练习记录
author : Linno

题目链接 &＃xff1a;https://codeforces.com/contest/1594

补题进度 &＃xff1a;已补完

这次做得可谓是相当差了&＃xff0c;A题想复杂、C题调一小时重写才过&＃xff0c;E题十分钟写完没交上去。总之还是太菜了。

题意

给一个n,求L和R&＃xff0c;使得[L,R]中所有整数加起来等于n。

思路

对于正数&＃xff0c;我们知道n&＃61;sum[n]-sum[n-1]&＃xff0c;我们要减去n前面那一坨&＃xff0c;只需要取负数的同样位置即可&＃xff0c;即L&＃61;-n&＃43;1,R&＃61;n。负数同理。

代码

#include
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int maxn&＃61;2e5&＃43;7;
const int mod&＃61;1e9&＃43;7;int t,n,L,R;signed main(){cin>>t;while(t--){cin>>n;if(n>0){L&＃61;-n&＃43;1,R&＃61;n;}else L&＃61;-n&＃43;1,R&＃61;n;cout<}

B-Special Numbers

题意

给出n,k&＃xff0c;求第k个【n的幂集子集】之和的大小。

思路

考虑二进制&＃xff0c;第k大的数其实就是k&＃xff0c;普及到其他进制&＃xff0c;也不过是把k二进制拆分&＃xff0c;k&＃61;1010表示第10大的数是n3&＃43;n1n^3&＃43;n^1n3&＃43;n1

代码

#include
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int maxn&＃61;2e5&＃43;7;
const int mod&＃61;1e9&＃43;7;int fpow(int a,int p){int res&＃61;1;while(p){if(p&1) res&＃61;res*a%mod;a&＃61;a*a%mod;p>>&＃61;1;}return res;
}int t,n,k,ans,cnt;signed main(){cin>>t;while(t--){cin>>n>>k;ans&＃61;0;cnt&＃61;0;while(k){if(k&1){ans&＃43;&＃61;fpow(n,cnt);ans%&＃61;mod;}k>>&＃61;1;cnt&＃43;&＃43;;}cout<}

C-Make Them Equal

题意

求多少次操作可以使得n长的字符串全为ch&＃xff0c;每次操作可选择[1,n]中的一个数x&＃xff0c;所有除不尽x的位置全部变为ch。

思路

很考察细节。很容易想到最多两次操作就能完成&＃xff0c;对于这种情况我们都可以取pos1&＃61;n-1,pos2&＃61;n&＃xff1b;对于1次操作的情况&＃xff0c;x所在的位置字符必为ch&＃xff0c;那么前面的元素必除不尽&＃xff0c;遍历后面的元素即可。对于0次操作&＃xff0c;就是所有位置都为ch。

代码

#include
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int maxn&＃61;3e5&＃43;7;
const int mod&＃61;1e9&＃43;7;int t,n,pos,pos2,vt[maxn];
char ch;
string str;signed main(){cin>>t;while(t--){cin>>n>>ch;cin>>str;int flag&＃61;0,flag2&＃61;0,cnt&＃61;0;for(int i&＃61;0;i}

D-The Number of Imposters

题意

给定n个点m条边&＃xff0c;每条边u指定v为c&＃xff0c;已知c为imposter的点必说真话&＃xff0c;c为crewmate的点必说假话&＃xff0c;求图中最多有多少个imposter。

思路

相当于黑白涂色了&＃xff0c;边的性质为1则两端不同色&＃xff0c;否则两端同色。

双向建边跑二分图&＃xff0c;取每个联通分块中个数多的答案加起来。

代码

#include
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int maxn&＃61;2e5&＃43;7;
const int maxm&＃61;1e6&＃43;7;struct E{int nxt,v,f;
}e[maxm];int head[maxn],cnt&＃61;0,ans&＃61;0;
int vis[maxn],num[3],flag;void addedge(int u,int v,int f){e[&＃43;&＃43;cnt]&＃61;(E){head[u],v,f};head[u]&＃61;cnt;
}void dfs(int x,int col){ vis[x]&＃61;col;num[col]&＃43;&＃43;;for(int i&＃61;head[x];i;i&＃61;e[i].nxt){int to&＃61;e[i].v,fang&＃61;(col&＃61;&＃61;2)?1:2;if(e[i].f&＃61;&＃61;1){if(vis[to]){if(vis[to]!&＃61;fang) flag&＃61;1;continue;}else dfs(to,fang); }if(e[i].f&＃61;&＃61;2){if(vis[to]){if(vis[to]!&＃61;col) flag&＃61;1;continue;}else dfs(to,col);}}
}void init(){ans&＃61;0;cnt&＃61;0;memset(vis,0,sizeof(vis));memset(head,0,sizeof(head));}signed main(){int t,n,m,u,v;string str;cin>>t;while(t--){cin>>n>>m;init();for(int i&＃61;1;i<&＃61;m;i&＃43;&＃43;){cin>>u>>v;cin>>str;if(str&＃61;&＃61;"imposter") flag&＃61;1;else flag&＃61;2;addedge(u,v,flag);addedge(v,u,flag);}flag&＃61;0;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){num[1]&＃61;0,num[2]&＃61;0;if(!vis[i]){dfs(i,1);ans&＃43;&＃61;max(num[1],num[2]);}}if(flag) cout<<-1<<"\n";else cout<}

E1-Rubik’s Cube Coloring (easy version)

题意

有n^2-1个节点&＃xff0c;每个节点涂上魔方6种颜色中的一种&＃xff0c;相邻点颜色必须在魔方中相邻&＃xff08;有4种&＃xff09;&＃xff0c;求种方案数。

思路

第一个节点可以涂6种色&＃xff0c;然后对于任意两个相邻的点都只能涂4种色&＃xff0c;共2n−12^n-12n−1个点&＃xff0c;那么答案就是6∗42n−26*4^{2^n-2}6∗42n−2。

注意对2用快速幂不要取模&＃xff0c;不会爆long long。

代码

#include
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int maxn&＃61;2e5&＃43;7;
const int mod&＃61;1e9&＃43;7;int fpow(int a,int p){int res&＃61;1;while(p){if(p&1) res&＃61;res*a%mod;a&＃61;a*a%mod;p>>&＃61;1;}return res;
}int k;signed main(){cin>>k;int tmp&＃61;1;for(int i&＃61;1;i<&＃61;k;i&＃43;&＃43;) tmp<<&＃61;1; int ans&＃61;6*fpow(4,tmp-2);cout<}

E2-Rubik’s Cube Coloring (hard version)

题意

在上一题的基础上加多一个限定&＃xff0c;就是我们固定住第i个节点的颜色&＃xff0c;再求方案数。

思路

真正用到的点只有2000个&＃xff0c;可以建立一棵虚树进行dp。

由于是完全二叉树&＃xff0c;祖先的个数也只有$logn$个&＃xff0c;可以接受。

所有隐式节点或者说没被建立的节点&＃xff0c;其值不受固定颜色点的干扰

转移时直接把两个子树乘起来。

代码

不是很会写&＃xff0c;抄博客的。

#include
#define int long long
using namespace std;
typedef double db;
const int mod&＃61;1e9&＃43;7;
const db eps&＃61;1e-10;
inline int Max(int x,int y){return x>y?x:y;}
inline int Min(int x,int y){return xinline db Max(db x,db y){return x-y>eps?x:y;}
inline db Min(db x,db y){return x-yinline int Add(int x,int y,int M&＃61;mod){return (x&＃43;y)%M;}
inline int Mul(int x,int y,int M&＃61;mod){return 1ll*x*y%M;}
inline int Dec(int x,int y,int M&＃61;mod){return (x-y&＃43;M)%M;}
inline int Abs(int x){return x<0?-x:x;}
inline int read(){ //快读 int s&＃61;0,w&＃61;1;char ch&＃61;getchar();while(!isdigit(ch)){if(ch&＃61;&＃61;&＃39;-&＃39;)w&＃61;-1;ch&＃61;getchar();}while(isdigit(ch)){s&＃61;s*10&＃43;ch-&＃39;0&＃39;;ch&＃61;getchar();}return s*w;
}
inline void write(int x){ //快速输出 if(x<0)putchar(&＃39;-&＃39;),x&＃61;-x;if(x>9)write(x/10);putchar(x%10&＃43;&＃39;0&＃39;);
}
const int N&＃61;2e5&＃43;10;
int k,n;
int F[61];
string s;
typedef long long ll;
mappa,col,lson,rson,f[4]; //实际上的点编号太大了&＃xff0c;用map存
vectorNode;
inline int qpow(int x,int y){ //快速幂 int res&＃61;1;while(y){if(y&1)res&＃61;Mul(res,x);x&＃61;Mul(x,x);y>>&＃61;1;}return res;
}
inline int Getdep(int v){return log2(v)&＃43;1;} //获取点的深度
void Treat(){for(auto v:Node){if(lson[v]||rson[v])continue;int Dep&＃61;k-Getdep(v)&＃43;1;if(col[v])f[col[v]][v]&＃61;Mul(1,qpow(4,F[Dep]));else for(int i&＃61;1;i<&＃61;3;&＃43;&＃43;i)f[i][v]&＃61;Mul(2,qpow(4,F[Dep]));}
}
void DP(ll x){if(!lson[x]&&!rson[x])return;if(lson[x])DP(lson[x]);if(rson[x])DP(rson[x]);ll L1&＃61;f[1][lson[x]],L2&＃61;f[2][lson[x]],L3&＃61;f[3][lson[x]],R1&＃61;f[1][rson[x]],R2&＃61;f[2][rson[x]],R3&＃61;f[3][rson[x]];if(!lson[x]){L1&＃61;L2&＃61;L3&＃61;Mul(2,qpow(4,F[k-Getdep(x*2)&＃43;1]));}if(!rson[x]){R1&＃61;R2&＃61;R3&＃61;Mul(2,qpow(4,F[k-Getdep(x*2)&＃43;1]));}if(!col[x]){f[1][x]&＃61;Mul(2,Mul(Add(L2,L3),Add(R2,R3)));f[2][x]&＃61;Mul(2,Mul(Add(L1,L3),Add(R1,R3)));f[3][x]&＃61;Mul(2,Mul(Add(L2,L1),Add(R2,R1)));}else{if(col[x]&＃61;&＃61;1)f[1][x]&＃61;Mul(Add(L2,L3),Add(R2,R3));if(col[x]&＃61;&＃61;2)f[2][x]&＃61;Mul(Add(L1,L3),Add(R1,R3));if(col[x]&＃61;&＃61;3)f[3][x]&＃61;Mul(Add(L2,L1),Add(R2,R1));}
}
signed main(){k&＃61;read();F[1]&＃61;0;for(int i&＃61;2;i<&＃61;60;&＃43;&＃43;i){F[i]&＃61;Add(F[i-1],1,mod-1);F[i]&＃61;Mul(F[i],2,mod-1);}n&＃61;read();for(int i&＃61;1;i<&＃61;n;&＃43;&＃43;i){int pos&＃61;read();cin>>s;if(s&＃61;&＃61;"orange"||s&＃61;&＃61;"red")col[pos]&＃61;1;if(s&＃61;&＃61;"white"||s&＃61;&＃61;"yellow")col[pos]&＃61;2;if(s&＃61;&＃61;"blue"||s&＃61;&＃61;"green")col[pos]&＃61;3;while(pos){ //返回向上到父亲的一条链Node.emplace_back(pos);pa[pos]&＃61;pos/2;if(pos%2&＃61;&＃61;0)lson[pos/2]&＃61;pos;else rson[pos/2]&＃61;pos;pos/&＃61;2;}}sort(Node.begin(),Node.end()); //排序所有关键节点 ll root&＃61;1;Treat();DP(root);int res&＃61;Add(f[3][root],Add(f[1][root],f[2][root]));write(res);putchar(&＃39;\n&＃39;);return 0;
}

F-Ideal Farm

题意

如果每个盒子都有求并且存在一个区间[l,r]使得∑i&＃61;lra[i]&＃61;k,其中a[i]表示第i个盒子的球数\sum_{i&＃61;l}^ra[i]&＃61;k,其中a[i]表示第i个盒子的球数∑i&＃61;lr​a[i]&＃61;k,其中a[i]表示第i个盒子的球数&＃xff0c;那么我们就说这个方案是合理的。每组数据给定球数s,盒子数n以及k&＃xff0c;问是否无论怎么划分都是合理的。

思路

首先我们向每个盒子加一个球&＃xff0c;那么剩下的球&＃xff0c;每隔k个盒子就再放k个&＃xff0c;这样可以保证前面的区间都不存在方案使之合理&＃xff0c;如果到最后依然有球剩下&＃xff0c;那么就说明可以构建出一种不合理的方案&＃xff0c;否则无论怎样都是合理的。

注&＃xff1a;k>s是不合理的&＃xff0c;并且特判s&＃61;&＃61;k是合理的!

代码

#include
#define int long long
using namespace std;int t,s,n,k,flag,tim;signed main(){cin>>t;while(t--){cin>>s>>n>>k;flag&＃61;0;if(s&＃61;&＃61;k){puts("YES");continue;}if(k>s) flag&＃61;1;else{s-&＃61;n; //每个pen先放一个tim&＃61;n/k;s-&＃61;tim*k;if(s>&＃61;0) flag&＃61;1;}if(flag) puts("NO");else puts("YES"); } return 0;
}