[关闭]
@2368860385 2018-12-19T13:08:06.000000Z 字数 5069 阅读 184

北京八十中集训——day2

比赛总结

考试过程：

预计：50+40=90
实际：50+40=90

T1：
50分比较好写，找了写性质，没想到什么更优秀的性质，于是打了一个搜索，一个dp，拍上了。继续想了会儿，没有想出正解。
T2：
看了题目后，没有什么思路，10分的比较好写，想先看T3回来再写。
T3：
看完后，感觉好像就是模拟在树上走一走，求最大值，感觉不像是这么简单，又想了会儿，没想到反例，就开始写了。写完后又写了暴力，没拍上，调了几个bug。最后发现一个bug是反向走的时候要判断是否走到点上，时间有点紧，有点紧张，没有想出怎么判。写了一个二分+倍增判段，还是拍不上。最后把暴力粘上，写上数据分治就交了。
暴力：30
有bug的算法：30
暴力+有bug的算法+数据分治：40（交的这份）
暴力+写错的二分+倍增判断是否走到点上：60（早知道就把写错的二分+倍增粘上了。。。）
数据好像有点水。。。

总结：
最后有点慌，思绪有点混乱，加上这道题本来就分类较多，细节较多，最后没调出。
时间分配
调试过程中：调出一个bug，多了新bug，导致一直拍不上。

T1

打完50分暴力，找了些性质，但是没有想出什么更优秀的方法。

