A. Perpendicular Segments

不难发现， \(A,B,C,D\) 可以当作正方形的四个顶点，\(len(AB)=len(CD)=\) 正方形对角线长度，因此只要在给定区间找到最大正方形即可。

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>

#define x first
#define y second
#define int long long
#define endl '\n'

using namespace std;

typedef pair<int, int> PII;

const int N = 200010;

int T;
int x, y, k;

void solve()
{
    cin >> x >> y >> k;

    int d = min(x, y);
    cout << "0 0 " << d << ' ' << d << endl;
    cout << "0 " << d << ' ' << d << " 0" << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> T;
    while (T--) solve();

    return 0;
}

B. Black Cells

分情况

  • 当 \(n\) 为偶数时，所有白色格子都可以成对被涂黑，并且只有一种方案。
  • 当 \(n\) 为奇数时，有一个白色格子需要被单独涂黑，暴力枚举即可。

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>

#define x first
#define y second
#define int long long
#define endl '\n'

using namespace std;

typedef pair<int, int> PII;

const int N = 2010;

int T;
int n;
int a[N];

void solve()
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    if (n == 1)
    {
        cout << 1 << endl;
        return;
    }

    int res = 1e18;
    for (int i = (n % 2 ? 0 : -1); i < (n % 2? n : 0); i++)
    {
        vector<int> s;
        for (int j = 0; j < n; j++)
            if (i != j)
                s.push_back(a[j]);
                
        int ans = 0;
        for (int j = 0; j < s.size(); j += 2)
            ans = max(ans, s[j + 1] - s[j]);
            
        res = min(res, ans);
    }

    cout << res << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> T;
    while (T--) solve();

    return 0;
}

C. Action Figures

贪心，由于越往后的商品越贵，因此应该优先使价值最大的商品免费。

如果某一天商店不能访问，那么这一天的商品只能之后买，没有办法免费。

从后往前遍历商品，若当前商品之前有未被购买的商品，可以让当前商品和之前未被购买的某一个商品成对购买，以达到当前商品免费。

对于之前未被购买商品的选择顺序，优先选择当天不能购买的，如果没有，则优先选价值最小的。

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>

#define x first
#define y second
#define int long long
#define endl '\n'

using namespace std;

typedef pair<int, int> PII;

const int N = 200010;

int T;
int n;
string s;

void solve()
{
    cin >> n >> s;
    s = ' ' + s;

    vector<int> s0, s1;
    for (int i = 1; i <= n; i++)
    {
        if (s[i] == '0') s0.push_back(i);
        else s1.push_back(i);
    }

    reverse(s1.begin(), s1.end());

    int res = 0;
    for (int i = n; i >= 1; i--)
    {
        if (s[i] == '0') res += i;
        else
        {
            while (s0.size() && s0.back() > i) s0.pop_back();
            while (s1.size() && s1.back() >= i) s1.pop_back();
            if (s0.size()) s0.pop_back();
            else if (s1.size()) 
            {
                s[s1.back()] = '0';
                s1.pop_back();
            }
            else res += i;
        }
    }

    cout << res << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> T;
    while (T--) solve();

    return 0;
}

D. Sums of Segments

对于数组 \(b\)，可以分为 \(n\) 段，分别是 \([s(1,1),s(1,2),...s(1,n)],[s(2,2),s(2,3),...s(2,n)]...[s(n,n)]\)

对于前 \(i\) 段的和，设为 \(sum[i]\)，手算一下，有 \(sum[i] = pre[1] * 1 + pre[2] * 2 + ... + pre[i] * i + (prei[i+1] + pre[i+2]+...+pre[n]) * i - pre[0] * n - pre[1] * (n - 1) - ... - pre[i - 1] * (n - i + 1)\)

若要求的长度无法划分为整段，假设可以划分为 \(x\) 段，剩余长度为 \(y\)，则可以先求 sum[x]，再求超出部分的和，为 \(pre[x+1]+pre[x+2]+...+pre[x + y]-pre[x]*y\)

因此可以预处理四个数组： 1. \(a[i]\) 的前缀和数组 \(pre[i]\) 2. \(pre[i]\) 的前缀和数组 \(ppre1[i]\) 3. \(pre[i]*i\) 的前缀和数组 \(ppre2[i]\) 4. \(pre[i]*(n-i)\) 的前缀和数组 \(ppre3[i]\)

可以推出数组 \(b\) 的前缀和公式: \(ppre2[x] + (ppre1[n] - ppre1[x]) * x - ppre3[x - 1] + ppre1[x + y] - ppre1[x] - pre[x] * y\)

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 300010;

int n, q;
int a[N];
int pre[N], ppre1[N], ppre2[N], ppre3[N];

int calc(int c)
{
    if (!c) return 0;

    int l = 1, r = n;
    while (l < r)
    {
        int mid = l + r >> 1;
        if ((n * 2 - mid + 1) * mid / 2 < c) l = mid + 1;
        else r = mid;
    }

    int x = l - 1, y = c - (n * 2 - l + 2) * (l - 1) / 2;
    return ppre2[x] + (ppre1[n] - ppre1[x]) * x - ppre3[x - 1] + ppre1[x + y] - ppre1[x] - pre[x] * y;
}

signed main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i <= n; i++)
    {
        pre[i] = pre[i - 1] + a[i];
        ppre1[i] = ppre1[i - 1] + pre[i];
        ppre2[i] = ppre2[i - 1] + i * pre[i];
        ppre3[i] = ppre3[i - 1] + (n - i) * pre[i];
    }

    cin >> q;
    while (q--)
    {
        int l, r;
        cin >> l >> r;
        
        cout << calc(r) - calc(l - 1) << endl;
    }

    return 0;
}