Practice.
A. Sum
题意
给定三个数，输出是否可以找出一个数，满足其为另外两个数的和。
思路
如题。
时间复杂度：\(O(1)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
void solve(){
int a, b, c;
cin >> a >> b >> c;
cout << (a + b == c || a + c == b || b + c == a ? "YES\n" : "NO\n");
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t --) solve();
}如题
B. Increasing
题意
给定一个序列，满足是否可以重新排列序列，使序列严格单调递增。
思路
没有重复元素即可。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
void solve(){
int n;
cin >> n;
map<int, bool> mp;
bool f = true;
for(int i=0;i<n;i++){
int cur;
cin >> cur;
if(mp[cur]) {
f = false;
}
mp[cur] = true;
}
cout << (f ? "YES\n" : "NO\n");
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t --) solve();
}说那么复杂干嘛（
C. Stripes
题意
给定一个 \(8 \times 8\) 的矩阵，定义操作为将某一行全部涂成红色，或将某一列全部涂成蓝色，后面的颜色会覆盖前面的颜色。给定任意次操作后的矩阵，输出最后涂上的是什么颜色。
思路
首先，既然存在覆盖，那么被覆盖的某行或某列一定不是在最后操作的。
那么，我们可以找出全为红色的行，或者全为蓝色的列，若能找到就为答案。不然，一定存在覆盖。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
void solve(){
vector<string> s(8);
for(int i=0;i<8;i++) cin >> s[i];
bool f = false;
for(int i=0;i<8;i++){
bool now = true;
for(int j=0;j<8;j++){
if(s[i][j] == 'B') now = false;
}
if(now){
f = true;
cout << "R\n";
break;
}
}
if(!f) for(int j=0;j<8;j++){
bool now = true;
for(int i=0;i<8;i++){
if(s[i][j] == 'R') now = false;
}
if(now){
f = true;
cout << "B\n";
break;
}
}
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t --) solve();
}略微有点小思维
D. Coprime
题意
给定一个序列 \(a\)，找出 \(i, j, i \neq j\)，满足 \(a_i, a_j\) 互质。输出满足条件的 \(i + j\) 的最大值。
思路
虽然整体数据量很大，但是需要留意的是 \(a_i \leq 1000\)。
因而，我们不妨记录出现过的数对应的下标最大值。然后，我们直接对 \(1000\) 中出现过的数字遍历，统计出最大值即可。
时间复杂度：\(O(1000 ^ 2 \log x)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
int gcd(int a, int b){
return a == 0 ? b : gcd(b % a, a);
}
void solve(){
int n;
cin >> n;
vector<int> a(1001);
for(int i=1;i<=n;i++){
int cur;
cin >> cur;
a[cur] = max(a[cur], i);
}
int ans = -1;
for(int i=1;i<=1000;i++)
for(int j=i;j<=1000;j++){
if(gcd(i, j) == 1 && a[i] > 0 && a[j] > 0) ans = max(ans, a[i] + a[j]);
}
cout << ans << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t --) solve();
}来绕一个弯（（
E. Scuza
题意
给定一个上升台阶的所有相邻两层的高度差，对于 \(q\) 个询问给定的腿长 \(k_i\)，输出能登上的台阶距离地面的最大高度。
思路
首先，台阶上升，所以台阶距离地面的高度具有单调性。
那么，二分不就好了么。
时间复杂度：\(O(n \log n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int inf = 0x3f3f3f3f3f3f3f3f;
void solve(){
int n, q;
cin >> n >> q;
vector<int> a(n + 1), s(n + 2);
for(int i=1;i<=n;i++){
cin >> a[i];
a[i] += a[i - 1];
s[i] = max(s[i - 1], a[i] - a[i - 1]);
}
s[n + 1] = inf;
while(q--){
int x;
cin >> x;
cout << a[upper_bound(s.begin(), s.end(), x) - s.begin() - 1] << ' ';
}
cout << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t --) solve();
}考虑到lower_bound找不到会指向最后一个点，那么我们不妨在最后插一个无穷大
F. Smaller
题意
给定两个初始均为 \('a'\) 的字符串 \(s, t\)，定义操作为下面两种任选一：
\(1\ k\ x\)，在 \(s\) 后面循环拼接上 \(k\) 个 \(x\)；
\(2\ k\ x\)，在 \(t\) 后面循环拼接上 \(k\) 个 \(x\)。
对于每次操作，输出是否可以重新排列两个字符串，使 \(s\) 的字典序小于 \(t\)。
思路
我们不妨直接考虑怎么样才能让字典序较小：
既然可以重新排序，而且一开始两个字符串是一样的，且只有一种字母，那么，只要 \(t\) 中出现了不是 \(a\) 的字符，我们直接把他放到第一个，而 \(s\) 的第一个直接放上 \(a\)，就一定可以满足 \(s < t\)；
但是，若没有非 \(a\) 字符，我们就只能统计有多少个 \(a\)，个数少的字典序自然小。
那么，我们只要按照上述思路，统计 \(s, t\) 中是否出现了非 \(a\) 字符，以及 \(a\) 出现的次数即可。
最后，若 \(s\) 出现了非 \(a\) 字符而 \(t\) 中没有出现，或者都没出现但 \(s\) 的 \(a\) 数量更多，那么输出 \(NO\)，否则为 \(YES\)。
时间复杂度：\(O(nm)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int N = 1e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;
void init(){}
void solve() {
int cnt1 = 1, cnt2 = 1;
bool h1 = false, h2 = false;
int q;
cin >> q;
while(q --){
int d, k;
cin >> d >> k;
string s;
cin >> s;
for(char e : s){
if(d == 1){
if(e == 'a') cnt1 += k;
else h1 = true;
}
if(d == 2){
if(e == 'a') cnt2 += k;
else h2 = true;
}
}
cout << ((!h1 && !h2 && cnt1 >= cnt2) || (h1 && !h2) ? "NO\n" : "YES\n");
}
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
init();
int t;
cin >> t;
while (t --) solve();
}略微绕了一下（
G. Orray
题意
给定一个序列 \(a\)，定义 \(b_i\) 为 \(a\) 前 \(i\) 个数按位或的值。将序列重新排序，满足 \(b\) 的字典序最大。输出任意一种满足条件的方案。
思路
首先，按位或一定是越或越大的，因而我们一定会把最大的数放在第一个。
接着，要让下个数尽可能大，我们当然希望找到一个数，对于当前的数的最高位 \(0\)，这个数的该位为 \(1\)。
我们可能找不到这个数，但是有趣的是，既然数据范围为 \(1e9\)，那么我们一定可以找出 \(32\) 个以内的数，让按位或的值递增。
因而，我们不妨直接遍历 \(32\) 次，找出剩下的让按位或的结果最大的数，输出该数即可。
而，当我们拿不出数字使按位或的结果变大时，就结束了。剩余的数随便输出即可。
时间复杂度：\(O(32 n^2)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int N = 1e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353;
void init(){}
void solve() {
int n;
cin >> n;
vector<int> a(n);
for(int i=0;i<n;i++) cin >> a[i];
vector<int> ans;
vector<bool> vis(n);
int tot = 0;
for(int i=31; i>=0;i--){
int idx = -1, now = 0;
for(int j=0;j<n;j++){
if(vis[j]) continue;
if((tot | a[j]) > now){
now = tot | a[j];
idx = j;
}
}
if(idx == -1) break;
vis[idx] = true;
ans.emplace_back(a[idx]);
tot |= a[idx];
}
for(auto e : ans) cout << e << ' ';
for(int i=0;i<n;i++) if(!vis[i]) cout << a[i] << ' ';
cout << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
init();
int t;
cin >> t;
while (t --) solve();
}想不到就绕死了（