本文主要是介绍Problem A: Bird，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
考虑到集训篇题目有点少。
我再写两篇QAQ
emmm一开始没有想法，甚至连暴力都不知道…最后交了一个40分傻逼费用流…
正解：首先肯定能发现如果对于一条边，正着跑了一次，反着跑了一次，那么这两次其实可以抵消掉（实际就费用流的思想） 考虑到树高实际只有log，那么用f[i]表示i的子树到i的最小花费，那么模拟费用流，在x的所有祖先上求一次min(f[x])
就可以得到应该在哪个点的子树取到最小值，然后暴力更改即可
c++代码如下：
#include<bits/stdc++.h>
#define rep(i,x,y) for(register int i = x; i <= y; ++ i)
#define repd(i,x,y) for(register int i = x ; i >= y; -- i)
using namespace std;
typedef long long ll;
inline char gc(){static char now[1<<16],*S,*T;if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}return *S++;
}
template<typename T>inline void read(T&x)
{x = 0;char c;int sign = 1;do { c = gc(); if(c == '-') sign = 1; }while(!isdigit(c));do { x = x * 10 + c - '0'; c = gc(); }while(isdigit(c));x *= sign;
}
const int OUT_LEN = 1024 * 1024;
char obuf[OUT_LEN], *oh = obuf;
inline void write_char(char c) {if (oh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf;*oh++ = c;
}template<class T>
inline void W(T x) {static int buf[30], cnt;if (x == 0) write_char('0');else {if (x < 0) write_char('-'), x = -x;for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48;while (cnt) write_char(buf[cnt--]);}
}inline void flush() {fwrite(obuf, 1, oh - obuf, stdout);
}const int N = 6e5 + 50;
int n,m,f[N],c[N],p[N];
int mark1[N],mark2[N];void dfs(int x)
{if(x > n) return ;f[x] = 0x3f3f3f3f;if(c[x]) f[x] = 0;dfs(x << 1); dfs(x << 1|1);f[x] = min(f[x],min(f[x << 1] + 1,f[x << 1|1] + 1));
}void update(int x)
{if(!x) return;f[x] = 0x3f3f3f3f;if(c[x]) f[x] = 0;f[x] = min(f[x],min(f[x << 1] + (mark1[x << 1] > 0 ? -1 : 1),f[x << 1|1] + (mark1[x << 1|1] > 0 ? -1 : 1)));update(x >> 1);
}int solve(int x)
{int k = f[x],num = 0x3f3f3f3f,y = x,p = 0,ans = 0;while(x){if(f[x] + p < num) k = x,num = f[x] + p;if(mark2[x]) --p; else ++p;x = x >> 1;}x = y;while(x != k){if(mark2[x]) -- mark2[x],-- ans;else ++mark1[x],++ ans;x = x >> 1;}if(c[x]) { --c[x]; update(y); return ans; }while(!c[x]){if(f[x << 1] + (mark1[x << 1] > 0 ? -1 : 1) < f[x << 1|1] + (mark1[x << 1|1] > 0 ? -1 : 1)){if(mark1[x << 1] > 0) --mark1[x << 1], -- ans;else ++mark2[x << 1],++ans;x = x << 1;}else{if(mark1[x << 1|1] > 0) --mark1[x << 1|1], -- ans;else ++mark2[x << 1|1],++ans;x = x << 1|1;}}-- c[x];update(y); update(x);return ans;
}int main()
{memset(f,0x3f,sizeof f);read(n); read(m);rep(i,1,n) read(c[i]);rep(i,1,m) read(p[i]);dfs(1);int ans = 0;rep(i,1,m){ans += solve(p[i]);printf("%d ",ans);}flush();return 0;
}这篇关于Problem A: Bird的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
