A：Biscuits（点此看题面）
- 有(n)个数，问有多少种方法选数，使得选出数之和模(2)余(p)。
- (nle50)
签到题
设(f_{i,0/1})表示取到第(i)位，当前模(2)余(0/1)的方案数。
显然就考虑取和不取两种转移即可。
代码：(O(n))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 50
#define LL long long
using namespace std;
int n,p;LL f[N+5][2];
int main()
{
RI i,x;for(scanf("%d%d",&n,&p),f[0][0]=i=1;i<=n;++i)
scanf("%d",&x),x&=1,f[i][0]=f[i-1][0]+f[i-1][x],f[i][1]=f[i-1][1]+f[i-1][x^1];//DP转移
return printf("%lld
",f[n][p]),0;
}
B：Moderate Differences（点此看题面）
- 给定一张(n)个各格子的纸条，其中第一个格子填(A)，最后一个格子填(B)。
- 要求相邻格子之间差值的绝对值在([C,D])中。
- 问是否存在一张合法的纸条。
- (nle5 imes10^5)
简单题
不妨令第一个格子为(0)，最后一个各自为(B-A)，显然与原问题等价。
考虑第一个格子可能值为(0)，第二个格子可能为([-D,-C]∪[C,D])。
每新增一个格子，相当于选择一个已有值域区间，加上一个数则左右端点各自加上(C,D)，减去一个数则左右端点格子减去(D,C)。
那么我们枚举共加了(i)次，对应的最终值域区间为([i imes C-(n-1-i) imes D,i imes D-(n-1-i) imes C])。
代码：(O(n))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define LL long long
using namespace std;
int n;LL A,B,C,D;
int main()
{
RI i;for(scanf("%d%lld%lld%lld%lld",&n,&A,&B,&C,&D),i=0;i^n;++i)//枚举加了几次
if(i*C-(n-1-i)*D<=B-A&&B-A<=i*D-(n-1-i)*C) return puts("YES"),0;return puts("NO"),0;//看B-A是否在某一个值域区间中
}
C：Snuke and Spells（点此看题面）
- 有一个长度为(n)的数列，你将会进行若干轮操作，若当前数的个数为(k)，则删去所有(a_i=k)的(a_i)。
- 多组操作，每次修改数列中的一个(a_i)。然后回答至少需要修改几个(a_i)才能让这个数列能被删空。
- (nle2 imes10^5)
转化
考虑若干相同的数可以转化为一些连续的数，例如连着的(3)个(4)可以变成(2,3,4)。
假设数字(i)出现了(c_i)次，就变成了若干([i-c_i+1,i])的区间能否覆盖整个([1,n])。
一次修改只会改变两个区间的长度，直接暴力修改。
然后询问至少要该几个数字才能覆盖整个([1,n])，就是看有多少位置没被覆盖。
代码：(O(n))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 200000
using namespace std;
int n,a[N+5],c[N+5],s[N+5];
int main()
{
RI Qt,i,x,y,ans=0;for(scanf("%d%d",&n,&Qt),i=1;i<=n;++i) scanf("%d",a+i),++c[a[i]];//统计每个数字出现次数
for(i=1;i<=n;++i) ++s[max(i-c[i]+1,1)],--s[i+1];for(i=1;i<=n;++i) ans+=!(s[i]+=s[i-1]);//差分实现覆盖
W(Qt--) scanf("%d%d",&x,&y),c[a[x]]<=a[x]&&!--s[a[x]-c[a[x]]+1]&&++ans,//删去原贡献
--c[a[x]],++c[a[x]=y],c[y]<=y&&!s[y-c[y]+1]++&&--ans,printf("%d
",ans);return 0;//加上新贡献
}
D：Game on Tree（点此看题面）
- 给定一棵树，先手和后手轮流操作。
- 每次断开一条边，并删去不包含(1)号点的连通块，不能操作的人就输了。
- 问谁必胜。
- (nle10^5)
博弈论
显然这是一道博弈论题目，因此思考如何构造(SG)函数。
首先，如果根节点有(k)个子节点，我们可以把根节点复制(k)份，每个根节点下接一个子节点。
那么这(k)个子树就独立了，既然如此原根节点(SG)值就是复制得到的(k)个根节点(SG)值的异或和。
现在就变成了在只有一个儿子时，父节点与子节点(SG)值的关系，发现：
- 若直接断开连接父节点和子节点的边，后继状态(SG=0)。
- 若断开其他边，我们发现子节点所有(SG)值都有可能转移到。
由于一个状态的(SG)等于所有后继状态(SG)的( exttt{mex})，所以父节点的(SG)等于子节点的(SG+1)。
那么直接(dfs)扫一遍就好了。
代码：(O(n))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100000
#define add(x,y) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y)
using namespace std;
int n,ee,lnk[N+5];struct edge {int to,nxt;}e[N<<1];
I int SG(CI x,CI lst=0) {RI i,t=0;for(i=lnk[x];i;i=e[i].nxt) e[i].to^lst&&(t^=SG(e[i].to,x)+1);return t;}//父节点SG=子节点SG+1异或和
int main()
{
RI i,x,y;for(scanf("%d",&n),i=1;i^n;++i) scanf("%d%d",&x,&y),add(x,y),add(y,x);
return puts(SG(1)?"Alice":"Bob"),0;//SG>0则先手胜，否则后手胜
}
E：Jigsaw（点此看题面）
- 一块拼图分三部分，中间高度(m)，左边长度(a_i)、离地面(c_i)，右边长度(b_i)、离地面(d_i)。
- 给定(n)块拼图，你需要把它们排成一排，一块拼图要么放在地上，要么架在另一块拼图上。
- 要求所有拼图不悬空，问是否存在合法方案。
- (nle10^5,mle200)
建图
显然如果一块拼图(c_i=0)，另一块拼图(d_i=a_i)，我们就可以把两块拼图拼在一起（(d_i=0,c_i=b_i)同理）。
那么那一块拼图看成一条有向边：(c_i=0)时左端点为(a_i)，否则为(m+c_i)；(d_i=0)时右端点为(m+b_i)，否则为(d_i)。
现在问题就变成了是否能选出若干条从([1,m])的点出发，在([m+1,2m])的点结束的路径，满足所有边都被经过恰好一次。
既然我们只用判YES或NO，只要满足三个条件：
- 对于所有([1,m])的点，入度不大于出度。
- 对于所有([m+1,2m])的点，出度不大于入度。
- 不存在环。（即任意连通块存在至少一点入度不等于出度）
代码：(O(m))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define M 400
using namespace std;
int n,m,ee,dI[M+5],dO[M+5],f[M+5],fa[M+5];
I int getfa(CI x) {return fa[x]?fa[x]=getfa(fa[x]):x;}//并查集
int main()
{
#define Union(x,y) (++dO[x],++dI[y],(fx=getfa(x))^(fy=getfa(y))&&(fa[fx]=fy))//并查集上合并
RI i,a,b,c,d,fx,fy;scanf("%d%d",&n,&m);
for(i=1;i<=n;++i) scanf("%d%d%d%d",&a,&b,&c,&d),Union(c?m+c:a,d?d:m+b);//拼图转化为边
for(i=1;i<=2*m;++i) f[getfa(i)]|=dI[i]!=dO[i];//记录一个连通块是否存在入度不等于出度的点
for(i=1;i<=2*m;++i) if((dI[i]||dO[i])&&!fa[i]&&!f[i]) return puts("NO"),0;//存在环
for(i=1;i<=m;++i) if(dI[i]>dO[i]) return puts("NO"),0;//[1,m]中有点入度大于出度
for(i=m+1;i<=2*m;++i) if(dI[i]<dO[i]) return puts("NO"),0;return puts("YES"),0;//[m+1,2m]中有点出度大于入度
}
F：Zigzag（点此看题面）
- 有一个(n)行的三角形，第(i)行有(i)个点。每次只能从((i,j))走到((i+1,j))或((i+1,j+1))。
- 你要找出(m)条从上往下的路径，满足第(i)条路径任意时刻都在第(i-1)条路径的右边。
- 同时你有(k)个限制，表示某一次路径在某一层必须走某一个方向。
- (n,mle20,kle (n-1) imes m)
状压
考虑我们完全可以把一条路径状压起来。
假设上一次路径为(pre)，这一次路径为(now)，那么这次路径是合法的当且仅当(now)二进制下任意前缀和始终大于等于(pre)对应前缀和。
这也是我仅能想到的东西了。。。
动态规划
我们设(f_{i,j,k})表示当前做到第(i)条路径，前(j-1)位已经确定完毕且与第(i-1)条路径相同，第(i-1)条路径为(k)。
转移时分类讨论：
- 如果前一条路径这一位为(1)，当前路径这一位为(0)，显然非法。
- 如果前一条路径与当前路径这一位相同，直接转移。
- 如果前一条路径与当前路径这一位不同，由于已经判掉了(1,0)的情况，那么只可能是(0,1)。
- 考虑我们找到前一条路径接下来的第一个(1)，然后把它移到前面来，发现这并不影响之后的决策。
- 而如果找不到(1)，即接下来全是(0)，那么更加可以任填了。
就按照这种思路(DP)就好了，其实很好理解。
代码：(O(nm2^{n-1}))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 20
#define X 1000000007
#define Inc(x,y) ((x+=(y))>=X&&(x-=X))
using namespace std;
int n,m,a[N+5][N+5],p[1<<N][N+5],f[N+5][1<<N];
int main()
{
RI i,j,k,t,x,y,l;scanf("%d%d%d",&n,&m,&t),l=1<<n-1;
for(memset(a,-1,sizeof(a)),i=1;i<=t;++i) scanf("%d%d",&x,&y),scanf("%d",a[x]+y-1);//存储限制
for(k=0;k^l;++k) for(j=0;j^n;++j) {for(t=j+1;t^n&&!(k>>t&1);++t);p[k][j]=t^n?t:-1;}//预处理k第j位之后的第一个1
for(f[n-1][0]=i=1;i<=m;++i)//枚举链
{
for(k=0;k^l;++k) f[0][k]=f[n-1][k];for(j=1;j^n;++j) for(k=0;k^l;++k) f[j][k]=0;//初始化
for(j=0;j^(n-1);++j) for(k=0;k^l;++k) if(f[j][k]) for(x=0;x^2;++x)
{
if(~a[i][j]&&a[i][j]^x) continue;if(k>>j&1&&!x) continue;//不满足限制，或填法为1,0直接跳过
if((k>>j&1)==x) {Inc(f[j+1][k],f[j][k]);continue;}//与前一条链相同直接转移
~(t=p[k][j])?Inc(f[j+1][k^(1<<j)^(1<<t)],f[j][k]):Inc(f[j+1][k^(1<<j)],f[j][k]);//把下一个1移上来，找不到则随意转移
}
}
for(t=k=0;k^l;++k) Inc(t,f[n-1][k]);return printf("%d
",t),0;//统计答案
}