CF1162A Zoning Restrictions Again
每个位置越高越好，暴力模拟即可。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=55;
int n,h,m;
int a[N];
int main()
{
scanf("%d%d%d",&n,&h,&m);
for(int i=1;i<=n;i++)
a[i]=h;
for(int i=1;i<=m;i++)
{
int l,r,x;
scanf("%d%d%d",&l,&r,&x);
for(int j=l;j<=r;j++)
a[j]=min(a[j],x);
}
long long ans=0;
for(int i=1;i<=n;i++)
ans+=1LL*a[i]*a[i];
printf("%lld",ans);
return 0;
}
CF1162B Double Matrix
可以发现，最后两个矩阵的 \((i,j)\) 的数分别为 \(\min(a_{i,j},b_{i,j})\)，\(\max(a_{i,j},b_{i,j})\) 会尽可能优，其他情况不会比这种情况更优，判断一下是否合法即可。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=55;
int n,m;
int a[N][N],b[N][N];
int c[N][N],d[N][N];
bool check(int s[N][N])
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(s[i][j]<=s[i-1][j]||s[i][j]<=s[i][j-1]) return false;
return true;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&b[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
c[i][j]=min(a[i][j],b[i][j]),d[i][j]=max(a[i][j],b[i][j]);
if(check(c)&&check(d)) printf("Possible");
else printf("Impossible");
return 0;
}
CF1162C Hide and Seek
枚举代币在哪个位置，判一下向左移，不动，向右移是否合法即可。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=100005;
int n,k;
int a[N];
int Max[N],Min[N];
int main()
{
scanf("%d%d",&n,&k);
memset(Min,63,sizeof(Min));
for(int i=1;i<=k;i++)
{
scanf("%d",&a[i]);
Max[a[i]]=max(Max[a[i]],i);
Min[a[i]]=min(Min[a[i]],i);
}
int ans=0;
for(int i=1;i<=n;i++)
{
if(i-1>=1&&Min[i]>Max[i-1]) ans++;
if(i+1<=n&&Min[i]>Max[i+1]) ans++;
if(Min[i]>Max[i]) ans++;
}
printf("%d",ans);
return 0;
}
CF1162D Chladni Figure
枚举 \(n\) 的因子 \(d\)，判断 \(k=d\) 的时候是否合法即可。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=200005;
int n,m;
pair<int,int>seg[N];
pair<int,int>b[N];
int tot;
bool check(int k)
{
tot=0;
for(int i=1;i<=m;i++)
{
pair<int,int>nxt={(seg[i].first+k)%n==0?n:(seg[i].first+k)%n,(seg[i].second+k)%n==0?n:(seg[i].second+k)%n};
if(nxt.first>nxt.second) swap(nxt.first,nxt.second);
b[++tot]=nxt;
}
sort(b+1,b+tot+1);
for(int i=1;i<=m;i++)
if(seg[i]!=b[i]) return false;
return true;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
if(a>b) swap(a,b);
seg[i]={a,b};
}
sort(seg+1,seg+m+1);
if(check(1))
{
printf("Yes");
return 0;
}
for(int i=2;i<=sqrt(n);i++)
if(n%i==0)
{
if(check(i)||check(n/i))
{
printf("Yes");
return 0;
}
}
printf("No");
return 0;
}
CF1162E Thanos Nim
最后的获胜条件等价于 \(0\) 的堆数要 \(> \frac{2}{n}\)。
如果最小堆的数量 \(> \frac{2}{n}\)，先手一定会取到某个最小堆，最小堆的数量会 \(\leq \frac{2}{n}\)，后手可以将最小堆的数量 \(> \frac{2}{n}\)，一直循环直到后手将 \(0\) 的堆数 \(> \frac{2}{n}\)。
那么可以推出：
如果最小堆的数量 \(\leq \frac{n}{2}\)，则先手必胜，否则后手必胜。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=55;
int n;
int a[N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
int m=*min_element(a+1,a+n+1);
int cnt=0;
for(int i=1;i<=n;i++)
if(a[i]==m) cnt++;
if(cnt>n/2) printf("Bob");
else printf("Alice");
return 0;
}
CF1162F Palindrome XOR
可以发现，\(b\) 的二进制位数一定等于 \(m\)，考虑枚举 \(a\) 的位数 \(n\)。
问题可以转化成一些限制，表示某些位置要和某些位置的数相等或不同。
考虑建图，边权为 \(1\) 的边表示这两个点的权值不同，边权为 \(0\) 的边表示这两个点的权值相同。方案数即为原图的染色方案。
对于一个二进制位，我们可以将其拆成两个点，表示这个点取 \(0\) 或 \(1\)。再用两个点 \(0,1\) 表示取 \(0\) 和 \(1\) 的点，在这两个点之间连一条权值为 \(1\) 的边。
对于某个位置 \(i\)，它的权值已经确定，就将它连向它的权值一条权值为 \(0\) 的边。
对于 \(s_i=1\)，可以在 \(a_i\) 和 \(b_i\) 之间连权值为 \(1\) 的边；\(s_i=0\) 可以在 \(a_i\) 和 \(b_i\) 之间连权值为 \(0\) 的边。
回文的限制也连一下权值为 \(0\) 的边。
可以将权值为 \(0\) 的边缩起来，然后二分图染色判断一下是否合法。如果合法，令 \(cnt\) 为图中的联通块数，这种情况下的答案为 \(2^{cnt-1}\)。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N=2005;
const int MOD=998244353;
long long pw[N];
int n;
char s[N];
int fa[N];
int getf(int v)
{
if(v==fa[v]) return v;
else return fa[v]=getf(fa[v]);
}
void merge(int u,int v)
{
int f1=getf(u),f2=getf(v);
if(f1!=f2) fa[f2]=f1;
return;
}
int ida[N],idb[N];
int id[2],tot;
vector<int>G[N];
int col[N];
bool flag;
void dfs(int u)
{
for(int v:G[u])
{
if(col[v]!=-1)
{
if(col[v]==col[u])
{
flag=true;
return;
}
else continue;
}
col[v]=col[u]^1;
dfs(v);
if(flag) return;
}
return;
}
int main()
{
scanf("%s",s+1);
n=strlen(s+1);
id[0]=++tot;
id[1]=++tot;
for(int i=1;i<=n;i++)
ida[i]=++tot,idb[i]=++tot;
pw[0]=1;
for(int i=1;i<=tot;i++)
pw[i]=pw[i-1]*2%MOD;
long long ans=0;
for(int len=2;len<=n;len++)
{
for(int i=1;i<=tot;i++)
fa[i]=i,col[i]=-1,G[i].clear();
merge(ida[len],id[1]);
merge(idb[1],id[1]);
for(int i=1;i<len;i++)
merge(ida[i],id[0]);
for(int i=len;i<=n;i++)
merge(ida[i],ida[n-(i-len+1)+1]);
for(int i=1;i<=n;i++)
{
merge(idb[i],idb[n-i+1]);
if(s[i]=='0') merge(ida[i],idb[i]);
}
G[getf(id[0])].emplace_back(getf(id[1])),G[getf(id[1])].emplace_back(getf(id[0]));
for(int i=1;i<=n;i++)
if(s[i]=='1') G[getf(ida[i])].emplace_back(getf(idb[i])),G[getf(idb[i])].emplace_back(getf(ida[i]));
flag=false;
int num=0;
for(int i=1;i<=tot;i++)
if(getf(i)==i&&col[i]==-1)
{
col[i]=0;
dfs(i);
if(flag) break;
num++;
}
if(flag) continue;
ans=(ans+pw[num-1])%MOD;
}
printf("%lld",ans);
return 0;
}