题目链接:
https://codeforces.com/gym/103446

视频讲解:
https://www.bilibili.com/video/bv1994y1f76o

代码:https://hytidel.lanzoub.com/b030vuwli
密码:fkgp

2021ICPC上海区域赛题解DEGIK

E. Strange Integers

题意

给定$n(1\le n\le 1\mathrm{e}5)$个数$a_1,\cdots ,a_n(1\le a_i\le 1\mathrm{e}9)$和一个参数$k(0\le k\le 1\mathrm{e}9)$,问从中至多可以选出几个数使得选出来的数两两之差的绝对值不小于$k$.

解I

$n$最大$1\mathrm{e}5$,时间$1s$,考虑$O(n)$暴力枚举.将序列升序排列后取出最大数$maxnum$,从后往前扫一遍序列,每次检查两数之差是否$\ge k$,若是则$ans++$,并将$maxnum$更新为当前的$a[i]$.

代码I -> 2021ICPC上海-E(暴力)

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<sstream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef queue<int> qi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
#define umap unordered_map
#define IOS ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
#define CaseT int CaseT; cin >> CaseT; while(CaseT--)
#define endl 'n'
#define so sizeof
#define pb push_back
#define npt nullptr
const double eps = 1e-7;
const int INF = 0x3f3f3f3f;
const ll INFF = 0x3f3f3f3f3f3f3f3f;

const int MAXN = 1e5 + 5;
int n, k;  // 元素个数、参数
int nums[MAXN];
int minnum = INF;
int ans = 1;  // 至少选最小数

int main() {
	IOS;
#ifndef ONLINE_JUDGE
	clock_t my_clock = clock();
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	// ----------------------------------------------------------------
	cin >> n >> k;
	for (int i = 0; i < n; i++) cin >> nums[i];

	sort(nums, nums + n);

	int maxnum = nums[n - 1];
	for (int i = n - 2; i >= 0; i--) {
		if (maxnum - nums[i] >= k) {
			ans++;
			maxnum = nums[i];
		}
	}
	cout << ans;
	// ----------------------------------------------------------------
#ifndef ONLINE_JUDGE
	cout << endl << "Time used " << clock() - my_clock << " ms." << endl;
#endif
	return 0;
}

解II

贪心.将序列升序排列后取出最小数$minnum$,每次取序列中第一个$\ge minnum+k$的数,直至无法再取或已取完整个序列.

代码II -> 2021ICPC上海-E(贪心+lower_bound或二分)

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<sstream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef queue<int> qi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
#define umap unordered_map
#define IOS ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
#define CaseT int CaseT; cin >> CaseT; while(CaseT--)
#define endl 'n'
#define so sizeof
#define pb push_back
#define npt nullptr
const double eps = 1e-7;
const int INF = 0x3f3f3f3f;
const ll INFF = 0x3f3f3f3f3f3f3f3f;

const int MAXN = 1e5 + 5;
int n, k;  // 元素个数、参数
int nums[MAXN];
int minnum = INF;
int ans = 1;  // 至少选最小数

int main() {
	IOS;
#ifndef ONLINE_JUDGE
	clock_t my_clock = clock();
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	// ----------------------------------------------------------------
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> nums[i];
		minnum = min(minnum, nums[i]);
	}

	sort(nums, nums + n);

	int idx = lower_bound(nums, nums + n, minnum + k) - nums;
	while (idx != n) {
		ans++;
		minnum = nums[idx];
		idx = lower_bound(nums, nums + n, minnum + k) - nums;
	}
	cout << ans;
	// ----------------------------------------------------------------
#ifndef ONLINE_JUDGE
	cout << endl << "Time used " << clock() - my_clock << " ms." << endl;
#endif
	return 0;
}

但事实上,暴力解法比lower_bound的解法还快,如下图,上面是暴力,下面是lower_bound.

D. Strange Fractions

题意

给定$T(1\le T\le 1\mathrm{e}5)$个分数$\frac{p}{q}(1\le p,q\le 1\mathrm{e}7)$,求整数$a,b(1\le a,b\le 1\mathrm{e}9)s.t.\frac{p}{q}=\frac{a}{b}+\frac{b}{a}$,若不存在,输出$00$.

