Codeforces Round #642 (Div. 3)(A-E题解)

这场虽然只写了4题但是打的还是比较舒服的，除了T2粗心WA一发，其他都是一次AC还是比较舒服，开局也不错，20分钟切了两题。


题目大意：
要你构造一个长度为 $n$n的数组，使得它们的和等于 $m$m，并且要你最大化 $\sum _{i=0}^{i=n-1}\mid a\left[i\right]-a[i+1]\mid$i=0∑i=n−1​∣a[i]−a[i+1]∣
思路：很显然的一个题。分类讨论一下。
$n=1$n=1:直接输出0即可。
$n=2$n=2：输出 $m$m即可。
$n>=3$n>=3： $\mathrm{00..000}m\mathrm{000...00}$00..000m000...00这样构造即可，输出 $2m$2m.
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 10;
typedef long long int ll;
void solved(){
	int t;cin>>t;
	while(t--){
		ll n,m;cin>>n>>m;
		if(n == 1){
			cout<<"0"<<endl;continue;
		}
		if(n == 2){
			cout<<m<<endl;continue;
		}
		if(n >= 3){
			cout<<m * 2<<endl;
		}
	}
}
int main(){
	solved();
	return 0;
} 

题目大意：
给你两个长度为 $n$n的序列 $a,b$a,b。现在你可以在 $a,b$a,b之间最多交换 $k$k次，要你使得最后序列 $a$a的和最大。
思路：很显然的贪心，对 $a$a升序，对 $b$b降序，在满足 cnt<=k并且 $ai>bi$ai>bi就交换。
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 10;
typedef long long int ll;
int a[maxn],b[maxn];
bool cmp(int a,int b){
	return a > b;
}
void solved(){
	int t;cin>>t;
	while(t--){
		int n,k;cin>>n>>k;
		for(int i = 1; i <= n; i++)cin>>a[i];
		for(int i = 1; i <= n; i++)cin>>b[i];
		sort(b + 1,b + 1 + n,cmp);
		sort(a + 1,a + 1 + n);
		int ans = 0;
		int pos = 1,cnt = 0;
		for(int i = 1; i <= n; i++){
			if(cnt < k&& b[pos] > a[i]){
				ans += b[pos++];cnt++;continue;
			}
			ans += a[i];
		}
		cout<<ans<<endl;
	}
}
int main(){
	solved();
	return 0;
} 

题目大意：
给你一个 $n\ast n$n∗n的矩阵( $n$n是奇数),矩阵里面每个位置都填有一个数，每个数可以向上下左右对角线 $8$8个方向移动，现在问你，要使得所有有都在一个格子里最少要移动多少步？
思路：
也是很显然的一个题，全部往中间移动就行了。然后找一下关系，不难发现，中心点的第一个外层格子的数量为 $8$8，第二层为 $16$16，第三层为 $24$24,第 $i$i层为 $8\ast i$8∗i.每层要移动到中心点需要移动 $i$i步，所以最终答案的形式是 $1\ast 8+2\ast 16+3\ast 24+。。。。$1∗8+2∗16+3∗24+。。。。所以这题就出了。
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 10;
typedef long long int ll;
void solved(){
	int t;cin>>t;
	while(t--){
		int n;cin>>n;
		ll ans = 0;
		ll cnt = 8;
		for(int i = 1; i <= 2 + (n - 5) / 2; i++){
			ans += i * cnt;
			cnt += 8;
		}
		cout<<ans<<endl;
	}
}
int main(){
	solved();
	return 0;
} 

前3题好像都挺水的，真正拉分的是后3题，然后我就会D。。。。唉。。。太菜了。

题目大意：
一开始给你一个全为 $0$0长度为 $n$n的序列，你每次选择一个子区间，子区间满足全 $0$0，并且长度最长，如果长度相同优先选择最左边的，问你经过 $n$n次操作，最终序列是什么？
思路：
一开始想歪了。。。想着构造了。。。后面发现好像构造不了，因为每次考虑全 $0$0长度最长并且最左边，可以考虑用优先队列来维护，维护两个点，第一点是长度，第二点是最左边。然后模拟一下大概就出来了。
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 10;
typedef long long int ll;
int a[maxn];
struct node{
	int l,r;
	node(){}
	node(int a,int b):l(a),r(b){}
	bool operator <  (const node &rhs)const{
		if((r - l) == (rhs.r - rhs.l))
		return l > rhs.l;
		return (r - l) < (rhs.r - rhs.l); 
	}
};
void solved(){
	int t;cin>>t;
	while(t--){
		int n;cin>>n;
		for(int i = 1; i <= n;i++)a[i] = 0;
		priority_queue<node>st;
		st.push(node(1,n));
		int tot = 1; 
		while(!st.empty()){
			node cur = st.top();st.pop();		
			int mid = cur.r + cur.l >> 1;
			a[mid] = tot++;
			int l = cur.l,r = cur.r;
			if(!a[l + (mid - 1) >> 1])
			st.push(node(l,mid - 1));
			if(!a[mid + 1 + r >> 1])
			st.push(node(mid + 1,r)); 
		} 
		for(int i = 1; i <= n; i++){
			if(!a[i])a[i] = tot++;
		}
		for(int i = 1; i <= n; i++)cout<<a[i]<<" ";
		cout<<endl;
	}
}
int main(){
	solved();
	return 0;
}