T1 打地鼠
都切掉了的简单题
1 #include<bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 const int NN=2005;
5 int n,k,g[NN][NN],ans,sum[NN][NN];
6 char s[NN];
7 inline int calc(int x1,int y1,int x2,int y2){
8 return sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
9 }
10 namespace WSN{
11 inline short main(){
12 scanf("%lld%lld",&n,&k);
13 for(int i=1;i<=n;i++){
14 scanf("%s",s+1);
15 for(int j=1;j<=n;j++){
16 g[i][j]=s[j]-'0';
17 sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+g[i][j];
18 }
19 }
20 for(int i=1;i<=n-k+1;i++)
21 for(int j=1;j<=n-k+1;j++)
22 ans=max(ans,calc(i,j,i+k-1,j+k-1));
23 printf("%lld\n",ans);
24 return 0;
25 }
26 }
27 signed main(){return WSN::main();}
View Code
T2 竞赛图
首先把图中能够当作强联通图的部分缩点来看，
这样化简后的图，如果两个点之间只有一种方向的边，那么他们形成的子图是不合法的
转移的时候用强联通的子集更新非强联通的点集，枚举所有从强联通图出来的边，考虑记录当前枚举的点集合法与否即可
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int NN=25;
4 int T,n,ans,U,to[1<<24];
5 bool bin[1<<24];
6 namespace WSN{
7 inline short main(){
8 scanf("%d",&T);
9 while(T--){
10 memset(to,0,sizeof(to)); memset(bin,1,sizeof(bin));
11 scanf("%d",&n);ans=0;U=(1<<n)-1; to[0]=U;
12 for(int i=0;i<n;i++) for(int j=0,t;j<n;j++){scanf("%d",&t);if(t) to[1<<i]|=1<<j;}
13 for(int s=1,ss;s<=U;s++) ss=s&(-s),to[s]=to[s^ss]&to[ss];
14 for(int s=1;s<=U;s++) if(bin[s])
15 for(int i=to[s];i;i--,i&=to[s]) bin[s|i]=0;
16 for(int s=0;s<=U;s++) ans+=bin[s]; printf("%d\n",ans);
17 }
18 return 0;
19 }
20 }
21 signed main(){return WSN::main();}
View Code
T3 糖果
沽沽沽
T4 树
极其类似染色这道题，
我们可以在初始建树的时候给每个点附上一个自己的编号为点权
那么图中的点权范围是从一到$n$的
考虑每次修改操作将路径上的所有点赋值成一个大于$n$的新数，
这样我们可以发现每次对于黑边的查找，实质上是找路径上有几个点对点权不一样
线段树上维护一个$lc,rc,sum$分别表示区间首点权，区间尾点权，区间内黑色边数即可
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int NN=300001;
4 int n,q,du[NN];
5 int dfn[NN],rk[NN],son[NN],fa[NN],top[NN],siz[NN],dep[NN],cnt;
6 struct SNOW{int to,next;};SNOW e[NN<<1]; int head[NN],rp;
7
8 inline void add(int x,int y){e[++rp]=(SNOW){y,head[x]}; head[x]=rp;}
9 inline void dfs1(int f,int x){
10 fa[x]=f; dep[x]=dep[f]+1; siz[x]=1;
11 for(int i=head[x];i;i=e[i].next){
12 int y=e[i].to;if(y==f) continue;
13 dfs1(x,y);
14 siz[x]+=siz[y];
15 if(siz[son[x]]<siz[y]) son[x]=y;
16 }
17 }
18 inline void dfs2(int x,int t){
19 top[x]=t; dfn[x]=++cnt; rk[cnt]=x;
20 if(son[x]) dfs2(son[x],t);
21 for(int i=head[x];i;i=e[i].next){
22 int y=e[i].to;
23 if(y!=fa[x]&&y!=son[x]) dfs2(y,y);
24 }
25 }
26 struct SNOWtree{
27 #define lid (id<<1)
28 #define rid (id<<1|1)
29 int ll[NN<<2],rr[NN<<2],sm[NN<<2],laz[NN<<2];
30 int lc[NN<<2],rc[NN<<2];
31 inline void pushup(int id){
32 lc[id]=lc[lid]; rc[id]=rc[rid];
33 sm[id]=sm[lid]+sm[rid]+(lc[rid]!=rc[lid]);
34 }
35 inline void pushdown(int id){
36 if(laz[id]==-1 || ll[id]==rr[id]) return;
37 laz[lid]=laz[rid]=laz[id];
38 sm[lid]=sm[rid]=0;
39 lc[lid]=rc[lid]=laz[id];
40 lc[rid]=rc[rid]=laz[id];
41 laz[id]=-1;
42 }
43 inline void build(int id,int l,int r){
44 ll[id]=l; rr[id]=r; laz[id]=-1;
45 if(l==r){lc[id]=rc[id]=l;return;}
46 int mid=l+r>>1;
47 build(lid,l,mid); build(rid,mid+1,r);
48 pushup(id);
49 }
50 inline void change(int id,int l,int r,int v){
51 if(l<=ll[id]&&rr[id]<=r){lc[id]=rc[id]=laz[id]=v;sm[id]=0;return;}
52 pushdown(id); int mid=ll[id]+rr[id]>>1;
53 if(l<=mid) change(lid,l,r,v);
54 if(r>mid) change(rid,l,r,v);
55 pushup(id);
56 }
57 inline int query(int id,int l,int r){
58 if(l<=ll[id]&&rr[id]<=r) return sm[id];
59 pushdown(id); int mid=ll[id]+rr[id]>>1,ans=0;
60 if(r<=mid) return query(lid,l,r);
61 if(l>mid) return query(rid,l,r);
62 return query(lid,l,mid)+query(rid,mid+1,r)+(lc[rid]!=rc[lid]);
63 }
64 inline int look(int id,int pos){
65 if(ll[id]==rr[id]) return lc[id];
66 pushdown(id); int mid=ll[id]+rr[id]>>1;
67 if(pos<=mid) return look(lid,pos);
68 else return look(rid,pos);
69 }
70 }tr;
71 inline void update(int x,int y,int v){
72 while(top[x]!=top[y]){
73 if(dep[top[x]]<dep[top[y]]) swap(x,y);
74 tr.change(1,dfn[top[x]],dfn[x],v);
75 x=fa[top[x]];
76 }if(dfn[x]>dfn[y]) swap(x,y);
77 tr.change(1,dfn[x],dfn[y],v);
78 }
79 inline int query(int x,int y){
80 int sum=0;
81 while(top[x]!=top[y]){
82 if(dep[top[x]]<dep[top[y]]) swap(x,y);
83 sum+=tr.query(1,dfn[top[x]],dfn[x])+(tr.look(1,dfn[top[x]])!=tr.look(1,dfn[fa[top[x]]]));
84 x=fa[top[x]];
85 }if(dfn[x]>dfn[y]) swap(x,y);
86 sum+=tr.query(1,dfn[x],dfn[y]);
87 return sum;
88 }
89 namespace WSN{
90 inline short main(){
91 /* freopen("1.in","r",stdin);
92 freopen("1.out","w",stdout);*/
93 scanf("%d",&n);
94 for(int i=1,x,y;i<n;i++){
95 scanf("%d%d",&x,&y);
96 add(x,y); add(y,x);
97 }
98 int color=n; scanf("%d",&q);
99 dfs1(0,1); dfs2(1,1); tr.build(1,1,n);
100 while(q--){
101 int typ,x,y;scanf("%d%d%d",&typ,&x,&y);
102 if(typ==1){
103 update(x,y,++color);
104 /*for(int i=1;i<=n*4;i++) if(tr.ll[i]) cout<<tr.ll[i]<<" "<<tr.rr[i]<<" "<<tr.pr[i]<<" "<<tr.nx[i]<<" "<<tr.co[i]<<" "<<tr.laz[i]<<endl;*/
105 }
106 if(typ==2) printf("%d\n",query(x,y));
107 }
108 return 0;
109 }
110 }
111 signed main(){return WSN::main();}
View Code