Practice.
A. Spell Check
题意
给定一个字符串，判断其是否为字符串 \(\mathtt{Timur}\) 任意排列后的字符串。
思路
我们用 \(map\) 存一下这 \(5\) 个字符的出现次数，如果都出现一次，并且长度为 \(5\)，即可。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define psi pair<string, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
string s;
cin >> s;
map<char, int> mp = {{'T', 0}, {'i', 0}, {'m', 0}, {'u', 0}, {'r', 0}};
for(char e : s){
if(mp.count(e)) mp[e] ++;
else{
cout << "NO\n";
return;
}
}
cout << ((mp['T'] == 1 && mp['i'] == 1 && mp['m'] == 1 && mp['u'] == 1 && mp['r'] == 1) ? "YES\n" : "NO\n");
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}水
B. Colourblindness
题意
对于一个蓝绿色盲，给定两串长度相等的 \(R, G, B\) 字符串，输出是否相同。
思路
将 \(G, B\) 视为 \(1\)，\(R\) 视为 \(0\)，枚举即可。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define psi pair<string, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
map<char, int> mp = {{'R', 0}, {'G', 1}, {'B', 1}};
int n;
cin >> n;
string a, b;
cin >> a >> b;
for(int i=0;i<n;i++){
if(mp[a[i]] != mp[b[i]]){
cout << "NO\n";
return;
}
}
cout << "YES\n";
return;
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}这就不得不提某个愚人节了（
C. Word Game
题意
对于 \(3\) 个人，给定每个人写下的单词数 \(n\)，并给出每个人写下的单词，按照下面的方式给每个人计分，并输出每个人的分数：
对于某个人说出的某个单词：
如果这个单词只被 \(1\) 个人写下，那么这个人得 \(3\) 分；
如果这个单词被 \(2\) 个人写下，那么这两个人各得 \(1\) 分；
如果这个单词被 \(3\) 个人写下，那么所有人都不得分
思路
用 \(map\) 存一下出现次数，然后再枚举所有单词统计分数即可。
时间复杂度：\(O(n \log n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define psi pair<string, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
vector<string> a(n), b(n), c(n);
map<string, int> cnt;
for(int i=0;i<n;i++){
cin >> a[i];
cnt[a[i]] ++;
}
for(int i=0;i<n;i++){
cin >> b[i];
cnt[b[i]] ++;
}
for(int i=0;i<n;i++){
cin >> c[i];
cnt[c[i]] ++;
}
int A = 0, B = 0, C = 0;
for(auto e : a){
if(cnt[e] == 1) A += 3;
else if(cnt[e] == 2) A ++;
}
for(auto e : b){
if(cnt[e] == 1) B += 3;
else if(cnt[e] == 2) B ++;
}
for(auto e : c){
if(cnt[e] == 1) C += 3;
else if(cnt[e] == 2) C ++;
}
cout << A << ' ' << B << ' ' << C << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}ctrl c + ctrl v
D. Line
题意
给定一个由 \(L, R\) 组成的字符串，定义 \(L\) 表示该位置左边有多少字符，\(R\) 表示该位置右边有多少字符（上述均不包含本身）。
定义字符串的 值 为各字符代表的数量之和。
现在，定义一次操作为选定一个字符，将其改为 \(L\) 或 \(R\)。对于 \(k \in [1, n]\)，输出最多执行 \(k\) 次操作后字符串 值 的最大值。
思路
这是一个很显然的贪心，如果我们不考虑操作次数，最后前一半的字符肯定是 \(R\)，后一半的字符肯定是 \(L\)（若有奇数个，显然中间的字符的选择是无影响的）。
并且，我们可以贪心地认为，我们只要从两边开始向里修改，即可让 值 最大。
当然，如果次数过多了，我们随便挑一个字符将其改为本身即可。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define psi pair<string, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
int ans = 0;
string s;
cin >> s;
for(int i=0;i<n;i++) {
char cur = s[i];
if (cur == 'L') ans += i;
else ans += n - i - 1;
}
int l = 0, r = n - 1, cnt = 0;
while(l < r){
if(s[l] == 'L'){
ans -= l;
ans += n - l - 1;
cnt ++;
cout << ans << ' ';
}
if(s[r] == 'R'){
ans -= n - r - 1;
ans += r;
cnt ++;
cout << ans << ' ';
}
l ++, r --;
}
for(int i=cnt;i<n;i++) cout << ans << ' ';
cout << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}简单的贪心 + 双指针
E. Counting Rectangles
题意
给定 \(n\) 个 \(h_i \times w_i\) 的矩形。
现在，给定 \(q\) 次询问，每次询问给定四个整数 \(h_s\ w_s\ h_b\ w_b\)，输出满足 \(h_s < h_i < h_b, w_s < w_i < w_b\) 的所有矩形的面积和。
思路
首先，根据题给范围，我们不可以在每次询问时都遍历一遍区间。
注意范围，我们需要的就是一个矩形范围内的所有矩形的面积和。
因而，我们考虑二维前缀和。
因为长度范围很小，我们直接开一个二维数组，\(a[h][w]\) 表示以原点和 \((h, w)\) 为对角顶点的矩形范围内所有矩形的面积和，套板子即可。
时间复杂度：\(O(n + 1e6 + q)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define psi pair<string, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n, q;
cin >> n >> q;
vector<vector<int>> sum(1010, vector<int>(1010, 0));
for(int i=0;i<n;i++) {
int h , w;
cin >> h >> w;
sum[h][w] += h * w;
}
for(int i=1;i<=1e3;i++)
for(int j=1;j<=1e3;j++){
sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
}
while(q --){
int hs, ws, hb, wb;
cin >> hs >> ws >> hb >> wb;
cout << (sum[hb - 1][wb - 1] - sum[hs][wb - 1] - sum[hb - 1][ws] + sum[hs][ws]) << '\n';
}
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}对，没错，我 \(tle\) 过
F. L-shapes
题意
给定一个由 "." 和 "*" 组成的矩阵，定义 "L型" 如下：
*. .* ** **
** ** .* *.检查矩阵是否满足下面的条件：
只包含 "L型"，不包含其他由 "*" 组成的图形；
"L型" 中的 "*" 字符需满足以其为中心的 \(9\) 宫格里都没有 "*"（除了 "L型" 的其他 "*" 字符）
下面给出不满足条件 \(2\) 的例子：
..** ....
*.*. *.**
**.. ***.思路
这是一个 \(2 \times 2\) 的图案，考虑数据范围，我们完全可以枚举所有 \(2 \times 2\) 的区域，判断其是否为 \(4\) 个图案的其中一种。
如果我们判定这是一个 "L型" 图案，我们就可以进行分讨，判断外围一圈中指定位置是否出现了 "*"，如果有，直接输出 \(NO\)。
在判定之时，如果是 "L型" 图案，我们顺便标记一下图案中的 "*"，那么，最后如果出现未被标记的 "*"，就是出现了 "非L型"。
下面用 "/" 表示需要判定的位置：
///. ./// //// ////
/*.. ..*/ /**/ /**/
/**/ /**/ ..*/ /*..
//// //// ./// ///.时间复杂度：\(O(n^2)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define psi pair<string, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
//直接按2x2扫
int n, m;
cin >> n >> m;
vector<vector<char>> a(n + 2, vector<char>(m + 2, '.'));
vector<vector<bool>> st(n + 2, vector<bool>(m + 2));
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
for (int j = 1; j <= m; j++) a[i][j] = s[j - 1];
}
//tl tr
//bl br
for (int i = 1; i < n; i++)
for (int j = 1; j < m; j++) {
char tl = a[i][j], tr = a[i][j + 1], bl = a[i + 1][j], br = a[i + 1][j + 1];
if (tl == '*' && tr == '.' &&
bl == '*' && br == '*') {
bool ok = true;
ok &= a[i - 1][j - 1] != '*' && a[i - 1][j] != '*' && a[i - 1][j + 1] != '*';
ok &= a[i][j - 1] != '*' && a[i][j + 2] != '*';
ok &= a[i + 1][j - 1] != '*' && a[i + 1][j + 2] != '*';
ok &= a[i + 2][j - 1] != '*' && a[i + 2][j] != '*' && a[i + 2][j + 1] != '*' && a[i + 2][j + 2] != '*';
if (!ok) {
cout << "NO\n";
return;
}
st[i][j] = st[i + 1][j] = st[i + 1][j + 1] = true;
}
if (tl == '.' && tr == '*' &&
bl == '*' && br == '*') {
bool ok = true;
ok &= a[i - 1][j] != '*' && a[i - 1][j + 1] != '*' && a[i - 1][j + 2] != '*';
ok &= a[i][j - 1] != '*' && a[i][j + 2] != '*';
ok &= a[i + 1][j - 1] != '*' && a[i + 1][j + 2] != '*';
ok &= a[i + 2][j - 1] != '*' && a[i + 2][j] != '*' && a[i + 2][j + 1] != '*' && a[i + 2][j + 2] != '*';
if (!ok) {
cout << "NO\n";
return;
}
st[i + 1][j] = st[i][j + 1] = st[i + 1][j + 1] = true;
}
if (tl == '*' && tr == '*' &&
bl == '*' && br == '.') {
bool ok = true;
ok &= a[i - 1][j - 1] != '*' && a[i - 1][j] != '*' && a[i - 1][j + 1] != '*' && a[i - 1][j + 2] != '*';
ok &= a[i][j - 1] != '*' && a[i][j + 2] != '*';
ok &= a[i + 1][j - 1] != '*' && a[i + 1][j + 2] != '*';
ok &= a[i + 2][j - 1] != '*' && a[i + 2][j] != '*' && a[i + 2][j + 1] != '*';
if (!ok) {
cout << "NO\n";
return;
}
st[i][j] = st[i + 1][j] = st[i][j + 1] = true;
}
if (tl == '*' && tr == '*' &&
bl == '.' && br == '*') {
bool ok = true;
ok &= a[i - 1][j - 1] != '*' && a[i - 1][j] != '*' && a[i - 1][j + 1] != '*' && a[i - 1][j + 2] != '*';
ok &= a[i][j - 1] != '*' && a[i][j + 2] != '*';
ok &= a[i + 1][j - 1] != '*' && a[i + 1][j + 2] != '*';
ok &= a[i + 2][j] != '*' && a[i + 2][j + 1] != '*' && a[i + 2][j + 2] != '*';
if (!ok) {
cout << "NO\n";
return;
}
st[i][j] = st[i][j + 1] = st[i + 1][j + 1] = true;
}
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
if (a[i][j] == '*' && !st[i][j]) {
cout << "NO\n";
return;
}
}
cout << "YES\n";
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}无脑大模拟，出题太缺德
G. Even-Odd XOR
题意
给定无重复数字的序列的长度 \(n\)，构造该序列，满足奇数位上的所有数的异或值等于偶数位上所有数的异或值。
思路
因为 \(n\) 是 \(2e5\) 级别的，那么我们只需找一个大于 \(2e5\) 的 \(2\) 的次方 \(x\)，然后我们按顺序在前 \(n - 2\) 个数中放入 \(1, 2, 3, \ldots\)，并计算奇数位和偶数位各数的异或值，最后和 \(x\) 取异或后输出两个数即可。
当然，存在 \(n\) 为奇数的情况，不过因为任何数 和 \(0\) 异或值都不变，所以我们在前面塞一个 \(0\) 即可。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define psi pair<string, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
int even = 0, odd = 0;
if(n % 2 == 1 && n > 3){
cout << "0 ";
n --;
}
for(int i=1;i<=n-2;i++){
cout << i << ' ';
if(i % 2 == 0) even ^= i;
else odd ^= i;
}
cout << (262144 ^ even) << ' ' << (262144 ^ odd) << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}有人 wa on 1 好多次，我不说是谁
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Blog - Floating Ocean！
评论