noi前橙名计划失败。全程搞C而gg……
A - Biscuits
题意：背包，求价值为奇/偶的方案数。
#include<cstdio>
#include<queue>
#include<algorithm>
#define ld long double
#define MN 21000000
using namespace std; int read_p,read_ca;
inline int read(){
read_p=;read_ca=getchar();
while(read_ca<''||read_ca>'') read_ca=getchar();
while(read_ca>=''&&read_ca<='') read_p=read_p*+read_ca-,read_ca=getchar();
return read_p;
}
int n,p,a;
long long mmh[];
int main(){
mmh[]=;
n=read();p=read();
while(n--){
a=read()&;
if (a&){
mmh[]=mmh[]=mmh[]+mmh[];
}else mmh[]<<=,mmh[]<<=;
}
printf("%lld\n",mmh[p]);
}
B - Moderate Differences
题意：询问是否可以把B-A表示成n-1个绝对值在C和D之间的数的和。
#include<cstdio>
#include<queue>
#include<algorithm>
#define ld long double
#define MN 21000000
using namespace std; int read_p,read_ca;
inline int read(){
read_p=;read_ca=getchar();
while(read_ca<''||read_ca>'') read_ca=getchar();
while(read_ca>=''&&read_ca<='') read_p=read_p*+read_ca-,read_ca=getchar();
return read_p;
}
long long n,a,b,c,d,w;
int main(){
scanf("%lld%lld%lld%lld%lld",&n,&a,&b,&c,&d);
b-=a;n--;
for (int i=;i<=n;i++){
w=-d*i+c*(n-i);
if (b-w<=(d-c)*n&&b>=w) return /*printf("%d %lld %lld %lld\n",i,w,n,b-w),*/puts("YES"),;
}
puts("NO");
}
C - Snuke and Spells
题意：定义一种操作为当序列长度为k时把所有等于k的元素删去，问将给定序列至少修改多少元素，序列能进行不断操作后为空。
题解：有一个结论：如果等于 $i$ 的数有$N_{i}$个，那么看成区间$[i-N_{i}+1,i]$，未被区间覆盖的位置数量即为答案。
#include<cstdio>
#include<algorithm>
#define MN 210000
using namespace std; int n,m,x,y,c[MN<<],t[MN],a[MN],mmh=;
int main(){
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++){
scanf("%d",&a[i]);
if (a[i]-t[a[i]]>) mmh+=(c[a[i]-t[a[i]]]++)==;
t[a[i]]++;
}
while (m--){
scanf("%d%d",&x,&y);
t[a[x]]--;
if (a[x]-t[a[x]]>)mmh-=(--c[a[x]-t[a[x]]])==;
a[x]=y;
if (a[x]-t[a[x]]>)mmh+=(c[a[x]-t[a[x]]]++)==;
t[a[x]]++;
printf("%d\n",n-mmh);
}
}
D - Game on Tree
题意：裸删边游戏。
题解：大佬论文
#include<cstdio>
#include<queue>
#include<algorithm>
#define ld long double
#define MN 210000
using namespace std; int read_p,read_ca;
inline int read(){
read_p=;read_ca=getchar();
while(read_ca<''||read_ca>'') read_ca=getchar();
while(read_ca>=''&&read_ca<='') read_p=read_p*+read_ca-,read_ca=getchar();
return read_p;
}
struct na{int y,ne;}b[MN];
int n,m,l[MN],num=,x,y,s[MN];
inline void in(int x,int y){
b[++num].y=y;b[num].ne=l[x];l[x]=num;
}
void dfs(int x,int f){
int u=;s[x]=;
for (int i=l[x];i;i=b[i].ne)
if (b[i].y!=f){
dfs(b[i].y,x);u^=s[b[i].y]+;
} s[x]=u;
/*for (int i=l[x];i;i=b[i].ne)
if (b[i].y!=f){
if ((u^s[b[i].y])==0) s[x]=1;
}*/
//printf("%d %d\n",x,s[x]);
}
int main(){
n=read();
for (int i=;i<n;i++) x=read(),y=read(),in(x,y),in(y,x); dfs(,);
puts(s[]?"Alice":"Bob");
}
E - Jigsaw
题意：问能否把拼图排成一排使得相邻拼图契合。
题解：把拼图看成边，其两段信息作为点连边然后并查集。
#include<cstdio>
#include<algorithm>
#define NO return puts("NO"),0
using namespace std; int n,m,f[],a,b,c,d,x,y,D[],bo[],C[];
int gf(int x){return x==f[x]?x:f[x]=gf(f[x]);}
int main(){
scanf("%d%d",&n,&m); for (int i=;i<;i++) f[i]=i;
while (n--){
scanf("%d%d%d%d",&a,&b,&c,&d);
if (c==) x=a;else x=-c;x+=;
if (d==) y=-b;else y=d;y+=;
f[gf(x)]=gf(y);
D[x]++;D[y]--;bo[x]=;
}
for (int i=;i<;i++) if (D[i]>) NO;
for (int i=;i<;i++) if (D[i]<) NO;
for (int i=;i<;i++)
if (bo[gf(i)]|=bo[i],D[i]) C[f[i]]=;
for (int i=;i<;i++)
if (f[i]==i&&!C[i]&&bo[i]) NO;
puts("YES");
}
F - Zigzag
题意：在$\frac{n*(n+1)}{2}$三角形上从顶到底画m条可重合，不可相交的线，某些线的部分已经确定，求方案数，、
题解：dp[i][j]表示考虑了前$i$条线，第$i$条线的位置状态为$j$的方案数。转移起来有点麻烦，窝看并抄了dalao的代码，实现得非常优雅，大约是从高往低考虑往左走的线可以向往右的线转移。
#include<cstdio>
#include<algorithm>
#define MN 1000
using namespace std; const int MOD=1e9+;
int n,m,k,le[MN],ri[MN],x,y,z,mmh[<<],MMH=;
inline void M(int &x){while(x>=MOD)x-=MOD;}
int lowbit(int x) { return x & -x; }
int main(){
scanf("%d%d%d",&n,&m,&k);n--;
for (int i=;i<=m;i++) le[i]=(<<n)-,ri[i]=;
while(k--){
scanf("%d%d%d",&x,&y,&z);y--;
if (z==) le[x]^=<<y;else ri[x]^=<<y;
}
mmh[]=;
for (int i=;i<=m;i++){
for (int k=;k<n;k++)
for (int j=;j<(<<n);j++) if (~j>>k&)
M(mmh[j+(<<k)-lowbit(j&~((<<k)-))]+=mmh[j]);
for (int j=;j<(<<n);j++)
if (!((j&ri[i])==ri[i]&&(j&le[i])==j)) mmh[j]=;
}
for (int j=;j<(<<n);j++) M(MMH+=mmh[j]);
printf("%d\n",MMH);
}