A. Sonya and Queries

由于默认补足前导0，而且必须从低到高匹配，可以直接使用map.

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
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
const int maxn = 2e5 + 10;
int a[maxn];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    map<int, int> mp;
    while(t--) {
        char op;
        int num;
        cin >> op >> num;
        if(op == '?') {
            cout << mp[num] << endl;
            continue;
        }
        int res = 0;
        for (int i = 1; num; i *= 10) {
            res += (num & 1) * i;
            num /= 10;
        }
        if(op == '+') mp[res]++;
        else mp[res]--;
    }
    return 0;
}

B. Searching Rectangles

一道有点毒瘤的二分交互题。

由于两个矩形不相交，一定存在一条竖线/横线使得两个矩形分别在线的两侧，通过两次二分找到一条符合条件的线即可。

找到分割线后，分别在两个区域内询问出一个矩形的上下左右边界，求各个边界也用二分即可。

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <bits/stdc++.h>
using namespace std;
int n;
int ans[2][4];
int query(int x1, int y1, int x2, int y2) {
    int tmp;
    printf("? %d %d %d %d\n", x1, y1, x2, y2);
    fflush(stdout);
    scanf("%d", &tmp);
    return tmp;
}
int lr() {
    int l = 1, r = n;
    int x, y;
    while(l + 1 < r) {
        int mid = (l + r) >> 1;
        x = query(1, 1, mid, n);
        y = query(mid + 1, 1, n, n);
        if(!x && !y) return 0;
        if(x && !y) r = mid;
        else if(!x && y) l = mid + 1;
        else if(x && y) return mid;
    }
    x = query(1, 1, l, n);
    y = query(r, 1, n, n);
    if(x == 1 && y == 1) return l;
    else return 0;
}
int ud() {
    int l = 1, r = n;
    int x, y;
    while(l + 1 < r) {
        int mid = (l + r) >> 1;
        x = query(1, 1, n, mid);
        y = query(1, mid + 1, n, n);
        if(!x && !y) return 0;
        if(x && !y) r = mid;
        else if(!x && y) l = mid + 1;
        else if(x && y) return mid;
    }
    x = query(1, 1, n, l);
    y = query(1, r, n, n);
    if(x == 1 && y == 1) return l;
    else return 0;
}
void queryRec(int id, int x1, int y1, int x2, int y2) {
    //upper_bound
    int x;
    // right
    int l = x1, r = x2;
    while(l < r) 
    {
        int mid = (l + r) >> 1;
        x = query(x1, y1, mid, y2);
        if(x) r = mid;
        else l = mid + 1;
    }
    ans[id][2] = l;

    // left
    l = x1, r = x2;
    while(l < r) {
        int mid = ((l + r) & 1) ? ((l + r) >> 1) + 1 : ((l + r) >> 1);
        x = query(mid, y1, x2, y2);
        if(x) l = mid;
        else r = mid - 1;
    }
    ans[id][0] = r;

    // up
    l = y1, r = y2;
    while(l < r) {
        int mid = (l + r) >> 1;
        x = query(x1, y1, x2, mid);
        if(x) r = mid;
        else l = mid + 1;
    }
    ans[id][3] = l;

    // down
    l = y1, r = y2;
    while(l < r) {
        int mid = ((l + r) & 1) ? ((l + r) >> 1) + 1 : ((l + r) >> 1);
        x = query(x1, mid, x2, y2);
        if(x) l = mid;
        else r = mid - 1;
    }
    ans[id][1] = r;
}
int main() 
{
    scanf("%d", &n);
    int u = lr();
    if(u) {
        queryRec(0, 1, 1, u, n);
        queryRec(1, u + 1, 1, n, n);
    }
    else {
        u = ud();
        queryRec(0, 1, u + 1, n, n);
        queryRec(1, 1, 1, n, u);
    }
    printf("!");
    for (int i = 0; i <= 1; ++i) {
        for (int j = 0; j <= 3; ++j) printf(" %d", ans[i][j]);
    }
    printf("\n");
    fflush(stdout);
    return 0;
}

C. Sonya and Problem Without a Legend

要严格单调增，不好求。尝试让每第 $i$ 个元素减掉 $i$, 即加上一个等差数列 $(1, 1)$，减出来的数列求一下其非严格单调递增的结果，再还原就能得到一个严格单调递增的数组。且容易知道减掉后答案是不会变的。

怎么求这个非严格单调递增数列呢？为了让答案尽可能小，第 $i$ 个元素要么不变（已经符合严格不下降的条件），要么就变成第 $i-1$ 个元素。

这是因为：如果变得比第 $i-1$ 个元素更大的话，不仅当前答案会增加，对之后的修改也有弊无利。故可以推出：最终的数组中所有元素的值都是原数组的某一个元素值。

再看 $n\leq 3000$, 考虑 $O(n^2)$ 的动态规划。设 $dp[i][j]$ 表示修改完成前 $i$ 个数，且第 $i$ 个数变成了原数组第 $j$ 大的数的答案。

那么

其中 $b$ 是原数组排序后的数组。

这个式子是 $O(n^3)$ 的。但其实可以用滚动数组优化掉对 $m$ 的枚举, 伪代码：

1
2
3
4
5
for i from 1 to n
	int res = INF
	for j from 1 to n
		res = min(res, dp[i - 1][j])
		dp[i][j] = res + abs(a[i] - b[j])

代码

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
#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
const int maxn = 3005;
const int inf = 1e18;
int a[maxn], b[maxn];
int dp[maxn][maxn];
signed main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i], a[i] -= i, b[i] = a[i];
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) dp[i][j] = inf;
    sort(b + 1, b + 1 + n);
    for (int i = 1; i <= n; ++i) dp[1][i] = abs(a[1] - b[i]);
    for (int i = 2; i <= n; ++i) {
        int res = inf;
        for (int j = 1; j <= n; ++j) {
            res = min(dp[i - 1][j], res);
            dp[i][j] = res + abs(a[i] - b[j]);
        }
    }
    int ans = inf;
    for (int i = 1; i <= n; ++i) {
        ans = min(ans, dp[n][i]);
    }
    cout << ans << endl;
    return 0;
}