Codeforces Round 919 (Div. 2) （A-D）_919 div2 b. summation game

比赛链接

---

A. Satisfying Constraints

---

题意：

Alex有n个限制条件，分以下三类：

1. $\ge x$
2. $\le x$
3. $\ne x$

Alex想知道有多少个数k可以满足条件，题目保证答案是有限个的（即至少包括一个限制1和一个限制2）。

输入格式：

第一行一个整数 $t$，表示 $t$ 组数据$(1\le t\le 500)$
每组数据的第一行有一个整数 $n$，表示 $n$ 个限制条件$(2\le n\le 100)$
接下来 $n$ 行每行包括两个正整数 $a$ 和 $x$ ，$a==1$ 时表示限制1，$a==2$ 时表示限制2，$a==3$ 时表示限制3，x的含义在题意中 ( a ∈ { 1 , 2 , 3 } ,   1 ≤ x ≤ 1 0 9 ) (a \in \{1,2,3\}, \, 1 \leq x \leq 10^9) (a∈{1,2,3},1≤x≤109)

输出格式：

每组数据输出一个整数，表示满足条件k的个数。

思路：

如果有多个限制1，那么只有x最大的那个限制1能生效，其他的都是多余的，同理限制2。再把限制1和限制2围出的区间中的限制3去掉，剩下的就是有效的k的个数。
所以用一个变量 $l$ 存储限制1最大的x，同理 $r$ 存储限制2最小的x。把所有限制3都存下来，最后排个序，然后在上面二分查找 $l$ 和 $r$ ，下标之差就是区间 $[l,r]$ 中限制3的个数。
注意 $l$ 可能大于 $r$ ，这时候没有满足条件的k，答案为0。

code：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=105;

int T,n;
int l,r,a[maxn],cnt;

int main(){
	cin>>T;
	while(T--){
		cin>>n;
		cnt=l=0;r=2e9;
		for(int i=1,op,t;i<=n;i++){
			cin>>op>>t;
			if(op==1)l=max(l,t);
			else if(op==2)r=min(r,t);
			else a[++cnt]=t;
		}
		sort(a+1,a+cnt+1);
		int t=r-l+1-(upper_bound(a+1,a+cnt+1,r)-lower_bound(a+1,a+cnt+1,l));
		cout<<max(0,t)<<endl;
	}
	return 0;
}
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

---

B. Summation Game

---

题意：

Alice和Bob玩一个游戏，他们有一个数组 $a_1,a_2,\dots ,a_n$ ，这个游戏有两个步骤：

1. Alice先移除至多k个元素
2. Bob给至多x个元素乘上$-1$

Alice想要让最后的数组元素之和最大，Bob想要元素之和最小，如果两人都发挥最佳状态，问最后元素的和是什么

输入格式

第一行一个整数 $t$，表示 $t$ 组数据$(1\le t\le 10^4)$
每组数据第一行有三个整数 $n,k,x$，表示 $n$ 表示数组a的大小，$k,x$ 含义同题意。$(1\le n\le 2\cdot 10^5)$
接下来一行 $n$ 个整数 $a_1,a_2,\dots ,a_n$$(1\le a_i\le 1000)$，表示数组元素。
保证所有数据 $n$ 的总和不超过$2\cdot 10^5$

输出格式：

每组数据输出一个整数，表示最后元素之和。

思路：

从Bob的视角来看，Alice移除后，要想让数组最后的和最小，一定会给剩余的元素中前x个最大的数乘上-1。那么Alice要删掉一些大数（也就是变成0），防止它变成负的大数，Alice不会删Bob不选的数。

假如数组a排序后是有序的降序排列，数组总和为 $tot$。Bob把一个元素$a_i$$(1\le i\le x)$变为$-a_i$，那么 $tot$ 就损失了$2\ast a_i$（先失去一个$a_i$，又要减去一个$a_i$）。而Alice删掉一个元素$a_i$， $tot$ 只损失了 $a_i$。但是因为Alice删掉了一个Bob选的数，所以Bob会新选择第 $x+1$ 大的元素，Bob造成的损失变成了${\sum }_{k=1}^{x}2\ast a_k+2\ast a_i-2\ast a_{x+1}$。删掉$a_i$后数组剩余元素之和比删掉之前变化了 $a_i-2\ast a_{x+1}$ ，因为选 $i$ 不影响 $x+1$ ，所以我们肯定选最小的 $i$，这时候 $a_i$ 最大。

