[关闭]
@wsndy-xx 2019-08-18T11:37:21.000000Z 字数 5183 阅读 940

Noip 2019 冲刺

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

三

from hzwer 模拟赛整理 2014-10-5 NOIP模拟赛
time 08.17
忘记做过多长时间了，应该不到 3h

T1 祖孙询问

已知一棵n个节点的有根树。有m个询问。每个询问给出了一对节点的编号x和y，询问x与y的祖孙关系。
对于30%的数据，n,m≤1000。
对于100%的.据,n,m≤40000，每个节点的编号都不超过40000。

算法分析：存在祖孙关系的话二者的 Lca 一定为其中之一， 求 Lca 判断即可

得分分析：放在一年以前，20min AC 不在话下，现在的码力确实大减啊。
这种难度的题目就是给我这种水平的选手提供的吧。

代码：

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <algorithm>
  6. #include <cstring>
  8. using namespace std;
  9. const int N = 5e4 + 10;
  11. #define gc getchar()
  12. inline int read() {
  13.     int x = 0, f = 1; char c = gc;
  14.     while(c < '0' || c > '9') {if(c == '-') f = -1; c = gc;}
  15.     while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc;
  16.     return x * f;
  17. }
  19. int head[N], now = 1;
  20. int n;
  21. struct Node {
  22.     int v, nxt;
  23. } G[N << 1];
  24. int fa[N], son[N], size[N], topp[N], deep[N];
  25. int root;
  27. void Add(int u, int v) {
  28.     G[now].v = v; G[now].nxt = head[u]; head[u] = now ++;
  29. }
  31. void Dfs1(int u, int f, int dep) {
  32.     fa[u] = f, deep[u] = dep; size[u] = 1;
  33.     for(int i = head[u]; ~ i; i = G[i].nxt) {
  34.         int v = G[i].v;
  35.         if(v != f) {
  36.             Dfs1(v, u, dep + 1);
  37.             size[u] += size[v];
  38.             if(size[son[u]] < size[v]) son[u] = v;
  39.         }
  40.     }
  41. }
  43. void Dfs2(int u, int tp) {
  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]) {
  50.             Dfs2(v, v);
  51.         }
  52.     }
  53. }
  55. int Lca(int x, int y) {
  56.     int tpx = topp[x], tpy = topp[y];
  57.     while(tpx != tpy) {
  58.         if(deep[tpx] < deep[tpy]) swap(x, y), swap(tpx, tpy);
  59.         x = fa[tpx];
  60.         tpx = topp[x];
  61.     }
  62.     if(deep[x] < deep[y]) swap(x, y);
  63.     return y;
  64. }
  66. int main() {
  67.     freopen("tree.in", "r", stdin);
  68.     freopen("tree.out", "w", stdout);
  70.     n = read();
  71.     for(int i = 1; i <= N - 5; i ++) head[i] = -1;
  72.     for(int i = 1; i <= n; i ++) {
  73.         int u = read(), v = read();
  74.         if(v == -1) root = u;
  75.         else Add(u, v), Add(v, u);
  76.     }
  78.     Dfs1(root, 0, 0);
  79.     Dfs2(root, root);
  81.     int q = read();
  82.     for( ; q; q --) {
  83.         int x = read(), y = read();
  84.         int lca = Lca(x, y);
  85.         if(lca == x) {
  86.             puts("1");
  87.         } else if(lca == y) {
  88.             puts("2");
  89.         } else {
  90.             puts("0");  
  91.         }
  92.     }
  94.     return 0;
  95. }

T2 比赛

【问题描述】
有两个队伍A和B，每个队伍都有n个人。这两支队伍之间进行n场1对1比赛，每一场都是由A中的一个选手与B中的一个选手对抗。同一个人不会参加多场比赛，每个人的对手都是随机而等概率的。例如A队有A1和A2两个人，B队有B1和B2两个人，那么(A1 vs B1,A2 vs B2)和(A1 vs B2,A2 vs B1)的概率都是均等的50%。
每个选手都有一个非负的实力值。如果实力值为X和Y的选手对抗，那么实力值较强的选手所在的队伍将会获得(X-Y)^2的得分。
求A的得分减B的得分的期望值。
【输入格式】
第一行一个数n表示两队的人数为n。
第二行n个数，第i个数A[i]表示队伍A的第i个人的实力值。
第三行n个数，第i个数B[i]表示队伍B的第i个人的实力值。
【输出格式】
输出仅包含一个实数表示A期望赢B多少分。答案保留到小数点后一位（注意精度）。
【样例输入】
2
3 7
1 5
【样例输出】
20.0
【数据规模】
对于30%的数据，n≤50。
对于100%的.据,n≤50000;A[i],B[i]≤50000

