CodeForces 787 题解

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

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

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

 1 #include <bits/stdc++.h>
 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<int,int> pii;
11 //typedef pair<ll, int> pli;
12 
13 int n;
14 vector<int> s[2];
15 bool vis[N][2];
16 int deg[N][2];
17 int dp[N][2];
18 struct node
19 {
20     int pos, turn, ans; // 1 : win, 0 : lose
21 };
22 void bfs()
23 {
24     queue<node> 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         else
51         {
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 <bits/stdc++.h>
  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<int,int> pii;
 12 typedef pair<ll,int> pli;
 13 const ll inf = 0x3f3f3f3f3f3f3f3f;
 14 
 15 int n, m, s;
 16 vector<pii> 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<int> 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<pli,vector<pli>,greater<pli> > 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         else
101         {
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             else
111             {
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?'
':' ');
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 <bits/stdc++.h>
 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<int,int> 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 r
34 {
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 one
48     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         else
56         {
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?'
':' ');
75     return 0;
76 }