注

只需讨论$\frac{p}{q}$是最简分式的情况,若不然,分子分母同除以$\gcd (p,q)$化为最简分式.$\frac{p}{q}=\frac{a}{b}+\frac{b}{a}=\frac{a^2+b^2}{ab}$,注意这里推不出$\{\begin{array}{l}p=a^2+b^2\\ q=ab\end{array}$,因$a^2+b^2$与$ab$未必互素,如$a=b=2$时,$\frac{a^2+b^2}{ab}=\frac{8}{4}$,而$p=2,q=1$.

但是有题解这样推导,最后还是AC了,这是因为它忽略了指向正解的一步,见解II.

解I

令$x=\frac{a}{b},k=\frac{p}{q}$,化为关于$x$的一元二次方程$x^2-kx+1=0$,其判别式$\Delta =k^2-4$,方程有实根当且仅当$k^2-4=\frac{p^2}{q^2}-4\ge 0$,即$p^2\ge 4q^2$.

为使$x=\frac{k\pm \sqrt{k^2-4}}{2}=\frac{\frac{p}{q}\pm \frac{\sqrt{p^2-4q^2}}{q}}{2}=\frac{p\pm \sqrt{p^2-4q^2}}{2q}\in \mathbb{Q}$,则$\sqrt{p^2-4q^2}\in \mathbb{Z}$,进而$p^2-4q^2$是平方数,设其平方根为$tmp$,则$\frac{a}{b}=\frac{p\pm tmp}{2q}$,为保证$a,b\ge 1$,则取$a=p+tmp$和$b=2q$,注意将其约分再输出.未必要输出小数在前.

代码I -> 2021ICPC上海-D(推公式做法I)

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<sstream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef queue<int> qi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
#define umap unordered_map
#define IOS ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
#define CaseT int CaseT; cin >> CaseT; while(CaseT--)
#define endl 'n'
#define so sizeof
#define pb push_back
#define npt nullptr
const double eps = 1e-7;
const int INF = 0x3f3f3f3f;
const ll INFF = 0x3f3f3f3f3f3f3f3f;

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

bool check(ll n) {  // 判断n是否为平方数
	ll tmp = floor(sqrt(n) + 0.5);
	return tmp * tmp == n;
}

int main() {
	IOS;
#ifndef ONLINE_JUDGE
	clock_t my_clock = clock();
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	// ----------------------------------------------------------------
	CaseT{
		int p, q; cin >> p >> q;

		if ((ll)p * p < (ll)4 * q * q) {  // 无解
			cout << "0 0" << endl;
			continue;
		}

		ll tmp = (ll)p * p - (ll)4 * q * q;  // p^2-4q^2
		if (!check(tmp)) {  // 无解
			cout << "0 0" << endl;
			continue;
		}

		tmp = sqrt(tmp);
		int d = gcd(p + tmp, 2 * q);
		cout << (p + tmp) / d << ' ' << (2 * q) / d << endl;
	}
	// ----------------------------------------------------------------
#ifndef ONLINE_JUDGE
	cout << endl << "Time used " << clock() - my_clock << " ms." << endl;
#endif
	return 0;
}

解II

只需讨论$\frac{p}{q}$是最简分式的情况,若不然,分子分母同除以$\gcd (p,q)$化为最简分式.$\frac{p}{q}=\frac{a}{b}+\frac{b}{a}=\frac{a^2+b^2}{ab}$.若约定$\gcd (a,b)=1$,则$\gcd (a^2+b^2,ab)=1$,进而推出$\{\begin{array}{l}p=a^2+b^2\\ q=ab\end{array}$.

注意到$\{\begin{array}{l}a+b=\sqrt{p+2q}\\ a-b=\sqrt{p-2q}\end{array}$,若$p+2q,p-2q$是平方数,则有合法的$\{\begin{array}{l}a=\frac{\sqrt{p+2q}+\sqrt{p-2q}}{2}\\ b=\frac{\sqrt{p+2q}-\sqrt{p-2q}}{2}\end{array}$,判断$a,b$是否为整数.

$\gcd (a,b)=1$时,有$\gcd (a^2+b^2,ab)=1$的证明:不妨设$a=\prod _i{p}_i^{{\alpha }_i},b=\prod _i{q}_i^{{\beta }_i}$,其中$p_i\ne q_i$,则$ab=\left(\prod _i{p}_i^{{\alpha }_i}\right)\left(\prod _i{q}_i^{{\beta }_i}\right),a^2+b^2=\prod _i{p}_i^{2{\alpha }_i}+\prod _i{q}_i^{2{\beta }_i}$,则显然$a^2+b^2$的$\mathrm{R}\mathrm{H}\mathrm{S}$的两项都不能被$ab$整除,故$\gcd (a^2+b^2,ab)=1$.

代码II -> 2021ICPC上海-D(推公式做法II)

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<sstream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef queue<int> qi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
#define umap unordered_map
#define IOS ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
#define CaseT int CaseT; cin >> CaseT; while(CaseT--)
#define endl 'n'
#define so sizeof
#define pb push_back
#define npt nullptr
const double eps = 1e-7;
const int INF = 0x3f3f3f3f;
const ll INFF = 0x3f3f3f3f3f3f3f3f;

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

bool check(ll n) {  // 判断n是否为平方数
	ll tmp = floor(sqrt(n) + 0.5);
	return tmp * tmp == n;
}

int main() {
	IOS;
#ifndef ONLINE_JUDGE
	clock_t my_clock = clock();
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	// ----------------------------------------------------------------
	CaseT{
		ll p, q; cin >> p >> q;
		int d = gcd(p, q);
		if (d != 1) p /= d, q /= d;

		ll x = p + 2 * q, y = p - 2 * q;
		if (!check(x) || !check(y)) {  // 无解
			cout << "0 0" << endl;
			continue;
		}

		x = sqrt(x), y = sqrt(y);

		ll a = x + y >> 1, b = x - y >> 1;
		if (a + b == x && a - b == y) cout << a << ' ' << b << endl;  // a和b是整数
		else cout << "0 0" << endl;
	}
		// ----------------------------------------------------------------
#ifndef ONLINE_JUDGE
	cout << endl << "Time used " << clock() - my_clock << " ms." << endl;
#endif
	return 0;
}

G. Edge Groups

题意

给定一个有$n(3\le n\le 1\mathrm{e}5,n为奇数)$个节点、$(n-1)$条边的无向连通图,求将边分为$\frac{n-1}{2}$组且满足如下两条件的方案数,答案对$998244353$取模:①每组有且仅有两条边;②两条在同一组中的边有一个公共节点.

图用$(n-1)$行输入描述,每行包含两个正整数$u,v(1\le u<v\le n)$,表示节点$u$和$v$间连有无向边.

解

注意到连通$n$个节点至少需要$(n-1)$条边,则本题中的无向连通图是树.

考察以$x$为根节点的子树的方案数,其中$fa$为$x$的父节点.如下图,按子树的节点数为奇数、偶数分为两种情况,分别称为I型、II型子树.

II型子树有偶数个节点,奇数条边,再加上边$(x,y_2)$即可两两配对;I型子树有奇数个节点,偶数条边,$y_1$的子树中的边两两配对后,边$(x,y_1)$未配对,可能需与边$(fa,x)$配对,是否需要用到边$(fa,x)$取决于$x$的子树中I型子树的数量的奇偶:①有偶数个时,所有I型子树的边$(x,y_i)$可两两配对;②有奇数个时,所有I型子树的边$(x,y_i)$两两配对剩下的一条边与$(fa,x)$配对.

考察$n(n为偶数)$条边平均分为$\frac{n}{2}$组的方案数$dfac[n]$.$n=2$时,$dfac[2]=1$;$n=4$时,$dfac[4]=\frac{C_4^2{C}_2^2}{A_2^2}=3$;$n=6$时,$dfac[6]=\frac{C_6^2{C}_4^2{C}_2^2}{A_3^3}=15$;$n=8$时,$dfac[8]=\frac{C_8^2{C}_6^2{C}_4^2{C}_2^2}{A_4^4}=105$.

注意到$dfac[4]=dfac[2]\ast 3,dfac[6]=dfac[4]\ast 5,dfac[8]=dfac[6]\ast 7$,猜想$dfac[n]=dfac[n-2]\ast (n-1)$,下面证明该结论.$dfac[n]=\frac{C_n^2{C}_{n-2}^2{C}_{n-4}^2\cdots C_2^2}{A_{\frac{n}{2}}^{\frac{n}{2}}},dfac[n-2]=\frac{C_{n-2}^2{C}_{n-4}^2\cdots C_2^2}{A_{\frac{n-2}{2}}^{\frac{n-2}{2}}}$,则$\frac{dfac[n]}{dfac[n-2]}=\frac{C_n^2}{\frac{n}{2}}=\frac{n!}{2!\cdot (n-2)!}\cdot \frac{2}{n}=n-1$.

$dp[x]$表示以节点$x$为根节点的子树分组的方案数,设其子树的根节点分别为$y_i$,其中有$cnt$个I型子树,则状态转移方程$dp[x]=\{\begin{array}{l}dfac[cnt]\ast \prod _{i}dp[y_i],cnt为偶数\\ dfac[cnt+1]\ast \prod _{i}dp[y_i],cnt为奇数\end{array}$.

代码 -> 2021ICPC上海-G(树形DP+组合计数)

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<sstream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef queue<int> qi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
#define umap unordered_map
#define IOS ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
#define CaseT int CaseT; cin >> CaseT; while(CaseT--)
#define endl 'n'
#define so sizeof
#define pb push_back
#define npt nullptr
const double eps = 1e-7;
const int INF = 0x3f3f3f3f;
const ll INFF = 0x3f3f3f3f3f3f3f3f;

const int MAXN = 1e5 + 5, MOD = 998244353;
int n;  // 节点数
vi graph[MAXN];  // g[i]=j表示节点i和j间有有向边
int siz[MAXN];  // siz[i]表示以节点i为根节点的子树的大小(节点数)
int dfac[MAXN];  // dfac[n]=1*3*5*...*(n-1),n为偶数
int dp[MAXN];  // dp[i]表示以节点i为根节点的子树分组的方案数

void init() {  // 预处理出dfac[]
	dfac[0] = 1;
	for (int i = 2; i <= n; i += 2) dfac[i] = (ll)dfac[i - 2] * (i - 1) % MOD;
}

void dfs(int u, int fa) {  // 当前节点、前驱
	siz[u] = 1;  // 当前子树的大小初始值为1,即子树的根节点
	dp[u] = 1;  // 方案数初始化为1
	int cnt = 0;  // 统计以u为根节点的子树中,节点数为奇数的子树的数量
	for (auto& v : graph[u]) {  // 注意取引用,因要更新子树的信息
		if (v == fa) continue;  // 搜过了

		dfs(v, u);  // 搜以v为根节点的子树,v的前驱为u

		// 用子树更新根节点u的信息
		siz[u] += siz[v];
		dp[u] = (ll)dp[u] * dp[v] % MOD;

		if (siz[v] & 1) cnt++;  // 更新节点数为奇数的子树的数量
	}
	
	if (cnt & 1) cnt++;  // 有奇数个节点数为奇数的子树,则需把边(u,fa)一起考虑
	dp[u] = (ll)dp[u] * dfac[cnt] % MOD;
}

int main() {
	IOS;
#ifndef ONLINE_JUDGE
	clock_t my_clock = clock();
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	// ----------------------------------------------------------------
	cin >> n;
	for (int i = 1; i < n; i++) {
		int u, v; cin >> u >> v;
		graph[u].push_back(v), graph[v].push_back(u);
	}

	init();  // 预处理出dfac[]

	dfs(1, 0);  // 1号节点作为根节点,无前驱,记为0
	cout << dp[1];
	// ----------------------------------------------------------------
#ifndef ONLINE_JUDGE
	cout << endl << "Time used " << clock() - my_clock << " ms." << endl;
#endif
	return 0;
}

K. Circle of Life

题意

从左到右,有$n(2\le n\le 123)$个节点由$(n-1)$条边相连,节点编号分别为$1\sim n$.初始状态由一个长度为$n$的$0-1$串$s$给出,其中$s[i]=1$表示节点$i$处有精灵,$s[i]=0$表示节点$i$处无精灵($s$下标从$1$开始),每个节点处最多只有一个精灵.现进行$2n$次变换,每次变换时所有精灵会同时分裂成两个精灵,其中一个精灵向左移动,另一个精灵向右移动.当两个精灵在节点处或边上相遇时会湮灭,在节点$1$处向左移动、在节点$n$处向右移动的精灵会湮灭.

给定$n$,求一初始状态$s s.t. $进行$2n$次变换后至少剩下一个精灵.

解

手动模拟样例可知要在$2n$次变换内出现循环.

样例给出了$n=2$和$n=4$时的构造,容易猜想$n$为偶数时都构造$100\cdots 0$,但事实上$n=6$时需$14>12$步才能循环.

样例都是偶数,容易想到尝试$n$为奇数的情况.$n=3$时易得不存在满足的$s$;$n=5$时,先尝试偶数的猜想$10000$能否循环.$10000\to 01000\to 10100\to 00010\to 00101\to 01000$,出现了$01000$的循环.但是这样的循环不能推广,即它连接上其他的循环后的串未必循环,即使循环也未必在$2n$次内循环.

考虑如何用一些自身循环的子串连接成长度为$n$的串$ss.t.s$在$2n$次内循环.考察可以作为自身循环单元的子串的性质.为使得用它们连接成的串仍能在$2n$次内循环,对任一子串,其在两侧的"行为"应该镜像地相似,则它应是"比较对称"的.

考察哪些”比较对称“的串可作为自身循环单元.尝试得$1001$可作为自身循环单元.考虑打表$n=1\sim 7$的自身循环单元$ans[]$,将$n\ge 8$情况按模$4$的余数$r$分类:①$r=0$时,输出若干个$1001$即可;②$r=1$时,先输出$ans[5]$,再$n-=5$化为①的情况;③$r=2$时,先输出$ans[6]$,再$n-=6$化为①的情况;④$r=3$时,先输出$ans[7]$,再$n-=7$化为①的情况.

代码 -> 2021ICPC上海-K(构造)

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<sstream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef queue<int> qi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
#define umap unordered_map
#define IOS ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
#define CaseT int CaseT; cin >> CaseT; while(CaseT--)
#define endl 'n'
#define so sizeof
#define pb push_back
#define npt nullptr
const double eps = 1e-7;
const int INF = 0x3f3f3f3f;
const ll INFF = 0x3f3f3f3f3f3f3f3f;

string ans[] = { "X","0","01","X","1001","10001","011001","0101001" };

void solve(int n) {
	if (n <= 7) {
		cout << ans[n];
		return;
	}

	if (n % 4 == 0) {
		for (int i = 0; i < n / 4; i++) cout << ans[4];
		return;
	}
	else if (n % 4 == 1) {
		cout << ans[5];
		solve(n - 5);
	}
	else if (n % 4 == 2) {
		cout << ans[6];
		solve(n - 6);
	}
	else {
		cout << ans[7];
		solve(n - 7);
	}
}

int main() {
	IOS;
#ifndef ONLINE_JUDGE
	clock_t my_clock = clock();
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	// ----------------------------------------------------------------
	int n; cin >> n;
	
	if (n == 3) return cout << "Unlucky", 0;  // 特判无解

	solve(n);
	// ----------------------------------------------------------------
#ifndef ONLINE_JUDGE
	cout << endl << "Time used " << clock() - my_clock << " ms." << endl;
#endif
	return 0;
}

I. Steadily Growing Steam ($512\mathrm{M}\mathrm{B}$)

题意

有$n(1\le n\le 100)$张牌,每张牌有一个价值$v_i(|v_i|\le 1\mathrm{e}9)$和点数$t_i(1\le t_i\le 13)$.先选择至多$k(0\le k\le n)$张牌将其点数翻倍,再从$n$张牌中选若干张牌分成两堆,要求两堆内点数之和相等,求选出的牌的价值之和的最大值.

解I

将牌视为物品,点数视为体积,转化为背包.

设两堆的点数之和分别为$A$和$B$.注意到不关心$A$和$B$的具体数值,只关心它们是否相等,则可用$A-B$作为$0-1$背包的体积,即视放入$A$堆的体积为正,放入$B$堆的体积为负.初始点数$t$最大$13$,翻倍后最大$26$,最多$100$张牌,则体积范围$(-2600,2600)$.因数组的下标非负,可加一个$2600$的偏移量.

$dp[i][j][w]$表示只考虑前$i$张牌、还可以翻倍$j$次、当前背包体积为$w$的价值之和的最大值,$dp[100][100][5200]$,最终答案$ans=\underset{0\le j\le k}{\max }dp[n][j][2600]$.

考虑最后一个不同点,即已考虑完前$(i-1)$张牌,现考虑第$i$张牌.

状态转移方程$dp[i][j][w]=\max \{\begin{array}{l}dp[i-1][j][w],不选t_i\\ dp[i-1][j][w+t_i]+v_i,t_i放入A\\ dp[i-1][j][w-t_i]+v_i,t_i放入B\\ dp[i-1][j-1][w+2\ast t_i]+v_i,2t_i放入A\\ dp[i-1][j-1][w-2\ast t_i]+v_i,2t_i放入B\end{array}$,第一维$O(n)$,第二维$O(k)$,第三维$O(4nt)$,转移$O(1)$,总时间复杂度$O(n\cdot k\cdot 4nt)\approx O(4n^{3}t)$,看起来$1\mathrm{s}$不够,但事实上很多方案不合法,故实际方案数远小于$O(4n^{3}t)$.

物品价值数量级$1\mathrm{e}9$,最多$100$个物品,故dp数组要开ll.空间复杂度$100\times 100\times 5200\times 8÷1024÷1024\approx 397\mathrm{M}\mathrm{B}<512\mathrm{M}\mathrm{B}$,空间足够.

代码I -> 2021ICPC上海-I(背包DP)

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<sstream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef queue<int> qi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
#define umap unordered_map
#define IOS ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
#define CaseT int CaseT; cin >> CaseT; while(CaseT--)
#define endl 'n'
#define so sizeof
#define pb push_back
#define npt nullptr
const double eps = 1e-7;
const double pi = acos(-1);
const int INF = 0x3f3f3f3f;
const ll INFF = 0x3f3f3f3f3f3f3f3f;

const int MAXN = 105, MAXM = 5205;
int n, k;  // 牌数、最多翻倍次数
int v[MAXN], t[MAXN];  // 价值、点数
// dp[i][j][w]表示只考虑前i个物品、还可翻倍j次、当前背包体积为w的价值之和最大值
ll dp[MAXN][MAXN][MAXM]; 

int main() {
	IOS;
#ifndef ONLINE_JUDGE
	clock_t my_clock = clock();
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	// ----------------------------------------------------------------
	memset(dp, -INFF, so(dp));  // 置为-INFF,表示未更新
	dp[0][0][2600] = 0;  // k=2600为答案

	cin >> n >> k;
	for (int i = 1; i <= n; i++) cin >> v[i] >> t[i];

	for (int i = 1; i <= n; i++) {  // 枚举物品
		for (int j = 0; j <= k; j++) {  // 枚举翻倍次数
			for (int w = 0; w <= 5200; w++) {  // 枚举背包体积
				if (dp[i - 1][j][w] != -INFF) dp[i][j][w] = dp[i - 1][j][w];  // 不选t[i]

				if (w >= t[i] && dp[i - 1][j][w - t[i]] != -INFF)  // t[i]放入A
					dp[i][j][w] = max(dp[i][j][w], dp[i - 1][j][w - t[i]] + v[i]);

				if (w <= 5200 - t[i] && dp[i - 1][j][w + t[i]] != -INFF)  // t[i]放入B
					dp[i][j][w] = max(dp[i][j][w], dp[i - 1][j][w + t[i]] + v[i]);

				if (j && w >= 2 * t[i] && dp[i - 1][j - 1][w - 2 * t[i]] != -INFF)  // 2*t[i]放入A
					dp[i][j][w] = max(dp[i][j][w], dp[i - 1][j - 1][w - 2 * t[i]] + v[i]);

				if (j && w <= 5200 - 2 * t[i] && dp[i - 1][j - 1][w + 2 * t[i]] != -INFF)  // 2*t[i]放入B
					dp[i][j][w] = max(dp[i][j][w], dp[i - 1][j - 1][w + 2 * t[i]] + v[i]);
			}
		}
	}

	ll ans = -INFF;
	for (int j = 0; j <= k; j++) ans = max(ans, dp[n][j][2600]);
	cout << ans;
	// ----------------------------------------------------------------
#ifndef ONLINE_JUDGE
	cout << endl << "Time used " << clock() - my_clock << " ms." << endl;
#endif
	return 0;
}

解II:滚动数组优化 (By 暮冥)

dp数组的第一维滚动.

代码II -> 2021ICPC上海-I(背包dp+滚动数组优化)

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<sstream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef queue<int> qi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
#define umap unordered_map
#define IOS ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
#define CaseT int CaseT; cin >> CaseT; while(CaseT--)
#define endl 'n'
#define so sizeof
#define pb push_back
#define npt nullptr
const double eps = 1e-7;
const double pi = acos(-1);
const int INF = 0x3f3f3f3f;
const ll INFF = 0x3f3f3f3f3f3f3f3f;

const int MAXN = 105, MAXM = 2605;
int n, k;  // 牌数、最多翻倍次数
int v[MAXN], t[MAXN];  // 价值、点数
// dp[i][j][w]表示只考虑前i个物品、还可翻倍j次、当前背包体积为w的价值之和最大值
ll dp[2][MAXN][MAXM];  // 第一维滚动
int T = 1300;  // 偏移量
int idx;  // 滚动数组下标

int main() {
	IOS;
#ifndef ONLINE_JUDGE
	clock_t my_clock = clock();
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	// ----------------------------------------------------------------
	memset(dp, -INFF, so(dp));  // 置为-INFF,表示未更新
	dp[0][0][T] = 0;  // 初始条件,都不选
	idx = 1;  // 滚动数组下标从1开始

	cin >> n >> k;
	for (int i = 1; i <= n; i++) cin >> v[i] >> t[i];

	for (int i = 1; i <= n; i++) {  // 枚举物品
		memset(dp[idx], -INFF, so(dp[idx]));  // 初始化将要更新的部分

		for (int j = 0; j <= k; j++) {  // 枚举翻倍次数
			for (int w = -1300; w <= 1300; w++) {  // 枚举背包体积
				for (int p = -2; p <= 2; p++) {  // 枚举选择的物品,分别为-2*t[i],-t[i],0,t[i],2*t[i]
					int curw = w + p * t[i];  // 当前背包体积
					if (curw < -1300 || curw>1300) continue;  // 越界

					if (j) {  // 可以翻倍
						dp[idx][j][curw + T] = max(dp[idx][j][curw + T], dp[idx ^ 1][j - (abs(p) == 2)][w + T] + (p == 0 ? 0 : v[i]));
					}
					else if (abs(p) <= 1)  // 只能转移不翻倍的
						dp[idx][j][curw + T] = max(dp[idx][j][curw + T], dp[idx ^ 1][j][w + T] + (p == 0 ? 0 : v[i]));
				}
			}
		}
		idx ^= 1;
	}
	
	ll ans = -INFF;
	for (int i = 0; i <= k; i++) ans = max(ans, dp[n & 1][i][T]);
	cout << ans;
	// ----------------------------------------------------------------
#ifndef ONLINE_JUDGE
	cout << endl << "Time used " << clock() - my_clock << " ms." << endl;
#endif
	return 0;
}

优化空间的效果:如下图,下为朴素,上为滚动数组优化.

最后

以上就是俭朴唇膏为你收集整理的2021ICPC上海区域赛DEGKI2021ICPC上海区域赛题解DEGIK的全部内容，希望文章能够帮你解决2021ICPC上海区域赛DEGKI2021ICPC上海区域赛题解DEGIK所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。