Atcoder Grand Contest 011&012

012E Camel and Oases

题目描述

点此看题

解法

考试时直接切了，不知道这题有什么难的，我都会做的题肯定是水题。

首先有一个问题转化：我们可以将原序列划分为 \(\log\) 个连续段，使得每一段的 \(\max(x_i-x_{i-1})\leq v_j\)，其中 \(v_j=\frac{k}{2^j}\) 表示第 \(j\) 次跳跃后背包的容量（注意 \(v_j=0\) 也是合法的，但是只能存在一次）

首先考虑全局存不存在合法方案，一个重要的观察是只要我们确定 \(v\) 的分配顺序，那么可以通过贪心来确定段的划分，就是按照这个顺序能取就取。解决顺序问题可以考虑状压 \(dp\)，设 \(dp[s]\) 表示已使用的 \(v\) 集合为 \(s\) 的最远延伸距离。

那么怎么确定单个位置的答案呢？一个简单的观察是：\(x_i-x_{i-1}>k\) 的最多只存在 \(\log k\) 对，要不然就全局无解。所以我们以 \(x_i-x_{i-1}>k\) 为断点，由于每个点为起点都会取遍段的位置之后再离开，段中每个位置的答案是一样的。

设段是 \([l,r]\)，设 \(f(s),g(s)\) 分别表示前缀 \(/\) 后缀的最远延伸位置，那么可以枚举集合 \(s\)，设补集是 \(t\)，判断条件就是：

都可以暴力做，时间复杂度 \(O(n\log n)\)

#include 
#include 
#include 
using namespace std;
const int M = 1<<21;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,k,t,v[30],p[30],l[22][M],r[22][M],x[M],f[M],g[M];
signed main()
{
	n=read();m=read();
	for(int x=m;x;x/=2) v[k++]=x;v[k++]=0;
	for(int i=1;i<=n;i++) x[i]=read();
	for(int w=0;w=1;i--)
		{
			if(x[i+1]-x[i]<=v[w])
				r[w][i]=r[w][i+1];
			else r[w][i]=i;
		}
	}
	memset(g,0x3f,sizeof g);g[0]=n+1;
	for(int s=0;s<(1<>i&1))
		{
			f[s|(1<m) p[++t]=i;
	if(t>k)
	{
		for(int i=1;i<=n;i++) puts("Impossible");
		return 0; 
	}
	for(int x=1,y;x<=n;x=y+1)
	{
		y=r[0][x];int fl=0,t=(1<=x-1 && g[s^t]<=y+1);
		for(int i=x;i<=y;i++)
			puts(fl?"Possible":"Impossible");
	}
}

011D Half Reflector

题目描述

点此看题

解法

首先要知道单次操作之后会有什么样的变化，如果首位是 A 那么会立马弹开，如果首位是 B，那么经过它之后会变成 A，我们继续考虑后续的情况，关键的观察是球的上一个位置一定是 A：

• 下一个位置是 B，那么对于 AB 会变成 AA
• 下一个位置是 A，那么对于 AA 会变成 BA

使用归纳法，我们可以发现球的作用相当于给每个位置左移之后取反（在环的意义下，正好最后一个位置一定是 A）

那么就可以通过打整体标记实现 \(O(k)\) 模拟了。考试时我观察数据发现后缀会趋向 ABABAB... 这种类型，而且在 \(2n\) 次之内就会稳定下来，但是我们需要保留原来 \(k\) 的奇偶性，这样我们就可以在 \(O(n)\) 的时间内模拟了。

#include 
#include 
using namespace std;
const int M = 200005; 
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,k,a[M];char s[M];
signed main()
{
	n=read();k=read();scanf("%s",s+1);
	for(int i=1;i<=n;i++) a[i]=s[i]-'A';
	int t=0,p=1;k=min(k,2*n+(k&1));
	while(k--)
	{
		if(t^a[p]) t^=1,p=p%n+1;
		else a[p]^=1;
	}
	for(int i=p;i<=n;i++) putchar((a[i]^t)?'B':'A');
	for(int i=1;i