[关闭]
@wsndy-xx 2019-08-14T07:51:56.000000Z 字数 4416 阅读 683

Noip 2019 冲刺

多做几套模拟题，体会心路历程。

一

time 8.13

这套题的三道题不是同一时间做的，毕竟也没有机会创造 3.5 h。

T1 选择区间

输入 m 个区间 [x, y]，你希望从中选择尽量多的区间，使得两两不相交，也不能有公共端点。
其中 m <= 100000, x,y <= 1e9

算法分析
from mjt
对区间端点离散化后直接 n*logn 的 dp

from lyq
考虑不离散化的做法，直接对区间进行二分是错误的，错误也非常明显，无论怎么排序，然而对于一个区间 q，如果 q 完全包含于区间 p，显然 p 是无用的。因此首先将无用区间剔除，就可以非常简单的二分得到想要的。

得分分析
我可以在20分钟内实现一个70分的做法，同样有信心在 2h 内解决这道题
如果放在一年前同样不知道是否可以用更短的时间解决这道题，因为这道题涉及自己最不擅长的 dp

代码

  1. #include <bits/stdc++.h>
  3. using namespace std;
  4. const int N = 101000;
  6. struct Node {
  7.     int l, r;
  8.     bool notuse;
  9. } A[N];
  10. int f[N];
  11. int maxn[N];
  12. Node B[N];
  13. int js;
  15. bool Cmp(Node a, Node b) {
  16.     if(a.l == b.l) return a.r < b.r;
  17.     return a.l < b.l;
  18. }
  19. int n;
  21. int Find(int R, int x) {
  22.     int l = 1, r = R, Ans = 1;
  23.     while(l <= r) {
  24.         int mid = (l + r) >> 1;
  25.         if(A[mid].r < x) Ans = mid, l = mid + 1;
  26.         else r = mid - 1;
  27.     }
  28.     return Ans;
  29. }
  31. int main() {
  32.     cin >> n;
  33.     for(int i = 1; i <= n; i ++) cin >> A[i].l >> A[i].r;
  34.     sort(A + 1, A + n + 1, Cmp);
  35.     int l = 1; 
  36.     for(int i = 1; i <= n; i ++)
  37.         for(int j = i + 1; j <= n; j ++)
  38.             if(A[j].l > A[i].l && A[j].r < A[i].r) {
  39.                 A[i].notuse = 1;
  40.                 break;
  41.             }
  42.     for(int i = 1; i <= n; i ++) if(A[i].notuse == 0) B[++ js] = A[i];
  43.     n = js;
  44.     for(int i = 1; i <= n; i ++) A[i] = B[i];
  45.     for(int i = 1; i <= n; i ++) {
  46.         if(i == 1) {
  47.             maxn[i] = 1;
  48.             f[1] = 1; continue;
  49.         }
  50.         int wei = Find(i - 1, A[i].l);
  51.         if(A[wei].r < A[i].l) {
  52.             f[i] = maxn[wei] + 1;
  53.             maxn[i] = max(maxn[i - 1], f[i]);   
  54.         } else {
  55.             f[i] = 1;
  56.             maxn[i] = max(maxn[i - 1], 1);
  57.         }
  58.     }
  59.     int ans = 0;
  60.     for(int i = 1; i <= n; i ++) ans = max(ans, f[i]);
  61.     cout << ans;
  62.     return 0;
  63. }

T2 纲举目张

输入一棵n个点的树，每条边的长度是1，
一共q次询问，每次询问k个点，
B君希望在树上保留最少的边，使得询问给出的k个点是连通的。
输出最小的边数
其中 1<=n<=1e5,1<=q<=1e5,2<=k<=4

算法分析
对于 k=2 的数据直接输出树上两点间的距离。
对于全体数据
对任意两点之间从树上抽离出区间路径，然后类似线段求交统计答案
显然区间路径的建立是依靠树链剖分来实现的。
时间复杂度 q * logn * logn * C(不大的常数)？？
特别注意的是边权向点权的转化，一直没想到。

