Codeforces Round #802 (Div. 2) 题解

题目链接：https://codeforces.com/contest/1700

A. Optimal Path

解题思路：贪心，取第一行和最后一列值最小。

#include 
using namespace std;
#define inf 0x3f3f3f3f
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
typedef long long ll;
typedef unsigned long long ull;
const int mx = 2e5 + 10;
const int mod = 998244353;
typedef pair <int, int> pa;
 
 
int main() {
	int n, m;
	
	int t;
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d", &n, &m);
		printf("%lld\n", m * (m + 1) / 2 + 1ll * m * n * (n + 1) / 2 - m);
	}
	
    return 0;
}

B. Palindromic Numbers

解题思路：如果输入的数x最高位不是9，那么把回文数设成9999....，如果输入的最高位数是9，那么就把回文数设成11111....，这样就可以了。

#include 
using namespace std;
#define inf 0x3f3f3f3f
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
typedef long long ll;
typedef unsigned long long ull;
const int mx = 2e5 + 10;
const int mod = 998244353;
typedef pair <int, int> pa;
 
char s[mx];
 
int main() {
	int n, m;
	
	int t;
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		scanf("%s", s+1);
		for (int i=1;i<=n;i++)
			s[i] = '9' - s[i] + '0';
		if (s[1] != '0') {
			printf("%s", s+1);
		} else {
			int flag = 0;
			for (int i=n;i;i--) {
				//cout << flag << endl;
				if (i==n) {
					flag = (s[i] - '0' + 2) / 10;
					s[i] = (s[i] - '0' + 2) % 10;
					s[i] += '0';
				} else {
					int val = (s[i] - '0' + 1 + flag);
					s[i] = val % 10;
					flag = val / 10;
					s[i] += '0';
				}
			}
			printf("%s", s+1);
		}
		puts("");
	}
	
    return 0;
}

C. Helping the Nature

解题思路：这种题目就要转化为差分，那么三个条件等价于差分就是：

                1）s[1] - 1, s[i + 1] + 1

                2）s[i] - 1

                3）s[1] + 1

所以如果差分数据第i个位置大于0，那么就选操作（2），如果小于0，就选操作1，最后在看第一个位置的值是多少，大于0就用（2），小于0就用（3）。因为（1）会影响第一个位置的值，所以需要放在最后考虑。

#include 
using namespace std;
#define inf 0x3f3f3f3f
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
typedef long long ll;
typedef unsigned long long ull;
const int mx = 2e5 + 10;
const int mod = 998244353;
typedef pair <int, int> pa;
 
int a[mx];
ll b[mx];
 
int main() {
	int n, m;
	
	int t;
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		for (int i=1;i<=n;i++){
			scanf("%d", a+i);
		}
		for (int i=1;i<=n;i++) {
			b[i] = a[i] - a[i-1];
		}
		ll ret = 0;
		for (int i=2;i<=n;i++) {
			if (b[i] > 0) {
				ret += b[i];
			} else {
				ret -= b[i];
				b[1] += b[i];
			}
		}
		ret += abs(b[1]);
		printf("%lld\n", ret);
	}
	
    return 0;
}

D. River Locks

解题思路：假设给定时间为t，总容量容积为S，那么需要开的水龙头就是(S - 1) / t + 1 = k，当然水龙头肯定是从最高位开最好，这时候流出的总量肯定不小于S，但是存在某些水池不满的情况，这是为什么呢，因为剩下的水都流出到n + 1的位置了，那么肯定是这k个水龙头中的一个不满，所以在添加更多的水龙头也没用，需要增加t。因此得到t是单调的，可以去二分找最小的t就可以了。

#include 
using namespace std;
#define inf 0x3f3f3f3f
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
typedef long long ll;
typedef unsigned long long ull;
const int mx = 2e5 + 10;
const int mod = 998244353;
typedef pair <int, int> pa;
 
int a[mx];
ll b[mx];
 
bool check(int n, int v) {
	ll sum = 0;
	for (int i=1;i<=n;i++) {
		sum += v;
		if (a[i] > sum)
			return 0;
		sum -= a[i];
	}
	return 1;
}
 
int main() {
	int n, m;
	scanf("%d", &n);
	ll sum = 0;
	for (int i=1;i<=n;i++) {
		scanf("%d", a+i);
		sum += a[i];
	}
	int l = 1, r = 1e9;
	while (l < r) {
		int mid = (l + r) >> 1;
		if (check(n, mid))
			r = mid;
		else 
			l = mid + 1;
	} 
	//cout << l << endl;
	scanf("%d", &m);
	while (m--) {
		int u;
		scanf("%d", &u);
		if (u < l)
			puts("-1");
		else
			printf("%lld\n", sum / u + (sum % u != 0));
	}
 
    return 0;
}

E. Serega the Pirate

