2022 CCPC 绵阳
A. Ban or Pick, What’s the Trick?
题面描述：
红蓝双方有一个大小为 n n n 的英雄池，每次操作一方可以选择一个英雄或者 b a n ban ban 掉对方的一个英雄，每个英雄含有权值 v v v,求双方在最有策略下英雄权值之和的差(蓝方先操作)。
基本思路：
题目所给最大可选英雄数量为 10 10 10,则考虑 n × 10 × 10 n \times 10 \times 10 n×10×10 的 d p dp dp设当前进行的轮数为 t u r n turn turn,则之前红方操作的次数 t u r n b turnb turnb为 ⌊ t u r n − 1 2 ⌋ \lfloor{ turn-1\over 2}\rfloor ⌊2turn−1⌋,蓝方操作次数为 t u r n − 1 − t u r n b turn-1-turnb turn−1−turnb,将英雄按权值进行排序后，计算出 b a n , p i c k ban,pick ban,pick 所对应的英雄，判断合法性后进行 d f s dfs dfs,并使用记忆化搜索降低时间复杂度
代码：
#include <bits/stdc++.h>
using namespace std;
// #define int long long int
#define Paddi ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 4e5 + 10;
int n, k;
int dp[N][15][15];
vector<int> s1;
vector<int> s2;
const int Inf = 1e18;
int dfs(int turn, int np1, int np2)
{
if (turn > 2 * n)
return 0;
if ((dp[turn][np1][np2] != Inf) and (dp[turn][np1][np2] != -Inf))
return dp[turn][np1][np2];
int turnb = (turn - 1) / 2;
int turna = (turn - 1) - turnb;
int pos1 = turnb - np2 + np1;
int pos2 = turna - np1 + np2;
if (turn % 2 == 1)
{
int cnt = -Inf;
if ((pos1 != n) and (np1 != k))
cnt = max(cnt, dfs(turn + 1, np1 + 1, np2) + s1[pos1]);
if (pos2 != n)
cnt = max(cnt, dfs(turn + 1, np1, np2));
return dp[turn][np1][np2] = cnt;
}
else
{
int cnt = Inf;
if ((pos2 != n) and (np2 != k))
cnt = min(cnt, dfs(turn + 1, np1, np2 + 1) - s2[pos2]);
if (pos1 != n)
cnt = min(cnt, dfs(turn + 1, np1, np2));
return dp[turn][np1][np2] = cnt;
}
}
int main()
{
Paddi;
cin >> n >> k;
s1.resize(n);
s2.resize(n);
for (int i = 0; i < n; i++)
cin >> s1[i];
for (int i = 0; i < n; i++)
cin >> s2[i];
sort(s1.begin(), s1.end(), greater<int>());
sort(s2.begin(), s2.end(), greater<int>());
for (int i = 0; i <= 2 * n + 10; i++)
{
for (int j = 0; j <= k; j++)
{
for (int h = 0; h <= k; h++)
{
if (i % 2 == 0)
dp[i][j][h] = Inf;
else
dp[i][j][h] = -Inf;
}
}
}
int ans = dfs(1, 0, 0);
cout << ans << endl;
return 0;
}
E. Hammer to Fall
题面描述：
你有一张无向带权图 G G G,已知每一天被砸中的节点为 q i q_i qi,在某个节点被砸中之前，你要将所有在该节点上的人转移到相邻的节点，每个人转移的费用为该边的权值 w w w.求所需要的最小权值.
基本思路：
发现每个人的转移都是独立的，我们发现转移要考虑后续被砸中的节点，故我们考虑倒序
d
p
dp
dp,从后往前遍历被砸中的节点
x
x
x,有
d
p
[
x
]
=
m
i
n
(
x
,
y
,
w
)
∈
G
d
p
[
y
]
+
w
dp[x]=min_{(x,y,w) \in G} dp[y]+w
dp[x]=min(x,y,w)∈Gdp[y]+w
最暴力的想法是遍历每个相邻的节点。但是发现当某写节点连边数量较大时会超时。考虑到对节点所连边的数量进行分开处理。
对于小于边界的节点，我们暴力枚举每一个相邻的节点，对于大于边界的节点，我们用 s t d : s e t std: set std:set维护。
我们更新完一个节点后，将大于边界的节点的 s e t set set 全部进行更新。
设边界为 t t t,则时间复杂度为 O ( q ( t + 2 m t l o g n ) ) O(q(t+{2m\over t} logn)) O(q(t+t2mlogn))
利用基本不等式， t = 2 m l o g n t= \sqrt {2mlogn} t=2mlogn
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define Paddi ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#pragma GCC optimize(2)
const int N = 2e5 + 10;
struct Node
{
int v, w;
};
int read()
{
int x = 0, w = 1;
char ch = 0;
while (ch < '0' || ch > '9')
{
if (ch == '-')
w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = x * 10 + (ch - '0');
ch = getchar();
}
return x * w;
}
vector<struct Node> e[N], big[N];
set<array<int, 3>> now[N];
int dp[N], d[N], peo[N];
const int Mod = 998244353;
int n, m, q;
signed main()
{
n = read(), m = read(), q = read();
int t = sqrt(2 * m * log(n));
for (int i = 1; i <= n; i++)
peo[i] = read();
for (int i = 1; i <= m; i++)
{
int u, v, w;
u = read(), v = read(), w = read();
e[u].push_back({v, w});
e[v].push_back({u, w});
d[u]++, d[v]++;
}
for (int i = 1; i <= n; i++)
{
for (auto j : e[i])
now[i].insert({j.w, j.v, j.w});
for (auto j : e[i])
{
if (d[j.v] >= t)
big[i].push_back({j.v, j.w});
}
}
vector<int> query(q);
for (int i = 0; i < q; i++)
query[i] = read();
reverse(query.begin(), query.end());
for (int i = 0; i < q; i++)
{
int x = query[i];
int last = dp[x];
if (d[x] >= t)
{
auto it = *now[x].begin();
dp[x] = it[0];
}
else
{
int mi = 1e18;
for (auto j : e[x])
mi = min(mi, dp[j.v] + j.w);
dp[x] = mi;
}
for (auto j : big[x])
{
array<int, 3> a;
a[0] = last + j.w, a[1] = x, a[2] = j.w;
auto it = now[j.v].lower_bound(a);
now[j.v].erase(it);
now[j.v].insert({dp[x] + j.w, x, j.w});
}
}
int ans = 0;
for (int i = 1; i <= n; i++)
ans = (ans + (dp[i] * peo[i]) % Mod) % Mod;
printf("%lld\n", ans % Mod);
return 0;
}