Codeforces Round 965 (Div. 2) （题解A~D）_codeforce round 965 题解

A. Find K Distinct Points with Fixed Center

意思抽象出来就是已知n个数平均数为x,求出这n个数字

那么举个例子:假设n=3,就取x-1,x,x+1假设n=4就取x-2,x-1,x+1,x+2即可

void solve()
{
	int a,b;
	cin>>a>>b>>m;
	int nowa=a-m/2,nowb=b-m/2;
	for(int i=nowa,j=nowb;i<=a+m/2;i++,j++)
	{
		if(i==a&&m%2==0)continue;
		else cout<<i<<" "<<j<<"\n";
	}
	cout<<endl;
	return ;
}

B. Minimize Equal Sum Subarrays

给定一个排列p,你需要构造一个排列q,使得

使 pi+…+pj=qi+…+qj 的成对数 ( i,j ) (1≤i≤j≤n) 最小。

思路:把p最后一个移到第一个就行

证明:最后一个移到第一个相当于循环移位 可以保证每个区间(<n)都有且仅有一个不同的数字

#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
const int N=1e6+10,INF=4e18;
int n,m;
int q[N];
void solve()
{
	cin>>n;
	_rep(i,1,n)cin>>q[i];
	cout<<q[n]<<" ";
	_rep(i,1,n-1)cout<<q[i]<<" ";
	cout<<'\n';
	return ;
}

C. Perform Operations to Maximize Score

给定n,m。m为操作次数,每次操作可以使b为1的位置的a自增1
给定一个长度为n的数组a和b,a代表初始值,b(1,0)代表是否可操作

问怎么操作可以使a[i]+(a[i]删除之后的数组中位数) (i=[1,n])最大
从简单到复杂想一下,假设没有操作次数,那么怎么取到最大值?
首先把数组排序
例:
奇数1 2 3 4 5 6 7
偶数1 2 3 4 5 6
可以发现取奇数后四个和偶数后三个-->取i>=(n+2)/2的时候答案为a[i]+a[n/2]显然答案最大值取到n也就是①a[n]+a[n/2]
否则取i<(n+2)/2的时候答案为a[i]+a[(n+2)/2]显然答案最大值取到n/2也就是②a[n/2]+a[(n+1)/2],显然比①小不用考虑
所以最大值就是a[n]+a[n/2]

现在考虑有操作次数的情况,那么显然就是要使得操作完之后的a[n]+a[n/2]最大
两种情况 最大化中位数,最大化最大值

最大化最大值
假设最大值可以操作,那么肯定把每一次的操作都给最大值,这样每次操作都可以使得答案的贡献++
假设最大值不可以操作,那么把可操作的小的数字操作几次变成最大值,然后之后每次操作都可以使得答案的贡献++,这样是可能得到最大值的但是不一定能得到最大值,
因为"把可操作的小的数字操作几次变成最大值"是有可能浪费次数的，就比如样例:
4 4
4 4 4 7
1 1 1 0
把数组操作成4 8 4 7显然不如操作成6 6 4 7

最大化中位数
现在最大值不能操作,我要最大化中位数,那么用一个简单的二分就可以解决问题,那就是二分一个答案mid,然后从大到小枚举,不够且b[i]=1的就尝试用m次操作补上
最后满足条件的为cnt,只需要满足cnt>=(n+1)/2就返回true即可

#include <map>
#include <queue>
#include <deque>
#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define pp pop_back()
#define int long long
#define laile cout<<"laile"<<endl
#define lowbit(x) ((x)&(-x))
#define double long double
#define sf(x) scanf("%lld",&x)
#define sff(x,y) scanf("%lld %lld",&x,&y)
#define sd(x) scanf("%Lf",&x)
#define sdd(x,y) scanf("%Lf %Lf",&x,&y)
#define _for(i,n) for(int i=0;i<(n);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define all(x) (x).begin(), (x).end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef unsigned long long ULL;
typedef pair<int,int>PII;
const int N=1e6+10,INF=4e18;
int n,k;
struct aa
{
	int a,b;
}q[N];
bool cmp(aa a,aa b)
{
	return a.a<b.a;
}
bool check(int x)
{
	int nowk=k,cnt=0;
	for(int i=n-1;i>=1;i--)
	{
		if(q[i].a>=x){cnt++;continue;}
		else if(q[i].b)
		{
			if(nowk+q[i].a>=x)
			{
				cnt++;
				nowk-=x-q[i].a;
			}
		}
	}
	return cnt>=(n+1)/2;
}
void solve()
{
	cin>>n>>k;
	_rep(i,1,n)cin>>q[i].a;
	_rep(i,1,n)cin>>q[i].b;
	sort(q+1,q+1+n,cmp);
	int res=0;
	for(int i=n;i>=1;i--)
	if(q[i].b)
	{
		if(i>=(n+2)/2)res=max(res,q[i].a+k+q[n/2].a);
		else res=max(res,q[i].a+k+q[(n+2)/2].a);
		break;
	}
//	laile;
	int now=q[n].a;
	if(q[n].b)
	{
		cout<<now+k+q[n/2].a<<'\n';
		return;
	}
	int l=-1,r=now+1;
	while(l+1<r)
	{
		int mid=l+r>>1;
		check(mid)?l=mid:r=mid;
	}
	cout<<max(res,now+l)<<'\n';
	return ;
}
signed main()
{
	IOS;
	int T=1;
	cin>>T;
	while(T--)
		solve();
	return 0;
}

