SEERC2022(E,F,H,K)

正题

比赛链接:https://codeforces.com/gym/104114

---

E-Exercise【dp,贪心】

题目大意

给出长度为 $2n$ 的序列 $c_i$，将 $1\sim 2n$ 两两配对使得每一对 $(a_i,b_i)$ 的 $|c_{b_i}-c_{a_i}|$ 总和最小且对于任意 $i$ 不存在 $2i-1$ 与 $2i$ 配对的情况。

$1\le n\le 10^5$

解题思路

不考虑限制那么显然就是把 $c_i$ 排序然后相邻的配对，如果有的配对不符合限制我们就需要置换一下，找到相邻的一个进行如下配对。
$$A_1-A_2=B_2-B_1$$

也就是在两组相邻配对之间的 $c_i-c_{i-1}$ 会产生两次贡献。

因为这样原本的配对是不合法的，所以新的配对肯定是合法的，然后这种隔空配对是可以几个连一起互换的，贡献相同。

所以设 $f_{i,0/1}$ 表示到 $i$ ，是否有往后拉的线。

时间复杂度：$O(n\log n)$

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#define ll long long
using namespace std;
const ll N=2e5+10;
ll n,c[N],p[N],f[N][2];
ll read(){
	ll x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-f;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
void print(ll x)
{if(x>9)print(x/10);putchar(x%10+'0');return;}
bool cmp(ll x,ll y)
{return c[x]<c[y];}
ll cut(ll x)
{return 2*(c[p[x*2]]-c[p[x*2-1]]);}
signed main()
{
	n=read();
	for(ll i=2;i<2*n+2;i++)c[i]=read(),p[i]=i;
	sort(p+2,p+2*n+2,cmp);
	//0 �� 
	//1 �������
	ll sum=0;
	for(ll i=1;i<=n;i++)sum+=c[p[i*2+1]]-c[p[i*2]];
	f[0][1]=1e18;
	for(ll i=1;i<=n;i++){
		if((p[i*2]^1)==p[i*2+1]){
			f[i][0]=f[i-1][1]+cut(i);
			f[i][1]=min(f[i-1][0],f[i-1][1]+cut(i));
		}
		else{
			f[i][0]=min(f[i-1][0],f[i-1][1]+cut(i));
			f[i][1]=min(f[i-1][0],f[i-1][1]+cut(i));
		}
	}
	print(sum+f[n][0]);putchar('\n');
	return 0;
}

---

F-Fortune over Sportsmanship

题目大意

懒得转译了
https://codeforces.com/gym/104114/problem/F

解题思路

最小生成树，很神奇吧

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
using namespace std;
const int N=1050;
struct node{
	int x,y,w;
}a[N*N],p[N];
int n,tot,fa[N],ans;
int read(){
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-f;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
void print(int x)
{if(x>9)print(x/10);putchar(x%10+'0');return;}
int find(int x)
{return (x==fa[x])?x:(fa[x]=find(fa[x]));}
bool cmp(node x,node y)
{return x.w>y.w;}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			int w=read();
			if(i<j)a[++tot]=(node){i,j,w};
		}
	sort(a+1,a+1+tot,cmp);int m=0;
	for(int i=1;i<=tot;i++)
		if(find(a[i].x)!=find(a[i].y)){
			if(find(a[i].x)>find(a[i].y))swap(a[i].x,a[i].y);
			ans+=a[i].w;
			p[++m]=(node){find(a[i].x),find(a[i].y)};
			fa[find(a[i].y)]=find(a[i].x);
			if(m==n-1)break;
		}
	print(ans);putchar('\n');
	for(int i=1;i<=m;i++)
		print(p[i].x),putchar(' '),
		print(p[i].y),putchar('\n');
	return 0;
}

---

H-Hanoi【构造】

题目大意

汉诺塔，但是第一个塔不需要按照从大到小的顺序。

然后给出初始时第一个塔上盘的顺序，要求构造一种在最终第三个塔排好序的方案，次数不超过 $2\times n^2$ 。

$1\le n\le 500$

解题思路

考虑一种类似插入排序的方法，我们每次把塔顶前面按顺序的全丢到第三个塔，然后把第一个塔剩下的第一个丢到第二个塔，然后再把第三个塔的一个一个丢回第一个塔，第二个塔上的在合适的顺序插入这个过程。

这样每次不超过 $2n$ 可以进行一次插入排序，次数够用

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<vector>
#define mp(x,y) make_pair(x,y)
using namespace std;
const int N=510;
int n,a[N];
vector<pair<int,int> >e;
int read(){
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-f;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
void print(int x)
{if(x>9)print(x/10);putchar(x%10+'0');return;}
void write(){
	print(e.size());putchar('\n');
	for(int i=0;i<e.size();i++)
		print(e[i].first),putchar(' '),print(e[i].second),putchar('\n');
	return;
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)a[i]=read();
	for(int t=1;t<=n;t++){
		int c=0;
		for(int i=n;i>=1;i--){
			if(i==1){e.push_back(mp(1,3));write();return 0;}
			if(a[i]>a[i-1])e.push_back(mp(1,3));
			else {c=i;break;}
		}
		e.push_back(mp(1,3));
		e.push_back(mp(1,2));bool flag=0;
		for(int i=c;i<=n;i++){
			if(a[i]>a[c-1]&&!flag)
				e.push_back(mp(2,1)),flag=1;
			e.push_back(mp(3,1));
		}
		if(!flag)
			e.push_back(mp(2,1));
		sort(a+c-1,a+1+n);
	}
	return 0;
}

---

N-Nusret Gökçe

题目大意

一个长度为 $n$ 的序列，你可以给数字加 $1$ ，要求操作次数最少使得相邻的数字相差不超过 $m$ 。

$1\le n\le 10^5,0\le m\le 10^9$

解题思路

直接按照最低限度加，一个地方加了之后可能会更新周围的，用一个优先队列存一下就好了。

时间复杂度：$O(n\log n)$

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cctype>
#define ll long long
#define mp(x,y) make_pair(x,y)
using namespace std;
const ll N=1e5+10;
ll n,m,a[N];
priority_queue<pair<ll,ll> > q;
ll read(){
	ll x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-f;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
void print(ll x)
{if(x>9)print(x/10);putchar(x%10+'0');return;}
//bool cmp(ll x,ll y)
//{return (a[x]==a[y])?(a[x]>a[y]):(x<y);}
signed main()
{
	n=read();m=read();
	for(ll i=1;i<=n;i++)a[i]=read(),q.push(mp(a[i],i));
	while(!q.empty()){
		ll x=q.top().second;
		if(q.top().first!=a[x]){q.pop();continue;}
		q.pop();
		a[0]=a[n+1]=a[x];
		ll w=max(a[x-1]-m,a[x+1]-m);
		if(w>a[x]){
			a[x]=w;
			if(x>1)q.push(mp(a[x-1],x-1));
			if(x<n)q.push(mp(a[x+1],x+1));
		}
	}
	for(ll i=1;i<=n;i++)print(a[i]),putchar((i==n)?'\n':' ');
	return 0;
}