AGC 补题记录 AGC001 AGC002 AGC003 AGC004 AGC005 AGC006 AGC007 AGC008 AGC009 AGC010 AGC011 AGC012 AGC013 AGC014 AGC015 AGC016 AGC017 AGC018 AGC019 AGC020 AGC021
前面一篇太长了，翻着难受……
我要是能进队就把所有 AGC 和 ARC 全部补完 （
D
半天看不懂题意，问了 lxm 。就是说如果有一个长度为 (n) 的字符串前 (A_1) 段，前 (A_2) 段 (,cdots,) 前 (A_{m1}) 段位置上的字符能构成一个回文串，且前 (B_1) 段，前 (B_2) 段 (,cdots,) 前 (B_{m1}) 段位置上能构成一个回文串，那么这个字符串必须每个位置的字符都相等，并且 (A) 中元素和与 (B) 中元素和都是 (n) 。
摸了一下发现：
-
现有一段回文串 ([1 cdots n]) ，如果 ([1 cdots n-1],[2 cdots n]) 都是回文串，那么这个串一定所有字符都相等。
-
现有一段长度为奇数的串，如果这个串的 ([1 cdots n-1],[2 cdots n]) 都是回文串，那么这个串一定所有字符都相等。
结果摸了一会儿少摸出来一个结论，还是看了 lk 的博客 才知道，就是奇数个数不能 (>2) 。证明也很简单，(>2) 边数就不够了。可惜我没想到。
所以只需要把奇数提到最前面，如果有两个奇数就放一个放后面，然后令 (B_1=A_1+1,B_m=A_m-1) 就可以了。
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
#define il inline
const int N=1000005;
int n,m,a[N];
int main(){
scanf("%d%d",&m,&n);it i,tot=0;
for(i=1;i<=n;++i) scanf("%d",&a[i]),tot+=(a[i]&1);
if(tot>2) return puts("Impossible"),0;
std::sort(a+1,a+1+n,[&](ct p,ct q){return (p&1)>(q&1);});
if(n==1){
if(a[n]==1) return printf("%d
1
%d
",a[n],a[n]),0;
return printf("%d
",a[n]),puts("2"),printf("1 %d
",a[n]-1),0;
}
if(a[2]&1) std::swap(a[2],a[n]),a[1]>a[n]?std::swap(a[1],a[n]),0:0;
for(i=1;i<=n;++i) printf("%d ",a[i]);puts("");
printf("%d
",a[n]>1?n:n-1);
printf("%d ",a[1]+1);
for(i=2;i<n;++i) printf("%d ",a[i]);
if(a[n]>1) printf("%d",a[n]-1);
return 0;
}
E
我竟然能摸出来 AGC 的 E
题意是每次可以选择两个背包，串里面的肉和菜，问总方案。
菜和肉内部是一样的，没有标号，所以用可重排列：(frac{(a_1+a_2+ cdots a_n)!}{a_1!a_2!cdots a_n!})
那么现在要求的就是：
发现虽然 (n) 很大 ((n leq 2 imes 10^5)) ，但是 (a_i,a_j,b_i,a_j leq 2000) ，很小，所以应该从这入手。
考虑 (inom{a+b}{a}) 的意义：从 ((0,0)) 到 ((a,b)) 每次只能向上或者向右走的不同方案数。所以我们可以直接预处理坐标。
但现在还是 (O(n^2)) 的，考虑优化，就是把 (i,j) 放到同一边。很显然我们可以整体平移，把 ((0,0) ightarrow (a_i+a_j,b_i+b_j)) 平移一下，平移成 ((-a_i,-b_i) ightarrow (a_j,b_j)) ，和原来的意义是一样的，而且现在可以一起算。最后要减去自己和自己算的。
“这个题放 AGC 的 E 太简单了！” lxm：“AGC 难度就那样。”
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
#define il inline
using namespace std;
#define P 1000000007
const int N=200005,M=2003,MM=4006;
int n,a[N],b[N],f[MM+5][MM+5],ans,fac[N],ifac[N];
il int add(ct x){return x>=P?x-P:x;}
il void add(it &p,ct q){p+=q,p>=P?p-=P:0;}
il int ksm(it x,it L){it ans=1;while(L) L&1?ans=(0ll+ans)*x%P:0,x=(0ll+x)*x%P,L>>=1;return ans;}
il int C(ct n,ct m){return m<0||n<m?0:(0ll+fac[n])*ifac[m]%P*ifac[n-m]%P;}
int main(){
scanf("%d",&n);it i,j;
for(i=1;i<=n;++i) scanf("%d%d",&a[i],&b[i]),++f[-a[i]+M][-b[i]+M];
for(i=1;i<=MM;++i)
for(j=1;j<=MM;++j)
add(f[i][j],add(f[i-1][j]+f[i][j-1]));
for(i=fac[0]=1;i<=MM+MM;++i) fac[i]=(0ll+fac[i-1])*i%P;
for(i=MM+MM,ifac[i]=ksm(fac[i],P-2);i;--i) ifac[i-1]=(0ll+ifac[i])*i%P;
for(i=1;i<=n;++i) add(ans,f[a[i]+M][b[i]+M]),add(ans,P-C(a[i]+b[i]<<1,a[i]<<1));
printf("%d",(0ll+ans)*(P+1>>1)%P);
return 0;
}
F
我竟然能摸出来 AGC 的 F
给定一个排列，每次可以交换这样的 (P_i,P_j) ： (j-i geq K , |P_i-P_j|=1) ，问可以得到的字典序最小的排列。
发现题意可以转化成相邻数之差 (geq K) 就可以交换相邻的数，且让新的排列字典序最小。有一个粗暴的想法是直接连边跑个拓扑排序，然而手摸了一下发现边数可能会跟冒泡排序交换次数一样（
发现在 (i) 一定会向区间 ([i-K+1,i+K-1]) 连边，所以可以用线段树优化连边做，边数大概是 (O(n log n))的，估计跑不过去。
但是通过仔细思考发现完全不需要……因为把上面那个结论倒过来想，就是 ([i-K+1,i],[i,i+K-1]) 区间内一定两两有边，所以每次 (i) 只要找离它最近的连边就可以了……我真的太睿(ruo)智了
注意拓扑排序的时候要用 set，因为要字典序最小所以同一层要优先拿小的（因为这个卡了半个小时……
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
#define il inline
using namespace std;
const int N=1000005,inf=2139062143;
int n,K,a[N],p[N],s[N<<1],q[N],h[N],nxt[N],adj[N],rd[N],t;
il int Min(ct p,ct q){return p<q?p:q;}
il int Max(ct p,ct q){return p>q?p:q;}
il void add(ct u,it v){v<inf?v=p[v],nxt[++t]=h[u],h[u]=t,adj[t]=v,++rd[v]:0;}
il void topo(){
it top1=0,top2=0;
set<int> S;
for(it i=1;i<=n;++i) if(!rd[i]) S.insert(i);
while(!S.empty()){
ct top=*S.begin();q[++top2]=top;S.erase(top);
vector<int> g;
for(it i=h[top],j;i;i=nxt[i])
if(!--rd[j=adj[i]]) S.insert(j);
}
}
il void upd(ct rt,ct l,ct r,ct pos,ct x){
if(l==r) return s[rt]=x,void();
ct mid=l+r>>1,ls=rt<<1,rs=ls|1;
pos<=mid?upd(ls,l,mid,pos,x):upd(rs,mid+1,r,pos,x),s[rt]=Min(s[ls],s[rs]);
}
il int que(ct rt,ct l,ct r,ct u,ct v){
if(l>=u&&r<=v) return s[rt];
ct mid=l+r>>1,ls=rt<<1,rs=ls|1;
if(v<=mid) return que(ls,l,mid,u,v);
if(u>mid) return que(rs,mid+1,r,u,v);
return Min(que(ls,l,mid,u,mid),que(rs,mid+1,r,mid+1,v));
}
int main(){
scanf("%d%d",&n,&K);it i;
for(i=1;i<=n;++i) scanf("%d",&a[i]),p[a[i]]=i;
memset(s,127,sizeof(s));
for(i=n;i;--i) add(p[i],que(1,1,n,Max(p[i]-K+1,1),p[i])),add(p[i],que(1,1,n,p[i],Min(p[i]+K-1,n))),upd(1,1,n,p[i],i);
topo();
for(i=1;i<=n;++i) p[q[i]]=i;
for(i=1;i<=n;++i) printf("%d
",p[i]);
return 0;
}
AGC002
D
题意是从 (x) 到 (y) 经过 (k) 个点使得经过的边的最大编号最小。
大套路题，和 【NOI2018 归程】 是一个套路（归程都比这难……）
复习一下 kruscal 重构树的性质：
-
基于最小生成树
-
原树中的边权在新树中对应点权
-
叶子节点是生成树的节点，非叶子节点是生成树的边
-
每个非叶子节点到根的路径上的点在原图中的权值是单调的（因为是按照深度或者说距离建树的）
-
(lca(u,v)) 相当于 ((u,v)) 在最小生成树上的瓶颈（实际上这就是个堆）
这个题直接把边的编号当成边权，然后就是个重构树的板子。每次二分答案，倍增检验经过点个数即可。注意这个经过点是新树的叶子节点，dfs 统计 size 的时候不要弄错。
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
#define il inline
using namespace std;
typedef long long ll;
const int N=200005;
int n,m,Q,f[N],fa[N][20],w[N],sz[N];
vector<int> g[N];
il int fd(ct x){return f[x]^x?f[x]=fd(f[x]):x;}
il void dfs(ct x){
for(it i=1;i<=18;++i) fa[x][i]=fa[fa[x][i-1]][i-1];
if(g[x].empty()) return sz[x]=1,void();
for(const int &j : g[x])
if(j^fa[x][0]) dfs(j),sz[x]+=sz[j];
}
il int jump(it u,it v,ct x){
for(it i=18;~i;--i){
if(fa[u][i]&&w[fa[u][i]]<=x) u=fa[u][i];
if(fa[v][i]&&w[fa[v][i]]<=x) v=fa[v][i];
}
return u==v?sz[u]:sz[u]+sz[v];
}
int main(){
scanf("%d%d",&n,&m);it i,u,v,x,cnt=n;
for(i=1;i<=n+n;++i) f[i]=i;
for(i=1;i<=m;++i){
scanf("%d%d",&u,&v),u=fd(u),v=fd(v);
if(u^v) fa[u][0]=fa[v][0]=++cnt,g[cnt].push_back(u),g[cnt].push_back(v),w[cnt]=i,f[u]=f[v]=cnt;
}
dfs(cnt);
scanf("%d",&Q);
while(Q--){
scanf("%d%d%d",&u,&v,&x);
it l=1,r=m,mid;
while(l<=r) mid=l+r>>1,jump(u,v,mid)<x?l=mid+1:r=mid-1;
printf("%d
",l);
}
return 0;
}
E
以前做过的，补档。
题意是有 (n) 堆糖果，两人轮流，每次可以选择吃掉一个或者吃掉最大的一堆，问先手是否有必胜策略。
ly 讲的神仙博弈。看图：
把每堆排序画成小圈圈，然后每次可以拿最底下或者最左边一堆。如果某个点的状态不能扩展了就不能走，否则可以走：
然后就没了。
code
#include<stdio.h>
#include<algorithm>
#define it register int
#define ct const int
const int N=1000005;
int n,a[N],ans;
int main(){
scanf("%d",&n);it i,j;
for(i=1;i<=n;++i) scanf("%d",&a[i]);
std::sort(a+1,a+1+n,[&](ct p,ct q){return p>q;});
for(i=1;i<=n;++i)
if(i+1>a[i+1]){
for(j=i+1;a[j]==i;++j) ans^=1;
ans|=(a[i]-i&1),ans?puts("First"):puts("Second");
return 0;
}
return 0;
}
F
题意： (k) 种颜色的球，每种颜色有 (n) 个。所有球球排成一排，把每一种颜色的最左边出现的球涂成白色，求有多少种不同的颜色序列。
考虑 dp ，设 (f_{i,j}=) 用了 (i) 种颜色，有 (j) 种颜色除了白球还有球。简单的说就是前 (i) 个颜色都用了，都涂了最左边的白色，现在有 (j) 种颜色是除了白色还有球的。((jleq i))
考虑新放进来一个球：
-
放一种新的颜色：(f_{i,j}=f_{i-1,j}) 。这个不用说了，就是字面意思。
-
放一种用过白球的颜色： (f_{i,j}=f_{i,j-1} imes inom{n imes k - i - (j-1) imes (k-1)-1}{k-2} imes (n-j+1)) 。这个也很好理解：首先我们钦定这个新的位置放这个球，那么剩下空位的个数为总数 (-) 前面 (i) 个白球 (-) 前面 (j-1) 种颜色用完的的球 (-) 这一个球，然后这种颜色还有 (k-2) 个球没放，很显然要从这些位置里面选位置放。然后后面每种颜色都要排列，所以还要 ( imes (n-j+1)) 。然后就没了。
注意要特判 (K=1) ，答案就是 (1) ，还有边界是 (forall i , f_{i,0}=1) ，就是每个颜色只放白球，其他的不管，方案是 (1)。
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
#define il inline
#define P 1000000007
const int N=4000005;
int n,K,fac[N],ifac[N],f[2005][2005];
il int C(ct n,ct m){return m<0||n<m?0:(0ll+fac[n])*ifac[m]%P*ifac[n-m]%P;}
il int ksm(it x,it L){it ans=1;while(L) L&1?ans=(0ll+ans)*x%P:0,x=(0ll+x)*x%P,L>>=1;return ans;}
int main(){
scanf("%d%d",&n,&K);it i,j;
if(K==1) return putchar('1'),0;
for(i=fac[0]=1;i<N;++i) fac[i]=(0ll+fac[i-1])*i%P;
for(i=N-1,ifac[i]=ksm(fac[i],P-2);i;--i) ifac[i-1]=(0ll+ifac[i])*i%P;
for(i=0;i<=n;++i) f[i][0]=1;
ct tot=n*K;
for(i=1;i<=n;++i)
for(j=1;j<=i;++j)
f[i][j]=(f[i-1][j]+(0ll+f[i][j-1])*C(tot-i-(j-1)*(K-1)-1,K-2)%P*(n-j+1ll))%P;
printf("%d",f[n][n]);
return 0;
}
AGC003
D
以前做过的，补档。
题意是选出最多的数使得任意两个的积都不是完全立方数。
本身是完全立方数的直接扔了。
现在每个数就是这种形式 ： (ab,ab^2,a^2b^2)。
记录一下每个数所有质因子的次数，可以找到唯一的和它相补的数。
然后对于每个数用 map 统计一下到底是选他还是选他相补的数就好了。
code
#include<stdio.h>
#include<math.h>
#include<unordered_map>
#define it register int
#define ct const int
#define il inline
using namespace std;
const int N=1000005;
typedef long long ll;
int p[N],cnt,ans,n;
bool isp[N];
ll a[N],b[N];
unordered_map<ll,int> cn,in;
il void Pre(){
it i,j,x;
for(i=2;i<=3000;++i){
if(!isp[i]) p[++cnt]=i;
for(j=1;(x=p[j]*i)<=3000;++j){
isp[x]=1;
if(!(i%p[j])) break;
}
}
}
int main(){
scanf("%d",&n),Pre();it i,j;register ll x,y;
for(i=1;i<=n;++i){
scanf("%lld",&x),a[i]=b[i]=1;
for(j=1;x>1&&p[j]<=2155&&j<=cnt;++j){
y=(0ll+p[j])*p[j]*p[j];
while(!(x%y)) x/=y;
y/=p[j],(!(x%y))?a[i]*=y,b[i]*=p[j]:((!(x%p[j]))?a[i]*=p[j],b[i]*=y:0);
while(!(x%p[j])) x/=p[j];
}
if(x>1) y=(ll) (sqrt(x)+0.1),y*y==x?a[i]*=x,b[i]*=y:(x<=0x7fffffff?a[i]*=x,b[i]*=x*x:(++ans,a[i]=b[i]=0));
}
for(i=1;i<=n;++i) a[i]?++cn[a[i]]:0;
for(i=1;i<=n;++i) if(a[i]&&!in[a[i]]) in[a[i]]=in[b[i]]=1,ans+=(a[i]!=b[i]?(cn[a[i]]>cn[b[i]]?cn[a[i]]:cn[b[i]]):1);
printf("%d",ans);
return 0;
}
E （待更）
以前做过的，补档。
code
#include<stdio.h>
#include<algorithm>
#define it register int
#define ct const int
#define il inline
using namespace std;
const int N=1000005;
typedef long long ll;
int top,n,m;
ll q[N],tr[N],v[N];
il void work(it pos,ll x,ll val){
v[pos]+=val*(x/q[pos]),x%=q[pos];
pos=std::upper_bound(q+1,q+1+pos,x)-q;
if(pos==1) return tr[1]+=val,tr[x+1]-=val,void();
work(pos-1,x,val);
}
int main(){
scanf("%d%d",&n,&m);it i,j;register ll x;
q[++top]=n;
for(i=1;i<=m;++i){
scanf("%lld",&x);
while(top&&q[top]>x) --top;
q[++top]=x;
}
v[top]=1;
for(i=top;i>1;--i) work(i-1,q[i],v[i]);
for(i=1;i<=q[1];++i) tr[i]+=tr[i-1],printf("%lld
",tr[i]+v[1]);
n-=q[1];
while(n--) putchar('0'),putchar('
');
return 0;
}
F
太神了吧，还是 lxm 强。看了 CYJian 神仙的题解。
发现 (K leq 10^{18}) ，肯定要矩阵快速幂这种 (log) 级别的东西。
分类讨论一下，发现要考虑这几种情况：
-
上下拼接成一个大连通块
-
左右拼接成一个大连通块
-
上下左右拼接成一个大连通块 （答案是 (1)）
-
上下左右拼接都不是一个连通块 （答案是黑点的个数(^{K-1})）
考虑新图的连通块怎么表示：原图的黑点个数 - 左右相邻两个都是黑点的对数
所以答案就是这个玩意快速幂 (K-1) 次。
发现每次的贡献是黑点 (+) 相邻黑点对数 ( imes) 左右拼接边界上相邻黑点对数 (+) 左右拼接边界相邻的行点对数的平方
考虑推一个矩阵出来：
其中 (a) 表示相邻黑点对数， (b) 表示左右拼接边界相邻的黑点对数，(c) 表示黑格数。直接快速幂就可以了。
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
#define il inline
using namespace std;
#define P 1000000007
int n,m;
long long K;
char S[1005][1005];
struct ky{
int a[2][2];
ky operator * (const ky&b)const{
register ky c;
for(it i=0;i<2;++i)
for(it j=0;j<2;++j)
c.a[i][j]=((0ll+a[i][0])*b.a[0][j]+(0ll+a[i][1])*b.a[1][j])%P;
return c;
}
}o,ans;
il int ksm(it x,long long L){it ans=1;while(L) L&1?ans=(0ll+ans)*x%P:0,x=(0ll+x)*x%P,L>>=1;return ans;}
int main(){
scanf("%d%d%lld",&n,&m,&K);it i,j,tot=0;
for(i=1;i<=n;++i) scanf("%s",S[i]+1);
for(i=1;i<=n;++i) for(j=1;j<=m;++j) S[i][j]=(S[i][j]=='#'),tot+=S[i][j];
it lr=0,ud=0;
for(i=1;i<=n;++i) lr+=(S[i][1]&S[i][m]);
for(i=1;i<=m;++i) ud+=(S[1][i]&S[n][i]);
if(lr&&ud) return putchar('1'),0;
if(!lr&&!ud) return printf("%d",ksm(tot,K-1)),0;
it cnt=0;
for(i=1;i<=n;++i) for(j=1;j<=m;++j) cnt+=(S[i][j]&(lr?S[i][j+1]:S[i+1][j]));
o.a[0][0]=lr+ud,o.a[1][0]=cnt,o.a[1][1]=tot,ans.a[0][0]=ans.a[1][1]=1,--K;
while(K) K&1?ans=ans*o,0:0,o=o*o,K>>=1;
o.a[0][0]=o.a[0][1]=o.a[1][0]=o.a[1][1]=0,o.a[0][1]=1;o=o*ans;
printf("%d",(o.a[0][1]-o.a[0][0]+P)%P);
return 0;
}
AGC004
D
题意是任意加边使得每个点到 (1) 距离 (leq K)。
sb 题 ，给 (1) 一个自环，然后就只要每个点到 (1) 的步骤 (leq K) 。直接从下向上贪心即可。
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
#define il inline
using namespace std;
const int N=1000005;
int n,K,fa[N],ans;
vector<int> g[N];
il void ckMax(it &p,ct q){p=(p>q?p:q);}
il int dfs(ct x,ct dep){
it mxd=dep;
for(const int &i : g[x])
ckMax(mxd,dfs(i,dep+1));
if(mxd-dep==K-1) return ans+=(fa[x]!=1),dep-1;
return mxd;
}
int main(){
scanf("%d%d",&n,&K);it i;
for(i=1;i<=n;++i) scanf("%d",&fa[i]);
for(i=2;i<=n;++i) g[fa[i]].push_back(i);
ans=(fa[1]!=1),fa[1]=1,dfs(1,0),printf("%d",ans);
return 0;
}
E
题意是有一车机器人，但是只有一个出口，机器人可以同时移动，出了边界就死，到了出口就活，问多少能活。
其实就相当于一个出口上下左右移动罢了==
直接 dp ，把坐标系平移，以出口的位置 ((x,y)) 为中心，设 (f[l][r][u][d]) 表示最大答案，每一维表示历史最大左右上下偏移量。转移的话直接选某个方位移动一格就可以了。
但发现这样会卡空间，正确的优化方式是省掉一维，但是用 short 也可以轻松草过去。
虽然短但有一车细节，调吐了，最后还借鉴了别人代码。我菜死了。
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
#define il inline
using namespace std;
const int N=101;
int n,m,x,y;
short f[N][N][N][N],ans,sr[N][N],sc[N][N];
char S[N][N];
template <class I> il I Max(I p,I q){return p>q?p:q;}
template <class I> il I Min(I p,I q){return p<q?p:q;}
template <class I> il void ckMax(I&p,ct q){p=(p>q?p:q);}
template <class I> il void ckMin(I&p,ct q){p=(p<q?p:q);}
int main(){
scanf("%d%d",&n,&m);it i,j;
for(i=1;i<=n;++i) scanf("%s",S[i]+1);
for(i=1;i<=n;++i)
for(j=1;j<=m;++j)
sr[i][j]=sc[i][j]=(S[i][j]=='o'),S[i][j]=='E'?x=i,y=j:0,sr[i][j]+=sr[i][j-1],sc[i][j]+=sc[i-1][j];
for(i=x;i;--i)
for(j=y;j;--j)
for(it k=x;k<=n;++k)
for(it t=y;t<=m;++t){
ckMax(ans,f[i][j][k][t]);
if(i>1&&k+1<x+i)
ckMax(f[i-1][j][k][t],f[i][j][k][t]+sr[i-1][Min(t,m-y+j)]-sr[i-1][Max(j-1,t-y)]);
if(j>1&&t+1<y+j)
ckMax(f[i][j-1][k][t],f[i][j][k][t]+sc[Min(k,n-x+i)][j-1]-sc[Max(i-1,k-x)][j-1]);
if(k<n&&x+k<n+i)
ckMax(f[i][j][k+1][t],f[i][j][k][t]+sr[k+1][Min(t,m-y+j)]-sr[k+1][Max(j-1,t-y)]);
if(t<m&&y+t<m+j)
ckMax(f[i][j][k][t+1],f[i][j][k][t]+sc[Min(k,n-x+i)][t+1]-sc[Max(i-1,k-x)][t+1]);
}
cout<<ans;
return 0;
}
F
题意是每次选某条边且边上两点颜色相同，将其反色，问整个树反色的最小操作次数。
自己摸了一下就会了，但细节太多了（
首先观察到两个性质：
-
发现 (m) 要么是 (n-1) 要么是 (n) ，这启发我们要么是一棵树要么是一个基环树。
-
每个点要被操作奇数次，每次要操作偶数个点。这启示我们如果 (n) 为奇数肯定无解。
先考虑树怎么做：
首先不是所有树都有解的！比如我摸的第一棵树就无解。
我们发现每次操作两点是 (dep) 相邻的，就是说奇数层和偶数层的操作次数肯定相同。换句话说，如果把树进行黑白染色，那么黑点和白点的数目一定相同。只有这样才有解。
怎么让解最小？考虑把问题抽象成这样：每次把黑点往子树里面移，如果子树里面的空位比黑点少就要把多余的弄出去，如果多就可以把多余的移进来。所以每条边最小就是 (|a_i|) 。然后每个点独立可以直接计算。
再考虑基环树：
如果环上有奇数个点，缩一下就变成了树，可以 dp 一下。
如果环上有偶数个点，就相当于数轴上有一堆点，找一个点使得距离最小。其他部分再 dp 即可。
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
#define il inline
using namespace std;
const int N=1000005;
int n,m,u,v,t,h[N],nxt[N],adj[N],fa[N],f[N],dep[N],sum,len,s[N],ans;
vector<int> g;
il void add(){nxt[++t]=h[u],h[u]=t,adj[t]=v,nxt[++t]=h[v],h[v]=t,adj[t]=u;}
il void DFS(ct x){
dep[x]=dep[fa[x]]+1,f[x]=(dep[x]&1?1:-1),sum+=f[x];
for(it i=h[x],j;i;i=nxt[i])
if((j=adj[i])^fa[x]){
if(dep[j]) len=std::abs(dep[j]-dep[x])+1,u=x,v=j;
if(!dep[j]) fa[j]=x,DFS(j);
}
}
il void dfs(ct x){
for(it i=h[x],j;i;i=nxt[i])
if((j=adj[i])^fa[x]){
if((x==u&&j==v)||(x==v&&j==u)) continue;
dfs(j),s[x]+=s[j],f[x]+=f[j];
}
s[x]?g.push_back(s[x]*f[x]),0:ans+=std::abs(f[x]);
}
int main(){
scanf("%d%d",&n,&m);it i;
for(i=1;i<=m;++i) scanf("%d%d",&u,&v),add();
if(n&1) return puts("-1"),0;
u=v=0,DFS(1);
if(m==n-1){if(sum) return puts("-1"),0;}
if(m==n){
if(len&1){
if(sum%2) return puts("-1"),0;
ans+=std::abs(sum>>1),f[u]-=(sum>>1),f[v]-=(sum>>1);
}
if(!(len&1)){
if(sum) return puts("-1"),0;
s[u]=1,s[v]=-1;
}
}
dfs(1),g.push_back(0),std::sort(g.begin(),g.end()),m=g[g.size()-1>>1];
for(const int &p : g) ans+=std::abs(m-p);
printf("%d",ans);
return 0;
}
AGC005
D
题意是计数所有不含 (|P_i-i| = K) 的排列数。
一看就知道是容斥。设 (f_i=) 至少有 (i) 个位置满足 (|P_i-i|=K) ，那么答案就是 (sum_{i=0}^n (-1)^i f_i (n-i)!) ，((n-i)!) 表示剩下的位置随意排列。
直接 dp ，设 (f_{i,j,0/1}) 表示到 (i) 匹配了 (j) 个位置，(i) 这个位置选或不选。听说可以用什么二分图选链来理解，本质其实一样。
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
#define il inline
using namespace std;
#define P 924844033
const int N=4005;
int n,K,fac[N],f[N][N][2],g[N],cnt,ans;
il int add(ct x){return x>=P?x-P:x;}
il int Min(ct p,ct q){return p<q?p:q;}
int main(){
scanf("%d%d",&n,&K);it i,j;
for(i=1;i<=K;++i){
for(j=i;j<=n;j+=K) g[++cnt]=(j==i);
for(j=i;j<=n;j+=K) g[++cnt]=(j==i);
}
f[0][0][0]=1;
for(i=fac[0]=1;i<=n;++i) fac[i]=(0ll+fac[i-1])*i%P;
for(i=0;i<n+n;++i)
for(j=0;j<=Min(i,n);++j)
f[i+1][j][0]=add(f[i][j][0]+f[i][j][1]),!g[i+1]?f[i+1][j+1][1]=f[i][j][0]:0;
for(i=0;i<=n;++i)
ans=(ans+(0ll+fac[n-i])*(f[n<<1][i][0]+f[n<<1][i][1])%P*(i&1?P-1:1))%P;
printf("%d",ans);
return 0;
}
E （鸽）
F （鸽）
NTT 的质数到底有哪些？难道真的只有三个质数配吗？ 998244353 的孪生兄弟是谁？ 924844033 究竟有怎样不可告人的秘密？sxbk 出题人弄个原根是 5 的质数意义何在？
算了，先鸽一会儿。
AGC006
D
题意是给一个金字塔，某个数的权值是它左下正下右下三个数的中位数，问塔尖是啥。
一开始以为中位数是平均值，随手摸了权值发现不对，后来发现是中位数。中位数也很好办，直接二分，小于 (mid) 设为 (0) ，大于或等于设为 (1) ，然后看哪一组能成功：很显然只要不是贴边的两个连续 (0) 或 (1) 都是可以笑到最后的，而最靠近中间的显然更容易胜利，直接判断就可以了。
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
#define il inline
using namespace std;
const int N=1000005;
int n,m,a[N],b[N];
il bool ck(ct mid){
for(it i=1;i<=m;++i) b[i]=(a[i]>=mid);
for(it i=n,j=n;i;--i,++j){
if(b[j]==b[j+1]) return b[j];
if(b[i]==b[i-1]) return b[i];
}
return b[1];
}
int main(){
scanf("%d",&n),m=(n<<1)-1;it l=1e9,r=-1e9,mid;
for(it i=1;i<=m;++i) scanf("%d",&a[i]),a[i]<l?l=a[i]:0,a[i]>r?r=a[i]:0;
while(l<=r) mid=l+r>>1,ck(mid)?l=mid+1:r=mid-1;
printf("%d",r);
return 0;
}
E
摸一下就会啦（
题意是给一个 (3 imes n) 的矩阵，每次可以翻转一个 (3 imes 3) 的矩阵，问初始矩阵是否能操作成给定矩阵。初始矩阵 (a(i,j)=i+3(j-1))
发现这几个性质：
-
同一列的元素是绑定的，不可更改的，现在在同一列最后肯定还在同一列
-
中间一行的元素没法换到其他行，第一行只能和第三行互换，反之亦然
-
对奇偶性不同的列进行黑白染色，每次操作可以交换两个同色列或者翻转两个同色列，而交换同色列会使得异色列正反状态奇偶性发生改变，而如果是偶数次就能成功换，否则就不成功。
然后就没了。
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
#define il inline
using namespace std;
const int N=1000005;
int n,a[4][N],ans[N],b[N];
pair<int,int> pos[N];
int main(){
scanf("%d",&n);it i,j,x,y;
for(i=1;i<=3;++i)
for(j=1;j<=n;++j){
scanf("%d",&a[i][j]),x=(a[i][j]-1)%3+1,y=(a[i][j]+2)/3;
if((j&1)!=(y&1)) return puts("No"),0;
if((i==2)!=(x==2)) return puts("No"),0;
}
for(i=1;i<=n;++i){
x=(a[1][i]-1)%3+1,y=(a[1][i]+2)/3;
if((y!=(a[2][i]+2)/3)||(y!=(a[3][i]+2)/3)) return puts("No"),0;
if(x!=2&&(x+(a[3][i]-1)%3+1)!=4) return puts("No"),0;
if(x==3) ans[i&1]^=1;
b[i]=y;
}
for(i=1;i<=n;++i) while(b[i]^i) ans[(i&1)^1]^=1,std::swap(b[i],b[b[i]]);
if(ans[0]||ans[1]) return puts("No"),0;
puts("Yes");
return 0;
}
F
题意是给一些黑格，如果 ((x,y),(y,z)) 都是黑的，那么你可以把 ((x,z)) 涂黑，求最多黑格个数。
转换一下就是给一些连好的边，如果 ((x,y),(y,z)) 都有边那么 ((x,z)) 有边，求最多多少条边。
考虑把边画出来：(x ightarrow y ightarrow z ightarrow x) ，那么把这三个分别染成三种颜色，最后答案即为三种颜色的点的数量两两之间乘积的和。
但是可能会有矛盾，就是有完全图，发现没法染色，这时候直接加上连通块点数的平方即可。
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
#define il inline
using namespace std;
const int N=1000005;
int n,m,u,v,h[N],nxt[N],adj[N],w[N],t,col[N],cnt[5],tot,tote;
bool vs[N],flag;
long long ans;
il void add(){nxt[++t]=h[u],h[u]=t,adj[t]=v,w[t]=1,nxt[++t]=h[v],h[v]=t,adj[t]=u,w[t]=2;}
il void dfs(ct x){
++cnt[col[x]],vs[x]=1,++tot;
for(it i=h[x],j,c;i;i=nxt[i])
tote+=(w[i]&1),c=(col[x]+w[i])%3,!vs[j=adj[i]]?col[j]=c,dfs(j),0:flag|=(col[j]!=c);
}
int main(){
scanf("%d%d",&n,&m);it i;
for(i=1;i<=m;++i) scanf("%d%d",&u,&v),add();
for(i=1;i<=n;++i)
if(!vs[i]){
cnt[0]=cnt[1]=cnt[2]=flag=tot=tote=0,dfs(i);
if(flag) ans+=(0ll+tot)*tot;
else if(cnt[0]&&cnt[1]&&cnt[2]) ans+=(0ll+cnt[0])*cnt[1]+(0ll+cnt[1])*cnt[2]+(0ll+cnt[0])*cnt[2];
else ans+=tote;
}
printf("%lld",ans);
return 0;
}
AGC007
D
题意是坐标轴上一堆点，在时刻 (i) 处第一次经过某个点，那么在 (i+T) 时刻这个点会产生收益，但你要到这个点才能拿到收益。你最后还要从出口出去，问你最多的收益。
过程应该是这样的：走路 ( ightarrow) 回头 ( ightarrow) 走路 (cdots)
那么设 dp ： (f_{i}=) 到了 (i) 且前面所有的点的收益都被拿到了，现在在第 (i) 个点上，且后面的点没遍历的方案。
后面的 (max) 可以分类讨论一下，根据单调性可以拿个指针移动。
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
#define il inline
using namespace std;
typedef long long ll;
const int N=1000005;
int n,e,T,a[N];
ll f[N],mn=1e18;
template <class I> il I Min(I p,I q){return p<q?p:q;}
template <class I> il void ckMin(I&p,I q){p=(p<q?p:q);}
int main(){
scanf("%d%d%d",&n,&e,&T);it i,j;
for(i=1;i<=n;++i) scanf("%d",&a[i]);
for(i=1,j=0;i<=n;++i){
while(j<i&&T<=2*(a[i]-a[j+1])) ckMin(mn,f[j]-2*a[j+1]),++j;
f[i]=Min(f[j]+T,mn+2*a[i]);
}
printf("%lld",f[n]+e);
return 0;
}
E
题意是从 (1) 号点出发，每天可以从当前点走到另一个叶子，最后回到 (1) 号点，要求到过所有叶子并且每条边经过恰好两次。求最高的从叶子到叶子的路径长度。
其实不是很难，可惜没想到。
考虑二分答案 (ans) ，然后暴力 dp : 设 $f_{i,x} 表示 (i) 子树内第一个走到的叶子节点到 (i) 的距离不小于 (x)， 且每天的路径长度不超过 (ans) 时, 最后一个走到的叶子节点的距离 (i) 的最小值。
那么 (f[i][x]=min(f[r][x−f[l][x−w_l]−(w_l+w_r)],f[l][x−f[r][x−w_r]−(w_l+w_r)])) 。
仔细观察发现每个叶子要么第一次在他，要么最后一次在他。类似启发式合并，可以用双指针，复杂度 (O(nlog n))。
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
#define il inline
using namespace std;
typedef long long ll;
const int N=1000005;
int n,tr[N][2],c[N],w[N][2];
ll l,r,mid,ans;
vector<pair<ll,ll> > f[N];
il void dfs(ct x){
f[x].clear();
if(!tr[x][0]) return f[x].push_back({0,0});
dfs(tr[x][0]),dfs(tr[x][1]);
vector<pair<ll,ll> > vec;
for(it t=0,i,j;t<2;++t){
ct p=tr[x][t],q=tr[x][t^1],W=w[x][0]+w[x][1];
for(i=j=0;i<f[p].size();++i){
while(j+1<f[q].size()&&f[q][j+1].first+f[p][i].second<=mid-W) ++j;
if(j<f[q].size()&&f[q][j].first+f[p][i].second<=mid-W) vec.push_back({f[p][i].first+w[x][t],f[q][j].second+w[x][t^1]});
}
}
std::sort(vec.begin(),vec.end());
if(vec.empty()) return;
ll lst=vec[0].second;f[x].push_back(vec[0]);
for(it i=1;i<vec.size();++i)
if(vec[i].first>vec[i-1].first&&vec[i].second<lst) f[x].push_back(vec[i]),lst=vec[i].second;
}
int main(){
scanf("%d",&n);
for(it i=2,u,v;i<=n;++i) scanf("%d%d",&u,&v),tr[u][c[u]]=i,w[u][c[u]]=v,++c[u];
l=0,r=1e12,ans=-1;
while(l<=r) mid=l+r>>1,dfs(1),f[1].size()?ans=mid,r=mid-1:l=mid+1;
printf("%lld",ans);
return 0;
}
F
题意是不断复制原串，但是每个位置有可能出错，就是 (S_{i,j}=S_{i-1,j}) 或者 (S_{i,j}=S_{i,j-1}) ，问最少哪个 (i) 可以使得 (S_i = T) 。
先把相等判掉。考虑某个改变的位置，它必须是由它前面这个位置变来的，所以改变只能一段一段的，否则就无解。
所以现在就变成了某个字符扩展某一段字符需要的最小时间。轻松匹配一下就好了，每次往前找可以匹配的一段。如果是从前面转移来的就压到队列里面，表示这里要多一次才能扩展。不明白这题怎么能放到 F
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
#define il inline
using namespace std;
typedef long long ll;
const int N=1000005;
int n,ans;
char S[N],T[N];
queue<int> q;
int main(){
scanf("%d%s%s",&n,S+1,T+1);it flag=1;
for(it i=1;i<=n;++i) flag&=(S[i]==T[i]);
if(flag) return putchar('0'),0;
for(it i=n,j=n;i;--i){
while(i>1&&T[i-1]==T[i]) --i;
while(j&&(j>i||S[j]!=T[i])) --j;
if(!j) return puts("-1"),0;
while(!q.empty()&&q.front()-q.size()>=i) q.pop();
if(i!=j) q.push(j);
if(q.size()+1>ans) ans=q.size()+1;
}
printf("%d",ans);
return 0;
}
AGC008
D
题意是构造一个序列使得 (1,2,3,cdots,n) 每个数都出现了 (n) 次，且第 (i) 个数第 (i) 次出现在 (x_i) 。
瞎几把做，(n) 这么小，硬草就行。直接往前后找可行位置。
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
#define il inline
using namespace std;
const int N=1000005;
int n,m,a[N],pos[N],lft[N];
set<int> S;
int main(){
scanf("%d",&n);it i,x;
for(i=1;i<=n;++i) scanf("%d",&x),a[x]=i,pos[i]=x;
m=n*n;
for(i=1;i<=n;++i) lft[i]=n;
for(i=1;i<=m;++i) if(!a[i]) S.insert(i);
for(i=1;i<=m;++i)
if(a[i]){
lft[a[i]]-=a[i];
for(x=a[i]-1;(!S.empty())&&x;--x) a[*S.begin()]=a[i],S.erase(S.begin());
if(x&&S.empty()) return puts("No"),0;
}
for(i=1;i<=n;++i)
if(lft[i]){
if(!S.empty()){
auto p=S.lower_bound(pos[i]);
vector<int> g;
while(lft[i]&&(p!=S.end())) a[*p]=i,g.push_back(*p),--lft[i],++p;
if(lft[i]) return puts("No"),0;
for(const int &x : g) S.erase(x);
}
}
puts("Yes");
for(i=1;i<=m;++i) printf("%d ",a[i]);
return 0;
}
E
题意是计数 (forall i, p_i=a_i) 或 (p_{p_i}=a_i) 的排列个数。
神仙题。看了 litble的博客 才明白。
就是考虑先连 (p) 的边，再连 (a) 的边，最后只有四种情况：
- (forall i ,p_i=a_i)
- (forall i, p_{p_i}=a_i) ，且环长为奇数
- (forall i, p_{p_i}=a_i) ，且环长为偶数，此时被分成两个环
- 既有 (p_i=a_i) 又有 (p_{p_i}=a_i) ，是棵基环树
对于基环树把环上的链想办法扔到环里。记链长 (l1) ，扔进去的边有 (l2) 条，那么：
-
(l1>l2) 方案为 (0)
-
(l1=l2) 方案为 (1)
-
(l1<l2) 方案为 (2)
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
#define il inline
using namespace std;
typedef long long ll;
const int N=1000005;
#define P 1000000007
int n,a[N],f[N],pre[N],deg[N],cnt[N];
bool vs[N];
int main(){
scanf("%d",&n);it i,x,ans=1;
for(i=1;i<=n;++i) scanf("%d",&a[i]),++deg[a[i]];
for(i=1;i<=n;++i){
if(deg[i]>2) return puts("0"),0;
if(deg[i]<2||vs[i]) continue;
for(x=i;(!vs[x])||(x!=i);x=a[x]){
if(vs[x]) return puts("0"),0;
vs[x]=1,pre[a[x]]=x;
}
}
for(i=1;i<=n;++i)
if(!deg[i]){
it l1=0,l2=0;
for(x=i;(!vs[x]);x=a[x]) vs[x]=1,++l1;
do x=pre[x],++l2; while(deg[x]^2);
if(l1<l2) ans<<=1,ans>=P?ans-=P:0;
if(l1>l2) return puts("0"),0;
}
for(i=1;i<=n;++i)
if(!vs[i]){
it l=0;x=i;
do x=a[x],vs[x]=1,++l; while(x^i);
++cnt[l];
}
for(i=1;i<=n;++i){
x=1+(i!=1&&(i&1)),f[0]=1,f[1]=x;
for(it j=2;j<=cnt[i];++j)
f[j]=((j-1ll)*f[j-2]%P*i+f[j-1]*x)%P;
ans=(0ll+ans)*f[cnt[i]]%P;
}
printf("%d",ans);
return 0;
}
F （鸽）
AGC009
D
题意是找到一种重构树的方式使得最大深度最小，输出深度。
发现和点分树深度本质一样，答案不超过 (log) ，所以可以把答案用一个数压到一起，每次贪心即可。
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
#define il inline
using namespace std;
typedef long long ll;
const int N=1000005;
int n,h[N],nxt[N],adj[N],u,v,fa[N],t;
il void add(){nxt[++t]=h[u],h[u]=t,adj[t]=v,nxt[++t]=h[v],h[v]=t,adj[t]=u;}
il int dfs(ct x){
it s1=0,s2=0,p=0;
for(it i=h[x],j,w;i;i=nxt[i])
if((j=adj[i])^fa[x])
fa[j]=x,w=dfs(j),s2|=(s1&w),s1|=w;
while(((1<<p)<s2)||(s1&(1<<p))) ++p;
return (s1>>p<<p)|(1<<p);
}
int main(){
scanf("%d",&n);it i;
for(i=1;i<n;++i) scanf("%d%d",&u,&v),add();
printf("%d",__lg(dfs(1)));
return 0;
}
E
以前做过的，补档。
题意是有 (n) 个 (0) 和 (m) 个 (1)，每次可以选 (k) 个数替换成他们的平均数，问最后剩下一个数有多少种不同的可能。
根据分析可以转化成这样的形式：有多少数 (w) 可以写成 (m) 个 ((frac{1}{k})^y) ，且 (1-x) 可以写成 (n) 个 ((frac{1}{k})^x) 的形式。
设 dp ： (f_{i,j,0/1}) 表示小数点后 (i) 位，每一位的和是 (j) ，第 (i) 位末尾是否是 (0) 的方案数。转移的时候枚举数位做个前缀和即可。
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
#define il inline
using namespace std;
typedef long long ll;
#define rll register ll
#define cll const ll
#define P 1000000007
const int N=6005;
int n,m,k,f[N][N>>1][2],s[N],ans;
il void mo(it&p,ct q){p+=q,p>=P?p-=P:0;}
il int mo(ct x){return x>=P?x-P:x;}
int main(){
scanf("%d%d%d",&n,&m,&k),--k;ct nm=n%k,mm=m%k,lim=(n+m-1)/k;it i,j,x;
for(i=f[0][0][0]=1;i<=lim;++i){
for(j=0;j<=n;++j) f[i][j][0]=s[j]=mo(f[i-1][j][0]+f[i-1][j][1]);
for(j=1;j<=n;++j) mo(s[j],s[j-1]),f[i][j][1]=mo(s[j-1]+P-(j>k?s[j-k-1]:0));
for(j=1,x=i*k+1;j<=n;++j) if(j%k==nm&&(x-j)%k==mm&&x-j<=m) mo(ans,f[i][j][1]);
}
printf("%d
",ans);
return 0;
}
F
这场没有 F ，为了版面好看，写一个F上来。
AGC010
D
以前做过的，补档。
我对这题极其有印象是因为看了某位神仙的博客就把他的代码 css 复制过来自己用了
就是分奇偶性讨论。考虑每一层的局面。具体可以看上文博客。
code
#include<stdio.h>
#define it register int
#define ct const int
#define il inline
const int N=1000005;
int n,a[N],d;
il void gcd(ct a,ct b){return !b?d=a,void():gcd(b,a%b);}
il bool solve(){
it i,c0=0,c1=0;d=0;
for(i=1;i<=n;++i) c1+=(a[i]&1),c0+=((a[i]&1)^1);
if(c0&1) return 1;
if(c1>1||a[1]==1) return 0;
for(i=1;i<=n;++i){
if(a[i]==1) return 0;
a[i]-=(a[i]&1),gcd(a[i],d);
}
for(i=1;i<=n;++i) a[i]/=d;
return solve()^1;
}
int main(){
scanf("%d",&n);it i;
for(i=1;i<=n;++i) scanf("%d",&a[i]);
solve()?puts("First"):puts("Second");
return 0;
}
E
题意是先手把序列任意排列，后手通过交换相邻的质数使得字典序最大，但先手想让字典序最小。求最终序列。
好神啊……
发现不互质的数的相对位置是不会发生改变的，而互质的数的顺序是唯一的。
所以不互质的数连双向边，互质的连单向边。
现在就变成了一个有单向边和双向边的图，给边定向，让字典序最小。拓扑排序，队列改成优先队列即可。
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
#define il inline
using namespace std;
typedef long long ll;
const int N=1000005;
int n,a[N],h[N],nxt[N],adj[N],t,rd[N];
bool vs[N];
vector<int> g[N];
priority_queue<int> q;
il void add(ct u,ct v){nxt[++t]=h[u],h[u]=t,adj[t]=v,++rd[v];}
il void dfs(ct x){
vs[x]=1;
for(const int&j : g[x])
!vs[j]?add(x,j),dfs(j),0:0;
}
il void topo(){
for(it i=1;i<=n;++i) if(!rd[i]) q.push(i);
while(!q.empty()){
ct top=q.top();q.pop();
printf("%d ",a[top]);
for(it i=h[top],j;i;i=nxt[i])
if(!--rd[j=adj[i]]) q.push(j);
}
}
int main(){
scanf("%d",&n);it i;
for(i=1;i<=n;++i) scanf("%d",&a[i]);
std::sort(a+1,a+1+n);
for(i=1;i<=n;++i)
for(it j=i+1;j<=n;++j)
if(__gcd(a[i],a[j])!=1) g[i].push_back(j),g[j].push_back(i);
for(i=1;i<=n;++i) std::sort(g[i].begin(),g[i].end());
for(i=1;i<=n;++i) if(!vs[i]) dfs(i);
topo();
return 0;
}
F
题意是一棵树上每个节点都有 (A_i) 个石子，现在先手选一个节点放棋子，然后从先手开始轮流操作，每次从当前棋子占据的点上移除一个石子并将棋子移动到相邻节点，如果某人执行操作时棋子占据的点上没有石子他就输了，问从哪些点开始放石子先手必胜。
感觉比 E 简单一点？考虑每次如果走到一个比它大的，那后手可以反复横跳直到输为止，那么只能走比它小的（这时候只有先手会反复横跳），而后手是不会在其他位置又回到原始点的，因为会无形减小它，不优（给先手机会）。然后就是基础博弈论了，随便做一下即可。
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
#define il inline
using namespace std;
typedef long long ll;
const int N=1000005;
int n,a[N];
bool vs[N],f[N];
vector<int> g[N];
il void dfs(ct x){
if(vs[x]) return ;
vs[x]=1,f[x]=0;
for(const int&j : g[x])
a[x]>a[j]?dfs(j),f[x]|=(!f[j]):0;
}
int main(){
scanf("%d",&n);it i,u,v;
for(i=1;i<=n;++i) scanf("%d",&a[i]);
for(i=1;i<n;++i) scanf("%d%d",&u,&v),g[u].push_back(v),g[v].push_back(u);
for(i=1;i<=n;++i) if(!vs[i]) dfs(i);
for(i=1;i<=n;++i) if(f[i]) printf("%d ",i);
return 0;
}
AGC011
D
题意：有 (n) 个机器排成一排，有两种状态
A：球反方向滚动
B：球原方向滚动
球通过机器机器就会改变状态。滚进去一个球，求 (K) 次操作后的状态。
考虑直接模拟这个过程，维护一下球的状态，如果球向右，机器是 B ，那么只有机器状态会改变，否则球的状态会改变，反之亦然。
虽然暴力可以过，但我们可以发现最多 (2n) 次后序列会循环变化，所以我们把 (k) 变成 (min(k,2n+(k mod 2))) 即可。
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
#define il inline
using namespace std;
const int N=1000005;
int n,K;
char S[N];
int main(){
scanf("%d%d%s",&n,&K,S+1);
if(K>(n<<1)) K-=(n<<1),K&=1,K+=(n<<1);
char now='A';it i=1;
while(K--){
if(S[i]==now) S[i]='A'+'B'-S[i];
else now='A'+'B'-now,++i,i>n?i=1:0;
}
for(it j=i;j<=n;++j) putchar(S[j]==now?'A':'B');
for(it j=1;j<i;++j) putchar(S[j]==now?'A':'B');
return 0;
}
E
题意是给一个 (500000) 位以内的数，问他能被多少个 “上升数” 分解。上升数指每一位上的数字都不大于他右边的数字。
有一个神奇的想法，就是比如 (128756) 可以分成 (127999 + 699 + 58) ，就是找到一个不合法的位置，把前面 (-1) 后面改成 (9) 。这个可以用树状数组维护。代码重构了几次，最后迫不得已参考了这位神仙的博客。
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
#define il inline
using namespace std;
typedef long long ll;
const int N=1000005;
int n,a[N],b[N],pre[N],tr[N],ans;
char S[N];
il int Max(ct p,ct q){return p>q?p:q;}
il void ckMax(it &p,ct q){p=(p>q?p:q);}
il void upd(it x,ct w){while(x<=n) tr[x]+=w,x+=(x&-x);}
il int que(it x){it ans=0;if (x<1) return 0;while(x) ans+=tr[x],x-=(x&-x);return ans;}
il int ms(ct x){
it l=x,r=n,pre=que(x-1),mid;
while(l<r) mid=l+r>>1,que(mid)>pre?r=mid:l=mid+1;
return l;
}
il void work(){
it i,j;
for(i=n,++a[n];a[i]>9;++a[i-1],a[i]=0,--i);
for(j=Max(1,i-1);j<=n;++j){
if(b[j]>b[j+1]) upd(j,-1);
if(a[j]>a[j+1]) upd(j,1);
b[j]=a[j];
}
for(j=i;j<=n;++j) if(a[j]==a[j-1]) pre[j]=pre[j-1];else pre[j]=j;
}
int main(){
scanf("%s",S+1),n=strlen(S+1);it i,lst;
for(i=1;i<=n;++i) a[i]=b[i]=S[i]-'0';
for(i=1;i<=n;++i) pre[i]=(a[i]==a[i-1]?pre[i-1]:i);
for(i=1;i<=n;++i) if(a[i]>a[i+1]) upd(i,1);
for(i=1;i<=n;){
lst=i,i=ms(i),++ans;
if(i==n) break;
ckMax(lst,pre[i]),a[lst]=-1,i=lst+1,work();
}
printf("%d",ans);
return 0;
}
F
AGC012
D
题意是给你两种操作，求操作后不同的颜色序列有多少个。
操作 (1) ： 选两个相同颜色的小球，他们的重量不超过 (X) ，交换他们的位置。
操作 (2) ： 选两个不同颜色的小球，他们的重量不超过 (Y) ，交换他们的位置。
考虑把可以交换的球连一条边，那么同一联通块内的小球可以任意排列，答案就是可重排列计数：(frac{(sz_1+sz_2 cdots sz_n)!}{sz_1!sz_2! cdots sz_n!}) ，这样做是 (O(n^2)) 的。
考虑怎么降低边数，我们观察一下边可能长这样：
发现一堆边其实是没有用的。仔细观察发现同一种颜色可以合并的一定是一段前缀，不同颜色肯定都跟最小值连边，所以只需要记录和每种颜色 颜色不一样的最小颜色，那么也就只需要记录全局重量最小值和次小值。
发现如果一个连通块全是一种颜色的是没有意义的，因为对颜色序列是没影响的，所以只有跟最小值连边的连通块才是有意义的，直接按公式套即可。
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
#define il inline
using namespace std;
typedef long long ll;
const int N=1000005,inf=2e9;
#define P 1000000007
int n,x,y,fac[N],ifac[N],col[N],fa[N],sz[N],cn[N];
vector<pair<int,int> > g[N];
il int fd(ct x){return fa[x]^x?fa[x]=fd(fa[x]):x;}
il void mer(it u,it v){u=fd(u),v=fd(v),u^v?fa[u]=v:0;}
il int ksm(it x,it L){it ans=1;while(L) L&1?ans=(0ll+ans)*x%P:0,x=(0ll+x)*x%P,L>>=1;return ans;}
int main(){
scanf("%d%d%d",&n,&x,&y);it i,u,v;
if(n==1) return putchar('1'),0;
pair<int,int> mn(inf,0),mn2(inf,0);
for(i=fac[0]=1;i<=n;++i) fac[i]=(0ll+fac[i-1])*i%P;
for(i=n,ifac[i]=ksm(fac[i],P-2);i;--i) ifac[i-1]=(0ll+ifac[i])*i%P;
for(i=1;i<=n;++i) scanf("%d%d",&u,&v),g[u].push_back(make_pair(v,i)),col[i]=u,fa[i]=i;
for(i=1;i<=n;++i){
std::sort(g[i].begin(),g[i].end());
if(!g[i].empty()){
if(g[i][0]<mn||(g[i][0].first==mn.first)) mn2=mn,mn=g[i][0];
else if(g[i][0]<mn2) mn2=g[i][0];
}
}
for(i=1;i<=n;++i){
if(!g[i].empty()){
for(u=1;u<g[i].size();++u){
if(g[i][u].first+g[i][0].first>x) break;
mer(g[i][u].second,g[i][0].second);
}
pair<int,int> now;
if(col[mn.second]!=i) now=mn;
else now=mn2;
for(u=0;u<g[i].size();++u){
if(g[i][u].first+now.first>y) break;
mer(g[i][u].second,now.second);
}
}
}
vector<int> o;it cnt=0;
v=fd(mn.second);
for(i=1;i<=n;++i){
u=fd(i);
if(u==v){
if(!cn[col[i]]) o.push_back(col[i]);
++cn[col[i]],++cnt;
}
}
it ans=fac[cnt];
for(const int &p : o) ans=(0ll+ans)*ifac[cn[p]]%P;
printf("%d",ans);
return 0;
}
E
F
题意：给定一个长度为 (2n-1) 的序列 (a) ，将 (a) 任意排列，求有多少个序列 (b) 满足 (b_i) 是 (a_1 sim a_{2i-1}) 的中位数。
考虑倒着想，(b_n) 一定是所有数的中位数，那么 (b_{n-1}) 是序列删去两个数之后的中位数，所以 (b_{n-1}) 要么和 (b_n) 相等，要么是他左边的数，要么是他右边的数，就是距离不会超过 (1) 。
所以有这样的结论：
-
(forall i<j)，不可能存在 (b_j<b_i<b_{j+1}) 或 (b_{j+1}< b_i < b_{j+1})
-
(a_i < b_i < a_{2n-i})
所以 (b_i) 的合法区间是 ([a_i,min(b_j)]) 和 ([max(b_j),a_{2n-i}])
然后设 (dp_{i,l,r}) 表示第 (b_i) 在合法区间 (1) 有 (l) 种取法，在合法区间 (2) 有 (r) 种取法的方案数，每次暴力枚举 (b_i) ，从上一个转移过来即可，注意要判断边界，因为重复的数不能重复钦定。
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
#define il inline
using namespace std;
typedef long long ll;
const int N=105;
#define P 1000000007
int f[N][N][N],a[N],n,ans,m;
il void add(it &p,ct q){p+=q,p>=P?p-=P:0;}
int main(){
scanf("%d",&n),m=(n<<1)-1;it i;
for(i=1;i<=m;++i) scanf("%d",&a[i]);
std::sort(a+1,a+1+m);
f[n][1][0]=1;
for(i=n-1;i;--i){
ct fl=(a[i]!=a[i+1]),fr=(a[m-i]!=a[m-i+1]);
for(it l=0;l<=m;++l)
for(it r=0;r<=m;++r)
if(f[i+1][l][r]){
for(it x=1;x<=l+fl;++x) add(f[i][l+fl-x+1][r+fr+(x>1)],f[i+1][l][r]);
for(it x=1;x<=r+fr;++x) add(f[i][l+fl+1][r+fr-x],f[i+1][l][r]);
}
}
for(it l=0;l<=m;++l) for(it r=0;r<=m;++r) add(ans,f[1][l][r]);
printf("%d",ans);
return 0;
}
AGC013
D
E
lxm：这题可以容斥，有优化的方法。
题意就是有一些标记点，可以放正方形，但正方形边界不能放标记点上，一次安放的贡献是 (prod a_i) ，(a_i) 是正方形边长，问所有方案贡献和，取膜。
考虑暴力 dp ，当 (i) 为标记点 (f_i=0) ，当 (i) 不为标记点时：
维护三个变量就可以做到 (O(n)) 。
但是现在 (n) 非常大，肯定要矩阵快速幂，于是考虑推 (f_i ightarrow f_{i+1}) ，就是推转移过程。
令 (i-j = x_j) （因为 (i) 是公共的相当于只和 (j) 有关系）
如果 (f_i=0) ，那么 ：
如果 (f_i eq 0) 那么还要加上 (f_i) ：
考虑转移矩阵，实际上是转移这三项。
令：
显然 (f_i=c_i) ，考虑转移，如果 (f_i=0)：
如果 (f_i eq 0) ，
直接转移即可，初始是 (f_0) ，相当于 (a_0=0,b_0=0,c_0=1)。
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
#define P 1000000007
int n,m;
struct ky{
int a[4][4];
ky operator * (const ky&b)const{
register ky c;
for(it i=0;i<3;++i)
for(it j=0;j<3;++j)
c.a[i][j]=((0ll+a[i][0])*b.a[0][j]+(0ll+a[i][1])*b.a[1][j]+(0ll+a[i][2])*b.a[2][j])%P;
return c;
}
}o1,o2,f;
ky ksm(ky x,it L){
register ky ans;memset(ans.a,0,sizeof(ans.a));
ans.a[0][0]=ans.a[1][1]=ans.a[2][2]=1;
while(L) L&1?ans=ans*x,0:0,x=x*x,L>>=1;
return ans;
}
int main(){
scanf("%d%d",&m,&n);it i;
o1.a[0][0]=1,o1.a[0][1]=0,o1.a[0][2]=0,
o1.a[1][0]=1,o1.a[1][1]=1,o1.a[1][2]=0,
o1.a[2][0]=1,o1.a[2][1]=2,o1.a[2][2]=1,
o2.a[0][0]=1,o2.a[0][1]=0,o2.a[0][2]=1,
o2.a[1][0]=1,o2.a[1][1]=1,o2.a[1][2]=1,
o2.a[2][0]=1,o2.a[2][1]=2,o2.a[2][2]=2;
memset(f.a,0,sizeof(f.a)),f.a[0][0]=f.a[1][1]=f.a[2][2]=1;
it now=0,pre=0;
for(i=1;i<=n;++i) scanf("%d",&now),f=f*ksm(o2,now-pre-1)*o1,pre=now;
f=f*ksm(o2,m-now),printf("%d",f.a[2][0]);
return 0;
}
F
AGC014
D
题意是博弈，两人轮流选择一个点染色，先手染白后手染黑，染完之后所有黑色点会把它相邻的点都染黑，如果最后还有白点先手胜否则先手败，问是否有先手必胜策略。
摸了一会儿就会了 ==
首先如果一个点连接了两个叶子，染白它，先手必胜。
我们发现如果每次先手染倒数第二层的点，那么后手必然要染倒数第一层的点。那么这两层对上面实际上是没有影响的。于是问题缩小成了子问题，还是用上面那个判断方法。
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
using namespace std;
const int N=1000005;
int n,fa[N],col[N];
vector<int> g[N];
queue<int> q;
bool vs[N];
void dfs(ct x){
col[x]=1;it son=0;
for(const int &j : g[x])
if(j^fa[x]){
fa[j]=x,dfs(j);
if(col[j]==1){
col[x]=0,++son;
if(son>=2) puts("First"),exit(0);
}
}
}
int main(){
scanf("%d",&n);it i,u,v;
for(i=1;i<n;++i) scanf("%d%d",&u,&v),g[u].push_back(v),g[v].push_back(u);
dfs(1),col[1]==1?puts("First"):puts("Second");
return 0;
}
E
给定一棵树，初始所有边为蓝色。每次选择一条所有边都是蓝色的路径，删掉其中一条边，然后在路径的两个端点之间连一条红边。问是否能得到目标形态的树。
膜了 zzt 学长的代码想通的做法 ==
不断删除重边，每次用并查集启发式合并，一旦有重边就加入队列，最后判断是否能删完就可以了。非常神，完全想不到。
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
using namespace std;
const int N=1000005;
int n,ans,fa[N];
set<int> g[N];
set<pair<int,int> > q;
void add(it u,it v){
auto p=g[u].find(v);
if(p==g[u].end()) return g[u].insert(v),void();
g[u].erase(p),u>v?std::swap(u,v),0:0,q.insert({u,v});
}
int fd(ct x){return fa[x]^x?fa[x]=fd(fa[x]):x;}
int main(){
scanf("%d",&n);it i,u,v;
for(i=1;i<n;++i) scanf("%d%d",&u,&v),add(u,v),add(v,u);
for(i=1;i<n;++i) scanf("%d%d",&u,&v),add(u,v),add(v,u);
for(i=1;i<=n;++i) fa[i]=i;
while(!q.empty()){
auto p=*q.begin();q.erase(q.begin());
u=fd(p.first),v=fd(p.second),g[u].size()>g[v].size()?std::swap(u,v),0:0,fa[u]=v;
for(const auto&p : g[u]) g[p].erase(u),add(v,p),add(p,v);
g[u].clear(),++ans;
}
puts(ans==n-1?"YES":"NO");
return 0;
}
F
题意是每次把满足 (forall j<i, a_j<a_i) 的 (a_i) 全部移动到序列的最后面，而且相对顺序不发生改变。求多少次之后序列有序。
太神了 ==
设 (T_i) 表示 (i sim n) 有序的最小步数，(F_i) 表示排了 (i sim n) ，排了 (T_i-1) 步后序列的开头。
考虑 (i,i+1,f_i) 在原序列中的相对位置：
-
(i,i+1,f_i:) (i) 和 (i+1) 肯定可以一起排序，次数不变
-
(i+1,i,f_i:) (i) 和 (i+1) 肯定不能一起排序，次数 (+1)
-
(f_i,i,i+1:) 可以一起排序，次数不变
-
(f_i,i+1,i:) 不能一起排序，次数 (+1)
-
(i+1,f_i,i:) (i+1) 放到 (f_i) 后会变成 (f_i,i,i+1) ，可以一起排序，次数不变
-
(i,f_i,i+1:) (i) 放到 (f_i) 后会变成 (f_i,i+1,i) ，不能一起排序，次数 (+1)
所以分类讨论即可。
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
using namespace std;
const int N=1000005;
int n,a[N],f[N];
int main(){
scanf("%d",&n);it i;
for(i=1;i<=n;++i) scanf("%d",&a[i]),f[a[i]]=i;
it ans=0,now=0;
for(i=n-1;i;--i){
if(!ans){
if(f[i]>f[i+1]) ++ans,now=i+1;
continue;
}
if(f[now]<=f[i]&&f[i]<=f[i+1]) continue;
if(f[i]<=f[i+1]&&f[i+1]<=f[now]) continue;
if(f[i+1]<=f[now]&&f[now]<=f[i]) continue;
++ans,now=i+1;
}
printf("%d",ans);
return 0;
}
AGC015
D
题意是问 ([A,B]) 内的数 or 起来的所有可能。
没想出来，唉，看了这位神仙的博客 。
转成二进制，考虑 (A,B) 前面一样的可以不用管，只要找最高位的 (i) 使得 (A,B) 第 (i) 位不一样。令 (C=2^i) ，答案就是在 ([A,C),[C,B]) 这两个区间里面选。
分情况讨论：
-
只选区间 (1) 里面的：范围为 ([A,C))
-
只选区间 (2) 里面的：范围为 ([C,min(B,C+2^{k+1}-1]) ，其中 (k) 为 (B) 中除了 (i) 最高位的 (1) 。
-
都选，范围为 ([C+A,C*2-1])
注意后两种情况会有重叠，需要判断一下。
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
using namespace std;
typedef long long ll;
ll A,B,ans;
int main(){
scanf("%lld%lld",&A,&B);it i;
for(i=60;~i;--i) if((A>>i&1)!=(B>>i&1)) break;
if(i<0) return putchar('1'),0;
auto calc = [&](ll x){it ans=0;while(x) ++ans,x>>=1;return ans;};
A&=(1ll<<i+1)-1,B&=(1ll<<i)-1,ans+=(1ll<<i)-A,B=calc(B),ans+=(1ll<<B),ans+=(1ll<<i)-std::max(A,1ll<<B),printf("%lld",ans);
return 0;
}
E
非常 nb ，对这个计数一点思路都没有。参考了这位队爷的博客
题意：数轴上有 (n) 个点，每个点初始时在位置 (x_i)，以 (v_i) 的速度向数轴正方向前进。初始时刻，你可以选择一些点为其染色，染色的点会将其碰到的所有点都染上色。问有多少种初始染色方案，能使得最终所有的点都被染色。
F
题意： (Q) 次询问，问所有 (1 leq x leq X_i,1 leq y leq Y_i) 中 (gcd(x,y)) 递归次数最多的是多少，以及有多少点对达到最大值。
推了一会儿，诶我会第一问，就是斐波那契数列！诶第二问好像也有思路！意识到可能做过这个题（不然不会想这么快），然后发现来源竟然是校内 OJ 上某次 2020NOIP联考（搬题人sxbk）
第一问显然是斐波那契数列，第二问合法的一定是这样的： ((a,b) ightarrow (b+ka,a)) ，可以先预处理，然后直接搜。
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
using namespace std;
#define P 1000000007
typedef long long ll;
#define pb push_back
#define mkp make_pair
const int N=10005;
const ll inf=2e18;
vector<pair<ll,ll> > vec[N];
ll f[N],x,y;
int tot,T;
int main(){
for(it i=(f[0]=f[1]=1)+1;;++i){
f[i]=f[i-1]+f[i-2];
if(f[i]>inf){tot=i-1;break;}
}
for(it i=(vec[1].pb(mkp(1,2)),vec[1].pb(mkp(1,3)),vec[1].pb(mkp(1,4)),1);i+3<=tot;++i){
for(const auto &j : vec[i]){
x=j.first,y=j.second;x+=y;
while(x<=f[i+3]+f[i]) vec[i+1].pb(mkp(y,x)),x+=y;
}
std::sort(vec[i].begin(),vec[i].end());
}
scanf("%d",&T);
while(T--){
scanf("%lld%lld",&x,&y),x>y?std::swap(x,y),0:0;it i;
if(x==1 || (x==2&&y==2)){printf("1 %lld
",x*y%P);continue;}
for(i=1;i<=tot;++i)
if(vec[i][0].first>x||vec[i][0].second>y) break;
ll ans=0;i-=2;
for(const auto &j : vec[i]) if(j.second<=x) ans=(ans+(x-j.first)/j.second+(y-j.first)/j.second)%P;
printf("%d %lld
",i+1,ans);
}
return 0;
}
AGC016
D
题意：给定初始序列，每次操作可以将某个位置变成整个序列的异或和，问最少几步到达目标序列。
啥 sb 题啊，随便摸一下发现是这样的：((a,b,c) ightarrow (a, a xor b xor c , c)) ，这时候异或和为 (b) ；((a, a xor b xor c , c) ightarrow (b, a xor b xor c , c)) ，这时候异或和为 (a) 。所以我们发现每次操作都是内部消化，就是除了全体 (xor) 和不会增加新的数字进来，那么无解很好判断。继续刚刚的步骤，((b, a xor b xor c , c) ightarrow (b,a,c)) ，这时候我们相当于进行了一次交换。
那么现在我们把全体 (xor) 和也加进序列，这时候相当于每次把某个数和全体 (xor) 和换位置。所以如果最终全体 (xor) 和不出现在目标序列中，就得多一次把他换回去，否则不用。发现如果把可以换的连边，会形成一堆环或者链，注意到每个环或者链之间需要多一次操作进行搭桥，所以答案就是边 (+) 不同环或链个数 (-1) 。
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
using namespace std;
const int N=1000005;
int n,a[N],b[N],ans,cnt;
bool vs[N];
map<int,int> in,id;
vector<int> g[N];
void dfs(ct x){vs[x]=1;for(const auto&p : g[x]) if(!vs[p]) dfs(p);}
int main(){
scanf("%d",&n);it i,tot=0;
for(i=1;i<=n;++i) scanf("%d",&a[i]),tot^=a[i],++in[a[i]];++in[tot];
for(i=1;i<=n;++i){
scanf("%d",&b[i]),--in[b[i]];
if(in[b[i]]<0) return puts("-1"),0;
}
auto add = [&](ct u,ct v){g[u].push_back(v),g[v].push_back(u);};
for(i=1;i<=n;++i) if(!id[a[i]]) id[a[i]]=++cnt;if(!id[tot]) id[tot]=++cnt;
for(i=1;i<=n;++i) if(a[i]!=b[i]) ++ans,add(id[a[i]],id[b[i]]);
for(i=1;i<=cnt;++i) if((!g[i].empty())&&(!vs[i])) dfs(i),++ans;
ans-=(!g[id[tot]].empty()),printf("%d",ans);
return 0;
}
E
题意：好长，不想打了，看图（图源）
这个题有一百种做法然而我一种都不会。看了兔队的做法觉得非常 nb。
就考虑给每个鸡分配一个 bool 变量表示它是否活着，然后可以根据题目给的关系建立出 (2-SAT) 模型，然后是 DAG 每个点是否可达，跑可行解可以用 bitset 优化。
F
lxm：sb 题
题意：一个 DAG，每条边 ((u,v)) 都保证 (u<v) ，每次轮流沿 DAG 上的边移动一颗石头，不能移动则输，求所有 (2^m) 个边的子集中，只保留这个子集时先手必胜方案个数的和。
发现两个棋子是独立的，现在等价于求 (2^m- (sg_1==sg_2)) 的方案。
考虑分层 dp，最后只要使得 (1) 和 (2) 在同一层。我们枚举一个子集 (S) ，考虑计算这个子集的答案。我们另枚举一个子集 (T) 使得 (T) 里面的点 (sg) 都为 (0) 。这时候其他点的 (sg>0) ，那么就让其他点往 (T) 里面连一条边，(T) 的内部没有边。然后 (T) 向剩余的点集里面连边，并 ( imes f[S-T]) ，这样转移就相当于给 (S-T) 里面的 (sg+1) 。
转移可以通过预处理做到 (O(n)) ，时间复杂度为 (O(3^n imes n)) 。
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
using namespace std;
#define P 1000000007
const int N=1<<15;
int n,m,f[N],cnt[16][N],pw[N],e[16][N];
bool flag[N];
int main(){
scanf("%d%d",&n,&m);it i,ans=1;
for(it i=0,u,v;i<m;++i) scanf("%d%d",&u,&v),--u,--v,e[u][1<<v]=1,ans<<=1,ans>=P?ans-=P:0;
ct lim=1<<n;
for(i=pw[0]=1;i<=n;++i) pw[i]=pw[i-1]<<1,pw[i]>=P?pw[i]-=P:0;
for(it s=0;s<lim;++s) flag[s]=(((s&1)>0)==((s&2)>0));
for(i=0;i<n;++i) for(it s=0,j;s<lim;++s) j=s&-s,cnt[i][s]=cnt[i][s^j]+e[i][j];
f[0]=1;
for(it s=1,ss,st,o;s<lim;++s)
if(flag[s]){
f[s]=1;
for(ss=(s-1)&s;ss;ss=(ss-1)&s)
if(flag[ss]){
for(i=0,st=s^ss,o=f[st];i<n;++i)
if(st>>i&1) o=(0ll+o)*(pw[cnt[i][ss]]-1ll)%P;
else if(ss>>i&1) o=(0ll+o)*pw[cnt[i][st]]%P;
f[s]+=o,f[s]>=P?f[s]-=P:0;
}
}
printf("%d",(ans-f[lim-1]+P)%P);
return 0;
}
AGC017
D
E
F
AGC018
D
yg 哥哥太神了，竟然会去掉树的限制的题意（
题意是给定一棵有边权的树，有一个完全图，每条边边权是他们在树上的距离，求最长哈密顿路径。
考虑最长哈密顿回路怎么求：考虑每个点进子树走一圈再出来。考虑每条边把树分成两个连通块，那么小连通块走到大连通块一定会经过这条边。所以统计每条边的贡献即可。
现在要删掉最小的一条边（或者说路径）。如果随便删一条可能不在最优解里面，现在考虑删除一定在最优解里面的最小路径。发现每次从小连通块走到大连通块，所以所有最优路径都会经过重心，那么只要删去一条经过重心最短的边即可。如果有两个重心删去他们之间的边。
E
F
题意是给定两棵树，请你构造点权使得每个点在每棵树里的子树点权值都为 (+1) 或者 (-1) 。
神秘的构造题 == 看了这位神仙的题解
考虑自底向上推，每个点如果 (size) 为奇数就把它的点权设为 (0) ，否则设为 (+1) 或 (-1) ，那么无解肯定是某个点在两个子树里面的子树奇偶性不一样。
考虑每个点子树保留奇数个奇数点，在里面互相配对，多出来的跟其他子树配对，这时候每个点在第一棵树和第二棵树各有一条边，所以所有环都是偶环，这样图就是一个二分图，将他进行黑白染色，黑点为 (+1) ，白点为 (-1) 。
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
using namespace std;
const int N=1000005;
int n,fa[N],ds[N];
int fd(ct x){
if(x==fa[x]) return x;
ct fx=fd(fa[x]);
ds[x]^=ds[fa[x]],fa[x]=fx;
return fx;
}
void mer(ct x,ct y){
ct u=fd(x),v=fd(y);
if(u==v) return ;
ds[u]=ds[x]^ds[y]^1,fa[u]=v;
}
struct ky{
vector<int> g[N];
int root,fa[N],w[N],sz[N];
void build(){for(it i=1;i<=n;++i) scanf("%d",&fa[i]),~fa[i]?g[fa[i]].push_back(i),++sz[fa[i]]:root=i;}
void dfs(ct x){
vector<int> vec;
for(const int &j : g[x])
dfs(j),vec.push_back(w[j]);
if(!(sz[x]&1)) vec.push_back(x);
std::sort(vec.begin(),vec.end()),w[x]=vec[0];
for(it i=1;i<vec.size();i+=2) mer(vec[i],vec[i+1]);
}
}A,B;
int main(){
scanf("%d",&n),A.build(),B.build();
for(it i=1;i<=n;fa[i]=i,++i) if((A.sz[i]&1)!=(B.sz[i]&1)) return puts("IMPOSSIBLE"),0;
A.dfs(A.root),B.dfs(B.root),puts("POSSIBLE");
for(it i=1;i<=n;++i) printf("%d ",A.sz[i]&1?0:(fd(i),ds[i]&1?1:-1));
return 0;
}
AGC019
D
E
F
题意：有 (n+m) 个问题，其中有 (n) 个问题的答案是 YES，(m) 个问题的答案是 NO。每猜一个问题，会知道这个问题的答案，求最优策略下期望能猜对多少。
考虑每次如果 YES 比较多，会优先去猜 YES。现在我们抽象成网格行走，有一条 (x=y) 的直线，从 ((n,m)) 开始行走，如果我们在直线下就往左边走，如果在直线上就往下面走。如果我们每次只猜一种那么一定有 (max(n,m)) 能对，所以我们只需要统计经过直线 (x=y) 的路径数。由于每次猜对的概率为 (frac{1}{2}) ，总的方案数是 (inom{n+m}{m}) ，所以期望就是：
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
using namespace std;
#define P 998244353
const int N=1000005;
int n,m,fac[N],ifac[N];
int C(ct n,ct m){return m<0||n<m?0:(0ll+fac[n])*ifac[m]%P*ifac[n-m]%P;}
int ksm(it x,it L){it ans=1;while(L) L&1?ans=(0ll+ans)*x%P:0,x=(0ll+x)*x%P,L>>=1;return ans;}
int main(){
scanf("%d%d",&n,&m);it i,ans=0,mx=(n>m?n:m)<<1;
for(i=fac[0]=1;i<=mx;++i) fac[i]=(0ll+fac[i-1])*i%P;
for(i=mx,ifac[i]=ksm(fac[i],P-2);i;--i) ifac[i-1]=(0ll+ifac[i])*i%P;
for(i=1;i<=n;++i) ans=(ans+(0ll+C(i+i,i))*C(n-i+m-i,n-i))%P;
ans=(0ll+ans)*(P+1>>1)%P,ans=(0ll+ans)*ifac[n+m]%P*fac[n]%P*fac[m]%P;
printf("%d",(ans+(mx>>1))%P);
return 0;
}
AGC020
D
E
F
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
using namespace std;
int n,m,c,a[10];
double f[301][1<<6];
int Min(ct p,ct q){return p<q?p:q;}
int Max(ct p,ct q){return p>q?p:q;}
int main(){
scanf("%d%d",&n,&c),m=n*c;it i,fac=0;double pw=1.0;
for(i=0;i<n;++i) scanf("%d",&a[i]);
for(i=1;i<n;++i) pw*=c;//fac*=i;
std::sort(a,a+n);
double ans=0;ct lim=1<<n-1;
do{
memset(f,0,sizeof(f)),f[a[n-1]*n][0]=1;
for(i=1;i<=m;++i)
if(i%n>0)
for(it s=0,j,p=i%n-1;s<lim;++s)
for(j=i;j<=m;++j)
if(!(s>>p&1))
f[Min(Max(j,i+a[p]*n),m)][s|1<<p]+=f[j][s];
ans+=f[c*n][lim-1],++fac;
}while(next_permutation(a,a+n-1));
printf("%.12lf",ans/fac/pw);
return 0;
}
AGC021
D
题意是更改 (K) 个字符，使得 (S) 和它的反串的最长公共子序列最长。
神秘结论：字符串的最长回文子序列等于它和它的反串的最长公共子序列。
证明可以考虑归纳（lxm 的做法），也可以考虑反证（我的做法），但是我觉得反证还是不太好证，我感性理解了一下。还是 lxm 的做法 nb。
归纳是这样的：
这三种情况，前两种可以删掉虚线划出去的，递归到子问题；最后一种可以找到分界点，然后递归到子问题。（还是 lxm 强！）
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
using namespace std;
const int N=305;
int n,f[N][N][N],K;
char S[N];
int Max(ct p,ct q){return p>q?p:q;}
int dfs(ct l,ct r,ct K){
if(l>r) return 0;
if(l==r) return 1;
if(~f[l][r][K]) return f[l][r][K];
if(S[l]==S[r]) return f[l][r][K]=dfs(l+1,r-1,K)+2;
f[l][r][K]=Max(dfs(l+1,r,K),dfs(l,r-1,K));
if(K>0) f[l][r][K]=Max(f[l][r][K],dfs(l+1,r-1,K-1)+2);
return f[l][r][K];
}
int main(){
scanf("%s%d",S+1,&K),n=strlen(S+1),memset(f,-1,sizeof(f));
printf("%d",dfs(1,n,K));
return 0;
}
E
以前做过的，补档。
推荐看兔队的题解。
code
#include<bits/stdc++.h>
#define it register int
#define ct const int
#define il inline
using namespace std;
#define P 998244353
const int N=1000005;
int n,K,fac[N],ifac[N],ans;
il int C(ct n,ct m){return n<m||m<0?0:(0ll+fac[n])*ifac[m]%P*ifac[n-m]%P;}
il int ksm(it x,it L){it ans=1;while(L) L&1?ans=(0ll+ans)*x%P:0,x=(0ll+x)*x%P,L>>=1;return ans;}
il void add(it &p,ct q){p+=q,p>=P?p-=P:0;}
il void sub(it &p,ct q){p-=q,p<0?p+=P:0;}
int main(){
scanf("%d%d",&n,&K);it i,j;
for(i=fac[0]=1;i<N;++i) fac[i]=(0ll+fac[i-1])*i%P;
for(i=N-1,ifac[i]=ksm(fac[i],P-2);i;--i) ifac[i-1]=(0ll+ifac[i])*i%P;
for(i=n;i<=K;++i) if(i>=K-i) j=K-(i==K-i),add(ans,C(j,i)),sub(ans,C(j,i+i-n+1));
printf("%d",ans);
return 0;
}