有趣的一场
A
因为所有长度为 \(k\) 的区间都要满足条件，所以对于所有 \(i\le n-k\)，都有 \(s_i=s_{i+k}\)。随便判一下就没了。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=3e5+10;
int n,m,a[N];
string s;
void solve(){
read(n),read(m);
cin>>s;
s=' '+s;
int tot=0,s1=0,s2=0;
for(int i=1;i<=m;i++){
a[i]=-1;
for(int j=i;j<=n;j+=m){
if(s[j]=='0'||s[j]=='1'){
if(a[i]==-1){
a[i]=s[j]-'0';
}
else if(a[i]!=s[j]-'0'){
puts("NO");
return;
}
}
}
if(a[i]==-1){
tot++;
}
else if(a[i]==0){
s1++;
}
else{
s2++;
}
}
if(abs(s1-s2)>tot){
puts("NO");
}
else{
puts("YES");
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t;
read(t);
while(t--){
solve();
}
return 0;
}
B
Alice 要想获胜，有三种局面：
- 一步可以追到
Bob - 她站在树直径的中点可以到达树上任何一个点
- 她可以通过步步逼近缩小
Bob的移动区域
前两种特别好判。仔细想想第三种，其实就是在 Bob 在某个节点时，Alice 在一个距离他 \(da\) 的父节点 \(x\) 上时，他无法通过一步跑到 \(x\) 子树外一个与 \(x\) 的距离大于 \(da\) 的点，即 \(db\le 2\times da\)。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=1e5+10;
int n,posa,da,posb,db,dep[N],pos;
vector<int>e[N];
void dfs(int u,int fa){
if(dep[u]>dep[pos]){
pos=u;
}
for(auto v:e[u]){
if(v==fa){
continue;
}
dep[v]=dep[u]+1;
dfs(v,u);
}
}
void solve(){
read(n),read(posa),read(posb),read(da),read(db);
for(int i=1;i<=n;i++){
dep[i]=0;
vector<int>().swap(e[i]);
}
for(int i=1,u,v;i<n;i++){
read(u),read(v);
e[u].pb(v);
e[v].pb(u);
}
pos=0;
dfs(posa,0);
if(dep[posb]<=da){
puts("Alice");
return;
}
for(int i=1;i<=n;i++){
dep[i]=0;
}
int p=pos;
pos=0;
dfs(p,0);
if(min(dep[pos],db)<=da*2){
puts("Alice");
return;
}
puts("Bob");
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t;
read(t);
while(t--){
solve();
}
return 0;
}
C
先假设只有一组询问 \((0,0)\)，怎么做？
因为是往前移，所以先删去后面的对前面是没有影响的。这样我们得到了一个贪心的策略，找到从后往前第一个 \(a_i=i\) 的数，然后模拟。但哪怕是一组，\(O(n^2)\) 也是过不去的。
我们发现模拟过程可以用线段树维护。令 \(b_i=i-a_i\)，要找的数就是从后往前的第一个 \(b_i=0\) 的数。因为 \(b_i< 0\) 的数永远不可能贡献答案，所以可以将 \(b_i<0\) 的数赋为 \(+\infty\)。那么就相当于一直找到序列下标为 \(\left[1,n\right]\) 中下标最大的最小值的下标 \(x\)，若 \(b_x=0\)，则对答案产生 \(1\) 的贡献，令 \(b_x=+\infty\)，\(b_{x+1\sim n}\) 减 \(1\)，若 \(b_x>0\)，则停止寻找。
现在假设有多组询问，每组询问的形式均为 \((0,y)\)，显然可以给每个下标都打上一个是否可以被删除，最后维护一个前缀和数组 \(s\)。因为后面的不能删除，并不影响前面的删除，只是会是答案减少 \(1\)，所以 \((0,y)\) 答案就为 \(s_{n-y}\)
将询问形式还原为 \((x,y)\)，还是先假设只有一组询问，那么本质上是将查询的下标区间变为 \(\left[x+1,n\right]\)。如果是多组询问，每组询问的形式均为 \((x,y)\) 且 \(x\) 为定值，则加上一个前缀和。
现在我们做完了几乎所有的弱化版，考虑回到原题。现在最主要的问题是 \(x\) 不同该如何处理。有一个很显然的发现，当\(y\) 相同时，\(x\) 变小，答案是不减的。因为在答案上做加法显然是要容易于在答案上做减法的，所以将所有的询问离线下来，以 \(x\) 为第一关键字从大到小排序，用一个树状数组维护那个前缀和数组。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int read(){
int s=0,f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=s*10+(ch-'0');
ch=getchar();
}
return s*f;
}
const int maxn=300010,inf=1e9;
int n,q,a[maxn],Ans[maxn];
struct tree{
int c[maxn];
int lowbit(int x){
return x&(-x);
}
void add(int x){
while(x<=n){
c[x]++;
x+=lowbit(x);
}
}
int query(int x){
int res=0;
while(x){
res+=c[x];
x-=lowbit(x);
}
return res;
}
}tr;
struct que{
int num,mn;
}ans;
struct Seg{
int num[maxn<<2],mn[maxn<<2],tag[maxn<<2];
int ls(int p){return p<<1;}
int rs(int p){return p<<1|1;}
void push_up(int p){
if(mn[rs(p)]<=mn[ls(p)]){
mn[p]=mn[rs(p)];
num[p]=num[rs(p)];
}
else{
mn[p]=mn[ls(p)];
num[p]=num[ls(p)];
}
}
void build(int p,int l,int r){
tag[p]=0;
if(l==r){
num[p]=l;
mn[p]=l-a[l];
if(mn[p]<0)mn[p]=inf;
return;
}
int mid=(l+r)>>1;
build(ls(p),l,mid);
build(rs(p),mid+1,r);
push_up(p);
}
void push_down(int p){
tag[ls(p)]+=tag[p];
tag[rs(p)]+=tag[p];
mn[ls(p)]+=tag[p];
mn[rs(p)]+=tag[p];
tag[p]=0;
}
void update(int p,int l,int r,int q_l,int q_r,int x){
if(q_l<=l&&r<=q_r){
mn[p]+=x;
tag[p]+=x;
return;
}
push_down(p);
int mid=(l+r)>>1;
if(q_l<=mid){
update(ls(p),l,mid,q_l,q_r,x);
}
if(q_r>mid){
update(rs(p),mid+1,r,q_l,q_r,x);
}
push_up(p);
}
que query(int p,int l,int r,int q_l,int q_r){
if(q_l<=l&&r<=q_r){
return que{num[p],mn[p]};
}
push_down(p);
int mid=(l+r)>>1;
if(q_l>mid){
return query(rs(p),mid+1,r,q_l,q_r);
}
if(q_r<=mid){
return query(ls(p),l,mid,q_l,q_r);
}
que ansl=query(ls(p),l,mid,q_l,q_r),ansr=query(rs(p),mid+1,r,q_l,q_r);
if(ansl.mn<ansr.mn){
return ansl;
}
return ansr;
}
}tree;
struct ask{
int x,y,num;
}qu[maxn];
bool cmp(ask x,ask y){
return x.x>y.x;
}
int main(){
n=read(),q=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
int x,y;
for(int i=1;i<=q;i++){
qu[i].x=read(),qu[i].y=read();
qu[i].num=i;
}
sort(qu+1,qu+q+1,cmp);
tree.build(1,1,n);
for(int i=1;i<=q;i++){
while(1){
ans=tree.query(1,1,n,qu[i].x+1,n);
if(ans.mn!=0)break;
tr.add(ans.num);
tree.update(1,1,n,ans.num,n,-1);
tree.update(1,1,n,ans.num,ans.num,inf);
}
Ans[qu[i].num]=tr.query(n-qu[i].y)-tr.query(qu[i].x);
}
for(int i=1;i<=q;i++){
printf("%d\n",Ans[i]);
}
return 0;
}
D
这道题说是交互题倒也不是，倒更像一个为防止被随机化卡掉，而准备了一个数据生成器（虽然我也不知道如果给定做某一个人怎么随机化）。
首先看到让我们选择一个人并获胜，可以分析出给定一个 \(n\) 后胜者是确定的。我们大胆猜测胜者和 \(n\) 的奇偶性相关。
先考虑先手获胜的情况，如果我是先手，我必然会让对手的答案对 \(n\) 取模的变化越少越好，所以考虑将 \(i\) 和 \(i+n\) 分到一组。这样后手选出来的数之和就为 \(\frac{n(n+1)}{2}+kn(k\in \mathbb{Z})\)，当 \(n\) 是偶数时，\(\frac{n+1}{2}+k\) 不是整数，故总和不为 \(2n\) 的倍数。
根据前面的猜测，那么当 \(n\) 为奇数时，先手必胜，考虑证明。可以确定的是如果 \(i\) 和 \(i+n\) 互斥的话，那么选出来的数总和 \(\frac{n(n+1)}{2}+kn(k\in\mathbb{Z})\)。因为选出来的数和没选的数的和为 \(n(2n+1)\)，\(2n+1\) 是奇数，所以 \(\frac{n+1}{2}+k\) 和 \(2n+1-\frac{n+1}{2}-k\) 中间必然有一个是偶数，即选的数的和与没选的数的和中间必然有一个为 \(2n\) 的倍数。
现在唯一需要思考的就是将如何将 \(2n\) 个数分为两组。将数放到图上，将互斥的点之间连上边，即将同一集合中两点连边，\(i\) 与 \(i+n\) 连边。因为每个点都会连两条边，且没有自环，那么得到的都是一个个环。又因为 \(i\) 和 \(i+n\) 在同一环内，所以每个环的点数都为偶数，即所有环均为偶环。对得到的图做二分图染色可以得到需要的两个集合，找到其中和为 \(2n\) 倍数的集合即可。
点击查看代码
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=1e6+10;
int n,col[N],color;
vector<int>num[N],e[N];
void dfs(int u,int c){
col[u]=c;
for(auto v:e[u]){
if(!col[v]){
dfs(v,3-c);
}
}
}
signed main(){
cin>>n;
if(n%2==0){
cout<<"First"<<endl;
for(int i=1;i<=n*2;i++){
cout<<(i-1)%n+1<<' ';
}
cout<<endl;
return 0;
}
cout<<"Second"<<endl;
for(int i=1,x;i<=n*2;i++){
cin>>x;
num[x].pb(i);
}
for(int i=1;i<=n;i++){
e[num[i][0]].pb(num[i][1]);
e[num[i][1]].pb(num[i][0]);
}
for(int i=1;i<=n;i++){
e[i].pb(i+n);
e[i+n].pb(i);
}
for(int i=1;i<=n*2;i++){
if(!col[i]){
dfs(i,1);
}
}
int s=0;
for(int i=1;i<=n*2;i++){
if(col[i]==1){
s+=i;
s=s%(2*n);
}
}
if(s==0){
for(int i=1;i<=n*2;i++){
if(col[i]==1){
cout<<i<<' ';
}
}
cout<<endl;
}
else{
for(int i=1;i<=n*2;i++){
if(col[i]==2){
cout<<i<<' ';
}
}
cout<<endl;
}
return 0;
}
E
先将每个点放一个木板，将选择 \(1\) 个 \(1\times n\) 的木板视作选择 \(n-1\) 条横着的边，减少 \(n-1\) 个木板，选择 \(1\) 个 \(n\times 1\) 的木板视作选择 \(n-1\) 条竖着的边，减少 \(n-1\) 个木板，因为木板不能重叠，所以共用一个端点的横着的边和竖着的边不能被同时选择。最后答案：总点数-总边数+二分图最大匹配。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=210,M=1e6+10;
int n,m,id[2][N][N],tot,cnt,num;
int couple[M],head[M],Tot=1;
char a[N][N];
bool vis[M];
struct edge{
int v,nxt;
}e[M];
void add(int u,int v){
e[++Tot].v=v;
e[Tot].nxt=head[u];
head[u]=Tot;
}
bool find(int u){
if(vis[u]){
return 0;
}
vis[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(!couple[v]||find(couple[v])){
couple[v]=u;
return 1;
}
}
return 0;
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
read(n),read(m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
a[i][j]=getchar();
while(a[i][j]!='.'&&a[i][j]!='#'){
a[i][j]=getchar();
}
if(a[i][j]=='#'){
tot++;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<m;j++){
if(a[i][j]=='#'&&a[i][j+1]=='#'){
id[0][i][j]=++cnt;
}
}
}
num=cnt;
for(int i=1;i<n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]=='#'&&a[i+1][j]=='#'){
id[1][i][j]=++cnt;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int left=id[0][i][j-1],right=id[0][i][j],up=id[1][i-1][j],down=id[1][i][j];
if(left&&up){
add(left,up);
add(up,left);
}
if(right&&up){
add(right,up);
add(up,right);
}
if(left&&down){
add(left,down);
add(down,left);
}
if(right&&down){
add(right,down);
add(down,right);
}
}
}
int ans=tot-cnt;
for(int i=1;i<=num;i++){
for(int j=1;j<=cnt;j++){
vis[j]=0;
}
if(find(i)){
ans++;
}
}
write_endl(ans);
return 0;
}
一道类似的题
这题一个点可以被两个木板覆盖，所以将一个点可以被哪两条木板覆盖表示出来，将两条木板连边，得到答案为二分图最小点覆盖即二分图最大匹配。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=55;
int n,m,cnt1,cnt2,line[N],vis[N*N],couple[N*N];
char s[N][N];
vector<int>e[N*N];
bool find(int u,int T){
if(vis[u]==T){
return 0;
}
vis[u]=T;
for(auto v:e[u]){
if(!couple[v]||find(couple[v],T)){
couple[v]=u;
return 1;
}
}
return 0;
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
read(n),read(m);
for(int i=1;i<=n;i++){
s[i][0]='.';
for(int j=1;j<=m;j++){
s[0][j]='.';
s[i][j]=getchar();
while(s[i][j]!='.'&&s[i][j]!='*'){
s[i][j]=getchar();
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(s[i][j]=='*'&&s[i][j-1]=='.'){
cnt1++;
}
if(s[i][j]=='*'&&s[i-1][j]=='.'){
line[j]=++cnt2;
}
if(s[i][j]=='*'){
e[cnt1].push_back(line[j]);
}
}
}
int ans=0;
for(int i=1;i<=cnt1;i++){
if(find(i,i)){
ans++;
}
}
write_endl(ans);
return 0;
}