所以先计算出Bob一开始会造成的损失，然后Alice尝试删掉前 $i$ 个最大的元素，$O(k)$递推Bob造成的损失和Alice造成的损失，可以算出所有可能的情况，因为AIice先手 拥有选择权，取最大值即可。

时间复杂度$O(n\ast logn+x+k)$。

code：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=4e5+5;
typedef long long ll;

int T,n,k,x;
int a[maxn];

int main(){
	cin>>T;
	while(T--){
		cin>>n>>k>>x;
		ll tot=0;
		memset(a,0,sizeof(a));
		for(int i=1;i<=n;i++)
			cin>>a[i],tot+=a[i];
		sort(a+1,a+n+1,greater<int>());
		
		ll maxx,tmp=0,pre=0;
		for(int i=1;i<=x;i++)
			tmp+=-2*a[i];
		maxx=tot+tmp;
		for(int i=1;i<=k;i++){
			pre+=-a[i];
			tmp+=2*a[i]-2*a[i+x];
			maxx=max(maxx,tot+pre+tmp);
		}
		cout<<maxx<<endl;
	}
	return 0;
}
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

---

C. Partitioning the Array

---

题意：

给你一个n和数组a
你可以把数组a分成k个等长的连续子数列（k是n的因数），如下：
$[a_1,a_2,\dots ,a_k],[a_{k+1},a_{k+2},\dots ,a_{2k}],\dots ,[a_{n-k+1},a_{n-k+2},\dots ,a_n]$
如果存在一个数 $m$ $(m\ge 2)$ ，把所有数都模 $m$，使得这 $k$ 个连续子数列完全一致，答案数+1

问总的答案数

输入格式：

每个测试由多个测试用例组成。第一行包含一个整数 $t$ $(1\le t\le 10^4)$ —— 测试用例的数量。测试用例的说明如下

每个测试用例的第一行包含一个整数 $n$ $(1\le n\le 2\cdot 10^5)$ —— 数组的长度

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\dots ,a_n$ $(1\le a_i\le n)$ —— 数组的元素

可以保证n在所有测试用例中不超过$2\cdot 10^5$

输出格式：

每组用例输出一个整数——答案数

思路：

假设分成 $k$ 段，每段长为 $l=n/k$，这个 $k$ 可以 $O(\sqrt{n})$ 暴力枚举。如果一个 $m$ 满足条件，那么$k$ 段每个对应位置上（也就是$a_i,a_{i+l},\dots a_{i+l\ast j}$）模出来的数都一样，即模 $m$ 同余，两两之差是 $m$ 的倍数。

由于这个两数之差为 $m$ 的倍数的性质是传递的（即若 $a_1$ 与 $a_2$ 之差和 $a_2$ 与 $a_3$ 之差为 $m$ 的倍数，那么 $a_1$ 与 $a_3$ 之差也是 $m$ 的倍数），所以 $a_i,a_{i+l},\dots a_{i+l\ast j}$ 里取所有相邻两数的差再求它们的 $gcd$ ，得到的就是满足$a_i,a_{i+l},\dots a_{i+l\ast j}$同余的最大模数（也就是这一个对应位置上可以满足的最大的m）。

把每个对应位置上的最大模数都算出来，然后求它们的 $gcd$，得到的就是最大的 $m$，如果它大于等于2，答案数就+1。

暴力枚举 $k$ 是 $O(\sqrt{n})$ 的，验证 $k$ 符合条件需要枚举每个对应位置一共 $l=n/k$ 个，每个对应位置循环 $k$ 次，一共循环 $n$ 次，算上 $gcd$ 的 $logn$。最坏时间复杂度是$O(n\sqrt{n}logn)$，时限有3秒之多，可以通过。

code：

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=2e5+5;

int T,n,a[maxn];
inline int gcd(int a,int b){//gcd(a,0)=a
	while(b)b^=a^=b^=a%=b;
	return a;
}

bool check(int l){
	int tmp=0;
	for(int i=1;i<=l;i++)
		for(int j=i+l;j<=n;j+=l)
			tmp=gcd(tmp,abs(a[j]-a[j-l]));
			//srds，这里不一定非得是相邻的，因为关系是传递的
			//所以减谁都没关系（当然不能减自己），重要的是可以推出所有关系
	return tmp!=1;
}

int main(){
	cin>>T;
	while(T--){
		cin>>n;
		for(int i=1;i<=n;i++)
			cin>>a[i];
		int cnt=0;
		for(int i=1;i*i<=n;i++){
			if(n%i==0){
				if(check(i))cnt++;
				if(i*i!=n && check(n/i))cnt++;
			}
		}
		cout<<cnt<<endl;
	}
	return 0;
}
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

