[关闭]
@RabbitHu 2017-09-04T14:44:10.000000Z 字数 3716 阅读 1494

DL24胡小兔--记一次极端悲催的模拟（模拟赛9）

作业

T1 挖矿(mining)

题目

【问题描述】
现在有 m+1 个星球，从左到右标号为 0 到 m，pf 最初在 0 号星球。
有 n 处矿体，第 i 处矿体有 ai 单位原矿，在第 bi 个星球上。 由于飞船使用的是老式的跳跃引擎，每次它只能从第 x 号星球移动到第 x+4 号星球或
x+7 号星球。每到一个星球，pf 会采走该星球上所有的原矿，求 pf 能采到的最大原矿数量。 注意，pf 不必最终到达 m 号星球。
【输入格式】
第一行 2 个整数 n，m。
接下来 n 行，每行 2 个整数 ai，bi。
【输出格式】 输出一行一个整数，表示要求的结果。
【输入样例】 3 13
100 4 10 7 1 11
【输出样例】 101
【样例提示】
第一次从 0 到 4，第二次从 4 到 11，总共采到 101 单位原矿。
【数据范围】
对于 20%的数据 n=1，m<=10^5
对于 40%的数据 n<=15，m<=10^5
对于 60%的数据 m<=10^5
对于 100%的数据 n<=10^5，m<=10^9，1<=ai<=10^4，1<=bi<=m

题解

首先用一个双队列打表可以发现：17以内有的数无法表示成若干个4与若干个7的和，大于等于18的数则都可以。

这道题可以考虑离散化：

将所有矿产读入后排序，从大至小枚举，维护一个队列存储当前矿产后面距离当前矿产不超过17的矿产DP值，用一个maxn记录距离超过17的矿产最大DP值。

每次处理新的矿产时，先将距离超过17的弹出队列（同时用它们的DP更新maxn），比较队列中能转移的所有DP值与maxn，取最大值即可。

T2 集合(multiset)

题目

【问题描述】
给定一个可重集合，一开始只有一个元素 0。然后你可以操作若干轮，每一 轮，你需要对于集合中的每个元素 x 进行如下三种操作之一:
1、将 x 变为 x+1。
2、将 x 分裂为两个非负整数 y,z，且满足 x=y+z。
3 、什么都不做。 每一轮，集合中的每个元素都必须进行上面三个操作之一。 对于一个最终的集合，你的任务是判断至少进行了多少轮。
【输入格式】
第一行为一个正整数 n，表示集合的最终大小。 第二行为 n 个非负整数，描述集合中的元素。
【输出格式】 输出一个非负整数，为最少的轮数。
【输入样例】 5
00033
【输出样例】 5

题解

我有一句……………………………………算了，不当讲。

从最终状态试图还原成初始状态（只有一个0），贪心考虑，每个时刻把0两两合并，把不是0的数都减1。

必要的优化：坚决不能直接给每个数都减1，一定要用原始值与当前时间比较……

T3 仓库(warehouse)

题目

【问题描述】
喵星系有 n 个星球，星球以及星球间的航线形成一棵树。
从星球 a 到星球 b 要花费[dis(a,b) Xor M]秒。(dis(a,b)表示 ab 间的航线长度，Xor
为位运算中的异或)
为了给仓库选址，pf 想知道，星球 i(1<=i<=n)到其它所有星球花费的时间之和。
第2页共3页
大连市第二十四中学 3 冲刺 Noip2017
【输入格式】
第一行包含两个正整数 n，M。
接下来 n-1 行，每行 3 个正整数 a,b,c，表示 a，b 之间的航线长度为 c。
【输出格式】
n 行，每行一个整数，表示星球 i 到其它所有星球花费的时间之和。
【输入样例】
4 0
1 2 1
1 3 2
1 4 3
【输出样例】
6
8
10
12
【数据范围】

保证答案不超过 2*10^9

题解

首先30分暴力可以用经典的转移来做。

2、3两个点可以写暴力的……我当时居然没看见？！

然后是正解！

可以发现由于 M <= 15，所有异或操作只涉及最后四位。

那么是否可以将后四位和前面其他位分开处理呢？前面的按照暴力的方法做，后面四位用cnt[i][j]记录到i距离后四位是j的点数、最后处理，可不可以呢？

可以！但要注意进位。

用ans[i]记录其他点到i的距离的前28位之和，cnt[i][j]记录到i距离后四位是j的点数。

则第一遍DFS处理的时候，设父亲是u、儿子是v、边权是w[e]:

对于ans，ans[u] 应包括：ans[v] + （v子树大小（不包括v本身））* (w[e] & 15)。

首先：

  1. ans[u] += ans[v] + w[e] & (-16); //有了ans[v] + 1 * w[e]

然后枚举j：

  1. ans[u] += ((j + w[e]) & (-16)) * cnt[v][j]; //这是进位！

