2021.04.28

训练地址

B. Bananas in a Microwave

题意：一开始的时候手里的数是0
这个题一开始想复杂了. 其实很简单. 我们想一个性质，我们用背包dp做这个题，从大到小枚举体积 j. 然后状态转移是从前往后推（不是之前的那个找前驱状态）.那么，我们对体积做变换（就是两个操作）。如果所得的体积之前已经出现过，就 break。这样子并不会影响。因为如果 $v_1 \rightarrow v_2 \rightarrow v_3$ ，如果从 $v_1$ 到 $v_2$ 的时候，发现 $v_2$ 已经搜索过（但是不是当前种类的操作转移的），那么 $v_3$ 仍然可以被更新答案。因为在搜索 $v_2$ 的时候， $v_3$ 的状态就可以搜索到.

#include<bits/stdc++.h>
using namespace std;
const int N = 210, M = 100010;
typedef long long ll;
int f[M];
int main()
{memset(f, -1, sizeof f);int n, m;scanf("%d%d", &n, &m);f[0] = 0;for(int i = 1; i <= n; i++){ll op, x, y;scanf("%lld%lld%lld", &op, &x, &y);for(ll j = m; j >= 0; j--){if(f[j] == -1) continue;ll z = j;for(ll k = 1; k <= y; k++){if(op == 1) z = (z * 100000 + x + 100000 - 1) / 100000;else z = (z * x + 100000 - 1) / 100000;if(z > m) break;if(f[z] != -1) break;f[z] = i;}}}for(int i = 1; i <= m; i++){printf("%d%c", f[i], i == m ? '\n' : ' ');}return 0;
}

C. Two Houses

将此题改编一下：有一张竞赛图，告诉每个点的入度，问是否存在两个点 $A$ 和 $B$ ，使得 $A$ 可以到 B 且 B 可以到 A. 并且使得 $∣ d in [A] - d in [B] ∣$ 最大。
我们按照入度从小到大排序，那么强连通分量的块一定是依次排列的。这个可以画画图，用反证法证明。
我们这样找块与块之间的分界线：假设枚举到第 $i$ 个起点，如果 $i$ 和 $i + 1$ 之间的分界线上的边全是指向右边的，那么这个分界线就是两个强连通块的分界线。而这个等价于：前 i 个点的出度之和 - 前 i 个点内部的出度之和 $i * (i - 1) /2$ = 分界线上的边的数量 $i * (n - i)$
有一个地方需要注意，就是答案无解的时候，不等价于 ans = 0. 因为可以某个点的数量不少于两个的强连通分量中的入度都是一样的。
因此判断那个地方要加上 $i! = l a s t$ .

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
const int N = 510;
typedef pair<ll, ll> P;
P din[N];
int main()
{ll n;scanf("%lld", &n);for(int i = 1; i <= n; i++){scanf("%lld", &din[i].x);din[i].y = i;}sort(din + 1, din + n + 1);ll sum = 0, sum2 = 0;int last = 1, A, B;ll ans = -1;for(ll i = 1; i <= n; i++){sum += n - din[i].x - 1;sum2 += din[i].x;if(sum == (i - 1) * i / 2 + i * (n - i)){if(i != last && ans < din[i].x - din[last].x){A = din[last].y, B = din[i].y;ans = din[i].x - din[last].x;}last = i + 1;}}if(ans == -1){printf("! 0 0\n");}else{printf("! %d %d\n", A, B);}return 0;
}

D. Christmas Game

在这里插入图片描述

