[WC2008]游览计划 题解 & 斯坦纳树类题目解法
题目地址:ė …
May all the beauty be blessed.
题目地址:BZOJ:Problem 3900. — 交换茸角
动物园里有 n 头麋鹿。每头麋鹿有两支茸角,每支茸角有一个重量。然而,一旦某头麋鹿上两支茸角的重量之差过大,这头麋鹿就会失去平衡摔倒。为了不然这种悲剧发生,动物园院长决定交换某些茸角,使得任意一头麋鹿的两角重量差不超过 c。然而,交换两支茸角十分麻烦,不仅因为茸角需要多个人来搬运,而且会给麋鹿造成痛苦。因此,你需要计算出最少交换次数,使得任意一头麋鹿的两角重量差不超过 c。
注意,交换两支茸角只能在两头麋鹿之间进行。因为交换同一头麋鹿的两支角是没有意义的。
输入格式:
第一行为整数 n,c。接下来 n 行,每行两个整数,分别表示一开始每头麋鹿的两角重量。
输出格式:
一个数,即最少交换次数。如果无论如何也不能使每头麋鹿平衡,输出 -1。
输入样例#1:
3 0 3 3 2 5 2 5
输出样例#1:
1
对于 100% 的数据,n <= 16, c <= 1000000, 每支茸角重量不超过 1000000。
这个n的范围看起来很像状压DP,那我们就往那个方向去想。
我们考虑用状压表示子集,dp[S]表示S集合中的所有鹿换角最少多少次能满足条件。对于初始值,我们把S集合中的鹿的所有角都拿出来排个序分好组,如果发现有一组角的差值大过c,那么这个集合内部就无法自行调整为满足条件的情况,dp值应设置为INF。如果集合内部已经满足条件,dp值应设置为0。如果都不是上面的情况,那么按照最差的换法,应该是每个鹿从待选角中找到配对的角换上,这个次数最差是集合内鹿的数量-1的,dp值应设置为这个最差的值。
对于转移,我们考虑枚举每个状态S的子集T,有下面的方程
dp[S] = \min(dp[S], dp[T] + dp[S \wedge T])
这个的复杂度是O(2^n \cdot n)的。
// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1;
char c = fgc();
while(c < '0' || c > '9') {
if(c == '-') neg = -1;
c = fgc();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = fgc();
}
return res * neg;
}
const int MAXN = 17, INF = 0x3f3f3f3f;
int n, c, a[MAXN], b[MAXN], dp[1 << MAXN];
std::vector<int> tmp;
int main() {
n = readint();
c = readint();
for(int i = 1; i <= n; i++) {
a[i] = readint();
b[i] = readint();
}
memset(dp, 0x3f, sizeof(dp));
dp[0] = 0;
for(int i = 1; i < (1 << n); i++) {
bool flag = false;
tmp.clear();
for(int j = 1; j <= n; j++) {
if(i & (1 << (j - 1))) {
if(std::abs(a[j] - b[j]) > c) flag = true;
tmp.push_back(a[j]);
tmp.push_back(b[j]);
}
}
if(!flag) {
dp[i] = 0;
continue;
}
std::sort(tmp.begin(), tmp.end());
flag = false;
for(int j = 0; j < tmp.size(); j += 2) {
if(tmp[j + 1] - tmp[j] > c) {
flag = true;
break;
}
}
if(!flag) dp[i] = tmp.size() / 2 - 1;
}
for(int i = 1; i < (1 << n); i++) {
for(int j = (i - 1) & i; j; j = (j - 1) & i) {
dp[i] = std::min(dp[i], dp[j] + dp[i ^ j]);
}
}
if(dp[(1 << n) - 1] == INF) {
printf("-1");
} else {
printf("%d", dp[(1 << n) - 1]);
}
return 0;
}
本篇题解借鉴和参考了洛谷题解区的同学所写的题解以及部分博文,由于未能记录全面,并没能将这些参考内容全部列出,为此对这些内容的作者感到抱歉。
NOIP2017已经结束啦。在华中科大计科实验室度过的7个小时犯了挺多的错误,现在想想,其实自己能上300。初次考试,题型有少许变化加上自己没有经验,成功爆炸。还好最后D1T2救了一下场。
接下来是题解和感想。
T1实在是太太太太太太拉分了orz
30,90,0
赛题 #A: P3951 小凯的疑惑 | 数论,找规律
赛题 #B: P3952 时间复杂度 | 大模拟,耐心
赛题 #C: P3953 逛公园 | 图论,记忆化搜索,k短路计数
求使px+qy=n无自然数范围内的解的最大正整数n。其中,p, q互质。
只需输出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;
}
千言万语汇成一句话:数论推个屁,打表找规律。铭记在心,终生受用。
维护一个管理循环的栈。由于循环从里到外结束,可用栈管理循环的嵌套关系。
细节比较多,如果该循环能够计入这一次的复杂度,则满足以下条件:
不计入复杂度但能执行的循环满足以下条件中任意的一条:
不能被执行的循环满足以下条件中任意的一条:
语法错误有3类:
对于不能被执行的循环,打标记并使之后的循环对答案无贡献,直到它出栈。逐循环计算它对总复杂度的贡献。只要把以上细节写全了就能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的路径数量。
最短路计数。(模板题:洛谷P1144、洛谷P1608)
在SPFA求最短路的时候加一个cnt数据记录到某点最短路的数量。如果一个点的最短路被更新,cnt重置为1,否则如果找到另外一条最短路,对cnt加一。
很容易设计一个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之前的我果然是个鶸。
第一次碰到纯粹的数据结构题,第一次碰到这么难的DP。
100,20,30
赛题 #A: P3958 奶酪 | BFS,并查集
赛题 #B: P3959 宝藏 | 状压DP,记忆化搜索
赛题 #C: P3960 列队 | 数据结构,线段树,平衡树
给一堆球体,有两个平行于xOy坐标平面的平面作为底面(z=0)和顶面(z=h),两个相交或者相切的球体可以视作联通,求是否能找到一条路径从底面到顶面去。
建图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是边本来的权值。
考虑使用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),每次求拿出的那个数是什么。
其实我们发现我们可以用一个长为m+q的线段树来维护这个序列。当每一次删点的时候记录哪些区间的子树里删了这个点,就可以统计出一个该区间内总共删掉的点数,然后每次查找第几个元素的时候以此为参考到它的左子树or右子树查找。至于多出来的那些个可能乱序的元素,就直接扔进vector然后如果要找就算一下下标。
对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