【LGR-074】洛谷 8 月月赛 I & MdOI Round 3

P6746 『MdOI R3』Operations

考虑我们到达两个数都是0的情况有几种可能:

1.第一个数和第二个数调到相等后直接操作1

这个首先可以,至于能不能,可以发现设A>B, $\lfloor\sqrt{\lfloor\frac A B \rfloor}\rfloor$ 就是可行的答案,如果这个答案操作后不能使之一样说明我们萎住了

2.第一个数和第二个数减去较小的数之后出现0,然后再操作2都是0了

然后他们的代价是一样的

3.我们两次操作2,第一次先消掉一个数变为0,第二次再消掉另一个数

4.如果相等一次操作1

注意0的情况

code:

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
ll a, b, c, d;
ll ans1, ans2;
int main() {
	scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
	if(a == 0 && b == 0)return puts("0"), 0;
	if(a == 0 || b == 0) {
		return printf("%lld\n", d), 0;
	}
	if(a == b) {
		ans1 = c;
		ans2 = 2 * d;
		printf("%lld\n", min(ans1, ans2));
	} else {
		ans1 = c + d;
		ans2 = 2 * d;
		printf("%lld\n", min(ans1, ans2));
	}
	return 0;
}

P6747 『MdOI R3』Teleport

显然异或具有交换性结合性

所以就是最大化小于m的这个东西

\sum_i a_i xor k * (n \% 2)

外面是求个,里面是异或,就能阻止我算每一位贡献了吗???

如果题面中的m是限制k的大小

考虑如果第i为为1有j个a_i,那么我们如果这一位k选择了1,我们最后就会多出n-j个2^{i,否则多出j个2}i

而显然的是我们高位多1不一定更优,所以数位dp一下

$dp_{i,0/1}$ 表示当前到第i位,卡没卡到上界,得到的最大和是什么

转移显然,做完了

如果是限制和的大小

先把贡献数组进位一下

然后我们直接考虑某一位能不能放1就好了....

~~说实话读错题了~~

等等这个东西好像违反了我们k的作用啊....QAQ

唉再等等我们最大化k???那没事了....我又读错题了....

还是有一点细节的...

code:


#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using std::min;
#define int long long
const int MAXN = 1e5 + 7;
int n, a[MAXN], q, cnt[MAXN];
ll m, V[MAXN], sum[MAXN];

inline void init() {
	for(int i = 1; i <= n; ++i) {
		for(int j = 0; j <= 30; ++j) {
			if((a[i] >> j) & 1) {
				cnt[j]++;
			}
		}
	}
	V[0] = 1;
	for(int j = 1; j <= 50; ++j) {
		V[j] = V[j - 1] * 2;
	}//init every sum
	sum[0] = min(cnt[0], n - cnt[0]);
	for(int j = 1; j <= 50; ++j) {
		sum[j] = sum[j - 1] + V[j] * min(cnt[j], n - cnt[j]);
		//确定前j位....
	}
	return ;
}


inline void solve() {
	ll k = 0;
	if(sum[50] > m)return (void)puts("-1");
	for(int j = 50; j >= 1; --j) {
		if((__int128)V[j] * (n - cnt[j]) + sum[j - 1] <= m) {
			k |= (1ll << j);
			m -= V[j] * (n - cnt[j]);
		} else {
			m -= V[j] * cnt[j];
		}
	}
	if((n - cnt[0]) <= m) {
		k++;
	}
	printf("%lld\n", k);
	return ;
}



signed main() {
	// freopen("test.in", "r", stdin);
	// freopen("test1.out", "w", stdout);
	scanf("%lld", &n);
	for(int i = 1; i <= n; ++i)scanf("%lld", &a[i]);
	init();
	scanf("%lld", &q);
	for(int i = 1; i <= q; ++i) {
		scanf("%lld", &m);
		solve();
	}
	return 0;
}

P6748 『MdOI R3』Fallen Lord

考虑度数为1的叶子,他们可以直接确定父亲到那条边的权值

确定完之后我们考虑父亲可能会自闭,就是他到父亲那条边怎么调整都不能使得合法了,所以要减小儿子边

脑补一下那个序列,我们可以使得父亲边取到m,然后当前新中位数到 $a_i$ 区间所有值都调整到中位数

或者当前父亲边取到中位数,然后当前新中位数到 $a_i$ 区间所有值都调整到中位数...

这样不停做下去就好了...

但是这样我肯定没了啊,因为显然我一条边会对两个端点的答案产生影响,所以单调状态不太行

考虑DP

会发现我们无论如何都只有3种取值: $=a_{son},=a_{fa},=m$

而一个数成为中位数要是有 $\lfloor \frac k 2 \rfloor$ 个数比他小于等于的

所以我们设计一个dp状态, $dp_{0,1,2}$ 表示点i->fai这条边权值 $=a_{son},=a_{fa},=m$ 时最大子树权值和qwq

会发现我们的root没有这样一条边啊,完蛋了...