得分分析
可以在 20 分钟内拿下 30 分
可以在 2h 内解决这道题
不过要是放在一年前，感觉自己会非常快的想到这道题自己的正解，并且在 1.5h 甚至 1h 就可以实现这道题的正解，毕竟这种树上路径抽离的题目自己以前接触过。岁月不饶人，放在现在是不会那么快的就想到了。

代码

  1. #include <bits/stdc++.h>
  3. using namespace std;
  4. const int N = 1e5 + 10;
  6. #define gc getchar()
  7. inline int read() {
  8.     int x = 0; char c = gc;
  9.     while(c < '0' || c > '9') c = gc;
  10.     while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc;
  11.     return x;
  12. }
  14. int now = 1, n, q;
  15. int head[N];
  16. struct Node {
  17.     int v, nxt;
  18. } G[N << 1];
  20. void Add(int u, int v) {
  21.     G[now].v = v, G[now].nxt = head[u]; head[u] = now ++;
  22. }
  24. int son[N], size[N], topp[N], deep[N], fa[N];
  25. int tree[N], tjs;
  26. int a[10];
  28. void Dfs1(int u, int f, int dep) {
  29.     deep[u] = dep;
  30.     size[u] = 1;
  31.     fa[u] = f;
  32.     for(int i = head[u]; ~ i; i = G[i].nxt) {
  33.         int v = G[i].v;
  34.         if(v != fa[u]) {
  35.             Dfs1(v, u, dep + 1);
  36.             size[u] += size[v];
  37.             if(size[son[u]] < size[v]) son[u] = v;
  38.         }
  39.     }
  40. }
  42. void Dfs2(int u, int tp) {
  43.     tree[u] = ++ tjs;
  44.     topp[u] = tp;
  45.     if(!son[u]) return ;
  46.     Dfs2(son[u], tp);
  47.     for(int i = head[u]; ~ i; i = G[i].nxt) {
  48.         int v = G[i].v;
  49.         if(v != fa[u] && v != son[u]) Dfs2(v, v);
  50.     }
  51. }
  53. struct Seg {
  54.     int l, r;
  55. } seg[N * 4];
  56. int segjs;
  58. void Lca(int x, int y) {
  59.     if(x == y) return ;
  60.     int tp1 = topp[x], tp2 = topp[y];
  61.     while(tp1 != tp2) {
  62.         if(deep[tp1] < deep[tp2]) swap(x, y), swap(tp1, tp2);
  63.         seg[++ segjs].l = tree[tp1], seg[segjs].r = tree[x];
  64.         x = fa[tp1];
  66.         tp1 = topp[x];
  67.     }
  68.     if(tree[x] == tree[y]) return ;
  69.     if(tree[x] < tree[y]) swap(x, y);
  70.     seg[++ segjs].l = tree[y] + 1;
  71.     seg[segjs].r = tree[x];
  72. }
  74. bool Cmp(Seg a, Seg b) {
  75.     if(a.l == b.l) return a.r < b.r;
  76.     else return a.l < b.l;
  77. }
  79. Seg A[N * 4];
  80. int ansjs;
  82. int main() {
  83.     n = read();
  84.     for(int i = 1; i <= n; i ++) head[i] = -1;
  85.     for(int i = 1; i <= n - 1; i ++) {
  86.         int u = read(), v = read();
  87.         Add(u, v), Add(v, u);
  88.     }
  89.     Dfs1(1, 0, 0);
  90.     Dfs2(1, 1);
  91.     q = read();
  92.     for(; q; q --) {
  93.         int s = read();
  94.         segjs = 0;
  95.         for(int i = 1; i <= s; i ++) a[i] = read();
  96.         for(int i = 1; i <= s; i ++) {
  97.             for(int j = i + 1; j <= s; j ++) {
  98.                 Lca(a[i], a[j]);
  99.             }
  100.         }
  101.         if(segjs == 0) {
  102.             cout << 0 << "\n";
  103.             continue;
  104.         }
  105.         sort(seg + 1, seg + segjs + 1, Cmp);
  106.         ansjs = 1;
  107.         A[1].l = seg[1].l, A[1].r = seg[1].r;
  108.         for(int i = 2; i <= segjs; i ++) {
  109.             if(seg[i].l <= seg[i - 1].r) {
  110.                 A[ansjs].r = max(A[ansjs].r, seg[i].r);
  111.             } else {
  112.                 ansjs ++;
  113.                 A[ansjs].l = seg[i].l, A[ansjs].r = seg[i].r;
  114.             }
  115.         }
  116.         int ans = 0;
  117.         for(int i = 1; i <= ansjs; i ++) {
  118.             if(A[i].l == A[i].r && A[i].l == 0) continue;
  119.             ans += A[i].r - A[i].l + 1;
  120.         }
  121.         cout << ans << "\n";
  122.     }
  123.     return 0;
  124. }

