Codeforces Round 920 (Div. 3)(a~f)

A. Square

给出正方形的四个顶点，求面积。

通过正方形对边斜率相同找出相邻的两点求其距离的平方。

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<stack>
using namespace std;
const int N = 1000010;
typedef long long ll;
const ll mod = 998244353;
ll t = 1;
int main() {
    cin >> t;
    while (t--) {
        int x1, y1, x2, y2, x3, y3, x4, y4;
        cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
        if ((y2 - y1) * (x4 - x3) == (y4 - y3) * (x2 - x1)) {
            cout << (y2 - y1) * (y2 - y1) + (x2 - x1) * (x2 - x1) << endl;
        }
        else if ((y2 - y3) * (x4 - x1) == (y4 - y1) * (x2 - x3)) {
            cout << (y2 - y3) * (y2 - y3) + (x2 - x3) * (x2 - x3) << endl;
        }
        else if ((y2 - y4) * (x1 - x3) == (y1 - y3) * (x2 - x4)) {
            cout << (y2 - y4) * (y2 - y4) + (x2 - x4) * (x2 - x4) << endl;
        }
    }
    return 0;
}

B. Arranging Cats

给出长度为n的两个01字符串，可以对串一进行三种操作：01互换，0变成1，1变成0。求把串一转换成串二的最小步骤。

求出串一为0串二为1的数量a1和串一为1串二为0的数量a2，最小步骤为进行01互换直到a1或者a2等于0，再继续单个变换，答案为max(a1,a2)。

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<stack>
using namespace std;
const int N = 1000010;
typedef long long ll;
const ll mod = 998244353;
ll t = 1;
int main() {
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        string s1, s2;
        cin >> s1 >> s2;
        int a1 = 0, a2 = 0, a3 = 0, a4 = 0;
        for (int i = 0; i < n; i++) {
            if (s1[i] == '1' && s2[i] == '0') {
                a1++;
            }
            if (s1[i] == '0' && s2[i] == '1') {
                a2++;
            }
        }
        cout << max(a1, a2) << endl;
    }
    return 0;
}

C. Sending Messages

给出长度为n的递增时间序列（m1、m2、、mn），问电量为f的手机是否能在这些时间发信息，开机没单位时间消耗a电量，关机消耗b电量并可以在任意时间打开。

遍历时间，求两时间的间隔开机和关机消耗电量最小的加到答案上，最后和f比对能否发完。

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<stack>
using namespace std;
const int N = 1000010;
typedef long long ll;
const ll mod = 998244353;
ll t = 1;
ll m[N];
int main() {
    cin >> t;
    while (t--) {
        ll n,f,a,b;
        cin >> n >> f >> a >> b;
        for (int i = 1; i <= n; i++)
            cin >> m[i];
        for (int i = 1; i <= n; i++) {
            ll x = m[i] - m[i - 1];
            f -= min(x * a, b);
            if (f <= 0) {
                cout << "NO" << endl;
                break;
            }
        }
        if (f > 0)cout << "YES" << endl;
    }
    return 0;
}

D. Very Different Array

给出长度为n的数组a和长度为m的数组b，从b中取n个元素形成数组c，求当i从1到n的最大|a(i)-c(i)|的和。

将a和c从小到大排序，c中小于a最小元素的那部分和a右半边差值比左半边大，大于a最大元素的那部分则是与左半边的差值大，中间的则是和a当前最大最小元素差值最大，所以从b中优先选最大值和最小值。将a，b排序，通过双指针对比a最大b最小元素差值和a最小b最大元素差值，将差值大的加入答案并去除a，b中的对应元素，直到取了n个元素。

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<stack>
using namespace std;
const int N = 1000010;
typedef long long ll;
const ll mod = 998244353;
ll t = 1;
ll m[N];
int main() {
    cin >> t;
    while (t--) {
        ll sum = 0;
        ll n, m;
        cin >> n >> m;
        vector<ll> a, b;
        for (ll i = 0; i < n; i++) {
            ll a1;
            cin >> a1;
            a.push_back(a1);
        }
        for (ll i = 0; i < m; i++) {
            ll b1;
            cin >> b1;
            b.push_back(b1);
        }
        sort(a.begin(), a.end());
        sort(b.begin(), b.end());
        ll i1 = 0, j1 = n - 1;
        ll i2 = 0, j2 = m - 1;
        while (i1 <= j1) {
            ll x1 = fabs(a[j1] - b[i2]);
            ll x2 = fabs(b[j2] - a[i1]);
            if (x1 > x2) {
                sum += x1;
                j1--;
                i2++;
            }
            else {
                sum += x2;
                j2--;
                i1++;
            }
        }
        cout << sum << endl;
    }
    return 0;
}

E. Eat the Chip

给出h行w列的图，已知两点坐标，其中一点x1只能向左下、下、右下移动，另外一点x2只能向左上、上、右上移动，当其中一点走到另外一点当前的位置时该点胜利，若无法走到则平局，x1先动，求结局。

