牛客寒假集训营第四场补题

yuanheci 2023年01月31日 348次浏览

1、B题《清楚姐姐学构造》

题目描述

清楚姐姐最近在学习构造类问题，她现在遇到这样一个题目：

给定一个长度为 $N$ 的数组 $c$ 和一个质数 $m$ ，请你构造另外两个数组 $a,b$ 满足：

$\left\{\begin{matrix} a_{i}\equiv a_{N-1-i}\pmod{m} \\ b_{i}\equiv -b_{N-1-i}\pmod{m} \\ c_{i}\equiv a_{i}+b_{i}\pmod{m} \end{matrix}\right.$

数组 $a,b,c$ 的下标均从 $0$ 开始计算。

如果可以构造出数组 $a,b$ ，则首先输出 $Yes$ ，然后输出任意一种解，否则只需输出一行一个字符串 $No$ 。

$\equiv$ 为同余符号，它表示两个整数对 $m$ 取余数的结果相同，对于负数取余数，若结果仍为负数，则需要加上 $m$ 。例如我们认为在模数 $m$ 为 $7$ 的情况下 $−12,−5,2$ 同余，即 $−12≡−5≡2\ (mod \ 7)$ 。

输入描述

第一行输入一个正整数和一个质数 $N,m(1≤N≤10^5,2≤m≤10^9+7)$ 。

接下来一行输入 $N$ 个非负整数 $c_i(0\leq c_i < m)$ 表示数组 $c$ 的值。

输出描述

如果可以构造出这样的数组 $a$ 和数组 $b$ ，则首先输出 $Yes$ ，接下来输出两行，每行 $N$ 个整数，用空格隔开,输出的整数范围应该在 $[-2^{31},2^{31})$ 范围内，行末无需多余空格。

否则只需输出一行一个字符串 $No$ 。

裁判程序将忽略大小写，你可以输出任意大小写的 $YES$ 和 $No$ 。

示例1

输入：
4 11
1 2 7 6

输出：
Yes
9 10 10 9
3 3 8 8

说明

一般来讲，我们称对 $m$ 取余数后的数字形成的集合为模系，模系中的数字取值范围在 $[0,m)$ 区间内。

也就是说实际上对于模 $11$ 而言，不应该出现例如 $−3$ 或者 $19$ 这样的数字，应该写作 $8$ 。

裁判程序具有一定的鲁棒性，即使你输出了如下的答案，也能够通过本题

9 10 10 9
3 3 -3 -3

分析

222

注意分类讨论。

AC代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 100010;
LL a[N], b[N], c[N];
int n, m;

LL qmi(int a, int k){
	LL ans = 1;
	while(k){
		if(k & 1) ans = ans * a % m;
		a = 1LL* a * a % m;
		k >>= 1;
	}
	return ans;
}

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 0; i < n; i++) scanf("%lld", &c[i]);
	if(m == 2){
		for(int i = 0; i < n / 2; i++){
			int j = n - 1 - i;
			bool flag = false;
			for(int x = 0; x < 2; x++){
				for(int y = 0; y < 2; y++){
					if(c[i] == (x + y) % 2 && c[j] == (x - y + 2) % 2){
						a[i] = a[j] = x;
						b[i] = y, b[j] = (-y + 2) % 2;
						flag = true;
						break;
					}
				} 
				if(flag) break;
			}
			if(!flag) {
				puts("No");
				return 0;
			}
		}
		if(n & 1) {
			a[n / 2] = c[n / 2];
			b[n / 2] = 0; 
		} 
	}
	else{
		LL inv = qmi(2, m - 2);
		for(int i = 0; i < n; i++){
			a[i] = (c[i] + c[n - 1 - i]) * inv % m;
			b[i] = (c[i] - a[i] + m) % m; 
		}
	}	
	puts("yes");
	for(int i = 0; i < n; i++) printf("%lld ", a[i]);
	puts("");
	for(int i = 0; i < n; i++) printf("%lld ", b[i]);
	
	return 0;
}

2、C-D题《清楚姐姐学01背包》

清楚姐姐学01背包

题目描述

清楚姐姐最近学会了 $01$ 背包， $01$ 背包是背包问题中最简单的问题。

