目录
- A. Hard Way
- B. Power Walking
- C. Great Sequence
- D. Repetitions Decoding
A. Hard Way
题意：
给定一个三角形，若从y = 0上任意一点，无法通过线段到达三角形边上（线段不能通过三角形内部），计算这种边的总长度。
题解：
当且仅当，三角形上面的边是平行于x轴的情况下，存在答案。这条边的长度即为答案。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13void slove() { int T; cin>>T; while(T--) { ll x1, y1, x2, y2, x3, y3; cin>>x1>>y1>>x2>>y2>>x3>>y3; if(y1 == y2 && y3 < y2) cout<<abs(x2-x1)<<endl; else if(y1 == y3 && y2 < y1) cout<<abs(x1-x3)<<endl; else if(y2 == y3 && y1 < y3) cout<<abs(x2-x3)<<endl; else cout<<0<<endl; } }
B. Power Walking
题意： 给定一个数组。将该数组分为 k组（1 <= k <= n），每组的价值为不同数字的个数。计算每个 k对应的所有组的总价值的最小值。
题解：
每次分组都先把独立存在的数分出去。记原数组中不同数字的个数为cnt。当 k <= cnt时，答案为 cnt； 当 k > cnt 时，答案为 cnt++。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23void slove() { int T; cin>>T; while(T--) { int n; cin>>n; map<int, int> mp; mp.clear(); int cnt = 0; for(int i = 0; i < n; i++) { int x; cin>>x; if(!mp[x]) cnt++, mp[x] = 1; } for(int i = 1; i <= n; i++) { if(i <= cnt) cout<<cnt<<" "; else cnt++, cout<<cnt<<" "; } cout<<endl; } }
C. Great Sequence
题意： 给定一个数组和一个 x。当一个数组中一半的数乘以x后对应的数，是该数组的另一半数时称为 great sequence。你可以在原数组中一次插入任意一个数，问最少需要插入几次能使得原数组成为great sequence。
题解：
统计原数组中的数，且其倍数为 x的数也在数组中的个数。剩下的个数就是最终答案。（好绕…）。记得开 ll
代码：
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
66
67
68
69#include<bits/stdc++.h> using namespace std; typedef long long ll; #define endl "n" #define IOS ios::sync_with_stdio(false); cin.tie(0) #define inf 0x3f3f3f3f #define pii pair<int, int> #define pll pair<ll, ll> #define pdd pair<double, double> #define debug(a) cout<<"tdebug:"<<a<<endl const double PI = acos(-1.0); const int mod = 998244353; const int eps = 1e-8; const int N = 10 + 2e5; void slove(); template<typename T>void read(T &x) { x = 0;char ch = getchar();ll f = 1; while(!isdigit(ch)){if(ch == '-') f *= -1; ch = getchar();} while(isdigit(ch)){x = x*10+ch-48; ch = getchar();} x *= f; } template<typename T>void print(T x) { if(x < 0) putchar('-'), x = -x; if(x >= 10) print(x/10); putchar(x % 10 + '0'); } int main() { #ifndef ONLINE_JUDGE freopen("in.in", "r", stdin); freopen("out.out", "w", stdout); #endif IOS; slove(); return 0; } ll a[N]; void slove() { int T; cin>>T; while(T--) { ll n, x; cin>>n>>x; map<ll, ll> mp; mp.clear(); for(int i = 0; i < n; i++) { cin>>a[i]; mp[a[i]]++; } ll cnt = 0; for(auto i:mp) { if(mp[i.first] > 0 && mp[i.first*x] > 0) { ll minn = min(mp[i.first], mp[i.first*x]); mp[i.first] -= minn, mp[i.first*x] -= minn, cnt += 2*minn; } } cout<<n-cnt<<endl; } }
D. Repetitions Decoding
题意：
给定一个数组，每次可以在数组的任一位置插入两个相同的数，数也是任意的。定义 123123这种序列为 tandem repeats。输出最终使得原数组成为 tandem repeats的过程中，操作的总次数，每次在哪个位置，插入什么值。并且输出最终数组中，每一部分为 tandem repeats的连续子段的长度。
题解：
从前往后遍历数组。假设当前位置为 i，则在它后面的位置找到位置 j，使得 a[j] == a[i]。然后将 i到 j之间的数字，不断地插入 j后面的位置（每在后面插入一次值，下次插入位置就向后加1）。最终就能得到一个 tandem repeats。注意一下输出格式。
示例：
1 3 1 2 2 3
1 3 1 3 3 2 2 3（在第二个 1后面插入 3 3，这时前面的1 3 1 3已经是 tandem repeats了）
1 3 1 3 3 2 2 3 2 2 （在第二个 3后面插入 2 2）
1 3 1 3 3 2 2 3 2 2 2 2 （在上一次插入位置的下一位置插入 2 2）
这时整个数组已经是 tandem repeats了，能分为 3部分：[1 3 1 3] 、[3 2 2 3 2 2]、 [2 2]
代码：
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111#include<bits/stdc++.h> using namespace std; typedef long long ll; #define endl "n" #define IOS ios::sync_with_stdio(false); cin.tie(0) #define inf 0x3f3f3f3f #define pii pair<int, int> #define pll pair<ll, ll> #define pdd pair<double, double> #define debug(a) cout<<"tdebug:"<<a<<endl #define for1(i, a, b) for(int i = a; i <= b; i++) #define for2(i, b, a) for(int i = b; i >= a; i--) const double PI = acos(-1.0); const int mod = 998244353; const int eps = 1e-8; const int N = 10 + 2e5; void slove(); template<typename T>void read(T &x) { x = 0;char ch = getchar();ll f = 1; while(!isdigit(ch)){if(ch == '-') f *= -1; ch = getchar();} while(isdigit(ch)){x = x*10+ch-48; ch = getchar();} x *= f; } template<typename T>void print(T x) { if(x < 0) putchar('-'), x = -x; if(x >= 10) print(x/10); putchar(x % 10 + '0'); } int main() { #ifndef ONLINE_JUDGE freopen("in.in", "r", stdin); freopen("out.out", "w", stdout); #endif IOS; slove(); return 0; } void slove() { int T; cin>>T; while(T--) { int n; cin>>n; int a[N]; map<int, int> mp; for1(i, 1, n) { cin>>a[i]; mp[a[i]]++; } int f = 0; for(auto i:mp) { if(mp[i.first]&1) { cout<<"-1"<<endl; f = 1; break; } } if(f) continue; vector<pii> ans; ans.clear(); vector<int> ans2; ans2.clear(); mp.clear(); int idx = 1; for1(i, 1, n) { for1(j, i+1, n) { if(a[j] == a[i]) { idx = j; for1(k, i+1, j-1) { for2(x, n, idx+1) a[x+2] = a[x]; n += 2; a[idx+1] = a[idx+2] = a[k]; ans.push_back(make_pair(idx, a[k])); idx++; } ans2.push_back(idx-i+1); i = idx; //后面有 i++ break; } } } cout<<ans.size()<<endl; for(auto x:ans) cout<<x.first<<" "<<x.second<<endl; if(ans.size() == 0) { cout<<n/2<<endl; for1(i, 1, n/2) cout<<2<<" "; cout<<endl; } else { cout<<ans2.size()<<endl; for(auto i : ans2) cout<<i<<" "; cout<<endl; } } }
最后
以上就是神勇果汁最近收集整理的关于Codeforces Round #773 (Div. 2)（ＡＢＣＤ）A. Hard WayB. Power WalkingC. Great SequenceD. Repetitions Decoding的全部内容，更多相关Codeforces内容请搜索靠谱客的其他文章。
发表评论 取消回复