首先x1与x2同行或x1在x2下面平局，易知两点间行距离为偶数时只能x1获胜或平局，奇数则只能x2获胜或平局(只有一列时更直观)。当行距离为偶数时，x1一定朝x2的方向移动，x2朝远离x1的方向移动（反之亦然），当x1和x2的列距离小于等于1时x1一定能获胜（x1先走，后续只要不断靠近列距离是不会增加的），列距离大于1则要分三种情况，x2走到列边界的时间大于x1和x2走到同行的时间则平局，若x1走到列边界的时间小于x1x2同行的时间则x1获胜，否则平局。

由于x1和x2的相对位置不同要走的方向不同，每个都列举很麻烦，可以通过变换相对边距离达成x1一定在x2左边或者正上方，若行距离为奇数可以让x1先走一步，然后互换x1和x2的相对图的位置变成行距离为偶数的情况并把答案换成x2就可以了。

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<stack>
using namespace std;
const int N = 1000010;
typedef long long ll;
const ll mod = 998244353;
ll t = 1;
ll m[N];
int main() {
    cin >> t;
    while (t--) {
        ll h, w, xa, xb, ya, yb;
        cin >> h >> w >> xa >> ya >> xb >> yb;
        ll d1 = xb - xa - 1, d2 = yb - ya ;
        if (xb <= xa)cout << "Draw" << endl;
        else{
            if (d1 % 2 == 0) {
                if (ya > yb) {
                    ya = w - ya + 1;
                    yb = w - yb + 1;
                }
                ll e1 = w - ya, e2 = w - yb;
                ll d = d1 / 2;
                if (yb - ya <= 1) {
                    cout << "Alice" << endl;
                }
                else {
                    if (yb + d <= w)cout << "Draw" << endl;
                    else if (d + ya + 1 >= w)cout << "Alice" << endl;
                    else cout << "Draw" << endl;
                }
            }
            else {
                ll xx = xa, xy = ya;
                xa = h - xb + 1, ya = w - yb + 1;
                xb = h - xx + 1, yb = w - xy + 1;
                if (ya > yb) {
                    ya = w - ya + 1;
                    yb = w - yb + 1;
                }
                xb--;
                if (yb != w)yb++;
                ll e1 = w - ya, e2 = w - yb;
                ll d = d1 / 2;
                if (yb - ya <= 1) {
                    cout << "Bob" << endl;
                }
                else {
                    if (yb + d <= w)cout << "Draw" << endl;
                    else if (d + ya + 1 >= w)cout << "Bob" << endl;
                    else cout << "Draw" << endl;
                }
            }
        }
    }
    return 0;
}

F. Sum of Progression

给出长度为n的数列a，有q次询问，每次给三个数s、d、k，求a(s)+a(s+d)+...+a(s+d*(k-1))*k。

根号分治，当d大于sqrt(n)时直接求，时间复杂度为O(nsqrt(n))，d小于sqrt(n)的预处理。将题目的加法以图片中展示的形式分开，可以看到当我们要求S=s+d，D=d，K=k-1时只需要用总的减去图片中两横线间的就可以了，其中也能分成左边和右边，左边就是当S1=s，D1=d，K1=2时的答案，右边是前缀和乘数量。我们就可以存下d小于sqrt（n）时数组每个位置加d的前缀和和题目中加法的前缀和。

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<stack>
using namespace std;
const int N = 100010;
typedef long long ll;
const ll mod = 998244353;
ll t = 1;
ll a[N];
ll s[N], d[N], k[N];
ll S[330][N], S1[330][N];
int main() {
    cin >> t;
    while (t--) {
        ll n, q;
        cin >> n >> q;
        for (int i = 1; i <= n; i++) {
            scanf_s("%lld", &a[i]);
        }
        int sn = sqrt(n);
        for (int i = 1; i <= sn; i++) {
            for (int j = 1; j <= n; j++) {
                if(j>=i){
                    S[i][j] = S[i][j - i] + a[j];
                    S1[i][j] = S1[i][j - i] + a[j] * (j / i);
                }
                else {
                    S[i][j] = a[j];
                    S1[i][j] = a[j] * (j / i);
                }
            }
        }
 
        for (ll i = 0; i < q; i++) {
            ll s, d, k;
            cin >> s >> d >> k;
            if (d <= sn) {
                ll x = s + d * (k - 1);
                printf("%lld ", S1[d][x] - S1[d][s]+a[s] * (s / d) -(S[d][x]-S[d][s]+a[s]) * (s / d - 1));
            }//不减S1[d][s-d]时防止出现负数，这样方便一点。
            else {
                ll sum = 0;
                for (ll j = 0; j < k; j++) {
                    sum += a[s + j * d] * (j + 1);
                }
                printf("%lld ",sum);
            }
        }
        cout << endl;
    }
    return 0;
}