$01$ 背包的约束条件是给定几种物品，每种物品有且只有一个，并且有权值和体积两个属性。在 $01$ 背包问题中，因为每种物品只有一个，对于每个物品只需要考虑选与不选两种情况。

如果不选择将其放入背包中，则不需要处理。如果选择将其放入背包中，由于不清楚之前放入的物品占据了多大的空间，需要枚举将这个物品放入背包后可能占据背包空间的所有情况。

现在清楚姐姐有 $N$ 个蝴蝶结，第 $i$ 个蝴蝶结的体积为 $w_i$ ，好看程度为 $v_i$ ，她准备了一个容量大小为 $M$ 的包包。她可以从这 $N$ 个蝴蝶结中任选若干个放入背包，但是所选蝴蝶结的体积总和不能大于背包的容量 $M$ ，清楚姐姐想要让所选蝴蝶结的好看程度总和最大化。

她运用自己刚刚学会的 $01$ 背包知识，快速算出了她能用她的包包装下蝴蝶结好看程度总和的最大值。

现在清楚姐姐有了一个新的问题，我们定义原问题的答案，即所选蝴蝶结好看程度总和的最大值为 $Val_{max}$ 。

定义从这 $N$ 个蝴蝶结中去掉第iii个蝴蝶结后，从剩余 $N−1$ 个蝴蝶结中任选若干个放入背包，所选蝴蝶结好看程度总和的最大值为 $Val'_{i}$ 。

若 $Val'_{i}<Val_{max}$ ，则称第iii个蝴蝶结为一个“必选蝴蝶结”。

清楚姐姐现在获得了调整蝴蝶结好看程度的机会，她想要知道，对于第iii个蝴蝶结，在它初始好看程度的基础上，再加上多少，该蝴蝶结就能够成为一个“必选蝴蝶结”。

输入描述

第一行输入两个正整数 $N,M(1 \leq N,M \leq 5000)$ 。
接下来 $N$ 行，每行输入两个正整数 $w_i,v_i(1 \leq w_i \leq M, v_i \leq 10^9)$ 表示每个蝴蝶结的体积以及好看程度。

输出描述

输出 $N$ 行，每行一个整数，第iii行表示在它初始好看程度的基础上，再加上多少，该蝴蝶结就能够成为一个“必选蝴蝶结”。特别的，如果该蝴蝶结已经是一个“必选蝴蝶结”，则输出 $0$ 。

示例1

示例2

说明

注意只有当 $Val'_{i}<Val_{max}$ 时，才称其为“必选蝴蝶结”，与原本的最大值完全相等时说明该蝴蝶结的好看程度还需要再加上 $1$ 点。

分析

1、对于小数据范围的 $C$ 题 $（1 <= N, M <= 100）$

对于 $C$ 题，数据范围只有 $100$ ，所以可以暴力来做。

对于每个物品，计算不选它的时候所有体积下的最大价值，然后人为强制把这个物品选上，计算此时的最大价值，通过前后两者就可以算出还需要加上多少价值才能把这个物品变为“必选物品”。

时间复杂度 $O(n^2 * m)$

AC代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 110;
LL f[N];
LL v[N], w[N];
int n, m; 

LL calc(int id){
	memset(f, 0, sizeof f);
	//不选id的结果 
	for(int i = 1; i <= n; i++){
		if(i == id) continue;
		for(int j = m; j >= v[i]; j--)
			f[j] = max(f[j], f[j - v[i]] + w[i]);
	}
	//再把id编号的物品强制选上
	LL ans = 1e18, notsel = f[m];
	for(int j = m - v[id]; j >= 0; j--){
		LL sel = f[j] + w[id];
		if(sel > notsel) return 0;
		ans = min(ans, notsel - sel + 1);
	}
	return ans;
} 

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) scanf("%lld%lld", &v[i], &w[i]);
	
	for(int i = 1; i <= n; i++){
		printf("%lld\n", calc(i));
	}
	
    return 0;
}

2、对于大数据范围的 $D$ 题 $（1 <= N, M <= 5000）$

AC代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 5010;
LL f1[N][N], f2[N][N];
LL v[N], w[N];
int n, m; 

