div4_971Codeforces Round 971 (Div. 4) 题解

A. Minimize!

输出\(b-a\)即可

code:

#include <bits/stdc++.h>

using namespace std;

int T;
int a, b;

int main()
{
    cin >> T;
    while (T--)
    {
        cin >> a >> b;
        cout << b - a << endl;
    }

    return 0;
}

B. osu!mania

从下到上，从左到右遍历字符串，输出每个\(\#\)在当前行的位置

code:

#include <bits/stdc++.h>

using namespace std;

const int N = 510;

int T;
int n;
string s[N];

int main()
{
    cin >> T;
    while (T--)
    {
        cin >> n;
        for (int i = 0; i < n; i++) cin >> s[i];
        
        for (int i = n - 1; i >= 0; i--)
            for (int j = 0; j < 4; j++)
                if (s[i][j] == '#')
                    cout << j + 1 << ' ';
        cout << endl;
    }

    return 0;
}

C. The Legend of Freya the Frog

青蛙跳到横坐标\(x\)至少需要\(\lceil\frac{(x+k-1)}{k}\rceil\)步，跳到纵坐标\(y\)至少需要\(\lceil\frac{(y+k-1)}{k}\rceil\)步

但是，由于青蛙每次跳跃都会变换方向，因此，当青蛙仅到达\(x\)和\(y\)其中之一时，青蛙之后每向目标坐标真正移动一次，都需要消耗两个移动次数，因为消耗的其中一个移动次数时面向的方向是青蛙已经到达的方向，所以该方向青蛙移动的坐标是\(0\)

code:

#include <bits/stdc++.h>

using namespace std;

int T;
int x, y, k;

int main()
{
    cin >> T;
    while (T--)
    {
        cin >> x >> y >> k;
        
        x = (x + k - 1) / k, y = (y + k - 1) / k;
        if (x > y) cout << x * 2 - 1 << endl;
        else cout << y * 2 << endl;
    }

    return 0;
}

D. Satyam and Counting

因为纵坐标的值只能是\(0\)或\(1\)，因此给出的坐标点中能构成三角形的情况只有两种

• 当横坐标\(x\)上存在\((x,0)\)和\((x,1)\)时，其余所有点都能跟这两个点构成直角三角形
  
• 当三个点的横坐标连续，并且中间点的纵坐标和其余两个点的纵坐标不同时，这三个点可以构成直角三角形

可以发现，没有其他情况能构成直角三角形

code:

#include <bits/stdc++.h>

#define x first
#define y second
#define int long long

using namespace std;

typedef pair<int, int> PII;

const int N = 200010;

int T;
int n;
map<PII, int> p;

signed main()
{
    cin >> T;
    while (T--)
    {
        p.clear();
        
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            int x, y;
            cin >> x >> y;
            p[{x, y}]++;
        }
        
        int res = 0;
        for (int i = 0; i <= n; i++)
        {
            if (p[{i, 0}] && p[{i, 1}]) res += n - 2;
            if (p[{i, 0}] && p[{i + 1, 1}] && p[{i + 2, 0}]) res++;
            if (p[{i, 1}] && p[{i + 1, 0}] && p[{i + 2, 1}]) res++;
        }
        
        cout << res << endl;
    }
	
    return 0;
}

E. Klee's SUPER DUPER LARGE Array!!!

可以发现，不带绝对值的答案区间具有单调性，可以用二分查找距离\(0\)最近的答案，加上绝对值输出即可

#include <bits/stdc++.h>

#define int long long

using namespace std;

int T;
int n, k;

int check(int x)
{
    return (k * 2 + x - 1) * x / 2 - (k * 2 + x + n - 1) * (n - x) / 2; 
}

signed main()
{
    cin >> T;
    while (T--)
    {
        cin >> n >> k;
        
        int l = 1, r = n;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (check(mid) < 0) l = mid + 1;
            else r = mid;
        }
        
        cout << min(abs(check(l)), abs(check(l - 1))) << endl;
    }

    return 0;
}

F. Firefly's Queries

恶心的模拟，只需要分别处理出\(l\)和\(r\)所在的\(c\)数组下标，再用前缀和维护区间和即可

code:

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 200010;

int T;
int n, q;
int a[N];
int pre[N];

signed main()
{
    cin >> T;
    while (T--)
    {
        cin >> n >> q;
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
            pre[i] = pre[i - 1] + a[i];
        }
        
        while (q--)
        {
            int x, y;
            cin >> x >> y;
            
            int id1 = (x + n - 1) / n, id2 = y / n;
            int res = max((int)0, id2 - id1) * pre[n];
            x %= n, y %= n;
            if (id2 >= id1 && !(id2 == id1 && !y))
            {
                if (!x) x = n;
                res += pre[n] - pre[min(n, id1 + x - 2)];
                res += pre[id1 - 1] - pre[max((int)0, x - n + id1 - 2)];
                if (y)
                {
                    id2++;
                    res += pre[min(n, id2 + y - 1)] - pre[id2 - 1];
                    res += pre[max((int)0, y - n + id2 - 1)];
                }
            }
            else
            {
                if (!x) x = n;
                if (!y) y = n;
                res += pre[min(n, id1 + y - 1)] - pre[min(n, id1 + x - 2)];
                res += pre[max((int)0, y - n + id1 - 1)] - pre[max((int)0, x - n + id1 - 2)];
            }
        
            cout << res << endl;
        }
    }

    return 0;
}

G1. Yunli's Subarray Queries (easy version)

考虑用\(map\)来维护\(i-k+1\)到\(i\)的最小修改次数

假设当前位置是\(i\)，并且不改变\(a[i]\)的值，则\(a[1]\)的值应修改为\(a[i]-i+1\)，因此，\(p[a[i]-i+1]\)记录的就是\(i-k+1\)到\(i\)中不改变\(a[i]\)的情况下所有不需要改变的数的个数，至于\(i-k+1\)到\(i\)中最大不需要改变的数的个数，可以用优先队列维护，每次及时弹出不在范围内的数即可

code:

#include <bits/stdc++.h>

using namespace std;

const int N = 200010;

int T;
int n, k, q;
int a[N];
int f[N];

int main()
{
    cin >> T;
    while (T--)
    {
        cin >> n >> k >> q;
        for (int i = 1; i <= n; i++) cin >> a[i];
        
        map<int, int> p, st;
        priority_queue<int, vector<int>, less<int>> heap;
        for (int i = 1; i <= n; i++)
        {
            if (i > k) 
            {
                st[p[a[i - k] - i + k + 1]]++;
                heap.push(--p[a[i - k] - i + k + 1]);
            }
            if (p[a[i] - i + 1]) st[p[a[i] - i + 1]]++;
            heap.push(++p[a[i] - i + 1]);
            while (st[heap.top()]) st[heap.top()]--, heap.pop();
            f[i] = k - heap.top();
        }
        
        while (q--)
        {
            int l, r;
            cin >> l >> r;
            cout << f[r] << endl;
        }
    }

    return 0;
}