A. Sum
两个小数之和是不是大数
#include <bits/stdc++.h>
using namespace std;
void solve(){
int a[3];
cin >> a[0] >> a[1] >> a[2];
sort(a, a + 3);
if(a[0] + a[1] == a[2]) puts("YES");
else puts("NO");
}
int main()
{
freopen("test.in", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int _t = 1;
cin >> _t;
while(_t -- ){
solve();
}
return 0;
}B. Increasing
原数组排完序后，是不是严格单调递增的也就是数组中不能有重复的元素
#include <bits/stdc++.h>
using namespace std;
void solve(){
int a[102], n;
cin >> n;
for(int i = 0; i < n; i ++ ) cin >> a[i];
sort(a, a + n);
int m = unique(a, a + n) - a;
if(m == n) puts("YES");
else puts("NO");
}
int main()
{
freopen("test.in", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int _t = 1;
cin >> _t;
while(_t -- ){
solve();
}
return 0;
}C. Stripes
查看是否有一整行都是R，或者一整列都是B，就输出
#include <bits/stdc++.h>
using namespace std;
void solve(){
char ans;
char g[10][10];
for(int i = 0; i < 8; i ++ )
for(int j = 0; j < 8; j ++ )
cin >> g[i][j];
for(int i = 0; i < 8; i ++ )
{
bool f = true;
for(int j = 0; j < 8; j ++ )
if(g[i][j] != 'R')
f = false;
if(f) ans = 'R';
}
for(int i = 0; i < 8; i ++ )
{
bool f = true;
for(int j = 0; j < 8; j ++ )
if(g[j][i] != 'B')
f = false;
if(f) ans = 'B';
}
cout << ans << endl;
}
int main()
{
freopen("test.in", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int _t = 1;
cin >> _t;
while(_t -- ){
solve();
}
return 0;
}
D. Coprime
找到两个互质的数，使它们的下标之和最大因为2e5个数据，故暴力必然超时
此时发现每个元素最大为1000，故可以预处理所有元素之间是否互质
提前维护每个数的最大下标，如果两个元素互质，就用它们的最大下标之和更新答案
#include <bits/stdc++.h>
using namespace std;
void solve(){
unordered_map<int, int> p;
int ans = -1;
int n;
cin >> n;
for(int i = 1; i <= n; i ++ )
{
int x;
cin >> x;
p[x] = i;
}
for(int i = 1; i <= 1000; i ++ )
for(int j = i; j <= 1000; j ++ )
if(__gcd(i, j) == 1 && p.count(i) && p.count(j))
ans = max(ans, p[i] + p[j]);
cout << ans << endl;
}
int main()
{
freopen("test.in", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int _t = 1;
cin >> _t;
while(_t -- ){
solve();
}
return 0;
}E. Scuza
题意：有很多台阶，如果腿长大于台阶高度，就可以上去，最终问最高可以到多高求最终高度肯定需要前缀和，难度在于怎么找到数组中第一个大于自己数的下标
有2e5个数，暴力循环必定会超时，二分又没有单调性
这时需要进行一个操作
b[i] = max(b[i - 1], a[i]);，开一个b数组，存i之前最大的数，然后对b数组进行二分，找到第一个大于自己数的下标
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
LL a[N], b[N], s[N];
void solve()
{
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
b[i] = max(b[i - 1], a[i]);
s[i] = s[i - 1] + a[i];
}
while (q--)
{
int x;
cin >> x;
int t = upper_bound(b + 1, b + n + 1, x) - b - 1;
cout << s[t] << " ";
}
cout << endl;
}
int main()
{
freopen("test.in", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int _t = 1;
cin >> _t;
while (_t--)
{
solve();
}
return 0;
}F. Smaller
可以发现性质，
- 只要第二个字符串包含不是a的字母，我们就把它排到第一个，而把第一个字符串第一个排成a，这样必定YES.
- 如果第二个字符串没有除a意外的其他字母，而第一个字符串有除a以外的其他字母，则必NO
- 如果两个都没有除a意外的其他字母，则比较两个字符串a的数量，如果第一个小，则YES，否则NO
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n;
cin >> n;
long long cnt1 = 0, cnt2 = 0;
bool st1 = 0, st2 = 0;
while(n -- )
{
int d, k;
string s;
cin >> d >> k >> s;
if(d == 1)
{
for(auto c : s)
if(c != 'a')
st1 = true;
else cnt1 += k;
}
else
{
for(auto c : s)
if(c != 'a')
st2 = true;
else cnt2 += k;
}
if(st2 || (!st1 && cnt1 < cnt2)) puts("YES");
else puts("NO");
}
}
int main()
{
freopen("test.in", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int _t = 1;
cin >> _t;
while(_t -- ){
solve();
}
return 0;
}G. Orray
题意：给定n个数的数组a，定义一个数组b，$b_i = a_1|a_2 |...or|a_i$，现在为了使b数组的字典序最大，应该使a数组怎样排序有关或运算，我们按每一数位来看，
首先最大值肯定放第一个，然后出去第一个已经是1的数位，只看其他数位做比较，找出第二个最大值，以此类推，最后全称为1后就不在改变，按放到顺序也无所谓了
那怎么去掉已经变为1的数位呢，我们设置一个mask，初始为(1 << 30) - 1，每个数位全为1，哪个数位变为1，就把mask相应的数位变为0，做法就是mask ^= maxv，在找除去变为1的数位的最大值时，可以使每个数先与mask在比大小，这样可以去掉已经变为1的数位
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N];
bool st[N];
void solve(){
int n;
cin >> n;
memset(st, 0, sizeof st);
for(int i = 1; i <= n; i ++ ) cin >> a[i];
long long mask = (1 << 30) - 1;
for(int i = 1; i <= n; i ++ )
{
int maxv = 0, k = 0;
for(int j = 1; j <= n; j ++ )
{
int t = a[j] & mask; // 出去已经变为1的数位
if(t > maxv)
{
maxv = t;
k = j;
}
}
if(maxv == 0) // 已经全部变为1了，那剩下的数只要没用过的就随便排
{
for(int j = 1; j <= n; j ++ )
if(!st[j])
cout << a[j] << " ";
cout << "\n";
return;
}
cout << a[k] << " ";
st[k] = true;
mask ^= maxv; // 把已经是1的数位在mask相应位置变为0
}
cout << "\n";
}
int main()
{
freopen("test.in", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int _t = 1;
cin >> _t;
while(_t -- ){
solve();
}
return 0;
}
