链接
C. Snuke and Spells
容易发现合法序列排序后一定是若干段值域连续的部分组成:
可以发现最小次数就是重叠/空出的部分大小。
每次修改只会对 \(O(1)\) 个点 \(±1\),直接维护即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define N 200010
using namespace std;
int a[N],c[N],r[N];
int ans=0;
void add(int x){if(r[x]<=1){--r[x];return;}c[--r[x]]++;if(c[r[x]]==1) ++ans;}
void del(int x){if(r[x]<=0){++r[x];return;}if(c[r[x]]==1) --ans;c[r[x]++]--;}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) r[i]=i+1;
for(int i=1;i<=n;i++) scanf("%d",&a[i]),add(a[i]);
for(int i=1;i<=m;i++)
{
int x,y;scanf("%d%d",&x,&y);
del(a[x]);a[x]=y;add(a[x]);
printf("%d\n",n-ans);
}
return 0;
}
D. Game on Tree
考虑每个子树分别计算 SG 值。令 \(f_i\) 表示以 \(i\) 为根的子树(不能删 \(i\))的 SG 值。
可以发现在不能删 \(i\) 情况下,所有子树都等价于一个子问题,所以可以直接异或。
对于子树从不能删根到能够删根,容易发现本质是将子树所有 SG +1 并加上一个 \(0\) 元素,所以 \(\text{mex}\) 就是 \(f_v+1\)。
故 \(f_u=\bigoplus(f_v+1)\)。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define N 200010
using namespace std;
int a[N],c[N],r[N];
int ans=0;
void add(int x){if(r[x]<=1){--r[x];return;}c[--r[x]]++;if(c[r[x]]==1) ++ans;}
void del(int x){if(r[x]<=0){++r[x];return;}if(c[r[x]]==1) --ans;c[r[x]++]--;}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) r[i]=i+1;
for(int i=1;i<=n;i++) scanf("%d",&a[i]),add(a[i]);
for(int i=1;i<=m;i++)
{
int x,y;scanf("%d%d",&x,&y);
del(a[x]);a[x]=y;add(a[x]);
printf("%d\n",n-ans);
}
return 0;
}
E. Jigsaw
考虑如果 \(c=0\) 令其左权值为 \((a,0)\),否则为 \((c,1)\),右权值若 \(d=0\) 为 \((b,1)\) 否则为 \((d,0)\),可以发现这等价于在左权值与右权值之间连了一条边,最后要求找一个环满足所有边被恰好经过一次。可以发现这就是欧拉回路。
欧拉回路的充要条件是所有点入度=出度且图弱联通。
注意 \((a,0)\) 与 \((b,1)\) 之间是可以任意转化的,考虑建一个特殊点,可以发现每个 \((a,0)\) 缺少的出度是唯一的,缺少的出度只能连向特殊点,\((b,1)\) 同理。
复杂度 \(O(n)\)。
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 100010
using namespace std;
int f[N],id[N],od[N];
int find(int x){return f[x]==x?f[x]:(f[x]=find(f[x]));}
void merge(int x,int y){f[find(x)]=find(y);}
void add(int x,int y){merge(x,y);id[y]++;od[x]++;}
int main()
{
int n,h;
scanf("%d%d",&n,&h);
int m=h*2+1;
for(int i=1;i<=m;i++) f[i]=i;
for(int i=1,a,b,c,d;i<=n;i++)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
if(c==0 && d==0) add(a,b+h);
else if(c==0) add(a,d);
else if(d==0) add(c+h,b+h);
else add(c+h,d);
}
for(int i=1;i<=h;i++) if(od[i]<id[i]){puts("NO");return 0;}
for(int i=h+1;i<m;i++) if(od[i]>id[i]){puts("NO");return 0;}
for(int i=1;i<m;i++) if(od[i]!=id[i]) merge(i,m);
if(find(m)!=find(1)){puts("NO");return 0;}
for(int i=1;i<m;i++) if((od[i] || id[i]) && find(i)!=find(1)){puts("NO");return 0;}
puts("YES");
return 0;
}
F. Zigzag
咕咕咕
- AtCoder Contest Grand 017atcoder contest grand 017 authentic atcoder contest grand negative atcoder contest grand atcoder contest radius grand atcoder contest grand 001 atcoder contest grand 022 avoidance atcoder contest grand histogram atcoder contest grand atcoder contest grand 019 atcoder contest grand 039