算法分析：根据期望的和=和的期望，只需把A队每个人的期望得分减去B队每个人的期望得分即为答案。
两个人相遇的概率为 (1/n),
假设固定 B 的选手不动，对 A 进行排列会存在 (n!) 种情况，其中 A 的选手 a 与 B 的选手 b 相遇的情况有 (n - 1) ! 种，所以相遇的概率为 (1/n)
对于贡献，排序后可以线性算出，lower_bound 也可以，只不过算价值时复杂度带 log，不过无所谓啦。

得分分析：这道题一开始想的是暴力枚举所有的情况然后计算，不过部分分不允许这样做，后来想到了正解的做法，只不过两者相遇的概率想错了，后来‘偷了’两份大样例然后乱试一番找到了正确的概率，写了出来，不过卡精度这种事虽然经常听说但是我还是第一次遇到。。。

代码：

  1. #include <iostream>
  2. #include <string>
  3. #include <cstdio>
  4. #include <cmath>
  5. #include <algorithm>
  6. #include <cstdlib>
  8. using namespace std;
  9. const int N = 5e4 + 10;
  11. double a[N], b[N];
  12. int n;
  13. double f[N], sum[N], sumf[N];
  15. int main() {
  16.     freopen("mat.in", "r", stdin);
  17.     freopen("mat.out", "w", stdout);
  18.     scanf("%d", &n);
  19.     for(int i = 1; i <= n; i ++) scanf("%lf", &a[i]);
  20.     for(int i = 1; i <= n; i ++) scanf("%lf", &b[i]);
  21.     sort(a + 1, a + n + 1);
  22.     sort(b + 1, b + n + 1);
  23.     for(int i = 1; i <= n; i ++) f[i] = b[i] * b[i];
  24.     for(int i = 1; i <= n; i ++) sumf[i] = sumf[i - 1] + f[i];
  25.     for(int i = 1; i <= n; i ++) sum[i] = sum[i - 1] + b[i];
  26.     double Ansa = 0;
  27.     for(int i = 1; i <= n; i ++) {
  28.         int wei = lower_bound(b, b + n + 1, a[i]) - b;
  29.         wei --;
  30.         if(wei < 1) continue;
  31.         double js = (double) wei;
  32.         Ansa += (js * a[i] * a[i] - 2 * sum[wei] * a[i] + sumf[wei]);
  33.     }
  34.     for(int i = 1; i <= n; i ++) f[i] = a[i] * a[i];
  35.     for(int i = 1; i <= n; i ++) sumf[i] = sumf[i - 1] + f[i];
  36.     for(int i = 1; i <= n; i ++) sum[i] = sum[i - 1] + a[i];
  37.     double Ansb = 0;
  38.     for(int i = 1; i <= n; i ++) {
  39.         int wei = lower_bound(a, a + n + 1, b[i]) - a;
  40.         wei --;
  41.         if(wei < 1) continue;
  42.         double js = (double) wei;
  43.         Ansb += (js * b[i] * b[i] - 2 * sum[wei] * b[i] + sumf[wei]);
  44.     }
  46.     double nn = n * 1.0;
  47.     double Answer = (Ansa - Ansb) / nn;
  49.     printf("%.1lf", Answer);
  51.     return 0;
  52. }

T3 数字

