牛客月赛106（0/1最短路，树存最长链）

目次
        A. 末了DISCO
        D. 太阳系DISCO
        E. 平凡DISCO-1

---

 
 
 
 
A. 末了DISCO


        （1）pow(a, b) ：a ^ b
        （2）数据范围，爆long long。因此直接判 a ^ b 的奇偶，奇赋值 1 ，偶赋值 0
        （3）注意 b 大概为 0

1. #include<bits/stdc++.h>
2. #define LL long long
3. using namespace std;
5. LL a, b, c, d, n, ans;
7. int main()
8. {
9.         cin >> a >> b >> c >> d;
10.         LL t1 = 2;
11.         if (a % 2 != 0 || b == 0)
12.                 t1 = 1;
13.         ans = t1 * c + d;
14.         if (ans % 2 == 0)
15.                 cout << "NO";
16.         else
17.                 cout << "YES";
18.         return 0;
19. }

复制代码

 




D. 太阳系DISCO


        （1）标题实质为最短路，每次耗费均为 1，用 bfs 即可
        （2）逆时针走 y 步，即为顺时针走 n - y 步，题中规定 y < n，否则模前要 + n
        （3）每一个队首出队都有顺 / 逆两种选择，到达的两个点都入队
        （4）技能最多用一次，用两次便是没用。和不消技能作比力
        （5）技能在哪用都一样，那就选择体如今末了一次上

1. #include<bits/stdc++.h>
2. #define LL long long
3. using namespace std;
5. const int N = 2e5 + 5, INF = 0x3f3f3f3f;
6. int n, k, a, b, x, y, ans, dis[N];
7. queue <int> q;
9. int main()
10. {
11.         cin >> n >> k >> a >> b >> x >> y;
12.         memset(dis, 0x3f, sizeof(dis));
13.         q.push(a), dis[a] = 0;
14.         while (q.size())
15.         {
16.                 int p = q.front();
17.                 q.pop();
18.                 int e1 = (p + x) % n;
19.                 if (dis[e1] > dis[p] + 1)
20.                 {
21.                         dis[e1] = dis[p] + 1;
22.                         q.push(e1);
23.                 }
24.                 int e2 = (p + n - y) % n;
25.                 if (dis[e2] > dis[p] + 1)
26.                 {
27.                         dis[e2] = dis[p] + 1;
28.                         q.push(e2);
29.                 }
30.         }
31.         if (dis[b] == INF)
32.                 ans = -1;
33.         else
34.                 ans = dis[b];
35.         if (k)
36.                 ans = min(ans, dis[(b + n / 2) % n] + 1);
37.         cout << ans;
38.         return 0;
39. }

复制代码

 



E. 平凡DISCO-1


        （1）找树最深的一条链，把其叶子结点作为被换对象
        （2）该条链上每一个点作为父节点，撤消链上的下一个子节点外，其他的子节点作为根节点是的最大深度，找到最大的值，作为被换对象
        （3）son[] 数组里存的是最长链各节点值

1. #include<bits/stdc++.h>
2. #define LL long long
3. using namespace std;
5. const int N = 5e5 + 5, INF = 0x3f3f3f3f;
6. int n, ans, dep[N], son[N];
7. vector<int> G[N];
9. void dfs(int u, int fa)
10. {
11.         dep[u] = 1;
12.         for (int i = 0; i < G[u].size(); i ++)
13.         {
14.                 int v = G[u][i];
15.                 if (v != fa)
16.                 {
17.                         dfs(v, u);
18.                         dep[u] = max(dep[u], dep[v] + 1);
19.                         if (dep[v] > dep[son[u]])
20.                                 son[u] = v;
21.                 }
22.         }
23. }
25. void add(int u, int fa)
26. {
27.         for (int i = 0; i < G[u].size(); i ++)
28.         {
29.                 int v = G[u][i];
30.                 if (v != fa && v != son[u])
31.                         ans = max(ans, dep[v]);       
32.         }
33.         if (son[u])                        // 还没到最长链的叶子结点
34.                 add(son[u], u);
35. }
37. int main()
38. {
39.         cin >> n;
40.         for (int i = 1; i < n; i ++)
41.         {
42.                 int u, v;
43.                 cin >> u >> v;
44.                 G[u].push_back(v);
45.                 G[v].push_back(u);
46.         }
47.         dfs(1, 0);
48.         add(1, 0);
49.         cout << dep[1] + max(ans - 1, 0);
50.         return 0;
51. }

复制代码