赶进度赶进度，丢个代码两三句备注一下完事了。
day1：
前面两道题没实际写代码怕印象不深所以描述一下大意。
T1：
题目大意：给出两个数&、|、^的结果（可能只给出其中某一项或者某两项），求这两种数有多少种选取情况。
关键点是讨论无限解。只给出^和只给出&的情况无法确定最高位的1在哪里所以解是无穷个。
其它情况只要把给出的数据转化成二进制一位一位讨论就行了。
T2：
题目大意：一开始存在一个空集A。有四种操作，给出一个集合B使A成为与B的交集或并集，以及让A中的所有元素加一或者减一。要求输出每次操作后A中元素之和。
开桶来维护集合里存在哪些元素，当前存在的元素标记为tim。成为并集的时候，读入B集合，将里面未标记为tim的标记一下，维护现存元素的和。成为交集的时候先让tim++，对于B集合里的每个元素，若原本标记为tim-1（先前的tim）则存在于新的A中，让它被标记为当前的tim，同样维护元素的和。关于加减操作，记录一下全局总变化值val，每次读入的B数组也先变化val再进行操作。输出答案的时候考虑siz和val共同作用的影响。
T3：
很容易想到对于每个空地联通块统计相同颜色的方块的贡献，然后发现很多方块要被记录多次使答案变大。能想到的解决方法是容斥，统计多少方块被一个连通块记录，被两个连通块记录…枚举连通块的所有选择状态然后枚举每个方块，或者其它怎样枚举，然后爆炸。
每个方块最多被四个连通块统计到，所以可以记录下统计到它的连通块，然后只针对这最多四个连通块的选择情况修改记录值。写一个哈希表，传进所选连通块的编号。翻众巨神们的博客发现还可以直接哈希。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=;
int n,m,k,tim;
long long ans;
int a[N][N],c[N][N],b[N][N][];
int h[]={,,-,,};
int l[]={,-,,,};
int p=,mod=;
struct node{
int x0,x1,x2,x3,col;
}t[];
int check(int x,node xx){
if(t[x].x0!=xx.x0)return ;
if(t[x].x1!=xx.x1)return ;
if(t[x].x2!=xx.x2)return ;
if(t[x].x3!=xx.x3)return ;
if(t[x].col!=xx.col)return ;
return ;
}
void dfs(int x,int y){
c[x][y]=tim;
for(int i=;i<=;i++){
int x1=x+h[i],y1=y+l[i];
if(x1<=||x1>n||y1<=||y1>m)continue;
if(c[x1][y1]!=tim&&a[x1][y1]){
c[x1][y1]=tim;
if(!b[x1][y1][])b[x1][y1][]=tim;
else if(!b[x1][y1][])b[x1][y1][]=tim;
else if(!b[x1][y1][])b[x1][y1][]=tim;
else b[x1][y1][]=tim;
}
else if(!c[x1][y1]&&!a[x1][y1])dfs(x1,y1);
}
}
int head[*],Next[*],v[*],cnt,siz[*],color[*];
int has(int x0,int x1,int x2,int x3,int col){
long long val=((((1ll*x0*p%mod+x1)%mod*p+x2)%mod*p+x3)%mod*p+col)%mod;
for(int i=head[val];i;i=Next[i]){
if(check(i,(node){x0,x1,x2,x3,col})){
siz[i]++;
return siz[i]-;
}
}
t[++cnt]=(node){x0,x1,x2,x3,col},Next[cnt]=head[val],head[val]=cnt;
siz[cnt]=;
return siz[cnt]-;
}
int main()
{
// freopen("1.in","r",stdin);
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
scanf("%d",&a[i][j]);
}
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(!a[i][j]&&!c[i][j]){
tim++;
dfs(i,j);
}
}
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(a[i][j]){
if(b[i][j][]){
ans+=has(b[i][j][],,,,a[i][j]);
}
if(b[i][j][]){
ans+=has(b[i][j][],,,,a[i][j]);
ans-=has(b[i][j][],b[i][j][],,,a[i][j]);
}
if(b[i][j][]){
ans+=has(b[i][j][],,,,a[i][j]);
ans-=has(b[i][j][],b[i][j][],,,a[i][j]);
ans-=has(b[i][j][],b[i][j][],,,a[i][j]);
ans+=has(b[i][j][],b[i][j][],b[i][j][],,a[i][j]);
}
if(b[i][j][]){
ans+=has(b[i][j][],,,,a[i][j]);
ans-=has(b[i][j][],b[i][j][],,,a[i][j]);
ans-=has(b[i][j][],b[i][j][],,,a[i][j]);
ans-=has(b[i][j][],b[i][j][],,,a[i][j]);
ans+=has(b[i][j][],b[i][j][],b[i][j][],,a[i][j]);
ans+=has(b[i][j][],b[i][j][],b[i][j][],,a[i][j]);
ans+=has(b[i][j][],b[i][j][],b[i][j][],,a[i][j]);
ans-=has(b[i][j][],b[i][j][],b[i][j][],b[i][j][],a[i][j]);
}
}
}
}
int num=;
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(a[i][j]==a[i][j-]&&a[i][j]){
num=;
for(int k=;k<=;k++){
for(int l=;l<=;l++){
if(b[i][j][k]==b[i][j-][l]&&b[i][j][k]){
num=;
break;
}
}
}
ans+=num;
}
}
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(a[i][j]==a[i-][j]&&a[i][j]){
num=;
for(int k=;k<=;k++){
for(int l=;l<=;l++){
if(b[i][j][k]==b[i-][j][l]&&b[i][j][k]){
num=;
break;
}
}
}
ans+=num;
}
}
}
printf("%lld\n",ans);
return ;
}
哈希表
#include<iostream>
#include<cstdio>
using namespace std;
const int N=;
int n,m,k,tim;
long long ans;
int a[N][N],c[N][N],b[N][N][];
int h[]={,,-,,};
int l[]={,-,,,};
int p=,mod=;
void dfs(int x,int y){
c[x][y]=tim;
for(int i=;i<=;i++){
int x1=x+h[i],y1=y+l[i];
if(x1<=||x1>n||y1<=||y1>m)continue;
if(c[x1][y1]!=tim&&a[x1][y1]){
c[x1][y1]=tim;
if(!b[x1][y1][])b[x1][y1][]=tim;
else if(!b[x1][y1][])b[x1][y1][]=tim;
else if(!b[x1][y1][])b[x1][y1][]=tim;
else b[x1][y1][]=tim;
}
else if(!c[x1][y1]&&!a[x1][y1])dfs(x1,y1);
}
}
int head[*],Next[*],v[*],cnt,siz[*];
int has(int x0,int x1,int x2,int x3,int col){
long long val=((((1ll*x0*p%mod+x1)%mod*p+x2)%mod*p+x3)%mod*p+col)%mod;
for(int i=head[val];i;i=Next[i]){
if(v[i]==col){
siz[i]++;
return siz[i]-;
}
}
v[++cnt]=col,Next[cnt]=head[val],head[val]=cnt;
siz[cnt]=;
return siz[cnt]-;
}
int main()
{
// freopen("1.in","r",stdin);
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
scanf("%d",&a[i][j]);
}
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(!a[i][j]&&!c[i][j]){
tim++;
dfs(i,j);
}
}
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(a[i][j]){
if(b[i][j][]){
ans+=has(b[i][j][],,,,a[i][j]);
}
if(b[i][j][]){
ans+=has(b[i][j][],,,,a[i][j]);
ans-=has(b[i][j][],b[i][j][],,,a[i][j]);
}
if(b[i][j][]){
ans+=has(b[i][j][],,,,a[i][j]);
ans-=has(b[i][j][],b[i][j][],,,a[i][j]);
ans-=has(b[i][j][],b[i][j][],,,a[i][j]);
ans+=has(b[i][j][],b[i][j][],b[i][j][],,a[i][j]);
}
if(b[i][j][]){
ans+=has(b[i][j][],,,,a[i][j]);
ans-=has(b[i][j][],b[i][j][],,,a[i][j]);
ans-=has(b[i][j][],b[i][j][],,,a[i][j]);
ans-=has(b[i][j][],b[i][j][],,,a[i][j]);
ans+=has(b[i][j][],b[i][j][],b[i][j][],,a[i][j]);
ans+=has(b[i][j][],b[i][j][],b[i][j][],,a[i][j]);
ans+=has(b[i][j][],b[i][j][],b[i][j][],,a[i][j]);
ans-=has(b[i][j][],b[i][j][],b[i][j][],b[i][j][],a[i][j]);
}
}
}
}
int num=;
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(a[i][j]==a[i][j-]&&a[i][j]){
num=;
for(int k=;k<=;k++){
for(int l=;l<=;l++){
if(b[i][j][k]==b[i][j-][l]&&b[i][j][k]){
num=;
break;
}
}
}
ans+=num;
}
}
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(a[i][j]==a[i-][j]&&a[i][j]){
num=;
for(int k=;k<=;k++){
for(int l=;l<=;l++){
if(b[i][j][k]==b[i-][j][l]&&b[i][j][k]){
num=;
break;
}
}
}
ans+=num;
}
}
}
printf("%lld\n",ans);
return ;
}
直接哈希
害，我居然不会写哈希表。丑陋取模以及丑陋模数又让这份代码交了一页，大佬们都差点没把它救回来。
day2：
T1：
仔细读一遍题，发现要求给出的m长度串的最小循环节。一个字符串的所有循环节一定都是最小循环节的整数倍，利用gcd可证。
利用kmp算法的next数组可以直接求出最小循环节，若len%(len-next[n])==0，则(len-next[n])就是最小循环节的长度。
然后分类讨论一下，直接求出答案。
#include<iostream>
#include<cstdio>
using namespace std;
int t,n,m,nxt[];
char s[];
int main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
scanf("%s",s+);
for(int i=,j=;i<=m;i++){
j=nxt[i-];
while(s[j+]!=s[i]&&j){
j=nxt[j];
}
if(s[j+]==s[i])nxt[i]=j+;
}
if(m%(m-nxt[m])==&&nxt[m])printf("%lld\n",max(1ll*m*(n-)+nxt[m],1ll*nxt[m]));
else printf("%lld\n",max(1ll*m*(n-),1ll*nxt[m]));
for(int i=;i<=m;i++)nxt[i]=;
}
return ;
}
改成不仔细地读一遍题。关于我连-1都没判这个问题，我笑死了。
T2：
不会，刚听完讲，咕着。
T3：
首先对于自环的情况，输出原树直径/2+1。
其它情况则是求一个环上挂着的最长链。可能的答案存在四种：环最底下两个节点的儿子能走到的最长链，环最顶端节点（lca）除了环占用的两条链以外的儿子能走到的最长链，lca先往父亲走一步然后不返回这棵子树在整棵树上能走到的最长链，以及底端两个节点到lca路径上的节点除去被占用的这条路其它的最长链。
dfs的时候预处理一个节点的子节点们能走到的最长链、次长链、第三长链，解决第一种情况和第二种情况。
第三种情况，预处理每个点作为lca时的答案。这个答案可能是父亲的答案+1，也有可能是从父节点的其它子节点贡献来。讨论当前点是不是父节点记下的最长链子节点。
第四种情况，预处理每个点的父亲如果不走它能走到的最长链，和lca一样存在倍增数组里。查询的时候注意区间范围，不能查到lca。
害忘说了忘说了，有可能询问的两个点其中一个是另一个的祖先，这个时候特殊处理一下，大致和通常情况没什么区别。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=;
int n,m;
int ver[N*],head[N],Next[N*],tot,sum,x1,y1,ans;
void add(int x,int y){
ver[++tot]=y;
Next[tot]=head[x];
head[x]=tot;
}
int lon[N][],k[N][],tim[N],dep[N],lip[N];
void dfs1(int x,int fa){
for(int i=head[x];i;i=Next[i]){
int y=ver[i];
if(y==fa)continue;
dep[y]=dep[x]+;
dfs1(y,x);
if(tim[y]>lon[x][]){
lon[x][]=lon[x][];
k[x][]=k[x][];
lon[x][]=lon[x][];
k[x][]=k[x][];
lon[x][]=tim[y];
k[x][]=y;
}
else if(tim[y]>lon[x][]){
lon[x][]=lon[x][];
k[x][]=k[x][];
lon[x][]=tim[y];
k[x][]=y;
}
else if(tim[y]>lon[x][]){
lon[x][]=tim[y];
k[x][]=y;
}
}
tim[x]=lon[x][]+;
ans=max(ans,(lon[x][]+lon[x][])/+);
}
int st[N][],maxx[N][];
void dfs2(int x,int fa){
for(int i=head[x];i;i=Next[i]){
int y=ver[i];
if(y==fa)continue;
if(y==k[x][])lip[y]=lon[x][]+;
else lip[y]=lon[x][]+;
lip[y]=max(lip[y],lip[x]+);
st[y][]=x;
for(int i=;i<=;i++){
st[y][i]=st[st[y][i-]][i-];
}
if(k[x][]==y)maxx[y][]=lon[x][];
else maxx[y][]=lon[x][];
for(int i=;i<=;i++)maxx[y][i]=max(maxx[st[y][i-]][i-],maxx[y][i-]);
dfs2(y,x);
}
}
int get(int x,int y){
for(int i=;i>=;i--){
if(dep[st[x][i]]>dep[y])x=st[x][i];
}
if(st[x][]==y){
x1=x;
return st[x][];
}
if(dep[st[x][]]==dep[y])x=st[x][];
for(int i=;i>=;i--){
if(st[x][i]&&st[x][i]!=st[y][i])x=st[x][i],y=st[y][i];
}
x1=x,y1=y;
return st[x][];
}
void work(int x,int lca){
for(int i=;i>=;i--){
if(dep[st[x][i]]>dep[lca])sum=max(sum,maxx[x][i]),x=st[x][i];
}
}
int main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
scanf("%d",&n);
for(int i=,x,y;i<n;i++){
scanf("%d%d",&x,&y);
add(x,y),add(y,x);
}
dfs1(,);
dfs2(,);
scanf("%d",&m);
for(int i=,x,y;i<=m;i++){
scanf("%d%d",&x,&y);
if(x==y){
printf("%d\n",ans);
continue;
}
x1=y1=sum=;
if(dep[x]<dep[y])swap(x,y);
int lca=get(x,y);
if(lca==y){
work(x,lca);
sum=max(sum,lon[x][]);
if(k[lca][]==x1){
sum=max(sum,lon[lca][]);
}
else sum=max(sum,lon[lca][]);
sum=max(sum,lip[lca]);
}
else{
work(x,lca),work(y,lca);
sum=max(sum,max(lon[x][],lon[y][]));
if((k[lca][]==x1||k[lca][]==y1)&&(k[lca][]==x1||k[lca][]==y1)){
sum=max(sum,lon[lca][]);
}
else if(k[lca][]==x1||k[lca][]==y1){
sum=max(sum,lon[lca][]);
}
else sum=max(sum,lon[lca][]);
sum=max(sum,lip[lca]);
}
printf("%d\n",sum);
}
return ;
}
在这道题上死了一下午，一个是把询问点相邻的情况和自环的情况当成同类了，一个是直接输出直径相关的答案的时候没有考虑明白答案的定义。
感觉是和noip难度最接近的一套题…对不起，csp-s。不过大概率真正的考试题比这样的题要难吧。
没什么发挥余地，不爆炸就万幸了（笑）
csp-s2019爆零滚粗？