【问题描述】
一个数字被称为好数字当他满足下列条件：
1. 它有2*n个数位，n是正整数(允许有前导0)。
2. 构成它的每个数字都在给定的数字集合S中。
3. 它前n位之和与后n位之和相等或者它奇数位之和与偶数位之和相等
例如对于n=2,S={1,2}，合法的好数字有1111,1122,1212,1221,2112,2121,2211,2222这样8种。
已知n，求合法的好数字的个数mod 999983。
【输入格式】
第一行一个数n。
接下来一个长度不超过10的字符串，表示给定的数字集合。
【输出格式】
一行一个数字表示合法的好数字的个数mod 999983。
【样例输入】
2
0987654321
【样例输出】
1240
【数据规模】
对于20%的数据，n≤7。
对于100%的.据,n≤1000,|S|≤10。

算法分析：
ANS=前n位之和与后n位之和相等的方案数+奇数位之和与偶数位之和相等的方案数-前n位之和与后n位之和相等且奇数位之和与偶数位之和相等的方案数
前2个需要+的方案数都很好求，直接递推，重点是最后一个要满足2个条件的方案数怎么求，其实也很简单：
因为前n位之和=后n位之和，奇数位之和=偶数位之和
所以前n位中奇数位之和=后n位中偶数位之和 且
前n位中偶数位之和=后n位中奇数位之和
现在只要求上面这个问题的方案数，由于两个等式中的元素无交集，也是十分好算的。

得分分析：这题不给暴力分我怎么得分呢？

代码：

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <iomanip>
  4. #include <functional>
  5. #include <fstream>
  6. #include <cstring>
  7. #include <cstdio>
  8. #include <cstdlib>
  10. using namespace std;
  12. const int maxn = 1000 + 50;
  13. const int maxsum = 10000 + 50;
  14. const int mo = 999983;
  16. ifstream fin("num.in");
  17. ofstream fout("num.out");
  19. int f[maxn][maxsum] = {0};
  20. int n;
  21. bool canuse[10] = {0};
  22. int maxvalue = 0;
  23. long long ans = 0;
  25. void ReadData() {
  26.     fin >> n;
  27.     char c;
  28.     while (fin >> c) {
  29.         canuse[c - '0'] = true;
  30.         maxvalue = max(maxvalue, c - '0');
  31.     }
  32. }
  34. void DP() {
  35.     f[0][0] = 1;
  36.     for (int i = 0; i <= maxvalue; i++) {
  37.         if (canuse[i]) {
  38.             f[1][i] = 1;
  39.         }
  40.     }
  41.     for (int i = 1; i < n; i++) {
  42.         for (int j = 0; j <= maxvalue * i; j++) {
  43.             for (int k = 0; k <= maxvalue; k++) {
  44.                 if (canuse[k]) {
  45.                     f[i + 1][j + k] += f[i][j];
  46.                     f[i + 1][j + k] %= mo;
  47.                 }
  48.             }
  49.         }
  50.     }
  51. }
  53. inline long long sqr(long long X) {
  54.     return X * X;
  55. }
  57. void CalcAns() {
  58.     for (int i = 0; i <= maxvalue * n; i++) {
  59.         ans += 2 * sqr(f[n][i]);
  60.         ans %= mo;
  61.     }
  62.     int a = int(n / 2.0 - 1e-8) + 1;
  63.     int b = n >> 1;
  64.     long long A = 0;
  65.     long long B = 0;
  66.     for (int i = 0; i <= maxvalue * a; i++) {
  67.         A += sqr(f[a][i]);
  68.         A %= mo;
  69.     }
  70.     for (int i = 0; i <= maxvalue * b; i++) {
  71.         B += sqr(f[b][i]);
  72.         B %= mo;
  73.     }
  74.     ans = (ans + mo - A * B % mo) % mo;
  75. }
  77. int main() {
  78.     ReadData();
  79.     DP();
  80.     CalcAns();
  81.     fout << ans << endl;
  82.     return 0;
  83. }

总结：个人感觉这套题目的难度比较接近 Noip2018 Day1 （noip2019 没了， upset）。不过对于第三题的评价个人无法完成。
对于 T2 如果有大样例，并且不存在卡精度的数据的话可以在 90min 内解决这道题目，但是这题卡精度能得多少分这就只能看命了。
20min + 90min + 0min = 110min 的时间内得到 100 + 60（应该是100啊） + 0 = 160分 的成绩。水平有限。

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