重新设计状态,f,g数组拆开

$f_{u,0/1}$ 表示i->fai这条边权值小于等于/大于 $a_u$ 时候子树内满足条件边权最大值..

$g_{u,0/1}$ 表示i->fai这条边权值小于等于/大于 $a_{fa{u}}$ 时候,包括那条边子树内...边权最大值

考虑转移QAQ,这里可以用前面的思路了!

已知儿子的g怎么求父亲f?

首先全部小于等于 $a[fa_u]$ 的 $g_{v,0}$ 全选上,然后对于父亲的 $f_0$ ,我们有 $d_u-(d_u/2+1)$ 条边可以设置为m,另种情况 $f_{1}$ 则是 $d_u-(d_u/2+1)-1$ ,然后从大到小的枚举k个 $f_{v,1}-f_{v,0}$ 即可替换转移....

然后已知一个点的f求g?....

如果 $a_u<=a_fa_u$

$f_{u,0}->g_{u,0}$ 那么我们这条边选择 $a_u$

$f_{u,1}->g_{u,0}$ 那么我们这条边选择 $a_fa_u$

$f_{u,1}->g_{u,1}$ 那么我们这条边选择 $m$

$a_u>a_fa_u$

$f_{u,0}->g_{u,0}$ 那么我们这条边选择 $a_fa_u$

$f_{u,0}->g_{u,1}$ 那么我们这条边选择 $a_u$

$f_{u,1}->g_{u,1}$ 那么我们这条边选择 $m$

综上下(累死了QAQ)

g_{u,0}=max(f_{u,0}+a_u,f_{u,1}+a_fa_u) || f_{u,0}+a_fa_u

g_{u,1}=max(f_{u,1}+m,f_{u,0}+a_u) || f_{u,1}+m

终于做完了....

如果一个点度数<=2,那么 $f_{u,1}$ 是不合法的,所以设置为-inf

code:


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int MAXN = 5e5 + 7;
const int MAXM = 1e6 + 7;
const ll inf = 1e16;
int n, m;
int a[MAXN], in[MAXN];
int ccnt, home[MAXN], nxt[MAXM], to[MAXM];
inline void ct(int x, int y) {
	ccnt++;
	nxt[ccnt] = home[x];
	home[x] = ccnt;
	to[ccnt] = y;
}

ll f[MAXN][2], g[MAXN][2], que[MAXN];

inline void dfs(int u, int F) {
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v == F)continue;
		dfs(v, u);
	}
	int tot = 0;
	ll tmp = 0;
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v == F)continue;
		que[++tot] = g[v][1] - g[v][0];
		f[u][0] += g[v][0];
	}
	sort(que + 1, que + tot + 1);
	int Can = in[u] - (in[u] / 2 + 1);
	// printf("%d?\n", Can);
	//小于0说明没值啊....
	for(int i = tot; i >= tot - Can + 1 && que[i] > 0; --i) {
		f[u][0] += que[i];
	}
	f[u][1] = f[u][0];
	if(que[tot - Can + 1] > 0)
		f[u][1] -= que[tot - Can + 1];
	if(in[u] <= 2)f[u][1] = -inf;
	if(a[u] <= a[F]) {
		g[u][0] = max(f[u][0] + a[u], f[u][1] + a[F]);
		g[u][1] = f[u][1] + m;
	} else {
		g[u][0] = f[u][0] + a[F];
		g[u][1] = max(f[u][1] + m, f[u][0] + a[u]);
	}
	// printf("now we finish ->:!!%lld %lld %lld %lld %lld %lld\n", u, F, g[u][1], g[u][0], f[u][1], f[u][0]);
	return ;
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", a + i);
	}
	for(int i = 2, x, y; i <= n; ++i) {
		scanf("%d%d", &x, &y);
		ct(x, y);
		ct(y, x);
		in[x]++;
		in[y]++;
	}
	dfs(1, 0);//getans
	printf("%lld\n", f[1][0]);
	return 0;
}

小心fst吧....QAQ

P6749 『MdOI R3』Yoshino

不是人做的题

然额我们能看见n,m<=3e4这个条件!

也就是说如果暴力可行的话就可以暴力啦!

我们先O(nlogn)求出原来的答案

然后会发现这个修改内部不产生贡献,所以我们可以只考虑原来区间和新区间的贡献

首先,对于这个区间的前面的区间某个数V,他一定满足i<j,那么贡献就是这个区间内小于他的数个数, $V-x$

其次对于区间后面的某个数V,一定满足i>j,贡献是 $x+r-l+1-V$

在区间外的要小心判断下....就是L,R的限制

然后考虑原区间的贡献消除....好像我们只能差分然后前缀和了!....

好吧看来这一步跑满了的....O3!

当然正解好像是树套树,不过相信被爆锤了把?

我永远喜欢约战

夏晓光(loveJY)的博客

【LGR-074】洛谷 8 月月赛 I & MdOI Round 3

ZRB班D1图论