CF1693 ABCD 题解

题目链接：https://codeforces.com/contest/1693

这场的题都非常好啊……
因为现在是从 div1 开始做了，所以可能刚开始会有点吃力（这场我就会做一个 1B 呜呜呜）
1A
先把后缀的极长 0 段删去
考虑对于每一个 右移 操作，首先必然和一个 左移 操作一一对应（最后回到原点了），而且必然存在一种映射，使得每个左移操作的位置在右移操作的右边
也就是说每个 -1 必然在对应的 +1 右边，也就是说前面的前缀和必然都是正数
因此可以对序列做前缀和，如果 \(sum[i] \leq 0,i<n\) 那么必然不符合条件，如果 \(sum[n]\neq 0\) 同样不符合条件

// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define pii pair<int,int>
#define pb push_back

using namespace std;

typedef long long ll;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f,maxn=2e5+5;

int n;
ll a[maxn],sum[maxn];
int solve(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	int up=-1;
	for(int i=n;i>=1;i--)if(a[i]){up=i;break;}
	if(up==-1)return 1;
	for(int i=1;i<=up;i++)sum[i]=sum[i-1]+a[i];
	for(int i=1;i<up;i++)if(sum[i]<=0)return 0;
	if(sum[up])return 0;
	return 1;
}

signed main(){
	int te;scanf("%d",&te);
	while(te--)puts(solve() ? "Yes" : "No");

	return 0;
}

1B
贪心一下，子结点的权值之和一定 >= 父节点的

// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define pii pair<int,int>
#define pb push_back

using namespace std;

typedef long long ll;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f, maxn = 2e5+5;

int n;
vector<int>g[maxn];
int l[maxn], r[maxn], cnt=0;
ll sum[maxn];

void dfs(int x,int fat=0){
	if(g[x].size() == 0){
		sum[fat] += r[x];
		++ cnt;
		return ;
	}
	
	for(int u : g[x]){
		dfs(u,x);
	}
	if(sum[x] > r[x]){
		sum[x] = r[x];
	}else if(sum[x] < l[x]){
		sum[x] = r[x];
		++ cnt;
	}
	sum[fat] += sum[x];
}

void solve(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)g[i].clear(), sum[i] = 0;
	cnt = 0;
	
	for(int i=2;i<=n;i++){
		int x;scanf("%d",&x);
		g[x].pb(i);
	}
	for(int i=1;i<=n;i++)scanf("%d%d",&l[i],&r[i]);
	dfs(1);
	printf("%d\n",cnt);
}

signed main(){
	int te;scanf("%d",&te);
	while(te--)solve();

	return 0;
}

1C
这题好强……
随机走 == 最坏情况下的距离。
设 \(dis[i]\) 表示 \(i\rightarrow n\) 的答案，那么 \(dis[n] = 0\)
先考虑DAG的情况，考虑点 \(x\),将所有 \(x\) 的后继 \(u\) 按照 \(dis[u]\) 升序排好，那么：
\(dis[x]=min{dis[u]+out[x]-id_u}\) 也就是删掉比 \(dis[u]\) 距离还长的点的边，然后走 \(dis[u]\) （因为此时 \(dis[u]\) 成距离最大的了，即最坏情况）
递推即可（每次可以将图边的方向取反，然后正向递推）
那么考虑有环该如何做？
注意上面的递推过程很像 dijkstra 的实现过程，也就是说每次从堆中取出距离最小的点，因为边权为正，此时这个点的 dis 一定就是到 \(n\) 的最短距离（换言之不会被环更新了），我们这里也可以这么做。
实现和 dijkstra 基本相同，只不过边权变成了与第几次更新到这个点（当然得用 \(degree\) 减之）

// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define pii pair<int,int>
#define pb push_back

using namespace std;

typedef long long ll;
typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f, maxn = 2e5+5;

vector<int>g[maxn];
int dis[maxn], de[maxn], vis[maxn];
priority_queue<pii>pq; 

signed main(){
	memset(dis,0x3f,sizeof dis);
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y;scanf("%d%d",&x,&y);
		g[y].pb(x);
		++ de[x];
	}
	
	dis[n] = 0;
	pq.push(mpr(-dis[n], n));
	while(!pq.empty()){
		int x = pq.top().second;pq.pop();
		if(vis[x])continue;vis[x] = 1;
		
		for(int u : g[x]){
			if(dis[x]+de[u] < dis[u]){
				dis[u] = dis[x] + de[u];
				pq.push(mpr(-dis[u], u));
			}
			-- de[u];
		}
	}
	printf("%d\n",dis[1]);

	return 0;
}

1D
这题好强……
设 \(dp[i][0]\) 代表第 \(i\) 个