---

D. Array Repetition

---

题意：

Jayden 有一个数组a，最初是空的。有n个操作，他必须按给定顺序执行两种类型的操作：

1. Jayden 将一个整数x $(1\le x\le n)$ 添加到数组末尾
2. Jayden 将x个数组a的副本添加到数组的末尾，换句话说，数组a变成 $[a,\underset{x}{\underbrace{a,\dots ,a}}]$，保证在此之前，他至少执行过一次第一种操作

Jayden有q次查询。对于每个查询，您需要告诉他a数组的第 k 个元素是什么，数组的元素编号从1开始。

输入格式：

每个测试由多个测试用例组成。第一行包含一个整数 t $(1\le t\le 5000)$ —— 测试用例的数量。测试用例的说明如下：

每个测试用例的第一行包含两个整数n和q $(1\le n,q\le 10^5)$ —— 操作数和查询数。

以下n行描述操作。每行包含两个整数b和x ( b ∈ { 1 , 2 } ) (b \in \{1, 2\}) (b∈{1,2})，其中b表示操作的类型。如果 b=1
则 x $(1\le x\le n)$ 是 Jayden 附加到数组末尾的整数。如果 b=2 则 x $(1\le x\le 10^9)$ 是 Jayden 附加到数组末尾的副本数。

每个测试用例的下一行包含q个整数 $k_1,k_2,\dots ,k_q$ $(1\le k_i\le \min (10^{18},c))$，表示查询，其中c是完成所有操作后数组的大小。

保证在所有测试用例中n的和 与 q的和都不超过$10^5$。

输出格式：

对每组数据的每个询问 $k_i$ ，输出一个整数，表示第 $k_i$ 个元素是什么

思路：

操作1好说，新增了一个什么数直接就是操作数x。操作2把前面复制x遍放在后面，后面的某个位置上数可以算出原来在前面的什么位置上，这个数要么是操作2复制过来的，要么是操作1新增的。如果正好原来的这个位置上的数是操作1新增的，就直接返回这个操作数，如果是操作2复制过来的，就像上面一样继续去算 执行操作2前 原来在什么位置上。

所以给你一个 $k$，我们需要找到它是通过什么操作被新增出来的。很容易想到，如果被第 $i$ 个操作新增出来，那么前 $i-1$ 个操作得到的数列元素个数 $<k$，前 $i$ 个操作得到的数列元素个数 $\ge k$。因此读入操作的时候记录一下第 $i$ 个操作是什么，并计算通过前 $i$ 个操作得到了多少元素，之后查询的时候二分查找一下 $k$ 即可。因为我们还需要知道操作1新增的是什么数，所以再记录一下第 $i$ 个操作的操作数即可。

因为操作2至少要给原数组长度乘2，最多60次就会超出 $10^{18}$，所以一次查询最多找60次，算上二分查找，总的时间复杂度是$O(60\ast q\ast logn+n)$

code：

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const ll inf=1e18;

int T,n,q;
ll a[maxn];//一共几个数 
int opt[maxn],num[maxn];//操作 操作数

ll query(ll x){
	for(int i=lower_bound(a+1,a+n+1,x)-a;i>=1;i=lower_bound(a+1,a+i+1,x)-a){
		if(opt[i]==1)return num[i];
		x=((x-1)%a[i-1])+1;//进行操作2前 原来的位置
	}
}

int main(){
	cin>>T;
	while(T--){
		cin>>n>>q;
		for(int i=1,op,t;i<=n;i++){
			cin>>op>>t;
			if(op==1){
				a[i]=a[i-1]+1;
				num[i]=t;
				opt[i]=1;
			}
			else {
				if((inf+t)/(t+1)<a[i-1])a[i]=inf+1;//除法防爆longlong
				else a[i]=a[i-1]*(t+1);
				num[i]=t+1;//增加t个副本，再加上本身相当于长度乘t+1
				opt[i]=2;
			}
		}
		
		ll t;
		for(int i=1;i<=q;i++){
			cin>>t;
			cout<<query(t)<<endl;
		}
	}
	return 0;
} 
/*
1
10 3
1 1
1 2
1 9
2 111111110
2 6
2 142857142
2 2
1 8
1 7
1 6
333333333333333333 999999999999999999 1000000000000000000

9 9 8
*/
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62