A – 玩具谜题
sb 题，随便搞。
// P1563.cpp
#include <iostream>
using namespace std;
int main()
{
int N, M;
cin >> N >> M;
int dir[N];
string occupations[N];
int cmdKeys[M];
int cmdPath[M];
// I/O;
for (int i = 0; i < N; i++)
cin >> dir[i] >> occupations[i];
for (int j = 0; j < M; j++)
cin >> cmdKeys[j] >> cmdPath[j];
// Process;
int currentBias = 0;
for (int i = 0; i < M; i++)
if (cmdKeys[i] == 0)
if (dir[currentBias % N] == 1)
currentBias += cmdPath[i];
else
{
currentBias -= cmdPath[i];
if (currentBias < 0)
currentBias = N + currentBias;
}
else if (dir[currentBias % N] == 1)
{
currentBias -= cmdPath[i];
if (currentBias < 0)
currentBias = N + currentBias;
}
else
currentBias += cmdPath[i];
cout << occupations[currentBias % N];
return 0;
}
B – 天天爱跑步
草，出在 D1T2 是真的毒。当然，思路还是非常巧妙的。
首先，把树之类的都存进来，对于一个玩家预处理出其 LCA，并在 LCA 上打标记（只有到了 LCA 这颗子树才能产生贡献）。开一个桶，关键字是深度。当一个进入了一个 LCA 子树之后，就可以让子树内的点生效：在桶子里++即可。
剩下的回答，再来一遍 DFS，每次经过一个监视点就回答询问即可。细节超级超级多，看看代码吧。
// P1600.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 3e6 + 2000;
int head[MAX_N], current, fa[20][MAX_N], dep[MAX_N], wi[MAX_N], max_dep;
int bucket[MAX_N << 1], n, m, si[MAX_N], di[MAX_N], status[MAX_N], answer[MAX_N];
int bucket_up[1000011];
vector<int> lcaS[MAX_N], lcaT[MAX_N], tbuck[MAX_N];
struct route
{
int s, t, lca, len;
} routes[MAX_N];
struct edge
{
int to, nxt;
} edges[MAX_N << 1];
void addpath(int src, int dst)
{
edges[current].to = dst, edges[current].nxt = head[src];
head[src] = current++;
}
void initialize(int u)
{
max_dep = max(max_dep, dep[u]);
for (int i = head[u]; i != -1; i = edges[i].nxt)
if (edges[i].to != fa[0][u])
{
dep[edges[i].to] = dep[u] + 1;
fa[0][edges[i].to] = u;
initialize(edges[i].to);
}
}
int getLCA(int x, int y)
{
if (dep[x] < dep[y])
swap(x, y);
for (int i = 19; i >= 0; i--)
if (dep[fa[i][x]] >= dep[y])
x = fa[i][x];
if (x == y)
return x;
for (int i = 19; i >= 0; i--)
if (fa[i][x] != fa[i][y])
x = fa[i][x], y = fa[i][y];
return fa[0][x];
}
void dfs_downward(int u)
{
int now = wi[u] + dep[u], previous;
if (now <= max_dep)
previous = bucket[now];
for (int i = head[u]; i != -1; i = edges[i].nxt)
if (edges[i].to != fa[0][u])
dfs_downward(edges[i].to);
bucket[dep[u]] += status[u];
if (now <= max_dep)
answer[u] = bucket[now] - previous;
for (int i = 0, siz = lcaS[u].size(); i < siz; i++)
bucket[dep[lcaS[u][i]]]--;
}
void dfs_upward(int u)
{
int now = dep[u] - wi[u] + MAX_N, previous = bucket_up[now];
for (int i = head[u]; i != -1; i = edges[i].nxt)
if (edges[i].to != fa[0][u])
dfs_upward(edges[i].to);
for (int i = 0, siz = tbuck[u].size(); i < siz; i++)
bucket_up[MAX_N + tbuck[u][i]]++;
answer[u] += bucket_up[now] - previous;
for (int i = 0, siz = lcaT[u].size(); i < siz; i++)
bucket_up[MAX_N + lcaT[u][i]]--;
}
int main()
{
memset(head, -1, sizeof(head));
scanf("%d%d", &n, &m);
for (int i = 1; i <= n - 1; i++)
{
int u, v;
scanf("%d%d", &u, &v), addpath(u, v), addpath(v, u);
}
dep[1] = 1, initialize(1);
for (int i = 1; i < 20; i++)
for (int j = 1; j <= n; j++)
fa[i][j] = fa[i - 1][fa[i - 1][j]];
for (int i = 1; i <= n; i++)
scanf("%d", &wi[i]);
for (int i = 1; i <= m; i++)
{
scanf("%d%d", &routes[i].s, &routes[i].t);
status[routes[i].s]++;
routes[i].lca = getLCA(routes[i].s, routes[i].t);
routes[i].len = dep[routes[i].s] + dep[routes[i].t] - 2 * dep[routes[i].lca];
lcaS[routes[i].lca].push_back(routes[i].s);
}
dfs_downward(1);
for (int i = 1; i <= m; i++)
{
tbuck[routes[i].t].push_back(dep[routes[i].t] - routes[i].len);
lcaT[routes[i].lca].push_back(dep[routes[i].t] - routes[i].len);
}
dfs_upward(1);
for (int i = 1; i <= m; i++)
if (dep[routes[i].s] - dep[routes[i].lca] == wi[routes[i].lca])
answer[routes[i].lca]--;
for (int i = 1; i <= n; i++)
printf("%d ", answer[i]);
return 0;
}
C – 换教室
概率期望 DP 的经典题目。
先考虑用 Floyd 处理完图上最短路，然后设计状态\(dp[i][j]\)为第\(i\)个时间段内换了\(j\)次教室。然后根据两种选择，随便转移就可以了。代码可能比较丑。
// P1805.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2020, MAX_V = 330;
const double INF = 1e17 + 5;
int n, m, v, e, ci[MAX_N], di[MAX_N], dist[MAX_V][MAX_V], tmpx, tmpy, tmpz;
double pi[MAX_N], dp[MAX_N][MAX_N][2];
int main()
{
memset(dist, 63, sizeof(dist));
scanf("%d%d%d%d", &n, &m, &v, &e);
for (int i = 1; i <= n; i++)
scanf("%d", &ci[i]);
for (int i = 1; i <= n; i++)
scanf("%d", &di[i]);
for (int i = 1; i <= n; i++)
scanf("%lf", &pi[i]);
for (int i = 1; i <= e; i++)
scanf("%d%d%d", &tmpx, &tmpy, &tmpz), dist[tmpx][tmpy] = min(dist[tmpx][tmpy], tmpz), dist[tmpy][tmpx] = dist[tmpx][tmpy];
for (register int k = 1; k <= v; k++)
for (register int i = 1; i <= v; i++)
for (register int j = 1; j <= v; j++)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
for (int i = 1; i <= v; i++)
dist[i][i] = dist[0][i] = dist[i][0] = 0;
memset(dp, 127, sizeof(dp));
dp[1][0][0] = dp[1][1][1] = 0;
for (int i = 2; i <= n; i++)
{
dp[i][0][0] = dp[i - 1][0][0] + dist[ci[i - 1]][ci[i]];
for (int j = 1; j <= min(i, m); j++)
{
int C1 = ci[i - 1], C2 = di[i - 1], C3 = ci[i], C4 = di[i];
dp[i][j][0] = min(dp[i][j][0], min(dp[i - 1][j][0] + dist[C1][C3], dp[i - 1][j][1] + dist[C1][C3] * (1 - pi[i - 1]) + dist[C2][C3] * pi[i - 1]));
dp[i][j][1] = min(dp[i][j][1], min(dp[i - 1][j - 1][0] + dist[C1][C3] * (1 - pi[i]) + dist[C1][C4] * pi[i], dp[i - 1][j - 1][1] + dist[C2][C4] * pi[i] * pi[i - 1] + dist[C2][C3] * pi[i - 1] * (1 - pi[i]) + dist[C1][C4] * (1 - pi[i - 1]) * pi[i] + dist[C1][C3] * (1 - pi[i - 1]) * (1 - pi[i])));
}
}
double ans = INF;
for (register int i = 0; i <= m; i++)
ans = min(ans, min(dp[n][i][0], dp[n][i][1]));
printf("%.2lf", ans);
return 0;
}
D – 组合数问题
先预处理对\(k\)取模的值，然后前缀和处理。
// P2822.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_DOM = 2200;
struct ask
{
int n, m;
} asks[(int)1e4 + 20];
ll t, k, c_table[MAX_DOM][MAX_DOM], prs[MAX_DOM][MAX_DOM];
int max_dom;
int main()
{
scanf("%lld%lld", &t, &k);
c_table[1][1] = c_table[1][0] = 1 % k;
for (int i = 1; i <= t; i++)
scanf("%d%d", &asks[i].n, &asks[i].m), max_dom = max(max_dom, max(asks[i].n, asks[i].m));
for (int i = 2; i <= max_dom; i++)
{
c_table[i][0] = 1;
for (int j = 1; j <= i; j++)
c_table[i][j] = (c_table[i - 1][j - 1] + c_table[i - 1][j]) % k;
}
for (int i = 1; i <= max_dom; i++)
for (int j = 1; j <= max_dom; j++)
{
int res = ((c_table[i][j] == 0 && j <= i) ? 1 : 0);
prs[i][j] = prs[i - 1][j] + prs[i][j - 1] - prs[i - 1][j - 1] + res;
}
for (int i = 1; i <= t; i++)
printf("%d\n", prs[asks[i].n][min(asks[i].n, asks[i].m)]);
return 0;
}
E – 蚯蚓
这题蛮好。思考发现越后被切断的蚯蚓的长度越小，所以我们不需要用堆来保证单调性，考虑用一个「原生」队列、两个「被切断」队列来进行维护，每次取最大就直接取 max 就行。至于增长就直接用全局增量搞就可以了。
// P2827.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 7e6 + 200;
int n, m, q, u, v, t, seq[int(1e5) + 200];
queue<int> q1, q2, q3;
int queryans[MAX_N], acc;
int main()
{
scanf("%d%d%d%d%d%d", &n, &m, &q, &u, &v, &t);
for (int i = 1; i <= n; i++)
scanf("%d", &seq[i]);
sort(seq + 1, seq + 1 + n), reverse(seq + 1, seq + 1 + n);
for (int i = 1; i <= n; i++)
q1.push(seq[i]);
for (int tick = 1; tick <= m; tick++)
{
// get the biggest;
queue<int> *ptr = NULL;
int val = -0x3f3f3f3f;
if (!q1.empty() && q1.front() >= val)
ptr = &q1, val = q1.front();
if (!q2.empty() && q2.front() >= val)
ptr = &q2, val = q2.front();
if (!q3.empty() && q3.front() >= val)
ptr = &q3, val = q3.front();
ptr->pop();
// split it;
val += acc, queryans[tick] = val;
int lft = 1LL * val * u / v, rig = val - lft;
acc += q;
q2.push(lft - acc), q3.push(rig - acc);
}
for (int i = t; i <= m; i += t)
printf("%d ", queryans[i]);
puts("");
int cnt = 1;
while (!(q1.empty() && q2.empty() && q3.empty()) && cnt <= n + m)
{
queue<int> *ptr = NULL;
int val = -0x3f3f3f3f;
if (!q1.empty() && q1.front() >= val)
ptr = &q1, val = q1.front();
if (!q2.empty() && q2.front() >= val)
ptr = &q2, val = q2.front();
if (!q3.empty() && q3.front() >= val)
ptr = &q3, val = q3.front();
ptr->pop();
if (cnt % t == 0)
printf("%d ", val + acc);
cnt++;
}
return 0;
}
F – 愤怒的小鸟
应该比较好推。首先看到数据范围就显然是状态压缩，然后你就去找每一个点集是否能只被一个抛物线经过。之后裸的 DP 一下就可以了。
// P2831.cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define pr pair<double, double>
using namespace std;
const double eps = 1e-8;
int T, n, dotset[19][19], dp[(1 << 19)], lbit[(1 << 19)], m;
pr prs[20];
void solve(double &x, double &y, double a1, double b1, double c1, double a2, double b2, double c2)
{
y = (a1 * c2 - a2 * c1) / (a1 * b2 - a2 * b1);
x = (c1 - b1 * y) / a1;
}
int main()
{
for (int i = 0; i < (1 << 18); i++)
{
int bit = 0;
for (; bit < 18 && (i & (1 << bit)) ; bit++)
;
lbit[i] = bit;
}
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &m);
memset(dp, 0x3f, sizeof(dp)), memset(dotset, 0, sizeof(dotset));
for (int i = 0; i < n; i++)
scanf("%lf%lf", &prs[i].first, &prs[i].second);
// process the curves;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
if (fabs(prs[i].first - prs[j].first) < eps)
continue;
double a, b;
solve(a, b, prs[i].first * prs[i].first, prs[i].first, prs[i].second,
prs[j].first * prs[j].first, prs[j].first, prs[j].second);
if (a > -eps)
continue;
for (int k = 0; k < n; k++)
if (fabs(a * prs[k].first * prs[k].first + b * prs[k].first - prs[k].second) < eps)
dotset[i][j] |= (1 << k);
}
dp[0] = 0;
for (int stat = 0; stat < (1 << n); stat++)
{
int esspt = lbit[stat];
dp[stat | (1 << esspt)] = min(dp[stat | (1 << esspt)], dp[stat] + 1);
for (int k = 0; k < n; k++)
dp[stat | dotset[esspt][k]] = min(dp[stat | dotset[esspt][k]], dp[stat] + 1);
}
printf("%d\n", dp[(1 << n) - 1]);
}
return 0;
}