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$:

  1. 这n+2个数中有n个数都是$a$中的数.
  2. 剩余的两个数中,至少有一个数等于数组$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];
}
// x = b[n + 1]
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;
}