CF div2 round 960

C. Mad MAD Sum

手玩规律题，预处理两次就能得到一个规律的答案。

#include<bits/stdc++.h>
using namespace std;
#define ls(x) (x<<1)
#define rs(x) ((x<<1)+1)
int read() {
	int ret = 0; char c = getchar();
	while (c < '0' || c>'9') c = getchar();
	while (c >= '0' && c <= '9') ret = ret * 10 + c - '0', c = getchar();
	return ret;
}
int last[maxn], a[maxn];
signed main() {
	int t = read();
	while (t--) {
		int n = read();
		vector<int>b;
		int mx = 0;
		for (int i = 1; i <= n; i++)last[i] = 0;
		long long ans = 0;
		long long res = ans;
		for (int i = 1; i <= n; i++) {
			a[i] = read();
			if (last[a[i]] && a[i] > mx)mx = a[i];
			last[a[i]] = i;
			b.push_back(mx);
			ans += mx; res += a[i];
		}
		res += ans; ans = 0; int ls = 0; mx = 0;
		for (int i = 1; i < n; i++) {
			if (b[i] == ls)mx = ls;
			ls = b[i]; ans += mx;
			b[i] = mx;
		}
		res += ans;
		for (int i = b.size()-1; i >0; i--) {
			//cout << i << ' ';
			if (ans == 0)break;
			ans -= b[i];
			res += ans;
		}
		cout << res << endl;
		
	}
}

D. Grid Puzzle

贪心放置方块即可通过。。能放两格方块就放两格。考虑复杂了属于是。

#include<bits/stdc++.h>
using namespace std;
#define ls(x) (x<<1)
#define rs(x) ((x<<1)+1)
int read() {
	int ret = 0; char c = getchar();
	while (c < '0' || c>'9') c = getchar();
	while (c >= '0' && c <= '9') ret = ret * 10 + c - '0', c = getchar();
	return ret;
}
int a[maxn];
signed main() {
	int t = read();
	while (t--) {
		int n = read();
		int ans =0;
		bool x1 = 0,x2=0;
		for (int i = 1; i <= n; i++)
		{
			a[i] = read();
		}
		int cnt = 0;
		for (int i = 1; i <= n;i++ ) {
			if (!a[i]) {
				x1 = 0, x2 = 0; continue;
			}
			if (a[i] > 4)ans++, x1 = 0, x2 = 0;
			else if (a[i] > 2) {
				if (x2) {
					x2 = 0, x1 = 1; ans++;
				}
				else if (x1) {
					x2 = 1; x1 = 0; ans++;
				}
				else x1 = 0, x2 = 0, ans++;
			}
			else {
				if (x1)
					x1 = 0;
				else ans++,x1=1;
				x2 = 0;
			}
		}
		cout << ans << endl;
	}
}
E题看题解像点分治但是由于大码量所以没有补