解题思路：假设除了1以外，任意一点它的邻边都有小于它的数（1），那么现在整个矩形肯定“联通”的。那么如果存在一个点不满足（1）条件，那么整个矩形肯定不连通，需要移动。设不满足条件的点为(i,j)，那么想要(i,j)满足条件，要么移动(i,j)要么移动(i,j)的邻点。

        这里有一个结论就是当不满足条件的点大于4个时，肯定无法通过一次移动来令所有点都满足条件。这里就不给出证明了，方法也不难，大家可以自己证明一下。

        那么由此结论，我们可以去暴力所有不满足条件的点进行移动，一个不满足条件的点最多情况就是5（1+4旁边的4个），那么4个也就是20，可以用这20个点去暴力换所有的点如何去check是否满足（1）条件即可，只需要去check之前不满足的或者被移动的两个点和它邻点就行，其他的不用再check了。

#include 
using namespace std;
#define inf 0x3f3f3f3f
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
typedef long long ll;
typedef unsigned long long ull;
const int mx = 4e5 + 10;
const int mod = 998244353;
typedef pair <int, int> pa;
 
vector <int> vec[mx];
vector  vor;
set  ans_set;
int n,m;
 
pa dir[4] = {
		{0, -1},
		{0, 1},
		{-1, 0},
		{1, 0}};
		
bool judge(int x, int y) {
	if (vec[x][y] == 1)
		return 1;
	
	for (int i=0;i<4;i++) {
		int sx = x + dir[i].first;
		int sy = y + dir[i].second;
		if (sx <= 0 || sy <= 0 || sx > n || sy > m)
			continue;
		if (vec[sx][sy] < vec[x][y])
			return 1;
	}
	return 0;
}
 
bool judge_adjacent(int x, int y) {
	for (int i=0;i<4;i++) {
		int sx = x + dir[i].first;
		int sy = y + dir[i].second;
		if (sx <= 0 || sy <= 0 || sx > n || sy > m)
			continue;
		if (!judge(sx, sy))
			return 0;
	}
	return 1;
}
 
int check() {
	int ans = 0;
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=m;j++) {
			if (!judge(i, j)) {
				ans++;
				vor.push_back(pa(i, j));
			}
		}
	}
	return ans;
}
 
void get_ans(int x, int y) {
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=m;j++) {
			
			swap(vec[i][j], vec[x][y]);
			if (judge(i, j) && judge(x, y)) {
				if (judge_adjacent(i, j) && judge_adjacent(x, y)) {
					int flag_1 = 1;
					for (auto temp: vor) {
						if (!judge(temp.first, temp.second)) {
							flag_1 = 0;
							break;
						}
					}
					if (flag_1)
						ans_set.insert(pa(min(vec[x][y], vec[i][j]), max(vec[x][y], vec[i][j])));
				}
			}
			swap(vec[i][j], vec[x][y]);
		}
	}
}
 
int main() {
	scanf("%d%d", &n, &m);
	int x, y;
		
	for (int i=1;i<=n;i++) {
		vec[i].push_back(-1);
		for(int j=1;j<=m;j++) {
			int u;
			scanf("%d", &u);
			vec[i].push_back(u);
		}
	}
	
	int ret = check();
	if (ret == 0)
		printf("0\n");
	else {
		if (vor.size() > 4) {
			puts("2");
			return 0;
		}
		
		for (auto temp: vor) {
			x = temp.first;
			y = temp.second;
			get_ans(x, y);
			for (int i=0;i<4;i++) {
				int sx = x + dir[i].first;
				int sy = y + dir[i].second;
				if (sx <= 0 || sy <= 0 || sx > n || sy > m)
					continue;
				get_ans(sx, sy);
			}
		}
		
		if (ans_set.size() == 0)
			puts("2");
		else
			printf("1 %d\n", ans_set.size());
	}
	
    return 0;
}
/*
3 4
7  3 8 10
2 12 4 11
6 5 9 1
*/

F. Puzzle

解题思路：移动b数组就等于反向操作a数据，那么我们可以同时操作a，b两个数组，最后令两个相等就行了。那么就可以进行这样贪心，如果a、b两个相同的位置都是1，那么就保留，或者在同一列不在同一行，那就置换一下，否则就把1都往前面移（那剩下的0肯定都是满足的，因为1都移走了）。至于为什么可以把多个值放在一块显然是可以的，只是为了更方便理解，实际上每次对单个进行操作的结果是一样的。

#include
using namespace std;
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,(rt<<1)|1
typedef long long ll;
const int mx = 2e5 + 10;
 
int n; 
int a[4][mx];
int cnt[4];
 
int main() {
	scanf("%d", &n);
	int cnta = 0, cntb = 0;
	for (int i=0;i<4;i++) {
		for(int j=1;j<=n;j++) {
			scanf("%d", &a[i][j]);
		}
	}
	
	ll ans = 0;
	for (int i=1;i<=n;i++) {
		for (int j=0; j<4; j++) {
			ans += cnt[j];
			cnt[j] += a[j][i];
		}
		
		for (int j=0;j<2;j++) {
			int mi = min(cnt[j], cnt[j+2]);
			cnt[j] -= mi;
			cnt[j+2] -= mi;
		}
		for (int j=0;j<2;j++) {
			int mi = min(cnt[j], cnt[3-j]);
			cnt[j] -= mi;
			cnt[3-j] -= mi;
			ans += mi;
		}
	}
	for (int i=0;i<4;i++)
		if (cnt[i]) {
			puts("-1");
			return 0;
		}
	
	printf("%lld\n", ans);
	
	return 0;
}