A题，因为数据范围很小，所以只要暴力即可，如果能相遇一定范围不大，如果范围很大还没相遇一定是不会相遇的了。正解应当是用扩展欧几里得计算这个方程的整数解，再想办法看看有没有正整数解才是。

　　B题，只要看懂了题意，用map维护一下即可。真不知道题目给的n是干嘛用的。。

　　C题，如果不存在loop的情况就用np态判断一下即可。现在存在loop正向dfs是不可以的，因为dfs的顺序会对结果造成影响。那么采用倒着搜索的方式，如果某点是必败的，那么到达这个点的点必然是必胜的，如果当前点是必胜的，那么父亲节点的计数减1（每个点的计数初始化为这个点可以走的方法数），如果该父亲节点的计数点为0了，说明其子节点都是必胜点，该点为必败点。不论是必胜点还是必败点，在得出这个点的性质后需要入队继续搜索，那么自始至终没有入队的点就是loop点了。实现完以后可以发现这个方式和拓扑排序有点类似。代码如下：

1 #include 
      
        2 #define t_mid (l+r>>1) 3 #define ls (o<<1) 4 #define rs (o<<1|1) 5 #define lson ls,l,t_mid 6 #define rson rs,t_mid+1,r 7 using namespace std; 8 const int N = 7000 + 5; 9 typedef long long ll;10 typedef pair
       
         pii;11 //typedef pair
        
          pli;12 13 int n;14 vector
         
           s[2];15 bool vis[N][2];16 int deg[N][2];17 int dp[N][2];18 struct node19 {20     int pos, turn, ans; // 1 : win, 0 : lose21 };22 void bfs()23 {24     queue
          
            Q;25     Q.push((node){
    1, 0, 0});26     Q.push((node){
    1, 1, 0});27     dp[1][0] = dp[1][1] = 0;28     vis[1][0] = vis[1][1] = 1;29     for(int i=2;i<=n;i++) deg[i][0] = s[0].size();30     for(int i=2;i<=n;i++) deg[i][1] = s[1].size();31     while(!Q.empty())32     {33         node temp = Q.front(); Q.pop();34         int turn = temp.turn, pos = temp.pos, ans = temp.ans;35         int befturn = !turn;36         dp[pos][turn] = ans;37         if(ans == 0)38         {39             for(int step : s[befturn])40             {41                 int befpos = pos - step;42                 if(befpos <= 0) befpos += n;43                 if(!vis[befpos][befturn])44                 {45                     vis[befpos][befturn] = 1;46                     Q.push((node){befpos, befturn, 1});47                 }48             }49         }50         else51         {52             for(int step : s[befturn])53             {54                 int befpos = pos - step;55                 if(befpos <= 0) befpos += n;56                 if(--deg[befpos][befturn] == 0 && !vis[befpos][befturn])57                 {58                     vis[befpos][befturn] = 1;59                     Q.push((node){befpos, befturn, 0});60                 }61             }62         }63     }64 }65 66 int main()67 {68     cin >> n;69     int t; scanf("%d",&t);70     while(t--)71     {72         int x; scanf("%d", &x);73         s[0].push_back(x);74     }75     sort(s[0].begin(), s[0].end());76     scanf("%d",&t);77     while(t--)78     {79         int x; scanf("%d", &x);80         s[1].push_back(x);81     }82     bfs();83     for(int j=0;j<2;j++)84     {85         for(int i=2;i<=n;i++)86         {87             if(!vis[i][j]) printf("Loop ");88             else if(dp[i][j]) printf("Win ");89             else printf("Lose ");90         }91         puts("");92     }93     return 0;94 }
          
         
        
       
      

 

　　D题，1操作是u到v建边，2操作是u到[L, R]建边，3操作是[L, R]到u建边，1操作直接建边即可，2操作和3操作需要在线段树上建边，2操作需要在第一棵线段树上从父亲往子节点建权值为0的边，3操作在第二棵线段树上反过来即可。最后跑dij即可。需要注意的是，一棵线段树的空间是2N，因此总共的点数是N+2N*2=5N。要注意线段实际上是化为log个点再建边的。具体见代码：

