Practice.
A. 签到啦~
题意
给定一个序列以及一个整数 \(d\)，输出总和大于等于 \(d\) 的元素的数量的最小值。
思路
排序+枚举。
时间复杂度：\(O(n \log n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
void solve(){
int n, w;
cin >> n >> w;
vector<int> a(n);
for(int i=0;i<n;i++) cin >> a[i];
sort(a.rbegin(), a.rend());
int ans = 0;
for(int i=0;i<n;i++){
ans ++;
w -= a[i];
if(w <= 0) break;
}
cout << ans << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}打卡打卡（其实后面题目也不比这个难多少
B. 熙巨打票
题意
给定两个机器，机器在操作结束后需要 \(a\) 分钟的冷却时间，每个操作需要 \(b\) 分钟。
给定操作的数量，输出完成最后一个操作的时刻。
思路
首先，如果 \(a \leq b\)，那么我们直接无视冷却时间，因为我们轮换着用机器即可。
如果 \(a > b\)，我们可以画图，不难发现，除了前两个操作不需要加时间，接着每两个操作都需要 \(a + b\) 分钟。
当然，考虑到这个，我们需要分奇偶性做，奇数下会多一个操作时间 \(b\)。
时间复杂度：\(O(1)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
void solve(){
int a, b, n;
cin >> a >> b >> n;
if(a <= b) cout << b * n << '\n';
else cout << b * (2 - n % 2) + (a + b) * ((n - 1) / 2) << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}做的时候漏考虑了点（
C. 三元分配
题意
给定三个部门的员工数量，按照下面的要求配对所有的员工，若不能配对输出 \(P\)，否则输出 \(R\)：
单一部门内可配对；
两个部门员工数量之和为质数可配对
思路
首先，如果总和为奇数，那么一定无法将所有员工都配对。
那么，我们来考虑总和为偶数的情况：
全都是偶数，那么一定是可以配对的；
两个奇数，一个偶数，那么很明显，除非奇数的和为 \(2\)，那么我们可以直接把这俩员工配对，否则和一定不是质数。这时，我们就需要用这个唯一的偶数来分配。具体来说，我们只需满足这个唯一的偶数大于等于 \(2\)，那么我们只需分别拿出一个员工和这两个奇数来配对，那么就会剩下三个偶数，此时一定可以分配完。当然，需要满足这个唯一的偶数分别和两个奇数相加的和都是质数。
时间复杂度：\(O(1)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int N = 4e5 + 10;
vector<int> pri;
vector<bool> vis(N), is_pri(N);
void init() {
for(int i=2; i<=4e5; i++) {
if(!vis[i]) pri.emplace_back(i), is_pri[i] = true;
for(int j=0; j<pri.size(); j++) {
if(i * pri[j] > 4e5) break;
vis[i * pri[j]] = true;
if(i % pri[j] == 0) break;
}
}
}
void solve() {
int a, b, c;
cin >> a >> b >> c;
if((a + b + c) % 2 == 1) cout << "P\n";
else if(a % 2 == 0 && b % 2 == 0 && c % 2 == 0) cout << "R\n";
else if((a + b + c) == 2) cout << "R\n";
else if(((a + b) == 2 && c % 2 == 0) || ((a + c) == 2 && b % 2 == 0) || ((b + c) == 2 && a % 2 == 0)) cout << "R\n";
else if((a % 2 == 0 && is_pri[a + b] && is_pri[a + c] && a >= 2) || (b % 2 == 0 && is_pri[b + a] && is_pri[b + c] && b >= 2) || (c % 2 == 0 && is_pri[c + a] && is_pri[c + b] && c >= 2)) cout << "R\n";
else cout << "P\n";
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
init();
int t = 1;
cin >> t;
while(t --) solve();
}过于复杂的分类讨论（
D. "逆"天求和
题意
给定一个质数 \(p\)，输出 \([1, p - 1]\) 内所有数在模 \(p\) 的值位于 \([1, p - 1]\) 内的逆元之和。
思路
很有趣，我们直接打表找规律，发现是个等差数列求和，套公式提交直接就过了（
这边不给出证明，需要费马小定理的逆用。
时间复杂度：\(O(1)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
void solve(){
int n;
cin >> n;
cout << (1 + n - 1) * (n - 1) / 2 << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}确实很逆天
E. 读中国数字
题意
给定一个不超过 \(9999\ 9999\ 9999\) 的数，输出它的中文大写按照题给映射后的结果。
思路
我们按照下面的规则模拟即可：
每 \(4\) 位为一个单元，如果这个单元中出现了两个非 \(0\) 数夹了若干个 \(0\)，那么需要在中间加上 "零"。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
void solve(){
string s;
cin >> s;
while(s.size() % 4 != 0) s = "0" + s;
string ans = "";
string l[3] = {"Y", "W", ""};
bool st1 = false, st0 = false;
for(int level=0;level<s.size()/4;level++){
string p[4] = {"K", "B", "T", ""};
bool f = false;
for(int i=0;i<4;i++){
char now = s[level * 4 + i];
if(st1 && now == '0' && i < 3) st0 = true;
if(now != '0'){
if(st0 && st1){
ans += "0";
st0 = st1 = false;
}
ans += now;
ans += p[i];
f = st1 = true;
}
}
if(f) ans += l[3 - s.size() / 4 + level];
st0 = false;
}
cout << (ans == "" ? "0" : ans) << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}这个零太搞人了（
F. 您有一封新邮件待接收
题意
给定一个有向图，输出位于环中的所有元素，按照升序以及给定的映射输出。
思路
因为数据量很小，我们直接暴力 \(Dfs\)，记录经过 \(100\) 次的节点，并在第 \(101\) 次经过时停止搜索即可。
时间复杂度：\(O(不大)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int N = 4e5 + 10;
vector<int> e[N];
void dfs(int x, vector<int> &vis, set<int> &ans) {
vis[x] ++;
if(vis[x] == 100) ans.emplace(x);
else if(vis[x] > 100) return;
for(auto c : e[x]) dfs(c, vis, ans);
}
void solve() {
int n, m;
cin >> n >> m;
vector<string> s(n);
for(int i=0; i<n; i++) cin >> s[i];
for(int i=1; i<=n; i++) {
int k;
cin >> k;
e[i].clear();
e[i].reserve(k);
while(k --) {
int x;
cin >> x;
e[i].emplace_back(x);
}
}
vector<int> vis(n + 1);
set<int> ans;
dfs(m, vis, ans);
if(ans.empty()) cout << "No one is disturbed!" << '\n';
else {
cout << ans.size() << '\n';
for(auto c : ans) cout << s[c - 1] << ' ';
cout << '\n';
}
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//init();
int t = 1;
cin >> t;
while(t --) solve();
}怎么这么暴力（
H. 我爱XTU
题意
给定一个由 \(X,T,U\) 组成的字符串，输出三个字母数量相同的子串的个数。
思路
我们很容易就想到了前缀和。
那么我们不妨令 \(SX_i, ST_i, SU_i\) 为前 \(i\) 个数中 \(X,T,U\) 出现的个数。
对于区间 \([l, r]\)，需要满足 \(SX_r - SX_{l - 1} = ST_r - ST_{l - 1} = SU_r - SU_{l - 1}\)。
对于左边的等式，化简可得 \(SX_r - ST_r = SX_{l - 1} - ST_{l - 1}\)。
同样的，\(SX_r - SU_r = SX_{l - 1} - SU_{l - 1}\)。
这两个式子同时满足即可。
也就是说，对于二元组 \(<SX_p - ST_p, SX_p - SU_p>\)，我们只需找出有多少个 \(<SX_q - ST_q, SX_q - SU_q>\) 与之相等即可，这里我们可以用到 \(map\)。
当然，对于 \(l - 1 = 0\) 的情况，此时二元组为 \(<0, 0>\)，我们在遍历之前加上这个即可。
时间复杂度：\(O(n \log n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int N = 4e5 + 10;
void solve() {
map<pii, int> cnt;
cnt[{0, 0}] ++;
string s;
cin >> s;
int n = s.size(), ans = 0;
int sx = 0, st = 0, su = 0;
for(int i=0;i<n;i++){
char now = s[i];
if(now == 'X') sx ++;
else if(now == 'T') st ++;
else if(now == 'U') su ++;
pii cur = {sx - st, st - su};
ans += cnt[cur];
cnt[cur] ++;
}
cout << ans << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//init();
int t = 1;
cin >> t;
while(t --) solve();
}有个一摸一样的题：数据结构