Codeforces Round #748 (Div. 3) （CF1593）题解
CF1593D2. Half of Same
题意
给出一些数，寻找最大的整数k，使得对一些a[i]执行-k的操作后，能够使一半的数相同。
解法
先选定一个目标值，然后枚举k的值，枚举次数≤sqrt(max-min)
#include
#define For(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int N=105;
int t,n,a[N],all[2000005];
bool vis[2000005];
map mp;
signed main() {
cin>>t;
while(t--) {
cin>>n;
mp.clear();
int mx=0,x=1e6,y=-1e6;
For(i,1,n) {
cin>>a[i];
if(a[i]y) y=a[i];
mp[a[i]]++;
if(mp[a[i]]>mx) mx=mp[a[i]];
}
if(mx>=n/2) {puts("-1");continue;}
int ans=1,hh=0;
memset(vis,0,sizeof vis);
For(i,1,n) For(j,i+1,n) {
if(!vis[abs(a[i]-a[j])]) {all[++hh]=abs(a[i]-a[j]); vis[abs(a[i]-a[j])]=1;}
For(k,2,sqrt(abs(a[i]-a[j]))) if(abs(a[i]-a[j])%k==0) {
if(!vis[k]) {all[++hh]=k; vis[k]=1;}
if(!vis[abs(a[i]-a[j])/k]) {all[++hh]=abs(a[i]-a[j])/k; vis[abs(a[i]-a[j])/k]=1;}
}
}
For(i,1,n) {//设置基准值
For(k,1,hh) if(all[k]>ans) {
int tot=0;
For(j,1,n) {
if(abs(a[i]-a[j])%all[k]==0) tot++;
}
if(tot>=n/2) ans=all[k];
}
}
cout< CF1593E. Gardener and Tree
题意
T组数据，给出一棵树，执行k次操作，删掉所有的叶子结点，问最后还剩下几个点。
解法
直接操作即可。
注意在操作以后，可能有一些值的链接数为0，注意不要把它们删去。
#include
#define For(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int N=1600005;
int t,x,y,cnt,n,k;
int bs[N],head[N];
int tot,pcs[N],exist[N];
int tot2,pcs2[N];
int in_new[N];
struct node {
int next,to;
} sxd[N];
void add(int x,int y) {
sxd[++cnt].next=head[x];
sxd[cnt].to=y;
head[x]=cnt;
}
signed main() {
cin>>t;
while(t--) {
cin>>n>>k;
For(i,1,n) exist[i]=1;
For(i,1,n-1) {
cin>>x>>y;
add(x,y),add(y,x);
bs[x]++,bs[y]++;
}
For(i,1,k) {
if(i==1) {
tot=0;
For(j,1,n) if(bs[j]<=1) pcs[++tot]=j;
} else {
tot=tot2;
For(j,1,tot) pcs[j]=pcs2[j];
}
tot2=0;
For(j,1,tot) {
int at=pcs[j];
exist[at]=0;
for(int x=head[at];x;x=sxd[x].next) {
int nxt=sxd[x].to;
bs[nxt]--;
if(bs[nxt]<=1 && in_new[nxt]==0) {
pcs2[++tot2]=nxt;
in_new[nxt]=1;
}
}
}
}
int ans=0;
For(i,1,n) if(exist[i]) ans++;
cout< CF1593F. Red-Black Number
题意
T组数据，为一组数字中涂上红色与黑色。要求从左向右红色的数字合起来的数对给定的x取模后为0，黑色的数字合起来的数字对给定的y后为0。求红色数字个数与黑色数字个数的差的绝对值的最小值。
解法
考虑动态规划。
令f[i][j][k][m]表示计算到第i个数字，红色的余数j，黑色的余数k，目前的红色数m。因为当前的余数可以通过上一个余数*10+当前位置得到，所以可以动态规划，在struct里存储当前的答案即可。如果把答案存储下来，要考虑内存问题。
//f[i][j][k][l]:计算到第i个数字，红色的余数j，黑色的余数k，目前的红色数m
#include
#define For(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const short N=41;
short t,n,x,y,a[N];
char ch[N];
struct node {
bool val;
short ans[N];//1红，2黑
} f[N][N][N][N];
signed main() {
cin>>t;
while(t--) {
cin>>n>>x>>y;
scanf("%s",ch+1);
For(i,1,n) a[i]=ch[i]-'0';
memset(f,0,sizeof f);
f[0][0][0][0].val=1;
For(i,1,n) For(j,0,x-1) For(k,0,y-1) For(m,0,i-1) {
if(f[i-1][j][k][m].val==1) {
f[i][(j*10+a[i])%x][k][m+1].val=1;
For(l,1,i-1) f[i][(j*10+a[i])%x][k][m+1].ans[l]=f[i-1][j][k][m].ans[l];
f[i][(j*10+a[i])%x][k][m+1].ans[i]=1;
f[i][j][(k*10+a[i])%y][m].val=1;
For(l,1,i-1) f[i][j][(k*10+a[i])%y][m].ans[l]=f[i-1][j][k][m].ans[l];
f[i][j][(k*10+a[i])%y][m].ans[i]=2;
}
}
bool flag=0;
for(int i=(n+1)/2;i>=1;i--) {
if(f[n][0][0][i].ans[1]!=0) {
flag=1;
For(j,1,n) if(f[n][0][0][i].ans[j]==1) cout<<"R"; else cout<<"B";
puts("");
break;
}
if(f[n][0][0][n-i].ans[1]!=0) {
flag=1;
For(j,1,n) if(f[n][0][0][n-i].ans[j]==1) cout<<"R"; else cout<<"B";
puts("");
break;
}
}
if(flag==0) puts("-1");
}
return 0;
}
CF1593G. Changing Brackets
题意
T组数据，有一个以“(,),[,]“构成的字符串，有以下两种操作：
① 把左右小括号互换或把左右中括号互换，0费。
② 把【变成（或把】变成），1费。
目标把一个括号串变成合理的括号串
N组数据，对给出的字符串求解，离线操作。
解法
有以下结论：如果字符串中奇数位置的小括号数（与方向无关）与偶数位置的小括号数相同，那么就能0费完成。
所以，答案即为字符串中奇偶位置的小括号数差的绝对值。
可以通过预处理前缀和计算。
#include
#define For(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int N=1100005;
int t,k,l,r;
int ji[N],ou[N];
char ch[N];
signed main() {
cin>>t;
while(t--) {
scanf("%s",ch+1);
int n=strlen(ch+1);
memset(ji,0,sizeof ji);
memset(ou,0,sizeof ou);
For(i,1,n) {
ji[i]=ji[i-1]; ou[i]=ou[i-1];
if(ch[i]=='(' || ch[i]==')') {
if(i%2==1) ji[i]++;
else ou[i]++;
}
}
cin>>k;
while(k--) {
cin>>l>>r;
cout<