A - Max Mod Min

Problem Statement

就是每一次选择序列的最大值和序列的最小值, 然后把最大值 最小值的值替换最大值, 如果该值等于 , 那么就把最大值删除.

求需要几次这种操作, 使得给定序列的元素个数为一.

Editorial

算法1

暴力模拟 , 是答案

算法2

分析问题的单调性, 因为最大值在经过一次操作之后一定严格小于其自身的 , 所以每个元素被选作最大值的次数最多为 次, 所以答案为 .

所以, 根据单调性, 可以用一个双端队列来实现操作, 先对序列进行排序, 在进行模拟, 该做法复杂度有保证.

总复杂度为

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
signed main(){
  	fastio();
  	int n;
  	cin>>n;
  	F(i, 0, n) cin>>a[i];
  	sort(a, a + n);
  	deque<int> q;
  	F(i, 0, n) q.push_back(a[i]);
	int ans = 0;
	while(q.size()>1){
		int t = q.front(), e = q.back();
		q.pop_back();
		int tmp = e % t;
		if(tmp != 0) {
			q.push_front(tmp);
		}
		++ ans ;
	}
	cout<<ans<<endl;
	return 0;
}

B - Swap to Sort

Problem Statement

给定一个排列, 有两种操作:

  • 操作 A: 交换 和 .

  • 操作 B: 交换 和 .

求一个操作序列, 使得

  • 操作 A 的个数尽可能少.
  • 最后序列为单调递增
  • 总操作数不超过

Editorial

考虑构造一种操作策略, 使得其满足要求

最小化操作 A 的的个数

首先, 由于交换间隔为或, 可以想到从奇偶性入手.

定义:

  • 如果 和 奇偶性相同, 则称 为好下标, 反之则为坏下标, 序列的坏下标总数记作序列的不和谐度.

操作 A 中, 序列的不和谐值变化 或 .

操作 B 中, 序列的不和谐值不发生变化.

所以操作 A 至少要被使用 初始不和谐值.

使不和谐值为 0

可以发现, 要使操作 A 的个数最少, 必须要在 和 均为坏下标时实施操作, 要达到这点, 需要先使用操作 B 把分散的坏下标聚集起来, 再使用操作 A 进行消除.

排序

由于不和谐值已经为 , 所以只需用操作 B 进行排序即可.

分析总操作数

要使坏下标聚集在一起, 最多要使用 次操作 B

操作 A 最多使用 次

排序最多使用 次操作 B

所以当 时, 操作总和最多是 , 小于 .

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//////////////////// Global Variables ////////////////////

constexpr int N = 500;
int n,m,i,j,a[405];
vector<pair<char,int> > v;

/////////////////////// Functions ////////////////////////

void opt(int x,int l)
{
	swap(a[x],a[x+l]);
	v.push_back(make_pair(l==1?'A':'B',x));
}

////////////////////// Main Execution ////////////////////

signed main(){
  	fastio();
  	cin>>n;
  	Fe(i, 1, n) cin>>a[i];
	Fe(i, 1, n){
		if((i&1)!=(a[i]&1)){
			int j=i+1;
			while((j&1)==(a[j]&1)) j+=2;
			while(j>i+1) opt(j-=2,2);
			opt(i,1);
		}
	}
	Fe(i, 1, n){
		Fe(j, 1, n-2){
			if(a[j]>a[j+2]) opt(j,2);
		}
	}
	cout<<(int)v.size()<<endl;
	fitr(v,it){
		cout<<it->fi<<' '<<it->se<<endl;
	}
	return 0;
}

C - Min Diff Sum

Problem Statement

people, numbered , are going to stand on the number line. Let's denote by the coordinate the Person stands at. Then, should be an integer satisfying . Multiple people can occupy the same coordinate.

We define the dissatisfaction level as the following formula:

Find the minimum possible value of the dissatisfaction level.

Constraints