CF Div 1 637 题解/实录

前天晚上我打了Codeforces Div1 637，然后爬了……惨惨，掉了好多分。

本来昨天相当没心情写记录。因为我只想出来了ABCD，会了F，结果E根本毫无头绪，想不了。结果今天CF上说E题假了，那场比赛的Div1要unrated了，我就来记录一下自己是怎么爬的，顺便写一下题解。。

A. Nastya and Strange Generator

一句话题意：给你一个序列，问你是不是按照某个规则生成的

这样的序列的产生方式，一定是由若干个上升的段组成的，每个段的数是连续的，最右面的段的数字最小。。暴力判一下

这个题还没有爬，五分钟过了。。

int T;
int main() {
	read(T);
	while(T--){
		int n;
		read(n);
		vector<int> p(n+2,0),rp(n+2,0),vis(n+2,0);
		for(int i=1;i<=n;i++){
			read(p[i]);
			rp[p[i]] = i;
		}
		int ok = 1;
		for(int i=1;i<=n;i++){
			int cp = rp[i];
			if(vis[cp])continue;
			for(int j=cp;!vis[j] && j<=n;j++){
				vis[j] = 1;
				ok&=(p[j] == p[cp]+j-cp);
			}
		}
		cout<<(ok?"Yes":"No")<<"\n";
	}
	return 0;
}

B. Nastya and Scoreboard

一句话题意：给你n个数字灯的状况。让你再点亮恰好k个，最后的数字最大为多少？可以前导0. n k 2000

这个大概就是进行dp，dp[i][j]记录第i个灯之前点亮了j次，在所有第i个灯中是第几大的。记录转移的来源，每次排序离散化即可。

这个题目我花了十八分钟，其中有一个原因就是我没有发现题面中给出了每一个数字的编码。

int a[10] = {119,18,93,91,58,107,111,82,127,123};
int n,k,c[2020],dp[2020][2020],fr[2020][2020],bcnt[2020];
int main() {
	for(int i=0;i<200;i++)bcnt[i] = __builtin_popcount(i);
	memset(fr,7,sizeof(fr));
	read(n,k);
	for(int i=1;i<=n;i++){
		string cc;
		cin>>cc;
		for(int j=0;j<7;j++){
			c[i] = c[i]*2+cc[j]-'0';
		}
	}
	dp[1][0] = 1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=k;j++){
			if(!dp[i][j])continue;
			for(int ch=0;ch<10;ch++){
				if((a[ch]&c[i]) == c[i] && dp[i][j]*10+ch>dp[i+1][j+bcnt[a[ch]]-bcnt[c[i]]]){
					dp[i+1][j+bcnt[a[ch]]-bcnt[c[i]]] = dp[i][j]*10+ch;
					fr[i+1][j+bcnt[a[ch]]-bcnt[c[i]]] = ch;
				}
			}
		}
		vector<int> U;
		U.PB(0);
		for(int j=0;j<=k;j++)U.PB(dp[i+1][j]);
		sort(all(U));
		U.erase(unique(all(U)),U.end());
		for(int j=0;j<=k;j++)dp[i+1][j] = lower_bound(all(U),dp[i+1][j])-U.begin();
	}
	if(fr[n+1][k]<10000){
		string S;
		int cp = k;
		for(int i=n+1;i>1;i--){
			S+='0'+fr[i][cp];
			cp-=bcnt[a[fr[i][cp]]]-bcnt[c[i-1]];
		}
		reverse(all(S));
		cout<<S<<endl;
	}else{
		cout<<-1<<endl;
	}
	return 0;
}

C. Nastya and Unexpected Guest

0,1,…,n个点构成的数轴称为道路。小D在0点，他想到达号点。有个不同位置是安全岛，为。0和n都是安全岛。红绿灯绿g秒红r秒循环，只有绿时候才能走，红的时候必须在安全岛。r,g <2000

• 当绿灯亮着时，他必须始终移动
• 他只能在安全岛上更改方向（因为它很安全）
• 在红灯亮起的那一刻，男孩必须在安全岛之一上。绿灯亮时，他可以继续向任何方向移动。
• 任何时候到n号点就赢了

这个题我爬了……我写了个bitset，用了35分钟。花了18分钟让bitset成功运行，结果tle了。花了45分钟写了个dijkstra，还是tle了，最后用了15分钟变成不用优先队列的了，才通过。比赛就结束了。题目并不难……只是我太爬了。

