Codeforces Round 713
经典暴力模拟掉分场
本场链接：
https://codeforces.com/contest/1512
A - Spy Detected!
解析
水水水，不解析
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 0x3f3f3f3f;
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
int n;
scanf("%d", &n);
int a[n];
map<int, int> mp;
for(int i = 0; i < n; ++i) scanf("%d", &a[i]);
for(int i = 0; i < n; ++i) mp[a[i]]++;
for(int i = 0; i < n; ++i){
if(mp[a[i]] <= 1){
printf("%d\n", i + 1);
break;
}
}
}
return 0;
}
|
B - Almost Rectangle
思路
如果两个*在对角线，也就是行列都不同的情况下，构造矩形唯一，用1的行，2的列作为坐标得到第3个点，用1的列，2的行作为坐标得到第4个点；
如果在同行，为了尽量不超过图的范围，构造两个在上方的点，或者两个在下方的点即可。
代码
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 405;
char a[maxn][maxn];
int main()
{
int t;
cin >> t;
while(t--)
{
vector<int> r;
vector<int> c;
int n;
cin >> n;
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
cin >> a[i][j];
if(a[i][j] == '*'){
r.push_back(i), c.push_back(j);
}
}
}
int r1, c1, r2, c2;
if(r[0] == r[1]){
if(r[0] + 1 < n){
r1 = r2 = r[0] + 1;
c1 = c[0], c2 = c[1];
}
else {
r1 = r2 = r[0] - 1;
c1 = c[0], c2 = c[1];
}
}
else if(c[0] == c[1]){
if(c[0] + 1 < n){
c1 = c2 = c[0] + 1;
}
else{
c1 = c2 = c[0] - 1;
}
r1 = r[0], r2 = r[1];
}
else{
r1 = r[0], c1 = c[1];
r2 = r[1], c2 = c[0];
}
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
if((i == r1 && j == c1) || (i == r2 && j == c2)){
cout << '*';
}
else cout << a[i][j];
}
cout << endl;
}
}
return 0;
}
|
C - A-B Palindrome
题意
给一个部分为问号的01串，给定$a$,$b$，要求把所有的问号替换为0或1，使最后的串恰好有$a$个0和$b$个1.
给出串和$a,b$，问可否构造出，可以的话请你构造一个看看。
分析
写代码的时候为了避免不必要的讨论，分三次遍历。
第一次，统计原字符串中的0,1个数。
第二次，统计字符串中一位为0或者1，而其反转位为问号的位置，并且这些问号能替换的数字也就确定了，替换之。
第三次，统计字符串中为问号，且其反转位也为问号的位置。
*注意第三次要细分讨论：
如果串的长度是奇数，则把最中间的位置预先处理掉，然后在第三次遍历的过程中略过这点。
==怎么预处理？==
这个时候，由于我们剩下的操作就是把成对的问号替换掉，当然是偶数个的配对，因此如果中间的位置是问号的话，那它只能由$a,b$中为奇数的来替换，这样才保证剩余的未放置的0和1都是偶数个（在串可以构造的情况下）。
全都替换好了之后，检查剩余待替换的0,1个数是否都为0，是就输出替换后的串，否则-1.
代码
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
| #include <bits/stdc++.h>
#define r s.size() - i - 1
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t--)
{
int a, b;
string s;
cin >> a >> b >> s;
bool flag = 1;
for(int i = 0; i < s.size(); ++i){
if(s[i] != '?' && s[r] != '?'){
if(s[i] != s[r]) {
flag = 0;
break;
}
else if(s[i] == '1') b--;
else if(s[i] == '0') a--;
}
}
if(!flag){
cout << -1 << endl;
continue;
}
for(int i = 0; i < s.size(); ++i){
if(s[i] == '?' && s[r] == '0'){
s[i] = '0';
a-=2;
}
else if(s[i] == '0' && s[r] == '?'){
s[r] = '0';
a-=2;
}
else if(s[i] == '?' && s[r] == '1'){
s[i] = '1';
b-=2;
}
else if(s[i] == '1' && s[r] == '?'){
s[r] = '1';
b-=2;
}
}
if(!flag || b < 0 || a < 0){
cout << -1 << endl;
continue;
}
if(b % 2 != 0){
s[(s.size() - 1) / 2] = '1';
b--;
}
else if(a % 2 != 0){
s[(s.size() - 1) / 2] = '0';
a--;
}
for(int i = 0; i < s.size(); ++i){
if(s.size()%2 == 0 & i == (s.size() - 1) / 2) continue;
if(s[i] == '?'){
if(a > 0){
s[i] = s[r] = '0';
a -= 2;
}
else if(b > 0){
s[i] = s[r] = '1';
b -= 2;
}
}
}
if(a == 0 && b == 0){
cout << s << endl;
}
else cout << -1 << endl;
}
return 0;
}
|
D - Corrupted Array
被卡long long的hack数据叉掉了呜呜呜hacker好狠心啊
题意
给n+2个数，问是否可以还原出这样一个数组$a$:
- 这n+2个数中有n个数都是$a$中的数.
- 剩余的两个数中，至少有一个数等于数组$a$的求和.
思路
将原数组从小到大排序，由于要找一个等于其他n个数的和的数，而所有的数都是正数，因此这个和数只能出现在最大的两个数里面。
假如这个数就是倒数第一个，那么它应该等于前n个数的和；
假如这个数是倒数第二个，那么它应该等于前n+1个数的和减去其中某个数。
代码
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t--){
int n;
cin >> n;
int b[n + 2];
for(int i = 0; i < n + 2; ++i){
cin >> b[i];
}
sort(b, b + n + 2);
int sum = 0;
for(int i = 0; i < n + 1; ++i){
sum += b[i];
}
if(sum - b[n] == b[n]){
for(int i = 0; i < n; ++i){
cout << b[i] << ' ';
}
cout << endl;
}
else{
int flag = -1;
for(int i = 0; i < n + 1; ++i){
if(sum - b[i] == b[n + 1]){
flag = i;
break;
}
}
if(flag == -1){
cout << -1 << endl;
}
else{
for(int i = 0; i < n + 1; ++i){
if(i == flag) continue;
else cout << b[i] << ' ';
}
cout << endl;
}
}
}
return 0;
}
|
E - Permutation by Sum
题意
从$1$到$n$中找$r-l+1$个数，要求它们的和为$s$，问能否找出。
题目要求输出一个全排列，其中你找出的数要出现在$[r,l]$这个下标区间内。
分析
从$1$到$n$这些数中，由于所有整数应有尽有，不存在中间有空缺，因此从$1$到$\sum_{i=1}^n$的任意数都能取到。所以，只要这个$s$的范围在 $[前r-l+1个数的和,后r-l+1个数的和]$之间的话，那么就一定能构造出这样的$r-l+1$个数.
我们尝试贪心构造：
先将$r-l+1$简记为$num$，首先，我们初始状态下的$ans$数组为$1$到$num$这些数。
我们要做的是将其中的某些数替换为更大的数，来使数组总和达到$s$。
而由于所有整数应有尽有，不存在空缺，因此我们大胆地尽量缩小差距，最后差距恰好可以通过替换消除时，就完成了。
例如，现在的差距为$d$，$d=s-\sum_{i=1}^{num}$，我们通过一次替换可以缩小的最大差距为$n-1$，即把最小的1替换为未使用的最大的n。如果我们的差距不足$n-1$，再看将2替换为n可不可以，以此类推.
替换成功后，我们得标记n已经使用，这样我们就不会重复地将n引入$ans$数组了。为了简单地做到这点，使用双指针，一个从1开始，走到$num$,代表现在待替换的数；另一个从$n$开始，走到$num+1$，代表最大的未使用的数。
代码
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t--){
int n, l, r, s;
cin >> n >> l >> r >> s;
int num = r - l + 1;
int mn = (num * (num + 1)) / 2;
int mx = (n - num + 1 + n) * num / 2;
if(s > mx || s < mn){
cout << -1 << endl;
continue;
}
else{
int d = s - mn;
int in = n;
int ans[num] = {0};
int v[n + 1] = {0};
for(int i = 1; i <= num; ++i){
if(in - i <= d){
d -= in - i;
ans[i - 1] = in--;
}
else ans[i - 1] = i;
}
if(d > 0){
while(1){
if(in - num == d){
ans[num - 1] = in;
break;
} else in--;
}
}
for(int i = 0; i < num; ++i) v[ans[i]] = 1;
int p = 1;
for(int i = 1; i < l; ++i){
while(v[p]) p++;
cout << p++ << ' ';
}
for(int i = 0; i < num; ++i){
cout << ans[i] << ' ';
}
for(int i = r + 1; i <= n; ++i){
while(v[p]) p++;
cout << p++ << ' ';
}
cout << endl;
}
}
return 0;
}
|