对于cnt，不应考虑进位了（因为是后面四位）。

首先：

  1. cnt[u][w[e] & 15]++; // u->v这条边

然后枚举j：

  1. cnt[u][(j + w[e]) & 15] += cnt[v][j];

那么转移的时候怎么转移呢？

注意转移之前，ans[i]表示的是i的子树中所有点到i的距离和（去掉后面四位）。

首先，ans[v] 要加上 ans[u] - ans[v] （这个值相当于：除v的子树（不包括v）以外，其他所有点到父亲u的距离前四位之和， 再加上v的子树大小那么多条“多余的边”(u -> v)。）

那么我们再对v枚举j，去掉多余的(u -> v)：

  1. ans[v] -= ((j + w[e]) & (-16)) * cnt[v][j];

然后我们还要让 ans[v] 加上 v子树以外的点那么多条 边(u -> v)。

那么我们先对v枚举j，求出一个数组t[j]，表示 除了v子树（包括v）以外的节点中到u距离后四位为j的点的个数。

  1. t[(j + w[e]) & 15] = cnt[u][(j + w[e]) & 15] - cnt[v][j];

别忘了去掉v自己：

  1. t[w[e] & 15]--;

然后对u枚举j，利用t更新ans[v]。

  1. ans[v] += ((j + w[e]) & (-16)) * t[j];

ans更新完毕。

对于cnt，只需对u枚举j，也用t数组更新即可。

  1. cnt[v][(j + w[e]) & 15] += t[j];

AC代码：

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <iostream>
  6. #include <map>
  7. #include <queue>
  8. #define INF 0x3f3f3f3f
  9. #define NL putchar('\n')
  10. using namespace std;
  11. typedef long long ll;
  12. int read(){
  13.     char c; bool op = 0;
  14.     while((c = getchar()) < '0' || c > '9')
  15.         if(c == '-') op = 1;
  16.     int ret = c - '0';
  17.     while((c = getchar()) >= '0' && c <= '9')
  18.         ret = ret * 10 + c - '0';
  19.     return ret;
  20. }
  21. void write(int x){
  22.     if(x < 0) putchar('-'), x = -x;
  23.     if(x >= 10) write(x / 10);
  24.     putchar('0' + x % 10);
  25. }
  27. const int N = 100005;
  28. int n, M;
  29. int ecnt = 1, go[2 * N], nxt[2 * N], adj[N], w[2 * N];
  30. int ans[N];
  32. void add(int u, int v, int ww){
  33.     go[++ecnt] = v;
  34.     w[ecnt] = ww;
  35.     nxt[ecnt] = adj[u];
  36.     adj[u] = ecnt;
  37. }
  39. int cnt[N][16];
  40. const int all = 15, other = -16;
  42. void dfs2(int u, int pre){
  43.     int v;
  44.     for(int e = adj[u]; e; e = nxt[e]){
  45.         if((v = go[e]) == pre) continue;
  46.         dfs2(v, u);
  47.         ans[u] += ans[v] + (w[e] & other);
  48.         cnt[u][w[e] & all]++;
  49.         for(int j = 0; j < 16; j++){
  50.             ans[u] += ((j + w[e]) & other) * cnt[v][j];
  51.             cnt[u][(j + w[e]) & all] += cnt[v][j];
  52.         }
  53.     }
  54. }
  55. void change2(int u, int pre){
  56.     int v;
  57.     int t[16];
  58.     for(int e = adj[u]; e; e = nxt[e]){
  59.         if((v = go[e]) == pre) continue;
  60.         int tmp = ans[u] - ans[v];
  61.         for(int j = 0; j < 16; j++){
  62.             tmp -= ((j + w[e]) & other) * cnt[v][j];
  63.             t[(j + w[e]) & all] = cnt[u][(j + w[e]) & all] - cnt[v][j];
  64.         }
  65.         t[w[e] & all]--;
  66.         ans[v] += tmp;
  67.         cnt[v][w[e] & all]++;
  68.         for(int j = 0; j < 16; j++){
  69.             ans[v] += ((j + w[e]) & other) * t[j];
  70.             cnt[v][(j + w[e]) & all] += t[j];
  71.         }
  72.         change2(v, u);
  73.     }
  74. }
  76. int main(){
  78.     n = read(), M = read();
  79.     for(int i = 1; i < n; i++){
  80.         int u = read(), v = read(), ww = read();
  81.         add(u, v, ww);
  82.         add(v, u, ww);
  83.     }
  84.     dfs2(1, 0);
  85.     change2(1, 0);
  86.     for(int i = 1; i <= n; i++){
  87.         int res = ans[i];
  88.         for(int j = 0; j < 16; j++)
  89.             res += cnt[i][j] * (j ^ M);
  90.         write(res), NL;
  91.     }
  92.     return 0;
  93. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注