暂咕

$day1$

A. 位运算

---

分类讨论，贡献分离。

B. 集合论

---

维护类似时间戳的东西

C. 连连看

---

考场思路太局限了，考虑容斥。

我们可以看出两个方块能作出贡献，实际上是一个极大联通块(白块)所连节点，

然后我们就可以乱搞了

因为块会重复计算，容斥即可

有点懒，所以懒得细写了….

#include
#define int long long
#define MAXN 1101
using namespace std;
int read(){
char c=getchar();int ff=1;int x=0;
while(c<'0'||c>'9'){if(c=='-')ff=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();} return x*ff; } int dex[5]={-1,1,0,0}; int dey[5]={0,0,-1,1}; int a[MAXN][MAXN]; //int kt[4][MAXN*MAXN*2]; const int mod=23333333; /*struct node{ int head[mod];int tot=0;int nxt[mod];int to[mod];int val[mod]; int find(int x){ int me=x%mod; for(int i=head[me];i;i=nxt[i]){ if(to[i]==x){return val[i];} } return 0; } void init(){ for(int i=1;i<=tot;++i)nxt[i]=0; tot=0; } void insert(int x){ int me=x%mod; for(int i=head[me];i;i=nxt[i]){ if(to[i]==x){val[x]++;return ;} } tot++; to[tot]=x;head[me]=tot;val[tot]++; } void erase(int x){ int me=x%mod; for(int i=head[me];i;i=nxt[i]){ to[i]=0;val[i]=0; } head[me]=0; return ; } }T1,T2,T3;*/ int f[MAXN][MAXN][5]; int vis[MAXN][MAXN]; vector >v[MAXN*MAXN*2];int ans=0;
void work(int x){
if(!v[x].size())return ;
//printf("x=%lld\n",x);
mapT4,T1,T2,T3;
//kt[1][0]=0;kt[2][0]=0;kt[3][0]=0;
for(int i=0;i<v[x].size();++i){
int tox=v[x][i].first;int toy=v[x][i].second;
int k=1;for(k=1;k<=5;++k)if(f[tox][toy][k]==0)break;k--;
for(int j=1;j<=k;++j){
/*
ans+=T1.find(f[tox][toy][j]);
T1.insert(f[tox][toy][j]);
*/
ans+=T1[f[tox][toy][j]];
T1[f[tox][toy][j]]++;
//kt[1][++kt[1][0]]=f[tox][toy][j];
}
for(int j=1;j<=k;++j){
unsigned long long base=f[tox][toy][j];
for(int w=1;w<j;++w){
base=base*10000007ll+f[tox][toy][w];
/*
ans-=T2.find(base);
T2.insert(base);
kt[2][++kt[2][0]]=base;
*/
ans-=T2[base];
T2[base]++;
}
}
for(int j=1;j<=k;++j){
unsigned long long base=f[tox][toy][j];
for(int w=1;w<j;++w){
base=base*10000007ll+f[tox][toy][w];
for(int z=1;z<w;++z){
base=base*10000007ll+f[tox][toy][z];
/*
ans+=T3.find(base);
T3.insert(base);
*/

                ans+=T3\[base\];  
                T3\[base\]++;  
            //    kt\[3\]\[++kt\[3\]\[0\]\]=base;  
            }  
        }  
    }  
    if(k==4){  
        unsigned long long base=f\[tox\]\[toy\]\[4\]\*10000007ll;  
        base=f\[tox\]\[toy\]\[3\]+base\*10000007ll;  
        base=f\[tox\]\[toy\]\[2\]+base\*10000007ll;  
        base=base\*100000007ll+f\[tox\]\[toy\]\[1\];  
        ans-=T4\[base\];  
        T4\[base\]++;  
    }  
}  
/\*  
    for(int    i=1;i<=kt\[1\]\[0\];++i){T1.erase(kt\[1\]\[i\]);}  
    for(int    i=1;i<=kt\[2\]\[0\];++i){T2.erase(kt\[2\]\[i\]);}  
    for(int    i=1;i<=kt\[3\]\[0\];++i){T3.erase(kt\[3\]\[i\]);}  
    T1.init();T2.init();T3.init();  
\*/  

}
queue >q;int n,m;
void puss(int tox,int toy,int sum){
int j=0;
for(j=1;j<=4;++j){if(f[tox][toy][j]==0)break;} f[tox][toy][j]=sum; } int cnt=0; pairst[MAXN*MAXN];
void BFS(int x,int y){
int sss=0;
q.push(make_pair(x,y));vis[x][y]=1;
while(!q.empty()){
int mx=q.front().first;
int my=q.front().second;
q.pop();
for(int i=0;i<=3;++i){ int tox=mx+dex[i];int toy=my+dey[i]; if(tox<1||tox>n)continue;
if(toy<1||toy>m)continue;
if(a[tox][toy]==0&&vis[tox][toy]==0){
vis[tox][toy]=1;
q.push(make_pair(tox,toy));
}
else if(a[tox][toy]!=0&&vis[tox][toy]==0){
vis[tox][toy]=1;
st[++sss]=make_pair(tox,toy);
puss(tox,toy,cnt);
}
}
}
for(int i=1;i<=sss;++i){ int tox=st[i].first;int toy=st[i].second; vis[tox][toy]=0; } sss=0; } int look(int x1,int y1,int x2,int y2){ for(int i=1;i<=4;++i){ if(f[x1][y1][i]==0)continue; for(int j=1;j<=4;++j){ if(f[x2][y2][j]==0)continue; if(f[x1][y1][i]==f[x2][y2][j])return 0; } } return 1; } void QAQ(){ int sum=0; for(int i=1;i<=n;++i){ for(int j=1;j<=m;++j){ if(a[i][j]==0)continue; for(int k=0;k<=3;++k){ int tox=i+dex[k];int toy=j+dey[k]; if(tox<=0||tox>n)continue;
if(toy<=0||toy>m)continue;
if(a[i][j]!=a[tox][toy])continue;
sum+=look(i,j,tox,toy);
}
}
}
ans+=sum/2;
}
int mx=0;int k;
signed main(){
//freopen("link6.in","r",stdin);
n=read();m=read();k=read();
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j){
a[i][j]=read();
if(a[i][j]==0)continue;
v[a[i][j]].push_back(make_pair(i,j));
mx=max(a[i][j],mx);
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(!vis[i][j]&&a[i][j]==0){
cnt++;
BFS(i,j);
}
}
}
for(int i=1;i<=mx;++i){work(i);}
QAQ();
printf("%lld\n",ans);
}
/*
3 3 4
1 0 2
2 3 0
0 0 2
*/

