T1 电压机制
把题目转化为找那些边只被奇数环包含。
这样的话直接$dfs$生成一棵树，给每个点附上一个深度，根据其他的非树边都是返祖边
可以算出环内边的数量$dep[x]-dep[y]+1$，然后判断
如果在统计时使用差分的思想，可以复杂度降到$O(n)$，也可以用$set$多一个$log$都能过
1 #include<bits/stdc++.h>
2 using namespace std;
3 namespace AE86{
4 inline int read(){
5 int x=0,f=1;char ch=getchar();
6 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
7 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
8 }inline void write(int x,char opt='\n'){
9 char ch[20];int len=0;if(x<0)x=~x+1,putchar('-');
10 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
11 for(int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);}
12 }using namespace AE86;
13 const int NN=4e5+5;
14 int n,m,ans,dep[NN],val[NN],huan;
15 struct SNOW{int to,next,cir;bool vis;}e[NN]; int head[NN],rp=1;
16 inline void add(int x,int y){e[++rp]=(SNOW){y,head[x]};head[x]=rp;}
17
18 inline void dfs(int x,int d){
19 dep[x]=d;
20 for(int i=head[x];i;i=e[i].next){
21 if(e[i].vis) continue;
22 e[i].vis=e[i^1].vis=1;
23 int y=e[i].to;
24 if(dep[y]){
25 int tmp=dep[x]-dep[y]+1;
26 if(tmp&1){
27 ++e[i].cir; ++e[i^1].cir;
28 --val[y]; ++huan;
29 }
30 else{
31 --e[i].cir; --e[i^1].cir;
32 ++val[y];
33 }
34 val[x]+=e[i].cir;
35 continue;
36 }
37 dfs(y,d+1);
38 e[i].cir=e[i^1].cir=val[y];
39 val[x]+=val[y];
40 }
41 }
42 namespace WSN{
43 inline short main(){
44 freopen("a.in","r",stdin);
45 freopen("a.out","w",stdout);
46 n=read(); m=read();
47 for(int i=1,u,v;i<=m;i++)
48 u=read(),v=read(),add(u,v),add(v,u);
49 dfs(1,1);
50 for(int i=2;i<=rp;i+=2) if(e[i].cir==huan) ++ans;
51 write(ans);
52 return 0;
53 }
54 }
55 signed main(){return WSN::main();}
View Code
T2 括号密码
咕咕咕
T3 排列
无限之环加强版，没什么好说的，$24$种情况特判就行，然后有两种特殊情况树状数组维护左右区间值即可
1 #include<bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 namespace AE86{
5 inline int read(){
6 int x=0,f=1;char ch=getchar();
7 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
8 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;
9 }inline void write(int x,char opt='\n'){
10 char ch[20];int len=0;if(x<0)x=~x+1,putchar('-');
11 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
12 for(int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);}
13 }using namespace AE86;
14 const int NN=3005;
15 int a1,a2,a3,a4,b[NN],n,ans,sum[NN][NN];
16 namespace Tree_array{
17 struct tree{
18 int tr[NN];
19 inline int lowbit(int x){return x&(-x);}
20 inline void update(int x,int v){for(int i=x;i<NN;i+=lowbit(i))tr[i]+=v;}
21 inline int query(int x,int res=0){for(int i=x;i;i-=lowbit(i))res+=tr[i];return res;}
22 }L,R;
23 }using namespace Tree_array;
24 inline int get(int l1,int r1,int l2,int r2){
25 return sum[r1][r2]-sum[l1-1][r2]-sum[r1][l2-1]+sum[l1-1][l2-1];
26 }
27 inline void spj1234(){
28 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]<b[j]) ans+=get(i+1,j-1,b[i]+1,b[j]-1)*get(j+1,n,b[j]+1,n);
29 }
30 inline void spj1243(){
31 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]<b[j]) ans+=get(i+1,j-1,b[j]+1,n)*get(1,i-1,1,b[i]-1);
32 }
33 inline void spj1324(){
34 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]>b[j]) ans+=get(1,i-1,1,b[j]-1)*get(j+1,n,b[i]+1,n);
35 }
36 inline void spj1342(){
37 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]>b[j]) ans+=get(1,i-1,1,b[j]-1)*get(i+1,j-1,b[i]+1,n);
38 }
39 inline void spj1423(){
40 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]>b[j]) ans+=get(1,i-1,1,b[j]-1)*get(j+1,n,b[j]+1,b[i]-1);
41 }
42 inline void spj1432(){
43 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]<b[j]) ans+=get(i+1,j-1,b[j]+1,n)*get(j+1,n,b[i]+1,b[j]-1);
44 }
45 inline void spj2134(){
46 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]<b[j]) ans+=get(i+1,j-1,1,b[i]-1)*get(j+1,n,b[j]+1,n);
47 }
48 inline void spj2143(){
49 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]<b[j]) ans+=get(i+1,j-1,1,b[i]-1)*get(j+1,n,b[i]+1,b[j]-1);
50 }
51 inline void spj2314(){
52 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]>b[j]) ans+=get(1,i-1,b[j]+1,b[i]-1)*get(j+1,n,b[i]+1,n);
53 }
54 inline void spj2341(){
55 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]<b[j]) ans+=get(i+1,j-1,b[i]+1,b[j]-1)*get(j+1,n,1,b[i]-1);
56 }
57 inline void spj2413(){
58 for(int i=4;i<=n;++i){
59 memset(L.tr,0,sizeof(L.tr));memset(R.tr,0,sizeof(R.tr));
60 int sum=0;
61 for(int j=1;j<i;j++) R.update(b[j],1);
62 for(int j=1;j<i;j++)
63 if(b[j]>b[i]) ans+=sum;
64 else{
65 sum+=R.query(b[j]-1);
66 sum-=L.query(n)-L.query(b[j]);
67 L.update(b[j],1); R.update(b[j],-1);
68 }
69 }
70 }
71 inline void spj2431(){
72 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]<b[j]) ans+=get(i+1,j-1,b[j]+1,n)*get(j+1,n,1,b[i]-1);
73 }
74 inline void spj3124(){
75 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]>b[j]) ans+=get(i+1,j-1,1,b[j]-1)*get(j+1,n,b[i]+1,n);
76 }
77 inline void spj3142(){
78 reverse(b+1,b+n+1);spj2413();
79 }
80 inline void spj3214(){
81 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]<b[j]) ans+=get(i+1,j-1,1,b[i]-1)*get(1,i-1,b[i]+1,b[j]-1);
82 }
83 inline void spj3241(){
84 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]<b[j]) ans+=get(1,i-1,b[i]+1,b[j]-1)*get(j+1,n,1,b[i]-1);
85 }
86 inline void spj3412(){
87 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]>b[j]) ans+=get(i+1,j-1,b[i]+1,n)*get(j+1,n,b[j]+1,b[i]-1);
88 }
89 inline void spj3421(){
90 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]>b[j]) ans+=get(i+1,j-1,b[i]+1,n)*get(j+1,n,1,b[j]-1);
91 }
92 inline void spj4123(){
93 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]>b[j]) ans+=get(i+1,j-1,1,b[j]-1)*get(j+1,n,b[j]+1,b[i]-1);
94 }
95 inline void spj4132(){
96 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]<b[j]) ans+=get(1,i-1,b[j]+1,n)*get(j+1,n,b[i]+1,b[j]-1);
97 }
98 inline void spj4213(){
99 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]<b[j]) ans+=get(1,i-1,b[j]+1,n)*get(i+1,j-1,1,b[i]-1);
100 }
101 inline void spj4231(){
102 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]<b[j]) ans+=get(1,i-1,b[j]+1,n)*get(j+1,n,1,b[i]-1);
103 }
104 inline void spj4312(){
105 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]>b[j]) ans+=get(1,i-1,b[i]+1,n)*get(j+1,n,b[j]+1,b[i]-1);
106 }
107 inline void spj4321(){
108 for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(b[i]>b[j]) ans+=get(1,i-1,b[i]+1,n)*get(j+1,n,1,b[j]-1);
109 }
110 namespace WSN{
111 inline short main(){
112 freopen("c.in","r",stdin);
113 freopen("c.out","w",stdout);
114 n=read(); a1=read(); a2=read(); a3=read(); a4=read();
115 for(int i=1;i<=n;i++) b[i]=read();for(int i=1;i<=n;i++) sum[i][b[i]]=1;
116 for(int i=1;i<=n;i++){
117 for(int j=1;j<=n;j++) sum[i][j]+=sum[i][j-1];
118 for(int j=1;j<=n;j++) sum[i][j]+=sum[i-1][j];
119 }
120 if(a1==1&&a2==2&&a3==3&&a4==4) spj1234();
121 if(a1==1&&a2==2&&a3==4&&a4==3) spj1243();
122 if(a1==1&&a2==3&&a3==2&&a4==4) spj1324();
123 if(a1==1&&a2==3&&a3==4&&a4==2) spj1342();
124 if(a1==1&&a2==4&&a3==2&&a4==3) spj1423();
125 if(a1==1&&a2==4&&a3==3&&a4==2) spj1432();
126 if(a1==2&&a2==1&&a3==3&&a4==4) spj2134();
127 if(a1==2&&a2==1&&a3==4&&a4==3) spj2143();
128 if(a1==2&&a2==3&&a3==1&&a4==4) spj2314();
129 if(a1==2&&a2==3&&a3==4&&a4==1) spj2341();
130 if(a1==2&&a2==4&&a3==1&&a4==3) spj2413();
131 if(a1==2&&a2==4&&a3==3&&a4==1) spj2431();
132 if(a1==3&&a2==1&&a3==2&&a4==4) spj3124();
133 if(a1==3&&a2==1&&a3==4&&a4==2) spj3142();
134 if(a1==3&&a2==2&&a3==1&&a4==4) spj3214();
135 if(a1==3&&a2==2&&a3==4&&a4==1) spj3241();
136 if(a1==3&&a2==4&&a3==1&&a4==2) spj3412();
137 if(a1==3&&a2==4&&a3==2&&a4==1) spj3421();
138 if(a1==4&&a2==1&&a3==2&&a4==3) spj4123();
139 if(a1==4&&a2==1&&a3==3&&a4==2) spj4132();
140 if(a1==4&&a2==2&&a3==1&&a4==3) spj4213();
141 if(a1==4&&a2==2&&a3==3&&a4==1) spj4231();
142 if(a1==4&&a2==3&&a3==1&&a4==2) spj4312();
143 if(a1==4&&a2==3&&a3==2&&a4==1) spj4321();
144 write(ans);
145 return 0;
146 }
147 }
148 signed main(){return WSN::main();}
View Code
T4 B关系
咕咕咕，神仙$dp$套$dp$