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;
}