2017-2018 Northwestern European Regional Contest (NWERC 2017)

F. Factor-Free Tree

每次dfs(l,r)想找任意一个l<=i<=r,使得li<l&&r<ri,然后递归到dfs(l,i-1)和dfs(i+1,r)。lbn可持久化线段树卡着内存过了。

官方题解:

每次从两边一起往里面for,暴力找就行了。复杂度:

\(T(n)=max_{0\leq x\leq n/2} \{2x+T(x)+T(n-x)\}\)

据说是\(O(n\log n)\)的(感觉上是说越靠中间虽然越晚找到但分得越平均),妙啊。

J. Juggling Troupe

各种性质随便猜,然后很自然从左往右推,维护左边全是01,往右边发射了几个,快速模拟往左发射一个球的过程。

赛场上全程死在C题上了,感觉C那个判定有一万个坑,早知道就按lbn那样写了。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
char s[N];
int main() {
	scanf("%s", s);
	int n = (int) strlen(s);
	long long gor = 0;
	deque<int> zero;
	for (int i = 0; i < n; ++ i) {
		long long x = s[i] - '0' + gor;
		gor = 0;
		while (x >= 2) {
			gor ++;
			x -= 2;
			if (!zero.empty() && zero.back() == i - 1) {
				s[zero.back()] = '1';
				zero.pop_back();
			}
			else if (zero.empty()) {
				if (i) {
					x ++;
					zero.push_front(0);
					s[0] = '0';
				}
			}
			else {
				int step = max(1LL, min(i ? x + 1 : (x + 2) / 2, i - 1LL - zero.back()));
				gor --;
				x += 2;
				gor += step;
				x -= 2 * step;
				if (i) x += step;
				s[zero.back()] = '1';
				s[zero.back() += step] = '0';
			}
		}
		s[i] = '0' + x;
		if (s[i] == '0') zero.push_back(i);
	}
	puts(s);
}