DP的花式优化方法
本文章可能Ç …
标签： 数据结构
NOIP2017提高组题解&总结
本篇题解借鉴和参考了洛谷题解区的同学所写的题解以及部分博文，由于未能记录全面，并没能将这些参考内容全部列出，为此对这些内容的作者感到抱歉。
NOIP2017已经结束啦。在华中科大计科实验室度过的7个小时犯了挺多的错误，现在想想，其实自己能上300。初次考试，题型有少许变化加上自己没有经验，成功爆炸。还好最后D1T2救了一下场。
接下来是题解和感想。
NOIP2017 提高组 Day1
吐槽
T1实在是太太太太太太拉分了orz
个人成绩
30，90，0
题目列表（评测来自洛谷）
赛题 #A: P3951 小凯的疑惑 | 数论，找规律
赛题 #B: P3952 时间复杂度 | 大模拟，耐心
赛题 #C: P3953 逛公园 | 图论，记忆化搜索，k短路计数
小凯的疑惑
一句话题意
求使px+qy=n无自然数范围内的解的最大正整数n。其中，p, q互质。
解法
100% 1 \leq a, b \leq 10^9
只需输出pq - p - q即可。
证明：试使用反证法
假设存在正整数x, y使px + qy = pq - p - q
则有p(x+1)+q(y+1)=pq
易知p|q(y+1)
\because gcd(p, q)=1
\therefore p|y+1
同理q|x+1
令y+1=pj, x+1=qk
则有pqk+qpj=pq
也就是pq(j+k)=pq
\because j+k=x+y+2 \geq 2
上式并不成立，得证。
但是考场上推出这个方法应该打表找规律。
还有一种扩欧推出的方法，更多题解可以看洛谷题解 P3951 – 百科 – 洛谷。
代码
// Code by KSkun, 2017/11
#include <cstdio>
int main() {
int a, b;
scanf("%d%d", &a, &b);
printf("%lld", 1ll * a * b - a - b);
return 0;
}
总结
千言万语汇成一句话：数论推个屁，打表找规律。铭记在心，终生受用。
时间复杂度
没有概括，自己看洛谷
解法
100% L \leq 100
维护一个管理循环的栈。由于循环从里到外结束，可用栈管理循环的嵌套关系。
细节比较多，如果该循环能够计入这一次的复杂度，则满足以下条件：
- 之前不能有不能执行的循环
- 循环的终点是n
不计入复杂度但能执行的循环满足以下条件中任意的一条：
- 起点和终点都是常数，且起点小于等于终点
- 起点和终点都是n
不能被执行的循环满足以下条件中任意的一条：
- 起点是n
- 起点和终点都是常数，且起点小于终点
语法错误有3类：
- 变量名冲突（vis管理一下）
- E语句结束了不存在的循环（判断栈是否为空）
- 结束指令后仍有未关闭的循环（同2）
对于不能被执行的循环，打标记并使之后的循环对答案无贡献，直到它出栈。逐循环计算它对总复杂度的贡献。只要把以上细节写全了就能A。
代码
// Code by KSkun, 2017/11
#include <cstdio>
#include <cstring>
#include <stack>
#include <algorithm>
struct Loop {
char var;
int beg, end;
Loop(char var, int beg, int end): var(var), beg(beg), end(end) {}
};
inline int getComp(char *str) {
if(str[2] == 'n') {
int res = 0, len = strlen(str);
for(int i = 4; i < len; i++) {
if(str[i] == ')') break;
res = res * 10 + str[i] - '0';
}
return res;
}
return 0;
}
inline int getNum(char *str) {
if(str[0] == 'n') return -1;
int res = 0, len = strlen(str);
for(int i = 0; i < len; i++) {
res = res * 10 + str[i] - '0';
}
return res;
}
bool vis[50], iserr;
char op[5], var[5], beg[5], end[5], complexity[100], notValid;
int t, l, now, all, exp;
std::stack<Loop> sta;
int main() {
//freopen("p3952.in", "r", stdin);
scanf("%d", &t);
while(t--) {
memset(vis, 0, sizeof vis);
while(!sta.empty()) sta.pop();
iserr = false;
notValid = '-';
now = all = 0;
scanf("%d%s", &l, complexity);
exp = getComp(complexity);
while(l--) {
scanf("%s", op);
if(op[0] == 'F') {
scanf("%s%s%s", var, beg, end);
// ERR proccess
if(vis[var[0] - 'a']) {
iserr = true;
continue;
}
// non-ERR process
if(iserr) continue;
vis[var[0] - 'a'] = true;
Loop t = Loop(var[0], getNum(beg), getNum(end));
sta.push(t);
if(((t.beg == -1 && t.end != -1) || (t.beg != -1 && t.end != -1 && t.beg > t.end)) && notValid == '-') {
// if this is the first loop that any loop after it will not run.
notValid = t.var;
}
if(notValid != '-') continue;
if(t.end == -1 && t.beg != -1) {
now++;
}
} else if(op[0] == 'E') {
// ERR proccess
if(sta.empty()) {
// if stack is empty when trying to proccess an 'E' command
iserr = true;
continue;
}
// non-ERR proccess
if(iserr) continue;
Loop t = sta.top();
sta.pop();
vis[t.var - 'a'] = false;
if(t.var == notValid) {
notValid = '-';
}
if(notValid != '-') continue;
all = std::max(all, now); // always update all complexity value
if(t.end == -1 && t.beg != -1) {
now--;
}
}
}
if(!sta.empty()) {
// if stack is still not empty when all commands are inputed
iserr = true;
}
if(iserr) {
printf("ERR\n");
} else if(all == exp) {
printf("Yes\n");
} else {
printf("No\n");
}
}
return 0;
}
总结
考场上可能是没考虑周全，思路也比较乱，导致写出来代码很乱而且只有90，没能A掉。是一个遗憾。这种大模拟，重要的就是给自己偷懒，把能复用的代码写函数，能包的包起来，并且思路清晰分模块编写就好。本以为再也不会碰到这种大模拟题了，CCF在搞啥啊orz
逛公园
一句话题意
给一个有向图，求从1到N点长度不超过最短路径+K的路径数量。
解法
30% K = 0
最短路计数。（模板题：洛谷P1144、洛谷P1608）
在SPFA求最短路的时候加一个cnt数据记录到某点最短路的数量。如果一个点的最短路被更新，cnt重置为1，否则如果找到另外一条最短路，对cnt加一。
100% 1 \leq N \leq 100000, 1 \leq M \leq 200000, 0 \leq K \leq 50
很容易设计一个DP状态为dp[u][k]表示u点比最短路长k的路径数量，而初始dp[1][0]为1。规定dis数组为1到每个点的最短路距离，对于u点的所有入边（入边长度为len）的起点v，转移如下
dp[u][k] = \sum dp[v][dis[u]-dis[v]+k-len]
如果用SPFA转移，要考虑转移的状态是否已经计算过。我们规定转移的顺序是优先转移dis小的点，因此我们要保持转移队列的优先级有序。
但如果这个转移可以从N点开始，在反图上转移就不存在上面的问题。这种方案我们可以采用记忆化搜索。这道题时限有3s，能够满足需要。
那么0边如何处理？记忆化搜索不需要管0边，但是如果搜索的过程中遇到了一个0环，那么这个环任意跑多少圈都是一条可取的路径，这种情况是无解的，因此要在搜索过程中记录下搜索状态(u, k)是否已经在搜索栈中，可以用vis数组来处理一下。如果在栈中，就说明存在0环。
另外有一个很玄学的问题，搜索的最后要加一行dfs(N, K + 1);，否则就会有数据跑不过去，例如这一组数据
2 2 0 50 1 2 0 2 1 0
答案应该为-1，但是如果不加那一行答案就是1了。然而洛谷的数据好像不加那一行也能过，我不是很清楚原理是啥。
代码
// Code by KSkun, 2018/1
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
struct io {
char buf[1 << 26], *s;
io() {
fread(s = buf, 1, 1 << 26, stdin);
}
inline int read() {
register int res = 0, neg = 1;
while(*s < '0' || *s > '9') {
if(*s == '-') neg = -1;
s++;
}
while(*s >= '0' && *s <= '9') res = res * 10 + *s++ - '0';
return res * neg;
}
};
io ip;
#define read ip.read
struct Edge {
int to, w;
Edge(int to, int w): to(to), w(w) {}
};
std::vector<Edge> vec[100005], rev[100005];
inline void addedge(int u, int v, int w) {
vec[u].push_back(Edge(v, w));
rev[v].push_back(Edge(u, w));
}
int T, N, M, K, P, ut, vt, wt, dis[100005], dp[100005][55], ans;
bool vis[100005][55], zcircle;
std::queue<int> que;
bool inque[100005];
inline void spfa(int st) {
memset(dis, 0x3f, sizeof dis);
memset(inque, 0, sizeof inque);
que.push(st);
dis[st] = 0;
inque[st] = true;
while(!que.empty()) {
int u = que.front();
que.pop();
inque[u] = false;
for(int i = 0; i < vec[u].size(); i++) {
int v = vec[u][i].to;
if(dis[v] > dis[u] + vec[u][i].w) {
dis[v] = dis[u] + vec[u][i].w;
if(!inque[v]) {
inque[v] = true;
que.push(v);
}
}
}
}
}
inline int dfs(int u, int k) {
//printf("u %d k %d\n", u, k);
if(vis[u][k]) {
zcircle = true;
return -1;
}
if(dp[u][k] != -1) return dp[u][k];
vis[u][k] = true;
dp[u][k] = 0;
for(int i = 0; i < rev[u].size(); i++) {
int v = rev[u][i].to;
int delta = dis[u] - dis[v] + k - rev[u][i].w;
//printf(" v %d delta %d\n", v, delta);
if(delta < 0) continue;
dp[u][k] = (0ll + dp[u][k] + dfs(v, delta)) % P;
if(zcircle) return -1;
}
vis[u][k] = false;
return dp[u][k];
}
int main() {
T = read();
while(T--) {
memset(dp, -1, sizeof dp);
memset(vis, 0, sizeof vis);
zcircle = false;
ans = 0;
N = read();
M = read();
K = read();
P = read();
for(int i = 1; i <= N; i++) {
vec[i].clear();
rev[i].clear();
}
for(int i = 0; i < M; i++) {
ut = read();
vt = read();
wt = read();
addedge(ut, vt, wt);
}
spfa(1);
dp[1][0] = 1;
for(int i = 0; i <= K; i++) {
ans = (0ll + ans + dfs(N, i)) % P;
}
dfs(N, K + 1);
if(zcircle) {
printf("-1\n");
} else {
printf("%d\n", ans);
}
}
return 0;
}
总结
图论+DP的写法是第一次碰到，最短路计数的骗分也不会写，NOIP之前的我果然是个鶸。
NOIP2017 提高组 Day2
吐槽
第一次碰到纯粹的数据结构题，第一次碰到这么难的DP。
个人成绩
100，20，30
题目列表（评测来自洛谷）
赛题 #A: P3958 奶酪 | BFS，并查集
赛题 #B: P3959 宝藏 | 状压DP，记忆化搜索
赛题 #C: P3960 列队 | 数据结构，线段树，平衡树
奶酪
一句话题意
给一堆球体，有两个平行于xOy坐标平面的平面作为底面（z=0）和顶面（z=h），两个相交或者相切的球体可以视作联通，求是否能找到一条路径从底面到顶面去。
解法
100% 1 \leq N \leq 1000
建图BFS或者并查集检查是否有底面-顶面球体对在同一集合内都可以解决这个问题。题目本身并不难，而且默认了z坐标为正也不会爆long long。
代码
// Code by KSkun, 2018/1
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
struct Ball {
int x, y, z;
Ball(int x, int y, int z): x(x), y(y), z(z) {}
};
std::vector<Ball> balls;
std::vector<int> vec[1005];
std::queue<int> que;
bool top[1005], success, vis[1005];
int T, n, h, r, x, y, z;
inline long long dis(int a, int b) {
long long x = 1ll * (balls[a].x - balls[b].x) * (balls[a].x - balls[b].x),
y = 1ll * (balls[a].y - balls[b].y) * (balls[a].y - balls[b].y),
z = 1ll * (balls[a].z - balls[b].z) * (balls[a].z - balls[b].z);
return x + y + z;
}
inline bool can(int a, int b) {
return dis(a, b) <= 1ll * r * r * 4;
}
int main() {
scanf("%d", &T);
while(T--) {
success = false;
while(!que.empty()) que.pop();
memset(top, 0, sizeof top);
memset(vis, 0, sizeof vis);
balls.clear();
scanf("%d%d%d", &n, &h, &r);
for(int i = 1; i <= n; i++) {
vec[i].clear();
}
for(int i = 1; i <= n; i++) {
scanf("%d%d%d", &x, &y, &z);
balls.push_back(Ball(x, y, z));
if(std::abs(h - z) <= r) top[i] = true;
if(std::abs(z) <= r) que.push(i);
for(int j = 0; j < balls.size() - 1; j++) {
if(can(i - 1, j)) {
vec[i].push_back(j + 1);
vec[j + 1].push_back(i);
}
}
}
// BFS
while(!que.empty()) {
int u = que.front();
que.pop();
if(top[u]) {
success = true;
break;
}
vis[u] = true;
for(int i = 0; i < vec[u].size(); i++) {
int v = vec[u][i];
if(!vis[v]) {
que.push(v);
}
}
}
if(success) {
printf("Yes\n");
} else {
printf("No\n");
}
}
return 0;
}
感想
当时写的时候还在纠结是不是要爆ll，然后开了ull。后来发现我多虑了。好多人都栽在这个题上。我当时写的大常数BFS是能在老爷机上A了的，所以并不清楚发生了什么。
宝藏
一句话题意
给一个无向图，让你找一个最小生成树，生成树的每条边产生Z \times W的代价，其中Z是该边起点到指定根的距离（每条边长度为1），W是边本来的权值。
解法
100% 1 \leq n \leq 12, 0 \leq m \leq 1000
考虑使用dis数组记录每个点到指定根的距离，然后设计状压DP，dp[S]表示已经加入生成树的点为S的时候的最佳方案。
转移直接使用搜索即可。对于集合S中的每一个点尝试转移到它们的下层点。如果发现下层点的状态方案不是最优，则更新最优并搜索下去，否则回溯。
然后枚举指定根，每一次都搜一遍。
代码相当短，题目本身也并不是很难，就是一个大暴力。
代码
// Code by KSkun, 2018/1
#include <cstdio>
#include <cstring>
#include <algorithm>
const int INF = 0x3f3f3f3f;
int n, m, gra[15][15], dis[15], dp[1 << 13], ans = INF, ut, vt, wt;
inline int dfs(int s) {
for(int i = 1; i <= n; i++) {
// if the point has been chosen
if(s & (1 << (i - 1))) {
for(int j = 1; j <= n; j++) {
// if the goal is reachable and hasn't been chosen
if(!(s & (1 << (j - 1))) && gra[i][j] != INF) {
// if there is a better solution
if(dp[s | 1 << (j - 1)] > dp[s] + dis[i] * gra[i][j]) {
int lst = dis[j];
dis[j] = dis[i] + 1;
dp[s | 1 << (j - 1)] = dp[s] + dis[i] * gra[i][j];
dfs(s | 1 << (j - 1));
dis[j] = lst;
}
}
}
}
}
}
int main() {
memset(gra, 0x3f, sizeof gra);
memset(dis, 0x3f, sizeof dis);
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i++) {
scanf("%d%d%d", &ut, &vt, &wt);
gra[ut][vt] = gra[vt][ut] = std::min(gra[ut][vt], wt);
}
// choose who is the root
for(int i = 1; i <= n; i++) {
memset(dis, 0x3f, sizeof dis);
memset(dp, 0x3f, sizeof dp);
dis[i] = 1;
dp[1 << (i - 1)] = 0;
dfs(1 << (i - 1));
ans = std::min(ans, dp[(1 << n) - 1]);
}
printf("%d", ans);
return 0;
}
感想
考场上在想为什么今天还没出DP题以及这题怎么看怎么像生成树，然后疯狂想办法证贪心，然后GG。考完试一个华一大佬告诉我就是个贪心生成树，然后他也GG了，233。
列队
一句话题意
有一个n \times m的矩阵，每次从(x, y)拿出一个数并且删掉它，然后左对齐、上对齐，再把拿出的这个数插入(n, m)位置。给定很多(x, y)，每次求拿出的那个数是什么。
解法
30% n = 1
其实我们发现我们可以用一个长为m+q的线段树来维护这个序列。当每一次删点的时候记录哪些区间的子树里删了这个点，就可以统计出一个该区间内总共删掉的点数，然后每次查找第几个元素的时候以此为参考到它的左子树or右子树查找。至于多出来的那些个可能乱序的元素，就直接扔进vector然后如果要找就算一下下标。
100% 1 \leq n, m, q \leq 3 \times 10^5
对30%的做法进行延伸，我们可以发现，这个题需要n+1棵线段树，对应n行的前m-1个元素和最后一列，每一次在该行中删除一个元素，然后在最后一列中删一个元素加入该行，再往最后一列中加入一个元素。这样一来，思路就很明确了。
代码
// Code by KSkun, 2018/1
#include <cstdio>
#include <algorithm>
#include <vector>
struct io {
char buf[1 << 26], *s;
io() {
//freopen("p3960-13.in", "r", stdin);
//freopen("p3960-13.out", "w", stdout);
fread(s = buf, 1, 1 << 26, stdin);
}
inline int read() {
register int res = 0, neg = 1;
while(*s < '0' || *s > '9') {
if(*s == '-') neg = -1;
s++;
}
while(*s >= '0' && *s <= '9') res = res * 10 + *s++ - '0';
return res * neg;
}
};
io ip;
#define read ip.read
int n, m, q, x, y, N;
int lc[10000005], rc[10000005], del[10000005], root[300005], tot = 0;
std::vector<long long> vec[300005];
inline long long query(int o, int l, int r, int rnk) {
if(l == r) return l;
// res stands for how many points left subtree has
int mid = (l + r) >> 1, res = mid - l + 1 - del[lc[o]];
if(res >= rnk) return query(lc[o], l, mid, rnk);
else return query(rc[o], mid + 1, r, rnk - res);
}
inline void update(int &o, int l, int r, int rnk) {
if(!o) o = ++tot;
del[o]++;
if(l == r) return;
int mid = (l + r) >> 1;
if(mid >= rnk) update(lc[o], l, mid, rnk);
else update(rc[o], mid + 1, r, rnk);
}
inline long long del_line(int x, int y) {
long long res = query(root[x], 1, N, y);
update(root[x], 1, N, res);
return res < m ? 1ll * (x - 1) * m + res : vec[x][res - m];
}
inline long long del_row(int x) {
long long res = query(root[n + 1], 1, N, x);
update(root[n + 1], 1, N, res);
return res <= n ? 1ll * res * m : vec[n + 1][res - n - 1];
}
int main() {
n = read();
m = read();
q = read();
N = std::max(n, m) + q;
while(q--) {
x = read();
y = read();
if(y != m) {
long long res = del_line(x, y);
vec[n + 1].push_back(res);
printf("%lld\n", res);
vec[x].push_back(del_row(x));
} else {
long long res = del_row(x);
vec[n + 1].push_back(res);
printf("%lld\n", res);
}
}
return 0;
}
感想
从来没写过纯粹的数据结构题的我在考场上就是懵逼的qwq
