Abstract
第二次打 CodeForce 。
A. Primary Task
Idea
签到题。
意思就是说给一个字符串，要你判断一下前两位是不是 10 ，除去前两位后后面的部分是不是一个大于等于 2 的数（不能有前导零）。
Code
#include <bits/stdc++.h>
using namespace std;
void solve()
{
string text;
cin >> text;
if (text.length() <= 2)
{
cout << "NO" << endl;
return;
}
if (!(text[0] == '1' && text[1] == '0'))
{
cout << "NO" << endl;
return;
}
if (text[2] == '0')
{
cout << "NO" << endl;
return;
}
else if (text[2] == '1')
{
if (text.length() == 3)
{
cout << "NO" << endl;
return;
}
}
cout << "YES" << endl;
return;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(nullptr);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
B. Seating in a Bus
Idea
签到题。
给你一个序列，第 i 项表示第 i 个上车的人坐的位置，除了第一个人以外，其余的人必须坐在其他人旁边。不难发现所有人必须分布在一个连续区间上，那么我们只用维护左右端点就可以了，时间复杂度是 O(n) 的。
Code
#include <bits/stdc++.h>
using namespace std;
int a[10000000];
void solve()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
int l = a[0], r = a[0];
for (int i = 1; i < n; i++)
{
if (a[i] == l - 1)
{
l--;
}
else if (a[i] == r + 1)
{
r++;
}
else
{
cout << "NO" << endl;
return;
}
}
cout << "YES" << endl;
return;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(nullptr);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
C. Numeric String Template
Idea
签到题。
按顺序遍历字符串，用两个 map 给字母和数字建立起一一映射就可以了。
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[10000000];
void solve()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
int m;
cin >> m;
while (m--)
{
map<int, char> q1;
map<char, int> q2;
string text;
cin >> text;
if (text.length() != n)
{
cout << "NO" << endl;
continue;
}
bool ok = 1;
for (int i = 0; i < n; i++)
{
if (q1[a[i]])
{
if (text[i] != q1[a[i]])
{
cout << "NO" << endl;
ok = 0;
break;
}
}
if (q2[text[i]])
{
if (a[i] != q2[text[i]])
{
cout << "NO" << endl;
ok = 0;
break;
}
}
q1[a[i]] = text[i], q2[text[i]] = a[i];
}
if (ok)
{
cout << "YES" << endl;
}
}
return;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(nullptr);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
D. Right Left Wrong
Idea
这一题不再是简单的模拟了，需要一点贪心。
首先，由于 a[i] >= 1 ,所以我们总是希望尽可能多的取数，对于下面这个序列，我们要如何取数呢？
1 2 3 4 5 6
L L L R R R
我们希望每一个数字被取的次数尽可能多，那么最优的方案就是找到最左边的 L 和 最右边的 R ，之后，再找到剩余的项中，最左边的 L 和最右边的 R ，以此类推。
这显然是双指针，所以时间复杂度是 O(n) 。
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[10000000];
void solve()
{
int n;
cin >> n;
cin >> a[0];
for (int i = 1; i < n; i++)
{
int m;
cin >> m;
a[i] = a[i - 1] + m;
}
string text;
cin >> text;
int l = -1, r = text.length();
int ans = 0;
while (1)
{
for (l++; l <= text.length() - 1; l++)
{
if (text[l] == 'L')
{
break;
}
}
for (r--; r >= 0; r--)
{
if (text[r] == 'R')
{
break;
}
}
if (l <= r)
{
ans += a[r] - a[l - 1];
}
else
{
break;
}
}
cout << ans << endl;
return;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(nullptr);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
E. Photoshoot for Gorillas
Idea
一道有点烦人的数学题。
最优的排列是不难找到的。我们可以将矩阵上每一个格子的分值都计算出来，然后从大到小排列，将大猩猩按照从高到低的顺序依次往里面放就可以。
计算矩阵分值的时间复杂度是 O(n*m) ，考虑到对于所有测试样例 n*m <= 2*1e5，可以接受。
最后提一下怎么计算矩阵分值。
对于第 i 行第 j 列的单元格，我们假设方阵的左边位于第 L 列，那么不难得出以下约束条件。
- L >= 1
- L + k - 1 <= m
- L <= j <= L + k - 1
由此，可以得出 L 的取值范围的大小，记作 SL 。
同理可以求出方阵上边界的取值范围，记作 SU ，那么这个单元格的分值就是 SU * SL 。
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m, k;
int s;
int h[10000000];
int q[10000000];
void solve()
{
cin >> n >> m >> k;
cin >> s;
int cnt = 0;
map<int, bool> vis;
for (int i = 0; i < s; i++)
{
cin >> h[i];
}
sort(h, h + s);
map<int, int> times;
int maxH = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
int R = min(j, m - k + 1);
int L = max(1LL, (j - k + 1));
if (R < L)
{
continue;
}
int U = max(1LL, i - k + 1);
int D = min(n - k + 1, i);
if (D < U)
{
continue;
}
times[(D - U + 1) * (R - L + 1)]++;
if (!vis[(D - U + 1) * (R - L + 1)])
{
q[++cnt] = (D - U + 1) * (R - L + 1);
vis[(D - U + 1) * (R - L + 1)] = 1;
}
maxH = max(maxH, D - U + 1) * (R - L + 1);
}
}
sort(q + 1, q + 1 + cnt);
int res = 0;
int cur = cnt;
for (int i = s - 1; i >= 0; i--)
{
if (times[q[cur]])
{
times[q[cur]]--;
res += h[i] * q[cur];
}
else
{
cur--;
times[q[cur]]--;
res += h[i] * q[cur];
}
}
cout << res << endl;
return;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(nullptr);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}