对于确定的根节点，记 $d^{'} = d e pt h / k$ 。只有d’是奇数的时候才会有用。因为如果一个人把若干硬币从偶数点转移到了奇数点，那么这个人可以做重复的操作，把相同数量的硬币再移动到偶数点。那么，这就像一个Nim台阶游戏，只不过由若干相互独立的台阶组成。因此我们对每一个台阶，奇数位置的数字异或起来，然后把所有台阶再异或起来，如果不为0，先手赢，如果为0，先手输.
那么，我们可以跑一个树形dp，记录下来每个点离根节点距离为 $\mod 2k$ 的点权异或和，存在 $d p (u, k)$ 里面. 先跑一遍dfs记录下来以当前节点为子树的dp数组，然后再跑一遍树形dp，计算出父结点的最终答案后，把子节点所在子树扣掉，然后父结点剩余子树对子结点答案的贡献，计算答案。

#include<bits/stdc++.h>
using namespace std;
const int N = 100010, K = 50, M = 200010;
vector<int> a(N), win(N);
int dp[N][K];
int n, k2, k;
int h[N], e[M], ne[M], idx;
void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u, int fa)
{dp[u][0] = a[u];for(int i = h[u]; i != -1; i = ne[i]){int v = e[i];if(v == fa) continue;dfs(v, u);for(int i = 1; i < k2; i++) dp[u][i] ^= dp[v][i - 1];dp[u][0] ^= dp[v][k2 - 1];}
}
void dfs2(int u, int fa, vector<int>& my_xor)
{vector<int> final_xor(K);//my_xor 是从父结点传递过来，是除去当前u所在子树，fa以及其它子树的结果.for(int i = 1; i < k2; i++){final_xor[i] = my_xor[i - 1] ^ dp[u][i];}final_xor[0] = my_xor[k2 - 1] ^ dp[u][0];int res = 0;//注意这里是从k开始，千万别弄错. 因为我们只需要计算 depth / k 为奇数的情况for(int i = k; i < k2; i++) res ^= final_xor[i];win[u] = (res != 0);for(int i = h[u]; i != -1; i = ne[i]){int v = e[i];if(v == fa) continue;auto xor_send = final_xor;//把当前u的最终结果除去以v为根节点的子树for(int i = 1; i < k2; i++){xor_send[i] ^= dp[v][i - 1];}xor_send[0] ^= dp[v][k2 - 1];dfs2(v, u, xor_send);}
}
int main()
{scanf("%d%d", &n, &k);k2 = 2 * k;memset(h, -1, sizeof h);for(int i = 1; i < n; i++){int a, b;scanf("%d%d", &a, &b);add(a, b), add(b, a);}for(int i = 1; i <= n; i++) scanf("%d", &a[i]);dfs(1, -1);vector<int> tmp(K);for(int i = 0; i < K; i++) tmp[i] = 0;dfs2(1, -1, tmp);for(int i = 1; i <= n; i++){printf("%d%c", win[i] ? 1 : 0, i == n ? '\n' : ' ');}return 0;
}

F. Playlist

题意：
其实这个题，一开始想的是需要模拟出来这个过程（其实这个题和 2020 ec-final 的热身赛第一题的题意有点像），但是我们会发现，有一个很麻烦的问题，就是如果直接用链表模拟这个过程，可能会超时。
但是，我们发现一个性质，我们在循环枚举的时候，只有每次当这个数紧跟的数字被删掉的时候，才会对后续的数字有影响。那么，我们可以用一个队列来维护有那些数字的后面紧跟的数字被删掉了。

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N], ne[N];
bool st[N];
int main()
{int T;scanf("%d", &T);while(T--){int n;scanf("%d", &n);fill(st, st + n + 1, 0);queue<int> que;vector<int> ans;for(int i = 1; i <= n; i++){scanf("%d", &a[i]);ne[i] = i + 1;que.push(i);}ne[n] = 1;while(que.size()){int id = que.front(); que.pop();int nxt = ne[id];if(!st[id] && __gcd(a[id], a[nxt]) == 1){ans.push_back(nxt);st[nxt] = true;ne[id] = ne[nxt];que.push(id);}}printf("%d ", (int)ans.size());for(auto p : ans){printf("%d ", p);}printf("\n");}return 0;
}

