Practice.
A. Job Interview
题意
给定一个由 \(o, -, x\) 构成的字符串，判断字符串是否至少含有一个 \(o\)，且不包含 \(x\)。
思路
如题。
时间复杂度：\(O(1)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;
void init(){}
void solve() {
int n;
cin >> n;
string s;
cin >> s;
bool ans1 = false, ans2 = false;
for(char e : s){
if(e == 'o') ans1 = true;
if(e == 'x') ans2 = true;
}
cout << (ans1 && !ans2 ? "Yes\n" : "No\n");
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
init();
int t = 1;
//cin >> t;
while(t --) solve();
}打卡打卡
B. Coloring Matrix
题意
给定两个 \(n \times n\) 的矩阵 \(A, B\)，定义操作为将当前矩阵顺时针旋转 \(90°\)。输出对 \(A\) 进行任意次操作后，是否存在一种情况，使得对于所有 \(A_{i, j} = 1\)，满足 \(B_{i, j} = 1\)。
思路
如题，模拟即可。
时间复杂度：\(O(4n^2)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;
void init(){}
void solve() {
int n;
cin >> n;
vector<vector<int>> a(n ,vector<int>(n)), b(n ,vector<int>(n));
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin >> a[i][j];
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin >> b[i][j];
bool ans = true;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
if(a[i][j] == 1 && b[i][j] == 0) ans = false;
}
if(ans) {
cout << "Yes\n";
return;
}
ans = true;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
if(a[j][n - i - 1] == 1 && b[i][j] == 0) ans = false;
}
if(ans) {
cout << "Yes\n";
return;
}
ans = true;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
if(a[n - i - 1][n - j - 1] == 1 && b[i][j] == 0) ans = false;
}
if(ans) {
cout << "Yes\n";
return;
}
ans = true;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
if(a[n - j - 1][i] == 1 && b[i][j] == 0) ans = false;
}
if(ans) {
cout << "Yes\n";
return;
}
cout << "No\n";
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
init();
int t = 1;
//cin >> t;
while(t --) solve();
}复制粘贴.jpg
C. Cards Query Problem
题意
给定 \(q\) 个询问，询问为下面三者任选一：
\(1\ i\ j\)，将 \(i\) 写到一张空白的卡牌上并将其塞到 \(j\) 盒子；
\(2\ i\)，升序输出 \(i\) 盒子内所有卡牌的数字；
\(3\ i\)，升序输出所有包含数字 \(i\) 的盒子编号，不可以重复；
按照上述条件执行对应操作。
思路
直接模拟即可。
其中，盒子可使用 \(multiset\)，卡牌可使用 \(set\)。
注意对应关系。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;
void init(){}
void solve() {
int n, q;
cin >> n >> q;
map<int, multiset<int>> box;
map<int, set<int>> card;
while(q --){
int tp;
cin >> tp;
if(tp == 1){
int i, j;
cin >> i >> j;
card[i].emplace(j);
box[j].emplace(i);
}else if(tp == 2){
int i;
cin >> i;
for(auto e : box[i]) cout << e << ' ';
cout << '\n';
}else if(tp == 3){
int i;
cin >> i;
for(auto e : card[i]) cout << e << ' ';
cout << '\n';
}
}
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
init();
int t = 1;
//cin >> t;
while(t --) solve();
}别绕晕即可
D. Writing a Numeral
题意
给定一个字符串 \(S\)，初始状态下 \(S\) 为 \(1\)。
现在，给定 \(q\) 个询问，询问为下面三者任选一：
\(1\ x\)，将 \(x\) 拼接到 \(S\) 的最后；
\(2\)，删除 \(S\) 开头的数字；
\(3\)，输出 \(S\) 转换为数字并\(\mod 998244353\) 后的值；
按照上述条件执行对应操作。
思路
我们可以用队列来维护 \(S\) 序列，以此记录开头的数字到底是什么。
这样，我们就可以直接模拟寻问 \(1\) 对应的操作。
而对于询问 \(2\)，我们直接减掉对应的值即可。其中，位数就是队列的长度 \(-1\)，我们可以用快速幂求出 \(10 ^ t\)。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;
void init(){}
int qp(int a, int b){
int ans = 1;
while(b > 0){
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
void solve() {
int q;
cin >> q;
int ans = 1;
queue<int> nums;
nums.emplace(1);
while(q --){
int t;
cin >> t;
if(t == 1){
int x;
cin >> x;
nums.emplace(x);
ans = (ans * 10 % mod + x) % mod;
}else if(t == 2){
ans = (ans + mod - nums.front() * qp(10, nums.size() - 1) % mod) % mod;
nums.pop();
}else if(t == 3){
cout << ans << '\n';
}
}
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
init();
int t = 1;
//cin >> t;
while(t --) solve();
}这怎么可以用 \(java\) 的大数爆算啊，对吧（x
E. Unfair Sugoroku
待补充
F. Rook Score
题意
给定一个无限大的矩阵以及其中的 \(n\) 个点的值，除此之外，其余点的值全是 \(0\)。对于一个点 \((R, C)\)，对应的总和为 \(sumR_R + sumC_C - val_{R, C}\)，即这个点所在的行和列的元素总和（交点只被计算一次）。找出一个点，满足总和最大，并输出最大总和。
思路
首先，我们固定 \(C\)，那么我们只需找出最大的 \(sumR\) 即可。
如果行和列的交点的元素值为 \(0\)，那么我们就能保证这个总和一定是最大的，因为其他的总和不减掉交点也一定比他小。
然而，如果不为 \(0\)，那么我们需要减掉交点，这时，我们得到的答案并非就是最大的，我们需要继续枚举次大值。
如上，我们循环枚举，直到交点值为 \(0\) 或者枚举完即可。
有趣的是，我们按照上述操作，再枚举 \(C\) 即可，复杂度是可行的。
时间复杂度：\(O(np)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;
void init(){}
void solve() {
int n;
cin >> n;
map<pii, int> v;
map<int, int> mc, mr;
for(int i=0;i<n;i++){
int R, C, X;
cin >> R >> C >> X;
v[{R, C}] = X;
mr[R] += X;
mc[C] += X;
}
vector<pii> vr;
vr.reserve(mr.size()); //有意思的函数（不是reverse捏
for(auto r : mr) vr.emplace_back(r.second, r.first);
sort(vr.rbegin(), vr.rend());
int ans = 0;
for(auto C : mc){
int c = C.fs, sum = C.sc;
for(auto R : vr){
ans = max(ans, sum + R.fs - v[{R.sc, c}]);
if(v[{R.sc, c}] == 0) break;
}
}
cout << ans << '\n';
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
init();
int t = 1;
//cin >> t;
while(t --) solve();
}就离谱