void calc(LL f[][N]){
	for(int i = 1; i <= n; i++)
		for(int j = 0; j <= m; j++){
			f[i][j] = f[i - 1][j];
			if(j - v[i] >= 0) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
		}
}

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) scanf("%lld%lld", &v[i], &w[i]);
	calc(f1);
	reverse(v + 1, v + 1 + n);
	reverse(w + 1, w + 1 + n);
	calc(f2);
	reverse(v + 1, v + 1 + n);
	reverse(w + 1, w + 1 + n);
	
	for(int i = 1; i <= n; i++){
		LL vmax = 0, vmaxi = 0;
		for(int j = 0; j <= m; j++){
			vmax = max(vmax, f1[i - 1][j] + f2[n - i][m - j]);
			if(m - j >= v[i]){
				vmaxi = max(vmaxi, f1[i - 1][j] + f2[n - i][m - j - v[i]] + w[i]);
			}
		}
		printf("%lld\n", max(0LL, vmax - vmaxi + 1));
	}
	
	return 0;
}

3、E题《清楚姐姐打怪升级》

题目描述

清楚姐姐玩游戏打怪升级，一共有 $N$ 只怪物，第 $i$ 只怪物的生命值上限为 $h_i$ ，生命恢复速度为 $v_i$ ，清楚姐姐的攻击间隔为 $t$ ，攻击力为 $a$ 。

在每个时刻初，若怪物的生命值不满，则恢复 $v_i$ 点生命值，但是不能超过生命值上限 $h_i$ 。

在第 $1$ , $1+t$ , $1+2⋅t$ , $1+3⋅t$ ,…, $1+k⋅t$ 个时刻末，清楚姐姐可以选择一只怪物造成 $a$ 点伤害，若此时怪物的生命值小于等于 $0$ ，则该怪物死亡。

清楚姐姐想要知道自己至少在第几个时刻末可以杀死所有怪物，或者清楚姐姐永远也无法杀死所有怪物则输出 $−1$ 。

输入描述

第一行输入三个整数 $N,t,a(1≤N≤10^5,1≤t≤10^6,0≤a≤10^6)$ )，分别表示怪物的数目，清楚姐姐的攻击间隔和攻击力。

接下来 $N$ 行，每行输入两个整数 $h_i,v_i(1≤hi≤10^6,0≤vi≤10^6)$ ，分别表示每只怪物的生命值上限和生命恢复速度。

输出描述

仅一个整数，表示清楚姐姐至少在第几个时刻末可以杀死所有怪物，或者清楚姐姐永远也无法杀死所有怪物则输出 $-1$ 。

示例1

输入：
2 1 7
7 100
10 4

输出：
3

说明：
在第1个时刻末，清楚姐姐一刀解决第1只怪物。
在第2个时刻末，清楚姐姐攻击第2只怪物，怪物剩余血量为3。
在第3个时刻初，第2只怪物恢复4点生命，怪物剩余血量为7。
在第3个时刻末，清楚姐姐攻击第2只怪物，杀死所有怪物。

示例2

输入：
2 100 7
3 100
10 4

输出：
-1

分析

可惜了这题赛中没做出来，其实已经分析出来了，一个小细节错了导致一直wa，得出教训：记得回头看一看公式推导有没有出错！！源头都错了，后面当然对不了了。

出错的点， $(1 + k * t)$ 时刻恢复次数是 $k * t$ ，而不是 $k$ ！

根据上式算出的 $k$ 再加 $1$ 才是完整的时刻数，需要乘上 $t$ ，注意第一个时刻前面没有时间段，所以最终需要减去一个 $t$ 。

AC代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 100010;
LL h[N], v[N];
LL n, t, a;
LL ans = 1;

int main(){
	scanf("%lld%lld%lld", &n, &t, &a);
	for(int i = 1; i <= n; i++) scanf("%lld%lld", &h[i], &v[i]);
	for(int i = 1; i <= n; i++){
		if(h[i] > a && v[i] * t >= a){  //打不死（不能秒杀，并且伤害 <= 恢复）
			puts("-1");
			return 0;
		}
		if(a >= h[i]) ans += t;  //能一下秒杀
		else{
			LL t1 = abs(a - h[i]), t2 = abs(t * v[i] - a);
			ans += ((t1 + t2 - 1) / t2 + 1) * t;  //上取整
		}
	}
	printf("%lld\n", ans - t);
	
	return 0;
}

上一篇：牛客寒假集训营第五场补题下一篇：牛客寒假集训营第三场补题