Problem A: Bird
程序员文章站
2022-06-03 19:39:51
...
考虑到集训篇题目有点少。
我再写两篇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;
}
上一篇: 历史上真实的高纬是什么样的人?
推荐阅读
-
Unity实现Flappy Bird游戏开发实战
-
Unity3d实现Flappy Bird游戏
-
HDU 2256Problem of Precision(矩阵快速幂)
-
cfE. Ehab and a component choosing problem(贪心)
-
Problem01 不死神兔
-
HDUacm 1000 A + B Problem
-
数据结构(线性结构习题)Problem A: 求集合的交并补集
-
Problem09 求完数
-
洛谷P1919 【模板】A*B Problem升级版(FFT快速傅里叶)
-
Notice: Trying to get property of non-object problem(PHP)解决办法