2018冬令营模拟测试赛（十七）
[Problem A]Tree
试题描述
输入
见“试题描述”
输出
见“试题描述”
输入示例
见“试题描述”
输出示例
见“试题描述”
数据规模及约定
见“试题描述”
题解
这个数据范围肯定是树上背包了。
令 \(f(i, j, k)\) 表示子树 \(i\) 中选择了 \(j\) 个节点，路径与根的连接情况为 \(k\)，具体地：
- \(k = 0\) 时，路径的两个端点都在子树内部；
- \(k = 1\) 时，路径的一个端点是 \(i\)，另一个端点在子树内部；
- \(k = 2\) 时，路径的两个端点都是 \(i\)。
这个树上背包的过程是：初始时只有选择根节点的情况（此时路径两端点当然都是 \(i\)），然后考虑加入一个子树，那么现在就是要讨论新路径的两个端点是否在根，若不在根，则在新加入的子树中或者原来的子树中；具体地：
- 两个节点都不在根，那么有三种情况：
- 两个端点都在原来的子树中；
- 两个端点都在新加入的子树中；
- 一个端点在新加入的子树中，另一个在原来子树中。
- 一个节点在根，那么有两种情况：
- 另一个节点在原来子树中；
- 另一个节点在新加入的子树中。
- 两个节点都在根。
转移的时候把路径的首尾接好，设新加入的子树是 \(j\)，算好 \(i \rightarrow j\) 这条边经过一次还是两次。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define rep(i, s, t) for(int i = (s), mi = (t); i <= mi; i++)
#define dwn(i, s, t) for(int i = (s), mi = (t); i >= mi; i--)
int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
#define maxn 3010
#define maxm 6010
#define oo 700000000
int n, m, K, head[maxn], nxt[maxm], to[maxm], dist[maxm];
void AddEdge(int a, int b, int c) {
to[++m] = b; dist[m] = c; nxt[m] = head[a]; head[a] = m;
swap(a, b);
to[++m] = b; dist[m] = c; nxt[m] = head[a]; head[a] = m;
return ;
}
void upd(int& a, int b) {
if(a > b) a = b;
return ;
}
int f[maxn][maxn][2][2], siz[maxn];
void dp(int u, int fa) {
f[u][1][1][1] = 0;
siz[u] = 1;
for(int e = head[u]; e; e = nxt[e]) if(to[e] != fa) {
dp(to[e], u);
dwn(i, siz[u], 1) dwn(j, siz[to[e]], 1) {
upd(f[u][i+j][0][0], f[u][i][0][0] + f[to[e]][j][1][1] + (dist[e] << 1));
upd(f[u][i+j][0][0], min(f[to[e]][j][0][0], min(f[to[e]][j][0][1], f[to[e]][j][1][1])) + f[u][i][1][1] + (dist[e] << 1));
upd(f[u][i+j][0][0], f[u][i][0][1] + min(f[to[e]][j][0][1], f[to[e]][j][1][1]) + dist[e]);
upd(f[u][i+j][0][1], f[u][i][0][1] + f[to[e]][j][1][1] + (dist[e] << 1));
upd(f[u][i+j][0][1], f[u][i][1][1] + min(f[to[e]][j][0][1], f[to[e]][j][1][1]) + dist[e]);
upd(f[u][i+j][1][1], f[u][i][1][1] + f[to[e]][j][1][1] + (dist[e] << 1));
}
siz[u] += siz[to[e]];
}
// rep(i, 0, siz[u]) printf("[%d][%d]: %d %d %d\n", u, i, f[u][i][0][0], f[u][i][0][1], f[u][i][1][1]);
return ;
}
int main() {
n = read(); K = read();
rep(i, 1, n - 1) {
int a = read(), b = read(), c = read();
AddEdge(a, b, c);
}
rep(i, 1, n) rep(j, 0, n) rep(s, 0, 1) rep(t, 0, 1) f[i][j][s][t] = oo;
dp(1, 0);
int ans = oo;
rep(i, 1, n) upd(ans, min(f[i][K][0][0], min(f[i][K][0][1], f[i][K][1][1])));
printf("%d\n", ans);
return 0;
}
[Problem B]Tower
试题描述
输入
见“试题描述”
输出
见“试题描述”
输入示例
见“试题描述”
输出示例
见“试题描述”
数据规模及约定
见“试题描述”
题解
这个题直接上哈希……
由于在首尾添加一个字符，答案只可能加 \(1\) 或加 \(2\)，于是分别维护一下首尾正反长度为 \(nowans\) 和 \(nowans + 1\) 的串的哈希值就好了，有必要再开一个串记录当前串长什么样。然后记得把所有东西可持久化一下（包括当前串的首尾指针、答案、\(8\) 种哈希值），其实就是用个栈维护一下，到撤销的时候直接把栈的顶指针减去它撤回的步数即可。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <vector>
using namespace std;
#define rep(i, s, t) for(int i = (s), mi = (t); i <= mi; i++)
#define dwn(i, s, t) for(int i = (s), mi = (t); i >= mi; i--)
const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *Tail;
inline char Getchar() {
if(Head == Tail) {
int l = fread(buffer, 1, BufferSize, stdin);
Tail = (Head = buffer) + l;
}
return *Head++;
}
int read() {
int x = 0, f = 1; char c = Getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }
return x * f;
}
#define maxn 10000010
#define UI unsigned int
#define LL long long
#define rate 233
UI rinv;
void gcd(LL a, LL b, LL& x, LL& y) {
if(!b){ x = 1; y = 0; return ; }
gcd(b, a % b, y, x); y -= (a / b) * x;
return ;
}
void getinv() {
LL x, y;
gcd(rate, 4294967296ll, x, y);
rinv = x;
return ;
}
short S[maxn<<1];
int rpow[maxn], fr[2][2][maxn], ed[2][2][maxn]; // [rev][add]
int hd[maxn], tl[maxn], ans[maxn], top;
void getMore() {
if(ans[top] + 1 <= tl[top] - hd[top] + 1) {
ed[0][1][top] = ed[0][0][top] + rpow[ans[top]] * S[tl[top]-ans[top]];
ed[1][1][top] = ed[1][0][top] * rate + S[tl[top]-ans[top]];
fr[0][1][top] = fr[0][0][top] * rate + S[hd[top]+ans[top]];
fr[1][1][top] = fr[1][0][top] + rpow[ans[top]] * S[hd[top]+ans[top]];
}
else rep(rev, 0, 1) ed[rev][1][top] = fr[rev][1][top] = 0;
return ;
}
void addr(short c) {
top++;
S[tl[top] = tl[top-1]+1] = c;
hd[top] = hd[top-1];
if(ans[top-1] + 1 <= tl[top-1] - hd[top-1] + 1 && ed[0][1][top-1] * rate + c == ed[1][1][top-1] + rpow[ans[top-1]+1] * c) { // ans + 2
ans[top] = ans[top-1] + 2;
ed[0][0][top] = ed[0][1][top-1] * rate + c;
ed[1][0][top] = ed[1][1][top-1] + rpow[ans[top-1]+1] * c;
fr[0][0][top] = fr[0][1][top-1] * rate + S[hd[top-1]+ans[top-1]+1];
fr[1][0][top] = fr[1][1][top-1] + rpow[ans[top-1]+1] * S[hd[top-1]+ans[top-1]+1];
}
else if(ed[0][0][top-1] * rate + c == ed[1][0][top-1] + rpow[ans[top-1]] * c) { // ans + 1
ans[top] = ans[top-1] + 1;
ed[0][0][top] = ed[0][0][top-1] * rate + c;
ed[1][0][top] = ed[1][0][top-1] + rpow[ans[top-1]] * c;
fr[0][0][top] = fr[0][0][top-1] * rate + S[hd[top]+ans[top-1]];
fr[1][0][top] = fr[1][0][top-1] + rpow[ans[top-1]] * S[hd[top]+ans[top-1]];
}
else {
ans[top] = ans[top-1];
ed[0][0][top] = ed[0][0][top-1] * rate + c - rpow[ans[top]] * S[tl[top]-ans[top]];
ed[1][0][top] = (ed[1][0][top-1] + rpow[ans[top]] * c - S[tl[top]-ans[top]]) * rinv;
fr[0][0][top] = fr[0][0][top-1];
fr[1][0][top] = fr[1][0][top-1];
}
getMore();
return ;
}
void addl(short c) {
top++;
S[hd[top] = hd[top-1]-1] = c;
tl[top] = tl[top-1];
if(ans[top-1] + 1 <= tl[top-1] - hd[top-1] + 1 && fr[0][1][top-1] + rpow[ans[top-1]+1] * c == fr[1][1][top-1] * rate + c) { // ans + 2
ans[top] = ans[top-1] + 2;
fr[0][0][top] = fr[0][1][top-1] + rpow[ans[top-1]+1] * c;
fr[1][0][top] = fr[1][1][top-1] * rate + c;
ed[0][0][top] = ed[0][1][top-1] + rpow[ans[top-1]+1] * S[tl[top-1]-ans[top-1]-1];
ed[1][0][top] = ed[1][1][top-1] * rate + S[tl[top-1]-ans[top-1]-1];
}
else if(fr[0][0][top-1] + rpow[ans[top-1]] * c == fr[1][0][top-1] * rate + c) { // ans + 1
ans[top] = ans[top-1] + 1;
fr[0][0][top] = fr[0][0][top-1] + rpow[ans[top-1]] * c;
fr[1][0][top] = fr[1][0][top-1] * rate + c;
ed[0][0][top] = ed[0][0][top-1] + rpow[ans[top-1]] * S[tl[top]-ans[top-1]];
ed[1][0][top] = ed[1][0][top-1] * rate + S[tl[top]-ans[top-1]];
}
else {
ans[top] = ans[top-1];
fr[0][0][top] = (fr[0][0][top-1] + rpow[ans[top]] * c - S[hd[top]+ans[top]]) * rinv;
fr[1][0][top] = fr[1][0][top-1] * rate + c - rpow[ans[top]] * S[hd[top]+ans[top]];
ed[0][0][top] = ed[0][0][top-1];
ed[1][0][top] = ed[1][0][top-1];
}
getMore();
return ;
}
int main() {
getinv();
top = 1;
hd[1] = maxn; tl[1] = maxn - 1; ans[1] = 0;
rep(rev, 0, 1) rep(add, 0, 1) fr[rev][add][1] = ed[rev][add][1] = 0;
int q = read(), lst = 0; char c = Getchar(); LL sans = 0;
rpow[0] = 1; rep(i, 1, q + 1) rpow[i] = rpow[i-1] * rate;
while(!isdigit(c)) c = Getchar();
rep(i, 1, q) {
short op = c - '0', x = 0;
c = Getchar(); x = c - '0'; c = Getchar(); x = x * 10 + c - '0'; if(i < q) c = Getchar();
x = (x + lst) % 100;
if(op == 1) addr(x);
if(op == 2) addl(x);
if(op == 3) top -= x;
lst = ans[top];
// printf("%d %d: %d\n", op, x, lst);
sans += lst;
}
printf("%lld\n", sans);
return 0;
}
[Problem C]Alice and Bob VII
试题描述
从前，有 \(n\) 个盒子（编号从 \(1\) 到 \(n\)），\(m\) 把钥匙（编号从 \(1\) 到 \(m\)）和 \(d\) 个商店（编号从 \(1\) 到 \(d\)）。编号为 \(i\) 的钥匙可以打开编号为 \(a_{i,1},a_{i,2},\cdots,a_{i,k_i}\) 的盒子。但是，一把钥匙一旦打开了一个盒子，它会立刻消失。因此，一把钥匙不能打开多个盒子。编号为 \(i\) 的钥匙只在商店 \(s_i\) 出售，价格为 \(c_i\)
个金币。Alice 不能多次购买同一把钥匙。现在，Alice 想买一些钥匙来打开所有的盒子。
Bob 想来捣乱。他可以在 Alice 决定购买钥匙之前改变某些钥匙的价格。如果 Bob 支付 \(b_j\) 个金币，Bob 就可以将商店 \(j\) 中所有钥匙的价格全部提高 \(1\) 金币。对于每家商店，他可以重复上述过程任意非负整数次。例如：如果他支付 \(2b_j\) 个金币，他可以将商店 \(j\) 中所有钥匙的价格全部提高 \(2\) 金币；但是，他不能支付 \(\frac{b_j}{2}\) 个金币来将价格提高 \(0.5\) 金币。
Alice 的目的是最小化 \((Alice支付的金币 - Bob支付的金币)\)，Bob 的目的是最大化该值。假设 Alice 和 Bob 都以最优策略来操作，请你计算最终该值是多少。
如果该值为无穷大，输出 \(-1\)。
数据保证如果 Bob 不来捣乱，Alice 是可以打开所有盒子的。
输入
第一行三个整数 \(n,m,d(1 \le n \le 100,1 \le m \le 1000,1 \le n,d \le m)\)
接下来 \(m\) 行，每行表示一把钥匙。每行开头有三个整数 \(c_i,s_i,k_i\) ，分别表示钥匙价格，钥匙出售商店的编号，这把钥匙能打开多少个盒子。接下来 \(k_i\) 个整数，表示这把钥匙能打开的盒子的编号。\((1 \le c_i \le 1000,1 \le s_i \le d,1 \le k_i \le \mathrm{min}(10,n),1 \le a_i,j \le n, and\ if\ j \ne k,a_{i,j} \ne a_{i,k})\)
接下来 \(d\) 行，每行一个整数 \(b_i(1 \le b_i \le 1000)\)。
输出
输出一个整数表示答案。
输入示例1
3 4 1
2 1 2 1 2
2 1 2 2 3
2 1 2 3 1
3 1 3 1 2 3
5
输出示例1
6
输入示例2
3 4 1
2 1 2 1 2
2 1 2 2 3
2 1 2 3 1
3 1 3 1 2 3
2
输出示例2
-1
输入示例2
2 3 2
3 1 2 1 2
4 1 1 2
5 2 2 1 2
1
2
输出示例2
8
数据规模及约定
对于 \(30\%\) 的数据，\(1 \le n \le 5, 1 \le m \le 10\)
对于所有数据，\(1 \le n \le 100, 1 \le m \le 1000, 1 \le n,d \le m\)
题解
这是一道处于未知领域的题……要用到拉格朗日乘数法证明它的正确性，但是仔细想一想发现还是证明不了，把原题解丢在这里吧，作为一个未解问题。（或许这题彻头彻尾地错了呢？）
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <vector>
using namespace std;
#define rep(i, s, t) for(int i = (s), mi = (t); i <= mi; i++)
#define dwn(i, s, t) for(int i = (s), mi = (t); i >= mi; i--)
int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
#define maxn 2110
#define maxm 24210
#define oo 2147483647
struct Edge {
int from, to, flow, cost;
Edge() {}
Edge(int _1, int _2, int _3, int _4): from(_1), to(_2), flow(_3), cost(_4) {}
} es[maxm];
struct ZKW {
int n, m, s, t, cost, ans, head[maxn], nxt[maxm];
Edge es[maxm];
int d[maxn], Q[maxn], hd, tl;
bool inq[maxn];
bool vis[maxn];
void init() {
m = 0; memset(head, -1, sizeof(head));
return ;
}
void setn(int _) {
n = _;
return ;
}
void AddEdge(int a, int b, int c, int d) {
es[m] = Edge(a, b, c, d); nxt[m] = head[a]; head[a] = m++;
es[m] = Edge(b, a, 0, -d); nxt[m] = head[b]; head[b] = m++;
return ;
}
int Nxt(int x) { return (x + 1) % maxn; }
bool BFS() {
rep(i, 1, n) d[i] = oo;
d[t] = 0;
hd = tl = 0; Q[tl = Nxt(tl)] = t; inq[t] = 1;
while(hd != tl) {
int u = Q[hd = Nxt(hd)]; inq[u] = 0;
for(int i = head[u]; i != -1; i = nxt[i]) {
Edge& e = es[i^1];
if(e.flow && d[e.from] > d[u] + e.cost) {
d[e.from] = d[u] + e.cost;
if(!inq[e.from]) inq[e.from] = 1, Q[tl = Nxt(tl)] = e.from;
}
}
}
if(d[s] == oo) return 0;
cost = d[s];
return 1;
}
int DFS(int u, int a) {
if(u == t || !a) return ans += cost * a, a;
if(vis[u]) return 0;
vis[u] = 1;
int flow = 0, f;
for(int i = head[u]; i != -1; i = nxt[i]) {
Edge& e = es[i];
if(d[e.to] == d[u] - e.cost && (f = DFS(e.to, min(a, e.flow)))) {
flow += f; a -= f;
e.flow -= f; es[i^1].flow += f;
if(!a) return flow;
}
}
return flow;
}
int MaxFlow(int _s, int _t) {
s = _s; t = _t;
int flow = 0, f;
while(BFS())
do {
memset(vis, 0, sizeof(vis));
f = DFS(s, oo);
flow += f;
} while(f);
return flow;
}
} sol;
int CntP;
struct Point {
int id;
Point(): id(0) {}
int p() { return id ? id : id = ++CntP; }
} box[maxn], key[maxn], shop[maxn], S, T;
vector <int> idm[maxn];
int addcost[maxn];
int main() {
int bx = read(), ky = read(), shp = read();
sol.init();
rep(i, 1, ky) {
int pri = read(), sid = read(), k = read();
idm[sid].push_back(sol.m);
sol.AddEdge(shop[sid].p(), key[i].p(), 1, pri);
rep(j, 1, k) sol.AddEdge(key[i].p(), box[read()].p(), 1, 0);
}
rep(i, 1, shp) sol.AddEdge(S.p(), shop[i].p(), addcost[i] = read(), 0);
rep(i, 1, bx) sol.AddEdge(box[i].p(), T.p(), 1, 0);
sol.setn(CntP);
if(sol.MaxFlow(S.p(), T.p()) < bx) return puts("-1"), 0;
printf("%d\n", sol.ans);
return 0;
}