A - Boring Apartments
直接找规律。ans=10∗(dig−1)+2len(len+1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
string x;
cin >> x;
int dig = x[0] - '0' - 1;
int len = x.size();
cout << dig * 10 + len * (len + 1) / 2 << endl;
}
return 0;
}
|
B - Yet Another Bookshelf
这道题也是找规律。答案是从左数第一个1开始到右数第一个数结束，之间存在的0的个数。注意：输出的下标从1开始。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (auto &it : a) cin >> it;
while (a.back() == 0) a.pop_back();
reverse(a.begin(), a.end());
while (a.back() == 0) a.pop_back();
cout << count(a.begin(), a.end(), 0) << endl;
}
return 0;
}
|
C - Dominant Piranha
这道题的答案不唯一，按照找出一个答案的思路出发，显然答案大概率产生在最大的元素上，我们发现，只要最大的元素与相邻的元素不相等，最大的元素就能继续成长，成为更大的元素（如果最大的元素有多个，此时，就超越那些原本一样最大的元素），然后，显然他就能成为dominant 元素。
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
| #include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
int mx = 0;
for (auto &it : a) {
cin >> it;
mx = max(mx, it);
}
int idx = -1;
for (int i = 0; i < n; ++i) {
if (a[i] != mx) continue;
if (i > 0 && a[i - 1] != mx) idx = i + 1;
if (i < n - 1 && a[i + 1] != mx) idx = i + 1;
}
cout << idx << endl;
}
return 0;
}
|
D - Districts Connection
题意：给出了n个地区，每一个地区有一个匪帮，id为ai（两个地区有可能是同一个匪帮）。要求是找到一个连通图，使得两两地区的匪帮不是同一个匪帮。让你去判断存不存在这样的连通图，存在的话要输出图的边，有多个答案输出一个即可。
思路：写几个例子就能发现，只有当所有的地区都是一个匪帮时，才不存在连通图。其余情况都存在连通图。一个比较简单的构造方法就是先记录n=0的匪帮id：a0，把其他地区匪帮id不为a0的都挂在n=0这个地区上，这样剩下的不连通的区域就只剩下id同样是a0的其他地区，只需要找到一个挂在n=0上的id不为a0的地区，将剩余的挂载于其上即可。
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
| #include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (auto &it : a) cin >> it;
vector<pair<int, int>> res;
int idx = -1;
for (int i = 1; i < n; ++i) {
if (a[i] != a[0]) {
idx = i;
res.push_back({1, i + 1});
}
}
if (idx == -1) {
cout << "NO" << endl;
continue;
}
for (int i = 1; i < n; ++i) {
if (a[i] == a[0]) {
res.push_back({idx + 1, i + 1});
}
}
cout << "YES" << endl;
for (auto [x, y] : res) cout << x << " " << y << endl;
}
return 0;
}
|
其他题目的官方题解（水平不足，没做）：
http://codeforces.com/blog/entry/83903
