给我贺完了？
A - Shrinking
给定一个串 \(s\)，每次可以进行如下操作：
-
记串长为 \(n\).
-
构造长为 \(n-1\) 的串 \(s'\)，满足 \(s'_i\) 为 \(s_i\) 或 \(s_{i+1}\)，令 \(s\leftarrow s'\).
问使 \(s\) 中所有字符相同的最小操作次数。\(|s|\le 100\).
按照题意模拟即可，时间复杂度 \(O(|\Sigma|\cdot |s|^2)\)，此处 \(|\Sigma|=26\).
点击查看代码
#include<bits/stdc++.h>
#define N 105
using namespace std;
int read(){
int x=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*w;
}
int n;char s[N];int t[N],tp[N];
int ans=114514;
void solve(int x){
bool exi=false;
for(int i=1;i<=n;i++)
exi|=((tp[i]=s[i]-'a')==x);
if(!exi)return;
int cnt=0;
for(int o=1;o<n;o++){
bool fl=true;
for(int j=1;j<=n-o+1;j++)
if(tp[j]!=x){fl=false;break;}
if(fl)break;
cnt++;
for(int j=1;j<=n-o;j++)
t[j]=(tp[j]==x||tp[j+1]==x)?x:tp[j];
memcpy(tp,t,sizeof(tp));
}
ans=min(ans,cnt);
}
int main(){
scanf("%s",s+1),n=strlen(s+1);
for(int i=0;i<26;i++)solve(i);
printf("%d\n",ans);
return 0;
}
B - Colorful Hats
\(n\) 只猫戴帽子，\(a_i\) 表示除第 \(i\) 只猫外的帽子颜色总数，问是否存在合法的帽子颜色序列。
\(2\le n\le 10^5\)，\(1\le a_i\le n-1\).
记 \(L,R\) 分别为 \(\{a_n\}\) 中的最小值和最大值。
不难发现 \(L=R\) 或 \(L+1=R\)，否则无解。
称出现一次的帽子为奇异帽子，反之为平凡帽子。
- \(L=R\)
此时所有猫戴奇异帽子或平凡帽子。
得到 \(L=n-1\) 或 \(n\ge 2L\).
- \(L=R+1\)
若 \(a_i=L\)，其一定戴奇异帽子，反之戴平凡帽子。考虑帽子颜色种数的上下界。
记 \(a_i=L\) 的 \(i\) 有 \(cl\) 个，\(a_i=R\) 的有 \(cr\) 个。
不难发现 \(R\) 即帽子颜色总数。
若平凡帽子颜色均相同，帽子颜色总数最小为 \(cl+1\).
若每种平凡帽子只出现两次，帽子颜色种数最大为 \(\displaystyle cl+\lfloor\frac{cr}{2}\rfloor\).
点击查看代码
#include<bits/stdc++.h>
#define N 100010
using namespace std;
int read(){
int x=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*w;
}
int n,a[N],mn,mx,cn,cx;
int main(){
n=read();
for(int i=1;i<=n;i++)a[i]=read();
sort(a+1,a+1+n),mn=a[1],mx=a[n];
if(mn+1<mx)return puts("No"),0;
if(mn==mx){
if(mn==n-1||n>=2*mn)puts("Yes");
else puts("No");
return 0;
}
for(int i=1;i<=n;i++)
a[i]==mn?cn++:cx++;
if(mx>=cn+1&&mx<=cn+cx/2)puts("Yes");
else puts("No");
return 0;
}
C - +/- Rectangle
给定 \(n,m,h,w\)，构造一个 \(n\times m\) 的矩阵，满足：
-
元素权值绝对值 \(\le 10^9\)
-
矩阵元素权值和为正
-
任意 \(h\times w\) 的子矩阵元素权值和为负
或报告无解。
\(1\le h\le n\le 500\)，\(1\le w\le m\le 500\).
思考无解的情况，发现当且仅当 \(h|n\) 且 \(w|m\)，因为可以将其划分为若干 \(h\times w\) 的子矩阵，由于每个子矩阵为负，最后整个矩阵必定为负。
接下来假设 \(h\not|n\)，对于编号为 \(h\) 的倍数的行，将其设为负值。
然后随便搞搞即可。只需让最后几个非 \(h\) 的倍数的行把权值和补回来就好了。
对于 \(w\not|m\) 时同理。
点击查看代码
#include<bits/stdc++.h>
#define N 505
using namespace std;
int read(){
int x=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*w;
}
int n,m,h,w,ans[N][N];
int main(){
n=read(),m=read(),h=read(),w=read();
if(n%h==0&&m%w==0)return puts("No"),0;
if(n%h){
for(int i=1;i<=n;i++){
if(i%h){
for(int j=1;j<=m;j++)
ans[i][j]=1000000;
}
else{
for(int j=1;j<=m;j++)
ans[i][j]=-1000000*(h-1)-1;
}
}
}
else{
for(int j=1;j<=m;j++){
if(j%w){
for(int i=1;i<=n;i++)
ans[i][j]=1000000;
}
else{
for(int i=1;i<=n;i++)
ans[i][j]=-1000000*(w-1)-1;
}
}
}
puts("Yes");
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
printf("%d ",ans[i][j]);
printf("\n");
}
return 0;
}
D - XOR Replace
给定序列 \(\{a_n\}\)，每次可以将一个数变为序列的异或和，问到达 \(\{b_n\}\) 的最小步数。或报告无解。
\(2\le n\le 10^5\)，\(0\le a_i,b_i\le 2^{30}\).
不妨视作序列的异或和 \(x\) 放在位置 \(n+1\) 上，每次交换 \(a_i\) 和 \(a_{n+1}\).
容易判断无解。
考虑 \(a_1,a_2,\dots,a_k\Rightarrow a_k,a_1,\dots,a_{k-1}\).
可以从 \(1\) 到 \(k\) 执行 \(\operatorname{swap}(a_i,a_{n+1})\)，最后执行 \(\operaotrname{swap}(a_1,a_{n+1})\)，一共操作 \(k+1\) 次。
考虑 \(a_1,a_2,\dots,x,\dots,a_k\Rightarrow a_k,a_1,\dots,x,\dots\).
此时从第 \(n+1\) 个数的地方开始交换，会减少一次操作。
对于 \(a_i\not=b_i\)，从点 \(a_i\) 向点 \(b_i\) 连一条边。此时答案为 总边数 \(+\) 连通块数 \(-1\).
另外地，当 \(n+1\) 个数不属于任意连通块，此时多减去了 \(1\).
对 \(a_{n+1}\) 和 \(b_{n+1}\) 强制连边，不计入总边数。
使用并查集维护。
点击查看代码
#include<bits/stdc++.h>
#define N 200010
using namespace std;
int read(){
int x=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*w;
}
int n,a[N],b[N],ta[N],tb[N];
int t[N],tot,len;
int fa[N];
int find(int x){
return x==fa[x]?x:fa[x]=find(fa[x]);
}
void merge(int x,int y){
int fx=find(x),fy=find(y);
if(fx!=fy)fa[fx]=fy;
}
int main(){
n=read();
for(int i=1;i<=n;i++)
a[i]=read(),a[n+1]^=a[i];
for(int i=1;i<=n;i++)
b[i]=read(),b[n+1]^=b[i];
n++,memcpy(ta,a,sizeof(a)),memcpy(tb,b,sizeof(b));
sort(ta+1,ta+1+n),sort(tb+1,tb+1+n);
for(int i=1;i<n;i++){
if(ta[i]!=tb[i]){
puts("-1");
return 0;
}
}
int ans=0;
for(int i=1;i<=n;i++){
if(a[i]!=b[i]||(i==n)){
t[++tot]=a[i],t[++tot]=b[i];
if(i<n)ans++;
}
}
if(!ans){
puts("0");
return 0;
}
sort(t+1,t+1+tot),len=unique(t+1,t+1+tot)-t-1;
for(int i=1;i<=len;i++)fa[i]=i;
for(int i=1;i<=n;i++){
if(a[i]!=b[i]){
a[i]=lower_bound(t+1,t+1+len,a[i])-t;
b[i]=lower_bound(t+1,t+1+len,b[i])-t;
merge(a[i],b[i]);
}
}
for(int i=1;i<=len;i++)
ans+=(fa[i]==i);
printf("%d\n",ans-1);
return 0;
}
E - Poor Turkeys
有 \(n\) 只鸡，有 \(m\) 个形如 \((x,y)\) 的操作：
-
若 \(x\) 和 \(y\) 都活着，等概率吃掉一只。
-
若 \(x\) 和 \(y\) 恰好活着一只，吃掉剩下的一只。
-
若 \(x\) 和 \(y\) 均死亡，不进行任何操作。
求有多少个二元组 \((i,j)\) 满足 \(i<j\) 且鸡 \(i\) 和鸡 \(j\) 都可能存活。
\(n\le 400\)，\(m\le 10^5\)，\(x_i<y_i\).
时光倒流。
记 \(f_{i,j}\) 表示如果要留下 \(i\)，是否要炖了 \(j\)。初始 \(f_{i,i}=1\).
如果在某个时刻需要对 \(i,j\) 做抉择，为了留下 \(i\) 一定会炖掉 \(j\)，即 \(j\) 在此前应受到和 \(i\) 一样的保护。
考虑鸡 \(i\) 是否能存活。假设有限制 \((i,x)\)，\((i,y)\)，如果存在限制 \((x,y)\)，则 \(i\) 必定死亡。
对于鸡 \(i\)，记集合 \(S_i\) 表示让鸡 \(i\) 存活下来需要保护的鸡有哪些，初始 \(S_i=\{i\}\).
从后往前考虑每一对 \((x,y)\)，若 \(x,y\in S_i\)，\(i\) 必死无疑。若其一 \(\in S_i\)，不放设为 \(x\)，那么需要保护 \(y\)，将 \(y\) 加入 \(S_i\).
对于两只非必死的鸡 \(i,j\)，由于一只鸡不能死两次，\((i,j)\) 合法当且仅当 \(S_i\cap S_j=\emptyset\).
时间复杂度 \(O(nm+n^3)\)，可以用 bitset 优化为 \(O(nm+\frac{n^3}{\omega})\).
点击查看代码
#include<bits/stdc++.h>
#define N 405
#define M 100010
using namespace std;
int read(){
int x=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*w;
}
int n,m,x[M],y[M],g[M];
bitset<N>f[N];
int ans;
int main(){
n=read(),m=read();
for(int i=1;i<=m;i++)
x[i]=read(),y[i]=read();
for(int i=1,u,v;i<=n;i++){
f[i][i]=true;
for(int j=m;j;j--){
u=f[i][x[j]],v=f[i][y[j]];
if(u&&v)g[i]=true;
if(u)f[i][y[j]]=true;
else if(v)f[i][x[j]]=true;
}
}
for(int i=1;i<=n;i++){
if(g[i])continue;
for(int j=i+1;j<=n;j++){
if(g[j])continue;
ans+=!((f[i]&f[j]).any());
}
}
printf("%d\n",ans);
return 0;
}
F - Games on DAG
给定 \(n\) 个点 \(m\) 条边的 DAG，每条边 \((u,v)\) 满足 \(u<v\).
在 \(1,2\) 号点分别有一颗石头，两人博弈，每次可以沿有向边移动一颗石头，不能移动则输。
问 \(2^m\) 个边的子集中，保留这个子集先手必胜的方案数。答案模 \(10^9+7\).
\(2\le n\le 15\).
即 \(2^m\) 减去所有 \(\operatorname{SG}(1)=\operatorname{SG}(2)\) 的情况。
显然所有点的 SG 值不可能超过 \(n-1\).
对 \(\operatorname{SG}=k\) 的集合，应该在每个 \(\operatorname{SG}<k\) 的集合中选取一个点连边，\(>k\) 的可以任意连。
设 \(S\) 为 \(\operatorname{SG}>k\) 的集合，\(T\) 为 \(\operatorname{SG}=k\) 的集合.
-
对于 \(S\rightarrow T\) 的边，每个 \(S\) 中的元素至少向 \(T\) 连一条。
-
对于 \(T\rightarrow S\) 的边，随便连边。
-
对于 \(T\) 内部，不能连边。
\(1\) 和 \(2\) 应该同时在 \(S\) 或 \(T\) 内。
有 \(O(n\cdot 3^n)\) 的枚举子集做法。
点击查看代码
#include<bits/stdc++.h>
#define N 16
#define M (1<<N)
#define lb(x) x&-x
#define P 1000000007
using namespace std;
int read(){
int x=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*w;
}
int n,m;
int cnt[N][M],p2[N*N];
int E[N][N],f[M];
bool check(int T){
return !!(((T&1)+((T>>1)&1))^1);
}
int main(){
n=read(),m=read();
p2[0]=1;
for(int i=1;i<=m;i++)p2[i]=p2[i-1]*2%P;
for(int i=1,u,v;i<=m;i++){
u=read(),v=read();
E[u][v]++;
}
for(int S=0;S<(1<<n);S++)
for(int i=1;i<=n;i++)
cnt[i][S]=cnt[i][S^lb(S)]+(!S?0:E[i][(int)log2(lb(S))+1]);
f[0]=1;
for(int S=1;S<(1<<n);S++)
for(int T=S,R,cur;T;T=(T-1)&S){
R=S^T,cur=1;
if(!check(T))continue;
for(int i=1;i<=n;i++){
if((T>>(i-1))&1)cur=1ll*cur*p2[cnt[i][R]]%P;
if((R>>(i-1))&1)cur=1ll*cur*(p2[cnt[i][T]]-1)%P;
}
(f[S]+=1ll*f[R]*cur%P)%=P;
}
printf("%d\n",(p2[m]-f[(1<<n)-1]+P)%P);
return 0;
}
D,E,F 十分有意思。
标签：Atcoder,ch,Contest,int,while,le,016,isdigit,getchar From： https://www.cnblogs.com/SError0819/p/17809706.html