$day2$

A. 串串香

---

$hash$即可

B. 糊涂图

---

还没改出来QAQ….

C. 木叶下

---

树上直径，再用上$lca$即可

我们维护若干数组

$dp_{i}$表示从$x$的父亲不经过$x$的最大路径

$g_{i,4}$表示$x$的几个长链的儿子

$gofa_{i}$表示向$fa$的最长路径

$dis$是对于$dp$的倍增数组

然后根据数组定义打就没了

#include
#define int long long
#define MAXN 210005
using namespace std;
int read(){
char c=getchar();int ff=1;int x=0;
while(c<'0'||c>'9'){if(c=='-')ff=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();} return x*ff; } int anss,diss[MAXN]; int dp[MAXN];//从x的父亲不经过x的最大路径 int fa[MAXN][25]; int dis[MAXN][25]; int g[MAXN][4];//从x到x的子树的最大路径 int son[MAXN][4]; int deep[MAXN]; int gofa[MAXN];//向fa走的最长路径 struct node{int to,n;}e[MAXN*2];int tot,head[MAXN]; void add(int u,int v){e[++tot].to=v;e[tot].n=head[u];head[u]=tot;} void pianfen(int x,int fa){ for(int i=head[x];i;i=e[i].n){ int to=e[i].to; if(to==fa)continue; pianfen(to,x); anss=max(anss,diss[x]+diss[to]+1); diss[x]=max(diss[to]+1,diss[x]); } } int n,m; void DP(int x,int fa){ priority_queue >q;
g[x][1]=1;
for(int i=head[x];i;i=e[i].n){
int to=e[i].to;
if(to==fa)continue;
DP(to,x);
q.push(make_pair(g[to][1]+1,to));
//printf("psg=%lld x=%lld to=%lld\n",g[to][1]+1,x,to);
}
int th=1;
while(!q.empty()){
g[x][th]=q.top().first;
son[x][th]=q.top().second;
q.pop();
//printf("g[%lld][%lld]=%lld %lld\n",x,th,g[x][th],son[x][th]);
th++;
if(th==4)break;
}
}
void DFS2(int x,int fa){
for(int i=head[x];i;i=e[i].n){
int to=e[i].to;
if(to==fa)continue;
if(son[x][1]!=to)dp[to]=max(1ll,g[x][1]);
else dp[to]=max(1ll,g[x][2]);
//printf("dp[%lld]=%lld\n",to,dp[to]);
DFS2(to,x);
}
}
void jia_swaproot(int x,int fa){
for(int i=head[x];i;i=e[i].n){
int to=e[i].to;
if(to==fa)continue;
gofa[to]=max(gofa[x]+1,dp[to]+1);
jia_swaproot(to,x);
}
}
void DFS(int x,int faa){
//printf("xxx=%lld\n",x);
for(int i=head[x];i;i=e[i].n){
int to=e[i].to;
if(to==faa)continue;
fa[to][0]=x;
deep[to]=deep[x]+1;
dis[to][0]=dp[to];
//printf("dis[%lld]=%lld\n",to,dis[to][0]);
for(int j=1;j<=19;++j){ if(fa[to][j-1]==0)break; fa[to][j]=fa[fa[to][j-1]][j-1]; dis[to][j]=max(dis[to][j-1],dis[fa[to][j-1]][j-1]); } DFS(to,x); } } int Lca(int x,int y){ int maxn=0; if(deep[x]=0;--i){
if(deep[fa[x][i]]>=deep[y]){
maxn=max(dis[x][i]-1,maxn);
//printf("maxn=%lld %lld\n",maxn,dis[x][i]);
x=fa[x][i];
}
}
if(x==y){
maxn=max(maxn,g[yuanx][1]-1);
maxn=max(gofa[x]-1,maxn);
//printf("go=%lld %lld\n",gofa[x]-1,x);
return maxn;
}
for(int i=19;i>=0;--i){
if(fa[x][i]!=fa[y][i]){
maxn=max(dis[x][i]-1,maxn);
maxn=max(dis[y][i]-1,maxn);
x=fa[x][i],y=fa[y][i];
}
}
int lca=fa[x][0];
for(int j=1;j<=3;++j){
if(son[lca][j]==x||son[lca][j]==y)continue;
maxn=max(maxn,g[lca][j]-1);
break;
}
maxn=max(maxn,gofa[lca]-1);
maxn=max(maxn,g[yuanx][1]-1);maxn=max(maxn,g[yuany][1]-1);
return maxn;
}
signed main(){
//freopen("myx.in","r",stdin);
//freopen("wwb.out","w",stdout);
n=read();
for(int i=1;i<=n-1;++i){
int u=read();int v=read();
add(u,v);add(v,u);
}
deep[1]=1;
pianfen(1,0);
DP(1,0);
DFS2(1,0);
jia_swaproot(1,0);
DFS(1,0);

anss++;  
if(anss%2==1)anss/=2,anss++;  
else anss/=2;

m=read();  
for(int i=1;i<=m;++i){  
    int u=read();int v=read();  
    if(u==v){  
        printf("%lld\\n",anss);  
        continue;  
    }  
    int ans=Lca(u,v);  
    printf("%lld\\n",ans);  
}  

}