csp-s模拟100，101T1，T2题解

题面：https://www.cnblogs.com/Juve/articles/11799325.html

我太蒻了只会T1T2

组合：

欧拉路板子？不会呀。。。

然后打了个优化，防止暴栈

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<vector>
  6 using namespace std;
  7 inline int read(){
  8     int x=0,f=1;char ch=getchar();
  9     while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
 10     while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
 11     return x*f;
 12 }
 13 const int MAXN=4e5+5;
 14 int t,n,m,fa[MAXN],du[MAXN],edge,sta[MAXN<<1],top=0,deg[MAXN];
 15 int to[MAXN<<1],nxt[MAXN<<1],pre[MAXN],cnt=1,id[MAXN<<1];
 16 void add(int u,int v,int idd){
 17     ++cnt,to[cnt]=v,nxt[cnt]=pre[u],pre[u]=cnt,id[cnt]=idd;
 18 }
 19 int find(int x){
 20     return fa[x]=(fa[x]==x?x:find(fa[x]));
 21 }
 22 bool vis[MAXN<<1],visit[MAXN];
 23 void dfs1(int x,int edge){
 24     for(int i=pre[x];i;i=nxt[i]){
 25         if(vis[i]||vis[i^1]) continue;
 26         int y=to[i];
 27         vis[i]=vis[i^1]=1;
 28         pre[x]=i;
 29         dfs1(y,i);
 30         i=pre[x];
 31     }
 32     sta[++top]=edge;
 33 }
 34 void work1(){
 35     for(int i=1,u,v;i<=m;++i){
 36         u=read(),v=read();
 37         add(u,v,i),add(v,u,i);
 38         visit[u]=visit[v]=1;
 39         ++du[u],++du[v];
 40         fa[find(v)]=find(u);
 41     }
 42     int num=0,st=1,numm=0;
 43     for(int i=1;i<=n;++i){
 44         if(!visit[i]) continue;
 45         if(fa[i]==i) ++num;
 46         if(du[i]&1) st=i,++numm;
 47     }
 48     if(num>1||(numm!=2&&numm!=0)){
 49         puts("NO");
 50         return ;
 51     }
 52     dfs1(st,0);
 53     if(top!=m+1){
 54         puts("NO");
 55         return ;
 56     }
 57     puts("YES");
 58     while(top){
 59         if(sta[top]!=0){
 60             int p=sta[top];
 61             int q=p^1;
 62             if(p>q) printf("%d ",-id[p]);
 63             else printf("%d ",id[p]);
 64         }
 65         --top;
 66     }
 67     puts("");
 68 }
 69 void dfs2(int x,int edge){
 70     for(int i=pre[x];i;i=nxt[i]){
 71         if(vis[i]) continue;
 72         int y=to[i];
 73         vis[i]=1;
 74         pre[x]=i;
 75         dfs2(y,i);
 76         i=pre[x];
 77     }
 78     sta[++top]=edge;
 79 }
 80 void dfs(int x){
 81     visit[x]=1;
 82     for(int i=pre[x];i;i=nxt[i]){
 83         if(visit[to[i]]) continue;
 84         dfs(to[i]);
 85     }
 86 }
 87 void work2(){
 88     for(int i=1,u,v;i<=m;++i){
 89         u=read(),v=read();
 90         add(u,v,i);
 91         ++du[u],++deg[v];//出度，入度
 92     }
 93     int st=0,ed=0;
 94     for(int i=1;i<=n;++i){
 95         if(deg[i]==du[i]+1){
 96             if(!ed) ed=i;
 97             else{
 98                 puts("NO");
 99                 return ;
100             }
101         }
102         else if(deg[i]+1==du[i]){
103             if(!st) st=i;
104             else{
105                 puts("NO");
106                 return ;
107             }
108         }
109         else if(deg[i]!=du[i]){
110             puts("NO");
111             return ;
112         }
113     }
114     if(!st){
115         for(int i=1;i<=n;++i)
116             if(du[i]){
117                 st=i;
118                 break;
119             }
120     }
121     dfs(st);
122     for(int i=1;i<=n;++i)
123         if(!visit[i]&&deg[i]!=0){
124             puts("NO");
125             return ;
126         }
127     dfs2(st,0);
128     puts("YES");
129     while(top){
130         if(sta[top]!=0){
131             int p=sta[top];
132             printf("%d ",id[p]);
133         }
134         --top;
135     }
136     puts("");
137 }
138 signed main(){
139     freopen("merge.in","r",stdin);
140     freopen("merge.out","w",stdout);
141     t=read(),n=read(),m=read();
142     //cout<<t<<' '<<m<<' '<<n<<endl;
143     for(int i=1;i<=n;++i) fa[i]=i;
144     if(t==1) work1();
145     else work2();
146     return 0; 
147 }

View Code