首先我们观察到答案最多是千万级别的(我一开始算成了1e9导致自己失败)。原因是我们至多访问m个安全岛，每两个之间最多r+g=2000秒。然后我们就可以跑一个类似dijkstra的东西……复杂度。

const int N = 2020;
int n,m,d[10010],g,r;

bool vis[11000010];
ll mdi[11000010];
ll ans = 1e18;

vector<int> Q[2020];
int main() {
	read(n,m);
	for(int i=0;i<m;i++)read(d[i]);
	sort(d,d+m);
	read(g,r);
	memset(mdi,7,sizeof(mdi));
	mdi[g] = 0;
	Q[0].PB(g);
	int cnt = 1,cd = 0,cp = 0;
	while(cnt){
		for(auto ech:Q[cp]){
			if(vis[ech])continue;
			vis[ech] = 1;
			mdi[ech] = cd;
			int a = ech/(g+1),b = ech%(g+1);
			if(a!=m-1 && b>=d[a+1]-d[a]){
				int tgt = ech+g+1-(d[a+1]-d[a]);
				if(!vis[tgt]){
					Q[(cp+d[a+1]-d[a])%N].PB(tgt);
					cnt++;
				}
			}
			if(a && b>=d[a]-d[a-1]){
				int tgt = ech-g-1-(d[a]-d[a-1]);
				if(!vis[tgt]){
					Q[(cp+d[a]-d[a-1])%N].PB(tgt);
					cnt++;
				}
			}
			if(a == m-1){
				cout<<cd<<endl;
				return 0;
			}
			if(b == 0){
				Q[(cp+r)%N].PB(ech+g);
				cnt++;
			}
		}
		cnt-=Q[cp].size();
		Q[cp].clear();
		cd++;
		cp = (cp+1)%N;
	}
	cout<<-1<<endl;
	return 0;
}

D. Nastya and Time Machine

这个题质量还不错。赛后做的，我的做法还挺简单。

题解：给你一颗树。你需要构造一个序列(v,t)，使得相邻两个状态要不然t’=t+1,v’和v相邻，要不然v’=v,t'<t。要求每个状态不超过一次访问，树中所有节点都访问过，而且最大的t要最小。

这个题的做法如下：首先我们注意到，如果一个节点有n个儿子，这个节点又不是根节点，那么这个节点一定要访问n+1次。然后如果我们还需要有一次时间穿梭，就需要访问n+2次。比如一个4个儿子的节点，父亲访问他的时候时间是3，那么这个节点的访问时间序列我们就让他是3-(子节点)-4-(子节点)-5-(时间穿梭)-0-(子节点)-1-(子节点)-2，这样我们知道他的父亲访问他之前时间是2，他回去的时间是3，恰好差1。这种构造方法可以保证答案最优，由于我打字打累了，证明留给读者。

int n,u,v;
vector<int> G[100010];

vector<pii> Q;
void dfs(int num,int t,int fa = -1){
	int orit = t;
	Q.PB(MP(num,t));
	int rem = G[num].size()-(fa!=-1);
	for(auto ct:G[num]){
		if(ct == fa)continue;
		if(orit>rem && t>=orit && t!=0){
			t = orit-rem-1;
			Q.PB(MP(num,t));
		}
		t+=1;
		dfs(ct,t,num);
		Q.PB(MP(num,t));
		rem--;
	}
	if(fa!=-1 && t!=orit-1) Q.PB(MP(num,orit-1));
}

int main() {
	read(n);
	for(int i=1;i<n;i++){
		read(u,v);
		G[u].PB(v);
		G[v].PB(u);
	}
	dfs(1,0);
	cout<<Q.size()<<endl;
	for(auto ct:Q)cout<<ct.F<<' '<<ct.S<<endl;
	return 0;
}

E. Nastya and Bees

这道题，如果没有假出题人将绝杀，可惜的确假了。

（挖个坑，虽然假题我还是想观摩一下）

F. Nastya and CBS

一句话题意：一个任意多种括号的括号序列，支持修改和询问某一段合法不合法。

我还没有写这个题，但是我阅读了一份jiangly的AC代码（这是真的LGM，orz！）。

:(实在写不动了，想了解的自己去看吧，我估计做Div1F的人也没几个，不会看我写题解的。