G. Skyline Photo

题意：
首先思考这个，我们定义 $d p [i]$ 为从 $1$ ~ $i$ 的区间集合的最优方案的值。那么，我们可以从 $1$ ~ $i - 1$ 枚举最右边的划分边界是什么，即分成 $i$ ~ $j - 1$ 即 $dp_{j-1}$ ，以及从 $j$ 到 $i$ 作为一个区间的方案。
实际上，我们可以发现，当我们枚举到 $i$ 的时候，我们只需要找到左边第一个比 $h_i$ 小的元素 $h_j$ ，把 $i$ 加到和 $j$ 同一个区间里面去，更新答案， $dp_i = dp_jj$ 。那么我们就是枚举从 $j$ 又到 $i$ 左侧的分界线，而这之间的元素一定是大于 $h_i$ ，即 $dp_i = \max\{dp_{k-1}+b_i, dp_i\}$ ， $\le k \le i$ . 这可以用一个线段树维护最大值.
因为我们之前计算的 $dp_j$ 已经是 $1... j$ 的最优解。因此可以这样做。

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 300010;
struct node
{int l, r;ll maxv;
}tr[N * 4];
int n;
ll dp[N], h[N], b[N], stk[N];
void pushup(int u)
{tr[u].maxv = max(tr[2 * u].maxv, tr[2 * u + 1].maxv);
}
void build(int u, int l, int r)
{tr[u] = {l, r};if(l == r) {tr[u].maxv = -1e18;return;}int mid = (l + r) / 2;build(2 * u, l, mid), build(2 * u + 1, mid + 1, r);pushup(u);
}
void modify(int u, int x, ll v)
{if(tr[u].l == x && tr[u].r == x) {tr[u].maxv = v;}else{int mid = (tr[u].l + tr[u].r) / 2;if(x <= mid) modify(2 * u, x, v);else modify(2 * u + 1, x, v);pushup(u);}
}
ll query(int u, int l, int r)
{if(l <= tr[u].l && tr[u].r <= r){return tr[u].maxv;}int mid = (tr[u].l + tr[u].r) / 2;ll v = -1e18;if(l <= mid) v = max(v, query(2 * u, l, r));if(r > mid) v = max(v, query(2 * u + 1, l, r));return v;
}
int main()
{scanf("%d", &n);for(int i = 1; i <= n; i++){scanf("%lld", &h[i]);}for(int i = 1; i <= n; i++){scanf("%lld", &b[i]);}build(1, 1, n);int tt = 0;for(int i = 1; i <= n; i++){while(tt && h[stk[tt]] >= h[i]) tt--;int j = stk[tt];//这个地方一定要写成数组下标，不要写成数组元素！stk[++tt] = i;if(j){dp[i] = dp[j];ll v = query(1, j, i - 1);dp[i] = max(dp[i], v + b[i]);}else{dp[i] = b[i];if(i != 1){ll v = query(1, 1, i - 1);dp[i] = max(dp[i], v + b[i]);}}modify(1, i, dp[i]);}printf("%lld\n", dp[n]);return 0;
}

H. Useful Edges

在这里插入图片描述

思路：

我们固定了起点u，有很多终点 v，那么对于每一条边 (a, b)，想知道 b 离最近的终点 v 的距离. 那么可以转化为多源最短路问题，起点就是所有的 v，跑一遍 dijkstra，建立一个超级源点 S，然后向每一个终点 v 连边，边权是 $l_i$ . 因为 dijkstra 不能有负权边，那么把每个边加上一个很大的数字就可以了.

#include<bits/stdc++.h>
using namespace std;
const int N = 610;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;
ll dist[N][N], g[N][N], qs[N][N], d[N];
bool ok[N][N], st[N];
int n, m;
void dijkstra(int u)
{memset(d, 0x3f, sizeof d);memset(st, false, sizeof st);ll tmp = 1e9;for(int j = 1; j <= n; j++){if(qs[u][j]) d[j] = tmp - qs[u][j];}for(int i = 1; i <= n; i++){int t = -1;for(int j = 1; j <= n; j++){if(!st[j] && (t == -1 || d[t] > d[j])) t = j;}st[t] = true;for(int j = 1; j <= n; j++){d[j] = min(d[j], d[t] + g[t][j]);}}for(int i = 1; i <= n; i++) if(d[i] != INF) d[i] -= tmp;
}
int main()
{scanf("%d%d", &n, &m);memset(g, 0x3f, sizeof g);memset(dist, 0x3f, sizeof dist);//这个地方一定把自环初始化为0. 原因在于如果后面的qs中的u可能和某条边的端点重合//如果不初始化为0的话，那么 dist[i][i] 就不为0，就会使得答案变小. for(int i = 1; i <= n; i++) g[i][i] = dist[i][i] = 0;for(int i = 0; i < m; i++){int a, b, w;scanf("%d%d%d", &a, &b, &w);g[a][b] = g[b][a] = w;dist[a][b] = dist[b][a] = w;}for(int k = 1; k <= n; k++){for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);}}}int q;scanf("%d", &q);while(q--){int a, b, c;scanf("%d%d%d", &a, &b, &c);qs[a][b] = qs[b][a] = c;}for(int u = 1; u <= n; u++){dijkstra(u);for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){if(dist[u][i] == INF || g[i][j] == INF || d[j] == INF) continue;ok[i][j] |= (dist[u][i] + g[i][j] + d[j] <= 0);}}}int ans = 0;for(int i = 1; i <= n; i++){for(int j = i + 1; j <= n; j++){ans += ok[i][j];}}printf("%d\n", ans);
}

当然这个题还可以这么想，原图中所有边都变成之前的相反数，现在加入一条边 $(u, v, l)$ ，问是否存在一条经过 $(u, v)$ 的环，并且路径长度为非负的. 这样子的话，环上的每条边都是合法的，并且每条边两个端点在新图上的距离都是不小于 $g (i, j)$ 的。
因此我们就转化为求最长路的问题。
回忆 Floyd 的原理，第一层的 k 是枚举中转节点，并且 Floyd 求的是简单路径的最短路。因此，我们在求得时候，让 qs[i][j] = qs[j][i] = min(qs[i][j], qs[i][k] - dist[k][j])，那么就限制了中转节点，这样子就使得环只走一条正边，即不会走两条类似于 $(u, v, l)$ 一样的边.

#include<bits/stdc++.h>
using namespace std;
const int N = 610;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;
ll dist[N][N], g[N][N], qs[N][N], d[N];
int n, m;
int main()
{scanf("%d%d", &n, &m);memset(g, 0x3f, sizeof g);memset(dist, 0x3f, sizeof dist);//这个地方一定把自环初始化为0. 原因在于如果后面的qs中的u可能和某条边的端点重合//如果不初始化为0的话，那么 dist[i][i] 就不为0，就会使得答案变小.for(int i = 1; i <= n; i++) g[i][i] = dist[i][i] = 0;for(int i = 0; i < m; i++){int a, b, w;scanf("%d%d%d", &a, &b, &w);g[a][b] = g[b][a] = w;dist[a][b] = dist[b][a] = w;}for(int k = 1; k <= n; k++){for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);}}}int q;scanf("%d", &q);while(q--){int a, b, c;scanf("%d%d%d", &a, &b, &c);qs[a][b] = qs[b][a] = c;}for(int k = 1; k <= n; k++){for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){qs[i][j] = qs[j][i] = max(qs[i][j], qs[i][k] - dist[k][j]);}}}int ans = 0;for(int i = 1; i <= n; i++){for(int j = i + 1; j <= n; j++){ans += (qs[i][j] >= g[i][j]);}}printf("%d\n", ans);
}