1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #define LL long long 7 using namespace std; 8 const int mxn=1000; 9 bool vis[2001010];10 int main(){11     int x,y,b,d,l;12     scanf("%d%d%d%d",&x,&b,&y,&d);13     for(int i=0;i<=20000;i++){14         vis[b+i*x]=1;15     }16     for(int i=0;i<=20000;i++){17         if(vis[d+i*y]){18             printf("%d",d+i*y);19             return 0;20         }21     }22     printf("-1\n");23     return 0;24 }

 1 /*by SilverN*/ 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 const int mxn=100010; 9 int read(){10     int x=0,f=1;char ch=getchar();11     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}12     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}13     return x*f;14 }15 bool a[mxn],b[mxn];16 int n,m;17 int main(){18     int i,j,k,x;19     n=read();m=read();20     bool flag=0;21     for(i=1;i<=m;i++){22         flag=0;23         memset(a,0,sizeof a);24         memset(b,0,sizeof b);25         k=read();26         for(j=1;j<=k;j++){27             x=read();28             if(x<0){29                 if(b[-x])flag=1;30                 a[-x]=1;31             }32             else{33                 if(a[x])flag=1;34                 b[x]=1;35             }36         }37         if(!flag){38             printf("YES\n");39             return 0;40         }41     }42     printf("NO\n");43     return 0;44 }

 1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 #include<queue> 9 using namespace std;10 const int mxn=7010;11 int read(){12     int x=0,f=1;char ch=getchar();13     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}14     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}15     return x*f;16 }17 int a[2][mxn],f[2][mxn];18 int num[2];19 int vis[2][mxn];20 struct node{int u,p;};21 int n;22 queue<node>q;23 int main(){24     int i,j;25     n=read();26     num[0]=read();27     for(i=1;i<=num[0];i++)a[0][i]=read();28     num[1]=read();29     for(i=1;i<=num[1];i++)a[1][i]=read();30     //31     memset(f,-1,sizeof f);32     f[0][0]=f[1][0]=0;//在黑洞位置，必败态 33     q.push((node){0,0});34     q.push((node){1,0});//起始35     while(!q.empty()){36         node now=q.front();q.pop();37         int u=now.u,p=now.p;38         if(f[u][p]==0){//必败态 39             int v=u^1;//对手 40             for(i=1;i<=num[v];i++){41                 int np=(p-a[v][i]+n)%n;42                 if(f[v][np]==-1){43                     f[v][np]=1;44                     q.push((node){v,np});45                 }46             }47         }48         if(f[u][p]==1){//必胜态 49             int v=u^1;50             for(i=1;i<=num[v];i++){51                 int np=(p-a[v][i]+n)%n;52                 vis[v][np]++;53                 if(vis[v][np]==num[v] && f[v][np]==-1){54                     f[v][np]=0;55                     q.push((node){v,np});56                 }57             }58         }59     }60     for(i=0;i<=1;i++){61         for(j=1;j<n;j++){62             if(f[i][j]==-1)printf("Loop ");63             else if(f[i][j]==0)printf("Lose ");64                 else printf("Win ");65         }66         printf("\n");67     }68     return 0;69 }

  1 /*by SilverN*/  2 #include<algorithm>  3 #include<iostream>  4 #include<cstring>  5 #include<cstdio>  6 #include<cmath>  7 #include<queue>  8 #define LL long long  9 using namespace std; 10 const int INF=0x3f3f3f3f; 11 const int mxn=1500100; 12 LL read(){ 13     LL x=0,f=1;char ch=getchar(); 14     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 15     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 16     return x*f; 17 } 18 struct edge{int v,nxt,w;}e[mxn<<1]; 19 int hd[mxn],mct=0; 20 void add_edge(int u,int v,int w){ 21     e[++mct].v=v;e[mct].nxt=hd[u];e[mct].w=w;hd[u]=mct;return; 22 } 23 // 24 struct node{ 25     int v;LL dis; 26     friend bool operator < (node a,node c){return a.dis>c.dis;} 27 }; 28 priority_queue<node>q; 29 int n,m,S; 30 LL dis[mxn]; 31 inline void solve(int u,int v,int i){ 32     if(u==v)return; 33     if(dis[v]>dis[u]+e[i].w){ 34         dis[v]=dis[u]+e[i].w; 35         q.push((node){v,dis[v]}); 36     } 37     return; 38 } 39 void Dij(){ 40     memset(dis,0x3f,sizeof dis); 41     dis[S]=0; 42     q.push((node){S,0}); 43     int i,j; 44     while(!q.empty()){ 45         node now=q.top();q.pop(); 46         if(dis[now.v]<now.dis)continue; 47         int u=now.v; 48         for(i=hd[u];i;i=e[i].nxt){ 49             int v=e[i].v; 50             solve(u,v,i); 51         } 52     } 53     return; 54 } 55 // 56 int t[mxn<<1][2],cnt=0; 57 void Build(int l,int r,int rt,int tp){ 58     t[rt][tp]=++cnt; 59     if(l==r){ 60         if(!tp)add_edge(t[rt][tp],l,0); 61         else add_edge(l,t[rt][tp],0); 62         return; 63     } 64     int mid=(l+r)>>1; 65     Build(l,mid,rt<<1,tp);Build(mid+1,r,rt<<1|1,tp); 66     if(!tp){//正向  67         add_edge(t[rt][tp],t[rt<<1][tp],0); 68         add_edge(t[rt][tp],t[rt<<1|1][tp],0); 69     } 70     else{//反向  71         add_edge(t[rt<<1][tp],t[rt][tp],0); 72         add_edge(t[rt<<1|1][tp],t[rt][tp],0); 73     } 74     return; 75 } 76 vector<int>ve; 77 void update(int L,int R,int l,int r,int rt,int tp){ 78     if(L<=l && r<=R){ve.push_back(t[rt][tp]);return;} 79     int mid=(l+r)>>1; 80     if(L<=mid)update(L,R,l,mid,rt<<1,tp); 81     if(R>mid)update(L,R,mid+1,r,rt<<1|1,tp); 82     return; 83 } 84 int main(){ 85     int i,j,u,v,w,l,r,tp; 86     n=read();m=read();S=read(); 87     cnt=n+1; 88     Build(1,n,1,0); 89     Build(1,n,1,1); 90     for(i=1;i<=m;i++){ 91         tp=read(); 92         if(tp==1){ 93             u=read();v=read();w=read(); 94             add_edge(u,v,w); 95         } 96         else if(tp==2){ 97             u=read();l=read();r=read();w=read(); 98             ve.clear(); 99             update(l,r,1,n,1,0);100             for(j=0;j<ve.size();j++)101                 add_edge(u,ve[j],w);102         }103         else{104             v=read();l=read();r=read();w=read();105             ve.clear();106             update(l,r,1,n,1,1);107             for(j=0;j<ve.size();j++)108                 add_edge(ve[j],v,w);109         }110     }111     Dij();112     for(i=1;i<=n;i++)113         if(dis[i]>=4557430888798830300LL)printf("-1 ");114         else printf("%I64d ",dis[i]);115     return 0;116 }

 1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 using namespace std; 9 const int mxn=300010;10 int read(){11     int x=0,f=1;char ch=getchar();12     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}13     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}14     return x*f;15 }16 int n;17 int a[mxn];18 int pre[mxn],nxt[mxn],hd[mxn];19 int t[mxn];20 void add(int x,int v){21     if(!x)return;22     while(x<=n){t[x]+=v;x+=x&-x;}return;23 }24 int ask(int x){25     int res=0;26     for(int i=18;i>=0;i--){27         int p=res+(1<<i);28         if(p<=n && t[p]<x){29             x-=t[p];res=p;30         }31     }32     return res+1;33 }34 int f[mxn];35 vector<int>ve[mxn];36 int main(){37     int i,j;38     n=read();39     for(i=1;i<=n;i++){40         a[i]=read();41         pre[i]=hd[a[i]];42         hd[a[i]]=i;43     }44     for(i=1;i<=n;i++)nxt[pre[i]]=i,ve[1].push_back(i);45     for(i=1;i<=n;i++)if(!pre[i])add(i,1);46 //    for(i=1;i<=n;i++)printf("i:%d nxt:%d\n",i,nxt[i]);47     for(i=1;i<=n;i++){48         if(i>1)add(nxt[i-1],1);//记录上一个影响49         for(j=0;j<ve[i].size();j++){50 //            printf("solve:%d\n",ve[i][j]);51 //            printf("tot:%d\n",t[n]);52             int ne=ask(ve[i][j]+1);53 //            printf("ne:%d\n",ne);54             ve[ne].push_back(ve[i][j]);55             f[ve[i][j]]++;56         }57         add(i,-1);58     }59     for(i=1;i<=n;i++)printf("%d ",f[i]);60     return 0;61 }