【CodeForces】Round 1017 (Div. 4)记录

题目链接:Codeforces Round 1017 (Div. 4)

A. Trippi Troppi

image-20250523182202040

输入示例:

1
2
3
4
5
6
7
8
9
7
united states america
oh my god
i cant lie
binary indexed tree
believe in yourself
skibidi slay sigma
god bless america

输出示例:

1
2
3
4
5
6
7
usa
omg
icl
bit
biy
sss
gba

参考代码:

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
#include <bits/stdc++.h>
using namespace std;

int n;
string ans[10000];

void PrientAns()
{
for (int i = 0; i < n; i++)
{
cout << ans[i] << endl;
}
}

int main()
{
cin >> n;
int count = 0,index = 0;
string tempAns;

for (int i = 0; i < n * 3; i++)
{
string tempStr;
cin >> tempStr;

if (count < 2)
{
tempAns += tempStr[0];
count++;
}
else if (count == 2)
{
tempAns += tempStr[0];
ans[index] = tempAns;
tempAns.clear();
index++;
count = 0;
}
}

PrientAns();
return 0;
}

B. Bobritto Bandito

image-20250523181952687

image-20250523182119998

输入示例:

1
2
3
4
5
4
4 2 -2 2
4 1 0 4
3 3 -1 2
9 8 -6 3

输出示例:

1
2
3
4
-1 1
0 1
-1 2
-5 3

题目解析:把题目结构一下就行了,输入的是m、n、l、r,分别对应总天数、目标天数、总天数下的左区间和总天数下的右区间。其实根本不需要这么多参数,两个就行了,一个是n目标天数,一个是l,因为一定包含0而l和r的间隔一定等于m,所以知道l就能知道l和r,然后再选一个间隔为n且在l和r区间内的数作为答案即可。

参考代码:

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
#include <bits/stdc++.h>
using namespace std;

int n;
int days[2000], offsetDay[2000];
//string ansLeft[2000], ansRight[2000];

void PrientAns()
{
for (int i = 0; i < n; i++)
{
int left = 0, right = 0;

if (offsetDay[i] == 0)
{
//没有偏移
left = 0;
right = days[i];
}
else if (-offsetDay[i] >= days[i])
{
//偏移量大于目标天数,可以所有感染向左
left = -days[i];
right = 0;
}
else
{
//偏移量小于目标天数,感染需要向右分布部分
left = offsetDay[i];
right = days[i] + offsetDay[i];
}

cout << left << " " << right << endl;
}
}

int main()
{
cin >> n;
int count = 0, index = 0;
int tempNum;

for (int i = 0; i < n * 4; i++)
{
cin >> tempNum;

if (count == 0)
{
count++;
}
else if (count == 1)
{
days[index] = tempNum;
count++;
}
else if (count == 2)
{
offsetDay[index] = tempNum;
count++;
}
else
{
count = 0;
index++;
}
}

PrientAns();
return 0;
}

C. Brr Brrr Patapim

image-20250526114635836

输入示例:

1
2
3
4
5
6
7
8
9
10
3
3
1 6 2
6 2 4
2 4 3
1
1
2
2 3
3 4

输出示例:

1
2
3
5 1 6 2 4 3 
2 1
1 2 3 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
#include <bits/stdc++.h>
using namespace std;

int t, n, g[1601][1601], j, i, x[1601], h[1601], p;

int main()
{
cin >> t;
while (t > 0)
{
t--;
cin >> n;
for (int i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
{
cin >> g[i][j];
x[i + j] = g[i][j];
h[g[i][j]]++;
}
for (p = 1; p <= 2 * n; p++)
{
if (h[p] == 0)
x[1] = p;
h[p] = 0;
}
for (p = 1; p <= 2 * n; p++)
{
cout << x[p] << " ";
}
cout << endl;
}
}

D. Tung Tung Sahur

image-20250526142447276

输入示例:

1
2
3
4
5
6
7
8
9
10
11
5
R
RR
LRLR
LRLR
LR
LLLR
LLLLLRL
LLLLRRLL
LLRLRLRRL
LLLRLRRLLRRRL

输出示例:

1
2
3
4
5
YES
YES
NO
NO
YES

题目解析:如果按照递归模拟的思路去做时间复杂度应该过不了,就不考虑这个办法了。这里参考了用另一种思路,先定义输入的字符串为s1和s2,s1,我们以示例中的第四个输入为例子,LLLLLRL为s1,以LLLLRRLL为s2,需要将s1和s2按照L和R分割,将s1分割成LLLLL、R、L,分别为x、y、z,将s2分割成LLLL、RR、LL,这三段分别为,a、b、c。如果a和x的关系为a >= x && a <= x * 2则对b和y判断,全部通过则为yes,否则为no。

参考代码:

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
#include <bits/stdc++.h>
using namespace std;

int t, n;
string s1, s2;

int main()
{
cin >> t;
while (t--)
{
cin >> s1;
cin >> s2;

while (s1.size())
{
int pos = 0;
while (pos < s1.size() && s1[pos] == s1[pos + 1])
{
pos++;
}
int num = pos + 1;
char c = s1[pos];
int k = 0;
while (k < s2.size() && s2[k] == c)
{
k++;
}
if (k >= num && k <= 2 * num)
{
s2.erase(0, k);
}
else
break;
s1.erase(0, num);
}
if (!s1.size() && !s2.size())
{
cout << "YES" << endl;
}
else
{
cout << "NO" << endl;
}
}
}