T3 区间选择

输入 m 个区间，你希望从中选择尽量多的区间，使得两两不相交，也不能有公共端点。
假设输入的区间的 xi 和 yi 是 1 到 n 之间的整数，输入的区间不能有重复的。
输入的区间是没有顺序的（即输入[1,1] [2, 2] 和输入[2,2] [1, 1] 算作一种方案）
问有多少种选择这 m 个区间的方式，使得原问题的解，答案为 l 。
因为方案数很大，输出对 10007 取模的结果即可。
其中 n <= 50

得分分析：
鄙人只会 30 分暴力，现在的水平调试了 1h
啊！ 真笨。
不过有早就该收获的新收获。

代码

  1. #include <bits/stdc++.h>
  3. using namespace std;
  4. const int N = 1e5 + 10;
  6. int n, m, l_;
  7. struct Node {
  8.     int l, r;
  9. } a[N];
  10. int js;
  11. bool vis[N];
  12. int ans;
  14. Node b[N];
  15. int tot;
  17. bool Cmp(Node aa, Node bb) {
  18.     if(aa.l == bb.l) {
  19.         return aa.r < bb.r;
  20.     }
  21.     return aa.l < bb.l;
  22. }
  24. int f[N];
  26. bool Check() {
  27.     tot = 0;
  28.     for(int i = 1; i <= js; i ++) {
  29.         if(vis[i] == 1) {
  30.             b[++ tot] = a[i];
  31.         }
  32.     }
  33.     sort(b + 1, b + tot + 1, Cmp);
  34.     for(int i = 1; i <= tot; i ++) f[i] = 1;
  35.     for(int i = 2; i <= tot; i ++) {
  36.         for(int j = 1; j < i; j ++) {
  37.             if(b[i].l > b[j].r) {
  38.                 f[i] = max(f[i], f[j] + 1);
  39.             }
  40.         }
  41.     }
  42.     int seg = 0;
  43.     for(int i = 1; i <= tot; i ++) seg = max(seg, f[i]);
  44.     if(seg == l_) return 1; 
  45.     return 0;
  46. }
  48. void Dfs(int x, int step) {
  49.     if(step == m) {
  50.         if(Check()) ans ++;
  51.         return ;
  52.     }
  53.     int i = x + 1;
  54.     if(i == js + 1) return ;
  55.     vis[i] = 1;
  56.     Dfs(i, step + 1);
  57.     vis[i] = 0;
  58.     Dfs(i, step);
  59. }
  61. int main() {
  62.     cin >> n >> m >> l_;
  63.     for(int i = 1; i <= n; i ++) {
  64.         for(int j = i; j <= n; j ++) {
  65.             a[++ js].l = i;
  66.             a[js].r = j;
  67.         }
  68.     }
  69.     Dfs(0, 0);
  70.     cout << ans;    
  71.     return 0;
  72. }

总结：如果只写暴力可以在 20min + 20min + 60min = 100min 得到 70 + 30 + 30 = 130 分。
稍加思考可以在 120min + 30min + 60min = 3.5h 得到 100 + 30 + 30 = 160 分
目前的能力极限： 100 + 100 + 30 = 230 分
总体来说，个人认为难度 > noip2018 Day1

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注