Codeforces Round #683 (Div. 2, by Meet IT)

A

初始情况\(1\) ~ \(n\)堆分别有 \(1\) ~ \(n\) 个糖果，第\(i\)次操作给除了所选堆的糖果数 \(+ i\), 找到一种方案可以使得所有堆糖果数相同，输出操作次数和每次选定不变的堆.

选定当前堆不变，其他堆\(+ i\)等价于将选定堆\(-i\), 故只需要考虑如何将所有堆减到\(0\)即可, 即操作\(n\)次，第\(i\)次选择第\(i\)堆.



#include <bits/stdc++.h>

using namespace std; 

int main()

{

	int T;

	scanf("%d", &T);

	while(T -- )

	{

		int n;

		scanf("%d", &n);

		printf("%d\n", n);

		for(int i = 1; i <= n; ++ i) printf("%d%c", i, i == n ? '\n' : ' ');

	}

	return 0;

}

B

给一个矩阵，每次操作可以选中相邻的两个元素，将他们都乘\(-1\), 可以进行无限次操作，问矩阵中所有元素和的最大值

负号可以两两抵消，故考虑负号的个数，如果是偶数，全部抵消，求所有元素绝对值的和；如果是奇数，最后剩一个负号，选择绝对值最小的为负数即可



#include <bits/stdc++.h>

using namespace std;

const int N = 10 + 3;

int n, m;

int main()

{

	int T;

	scanf("%d", &T);

	while(T -- )

	{

		int x, sum = 0, num = 0, minx = 1e9;

		scanf("%d%d", &n, &m);

		for(int i = 1; i <= n; ++ i)

			for(int j = 1; j <= m; ++ j)

			{

				scanf("%d", &x);

				sum += abs(x);

				num += x < 0;

				minx = min(minx, abs(x));

			}

		if(num & 1) printf("%d\n", sum - 2 * minx);

		else printf("%d\n", sum);

	}

	return 0;

}

C

给\(n\)个数\(a_1\) ~ \(a_n\)，给定\(W\), 判断能否从中选出几个数使得它们的和\(sum\)满足: \(\left\lceil\dfrac{W}{2}\right\rceil \le sum \le W\),如果可以，输出选择的数的编号

从大到小枚举即可，若本身超过\(W\)跳过即可，若不足\(\left\lceil\dfrac{W}{2}\right\rceil\), 继续枚举求和, 两个\(< \left\lceil\dfrac{W}{2}\right\rceil\)的数求和不会超过\(W\)



#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 2e5 + 20;

int n;

LL W;

pair w[N];

int main()

{

	int T;

	scanf("%d", &T);

	while(T -- )

	{

		scanf("%d%lld", &n, &W);

		for(int i = 1; i <= n; ++ i)

		{

			scanf("%d", &w[i].first);

			w[i].second = i;

		}

		sort(w + 1, w + n + 1, greater>());

		vector vec;

		LL sum = 0;

		for(int i = 1; i <= n; ++ i)

		{

			if(w[i].first > W) continue;

			sum += w[i].first; vec.push_back(w[i].second);

			if(sum >= (W + 1) / 2) break;

		}	

		if(sum < (W + 1) / 2) { printf("-1\n"); continue; }

		printf("%d\n", vec.size());

		for(auto x: vec) printf("%d ", x);

		puts("");

	}

	return 0;

}

D

给两个字符串，定义\(S(C, D) = 4 \times LCS(C, D) - \left|C\right| - \left|D\right|\), 求两个字符串的子串\(C, D\)的最大\(S\)

定义\(f[i][j]\)为以\(A_i\)和\(B_j\)作为结尾的最大值

当\(A_i = B_j\)时， \(f[i][j]\) 可以从 \(f[i - 1][j - 1] + 4 - 2\)转移

当\(A_i \ne B_j\)时, \(f[i][j]\) 可以从 \(f[i - 1][j] - 1\) 和 \(f[i][j - 1] - 1\)转移



#include <bits/stdc++.h>

using namespace std;

const int N = 5000 + 20;

char a[N], b[N];

int n, m, f[N][N];

int main()

{

	scanf("%d%d", &n, &m);

	scanf("%s%s", a + 1, b + 1);

	int res = 0;

	for(int i = 1; i <= n; ++ i)

	for(int j = 1; j <= m; ++ j)

	{

		if(a[i] == b[j])

		f[i][j] = max(f[i][j], f[i - 1][j - 1] + 2);

		f[i][j] = max(f[i][j], max(f[i - 1][j], f[i][j - 1]) - 1);

		res = max(f[i][j], res);

	}

	printf("%d\n", res);

	return 0;

}

E

对于第\(i\)个数来说，找到\(a_i \ xor \ a_j\)最小的连边\((i, j)\)，只有最后形成一棵树才是合法的，问最少删去几个数，可以使得序列合法，\(a_i\)互不相同

01 trie建树，每次分叉的时候，只保留一个子树和另一个子树的一条链，递归求最大可保留点数即可.



#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 * 31 + 10;

int son[N][2], idx, n;

void insert(int x)

{

	int p = 0;

	for(int i = 30; i >= 0; -- i)

	{

		int u = x >> i & 1;

		if(!son[p][u]) son[p][u] = ++ idx;

		p = son[p][u];

	}

}

int query(int p)

{

	if(!son[p][1] && !son[p][0]) return 1;

	else if(!son[p][1])	return query(son[p][0]);

	else if(!son[p][0])	return query(son[p][1]);

	else return max(query(son[p][0]) + 1, query(son[p][1]) + 1);

}

int main()

{

	scanf("%d", &n);

	for(int i = 1; i <= n; ++ i)

	{

		int x;

		scanf("%d", &x);

		insert(x);

	}

	printf("%d\n", n - query(0));

	return 0;

}

2020.11.17

巴特西

Codeforces Round #683 (Div. 2, by Meet IT)

A

B

C

D

E

最新文章

热门文章