Codeforces Round 969 (Div. 2) A-C

Codeforces Round 969 (Div. 2) A-D

A：Dora’s Set

题目描述：
给定连续的序列，求在这连续的序列中，无限次找到三个互质的数并删除，求删除最多的策略。
解题思路：
该题其实很简单，主要是要想到连续的三个数，并且第一个数为奇数，那么这三个数就为互质的，就比如：3 4 5 ，167 168 169，这三个数就为互质的。那么就只需要考虑奇偶性就行了。
解题代码：

void solve() {int n,m;cin >> n >> m;if(m - n + 1 == 3 && n % 2 != 0) cout << 1 << endl;else {int ans = 0;int len = m - n + 1;if(n % 2 == 1){cout << (len) / 4 +(len % 4 == 3) << endl;}else {len --;cout << (len) / 4 +(len % 4 == 3) << endl;}}
}

B：Index and Maximum Value

题目描述：
给定一个n个元素的序列，然后进行m次操作，每次操作选择元素中的值在(l, r) 区间进行加一或者减一的操作。然后找到这个序列中的最大值。
解题思路：
对于该题，只需要考虑最大的那个值的变换就行了，因为如果变大或变小，都会将最大的那个值进行变大变小。
解题代码：

const int N = 1e6+5;
int arr[N];void solve() {int n,m;cin >> n >> m;int maxx = 0;for(int i = 1; i<= n; i++){cin >> arr[i];maxx = max(maxx, arr[i]);}while(m--){int a,b;char ch;cin >> ch >> a >> b;if(b >= maxx && a <= maxx){if(ch == '+') maxx ++;else maxx --;}cout << maxx << " ";}cout << endl;
}

C：Dora and C++

题目描述：
给定一个n个元素的序列和a,b。在n个元素的序列中任意多次选择任意一个值进行+a或者-b的操作，最后让这个序列中的最大值减最小值最小。
解题思路：
该题用到裴蜀定理，定义：

若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。

对于该题我们可以用gcd(a,b)将数列中的任意一个数降到[0, gcd(a,b))之间。
下面就进行最小化极差，对于每一个数，最小的是a[i]，最大的值就是a[i-1] + gcd(a,b)。那么只需要计算最大值和最小值之间的差就是要求的最小化极差。
解题代码：

const int N = 1e6+5;
int arr[N];void solve() {int n,a,b;memset(arr,0,sizeof arr);cin >> n >> a >> b;int len = __gcd(a,b);for(int i = 1; i<= n; i++){cin >> arr[i];arr[i] %= len;}sort(arr+1,arr+1+n);int ans = arr[n] - arr[1];for(int i = 2; i <= n; i++){ans = min(ans, arr[i-1] + len - arr[i]);}cout << ans << endl;
}