题目链接：Codeforces Round 920 (Div. 3)
PS：很长时间没写题，状态不好，写的很差
A. Square
题意：给出正方形四个点的坐标，求面积
解题思路：签到
查看代码 void solve(){
vector<PII> v;
for(int i = 1; i <= 4; i ++){
int x, y;
cin >> x >> y;
v.push_back({x, y});
}
sort(v.begin(), v.end());
auto a = v[0], b = v[3];
int ans = (b.first - a.first) * (b.second - a.second);
cout << ans << '\n';
}
B. Arranging Cats
题意：给定两个长度为 n 的字符串s, t，1 表示该位置有猫，0 表示没有猫，s是初始状态，t是目标状态，你可以选择三种操作：放入，拿出，移动，求最小操作次数
解题思路：分类讨论贪心，记初始状态猫数量sum1，目标状态猫数量sum2
1：sum1 == sum2 统计不同的位置数量res, ans = res / 2;
2：sum1 < sum2 先统计s[i] == '1' && t[i] == '0'数量res，先移动补满，再加上差值；
3：sum1 >= sum2 先统计t[i] == '1' && s[i] == '0'数量res，先移动补满，再加上差值。
查看代码 void solve(){
int n;
string s, t;
cin >> n >> s >> t;
if(s == t){
cout << 0 << '\n';
}
else{
int sum1 = 0, sum2 = 0;
for(auto si : s){
if(si == '1') sum1 ++;
}
for(auto ti : t){
if(ti == '1') sum2 ++;
}
int ans = 0;
if(sum1 == sum2){
int sum = 0;
for(int i = 0; i < s.size(); i ++){
if(s[i] != t[i]) sum ++;
}
ans = sum / 2;
}
else if(sum1 < sum2){
int sum = 0;
for(int i = 0; i < s.size(); i ++){
if(s[i] == '1' && t[i] == '0') sum ++;
}
ans = sum + (sum2 - sum1);
}
else{
int sum = 0;
for(int i = 0; i < s.size(); i ++){
if(t[i] == '1' && s[i] == '0') sum ++;
}
ans = sum + (sum1 - sum2);
}
cout << ans << '\n';
}
}
C. Sending Messages
题意：手机电量初始f， 每分钟消耗a，每次开机消耗b，需要在n个时间发送消息，初始开机，能不能发送所有消息
解题思路：求每次发信时间与前一次发信时间的差，如果不关机消耗的时间小于b那就从上一次直接不关机等到当前时间发消息，否则关机等到当前时间点再开机
查看代码 void solve(){
int n, f, a, b;
cin >> n >> f >> a >> b;
vector<int> m(n + 1);
for(int i = 1; i <= n; i ++){
cin >> m[i];
}
int sum = 0;
for(int i = 1; i <= n; i ++){
if((m[i] - m[i - 1]) * a >= b){
sum += b;
}
else{
sum += (m[i] - m[i - 1]) * a;
}
}
if(sum >= f) cout << "NO\n";
else cout << "YES\n";
}
D. Very Different Array
题意：给两个数组，每次选两个元素，并求差值绝对值，然后求最大差值绝对值之和
解题思路：先对数组排序，肯定优先从端点选择，取以下两种情况的最大值双指针实现一下即可
1：数组a的左端点和数组b的右端点差值绝对值 大于 数组a的右端点和数组b的左端点的差值绝对值；
2：反过来
查看代码 void solve(){
int n, m;
cin >> n >> m;
vector<int> a(n + 1), b(m + 1);
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 1; i <= m; i ++) cin >> b[i];
sort(a.begin() + 1, a.end());
sort(b.begin() + 1, b.end());
int ans = 0;
int l1 = 1, r1 = n;
int l2 = 1, r2 = m;
while(l1 <= r1){
if(abs(b[r2] - a[l1]) >= abs(a[r1] - b[l2])){
ans += abs(b[r2] - a[l1]);
r2 --, l1 ++;
}
else{
ans += abs(a[r1] - b[l2]);
r1 --, l2 ++;
}
}
cout << ans << '\n';
}
E. Eat the Chip
题意：两者下棋，Alice可以往左下，下，右下走，Bob可以往左上，上，右上走，Alice先手，如果一者通过移动把另外一方的棋子吃掉，直接获胜，如果两者都无法吃掉对面则·平局，两者都取最优策略，求获胜情况
解题思路：vp时想了很多分类讨论，但是都没弄明白。
1：首先，看两者x轴差值xc = xb-xa，如果是奇数，只有可能是Alice获胜或者平局，否则是Bob获胜或者平局
2：然后求出两者在迈出决胜一步之前的活动范围la, ra, lb, ra, 如果la <= lb + 1 && ra >= rb - 1就是攻击者胜利
如图如果差太多就没法攻击到，就算平局
查看代码 void solve(){
int h, w, xa, ya, xb, yb;
cin >> h >> w >> xa >> ya >> xb >> yb;
if(xa >= xb){
cout << "Draw\n";
return;
}
int xc = xb - xa;
if(xc & 1){
int la = max(ya - xc / 2, 1ll), ra = min(ya + xc / 2, w);
int lb = max(yb - xc / 2, 1ll), rb = min(yb + xc / 2, w);
if(la <= lb + 1 && ra >= rb - 1) cout << "Alice\n";
else cout << "Draw\n";
}//上追下
else{
int la = max(ya - xc / 2, 1ll), ra = min(ya + xc / 2, w);
int lb = max(yb - (xc - 1) / 2, 1ll), rb = min(yb + (xc - 1) / 2, w);
if(lb <= la + 1 && rb >= ra - 1) cout << "Bob\n";
else cout << "Draw\n";
}//下追上
}
F. Sum of Progression
题意：给定一个长度为n的数组，有q组查询，每次三个输入s,d,k，查询从s开始的k个数，分别是1 * a[s],2 * a[s + d],3 * a[s + d * 2]+......+k * a[s + (k - 1) * d]
解题思路：根号分治，没遇见过的类型，感觉是一种很巧的暴力？
如果d大于sqrt(n)，那就用暴力枚举求解，否则的话用预处理的方式来求解，s1[d][i]存储的是以 d 为间隔的到i的加上对应乘积的前缀和，s2[d][i]存储的是以 d 为间隔的到i的前缀和
假设一组查询是s，d，k，那么对应的答案就是 s1[d][s + (k - 1) * d] - s1[d][max(0ll, s - d)] - (s1[d][s + (k - 1) * d] - s1[d][max(0ll, s - d)]) * ((s + d - 1) / d - 1)，也就是剪掉多出的部分
int n, q;
void solve(){
cin >> n >> q;
vector<int> a(n + 1);
for(int i = 1; i <= n; i ++) cin >> a[i];
int B = 300;
vector<vector<int> > s1(B + 1, vector<int>(n + 1, 0));
vector<vector<int> > s2(B + 1, vector<int>(n + 1, 0));
for(int d = 1; d < B; d ++){
for(int i = 1; i <= n; i ++){
s1[d][i] = (i + d - 1) / d * a[i];
s2[d][i] = a[i];
if(i >= d){
s1[d][i] += s1[d][i - d];
s2[d][i] += s2[d][i - d];
}
}
}
while(q --){
int s, d, k;
cin >> s >> d >> k;
if(d >= B){
int ans = 0;
for(int i = 1; i <= k; i ++){
ans += a[s + (i - 1) * d] * i;
}
cout << ans << ' ';
}
else{
int l = s, r = s + (k - 1) * d;
int ans = s1[d][r] - s1[d][max(0ll, l - d)] - ((s + d - 1) / d - 1) * (s2[d][r] - s2[d][max(0ll, l - d)]);
cout << ans << ' ';
}
}
cout << '\n';
}