Codeforces Round 888 (Div. 3)

D

Prefix Permutation Sums

题意：有一个长度为n的前缀和数组，现在该数组丢了一个元素，问该数组能否匹配一个长度为n的排列。

思路：

求出该数组的差值后，只有两种情况是YES：
①1~n之间恰好有两个数的位置上是空的，并且恰好有一个数多余的数，等于这两个位置加起来，这样就能使得1~n填满。

②1~n之间恰好有一个数的位置上是空的。此时只需将这缺的数放到数组最后面，就能令数组合法。
 

void solve() {
	unordered_map<int,int>mp;
	int n,sum=0,cnt=0,now;
	cin>>n;
	for(int i=1; i
		cin>>a[i];
		mp[a[i]-a[i-1]]++;
	}
	for(int i=1; i<=n; i++) {
		if(!mp[i]) {
			cnt++;
			sum+=i;
		}
	}
	for(auto x:mp) {
		if(x.second>=2||x.first>n) {
			now=x.first;
			break;
		}
	}
	if(now==sum&&cnt==2||cnt==1)yes;
	else no;
}

E

Nastya and Potions

题意：共有n种药水，每种药水的价格为c[i]；药水也可以通过其他几种药水合成，合成使用的药水会被消耗。现在有k种药水无限供应，问获得每种药水的最小花费。
思路：我们通过记忆化搜索（dfs） 的方法来确定他每一种原料的最小花销，这样就能得到通过合成路线相加获得该药剂的最小花销。之后我们将这个价格和市场价格做比对，保留最小值即可，并记得标记已经得到的答案，已便用它来更新答案.

#include 
#define ios ios::sync_with_stdio(0), cin.tie(0)
#define PII pair
#define int long long
typedef long long ll;
const int N = 1e6 + 10;
const int inf = 0x3f3f3f3f;
 
using namespace std;
int c[N];
int st[N];
vector<int> e[N];
int dfs(int u)
{
	if (st[u] != -1)
		return st[u];
	if (e[u].size() == 0)
		return c[u];
	int sum = 0;
	for (auto x : e[u])
	{
		sum += dfs(x);
	}
	return st[u] = min(c[u], sum);
}
void solve()
{
	int n, k;
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
		cin >> c[i], e[i].clear(), st[i] = -1;
	for (int i = 1; i <= k; i++)
	{
		int x;
		cin >> x;
		c[x] = 0;
	}
	for (int i = 1; i <= n; i++)
	{
		int x;
		cin >> x;
		for (int j = 1; j <= x; j++)
		{
			int xx;
			cin >> xx;
			e[i].push_back(xx);
		}
	}
	for (int i = 1; i <= n; i++)
		cout << dfs(i) << " \n"[i == n];
}
signed main()
{
	// freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);
	ios;
	int _t = 1;
	cin >> _t;
	while (_t--)
		solve();
	system("pause");
	return 0;
}

F

Lisa and the Martians

题意：给定n和k，给你n个数，其中每个数a[i]<2^k。从中选取两个数，和一个任意数x(0 <= x < 2^k)。求的最大值。

思路：考虑每一个二进制位，若ai与aj该位都为1，那么我们就让x该位为0；若ai和aj该位都为0，那么我们就让x该位为1.只有二进位上相同时，我们才能得到该位的贡献。所以我们让ai和aj同或后最大，也就是ai和aj异或后最小。
结论，n个数的最小异或对答案就是排序后最小的相邻异或。
 

#include 
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;
 
using namespace std;
int n,k;
int a[N];
void solve()
{
	vectorv;
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		v.push_back({a[i],i});
	}
	sort(v.begin(),v.end());
	int mi=2e9,ansi=-1,ansj=-1;
	for(int i=1;i
	{
		int t=(v[i].first^v[i-1].first);
		if(t
		{
			mi=t;
			ansi=v[i].second;
			ansj=v[i-1].second;
		}
	}
	cout<' '<' '<<((1<-1)-a[ansi]<<'\n';
}
signed main()
{
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	ios;
	int _t=1;
	cin>>_t;
	while(_t--) solve();
	system("pause");
	return 0;
}

G

Vlad and the Mountains

题意：有n座山，告诉你每座山的高度h[i]。从山i到山j的力量花费为h[j]-h[i]。有q次询问，每次询问初始力量为e能否从a到b山。
思路：从a到b到c的能量花费为hb-ha+hc-hb=hc-ha，hc-ha<=e才行，即我们能从顶点a出发，可以到达任何一个顶点，且路径不经过高度大于ha+e的顶点。
我们可以将边(a,b)的边权看作max(ha,hb).因为hahb时，max(ha,hb)<=ha+e.

询问(a,b,u)等价于只用边权<=ha+e的边 能否 联通a b节点。离线, 将询问按 (ℎa+e) 值非降序排列,将边也是按max(hu , hv)非递减排序，这样就转化为了并查集可以维护的加边操做，对于每个询问，我们依次按排序后的边加入，这样就不要每询问一次就从头遍历一次边了，我们加入的边的max(hu, hv)一定是满足后面的要求的，所以对于后面的边如果可以加边就加边，不行的话就判断当前是否联通了
 

#include 
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;
 
using namespace std;
int n,m;
int fa[N];
int h[N];
struct Edge{
	int u,v,w;
};
struct Query{
	int a,b,e;
	int num;
	bool ok;
};
bool cmp(Edge a,Edge b)
{
	return a.w
}
bool cmp1(Query x,Query y)
{
	return x.e+h[x.a]
}
bool cmp2(Query x,Query y)
{
	return x.num
}
int getfa(int x)
{
	return fa[x]==x? x:fa[x]=getfa(fa[x]);
}
void solve()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=n;i++) cin>>h[i];
	vectoredge;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v;
		w=max(h[u],h[v]);
		edge.push_back({u,v,w});
	}
	int q;
	cin>>q;
	vectorquery;
	for(int i=1;i<=q;i++)
	{
		int a,b,e;
		cin>>a>>b>>e;
		query.push_back({a,b,e,i,0});
	}
	sort(edge.begin(),edge.end(),cmp);
	sort(query.begin(),query.end(),cmp1);
	int p=0;
	for(int i=0;i
	{
		int a=query[i].a,b=query[i].b,e=query[i].e;
		while(p
		{
			int u=edge[p].u,v=edge[p].v,w=edge[p].w;
			if(getfa(u)!=getfa(v))
			{
				fa[getfa(u)]=getfa(v);
			}
			p++;
		}
		if(getfa(a)==getfa(b))
		{
			query[i].ok=1;
		}
	}
	sort(query.begin(),query.end(),cmp2);
	for(int i=0;i
		if(query[i].ok) cout<<"YES\n";
		else cout<<"NO\n";
}
signed main()
{
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	ios;
	int _t=1;
	cin>>_t;
	while(_t--) solve();
	system("pause");
	return 0;
}