2018 HDU多校第三场赛后补题
从易到难来写吧，其中题意有些直接摘了Claris的，数据范围是就不标了。
如果需要可以去hdu题库里找。题号是6319 ～ 6331。
L. Visual Cube
题意：
在画布上画一个三维立方体。
题解：
模拟即可。
代码：
#include <bits/stdc++.h>
using namespace std;
int a, b, c, R, C;
char g[505][505];
int main () {
int T; cin >> T;
for ( ; T; --T) {
cin >> a >> b >> c;
R = c * 2 + b * 2 + 1;
C = a * 2 + b * 2 + 1;
memset(g, '.', sizeof g);
for (int i = R; i >= R - c * 2; i -= 2) {
for (int j = 1; j <= a; ++j) {
g[i][j * 2 - 1] = '+';
g[i][j * 2] = '-';
}
g[i][a * 2 + 1] = '+';
if (i == R - c * 2) continue;
for (int j = 1; j <= a; ++j) {
g[i - 1][j * 2 - 1] = '|';
}
g[i - 1][a * 2 + 1] = '|';
}
int ed = R, st = R - c * 2;
for (int j = a * 2 + 1; j <= C; ++j) {
int x = j - (a * 2);
if (x & 1) {
for (int i = st; i <= ed; ++i) {
int y = ed - i;
if (y & 1) g[i][j] = '|';
else g[i][j] = '+';
}
} else {
for (int i = st; i <= ed; ++i) {
int y = ed - i;
if (y & 1) g[i][j] = '.';
else g[i][j] = '/';
}
}
--ed, --st;
}
ed = b * 2 + 1, st = 1;
for (int j = 1; j <= a * 2; ++j) {
int x = j;
if (x & 1) {
for (int i = ed; i >= st; --i) {
int y = i - st;
if (y & 1) g[i][j + ed - i] = '/';
else g[i][j + ed - i] = '+';
}
} else {
for (int i = ed; i >= st; --i) {
int y = i - st;
if (y & 1) ;
else g[i][j + ed - i] = '-';
}
}
}
for (int i = 1; i <= R; ++i) {
for (int j = 1; j <= C; ++j) printf("%c", g[i][j]);
puts("");
}
}
return 0;
}D. Euler Function
题意：
求第\(n\)个使得\(\varphi(k)\)为合数的\(k\)。
题解：
其实应该会有尝试，就是\(n\)到一定大小\(\varphi(k)\)都是大于\(2\)的偶数，同时也是合数。其实找一下规律可以发现只有\(k = 1, 2, 3, 6\)时\(\varphi(k)\)为质数。证明在Claris的题解里有写。
代码：
#include<bits/stdc++.h>
using namespace std;
int main () {
int T,n;
scanf("%d",&T);
while (T--) {
scanf("%d",&n);
if (n==1) printf("5\n");
else printf("%d\n",5+n);
}
return 0;
}F. Grab The Tree
题意：
给定一棵\(n\)个点的树，每个点有权值。两个人玩游戏，先手需要占领若干不相邻的点，然后后手占领剩下所有点。每个人的得分为占领的点权异或和，分高的获胜。问最优策略下游戏的结果。
题解：
设\(sum\)为所有点权的异或和，\(A\)为先手得分，\(B\)为后手得分。
若\(sum=0\)，则 \(A=B\)，怎样都是平局。
否则考虑先手可以将原图分成两块，每一块里面的点都不相邻，然后取异或和较大的那块就好了，所以此时先手必胜。
代码：
#include<bits/stdc++.h>
#define N 100010
using namespace std;
int main () {
int T,n,u,v,w;
scanf("%d",&T);
while (T--) {
int sum=0;
scanf("%d",&n);
for(int i=1; i<=n; ++i) scanf("%d",&w),sum^=w;
for(int i=1; i<n; ++i) scanf("%d%d",&u,&v);
if (sum==0) printf("D\n"); else printf("Q\n");
}
return 0;
}C. Dynamic Graph Matching
题意：
给定一个n个点的无向图，\(m\)次加边或者删边操作。
在每次操作后统计有多少个匹配包含\(k = 1, 2, ...,\frac n 2\)条边。
其中匹配是指不相交的边集。
题解：
设 f[i][S] 表示前i次操作，匹配点集为S的方案数。
设当前边的两个端点为\(x，y\)。
对于加边，显然有\(f[i][S]=f[i-1][S]+f[i-1][S-x-y]。\)
其实，也可以直接省略第一维，执行\(f[S]+=f[S-x-y]\)。正确性是显然的。
对于删边，由于前面加边的顺序无所谓，所以我们不妨设我们删除的正是上一次加入的边（为了方便理解）。
这样，我们执行的就是一个你操作罢了：\(f[S]-=f[S-x-y]\)。
代码：
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
const int mo = 1e9 + 7, N = 11;
int n, m, bc[1 << N], f[1 << N], ans[N]; char op[5];
int bitcnt (int x) {
return x ? bitcnt(x >> 1) + (x & 1) : 0;
}
int main () {
int T; cin >> T;
for (int i = 0; i < (1 << N); ++i) bc[i] = bitcnt(i);
for ( ; T; --T) {
cin >> n >> m, f[0] = 1;
for (int s = 1; s < (1 << n); ++s) f[s] = 0;
for (int i = 1, x, y; i <= m; ++i) {
scanf("%s%d%d", op, &x, &y), --x, --y;
if (op[0] == '+') {
for (int s = 0, t; s < (1 << n); ++s) {
if ((s >> x & 1) || (s >> y & 1)) continue;
t = s | 1 << x | 1 << y;
f[t] += f[s];
if (f[t] >= mo) f[t] -= mo;
}
} else {
for (int s = (1 << n) - 1, t; ~s; --s) {
if ((s >> x & 1) || (s >> y & 1)) continue;
t = s | 1 << x | 1 << y;
f[t] -= f[s];
if (f[t] < 0) f[t] += mo;
}
}
for (int i = 1; i <= (n >> 1); ++i) ans[i] = 0;
for (int s = 1, t; s < (1 << n); ++s) {
t = bc[s]; if (t & 1) continue; else t >>= 1;
ans[t] += f[s];
if (ans[t] >= mo) ans[t] -= mo;
}
for (int i = 1; i <= (n >> 1); ++i) {
printf("%d%c", ans[i], i < (n >> 1) ? ' ' : '\n');
}
}
}
return 0;
}G. Interstellar Travel
题意：
给定平面上\(n\)个点，起点横坐标最小，终点横坐标最大，所有点都在第一象限内。（包括坐标轴）
每次可以飞到一个横坐标严格更大的点，代价为两个坐标的叉积。
求起点到终点总代价最小的飞行路线，并输出字典序最小的路线。
题解：
因为叉积的几何意义就是有向平行四边形的面积的，然后根据题目给出的性质，很快就能反应过来，只需要维护一个凸包就好了（因为这个凸包面积最大，并且是负的，对应最小代价）。
注意会有重点的问题。
代码：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 200005;
int n, top;
struct point {
int x, y, i;
point () {}
point (int _x,int _y,int _i = 0) :
x(_x), y(_y), i(_i) {}
} a[N], s[N];
point operator - (point u, point v) {
return point(u.x - v.x, u.y - v.y, u.i);
}
bool cmp (point u, point v) {
ll t = 1ll * u.x * v.y - 1ll * u.y * v.x;
return t == 0 ? (u.x == v.x ? u.i < v.i: u.x < v.x) : t < 0;
}
bool cmp2 (point u, point v) {
ll t = 1ll * u.x * v.y - 1ll * u.y * v.x;
return t == 0 ? u.i < v.i : t < 0;
}
void solve () {
s[top = 1] = a[1];
for (int i = 2; i <= n; ++i) {
if (a[i].x == a[i - 1].x && a[i].y == a[i - 1].y) continue;
while (top >= 2 && cmp2(a[i] - s[top - 1], s[top] - s[top - 1])) --top;
s[++top] = a[i];
}
}
int main () {
int T; cin >> T;
for ( ; T; --T) {
cin >> n;
for (int i = 1; i <= n; ++i) {
scanf("%d%d", &a[i].x, &a[i].y);
a[i].i = i;
}
sort(a + 2, a + n, cmp);
solve();
for (int i = 1; i <= top; ++i) {
printf("%d%c", s[i].i, i < top ? ' ' : '\n');
}
}
return 0;
}A. Ascending Rating
题意：
给定一个序列\(a[1..n]\)，对于每个长度为\(m\)的连续子区间，求出区间\(a\)的最大值以及从左往右扫描该区间时\(a\)的最大值的变化次数。
题解：
这题反正来似乎比较容易。。
考虑导致维护一个单调递减的单调队列，其中队列大小\(size\)就是当前区间最大值的变化次数，队列中最后一个元素就是区间最大值。具体想一想就好了。其实我是不会打单调数据结构的
代码：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 10000005;
int n, m, k, p, q, r, mo, a[N];
int h, t, Q[N];
ll A, B;
int read () {
int x = 0; char ch = getchar();
for ( ; ch < '0' || ch > '9'; ch = getchar());
for ( ; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - 48;
return x;
}
int main () {
int T; cin >> T;
for ( ; T; --T) {
cin >> n >> m >> k >> p >> q >> r >> mo;
for (int i = 1; i <= k; ++i) a[i] = read();
for (int i = k + 1; i <= n; ++i) a[i] = (1ll * p * a[i - 1] + 1ll * q * i + r) % mo;
h = 0, t = 1, A = B = 0;
for (int i = n; i >= n - m + 1; --i) {
if (a[i] < a[Q[h]]) Q[++h] = i;
else {
for ( ; t <= h && a[i] >= a[Q[h]]; ) --h;
Q[++h] = i;
}
}
A += a[Q[t]] ^ (n - m + 1);
B += (h - t + 1) ^ (n - m + 1);
for (int i = n - m; i; --i) {
if (Q[t] == i + m) ++t;
if (a[i] < a[Q[h]]) Q[++h] = i;
else {
for ( ; t <= h && a[i] >= a[Q[h]]; ) --h;
Q[++h] = i;
}
A += a[Q[t]] ^ i;
B += (h - t + 1) ^ i;
}
cout << A << " " << B << endl;
}
return 0;
}I. Random Sequence
题意：
给定一个正整数序列\(a[1..n]\)和一个\(v\)数组，每个数在\([1, m]\)之间，有些数已知，有些数未知。
求未知数随机填的情况下以下值的期望：
\[ \begin{eqnarray*} \prod_{i=1}^{n-3} v[\gcd(a_i,a_{i+1},a_{i+2},a_{i+3})] \end{eqnarray*} \]
题解：
观察下这题的数据范围，发现可以写个dp。
\(f[i][x][y][z]\)表示将位置\(1～i\)（可能进行的）填数后，\(a[i]=x，gcd(a[i],a[i-1])=y，gcd(a[i],a[i-1],a[i-2])=z\)的期望答案（即套上连乘符号的）。
则我们可以很轻松知道转移方程。
但要注意的是这个连乘符号可能导致算期望的式子和我们平时做到的略有不同。总之，是有这样的式子：
\[ E[s] = V[s] * \begin{eqnarray*} \sum_{pre(s)}^{} E[pre]*pro[pre,s] \end{eqnarray*} \]
但别以为这样就完事了。
注意到这样会MLE，所以你可以选择开滚动数组。
然后你又被卡TLE了。注意到对于一个合法状态\((x，y，z)\)，满足\(z|y\)且\(y|x\)。利用这个就可以简化状态数。
然后你就稳了。注意前三项是不计贡献的。
代码：
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 105, mo = 1e9 + 7;
int n, m, g[N][N], inv[N], a[N], v[N];
int f[2][N][N][N];
int ksm (int b, int p) {
if (p < 2) return p ? b : 1;
int t = ksm(b, p >> 1); t = 1ll * t * t % mo;
return p & 1 ? 1ll * t * b % mo : t;
}
int main () {
int T; cin >> T;
for (int i = 0; i <= 100; ++i) g[0][i] = g[i][0] = i;
for (int i = 1; i <= 100; ++i)
for (int j = 1; j <= 100; ++j) g[i][j] = __gcd(i, j);
for (int i = 1; i <= 100; ++i) inv[i] = ksm(i, mo - 2);
for ( ; T; --T) {
cin >> n >> m;
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for (int i = 1; i <= m; ++i) scanf("%d", &v[i]);
memset(f, 0, sizeof f);
int nx, ny, nz, tmp;
for (int z = 1; z <= m; ++z)
for (int y = 1; y <= m; ++y)
for (int x = 1; x <= m; ++x) {
if (a[1] && a[1] != z) continue;
if (a[2] && a[2] != y) continue;
if (a[3] && a[3] != x) continue;
nx = x, ny = g[x][y], nz = g[ny][z];
tmp = 1;
if (!a[1]) tmp = 1ll * tmp * inv[m] % mo;
if (!a[2]) tmp = 1ll * tmp * inv[m] % mo;
if (!a[3]) tmp = 1ll * tmp * inv[m] % mo;
f[1][nx][ny][nz] += tmp;
if (f[1][nx][ny][nz] >= mo) f[1][nx][ny][nz] -= mo;
}
for (int i = 3, c; i <= n; ++i) {
c = i & 1, memset(f[c ^ 1], 0, sizeof f[c ^ 1]);
for (int z = 1; z <= m; ++z)
for (int y = z; y <= m; y += z)
for (int x = y; x <= m; x += y) if (f[c][x][y][z]) {
if (a[i + 1]) {
nx = a[i + 1], ny = g[x][a[i + 1]], nz = g[y][a[i + 1]];
f[c ^ 1][nx][ny][nz] += 1ll * f[c][x][y][z] * v[g[a[i + 1]][z]] % mo;
if (f[c ^ 1][nx][ny][nz] >= mo) f[c ^ 1][nx][ny][nz] -= mo;
continue;
}
for (int j = 1; j <= m; ++j) {
nx = j, ny = g[x][j], nz = g[y][j];
f[c ^ 1][nx][ny][nz] += 1ll * f[c][x][y][z] * v[g[j][z]] % mo * inv[m] % mo;
if (f[c ^ 1][nx][ny][nz] >= mo) f[c ^ 1][nx][ny][nz] -= mo;
}
}
}
int ans = 0;
for (int z = 1; z <= m; ++z)
for (int y = z; y <= m; y += z)
for (int x = y; x <= m; x += y) ans = (ans + f[n & 1][x][y][z]) % mo;
cout << ans << endl;
}
return 0;
}M. Walking Plan
题意：
给定一个\(n\)个点，\(m\)条边的有向图，\(q\)次询问\(s\)到\(t\)经过至少\(k\)条边的最短路。
题解：
注意观察数据范围。
显然可以预处理出\(f[k][i][j]\)表示i经过恰好k条边到达j的最短路。
转移方程：\(f[k][i][j]=min(f[k−1][i][x]+w[x][j])\)。（看f[k]长得很像个矩阵，不过这题并不用这个性质）
当然你可以选择用\(O(n^3 * 10000)\)的时间预处理，然后愉快地gg了。
当然还有更好的选择。我们来分块！
我们预处理出\(f[k][i][j]\)表示i经过恰好k条边到达j的最短路，其中\(0<=k<=100\)。
再预处理出\(g[k][i][j]\)表示i经过恰好100k条边到达j的最短路，其中\(0<=k<=100\)。
对于一个询问，设\(A = k / 100\)，\(B\) \(=\) \(k\) \(mod\) \(100\)。
则我们枚举中间点，\(ans=min(a[A][s][x]+b[B][x][t])\)。
这样是不是就好了？
错！
题目中要求的是至少经过\(k\)条边，而非恰好。
所以我们在\(b\)数组中做点手脚。其实就是先跑出原图的最短路，然后以“恰当的方式”更新\(b\)数组就好了。
这个恰当的方式可以参考一下具体实现。
复杂度是\(O(n^3 \sqrt k+ nq)\)。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 55, K = 10005, S = 105, inf = 0x3f3f3f3f;
int n, m, q, ans, g[N][N], f[N][N], A[S][N][N], B[S][N][N];
int main () {
int T; cin >> T;
for ( ; T; --T) {
cin >> n >> m;
memset(g, 0x3f, sizeof g);
memset(A, 0x3f, sizeof A);
memset(B, 0x3f, sizeof B);
for (int i = 1, x, y, z; i <= m; ++i) {
scanf("%d%d%d", &x, &y, &z);
g[x][y] = min(g[x][y], z);
B[1][x][y] = g[x][y];
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) A[0][i][j] = B[0][i][j] = i == j ? 0 : inf;
for (int k = 2; k <= 100; ++k) {
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
for (int x = 1; x <= n; ++x)
B[k][i][j] = min(B[k][i][j], B[k - 1][i][x] + B[1][x][j]);
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) A[1][i][j] = B[100][i][j];
}
for (int k = 2; k <= 100; ++k) {
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
for (int x = 1; x <= n; ++x)
A[k][i][j] = min(A[k][i][j], A[k - 1][i][x] + A[1][x][j]);
}
for (int i = 1; i <= n; i++) g[i][i] = 0;
for (int x = 1; x <= n; ++x) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) g[i][j] = min(g[i][j], g[i][x] + g[x][j]);
}
}
for (int k = 0; k <= 100; ++k) {
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) f[i][j] = inf;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
for (int x = 1; x <= n; ++x) f[i][j] = min(f[i][j], B[k][i][x] + g[x][j]);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) B[k][i][j] = f[i][j];
}
cin >> q;
for (int s, t, k, u, v; q; --q) {
scanf("%d%d%d", &s, &t, &k), ans = inf;
u = k / 100, v = k % 100;
for (int i = 1; i <= n; ++i) {
ans = min(ans, A[u][s][i] + B[v][i][t]);
}
if (ans >= inf) ans = -1;
printf("%d\n", ans);
}
}
return 0;
}H. Monster Hunter
题意：
给定一棵\(n\)个点的树，除\(1\)外每个点有一只怪兽，打败它需要先消耗\(a[i]\)点 HP，再恢复\(b[i]\)点 HP。
求从\(1\)号点出发按照最优策略打败所有怪兽一开始所需的最少HP（其中，过程中不能出现HP为负的情况）。
题解：
这题教会了我们从简单的情况思考。
假设没有“树”的限制，即没有定死的先后顺序。怎么办？
显然贪心。
将怪兽分成两类考虑：\(a<b\)和\(a>=b\)。其实这种贪心见到过不止一次
显然应该先打前一类，再打后一类。
前一类的显然是先打a小的。可以感性理解一下。其实很好证，时间关系，不证了。
后一类呢，稍微要想一想。我就拖一下Claris的证明吧：
对于\(a>=b\)的怪兽，考虑两只怪兽\(i\),\(j\)。
先打\(i\)再打\(j\): $HPmin=HP - a[i] + b[i] - a[j] $
先打\(j\)再打\(i\): $HPmin=HP - a[j] + b[j] - a[i] $
这样的话，我们必定会选择\(b\)大的先打。
再回头考虑原问题。设排好序后，顺序为\(p[1]，p[2]，...，p[n]\)
若\(p[1] = 1\)，那么第一步打\(p[1]\)一定最优。
否则在打完\(p[1]\)的父亲\(fa\)后，紧接着打\(p[1]\)一定最优。直接合并它们。
剩下的是规模为\(n-1\)的子问题。
注意这里合并和快速搜索最优分别要用到并查集和堆。
复杂度是\(O(nlogn)\)的。
代码：
#include <bits/stdc++.h>
#define mp make_pair
#define ll long long
using namespace std;
const int N = 100005;
int n, P, a[N], b[N];
int tot, lnk[N], nxt[N << 1], son[N << 1], fa[N];
bool dead[N];
struct mons {
ll a, b; int i, t;
mons () {}
mons (ll _a, ll _b, int _i = 0,int _t = 0) :
a(_a), b(_b), i(_i), t(_t) {}
bool operator < (const mons &o) const {
bool k1 = a < b, k2 = o.a < o.b;
if (k1 != k2) return k1 < k2;
else return a >= b ? b < o.b : a > o.a;
}
void operator += (const mons &o) {
ll na = max(a, a - b + o.a), nb = - a + b - o.a + o.b + na;
a = na, b = nb;
}
} m[N], cur;
priority_queue <mons> q;
int read () {
int x = 0; char ch = getchar();
for ( ; ch < '0' || ch > '9'; ch = getchar());
for ( ; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - 48;
return x;
}
void add (int x, int y) {
nxt[++tot] = lnk[x], lnk[x] = tot, son[tot] = y;
}
void dfs (int x, int p) {
fa[x] = p;
for (int j = lnk[x]; j; j = nxt[j]) {
if (son[j] == p) continue;
dfs(son[j], x);
}
}
int get (int x) {
return dead[fa[x]] ? fa[x] = get(fa[x]) : fa[x];
}
int main () {
for (int T = read(); T; --T) {
n = read(), tot = 0;
for (int i = 1; i <= n; ++i) lnk[i] = 0, dead[i] = 0;
for (int i = 1; i <= n * 2; ++i) nxt[i] = 0;
for ( ; !q.empty(); q.pop());
m[1] = mons(0, 0, 1, 0);
for (int i = 2; i <= n; ++i) {
m[i].a = read(), m[i].b = read();
m[i].i = i, m[i].t = 0, q.push(m[i]);
}
for (int i = 1, x, y; i < n; ++i) {
x = read(), y = read();
add(x, y), add(y, x);
}
dfs(1, 0), dead[1] = 0;
for (int sec = 1; !q.empty(); ++sec) {
cur = q.top(), q.pop();
if (cur.t != m[cur.i].t || dead[cur.i]) continue;
get(cur.i), dead[cur.i] = 1;
P = get(cur.i);
m[P] += m[cur.i], m[P].t = sec;
if (P > 1) q.push(m[P]);
}
cout << max(0ll, m[1].a) << endl;
}
return 0;
}剩下的题可能有点难搞了。。