Codeforces Round 984 (Div. 3)
Log
2024/11/13
C 解决了，奇奇怪怪的。顺带解决了 D，全是实用细节，我一定会回来补坑的对吧！
2024/11/12
这次比赛敲出两题，第三题暴力解法超时，过后会想着如何优化时间复杂度。第三题考查动态字符串的搜索，估计用不了 KMP 算法。
排名 11832 / 39935
D. I Love 1543
Source: Codeforces Round 984 D. I Love 1543
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1010;
char g[N][N];
char layer[N * 4];
int solve()
{
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) scanf("%s", g[i]);
int count = 0;
for (int i = 0; (i + 1) * 2 <= n && (i + 1) * 2 <= m; i++)
{
int idx = 0;
for (int j = i; j < m - i; j++) layer[idx++] = g[i][j];
for (int j = i + 1; j < n - 1 - i; j++) layer[idx++] = g[j][m - 1 - i];
for (int j = m - 1 - i; j >= i; j--) layer[idx++] = g[n - 1 - i][j];
for (int j = n - 2 - i; j >= i + 1; j--) layer[idx++] = g[j][i];
for (int j = 0; j < idx; j++)
if (layer[j] == '1' && layer[(j + 1) % idx] == '5' && layer[(j + 2) % idx] == '4' && layer[(j + 3) % idx] == '3')
count++;
}
return count;
}
int main()
{
int T; cin >> T;
while (T--)
{
cout << solve() << endl;
}
return 0;
}
补题 C
C. Anya and 1100
While rummaging through things in a distant drawer, Anya found a beautiful string $s$ consisting only of zeros and ones.
Now she wants to make it even more beautiful by performing $q$ operations on it.
Each operation is described by two integers $i$ $(1≤i≤|s|)$ and $v$ $(v∈{0,1})$ and means that the $i$-th character of the string is assigned the value $v$ (that is, the assignment $s_i=v$ is performed).
But Anya loves the number $1100$, so after each query, she asks you to tell her whether the substring “1100” is present in her string (i.e. there exist such $1≤i≤|s|−3$ that $sisi+1si+2si+3=1100$).
Input
The first line contains one integer $t$ $(1≤t≤104)$ — the number of test cases.
The first line of the test case contains the string $s$ $(1≤|s|≤2⋅105)$, consisting only of the characters “0” and “1”. Here $|s|$ denotes the length of the string $s$.
The next line contains an integer $q$ $(1≤q≤2⋅105)$ — the number of queries.
The following $q$ lines contain two integers $i$ $(1≤i≤|s|)$ and $v$ $(v∈{0,1})$, describing the query.
It is guaranteed that the sum of $|s|$ across all test cases does not exceed $2⋅105$. It is also guaranteed that the sum of $q$ across all test cases does not exceed $2⋅105$.
Output
For each query, output “YES”, if “1100” is present in Anya’s string; otherwise, output “NO”.
You can output the answer in any case (upper or lower). For example, the strings “yEs”, “yes”, “Yes”, and “YES” will be recognized as positive responses.
Example
input
4
100
4
1 1
2 0
2 0
3 1
1100000
3
6 1
7 1
4 1
111010
4
1 1
5 0
4 1
5 0
0100
4
3 1
1 1
2 0
2 1
output
NO
NO
NO
NO
YES
YES
NO
NO
YES
YES
YES
NO
NO
NO
NO
Tutorial
solution
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long l;
char buf[1000000];
l n;
bool check_1100(l i) {
if (i < 0) return false;
if (i >= n - 3) return false;
if (buf[i] == '1' && buf[i + 1] == '1' && buf[i + 2] == '0' && buf[i + 3] == '0') return true;
return false;
}
void solve() {
scanf("%s", buf);
n = strlen(buf);
l count = 0;
for (l i = 0; i < n; i++)
if (check_1100(i)) count++;
l q; scanf("%lld", &q);
while (q--) {
l i, v; scanf("%lld %lld", &i, &v); i--;
if (buf[i] != '0' + v) {
bool before = check_1100(i - 3) || check_1100(i - 2) || check_1100(i - 1) || check_1100(i);
buf[i] = '0' + v;
bool after = check_1100(i - 3) || check_1100(i - 2) || check_1100(i - 1) || check_1100(i);
count += after - before;
}
printf(count ? "YES\n" : "NO\n");
}
}
int main() {
l t; scanf("%lld", &t);
while (t--) solve();
}
B. Startup
Arseniy came up with another business plan — to sell soda from a vending machine! For this, he purchased a machine with $n$ shelves, as well as $k$ bottles, where the $i$-th bottle is characterized by the brand index $b_i$ and the cost $c_i$.
You can place any number of bottles on each shelf, but all bottles on the same shelf must be of the same brand.
Arseniy knows that all the bottles he puts on the shelves of the machine will be sold. Therefore, he asked you to calculate the maximum amount he can earn.
Input
The first line contains one integer $t$ $(1≤t≤104)$ — the number of test cases.
The first line of each test case contains two integers $n$ and $k$ $(1≤n,k≤2⋅105)$, where $n$ is the number of shelves in the machine, and $k$ is the number of bottles available to Arseniy.
The next $k$ lines contain two integers $b_i$ and $c_i$ $(1≤b_i≤k,1≤c_i≤1000)$ — the brand and cost of the $i$-th bottle.
It is also guaranteed that the sum of $n$ across all test cases does not exceed $2⋅105$ and that the sum of $k$ across all test cases also does not exceed $2⋅105$.
Output
For each test case, output one integer — the maximum amount that Arseniy can earn.
Example
input
4
3 3
2 6
2 7
1 15
1 3
2 6
2 7
1 15
6 2
1 7
2 5
190000 1
1 1000
output
28
15
12
1000
my code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
using namespace std;
const int N = 200010;
int a[N];
bool cmp(int a, int b)
{
return a > b;
}
long long solve()
{
memset(a, 0, sizeof a);
map<int, int> mp;
int n, k;
cin >> n >> k;
for (int i = 1; i <= k; i++)
{
int b, c;
cin >> b >> c;
mp[b] += c;
}
int cnt = 0;
for (auto item : mp)
{
a[++cnt] = item.second;
}
sort(a + 1, a + 1 + cnt, cmp);
long long res = 0;
for (int i = 1; i <= n; i++)
res += a[i];
return res;
}
int main()
{
int T; cin >> T;
while (T--)
{
cout << solve() << endl;
}
return 0;
}
A. Quintomania
Boris Notkin composes melodies. He represents them as a sequence of notes, where each note is encoded as an integer from $0$ to $127$ inclusive. The interval between two notes $a$ and $b$ is equal to $|a−b|$ semitones.
Boris considers a melody perfect if the interval between each two adjacent notes is either $5$ semitones or $7$ semitones.
After composing his latest melodies, he enthusiastically shows you his collection of works. Help Boris Notkin understand whether his melodies are perfect.
Input
The first line contains an integer $t$ $(1≤t≤1000)$ — the number of melodies.
Each melody is described by two lines.
The first line contains an integer $n$ $(2≤n≤50)$ — the number of notes in the melody.
The second line contains $n$ integers $a_1,a_2,…,a_n$ $(0≤a_i≤127)$ — the notes of the melody.
Output
For each melody, output “YES”, if it is perfect; otherwise, output “NO”.
You can output the answer in any case (upper or lower). For example, the strings “yEs”, “yes”, “Yes”, and “YES” will be recognized as positive responses.
Example
input
8
2
114 109
2
17 10
3
76 83 88
8
38 45 38 80 85 92 99 106
5
63 58 65 58 65
8
117 124 48 53 48 43 54 49
5
95 102 107 114 121
10
72 77 82 75 70 75 68 75 68 75
output
YES
YES
YES
NO
YES
NO
YES
YES
my code
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 55;
bool solve()
{
int n; cin >> n;
int a[N];
bool valid = true;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
if (i > 1)
{
if (abs(a[i] - a[i - 1]) != 5 && abs(a[i] - a[i - 1]) != 7)
valid = false;
}
}
return valid;
}
int main()
{
int T; cin >> T;
while (T--)
{
if (solve()) puts("YES");
else puts("NO");
}
return 0;
}
