Codeforces Round #629 (Div. 3)题解
John_Ran 人气:1A. 给你两个数a，b，每次操作可以a:=a+1，操作多少次之后能使得a%b==0?
输出a对b的上取整乘以b与a的差就可以通过。
#include<bits/stdc++.h>
#define fi first
#define sd second
#define lson (nd<<1)
#define rson (nd+nd+1)
#define PB push_back
#define MP make_pair
#define mid (l+r>>1)
#define SZ(x) (int)x.size()
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
inline int read(){
int res=0, f=1;char ch=getchar();
while(ch<'0'|ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){res=res*10+ch-'0';ch=getchar();}
return res*f;
}
const int MAXN = 200'005;
const int MOD = 1000000007;
void addmod(int& a, int b){a+=b;if(a>=MOD)a-=MOD;}
int mulmod(int a, int b){return 1ll*a*b%MOD;}
void solve(){
int a,b;
a=read(),b=read();
cout<<(a+b-1)/b*b-a<<endl;
}
int main(){
int cases;cases=read();
while(cases--){
solve();
}
return 0;
}
B. 给两个数字n，k，构造一个长度为n，有n-2个a，2个b的，字典序为k的字符串。
找规律，发现周期为1的字符串，开头的b在n-1的位置，第二个b的不断靠近，确定周期即可。
#include<bits/stdc++.h>
#define fi first
#define sd second
#define lson (nd<<1)
#define rson (nd+nd+1)
#define PB push_back
#define MP make_pair
#define mid (l+r>>1)
#define SZ(x) (int)x.size()
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
inline int read(){
int res=0, f=1;char ch=getchar();
while(ch<'0'|ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){res=res*10+ch-'0';ch=getchar();}
return res*f;
}
const int MAXN = 200'005;
const int MOD = 1000000007;
void addmod(int& a, int b){a+=b;if(a>=MOD)a-=MOD;}
int mulmod(int a, int b){return 1ll*a*b%MOD;}
void solve(){
int n;n=read();
int k=read();
int t=1;
int s=0;
while(s+t<k){
s+=t;
t+=1;
}
int pos=n-t-1;
k-=s;
for(int i=0;i<n;++i){
if(i==pos||i==n-k){
cout<<"b";
}else{
cout<<"a";
}
}
cout<<endl;
}
int main(){
int cases;cases=read();
while(cases--){
solve();
}
return 0;
}
C. 给你一个字符串s，构造两个字符串s1，s2。使得s中的每一个数字都是s1，s2中对应位置数之和模3的结果并且其中最大的字符串最小。
s[i]=0,s1[i]=s2[i]=0,第一次s[i]=1的时候，给s1[i]=1，s2[i]=0，此后s[i]=1全都给s2[i]=1，s[i]=2给s2[i]=2即可通过。
#include<bits/stdc++.h>
#define fi first
#define sd second
#define lson (nd<<1)
#define rson (nd+nd+1)
#define PB push_back
#define MP make_pair
#define mid (l+r>>1)
#define SZ(x) (int)x.size()
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
inline int read(){
int res=0, f=1;char ch=getchar();
while(ch<'0'|ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){res=res*10+ch-'0';ch=getchar();}
return res*f;
}
const int MAXN = 200'005;
const int MOD = 1000000007;
void addmod(int& a, int b){a+=b;if(a>=MOD)a-=MOD;}
int mulmod(int a, int b){return 1ll*a*b%MOD;}
void solve(){
int n;cin>>n;
string s;cin>>s;
string s1="1";
string s2="1";
int ok=0;
for(int i=1;i<n;++i){
if(s[i]=='0'){
s1+="0";
s2+="0";
}else if(s[i]=='2'){
if(ok){
s2+="2";
s1+="0";
}else{
s1+="1";
s2+="1";
}
}else{
if(!ok){
s1+="1";
s2+="0";
ok=1;
}else{
s1+="0";
s2+="1";
}
}
}
cout<<s1<<endl;
cout<<s2<<endl;
}
int main(){
int cases;cases=read();
while(cases--){
solve();
}
return 0;
}
D. 给一个长度为n的环，里面的元素有不同的类型，要求相邻的元素且类型相同时，涂上的颜色不能相同，输出最小颜色数和一种解。
首先答案不会超过3，全都相等时给出n个1。n为偶数的时候1和2交错，n为奇数的时候，如果有两个相同类型的相邻或者是首尾相等，答案就是2.构造一种即可。
其他情况输出前n-1个为1和2交错，3作为结尾就能通过(wa得飞起。
#include<bits/stdc++.h>
#define fi first
#define sd second
#define lson (nd<<1)
#define rson (nd+nd+1)
#define PB push_back
#define MP make_pair
#define mid (l+r>>1)
#define SZ(x) (int)x.size()
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
inline int read(){
int res=0, f=1;char ch=getchar();
while(ch<'0'|ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){res=res*10+ch-'0';ch=getchar();}
return res*f;
}
const int MAXN = 200'005;
const int MOD = 1000000007;
void addmod(int& a, int b){a+=b;if(a>=MOD)a-=MOD;}
int mulmod(int a, int b){return 1ll*a*b%MOD;}
void solve(){
int n=read();
vector<int> A(n);
int isOne=1;
for(int i=0;i<n;++i){
A[i]=read();
if(A[i]!=A[0])isOne=0;
}
if(isOne){
cout<<"1\n";
for(int i=0;i<n;++i)cout<<"1"<<" \n"[i==n-1];
return;
}
if(!(n&1)){
cout<<"2\n";
for(int i=0;i<n;++i){
if(i&1)cout<<"2 ";
else cout<<"1 ";
}
cout<<"\n";
return;
}
if((n&1)&&A[0]==A[n-1]){
cout<<"2\n";
for(int i=0;i<n-1;++i){
if((i&1))cout<<"2 ";
else cout<<"1 ";
}
cout<<"1\n";
return;
}
int isTwo=0;
for(int i=1;i<n;++i)if(A[i]==A[i-1])isTwo=i;
if(isTwo){
vector<int>ans={1};
for(int i=1;i<n;++i){
if(i==isTwo)ans.PB(ans[i-1]);
else ans.PB(3-ans[i-1]);
}
cout<<"2\n";
for(int i=0;i<n;++i)cout<<ans[i]<<" \n"[i==n-1];
return;
}
cout<<"3\n";
for(int i=0;i<n-1;++i){
if(i&1)cout<<"2 ";
else cout<<"1 ";
}
cout<<"3\n";
}
int main(){
int cases;cases=read();
while(cases--){
solve();
}
return 0;
}
/*
1
7
5 6 6 1 3 5 4
*/
E. 给一棵树，多次询问，给定n个点，问是否有一条链能够使得所有点到这条链的距离不超过1。
对于某一个特定的点来说，要包括这个点，就必须包括这个点的父亲节点，把所有的父亲节点拿出来。考虑是否存在一条链把它们都包含，这个可以通过从上往下走和从下往上走来解决。
两种解法都要求将深度排序，之后，第一种通过判断下一个点是否在自己的子树中即可，具体实现上用dfs序来解决。第二种解法可以通过寻找LCA来解决，带个log。给出第一种解法的代码。
#include<bits/stdc++.h>
#define fi first
#define sd second
#define lson (nd<<1)
#define rson (nd+nd+1)
#define PB push_back
#define mid (l+r>>1)
#define MP make_pair
#define SZ(x) (int)x.size()
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
inline int read(){
int res=0, f=1;char ch=getchar();
while(ch<'0'|ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){res=res*10+ch-'0';ch=getchar();}
return res*f;
}
const int MAXN = 200'005;
const int MOD = 1000000007;
void addmod(int& a, int b){a+=b;if(a>=MOD)a-=MOD;}
int mulmod(int a, int b){return 1ll*a*b%MOD;}
#define go(e,u) for(int e=head[u];e;e=Next[e])
int to[MAXN<<1],Next[MAXN<<1],head[MAXN],tol;
void add_edge(int u,int v){
Next[++tol]=head[u];to[tol]=v;head[u]=tol;
Next[++tol]=head[v];to[tol]=u;head[v]=tol;
}
int n,m;
int fa[MAXN], dep[MAXN];
int L[MAXN], R[MAXN], dfn;
void dfs(int u, int f){
L[u]=++dfn;
go(e,u){
int v=to[e];
if(v==f)continue;
else{
fa[v]=u;
dep[v]=dep[u]+1;
dfs(v,u);
}
}
R[u]=dfn;
}
bool cmp(int a, int b){
return dep[a]<dep[b];
}
int main(){
n=read(),m=read();
for(int i=1;i<n;++i){
int u,v;
u=read();v=read();
add_edge(u,v);
}
dfs(1,0);
while(m--){//暴力会被一条链的情况卡掉,退化为O(n^2)
int num;
num=read();
vector<int> nodes;
for(int i=0;i<num;++i){
int x=read();
if(x!=1)nodes.PB(fa[x]);
}
int ok=1;
sort(nodes.begin(),nodes.end(),cmp);
for(int i=0;i<SZ(nodes)-1;++i){
int x=nodes[i];
int y=nodes[i+1];
if(R[y]<L[x]||L[y]>R[x]){
ok=0;
break;
}
}
if(!ok)cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
return 0;
}
F. 给一个长度为n的数组，每次操作可以将数组中最小的数加1，最大的数减1。问最少操作多少次才能使得数组中重复元素超过k个。
将元素排序，考虑最后相等超过k个的元素必然是数组中的某一个。枚举一下是哪一个，由于刚开始的时候是没有收益的(不会使得相等的数增加)，只有将其他元素都增加到A[i]-1或者减少到A[i]+1时才能每操作1次，有1的收益。
这个时候我们只需要快速得到将前面所有元素全都变成A[i]-1和后面的元素全都变成A[i]+1的代价，然后考虑先取左边还是先取右边即可，用前缀和O(n)就能做完。
#include<bits/stdc++.h>
#define fi first
#define sd second
#define lson (nd<<1)
#define rson (nd+nd+1)
#define PB push_back
#define mid (l+r>>1)
#define MP make_pair
#define SZ(x) (int)x.size()
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
inline int read(){
int res=0, f=1;char ch=getchar();
while(ch<'0'|ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){res=res*10+ch-'0';ch=getchar();}
return res*f;
}
const int MAXN = 200'005;
const int MOD = 1000000007;
void addmod(int& a, int b){a+=b;if(a>=MOD)a-=MOD;}
int mulmod(int a, int b){return 1ll*a*b%MOD;}
map<int, int> H;
LL sum[MAXN];
int n, k;
int A[MAXN];
int pos[MAXN], top;
void build(){
for(int i=1;i<=n;++i){
sum[i]=sum[i-1]+A[i];
}
}
LL query(int L, int R){
return sum[R]-sum[L-1];
}
int main(){
n=read();k=read();
for(int i=1;i<=n;++i)A[i]=read();
sort(A+1,A+n+1);
for(int i=1;i<=n;++i)++H[A[i]];
for(int i=1;i<=n;++i){
if(A[i]!=A[i-1]){
pos[++top]=i;
}
}
build();
LL ans=1e18;
for(auto it:H){
if(it.sd>=k){
cout<<"0";
return 0;
}
}
for(int i=1;i<=top;++i){
LL res1=0,res2=0;
int t=H[A[pos[i]]];
int l1=1,r1=pos[i]-1;
int l2=pos[i]+t,r2=n;
LL cost1=1e18;
LL cost2=1e18;
if(r1>=l1)cost1=1ll*r1*(A[pos[i]]-1)-query(l1,r1);
if(r2>=l2)cost2=query(l2,r2)-1ll*(r2-l2+1)*(A[pos[i]]+1);
int num1=r1,num2=(r2-l2+1);
/*
不能只根据填平的代价大小去决定选哪边
*/
res1+=cost1;
if(num1+t>=k){
res1+=k-t;
}else{
res1+=num1;
res1+=cost2;
res1+=k-(t+num1);
}
res2+=cost2;
if(num2+t>=k){
res2+=k-t;
}else{
res2+=num2;
res2+=cost1;
res2+=k-(t+num2);
}
ans=min(ans,min(res1,res2));
}
cout<<ans;
return 0;
}
/*
8 6
4 5 1 2 3 5 3 3
5
*/
加载全部内容