1 #include 
      
         2 #define t_mid (l+r>>1)  3 #define ls (o<<1)  4 #define rs (o<<1|1)  5 #define lson ls,l,t_mid  6 #define rson rs,t_mid+1,r  7 using namespace std;  8 const int N = 1e5 + 5;  9 const int V = N * 5; 10 typedef long long ll; 11 typedef pair
       
         pii; 12 typedef pair
        
          pli; 13 const ll inf = 0x3f3f3f3f3f3f3f3f; 14  15 int n, m, s; 16 vector
         
           G[V]; 17 void addEdge(int u,int v,int w) 18 { 19     G[u].push_back(pii(v, w)); 20 } 21 int id[2][N<<2], idx; 22 void build(int o,int l,int r,int who) 23 { 24     id[who][o] = ++idx; 25     if(l == r) 26     { 27         if(who == 0) addEdge(id[who][o], l, 0); 28         else addEdge(l, id[who][o], 0); 29         return ; 30     } 31     build(lson, who); 32     build(rson, who); 33     if(who == 0) 34     { 35         addEdge(id[who][o], id[who][ls], 0); 36         addEdge(id[who][o], id[who][rs], 0); 37     } 38     else 39     { 40         addEdge(id[who][ls], id[who][o], 0); 41         addEdge(id[who][rs], id[who][o], 0); 42     } 43 } 44 vector
          
            vs; 45 void get(int o,int l,int r,int ql,int qr,int who) 46 { 47     if(l == ql && r == qr) 48     { 49         vs.push_back(id[who][o]); 50         return ; 51     } 52     if(qr <= t_mid) get(lson,ql,qr,who); 53     else if(ql > t_mid) get(rson,ql,qr,who); 54     else 55     { 56         get(lson,ql,t_mid,who); 57         get(rson,t_mid+1,qr,who); 58     } 59 } 60  61 ll d[V]; 62 void dij(int s) 63 { 64     memset(d,0x3f,sizeof d); 65     d[s] = 0; 66     priority_queue
           
            
             ,greater
             
               > Q; 67 Q.push(pli(0LL, s)); 68 while(!Q.empty()) 69 { 70 pli p = Q.top(); Q.pop(); 71 int u = p.second; 72 ll dis = p.first; 73 if(dis > d[u]) continue; 74 for(pii e : G[u]) 75 { 76 int v = e.first, w = e.second; 77 if(d[u] + w < d[v]) 78 { 79 d[v] = d[u] + w; 80 Q.push(pli(d[v], v)); 81 } 82 } 83 } 84 } 85 86 int main() 87 { 88 cin >> n >> m >> s; 89 idx = n; 90 build(1,1,n,0); 91 build(1,1,n,1); 92 while(m--) 93 { 94 int op; scanf("%d",&op); 95 if(op == 1) 96 { 97 int u, v, w; scanf("%d%d%d",&u,&v,&w); 98 addEdge(u, v, w); 99 }100 else101 {102 vs.clear();103 int u, l, r, w;104 scanf("%d%d%d%d",&u,&l,&r,&w);105 if(op == 2)106 {107 get(1,1,n,l,r,0);108 for(int v : vs) addEdge(u, v, w);109 }110 else111 {112 get(1,1,n,l,r,1);113 for(int v : vs) addEdge(v, u, w);114 }115 }116 }117 dij(s);118 for(int i=1;i<=n;i++)119 {120 if(d[i] == inf) d[i] = -1;121 printf("%I64d%c",d[i],i==n?'\n':' ');122 }123 return 0;124 }
             
            
           
          
         
        
       
      

 

　　E题，利用主席树可以在log的时间内找出一段不同的数的个数，那么对于一个k，不断的二分+主席树来找到最右边的数字个数不超过k的范围，这个复杂度是两个log，再考虑到k是从1到n，对一个k每次至少跳k个单位的距离，那么总共需要进行这个两个log的操作的次数是n/1+n/2+...+n/n = ln(n)。那么总的时间复杂度是nlogloglog，TLE。那么正确的做法是二分+主席树可以利用类似与在线段树上的树上二分操作优化成一个log，每次去寻找右边第一个个数超过k的位置并跳过去，那么最终的复杂度是nloglog，可A。要注意的是这里主席数的节点要从右往左插入。具体见代码：

1 #include 
      
        2 #define t_mid (l+r>>1) 3 //#define ls (o<<1) 4 //#define rs (o<<1|1) 5 //#define lson ls,l,t_mid 6 //#define rson rs,t_mid+1,r 7 using namespace std; 8 const int N = 1e5 + 5; 9 typedef long long ll;10 typedef pair
       
         pii;11 12 int pre[N],a[N],n,m,tot;13 int rt[N*40],sum[N*40],ls[N*40],rs[N*40];14 void build(int &o,int l,int r)15 {16     o = ++tot;17     sum[o] = 0;18     if(l == r) return ;19     build(ls[o],l,t_mid);20     build(rs[o],t_mid+1,r);21 }22 void update(int &o,int l,int r,int last,int pos,int dt)23 {24     o = ++tot;25     sum[o] = sum[last];26     ls[o] = ls[last];27     rs[o] = rs[last];28     if(l == r) {sum[o] += dt; return ;}29     if(pos <= t_mid) update(ls[o],l,t_mid,ls[last],pos,dt);30     else update(rs[o],t_mid+1,r,rs[last],pos,dt);31     sum[o] = sum[ls[o]] + sum[rs[o]];32 }33 int query(int o,int l,int r,int k) // return the first bu man zu de r34 {35     if(l == r) return l;36     int cnt = sum[ls[o]];37     if(cnt > k) return query(ls[o],l,t_mid,k);38     else return query(rs[o],t_mid+1,r,k-cnt);39 }40 int ans[N];41 42 int main()43 {44     cin >> n;45     memset(pre,-1,sizeof pre);46     for(int i=1;i<=n;i++) scanf("%d",a+i);47     build(rt[0],1,n+1); // a[n+1] = 0, but all the ai is >= 1, so is different one48     for(int i=n;i>=1;i--)49     {50         int now = a[i];51         if(pre[now] == -1)52         {53             update(rt[i],1,n+1,rt[i+1],i,1);54         }55         else56         {57             int temp;58             update(temp,1,n+1,rt[i+1],pre[now],-1);59             update(rt[i],1,n+1,temp,i,1);60         }61         pre[now] = i;62     }63     for(int k=1;k<=n;k++)64     {65         int L = 1, res = 0;66         while(L <= n)67         {68             int pos = query(rt[L],1,n+1,k);69             L = pos;70             res++;71         }72         ans[k] = res;73     }74     for(int i=1;i<=n;i++) printf("%d%c",ans[i],i==n?'\n':' ');75     return 0;76 }