[补题篇] Codeforce 1417D (思维题)

116 阅读 0 评论 77 点赞

我是靠谱客的博主魁梧草丛，这篇文章主要介绍[补题篇] Codeforce 1417D (思维题)，现在分享给大家，希望可以做个参考。

题目链接：传送门~~

题目大意
给出一个长度为 n 的序列 a，你可以最多进行 3 * n 次操作，操作为：
使 a[i] = a[i] - x * i, a[j] = a[j] + x * i, 1 <= i , j <= n , 0 <= x <= 1e9

操作完以后，使得序列 a 中的全部元素相同。
如果可以实现，给出操作次数和每次操作的 i 、j 和 x，如果不能实现，就输出 -1 .

思路
我们观察操作可以发现，每次操作的增加量和减少量是相同的，也就是说序列 a 的和不能被 n 整除，那么就无法通过操作使得序列a 里的元素全部相等。
如果可以整除时，我们先进行一轮操作，把所有的数都给加到 a[1] 上，然后再进行一轮操作，把 a[1] 均分到后边的 n-1 个数。
这里有一个问题，在第一轮操作时，我们给 a[i] - x * i, 如果 a[i] 不能整除 i 的话，我们就不能一次把 a[i] 减为 0. 在这里我们就要先进行一波操作，使得 a[i] 成为 i 的整数倍。
具体做法，我们定义 z = i - (a[i] % i), 我们进行一次操作：a[1] = a[1] - z * 1, a[i] = a[i] + z * 1，这时的 a[i] 就成了 i 的整数倍。
到这里，我们就可以AC了。具体细节看代码 ~~~

代码

复制代码

#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <stack>
#define ll long long
#define chushi(a, b) memset(a, b, sizeof(a))
const double eps = 1e-8;
const ll INF = 1e9;
const ll mod = 998244353;
const int maxn = 1e4+10;
using namespace std;
typedef struct Node{
int x;
int y;
int z;
Node(int xx, int yy, int zz){
x = xx; y = yy; z = zz;
}
} node;
int a[maxn];
queue<node> qu;	// 用来存操作步骤
void go(int x, int y, int z){ // 进行操作
a[x] -= x * z;
a[y] += x * z;
qu.push(node(x, y, z)); // 加入到队列里边
}
int main(){
ios::sync_with_stdio(false);
int ncase;
cin >> ncase;
while(ncase--){
int n;
cin >> n;
int sum = 0;
for(int i = 1; i <= n; i++){
cin >> a[i];
sum += a[i];	// 统计序列和
}
if(sum % n){
// 不能被整除 -1 ，结束这轮
cout << -1 << endl;
continue;
}
for(int i = 2; i <= n; i++){
if(a[i] % i){	// 如果 a[i] 可以被 i 整除，就先进行一波操作
go(1, i, i - a[i] % i);
}
go(i, 1, a[i] / i);	// 把 a[i] 整到 a[1] 上
}
for(int i = 2; i <= n; i++) go(1, i, sum / n); // 把 a[1] 分到后边的序列
int num = qu.size();	// 计算操作数
cout << num << endl;	// 输出
while(num--){
node b = qu.front(); qu.pop();
cout << b.x << " " << b.y << " " << b.z << 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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <stack>
#define ll long long
#define chushi(a, b) memset(a, b, sizeof(a))
const double eps = 1e-8;
const ll INF = 1e9;
const ll mod = 998244353;
const int maxn = 1e4+10;
using namespace std;
typedef struct Node{
int x;
int y;
int z;
Node(int xx, int yy, int zz){
x = xx; y = yy; z = zz;
}
} node;
int a[maxn];
queue<node> qu;	// 用来存操作步骤
void go(int x, int y, int z){ // 进行操作
a[x] -= x * z;
a[y] += x * z;
qu.push(node(x, y, z)); // 加入到队列里边
}
int main(){
ios::sync_with_stdio(false);
int ncase;
cin >> ncase;
while(ncase--){
int n;
cin >> n;
int sum = 0;
for(int i = 1; i <= n; i++){
cin >> a[i];
sum += a[i];	// 统计序列和
}
if(sum % n){
// 不能被整除 -1 ，结束这轮
cout << -1 << endl;
continue;
}
for(int i = 2; i <= n; i++){
if(a[i] % i){	// 如果 a[i] 可以被 i 整除，就先进行一波操作
go(1, i, i - a[i] % i);
}
go(i, 1, a[i] / i);	// 把 a[i] 整到 a[1] 上
}
for(int i = 2; i <= n; i++) go(1, i, sum / n); // 把 a[1] 分到后边的序列
int num = qu.size();	// 计算操作数
cout << num << endl;	// 输出
while(num--){
node b = qu.front(); qu.pop();
cout << b.x << " " << b.y << " " << b.z << endl;
}
}
return 0;
}