CF 813_div2 总结

A: 有一个permutation p，每次操作可以交换两个位置的值，要多少操作使 p1 - pk 的 和最小

需改进点： 太慢发现性质，过于关注实际操作

如何得出：观察，直觉

正确想法：1 - k 的 排列和 就是最小的

总结： 

        1. 问使数组的某一属性最小大，考虑数组的整体结构

void solve(){
	int n, k; cin>>n>>k;
	int a[n+5];
	for(int i=0;i<n;i++) cin>>a[i];
	int ans=0;
	for(int i=0;i<k;i++){
		if(a[i]>k) ans++;
	}
	cout<<ans<<endl;
}
 
int main(){
	int t; cin>>t;
	while(t--){
		solve();
	}
}

---------------------------------------------------------------------------------------------------------------------------------

B:  构造一个n的排列，使 lcm(1,?1)+lcm(2,?2)+…+lcm(?,??) 最大

需改进点：太慢发现性质

如何想出：写example

正确想法：对于一个数 x，把它分配到一个最大的互质数 的 lcm 最优，于是就有以下结构：

下标：  i, i+1, ....., n-1,  n 

值：     i+1, i, ....., n,  n-1

总结：

        1. 求整体属性，一个个体可以多种选择，从个体切入运用最小化思考

void solve(){
	int n; cin>>n;
	int ans[n+5];
	for(int i=n;i>=0;i-=2){
		ans[i]=(i-1);
		ans[i-1]=(i);	
	}
	if(n%2==1) ans[1]=1;
	for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
	cout<<endl;
}
 
int main(){
	int t; cin>>t;
	while(t--){
		solve();
	}
}

--------------------------------------------------------------------------------------------------------------------------------

C：有一个数组a，每次操作选一个数x，并把所有a里的x变成0，求最少操作数使a升序

需改进点：太慢

如何想出：之前已经想出 aa...a bb...b c..c 的结构，画4 5个example后看出 0 前面所有必须是0。

1.什么时候必须操作？

先求出每个数x的最右边

从后面开始，如果 ai 大于 ai+1 （带表降序了），则必须变0，而ai的最右边的所有左边数都要变0

总结：

        1. 什么时候必须操作？（贪心）

#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
#include <vector>
#include <utility>
using namespace std;
 
void solve(){
	int n; cin>>n;
	int far[n+5];
	int a[n+5];
	for(int i=0;i<n;i++) cin>>a[i], far[a[i]]=i;
	map<int, bool> unique;
	int idx=0, c=0;
	for(int i=n-1;i>=1;i--){
		if(a[i]<a[i-1]){
			idx=i-1, c=1;
			break;
		}
	}
	if(!c){ cout<<0<<endl; return; }
	int f=0;
	for(int i=0;i<=idx;i++) f=max(f, far[a[i]]);
	int ans=0;
	for(int i=0;i<=f;i++){
		if(!unique[a[i]]){
			ans++;
			unique[a[i]]=1;
		}
	}
	cout<<ans<<endl;
}
 
int main(){
	int t; cin>>t;
	while(t--){
		solve();
	}
}

---------------------------------------------------------------------------------------------------------------------------

D:

大脑一片混乱，看不懂题目

----------------------------------------------------------------------------------------------------------------------------

总结：

        1. 需提升大脑精神