【无标题】

A. Special Characters

分析:AAAAAAA...和AA的贡献是一样的，都为2。

void solve() {
	int n; cin >> n;
	if (n % 2) {
		cout << "NO" << endl;
		return;
	}

	cout << "YES" << endl;
	for (int i = 1; i <= n/2; i ++) {
		if (i%2) {
			cout << "AA";
		}
		else {
			cout << "BB";
		}
	}
	cout << endl;

}

B. Array Fix

分析：ai最多是两位数。我们假设，last是上一个数，a(1)是ai的十位数，a(2)是ai的个位数。

贪心地想，假如a(1)>=last，那我们就要把ai拆分成两个数字，因为一会last更新成a(2)，可以使last尽量小，更有利于后面的操作。

假如a(1)<last，ai>=last，那么ai就不用拆分了。last = ai

假如ai<last，那就没办法了，输出NO

int a[N], b[N];
void solve() {
	int n; cin >> n;
	int pb = 1;
	rep(i, 1, n) {
		cin >> a[i];
	}
 
	int last = 0;
	int f = 1;
	rep(i, 1, n) {
		if (a[i] < last) {
			f = 0;
			break;
		}
		
		if (a[i] < 10) {
			last = a[i];
		}
		else {
			int t1 = a[i] / 10, t2 = a[i] % 10;
			if (t1 <= t2 && t1 >= last) {
				last = t2;
			}
			else {
				last = a[i];
			}
		}
 
	}
	if (f) cout << "YES" << endl;
	else cout << "NO" << endl;
}

C. Arrow Path

分析：很简单的一道dfs（放在B还差不多

char a[3][N];
bool st[3][N];
int f; int n;
int dir[][2] = { {1,0},{0,1},{-1,0},{0,-1} };
void dfs(int r, int c) {
	if (f) return;
	if (r == 2 && c == n) {
		f = 1;
		return;
	}

	for (int i = 0; i < 4; i++) {
		int nr = dir[i][0] + r;
		int nc = dir[i][1] + c;
		if (nr >= 1 && nr <= 2 && nc >= 1 && nc <= n && !st[nr][nc]) {
			st[nr][nc] = 1;
			if (a[nr][nc] == '<') {
				int r2 = nr, c2 = nc - 1;
				if (r2 != r || c2 != c) dfs(r2, c2);
			}
			else {
				int r2 = nr, c2 = nc + 1;
				if (r2 != r || c2 != c) dfs(r2, c2);
			}
		}
	}

}
void solve() {
	cin >> n;
	rep(i, 1, n) cin >> a[1][i];
	rep(i, 1, n) cin >> a[2][i];

	memset(st, 0, sizeof st);
	f = 0;
	st[1][1] = 1;
	dfs(1, 1);

	//tans;
	if (f) cout << "YES" << endl;
	else cout << "NO" << endl;

}

D. Tandem Repeats?

分析：暴力枚举“串联重复”字符串的开头和结尾，再验证该字符串是否符合“串联重复”，这种做法的时间复杂度是，肯定超时了。

于是乎，做题经验告诉我，我应该要找到一种方法，时间复杂度最多为O(n2)，虽然听起来好像是废话，但结合题目中字符串长度最大是5000，就可以猜想，这题的复杂度或许是O（n2）。

正解：倒着枚举字符串一半的长度，最长是n/2。

然后构建一个类似于前缀和的东西，在里面做查询就行。

这题是很好的题目，值得吃透。

void solve()
{
	string s; cin >> s;
	int n = s.size();
	s = '.' + s;
	int pre[5005] = { 0 };
	for (int len = n / 2; len >= 1; len--) {
		fill(pre + 1, pre + 1 + n, 0);
		rep(i, 1, n - len) {
			pre[i] = (s[i] == s[i + len] || s[i] == '?' || s[i + len] == '?');
		}
		rep(i, 1, n) pre[i] += pre[i - 1];
		rep(i, len, n) {
			if (pre[i] - pre[i - len] == len) {
				cout << 2 * len << endl;
				return;
			}
		}
	}
	cout << 0 << endl;
}