Codeforces Round 898 (Div. 4) (CF1873)

Coinred001，堂堂出道（
前面的水题打得太慢了（因为缺乏经验）

A. Short Sort

水题，手动枚举6种情况是最快的能AC的。

B. Good Kid

看数据范围，\(O(n^2)\) 枚举即可。（Div4不要想太多）

C. Target Practice

暴力，把 \(10 \times 10\) 的靶子直接输进数组。

D. 1D Eraser

因为是直接覆盖 \(k\) 个块，所以遇到白色的直接往后刷 \(k\) 个块。

E. Building an Aquarium

直接将 \(a\) 由小到大排序，再从前往后遍历 \(a\)，考虑水加到该高度需要多少水（可利用对之前 \(a\)的求和 \(sum\) 算出wat=i*a[i]-sum），在恰好少于给定水量 \(x\) 后通过整除算出 h=a[i]+(x+sum-i*a[i])/i。

F. Money Trees

扫一遍 \(h\)，求出能选择的区间。
之后枚举右端点，在 \(sum_a \leq k\) 的情况下滑动 \(l\) 求出最大长度。
当区间不能选时，若 \(a_r \leq k\) 可直接选单个，长度为 \(1\)。

G. ABBC or BACB

不难发现本题操作数就是可通过B消掉的A的个数
所以考虑夹在每个B之间以及两端有多少个A，因为每个B只能对应一段A，因此考虑舍弃A数目最少的一段。

H. Mad City

（这题赛时没有A，赛后WA on test 2，因为写错对拍不知道错哪里，警钟长鸣）
有趣的基环树上追及问题。
只要跑者到达第一次到达环上的点的时间，早于追者到达环上后从较短路上到达那个点的时间，那么就能够逃脱。
所以只要找到环，记录所有点及其大小，通过对环上每点按顺序编号可求得环上两点的距离。bfs跑者与追者到环上点的距离以及第一次入环的点，即可求得。
本题sb：直接拿环上两点作差得到距离，完全忘了重新编号的事，于是爆WA调一天（

Educational Codeforces Round 155 (Rated for Div. 2) (CF1879)

拿下9000+名，寄。

A. Rigged!

题目要求，选择合适的重量，使得第一个人力量大于此的同时，耐力在能举起的人中最长。
所以要尽可能用大重量卡掉耐力久的人，排序遍历比较即可。

bool cmp(Node a,Node b){return (a.e!=b.e)?(a.e>b.e):(a.p>b.p);}
...
sort(a+1,a+n+1,cmp);
int maxs=0,i;
for(i=1;i<=n;i++)
{
	if(a[i].p==1) break;
	maxs=max(maxs,a[i].s);
}
if(maxs<a[i].s)	cout<<maxs+1<<endl;
else			cout<<-1<< endl;

WA 3发的原因：输入格式看错了，排序想反了。

B. Chips on the Board

有点像ICPC网络赛的一题，想了挺久。
现在要使网格上每个点都有同行或同列的点被标记且被标记点 \(a_x\) 与 \(b_y\) 总和最小。
那么只要挑 \(a_x\) 最小的一行或者 \(a_y\) 最小的一列即可

C. Make it Alternating

计数题，操作：删除一个元素，最终使01序列的相邻元素互不相同，求最小操作数及其方案数。
统计连续段，将连续段删除至一个元素即可，方案数即每一段内方案个数之积乘最小操作数的全排列数
本场sb：由于排列组合水平严重下降，以为每段内方案做全排列再求积即可。

D. Sum of XOR Functions

异或和类型，不会，补了再说

Codeforces Round 899 (Div. 2) (CF1882)

尽力了（

A. Increasing Sequence

有点东西的构造。
递增数列，要让最后一个值最小，只要设置第一个数为1，之后每次递增1即可，遇到相等再加1即可。

B. Sets and Union

\(s_{i,j}\) 的范围很小，最终考虑暴力。
记录一个数在几个集合里面，枚举删掉带某一个数的集合后最终剩几个数，取最大值。

C. Card Game

这几天第一次用dp思想做题（
（虽然答案似乎用不着）
某一位被操作后，其前面的每一位的奇偶性都不再改变，考虑dp。
\(dp_{i,0/1}\) 表示为第i位作为偶/奇的最大值。
则转移为：

\[ dp_{n,0}=0, dp_{n,1}=max(0,a_n) \\ dp_{i,0}=\max\{dp_{i,0},dp_{i+1,0},dp_{i+1,1}\}; \\ dp_{i,1}=\max\{dp_{i+1,1}+a[i],dp_{i+1,0}+\max(0,a_i),dp_{i,1}\}; \]

从后往前的原因：最后一位的状态是确定的。

D. Tree XOR

不会做但挺有意思，以后看（

Codeforces Round 900 (Div. 3) (CF1878)

18000+，下大分丢大人场

A. How Much Does Daytona Cost?

以为是暴力结果被叉了。
实际上，长度为一的序列的众数就是那个唯一的元素，故是否存在子段众数为 \(k\)，只要判断这个元素是否存在过。

B. Aleksa and Stack

很神奇的构造题，但是写了半个钟头
之前都在想用先乘后除的方式构造，无一例外地爆long long了。
但是打表发现对于数列 \(a_i=i\) 来说，\(i=7\) 以后便不存在反例。
故取 \(a_i=i+8\) 即可。

C. Vasilije in Cacak

基础二分题。
设 \(\text{Calc}(l,r)\) 为 \(l\) 到 \(r\) 之间每个数之和
可知若存在 \(r\) 使得 \(Calc(r-k+1,r) \leq x \leq Calc(r-k+2,r+1)\)，则方案必然存在（证明：将元素从小到大往小一一位，直至变成更小的连续 \(k\) 个数）
有单调性，二分即可。

E. Iva & Pav

看赛时这题做的人比D多于是先开这题。
结果思维绕进对每一位的操作出不来了。
实际上由于与（或）和的单调性以及其可重复贡献性，直接ST维护区间与和，再二分即得。

D. Reverse Madness

思路简单，码量略大。
考虑分割出的子段里面有哪些有效的翻转操作即可。
贴码了

n=read(),k=read();
	scanf("%s",s+1);
	for(int i=1;i<=k;i++) l[i]=read();
	for(int i=1;i<=k;i++) r[i]=read();
	q=read();
	for(int i=1;i<=q;i++) x[i]=read();
	sort(x+1,x+q+1);
	for(int i=1,t=1;i<=k&&t<=q;i++)
	{
		vi rev,tmp;
		for(;t<=q && x[t]<=r[i];t++)
			rev.push_back(x[t]);
		if(rev.empty()) continue;
		for(int j=0;j<(int)rev.size();j++)
			rev[j]=min(rev[j],l[i]+r[i]-rev[j]);
		sort(rev.begin(),rev.end());
		for(int j=0;j<(int)rev.size();j++)
		{
			int p=1;
			for(;j+1<(int)rev.size() && rev[j]==rev[j+1];j++,p++);
			if(p&1) tmp.push_back(rev[j]);
		}
		rev.swap(tmp);
		auto iter=rev.begin();
		int p=0,mid=(l[i]+r[i])>>1;
		for(int j=l[i];j<=mid;j++)
		{
			if(iter!=rev.end() && j==*iter)
				p=1-p,iter=next(iter);
			if(p) swap(s[j],s[l[i]+r[i]-j]);
		}
	}
	printf("%s\n",s+1);