对于一个点，如果它被排序了，那么以它构成的逆序对就全消失了，所以对于每个点在hash表中统计是否有贡献，没有就跳过

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define int long long 6 #define re register 7 using namespace std; 8 const int MAXN=2e5+5,mod=19260817; 9 int n,m,a[MAXN],ans=0,sta[MAXN],top=0; 10 bool vis[MAXN]; 11 int c[MAXN],f[MAXN]; 12 inline int lowbit(re int x){ 13 return x&-x; 14 } 15 inline void update(re int pos,re int val){ 16 for(re int i=pos;i<=n;i+=lowbit(i)){ 17 c[i]+=val; 18 } 19 } 20 inline int query(re int pos){ 21 re int res=0; 22 for(re int i=pos;i>0;i-=lowbit(i)){ 23 res+=c[i]; 24 } 25 return res; 26 } 27 struct hash_map{ 28 int head[mod+5],nxt[MAXN],val[MAXN],to[MAXN],tot; 29 int &operator [](int v){ 30 int x=v%mod; 31 for(int i=head[x];i;i=nxt[i]){ 32 if(to[i]==v) return val[i]; 33 } 34 to[++tot]=v,nxt[tot]=head[x],head[x]=tot; 35 return val[tot]=0; 36 } 37 }mp; 38 signed main(){ 39 freopen("count.in","r",stdin); 40 freopen("count.out","w",stdout); 41 scanf("%lld%lld",&n,&m); 42 for(re int i=1;i<=n;++i){ 43 scanf("%lld",&a[i]); 44 } 45 for(re int i=n;i>=1;--i){ 46 re int t=query(a[i]-1); 47 ans+=t; 48 f[i]=t; 49 update(a[i],1); 50 mp[i]=t; 51 } 52 printf("%lld ",ans); 53 for(re int i=1,p;i<=m;++i){ 54 scanf("%lld",&p); 55 if(!mp[p]){ 56 printf("%lld ",ans); 57 continue; 58 } 59 for(int j=p;j<=n;++j){ 60 if(!mp[j]) continue; 61 if(a[j]<=a[p]){ 62 mp[j]=0; 63 ans-=f[j]; 64 } 65 } 66 printf("%lld ",ans); 67 } 68 puts(""); 69 return 0; 70 }

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 int n,mp[20][20],x,y; 7 bool check(int h,int l,int val){ 8 int i=h,j=l,t=0; 9 while(i-1>0&&mp[i-1][j]==val) --i; 10 t+=h-i+1; 11 i=h; 12 while(i+1<=15&&mp[i+1][j]==val) ++i; 13 t+=i-h; 14 //cout<<t<<endl; 15 if(t>=5) return 1; 16 i=h,j=l,t=0; 17 while(j-1>0&&mp[i][j-1]==val) --j; 18 t+=l-j+1; 19 j=l; 20 while(j+1<=15&&mp[i][j+1]==val) ++j; 21 t+=j-l; 22 //cout<<t<<endl; 23 if(t>=5) return 1; 24 t=1,i=h,j=l; 25 while(i-1>0&&j+1<=15&&mp[i-1][j+1]==val) --i,++j,++t; 26 i=h,j=l; 27 while(i+1<=15&&j-1>0&&mp[i+1][j-1]==val) ++i,--j,++t; 28 //cout<<t<<endl; 29 if(t>=5) return 1; 30 t=1,i=h,j=l; 31 while(i-1>0&&j-1>0&&mp[i-1][j-1]==val) --i,--j,++t; 32 i=h,j=l; 33 while(i+1<=15&&j+1<=15&&mp[i+1][j+1]==val) ++i,++j,++t; 34 //cout<<t<<endl; 35 if(t>=5) return 1; 36 return 0; 37 } 38 int main(){ 39 freopen("five.in","r",stdin); 40 freopen("five.out","w",stdout); 41 scanf("%d",&n); 42 for(int i=1;i<=n;++i){ 43 scanf("%d%d",&x,&y); 44 mp[x][y]=(i&1)+1; 45 if(check(x,y,mp[x][y])){ 46 if(i&1) printf("A %d ",i); 47 else printf("B %d ",i); 48 return 0; 49 } 50 /*for(int j=1;j<=15;++j){ 51 for(int p=1;p<=15;++p){ 52 cout<<mp[j][p]<<' '; 53 } 54 cout<<endl; 55 }*/ 56 } 57 puts("Tie"); 58 return 0; 59 }

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define int long long using namespace std; const int MAXN=1e5+5,MAXM=1e6+5,inf=0x3f3f3f3f3f3f3f3f; int n,m,k,d,p[MAXN],ans=0; bool vis[MAXN],is[MAXN]; int to[MAXM<<1],nxt[MAXM<<1],pre[MAXN],val[MAXM<<1],cnt=0; void add(int u,int v,int w){ ++cnt,to[cnt]=v,nxt[cnt]=pre[u],pre[u]=cnt,val[cnt]=w; } priority_queue< pair<int,int> >q; priority_queue<int>dis[MAXN]; void dijkstra(){ for(int i=1;i<=n;++i){ if(!is[i]) dis[i].push(inf); else{ dis[i].push(0); q.push(make_pair(0,i)); } } while(!q.empty()){ int x=q.top().second; q.pop(); if(vis[x]) continue; vis[x]=1; for(int i=pre[x];i;i=nxt[i]){ int y=to[i]; if(dis[y].top()>dis[x].top()+val[i]){ dis[y].push(dis[x].top()+val[i]); while(dis[y].size()>d+1) dis[y].pop(); q.push(make_pair(-dis[y].top(),y)); } } } } signed main(){ freopen("maze.in","r",stdin); freopen("maze.out","w",stdout); scanf("%lld%lld%lld%lld",&n,&m,&k,&d); for(int i=1,u,v,w;i<=m;++i){ scanf("%lld%lld%lld",&u,&v,&w); add(u+1,v+1,w),add(v+1,u+1,w); } for(int i=1;i<=k;++i){ scanf("%lld",&p[i]); ++p[i],is[p[i]]=1; } dijkstra(); printf("%lld ",dis[1].top()==inf?-1:dis[1].top()); return 0; }

csp-s模拟100，101T1，T2题解

相关推荐