D. Determine Winning Islands in Race

岛屿1~n,默认i->i+1有桥,A牛独享额外m个桥(连边均为编号小指大),桥为单向边
比赛中,走过的地方,离开就会坍塌,谁先到达n谁胜利
主角B牛从1~n-1分别出发,A只能从1开始走,B先走,然后轮流走,判断它是否胜利

1:如果没有额外m桥,显然B必胜
2:如果有额外m桥,理论上,①只要B没有把A的某个额外桥的起点坍塌,②并且A能先一步比B到那个额外桥的终点,B是必输的
假设B从9号点出发,显然可以预处理出A到1~8号点的最短路,所以先预处理出A到1~n的最短路
然后就是一个神仙思路:把所有的额外边建一条回边,然后从大到小枚举每个点,如果有以这个点为起点的回边就把i(回边起点)-dist[j(回边终点)]-1加进答案的multiset里面,解释在后面
这样做有什么好处呢？
回到B输的那个条件里面去假设起点为S,额外桥的终点为v,额外桥的起点为j,假设dist[j]为此时A到j的最短路(此时满足前面的①条件所以显然可以直接用dist[j])
那么B输是因为v-s>dist[j]+1(A比B先一步到i点)===>s<v-dist[j]-1
那么如果要B胜,是不是就要满足任意的①(前面写的①)的条件下,都有s>=v-dist[j]-1
于是本题得解

最后捋一下代码怎么写:
首先从后往前遍历每个点作为B的起点,如果i此时有回边就把此时i-dist[j]-1(此时i就是v)加入答案的multiset里面,最后只需要访问（*prev(MultisetId.end())）就是最大值
但是在i递减的过程中,B可能把A的额外桥的起点坍塌(此时i在A的额外桥起点的前面)
处理方法就是当i遍历到某个额外桥起点(j)的时候把此时对应的(v-dist[j]-1)删了,怎么删显然在建立回边时候可以把回边终点j和v-dist[j]-1记录下来然后遍历到j这个点的时候把v-dist[j]+1删掉就行了
最后每个点判断是否比multiset里面最大值要大也就是i(等价于起点S)>=*prev(MultisetId.end()),如果判断成立从这个点出发必胜

#include <map>
#include <set>
#include <queue>
#include <deque>
#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define pp pop_back()
#define int long long
#define laile cout<<"laile"<<endl
#define lowbit(x) ((x)&(-x))
#define double long double
#define sf(x) scanf("%lld",&x)
#define sff(x,y) scanf("%lld %lld",&x,&y)
#define sd(x) scanf("%Lf",&x)
#define sdd(x,y) scanf("%Lf %Lf",&x,&y)
#define _for(i,n) for(int i=0;i<(n);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define _pre(i,a,b) for(int i=(a);i>=(b);--i)
#define all(x) (x).begin(), (x).end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef unsigned long long ULL;
typedef pair<int,int>PII;
const int N=1e6+10,INF=4e18;
int n,m;
int dist[N];
vector<vector<int>> v(N), fv(N);
void bfs(vector<vector<int>>&v)
{
	memset(dist,-1,8*(n+1));
	dist[1]=0;
	queue<int>q;
	q.push(1);
	while(q.size())
	{
		int u=q.front();
		q.pop();
		for(auto &i:v[u])
			if(!~dist[i])
				dist[i]=dist[u]+1,q.push(i);
	}
	return ;
}
void solve()
{
	cin>>n>>m;
	vector<vector<int>>(n+1).swap(v);
	vector<vector<int>>(n+1).swap(fv);
//	for(auto &i:v)i.clear();//不用,很慢
//	for(auto &i:fv)i.clear();
//	v.clear(),fv.clear();二维向量不能直接clear
//	vector<vector<int>> v(n+1), fv(n+1);
	while(m--)
	{
		int a,b;
		cin>>a>>b;
		v[a].pb(b);
		fv[b].pb(a);
	}
	_rep(i,1,n-1)
		v[i].pb(i+1);
	bfs(v);
	multiset<int>good;
	vector<vector<int>>shan(n+1);
	string res=string(n-1,'0');
	for(int i=n;i>=1;i--)
	{
		for(auto& j:fv[i])
		{
			int now=i-dist[j]-1;
			good.insert(now);
			shan[j].push_back(now);
		}
		for(auto& j:shan[i])
			good.erase(good.find(j));
		if(i!=n)
		{
			int ma=good.empty()?-1:*prev(good.end());
			if(i>=ma)res[i-1]='1';
		}
	}
	cout<<res<<'\n';
	return ;
}
signed main()
{
	IOS;
	int T=1;
	cin>>T;
	while(T--)
		solve();
	return 0;
}