Codeforces Round #693 (Div. 3)
A. Cards for Friends
题意
有一张 的纸。如果一条边是偶数，就可以沿这个方向对半切。问能不能切出至少 张纸。
思路
宽和高每多一个因子 2，能切的份数就翻倍。分别统计出 c1 和 c2，最多就是 份，再和 比较就行。
两个方向都切到奇数以后就不能再切了。题目只要求至少 份，不用考虑怎么恰好凑出 。
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
int t, w, h, n;
int c1, c2;
int main() {
cin >> t;
while(t--) {
cin >> w >> h >> n;
c1 = 0, c2 = 0;
while(!(w & 1)) w >>= 1, c1++;
while(!(h & 1)) h >>= 1, c2++;
// cout << c1 << " " << c1 << endl;
if((1 << c1) * (1 << c2) >= n) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}B. Fair Division
题意
每颗糖的重量是 1 或 2，不能切开，问能不能分成总重量相同的两份。
思路
先数出 1 和 2 各有多少颗，记作 s1、s2。
s1 是奇数，总重量就是奇数，肯定不行。两种糖都是偶数个，分别平分就行。如果 2 是奇数个，就拿两颗 1 去和一颗 2 配平，所以这时还需要 s1 >= 2。
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
int t, a[107], n;
int main() {
cin >> t;
while(t--) {
cin >> n;
int s1 = 0, s2 = 0;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) s1 += (a[i] == 1), s2 += (a[i] == 2);
if((!(s1 & 1) && !(s2 & 1)) || (!(s1 & 1) && (s2 & 1) && s1 >= 2)) {
cout << "YES" << endl;
}
else cout << "NO" << endl;
}
return 0;
}C. Long Jumps
题意
可以从数组里任意一个位置开始。每次拿到 分，再跳到 ，跳出数组结束。问从哪里开始能拿到最多的分。
思路
从一个位置出发以后，后面怎么跳就固定了。s[i] 表示从 出发的总分，直接记忆化：
跳出数组时返回 0。因为 都是正数，只会往右跳，不会绕成环；每个位置算一次，总共 。
已经缓存的位置也不用单独作为起点再算：它是在前面某条路径上算出来的，而那条路径多拿了前面几步的分，总分只会更大。
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int maxn = 2e5 + 17;
int n, t, a[maxn], s[maxn], ans;
int sv(int p) {
if(p > n) return 0;
if(!s[p]) s[p] = a[p] + sv(p + a[p]);
return s[p];
}
int main() {
cin >> t;
while(t--) {
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) s[i] = 0;
ans = 0;
for(int i = 1; i <= n; i++) if(!s[i]) {
ans = max(ans, sv(i));
}
cout << ans << endl;
}
return 0;
}D. Even-Odd Game
题意
Alice 和 Bob 轮流拿走一个数，Alice 先手。Alice 拿偶数才加分，Bob 拿奇数才加分，拿到另一种数也会把它移走。问双方最优时谁赢。
思路
按从大到小的顺序拿就行。大数如果能给自己加分，就直接拿；如果只能给对方加分，拿走它也能阻止对方得分，不能只盯着自己的奇偶性选。
排完序以后交替取数，符合当前这一方的奇偶性就加分，否则跳过。最后比较两边的总分，注意总分用 long long。
时间主要在排序，是 。
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 17;
bool cmp(int x, int y) {
return x > y;
}
int n, a[maxn], t;
ll s[2];
int main() {
cin >> t;
while(t--) {
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + 1 + n, cmp);
s[1] = 0, s[0] = 0;
int c = 0;
for(int i = 1; i <= n; i++) {
if((a[i] & 1) == c) s[c] += 1ll * a[i];
c = 1 - c;
}
if(s[0] > s[1]) puts("Alice");
if(s[0] == s[1]) puts("Tie");
if(s[0] < s[1]) puts("Bob");
}
return 0;
}E. Correct Placement
题意
每个人看作一个矩形，可以旋转 90 度。对每个人，找另一个高和宽都严格更小、能放到他前面的矩形，输出编号，没有就输出 -1。每个人的答案独立计算。
思路
旋转这里不用分两个方向扫。先把每个矩形的两条边排一下，统一让 h 是短边、w 是长边，就只需要同时满足短边更短、长边也更短。
再按短边排序，维护前面矩形里最小的长边。如果这个最小值还比当前长边小，就找到了答案；连它都不够小，其他候选也不行。
同一短边的一组要先全部查询，再更新最小值，不然相等的短边也会被拿来当答案。两个条件都是严格小于，不能只判断其中一条边和 max(h,w) 的关系。
比如 和 ，后者的长边虽然更小，短边却放不进去，不能算答案。
这样还是排序加扫描，时间 ，最后按原编号输出。
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int maxn = 2e5 + 17;
int t, n;
struct frd {
int h, w, id, ans;
} f[maxn];
bool cmp1(frd x, frd y) { return x.h < y.h; }
bool cmp3(frd x, frd y) { return x.id < y.id; }
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> t;
while(t--) {
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> f[i].h >> f[i].w;
if(f[i].h > f[i].w) swap(f[i].h, f[i].w);
f[i].id = i;
f[i].ans = -1;
}
sort(f + 1, f + n + 1, cmp1);
int best = 0;
for(int i = 1, j; i <= n; i = j + 1) {
j = i;
while(j + 1 <= n && f[j + 1].h == f[i].h) j++;
// 先查询整组；best 只来自短边严格更小的组。
for(int k = i; k <= j; k++) {
if(best && f[best].w < f[k].w) f[k].ans = f[best].id;
}
// 查询完才更新，避免相同短边互相当答案。
for(int k = i; k <= j; k++) {
if(!best || f[k].w < f[best].w) best = k;
}
}
sort(f + 1, f + n + 1, cmp3);
for(int i = 1; i <= n; i++) cout << f[i].ans << (i == n ? '\n' : ' ');
}
return 0;
}