原文链接https://www.cnblogs.com/zhouzhendong/p/AtCoder-Grand-Contest-from-11-to-20.html
UPD(2018-11-16): 改个标题再弃坑。
发现 EF 这种神仙题根本做不动，这次做题顺序我要改一改了……
咕咕咕
AGC011F
AGC012F
AGC013D
AGC013E
AGC013F
AGC014E
AGC014F
AGC015E
AGC015F
AGC017F
AGC011
B 简单题。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=;
int read(){
int x=;
char ch=getchar();
while (!isdigit(ch))
ch=getchar();
while (isdigit(ch))
x=(x<<)+(x<<)+(ch^),ch=getchar();
return x;
}
int n,a[N];
LL s[N];
int main(){
n=read();
for (int i=;i<=n;i++)
a[i]=read();
sort(a+,a+n+);
for (int i=;i<=n;i++)
s[i]=s[i-]+a[i];
int ans=;
for (int i=n;i>=;i--)
if (s[i]*<a[i+])
break;
else
ans++;
cout << ans;
return ;
}
AGC011B
C 画个图就可以发现：一对边 (a,b) 和 (c,d) 的效果就是连接点对 (a,c)~(b,d) 和连接点对 (a,d)~(b,c) 。于是，对于原图中每一个连通块，都会与其他任何一个原图中的连通块在最终图的矩阵图中产生一个矩形连通区，每一个矩形连通区的连通块个数为 2 或 1 ，取决于生成这个矩形连通区的两个原图中的连通块能否黑白染色。注意孤立点需要特殊处理。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=;
int read(){
int x=;
char ch=getchar();
while (!isdigit(ch))
ch=getchar();
while (isdigit(ch))
x=(x<<)+(x<<)+(ch^),ch=getchar();
return x;
}
int n,m;
vector <int> e[N];
LL ans;
int vis[N],c[N];
int tot=,size=,sz=;
int dfs(int x,int f){
vis[x]=;
c[x]=f;
sz++;
int res=;
for (auto y : e[x])
if (!vis[y])
res|=dfs(y,f^);
else
res|=c[x]==c[y];
return res;
}
void solve(int x){
if (e[x].empty())
return;
size++;
tot+=dfs(x,)^;
}
LL _2(int x){
return 1LL*x*x;
}
int main(){
n=read(),m=read();
for (int i=;i<=m;i++){
int a=read(),b=read();
e[a].push_back(b);
e[b].push_back(a);
}
memset(vis,,sizeof vis);
for (int i=;i<=n;i++)
if (!vis[i])
solve(i);
ans=_2(n)-_2(sz)+_2(size)+_2(tot);
cout << ans;
return ;
}
AGC011C
D 有趣的打表找规律题。
#include <bits/stdc++.h>
using namespace std;
const int N=;
int n,k,a[N];
char s[N];
int main(){
cin >> n >> k >> s+;
for (int i=;i<=n;i++)
a[i]=s[i]-'A';
int t=,h=;
while (k--){
if (!(a[h]^t)){
a[h]^=;
continue;
}
if (!((a[h+]^t)&))
a[h]^=;
t^=,h++;
if (h==n)
break;
}
if (k>&&(n&))
a[h]^=k&;
else if (k>)
h++;
for (int i=h;i<=n;i++)
putchar('A'+(a[i]^t));
for (int i=n-h+;i<=n;i++)
putchar('A'+((n-i)&));
return ;
}
AGC011D
E
1. 一个上升数一定是由不超过 9 个形如 111...111 的数加起来组成的。
2. 所有形如 111...111 的数可以表示成 $\frac{10^k-1}9$ 。
3. 假设一个大整数能够拆成 n 个形如 $10^k$ 的数的和，那么 n 的下界就是这个大整数的各个数位之和。
于是就可以做了：将原数 × 9 ，然后线性枚举最少拆成几个，显然拆出来的数不多；每次 + 1 维护一下大整数及其下界，判定一下即可。很容易证明复杂度是正确的。
#include <bits/stdc++.h>
using namespace std;
const int N=;
int n,a[N];
char s[N];
int main(){
scanf("%s",s);
n=strlen(s);
for (int i=;i<n;i++)
a[i]=(s[i]-'')*;
reverse(a,a+n);
for (int i=;i<n;i++)
a[i+]+=a[i]/,a[i]%=;
while (a[n])
n++,a[n+]+=a[n]/,a[n]%=;
int now=;
for (int i=;i<n;i++)
now+=a[i];
for (int i=;;i++){
int p=;
while (a[p]==)
p++;
a[p]++,now+=-p*;
while (p--)
a[p]=;
if (now<=i)
return printf("%d",(i+)/),;
}
return ;
}
AGC011E
AGC012
B 真是一道清新的题目。一开始没有看到 $d_i\leq 10$ 的条件，想了半天不会。那么这个条件有什么用呢？
首先转化题意，我们需要得到在每一个节点上操作的最后一个操作编号是多少。这个就相当于每次对于连通块取 max 。由于 $d_i\leq 10$ ，所以一个节点的操作范围最多经过 10 条边，而且每一个节点上最多有 10 种 d 值的操作（因为取了 max ）。接下来考虑 “扩散” 操作：将每一个节点的操作 的 d 值减一后的结果 ，作用到其相邻节点 。由于 d 的限制，所以这种扩散操作最多进行 10 次。枚举节点并枚举边比较麻烦，所以直接枚举边就好了。
#include <bits/stdc++.h>
using namespace std;
const int N=;
int read(){
int x=;
char ch=getchar();
while (!isdigit(ch))
ch=getchar();
while (isdigit(ch))
x=(x<<)+(x<<)+(ch^),ch=getchar();
return x;
}
int n,m,q;
int a[N],b[N],c[N];
int Tag[N][];
void push(int x,int y){
for (int i=;i>;i--)
Tag[y][i-]=max(Tag[y][i-],Tag[x][i]);
}
int main(){
n=read(),m=read();
for (int i=;i<=m;i++)
a[i]=read(),b[i]=read();
q=read();
memset(Tag,,sizeof Tag);
for (int i=;i<=q;i++){
int v=read(),d=read();
c[i]=read();
Tag[v][d]=max(Tag[v][d],i);
}
for (int kk=;kk--;)
for (int i=;i<=m;i++){
push(a[i],b[i]);
push(b[i],a[i]);
}
for (int i=;i<=n;i++){
int Max=;
for (int j=;j<=;j++)
Max=max(Max,Tag[i][j]);
cout << c[Max] << endl;
}
return ;
}
AGC012B
C 简单构造题。首先将 a[1~100] 填充成 a[i]=i ，然后考虑后面怎么填。如果接下来直接填 1~k 那么会对答案做出 $2^k-1$ 的贡献，注意到空集是不行的。然后，在这个东西的基础上，如果在 a 的后面插入一个 k+1 ，那么会新得到 $2^a$ 种 good 串；类似于这样，我们先讲 n 加一，然后二进制分解，然后直接对于每一个二进制位构造就好了。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=;
LL read(){
LL x=;
char ch=getchar();
while (!isdigit(ch))
ch=getchar();
while (isdigit(ch))
x=(x<<)+(x<<)+(ch^),ch=getchar();
return x;
}
LL n;
int a[N],tot;
int main(){
n=read()+;
tot=;
for (int i=;i<=tot;i++)
a[i]=i;
int t=;
while (n>>(t+))
t++;
for (int i=;i<=t;i++)
a[++tot]=i;
int k=t;
for (int x=t-;x>=;x--)
if (n>>x&){
tot++;
for (int i=tot;i>+x;i--)
a[i]=a[i-];
a[+x]=++k;
}
cout << tot << endl;
for (int i=;i<=tot;i++)
cout << a[i] << " ";
return ;
}
AGC012C
D 所有的球可以分成两类：一类是*的，可以任意排列；另一类的位置是固定的。一个球是*的，当且仅当两种情况：1. 它可以直接和一个和它颜色不同的球交换；2. 它可以和一个和它颜色相同的最小的球交换，并且这个最小的球是*的。求出这个东西之后，直接计算一下排列数就好了。
#include <bits/stdc++.h>
using namespace std;
const int N=,mod=1e9+;
int read(){
int x=;
char ch=getchar();
while (!isdigit(ch))
ch=getchar();
while (isdigit(ch))
x=(x<<)+(x<<)+(ch^),ch=getchar();
return x;
}
int INF;
int n,x,y;
int c[N],w[N];
int Min[N],cnt[N];
int Fac[N],Inv[N];
int id[N];
int Pow(int x,int y){
int ans=;
for (;y;y>>=,x=1LL*x*x%mod)
if (y&)
ans=1LL*ans*x%mod;
return ans;
}
bool cmp(int a,int b){
return Min[a]<Min[b];
}
int main(){
n=read(),x=read(),y=read();
INF=max(x,y)+;
for (int i=;i<N;i++)
Min[i]=INF;
for (int i=;i<=n;i++){
c[i]=read(),w[i]=read(),id[i]=i;
Min[c[i]]=min(Min[c[i]],w[i]);
}
for (int i=;i<=n;i++)
if (w[i]+Min[c[i]]<=x)
w[i]=Min[c[i]];
sort(id+,id+n+,cmp);
int allcnt=;
memset(cnt,,sizeof cnt);
for (int i=;i<=n;i++){
if (id[]!=c[i]){
if (w[i]+Min[id[]]<=y)
allcnt++,cnt[c[i]]++;
}
else if (w[i]+Min[id[]]<=y)
allcnt++,cnt[c[i]]++;
}
for (int i=Fac[]=;i<=n;i++)
Fac[i]=1LL*Fac[i-]*i%mod;
Inv[n]=Pow(Fac[n],mod-);
for (int i=n;i>=;i--)
Inv[i-]=1LL*Inv[i]*i%mod;
int ans=Fac[allcnt];
for (int i=;i<N;i++)
ans=1LL*ans*Inv[cnt[i]]%mod;
cout << ans;
return ;
}
AGC012D
E 一道超级好题。首先，我们发现“跳跃”最多有 $O(\log _2 V)$ 次。对于当前 v ，我们总可以把当前序列变成一段一段的连通块。对于每一个 d ，预处理出跳跃 d 次后，从每一个点向左最左能走到的位置，向右最右能走到的位置，分别记为 R[d][i] 和 L[d][i] 。于是就相当于每一层最多只能覆盖一个连通块。考虑预处理出 mR[S] 表示在 S 集合内的层已经有覆盖，能从左边开始覆盖到的最远点位置；同理，预处理一个 mL[S] ；显然
$$mR[S]=\max\{R[k][mR[S-k]+1] | k\in S\}$$
注意这里的 减号是 集合运算。
注意 d=0 的层不能被计算，因为最后算的时候，d=0 的层是被钦定的。
于是最后询问的时候，就被转化成了左右两边两个询问。问题解决。
#include <bits/stdc++.h>
using namespace std;
int read(){
int x=,f=;
char ch=getchar();
while (!isdigit(ch)&&ch!='-')
ch=getchar();
if (ch=='-')
f=-,ch=getchar();
while (isdigit(ch))
x=(x<<)+(x<<)+(ch^),ch=getchar();
return x*f;
}
const int N=;
int n,v;
int x[N];
int R[][N],L[][N],mR[N],mL[N];
int Max[N];
int main(){
n=read(),v=read();
for (int i=;i<=n;i++)
x[i]=read();
int d;
for (d=;d<;d++){
int k=v>>d;
for (int i=,j;i<=n;i=j+){
for (j=i;j<n&&x[j+]-x[j]<=k;j++);
for (int k=i;k<=j;k++)
L[d][k]=i,R[d][k]=j;
}
if (k==)
break;
}
for (int i=;i<=d;i++)
R[i][n+]=n,L[i][]=;
for (int i=;i<(<<d);i++)
mR[i]=,mL[i]=n+;
for (int i=;i<(<<d);i++)
for (int j=;j<d;j++)
if (i>>j&){
mR[i]=max(mR[i],R[j+][mR[i^(<<j)]+]);
mL[i]=min(mL[i],L[j+][mL[i^(<<j)]-]);
}
int base=(<<d)-;
memset(Max,-,sizeof Max);
for (int i=;i<(<<d);i++){
int x=i,y=i^base;
Max[mL[x]]=max(Max[mL[x]],mR[y]);
}
for (int i=;i<=n+;i++)
Max[i]=max(Max[i],Max[i-]);
for (int i=;i<=n;i++){
int l=L[][i],r=R[][i];
puts(Max[r+]>=l-?"Possible":"Impossible");
}
return ;
}
AGC012E
AGC013
B 挺好的一道题。如果往“点双”里想就GG了。假设我们现在有一条路径 (S,T) ，如果 S 不满足条件，那么至少有一个点是空出来的，我们将 S 替换成那个点，路径变长 1 即可；当然新的 S 仍然可能不满足，那么就重复上述过程，直到满足为止。对于 T 也同理即可。
#include <bits/stdc++.h>
using namespace std;
const int N=;
int read(){
int x=;
char ch=getchar();
while (!isdigit(ch))
ch=getchar();
while (isdigit(ch))
x=(x<<)+(x<<)+(ch^),ch=getchar();
return x;
}
int n,m;
vector <int> e[N],a1,a2;
int vis[N];
void dfs(int x,vector <int> &a){
vis[x]=;
a.push_back(x);
for (auto y : e[x])
if (!vis[y])
return dfs(y,a);
}
int main(){
n=read(),m=read();
int k1,k2;
for (int i=;i<=m;i++){
int a=read(),b=read();
e[a].push_back(b);
e[b].push_back(a);
if (i==)
k1=a,k2=b;
}
vis[k1]=vis[k2]=;
dfs(k1,a1);
dfs(k2,a2);
reverse(a1.begin(),a1.end());
cout << (int)(a1.size()+a2.size()) << endl;
for (auto x : a1)
cout << x << " ";
for (auto x : a2)
cout << x << " ";
return ;
}
AGC013B
C 看似挺眼熟的，还是做了好久。首先我们可以发现以下几点性质：
1. 两个人发生一次碰撞相当于两个人交换身份。
2. 所有人的顺序始终不变。
于是我们只需要求出最终位置序列以及第一个人的位置就好了。
接下来的关键在于求第一个人的位置。
菜鸡zzd于是就写了个毒瘤二分。各种细节被坑到怀疑人生。
正解十分优美：考虑第一个人的排名(rk)变化原因：有一个人从 位置 L-1 到了 0 ，于是 rk++ ；或者是一个人从位置 0 到了 L-1 ，于是 rk-- 。
于是就可以很方便的解决这个问题啦。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=;
int read(){
int x=,f=;
char ch=getchar();
while (!isdigit(ch)&&ch!='-')
ch=getchar();
if (ch=='-')
f=-,ch=getchar();
while (isdigit(ch))
x=(x<<)+(x<<)+(ch^),ch=getchar();
return x*f;
}
int n,Len,T;
int x[N],w[N],res[N];
vector <int> v1,v2;
int s1,s2;
bool check(int x){
int L,R;
if (!w[])
L=(x-)>>,R=x>>;
else
L=x>>,R=(x-)>>;
LL tot=1LL*(L/s1)*Len+v1[L%s1]
+1LL*(R/s2)*Len+v2[R%s2];
return tot<=(T<<);
}
int main(){
n=read(),Len=read(),T=read();
v1.clear();
v2.clear();
for (int i=;i<n;i++){
x[i]=read(),w[i]=read()&;
if (w[i])
res[i]=(x[i]+T)%Len;
else
res[i]=((x[i]-T)%Len+Len)%Len;
if (!w[i])
v2.push_back(x[i]-x[]);
else
v1.push_back((x[]-x[i]+Len)%Len);
}
if (v1.empty()||v2.empty()){
for (int i=;i<n;i++)
printf("%d\n",res[i]);
return ;
}
sort(res,res+n);
sort(v1.begin(),v1.end());
s1=v1.size(),s2=v2.size();
int L=,R=T<<,ans=;
while (L<=R){
int mid=(L+R)>>;
if (check(mid))
L=mid+,ans=mid;
else
R=mid-;
}
int p0;
if (ans==)
p0=w[]?(x[]+T)%Len:(x[]+Len-T)%Len;
else {
if (!w[])
L=(ans-)>>,R=ans>>;
else
L=ans>>,R=(ans-)>>;
int tot=L/s1*Len+v1[L%s1]+R/s2*Len+v2[R%s2];
T=(T<<)-tot;
LL p=(R/s2*Len+v2[R%s2])-(L/s1*Len+v1[L%s1]);
if (w[]^(ans&))
p+=T;
else
p-=T;
p/=;
p0=((p+x[])%Len+Len)%Len;
}
int p=lower_bound(res,res+n,p0)-res;
if (w[]^(ans&)){
if (n>&&res[(p+)%n]==res[p])
p=(p+)%n;
}
else
if (n>&&res[(p+n-)%n]==res[p])
p=(p+n-)%n;
for (int i=;i<n;i++)
printf("%d\n",res[(p+i)%n]);
return ;
}
AGC013C(zzd)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=;
int n,L,T,p=,res[N];
int main(){
cin >> n >> L >> T;
for (int i=,x,w;i<n;i++){
cin >> x >> w;
if (w==)
res[i]=(x+T)%L,p=(p+(T+x)/L%n+n)%n;
else
res[i]=((x-T)%L+L)%L,p=(p-(T+L-x-)/L%n+n)%n;
}
sort(res,res+n);
for (int i=;i<n;i++,p=(p+)%n)
printf("%d\n",res[p]);
return ;
}
AGC013C
AGC014
B 直接猜结论：每一个节点被覆盖偶数次就是有解，否则无解。
#include <bits/stdc++.h>
using namespace std;
int read(){
int x=;
char ch=getchar();
while (!isdigit(ch))
ch=getchar();
while (isdigit(ch))
x=(x<<)+(x<<)+(ch^),ch=getchar();
return x;
}
const int N=;
int n,m;
int cnt[N];
int main(){
n=read(),m=read();
while (m--){
cnt[read()]^=;
cnt[read()]^=;
}
int ans=;
for (int i=;i<=n;i++)
ans+=cnt[i];
puts(ans?"NO":"YES");
return ;
}
AGC014B
C 简单题。
#include <bits/stdc++.h>
using namespace std;
const int N=;
int n,m,k;
char s[N][N];
int d[N][N],qx[N*N],qy[N*N];
int dx[]={ , ,-, };
int dy[]={-, , , };
bool check(int x,int y){
return <=x&&x<=n&&<=y&&y<=m&&s[x][y]!='#';
}
int main(){
cin >> n >> m >> k;
for (int i=;i<=n;i++)
scanf("%s",s[i]+);
memset(d,,sizeof d);
int sx,sy;
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
if (s[i][j]=='S')
sx=i,sy=j;
int head=,tail=;
tail++;
qx[tail]=sx,qy[tail]=sy;
d[sx][sy]=;
while (head<tail){
head++;
int x=qx[head],y=qy[head];
if (d[x][y]==k+)
continue;
for (int i=;i<;i++){
int nx=x+dx[i],ny=y+dy[i];
if (!check(nx,ny)||d[nx][ny])
continue;
d[nx][ny]=d[x][y]+;
tail++;
qx[tail]=nx,qy[tail]=ny;
}
}
int ans=;
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
if (s[i][j]!='#'&&d[i][j]){
if (i==||j==||i==n||j==m)
ans=;
else {
ans=min(ans,(i-+k-)/k+);
ans=min(ans,(j-+k-)/k+);
ans=min(ans,(n-i+k-)/k+);
ans=min(ans,(m-j+k-)/k+);
}
}
cout << ans;
return ;
}
AGC014C
D 又是一道结论题。
首先考虑一种构造方案：
以一个入度大于 1 的节点为根，每次找到一个子节点都是叶子节点的节点 $x$ ，先手将 $x$ 染白。于是接下来按照下面几种情况讨论：
1. 节点 $x$ 有多个儿子，那么先手获胜。
2. 节点 $x$ 有 1 个儿子，对手将这个儿子染黑； 于是我们将子树 $x$ 删除。
如果到最终也没有出现第一种情况，则后手获胜。为什么呢？我们将第二种情况视为节点 $x$ 与一个节点匹配，那么如果最终都没有出现第一种情况，则原图必然满足二分图匹配，那么无论先手选择哪一个节点染白，后手都可以选择其对应点染黑，则最终任意一个白点周围都至少存在一个黑点。
#include <bits/stdc++.h>
using namespace std;
const int N=;
int read(){
int x=;
char ch=getchar();
while (!isdigit(ch))
ch=getchar();
while (isdigit(ch))
x=(x<<)+(x<<)+(ch^),ch=getchar();
return x;
}
int n,in[N],rem[N];
vector <int> e[N];
int dfs(int x,int pre){
int s=;
for (auto y : e[x])
if (y!=pre){
if (dfs(y,x))
return ;
s+=rem[y];
}
if (s>)
return ;
rem[x]=!s;
return ;
}
int main(){
n=read();
for (int i=;i<n;i++){
int a=read(),b=read();
e[a].push_back(b);
e[b].push_back(a);
in[a]++,in[b]++;
}
if (n==)
return puts("Second"),;
int rt=;
for (int i=;i<=n;i++)
if (in[i]>)
rt=i;
puts(dfs(rt,)?"First":"Second");
return ;
}
AGC014D
AGC015
C 题目里面说了一个性质：所有连通块的连通关系都是树（没有环）。于是矩形中的连通块个数就是点数 - 边数。
#include <bits/stdc++.h>
#define y1 __zzd001
using namespace std;
int read(){
int x=;
char ch=getchar();
while (!isdigit(ch))
ch=getchar();
while (isdigit(ch))
x=(x<<)+(x<<)+(ch^),ch=getchar();
return x;
}
const int N=;
int n,m,q;
int g[N][N],s1[N][N],s2[N][N],s3[N][N];
int main(){
n=read(),m=read(),q=read();
for (int i=;i<=n;i++)
for (int j=;j<=m;j++){
scanf("%1d",&g[i][j]);
s1[i][j]=s1[i][j-]+s1[i-][j]-s1[i-][j-]+g[i][j];
s2[i][j]=s2[i][j-]+(g[i][j]&&g[i-][j])
+s2[i-][j]-s2[i-][j-];
s3[i][j]=s3[i][j-]+(g[i][j]&&g[i][j-])
+s3[i-][j]-s3[i-][j-];
}
while (q--){
int x1=read(),y1=read(),x2=read(),y2=read();
int ans=s1[x2][y2]-s1[x2][y1-]-s1[x1-][y2]+s1[x1-][y1-];
ans-=s2[x2][y2]-s2[x2][y1-]-s2[x1][y2]+s2[x1][y1-];
ans-=s3[x2][y2]-s3[x2][y1]-s3[x1-][y2]+s3[x1-][y1];
printf("%d\n",ans);
}
return ;
}
AGC015C
D 做这个题绕了个弯子，导致效率不高。
考虑到取 [A,B] 中的数 OR ，则最高的一些位必然是固定的，这个取决于 A 和 B 的最长公共前缀。
接下来我们设一个整数 x 的二进制形式下从最小位起第 i+1 位为 x[i] 。
设 A 和 B 在二进制下的不同的最高位为 A[i] 和 B[i] 。由于 A<B ，则 A[i] = 0, B[i] = 1 。接下来我们考虑分类讨论：
（设最终的 OR 结果为 s, A' = A and $(2^i-1)$ , B' = B and $(2^i-1)$）
1. 强制 s[i] = 0 ：于是我们可以任意取在 $[A^\prime,2^i)$ 范围内的值作为 s 。
2. 强制 s[i] = 0 ：设小于 $B^\prime$ 的最大二进制幂为 $2^k$ ，则我们可以取在 $[0,2^{k+1})\cup [A^\prime,2^i)$ 范围内的值作为 s 。
都挺容易证明的吧。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL A,B;
int main(){
cin >> A >> B;
if (A==B)
return puts(""),;
for (int i=;i>=;i--)
if ((~A>>i&1LL)&&(B>>i&1LL)){
A&=(1LL<<i)-;
B&=(1LL<<i)-;
LL ans=(1LL<<i)-A,k=;
while (B)
B>>=,k++;
ans+=min((1LL<<k)+(1LL<<i)-A,1LL<<i);
cout << ans << endl;
return ;
}
return ;
}
AGC015D
AGC016
B 简单题
#include <bits/stdc++.h>
using namespace std;
const int N=;
int n,a[N];
int main(){
cin >> n;
for (int i=;i<=n;i++)
cin >> a[i];
sort(a+,a+n+);
if (a[n]-a[]>)
return puts("No"),;
if (a[]==a[n])
return puts(a[]==n-||(a[]<n&&n%a[]==)?"Yes":"No"),;
int t=;
for (int i=;i<=n;i++)
if (a[i]==a[n])
t++;
if (n-t+<=a[n]&&a[n]<=n-t+t/)
puts("Yes");
else
puts("No");
return ;
}
AGC016B
C 构造题。
#include <bits/stdc++.h>
using namespace std;
const int N=;
int H,W,h,w;
int main(){
cin >> H >> W >> h >> w;
if (H%h==&&W%w==)
return puts("No"),;
puts("Yes");
int v1=N,v2=N*(w*h-)+;
for (int i=;i<=H;i++,puts(""))
for (int j=;j<=W;j++)
if (i%h==&&j%w==)
printf("%d ",-v2);
else
printf("%d ",v1);
return ;
}
AGC016C
D 这题的心酸就不说了。 设 s 为所有数的异或值，那么，对于一个数 $a_i$ 进行操作的效果相当于 $swap(a_i,s)$ 。于是问题就变成了通过 s 来交换位置使得所有数到对应位置。首先我们将本来位置就正确的扔掉。然后考虑从中找出一些环，则每一个环对于答案的贡献一定是 |环长|+1 ，至于包含 s 的环，贡献必然等于 |环长| 。于是考虑最小化环的个数。我们可以发现，对于任意一种构造环的方法，如果 $b_i=b_j$ ，那么一定可以通过交叉来让他们到一个环里。于是问题得到简化：相同的数值一定在同一个环里。最终，并查集搞搞即可。
#include <bits/stdc++.h>
using namespace std;
int read(){
int x=;
char ch=getchar();
while (!isdigit(ch))
ch=getchar();
while (isdigit(ch))
x=(x<<)+(x<<)+(ch^),ch=getchar();
return x;
}
const int N=;
int n;
int a[N],b[N],A[N],B[N];
map <int,int> Map;
int fa[N],cnt[N];
int getf(int x){
return fa[x]==x?x:fa[x]=getf(fa[x]);
}
void Merge(int x,int y){
fa[getf(x)]=getf(y);
}
int main(){
n=read();
for (int i=;i<=n;i++)
a[i]=read(),a[n+]^=a[i];
for (int i=;i<=n;i++)
b[i]=read(),b[n+]^=b[i];
for (int i=;i<=n+;i++){
A[i]=a[i];
B[i]=b[i];
}
sort(A+,A+n+);
sort(B+,B+n+);
for (int i=;i<=n+;i++)
if (A[i]!=B[i])
return puts("-1"),;
int _n=;
for (int i=;i<=n;i++)
if (a[i]!=b[i])
_n++,a[_n]=a[i],b[_n]=b[i];
a[_n+]=a[n+],b[_n+]=b[n+];
n=_n;
int m=;
for (int i=;i<=n+;i++)
a[i]=Map[a[i]]?Map[a[i]]:Map[a[i]]=++m;
for (int i=;i<=n+;i++)
b[i]=Map[b[i]];
for (int i=;i<=m;i++)
fa[i]=i;
for (int i=;i<=n+;i++)
Merge(b[i],a[i]);
for (int i=;i<=m;i++)
cnt[getf(i)]++;
int ans=n-;
for (int i=;i<=m;i++)
if (cnt[i])
ans++;
printf("%d",ans);
return ;
}
AGC016D
E 考虑当一个点不能被删除的时候，那么，所有连着它的边都必须选择另一边；如果一条边选择了某一个点，则在这条边之前出现的任何点都不能选他。于是只要枚举点对，然后对于边倒着跑一遍就好了。这里我偷了个懒，枚举的是点对，时间复杂度是 $O(n^2 m)$ ，居然过了。实际上处理出每一个点的答案再用 bitset 优化合并可以达到更好的效果。我懒得写了。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL read(){
LL x=,f=;
char ch=getchar();
while (!isdigit(ch)&&ch!='-')
ch=getchar();
if (ch=='-')
f=-,ch=getchar();
while (isdigit(ch))
x=(x<<)+(x<<)+(ch^),ch=getchar();
return x*f;
}
const int N=,M=;
int n,m;
int x[M],y[M];
int vis[N];
int check(){
for (int i=m;i>=;i--){
int a=x[i],b=y[i];
if (vis[a]&&vis[b])
return ;
if (!vis[a]&&!vis[b])
continue;
vis[a]=vis[b]=;
}
return ;
}
int main(){
n=read(),m=read();
for (int i=;i<=m;i++)
x[i]=read(),y[i]=read();
int ans=;
for (int i=;i<=n;i++)
for (int j=i+;j<=n;j++){
memset(vis,,sizeof vis);
vis[i]=vis[j]=;
ans+=check();
}
cout << ans << endl;
return ;
}
AGC016E
F 这题太巧妙了，根本想不到。
首先我们考虑如何判定一个图是否先手必胜。我们根据其有向边的关系，求一个每一个节点的 SG 值，于是，如果节点 1 和节点 2 的 SG 值 XOR 起来不是 0 ，那么先手必胜，否则后手必胜。
这一题 N<=15 ，我们如果直接状压 SG 情况会 TLE 。
于是我考虑简化状态：如果 1-> 2 最终有边，那么必然先手必胜。于是我们只需要处理出最后 13 个点的每一种 SG 值情况的出现次数（算了一下大约在 3e7 以下），然后直接对于每一种情况花 O(n) 来计入到总贡献中。但是还是 TLE 了，由于常数较大。
标算的做法十分巧妙： 我们考虑补集转化，求出 1 和 2 的 SG 值相同的情况总数。
设 dp[S] 为在所有点集 S 中的边的取舍情况中，不会使得点 1 和 2 的 SG 值不同的方案数。
考虑枚举一个集合 i ，表示当前集合中 SG 值为 0 的元素集合，显然 | i | > 0 ，且 节点 1 和 2 要么都在 i 中，要么都不在； 设 $j = \complement_S i$ 。我们考虑以下 4 种边的方案：
1. i -> i ： 显然是没有边的
2. j -> i ： 每一个 j 中的节点至少存在一条连向 i 中节点的边。
3. i -> j ： 这些边可以任意连。
4. j -> j ： 这个是最关键的一部分：我们将 j 中的所有节点的 SG 值都 -1 之后，发现方案数就是 dp[j] ！
于是直接加个预处理之后就可以在 $O(3^nn+2^nn^2)$ 的时间复杂度内解决这个问题了。
#include <bits/stdc++.h>
using namespace std;
int read(){
int x=;
char ch=getchar();
while (!isdigit(ch))
ch=getchar();
while (isdigit(ch))
x=(x<<)+(x<<)+(ch^),ch=getchar();
return x;
}
const int N=,S=<<N,mod=1e9+;
void Add(int &x,int y){
if ((x+=y)>=mod)
x-=mod;
}
int n,m;
int g[N][N],pw[N*N],cnte[N][S],dp[S];
int DP(int S){
int &v=dp[S];
if (~v)
return v;
if (!S)
return v=;
int d[N],t=;
for (int i=;i<n;i++)
if (S>>i&)
d[t++]=i;
v=;
for (int k=;k<(<<t);k++){
int i=;
for (int j=;j<t;j++)
if (k>>j&)
i|=<<d[j];
if ((i&)==||(i&)==)
continue;
int j=S^i,now=;
// i -> i no Edges
// j -> i at least one per node
for (int x=;now&&x<n;x++)
if (j>>x&)
now=1LL*now*(pw[cnte[x][i]]-)%mod;
if (!now)
continue;
// i -> j all
for (int x=;x<n;x++)
if (i>>x&)
now=1LL*now*pw[cnte[x][j]]%mod;
// j -> j DP(j)
now=1LL*now*DP(j)%mod;
Add(v,now);
}
return v;
}
int main(){
for (int i=pw[]=;i<N*N;i++)
pw[i]=*pw[i-]%mod;
n=read(),m=read();
memset(g,,sizeof g);
for (int i=;i<=m;i++){
int a=read()-,b=read()-;
g[a][b]=;
}
for (int x=;x<n;x++)
for (int i=;i<(<<n);i++)
for (int y=;y<n;y++)
if (g[x][y]&&(i>>y&))
cnte[x][i]++;
memset(dp,-,sizeof dp);
cout << (pw[m]-DP((<<n)-)+mod)%mod << endl;
return ;
}
AGC016F
AGC017
B 难怪过的人这么多。在写完一堆毒瘤大分讨爆了 9 发 OJ ，发现总是 wa 掉第三个点之后，猛然发现：
——原来 n 这么小啊！
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL read(){
LL x=;
char ch=getchar();
while (!isdigit(ch))
ch=getchar();
while (isdigit(ch))
x=(x<<)+(x<<)+(ch^),ch=getchar();
return x;
}
LL n,A,B,C,D;
LL LLabs(LL x){
return x<?-x:x;
}
int main(){
n=read()-,A=read(),B=read(),C=read(),D=read();
A=LLabs(B-A),D-=C;
for (LL i=;i<=n;i++){
LL j=n-i;
LL L=(i-j)*C-j*D;
LL R=(i-j)*C+i*D;
if (L<=A&&A<=R)
return puts("YES"),;
}
puts("NO");
return ;
}
AGC017B
C 把题目先转化一下：设 tax[x] 为 x 的出现次数，那么我们连接有向边 (x,x-tax[x]) 。问题被转化成了调节这些边，使得从 n 能走到 0 。
继续转化模型，将边 (x,x-tax[x]) 看作一条覆盖区间 [x-tax[x],x] 的线段，那么问题就变成了调节区间使得 [0,n] 被完全覆盖。
很容易发现这个问题的解就是没有被覆盖的区间长度。
每次操作相当于单点修改，只需要用桶维护一下单点被覆盖多少次，并动态维护没有被覆盖的区间长度就好了。
真是一道好题。
#include <bits/stdc++.h>
using namespace std;
const int N=;
int read(){
int x=;
char ch=getchar();
while (!isdigit(ch))
ch=getchar();
while (isdigit(ch))
x=(x<<)+(x<<)+(ch^),ch=getchar();
return x;
}
int n,m;
int tax[N],a[N],c[N],tot=;
int main(){
n=tot=read(),m=read();
for (int x=;x<=n;x++){
a[x]=read();
if (a[x]-tax[a[x]]>)
tot-=c[a[x]-tax[a[x]]]++==;
tax[a[x]]++;
}
while (m--){
int x=read(),y=read();
tax[a[x]]--;
if (a[x]-tax[a[x]]>)
tot+=--c[a[x]-tax[a[x]]]==;
a[x]=y;
if (a[x]-tax[a[x]]>)
tot-=c[a[x]-tax[a[x]]]++==;
tax[a[x]]++;
printf("%d\n",tot);
}
return ;
}
AGC017C
D
考虑处理出每一个节点的 SG 值。
对于节点 x ，显然他的所有子树都是独立的，我们只需要求出所有子树的 SG 值然后异或起来就好了。
假设 y 为 x 的一个儿子，则节点 y 对于 x 的贡献是什么呢？
显然不是 SG[y] ，因为 x 到 y 还有一条边。在 y 子树中操作的任何时候都可以直接删除这条边到达状态 0 ，相当于 y 子树的所有状态都连了一条到 0 的边。
所以 SG'[y] = SG[y] + 1 。
所以 SG[x] 就是所有的 SG'[y] 的异或值（其中 y 为 x 的儿子）。
#include <bits/stdc++.h>
#define y1 __zzd001
using namespace std;
typedef long long LL;
LL read(){
LL x=;
char ch=getchar();
while (!isdigit(ch))
ch=getchar();
while (isdigit(ch))
x=(x<<)+(x<<)+(ch^),ch=getchar();
return x;
}
const int N=;
int n,sg[N];
vector <int> e[N];
void solve(int x,int pre){
sg[x]=;
for (auto y : e[x])
if (y!=pre){
solve(y,x);
sg[x]^=sg[y]+;
}
}
int main(){
n=read();
for (int i=;i<n;i++){
int x=read(),y=read();
e[x].push_back(y);
e[y].push_back(x);
}
solve(,);
puts(sg[]?"Alice":"Bob");
return ;
}
AGC017D
E 转自 https://blog.csdn.net/zltjohn/article/details/79332801
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
int read(){
int x=;
char ch=getchar();
while (!isdigit(ch))
ch=getchar();
while (isdigit(ch))
x=(x<<)+(x<<)+(ch^),ch=getchar();
return x;
}
const int N=;
int n,m=;
int fa[N],in[N],out[N],cnt[N],f[N];
int _(int k){
if (k<)
return +k;
else
return k;
}
int getf(int x){
return fa[x]==x?x:fa[x]=getf(fa[x]);
}
int main(){
for (int i=;i<=m;i++)
fa[i]=i;
n=read();
read();
while (n--){
int a=read(),b=read(),c=read(),d=read();
int x=c?-c:a;
int y=d?d:-b;
x=_(x),y=_(y);
fa[getf(x)]=getf(y);
in[y]++,out[x]++;
}
for (int i=;i<=m;i++){
if (!in[i]&&!out[i])
continue;
cnt[getf(i)]++;
if (in[i]!=out[i])
f[getf(i)]=;
}
for (int i=;i<=;i++)
if (out[i]<in[i]||in[-i]<out[-i])
return puts("NO"),;
for (int i=;i<=m;i++)
if (cnt[i]&&!f[i])
return puts("NO"),;
puts("YES");
return ;
}
AGC017E