[数据结构与算法]Educational Codeforces Round 123 (Rated for Div. 2) A-E

题目链接:?http://codeforces.com/contest/1644

A. Doors and Keys

水题

#include<bits/stdc++.h>
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 = 3e5 + 10;



int main() {
	int t;
	char s[100];
	scanf("%d", &t);
	while (t--) {
		scanf("%s", s);
		int f1, f2, f3;
		f1 = f2 = f3 = 0;
		int ans = 0;
		for (int i=0; s[i]; i++) {
			switch (s[i]) {
			case 'r':
				f1 = 1;
				break;
			case 'g':
				f2 = 1;
				break;
			case 'b':
				f3 = 1;
				break;
			case 'R':
				if (!f1)
					ans = 1;
				break;
			case 'G':
				if (!f2)
					ans = 1;
				break;
			case 'B':
				if (!f3)
					ans = 1;
				break;
			}
		}
		puts(ans?"NO":"YES");
	} 
	return 0;
}

B. Anti-Fibonacci Permutation

暴力枚举即可。

#include<bits/stdc++.h>
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 = 3e5 + 10;
 
int number[mx];
 
int main() {
	int t;
	
	scanf("%d", &t);
	while (t--) {
		int n;
		scanf("%d", &n);
		for (int i=1;i<=n;i++) 
			number[i] = (n - i + 1);
		int m = n, j;
		while (m--) {
			for (j=3;j<=n;j++){
				if (number[j] == number[j-1] + number[j-2]) {
					break;
				}
			}
			if (j == n+1)
				for (int i=1;i<=n;i++)
					printf("%d%c", number[i], i==n?'\n':' ');
			else 
				m++;
			prev_permutation(number + 1, number + n + 1); 
		}
	}
	return 0;
}

C. Increase Subarray Sums

暴力枚举

#include<bits/stdc++.h>
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 = 5e3 + 10;

int number[mx];
int val[mx][mx];
int res[mx];

int main() {
	int t;
	
	scanf("%d", &t);
	while (t--) {
		int n,m;
		scanf("%d%d", &n, &m);
		for (int i=1;i<=n;i++) {
			scanf("%d", number + i);
		}
		
		for (int i=1;i<=n;i++) {
			res[i] = -1e9;
			for (int j=1;j+i-1<=n;j++) {
				val[j][j+i-1] = val[j][j+i-2] + number[j+i-1];
				res[i] = max(res[i], val[j][j+i-1]);
			}
		}
		
		for (int k=0;k<=n;k++) {
			int ans = 0;
			for (int i=1;i<=n;i++) {
				ans = max(ans, res[i] + min(i,k) * m);
			}
			printf("%d ",ans);
		}
		puts("");
	}
	return 0;
}

D. Cross Coloring

这种情况一般想到逆序处理，然后根据行列关系，求出新插入一个行列是否已经被之前的完全覆盖了，如果是则该插入不生效。

#include <bits/stdc++.h>
#include <windows.h>
#include <time.h>
#include <sys/time.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int mx = 3e5 + 10;
typedef int a[8];
const int mod = 998244353;

set <int> xi, yi;
int x[mx], y[mx];

ll qpow(ll x, ll y)
{
	ll ans = 1;
	while (y) {
		if (y&1) ans = ans * x % mod;
		y >>= 1;
		x = x * x % mod; 
	}
	return ans;
}

int main()
{
	int t;
	int n,m,k,q;
	scanf("%d", &t);
	while (t--) {
		xi.clear();
		yi.clear();
		scanf("%d%d%d%d", &n, &m, &k, &q);
		int ret = 0;
		for (int i=1;i<=q;i++)
			scanf("%d%d", x+i, y+i);
		for (int i=q; i; i--) {
			int f1 = 0, sum = 0;
			int xs = xi.size();
			int ys = yi.size();
			if (xi.find(x[i]) == xi.end()) {
				sum += m - ys;
				xi.insert(x[i]);
				f1++;
			}
			if (yi.find(y[i]) == yi.end()) {
				sum += n - xs;
				yi.insert(y[i]);
				f1++;
			}
			if (f1 == 2) sum--;
			
			if (sum)
				ret++;
		}
		printf("%lld\n", qpow(k, ret));
	}
	
	return 0;
}

E. Expand the Path

如果可以想到只需要去考虑每个相邻的DR或者RD的复制情况这个问题就好解决了。为什么呢？如果是DDDDDDR或者RRRRRD的情况，我们当然可以直接跳过到最后的DR和RD去考虑，因为本身字符就可以无限复制的而且是只能增多不能减少的，所以不管前面有多少个D或者R都直接考虑进来因为如果还需要就用最后一个复制就行了。然后我就考虑相邻的DR或者RD无限复制的情况就行了，这里就是贪心，肯定是最先复制越前面的D和R越好，后面的就不会越界。然后我们需要枚举每一处的DR或者RD作为“最前面”的复制D和R。然后需要考虑到前一个枚举的RD和后一个枚举的RD可行矩阵的交集，需要减去。每个DR复制的可行解肯定是一个矩阵，这一想便知。

#include<bits/stdc++.h>
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 = 3e5 + 10;
char str[mx];
int suf_d[mx];
int suf_r[mx];
 
int main() {
	int t;
	scanf("%d", &t);
	while(t--) {
		int n;
		scanf("%d", &n);
		scanf("%s", str + 1);
		int len = strlen(str + 1);
		suf_d[len+1] = suf_r[len+1] = 0;
		
		for (int i=len; i; i--) {
			suf_d[i] = suf_d[i+1];
			suf_r[i] = suf_r[i+1];
			if (str[i] == 'D') suf_d[i]++;
			else suf_r[i]++;
		}
		
		str[0] = str[1];
		int H = n, W = n;
		int p = 1;
		ll ans = 0;
		for (; str[p] == str[p-1]; p++)
			ans++;
		if (str[p-1] == 'D') H -= ans;
		else W -= ans;
		
		if (p == len + 1) {
			printf("%d\n", n);
			continue;
		}
		
		int lx = n - H, ly = n - W;
		while (p <= len) {
			int q = p + 1;
			while (str[q] == str[q-1]) q++;
			int ld = suf_d[q];
			int lr = suf_r[q];
			ans += 1ll * (H - ld) * (W - lr);
			ans -= 1ll * (lx - (n - H)) * (ly - (n - W));
			
			lx = n - ld;
			ly = n - lr;
			p = q;
			H = n - (suf_d[1] - suf_d[p]);
			W = n - (suf_r[1] - suf_r[p]);
		}
		printf("%lld\n", ans);
	}
	return 0;
}