整理后AC代码，题解在代码上方。

  1. /*
  2. 1、转化 
  3. 考虑每一列必定会出现两种颜色，而有一种颜色不会出现。
  4. 所以可以补集转化为一个长度为m的序列，每列的颜色是未出现的颜色。 
  5. 每四个方格都要有三种颜色=>这个序列中没有相邻的同色的。
  6. 此时问题就是求多少个这样的序列，相邻位置不同色，恰好出现M-R种red，M-G中green，M-B种blue。
  8. 2、
  9. 然后枚举第一个颜色是什么，分成三种情况讨论。
  10. 设第一种颜色为x，其余两种分别为y,z
  11. 此时x中颜色分别在x个不相邻的位置，可能会分成x个段，或者x-1个段，再次分情况讨论，设段数为g。
  13. 3、 
  14. 枚举长度为偶数的段数，设为e，那么这些段中，出现的yz的个数是一样的，（出现一个y必定有一个z）。
  15. 奇数段的开头可能是y，也可能是z，设oy是以y开头段数，oz是以z开头的段数
  16. 那么有
  17. 1、oy+oz=g-e ------ 奇数段和偶数段的和是分成的总段数g 
  18. 2、y(-e)-oy=z(-e)-oz ------ 同样，奇数段去掉开头后相当于一个偶数段（出现的yz的个数是一样的），那么yz各自去掉奇数段yz开头的颜色后，yz出现的颜色一样的。
  19. 可以求出oz,oy。
  21. 4、 
  22. 然后此时剩下的yz颜色（yz颜色表示yz一起出现）为 y-oy-e，设为r 
  23. ------ 总的y - 奇数段单独出现的y的个数 - 偶数段的开头的个数（偶数段的前两个位置必定一个y，后面也许还有许多yz）= 剩下的y（这些y中的每一个和一个z一起出现在奇数段后者偶数段）
  25. Finally： 
  26. 将这r段(yz颜色)在g段中选r个放上 --- C(g+r+1,r)
  27. 在这g段选e段为偶数段 --- C(g,e)
  28. 在这g-e段奇数段选oy段y开头 --- C(g-e,oy)
  29. 每个偶数段可以y开头，也可以z开头 --- 2^e 
  30. */
  31. #include<cstdio>
  32. #include<algorithm>
  33. #include<iostream>
  34. #include<cstring>
  35. #include<cmath>
  36. #include<cctype>
  37. #include<set>
  38. #include<map>
  39. #include<queue>
  40. #include<vector>
  41. using namespace std;
  42. typedef long long LL;
  44. inline int read() {
  45.     int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
  46.     for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
  47. }
  49. const int mod = 1e9 + 7;
  50. const int N = 1000000;
  51. int fac[N + 5], ifac[N + 5], mi[N + 5];
  53. int ksm(int a,int b) {
  54.     int res = 1;
  55.     while (b) {
  56.         if (b & 1) res = 1ll * res * a % mod;
  57.         a = 1ll * a * a % mod;
  58.         b >>= 1;
  59.     }
  60.     return res;
  61. }
  62. void init() {
  63.     fac[0] = 1; 
  64.     for (int i = 1; i <= N; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
  65.     ifac[N] = ksm(fac[N], mod - 2);
  66.     for (int i = N; i >= 1; --i) ifac[i - 1] = 1ll * ifac[i] * i % mod;
  67.     mi[0] = 1;
  68.     for (int i = 1; i <= N; ++i) mi[i] = 1ll * mi[i - 1] * 2 % mod;
  69. }
  70. int C(int n,int m) {
  71.     return 1ll * fac[n] * ifac[m] % mod * ifac[n - m] % mod;
  72. }
  73. int Calc(int n,int x,int y,int z) {
  74.     if (x <= 0) return 0;
  75.     LL ans = 0;
  76.     for (int g = x - 1; g <= x; ++g) {
  77.         if (g <= 0) continue;
  78.         for (int e = 0; e <= g; ++e) {
  79.             if ((g - e + y - z) & 1) continue;
  80.             int oy = (g - e + y - z) / 2;
  81.             int oz = g - e - oy;
  82.             if (oy < 0 || oz < 0) continue;
  83.             if (((y + z - e - g) < 0) || ((y + z - e - g) & 1)) continue;
  84.             int r = (y + z - e - g) / 2;
  85.             ans += 1ll * C(g + r - 1, r) * C(g, e) % mod * C(g - e, oy) % mod * mi[e] % mod;
  86.         }
  87.     }
  88.     return ans % mod;
  89. }
  90. int main() {
  91.     init();
  92.     int M = read(), R = read(), G = read(), B = read();
  93.     LL ans = 0;
  94.     R = M - R, G = M - G, B = M - B;
  95.     ans += 2 * Calc(M, R, G, B);
  96.     ans += 2 * Calc(M, G, B, R);
  97.     ans += 2 * Calc(M, B, R, G);
  98.     cout << ans % mod;
  99.     return 0;
  100. }

T2

本来想写10分的来着，去看T3了。

T3

首先求路径交。
然后分为两种情况：
1、在路径交上同向走，那么要求时间差<路径交的最大的边。
2、反向走，要求经过路径交的时间区间有交集，并且不能走到点上。

整理后AC代码：

  1. #include<cstdio>
  2. #include<algorithm>
  3. #include<cstring>
  4. #include<cmath>
  5. #include<iostream>
  6. #include<cctype>
  7. #include<set>
  8. #include<map>
  9. #include<queue>
  10. #include<vector>
  11. #define pa pair<LL,int>
  12. using namespace std;
  13. typedef long long LL;
  15. inline int read() {
  16.     int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
  17.     for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
  18. }
  20. const int N = 100005;
  21. const int Log = 21;
  22. struct Edge{
  23.     int to, nxt; LL w;
  24.     Edge() {}
  25.     Edge(int a,int b, LL c) { to = a, nxt = b, w = c; }
  26. }e[N << 1];
  27. int head[N], f[N][22], deth[N], fa[N], st[N], ed[N], En, Index;
  28. LL sum[N], g[N][22];
  29. int n;
  31. inline void add_edge(int u,int v, LL w) {
  32.     ++En; e[En] = Edge(v, head[u], w); head[u] = En;
  33.     ++En; e[En] = Edge(u, head[v], w); head[v] = En;
  34. }
  36. void dfs(int u) {
  37.     st[u] = ++Index;
  38.     deth[u] = deth[fa[u]] + 1;
  39.     for (int i = head[u]; i; i = e[i].nxt) {
  40.         int v = e[i].to;
  41.         if (v == fa[u]) continue;
  42.         f[v][0] = fa[v] = u; g[v][0] = e[i].w; sum[v] = sum[u] + e[i].w;
  43.         dfs(v);
  44.     }
  45.     ed[u] = Index;
  46. }
  47. inline int LCA(int u,int v) {
  48.     if (deth[u] < deth[v]) swap(u, v);
  49.     int d = deth[u] - deth[v];
  50.     for (int j = Log; j >= 0; --j) 
  51.         if (d & (1 << j)) u = f[u][j];
  52.     if (u == v) return u;
  53.     for (int j = Log; j >= 0; --j) 
  54.         if (f[u][j] != f[v][j]) u = f[u][j], v = f[v][j];
  55.     return f[u][0];
  56. }
  58. inline LL getRoad(int u,int v) {
  59.     int lca = LCA(u, v); 
  60.     return sum[u] + sum[v] - sum[lca] - sum[lca];
  61. }
  62. inline LL getmx(int u,int v) {
  63.     int lca = LCA(u, v); LL ans = 0;
  64.     for (int j = Log; j >= 0; --j) 
  65.         if (deth[f[u][j]] >= deth[lca]) ans = max(ans, g[u][j]), u = f[u][j]; 
  66.     for (int j = Log; j >= 0; --j) 
  67.         if (deth[f[v][j]] >= deth[lca]) ans = max(ans, g[v][j]), v = f[v][j]; 
  68.     return ans;
  69. }
  71. void Judge(int u,LL len) {  
  72.     for (int i = Log; i >= 0; --i) 
  73.         if (getRoad(u, f[u][i]) <= len) len -= getRoad(u, f[u][i]), u = f[u][i];
  74.     puts(len == 0 ? "NO" : "YES");
  75. }
  77. void solve() {
  78.     int u1 = read(), v1 = read(); LL t1; scanf("%lld", &t1); // 此处需开longlong 
  79.     int u2 = read(), v2 = read(); LL t2; scanf("%lld", &t2);
  81.     int lca = LCA(u2, v2), S, T;
  82.     int f1 = LCA(u1, u2), f2 = LCA(u1, v2);
  83.     int g1 = LCA(v1, u2), g2 = LCA(v1, v2);
  85.     // 求路径交，若没有，则相交于一点lca处 
  86.     if (st[u1] < st[lca] || st[u1] > ed[lca]) S = lca;
  87.     else S = deth[f1] > deth[f2] ? f1 : f2;
  88.     if (st[v1] < st[lca] || st[v1] > ed[lca]) T = lca;
  89.     else T = deth[g1] > deth[g2] ? g1 : g2;
  91.     bool fx = getRoad(u2, S) > getRoad(u2, T); // 方向 
  92.     t1 += getRoad(u1, S);
  93.     t2 += fx ? getRoad(u2, T) : getRoad(u2, S);
  95.     if (!fx) {
  96.         puts((abs(t1 - t2) < getmx(S, T)) ? "YES" : "NO");
  97.     }
  98.     else {
  99.         LL len = getRoad(S, T);
  100.         if (abs(t1 - t2) > len) { puts("NO"); return ; } // 经过路径的时间区间没有交集
  101.         len += t1 + t2; // uv从开始知道走完相交的路径所花的时间
  102.         if (len & 1) { puts("YES"); return ; }
  103.         len /= 2; int Mid = LCA(S, T); // len/2 相遇的时间 
  104.         if (getRoad(S, Mid) >= len - t1) Judge(S, len - t1);
  105.         else Judge(T, len - t2);
  106.     }
  107. }
  109. int main() {
  110.     n = read();int Q = read();
  111.     for (int i = 1; i < n; ++i) {
  112.         int u = read(), v = read(); LL w; scanf("%lld", &w);
  113.         add_edge(u, v, w);
  114.     }
  115.     dfs(1);
  116.     for (int j = 1; j <= Log; ++j) 
  117.         for (int i = 1; i <= n; ++i) {
  118.             f[i][j] = f[f[i][j - 1]][j - 1];
  119.             g[i][j] = max(g[i][j - 1], g[f[i][j - 1]][j - 1]);
  120.         }
  121.     while (Q--) solve();
  122.     return 0;
  123. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注