我是靠谱客的博主 神勇果汁,这篇文章主要介绍Codeforces Round #773 (Div. 2)(ABCD)A. Hard WayB. Power WalkingC. Great SequenceD. Repetitions Decoding,现在分享给大家,希望可以做个参考。

目录

  • 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
13
void 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
23
void 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)(ABCD)A. Hard WayB. Power WalkingC. Great SequenceD. Repetitions Decoding的全部内容,更多相关Codeforces内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(76)

评论列表共有 0 条评论

立即
投稿
返回
顶部