1624D. Palindromes Coloring
题意:
给定一个字符串,长度为n,顺序任意调换。取k个字串,要求为回文,求回文子串字串最短长度。
解法:
考虑每个字母的贡献,如果有成对的字母,则可以放在首尾,而单个只能放在中间。如果无法均匀分配,则剩下的配对字母应当拆分成单个以最大化答案。
#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int N=200005;
int t,n,k,sum[30];
char ch[N];
signed main() {
cin>>t;
while(t--) {
cin>>n>>k;
scanf("%s",ch+1);
memset(sum,0,sizeof sum);
For(i,1,n) sum[ch[i]-'a'+1]++;
int pr=0,sg=0;
For(i,1,26) pr+=sum[i]/2,sg+=sum[i]%2;
if(pr%k==0) cout<<(pr/k)*2+(sg>=k?1:0)<<'\n';
else cout<<(pr/k)*2+(sg+(pr%k)*2>=k?1:0)<<'\n';
}
return 0;
}
1624G. MinOr Tree
题意:
给一张图,求在能够组成一棵树的情况下,树的边的或和最小。
解法:
考虑每一位的贡献,从高到低用并查集判断在某一位全部为0时是否能够组成一棵树。如果可以,则禁用此位为1的所有边,继续向下查找。
#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int N=200005;
int t,n,m,need[N];
struct node {
bool ok;
int u,v,w,bi[31];
} a[N];
int fa[N],rk[N];
int find(int x) {
if(fa[x]==x) return x;
else return fa[x]=find(fa[x]);
}
void merge(int x,int y) {
int xx=find(x),yy=find(y);
if(rk[xx]<rk[yy]) fa[xx]=yy,rk[yy]=max(rk[yy],rk[xx]+1);
else fa[yy]=xx,rk[xx]=max(rk[xx],rk[yy]+1);
}
signed main() {
cin>>t;
while(t--) {
cin>>n>>m;
For(i,1,m) {a[i].ok=1; memset(a[i].bi,0,sizeof a[i].bi);}
For(i,1,m) {
cin>>a[i].u>>a[i].v>>a[i].w;
int temp=-1;
while(a[i].w) {
a[i].bi[++temp]=a[i].w%2;
a[i].w/=2;
}
}
memset(need,0,sizeof need);
for(int i=30;i>=0;i--) {
int sum=0; //合并的总次数
For(j,1,n) fa[j]=j,rk[j]=1;
For(j,1,m) if(a[j].ok==1 && a[j].bi[i]==0) {
if(find(a[j].u)!=find(a[j].v)) {
merge(a[j].u,a[j].v); sum++;
}
}
if(sum>=n-1) { //全部用0也可以做到,那为1的就不能再用了
For(j,1,m) if(a[j].ok==1 && a[j].bi[i]==1)
a[j].ok=0;
} else { //不行 只能开1
need[i]=1;
}
}
int ans=0;
For(i,0,30) ans+=need[i]*pow(2,i);
cout<<ans<<'\n';
}
return 0;
}