A. Plus or Minus
#include <bits/stdc++.h>
using namespace std;
int32_t main() {
ios::sync_with_stdio(false) , cin.tie(nullptr) , cout.tie(nullptr);
int t;
cin >> t;
while( t-- )
{
int a, b, c;
cin >> a >> b >> c;
if (a + b == c) cout << "+\n";
else cout << "-\n";
}
return 0;
}
B. Grab the Candies
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n;
cin >> n;
int a = 0 , b = 0;
for( int x ; n ; n -- ){
cin >> x;
if( x & 1 ) b += x;
else a += x;
}
if( a > b ) cout << "YES\n";
else cout << "NO\n";
}
int32_t main() {
ios::sync_with_stdio(false) , cin.tie(nullptr) , cout.tie(nullptr);
int t; cin >> t;
while( t -- )
solve();
return 0;
}
C. Find and Replace
把奇数位置的字符放入一个集合，把偶数位置的字符放入另一个集合，然后判断两个集合是否相交
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
string s;
cin >> n >> s;
set<char> st;
for (int i = 0; i < n; i += 2)
st.insert(s[i]);
for (int i = 1; i < n; i += 2) {
if (st.find(s[i]) != st.end()) {
cout << "NO\n";
return;
}
}
cout << "YES\n";
}
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t;
cin >> t;
while (t--) solve();
return 0;
}
D. Odd Queries
前缀和
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
int n , q ;
cin >> n >> q;
vector<int> a(n+1);
for( int i = 1 ; i <= n ; i ++ ) cin >> a[i];
for( int i = 1 ; i <= n ; i ++ ) a[i] += a[i-1];
for( int l , r , k , t; q ; q -- ){
cin >> l >> r >> k;
t = a[n] - a[r] + a[l-1] + ( l + r - 1 ) * k;
if( t & 1 ) cout << "YES\n";
else cout << "NO\n";
}
}
int32_t main() {
ios::sync_with_stdio(false) , cin.tie(nullptr) , cout.tie(nullptr);
int t;
cin >> t;
while( t -- )
solve();
return 0;
}
E. Interview
这题其实不算难，就是交互题，二分判断一下就好。
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n, q;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i], a[i] += a[i - 1];
int l = 1 , r = n , mid , res , t;
while( l <= r ){
mid = ( l + r ) >> 1;
cout << "? " << ( mid - l + 1 ) << " ";
for( int i = l ; i <= mid ; i ++ ) cout << i << " ";
cout << endl;
cin >> t;
if( t == a[mid] - a[l-1] ) l = mid + 1;
else r = mid - 1 , res = mid;
}
cout << "! " << res<< endl;
return ;
}
int32_t main() {
int t;
cin >> t;
while (t--)
solve();
return 0;
}
F. Bouncy Ball
同时维护点的坐标和方向向量，如果横坐标到边界就反向vx，如果纵坐标到边界就反向vy。
然后每次都计算出在当前方向上最多可以移动多远不用改变方向，然后一步移动过去。注意在移动前要判断目标点是否在移动的路径上。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int read() {
int x = 0, f = 1, ch = getchar();
while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
if (ch == '-') f = -1, ch = getchar();
while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
return x * f;
}
void solve() {
int n = read(), m = read(), sx = read(), sy = read(), tx = read(), ty = read();
string s;
cin >> s;
int vx, vy, cnt = 0, f, p, q, dx, dy;
if (s[0] == 'D') vx = 1;
else vx = -1;
if (s[1] == 'R') vy = 1;
else vy = -1;
set<tuple<int, int, int, int> > st;
while (sx != tx || sy != ty) {
if (st.count(make_tuple(sx, sy, vx, vy)) != 0) {
cout << "-1\n";
return;
}
st.emplace(sx, sy, vx, vy);
f = 0;
if (sx == 1 && vx == -1) vx = 1, f = 1;
if (sx == n && vx == 1) vx = -1, f = 1;
if (sy == 1 && vy == -1) vy = 1, f = 1;
if (sy == m && vy == 1) vy = -1, f = 1;
if (vx == 1) p = n - sx;
else p = sx - 1;
if (vy == 1) q = m - sy;
else q = sy - 1;
p = min(p, q);
cnt += f;
dx = vx * abs(sx - tx), dy = vy * abs(sy - ty);
if ( abs(dx) == abs(dy) && tx - sx == dx && ty - sy == dy) break;
sx += vx * p, sy += vy * p;
}
printf("%lld\n", cnt);
}
int32_t main() {
int t = read();
while (t--)
solve();
return 0;
}
G. Subsequence Addition
G1,G2其实我只写了一遍。简单来说就是把数组排序，然后判断每一个数是否小于他的前缀之和。注意特判第一个数是不是 1。证明没有，但是我暴力推了长度为 5 的所有情况，发现是复合的。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int read() {
int x = 0, f = 1, ch = getchar();
while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
if (ch == '-') f = -1, ch = getchar();
while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
return x * f;
}
void solve() {
int n = read();
vector<int> c(n);
for (auto &i: c) i = read();
sort(c.begin(), c.end());
if (c[0] != 1) {
cout << "NO\n";
return;
}
for( int i = 1 , sum = 1 ; i < n ; i ++ ){
if( c[i] > sum ){
cout << "NO\n";
return;
}
sum += c[i];
}
cout << "YES\n";
return;
}
int32_t main() {
int t = read();
while (t--)
solve();
return 0;
}