博客 > Code Forces

Round #683 (div. 2)

题目链接

A

数组是如下格式的(递增的):

1 2 3 4 5 6...

加法也是同数字递增的.

那么只要给 1 加上 2 3 4 5 6 , 给 2 加上 1 3 4 5 6 , 给3加上 1 2 4 5 6 … 也就是第i次不加第i个数, 那最终这几个数就会在他们的总和处相等.

最后的结果就是一个从1到n递增序列.

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LL long long
#define STL(x) x.begin(), x.end()
#define INI(x) scanf("%d", &x)
#define IND(x) scanf("%llf", &x)
#define INLL(x) scanf("%lld", &x)
#define INS(x) cin << x
#define IN(x) cin << x
int main() {
	// TODO: Write your code
	int t;
	INI (t);
	while (t--) {
		int n;
		INI (n);
		cout << n << endl;
		for (int i = 0; i < n; i++) {
			cout << i + 1 << " ";
		}
		cout << endl;
	}
	return 0;
}

B

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LL long long
#define STL(x) x.begin(), x.end()
#define INI(x) scanf("%d", &x)
#define IND(x) scanf("%llf", &x)
#define INLL(x) scanf("%lld", &x)
#define INS(x) cin << x
#define IN(x) cin << x
int main() {
	// TODO: Write your code
	int t;
	INI (t);
	while (t--) {
		int n, m;
		INI (n); INI(m);
		int sum = 0;
		int minabs = INF;
		int cnt = 0;
		bool hasZero = false;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				int t;
				INI(t);
				if (t == 0) hasZero = true;
				if (t < 0) cnt++, t = -t;
				sum += t;
				minabs = min(minabs, t);
			}
		}
		if (hasZero) {
			cout << sum << endl;
		} else {
			if (cnt % 2) {
				cout << sum - 2 * minabs << endl;
			} else {
				cout << sum << endl;
			}
		}
	}
	return 0;
}

C

O(nlogn)的解法

这也是我想到的解法. 就是直接排序一遍, 然后贪心取最大, 行就加进去不行就跳过.

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LL long long
#define STL(x) x.begin(), x.end()
#define INI(x) scanf("%d", &x)
#define IND(x) scanf("%llf", &x)
#define INLL(x) scanf("%lld", &x)
#define INS(x) cin << x
#define IN(x) cin << x
int main() {
	// TODO: Write your code
	int t;
	INI (t);
	while (t--) {
		int n;
		LL w;
		INI (n);
		INLL (w);
		pair<int, int> arr[n + 5];
		LL sum = 0;
		vector<int> items;
		bool flag = false; // if possible
		for (int i = 1; i <= n; i++) {
			LL t;
			INLL (t);
			arr[i] = {i, t};
		}
		sort (arr + 1, arr + 1 + n, [] (pair<int, int> & a, pair<int, int> & b) {
			return a.second > b.second;
		});
		for (int i = 1; i <= n; i++) {
			LL tsum = sum + arr[i].second;
			if (tsum <= w) {
				items.push_back (arr[i].first);
				sum = tsum;
			}
			if (sum >= (1 + w) / 2) {
				flag = true;
				break;
			}
		}
		if (flag) {
			cout << items.size() << endl;
			for (auto t : items) {
				cout << t << " ";
			}
			cout << endl;
		} else {
			cout << "-1\n";
		}
	}
	return 0;
}

O(n)的解法

这是CF官方题解的解法.

  1. 把数组里所有大于W的元素屏蔽一下.
  2. 然后看看有没有正好处在 [W2,W] 内的元素, 有的话就他一个就行.
  3. 如果没有, 就把剩下的元素以任意顺序枚举加入背包, 因为这时所有元素都小于 W2 , 也就不存在爆背包的情况, 就硬加就可以了. 加到总和满足条件为止.

D

知道是动态规划, 但是想复杂了. 以为是在LCS已求出的基础上再做一次DP, 或者至少是同步求多个DP, 后来发现不用. (虽然这么做应该也可以, 但最后反正没做出来)

以下是题解解法(关键是利润和代价, 以及一个在线累加过程):

只要把LCS以二维矩阵记录字符串匹配情况的思路用上就行了, 可以直接代替掉朴素的LCS.

dp[i][j] 为二维矩阵第 ij 列时 S 的最优解, 则有:

综上所述, 得到状态转移方程:

dp[i][j]={dp[i1][j1]+2,str1[i]=str2[j],max(dp[i1][j],dp[i][j1])1,本项>0,0,本项≤0.

代码

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
int    n, m;
string a, b;
int    dp[5050][5050] = {0};
int main() {
	cin >> n >> m;
	cin >> a >> b;
	a = " " + a, b = " " + b; // 从1开始
	int maxres = -INF;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (a[i] == b[j]) {
				dp[i][j] = dp[i - 1][j - 1] + 2; // 补充弹药
			} else {
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) - 1; // 吃老本
			}
			dp[i][j] = max(0, dp[i][j]); // 老本吃完
			maxres = max(maxres, dp[i][j]); // 拿到最佳状态, 作为最终结果
		}
	}
	cout << maxres << endl;
	return 0;
}

E

题目描述

给出长度为 n(2n200000) 的数组 a(0ai109).

a 中删去 m 个元素, 得到数组 b , 为每一个 bi 找一个配对的 bj(ij) , 使得 bibj 最小.

b 中元素当作无向图的节点, 连接所有的 (bi,bj) 边, 重边算同一条.

求构成的图是一棵树时, 最少删除的元素数 mmin.

分析

容易想到, 怎样可以使异或值尽可能小?

当然是让最高异位尽可能低, 这样异或结果中第一个 1 就出现得尽可能低.

再考虑怎样将此图构成一棵树?

已知有 (nm) 个节点, 要构造 (nm) 条边, 重边算同一条. 最后要形成一棵树, 必然满足如下条件:

接下来考虑有没有什么条件下, 此图一定不连通?

如果此图有两个连通分量, 那么这两个连通分量中的节点一定有成对的异或最小值, 而异或最小值的来源是最高异位尽可能低! 我们想要打破这种孤立的局面, 可以强行抬高最高异位!

易知, 从高到低的每一位都有: 每一个 bi 在此位上都可以为 10. 因此bik 从高到低的枚举进行一个字典树式的分组:

接下来对这两组进行讨论:

因此得到本题的解法(dfs):

/**
 * @param k 第k位
 * @param arr 要讨论的数集
 * @return 保留下来的元素数
 */
int dfs(k, arr) {
	// 把arr分组为k0和k1
	divide(arr, &k0, &k1);
	if (len(k0) >= 2 && len(k1) >= 2) { // 把一个删成1, 递归另一个
		res1 = dfs(k-1, k1);
		res2 = dfs(k-1, k0);
		res = max(res1, res2) + 1;
	} else if (len(k0) >= 2 || len(k1) >= 2) { // 递归长的那个
		res = dfs(k-1, 长的) + len(短的);
	} else { // k0和k1各一个, 到出口了
		res = len(arr);
	}
	return res;
}