Noip模拟63 2021.9.27(考场惊现无限之环)

T1 电压机制

把题目转化为找那些边只被奇数环包含。

这样的话直接$dfs$生成一棵树,给每个点附上一个深度,根据其他的非树边都是返祖边

可以算出环内边的数量$dep[x]-dep[y]+1$,然后判断

如果在统计时使用差分的思想,可以复杂度降到$O(n)$,也可以用$set$多一个$log$都能过

Noip模拟63 2021.9.27(考场惊现无限之环)
 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$种情况特判就行,然后有两种特殊情况树状数组维护左右区间值即可

Noip模拟63 2021.9.27(考场惊现无限之环)
  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$

上一篇:模拟62 考试总结


下一篇:okhttp android 使用教程