对一个数组，找到索引(i,j,k,l)使得∣ai−aj∣+∣aj−ak∣+∣ak−al∣+∣al−ai∣最大的值。
t(1≤t≤500)
n(4≤n≤100)
ai(−106≤ai≤106)
选则最大的两个数和最小的两个数，结果为最大-最小+次大-最小+最大-次小+次大-次小。
1
2
3
4
5
6
7
8
| void solve() {
int n;cin >> n;
vector<ll>a(n);
for (int i = 0;i < n;i++)
cin >> a[i];
sort(a.begin(), a.end());
cout << a[n - 1] - a[0] + a[n - 2] - a[0] + a[n - 1] - a[1] + a[n - 2] - a[1] << '\n';
}
|
有一些5种不同面值的金币，面值有：1,3,6,10,15。找到使用金币数目最少的组合方式达到数值为n的组合。
t(1≤t≤104)
n(1≤n≤109)
打表。
1
2
3
4
5
6
7
8
9
10
11
12
13
| void solve() {
ll n;cin >> n;
vector<ll>p = { 0,
1,2,1,2,3,1,2,3,2,1,
2,2,2,3,1,2,3,2,3,2,
2,3,3,3,2,3,3,3,4,2
};
ll ans = n / 15 + p[n % 15];
if (n / 15 > 0)
ans = min(ans, n / 15 - 1 + p[n % 15 + 15]);
cout << ans << endl;
}
|
交互题。
n×m的地图有两个地雷，每次询问一个坐标点，评审机会返回距离询问点最近的地雷的与询问点的曼哈顿距离。
t(1≤t≤3×103)
n,m(2≤n≤108,2≤m≤108)
第一次询问可以获得一条斜线，斜线上至少有一个地雷。
第二次询问可能可以找到正好一个交点，这个交点可能正好是地雷或者是两个地雷的行列序号的组合。再做第三次询问，得到两个交点至少有一个是地雷。第四次询问即可排除。
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
| bool f = false;
int ask(int x, int y) {
cout << "? " << x << ' ' << y << endl;
int res;cin >> res;
if (res == 0) {
cout << "! " << x << ' ' << y << endl;
f = true;
}
return res;
}
void solve() {
int n, m;cin >> n >> m;
f = false;
int x1 = ask(1, 1);
if (f) { return; }
int x2 = ask(1, m);
if (f) { return; }
int x3 = ask(n, 1);
if (f) { return; }
int x, y;
if (x2 + x3 == n + m - 2) {
// 同一条斜线
y = (x1 + x3 - n + 1) / 2;
x = x1 - y;
x += 1;y += 1;
cout << "! " << x << ' ' << y << endl;
return;
}
else if ((n + m - x2 - x3) % 2 != 0) {
// 有一个交点
if ((x1 + x2 - m + 1) % 2 == 0) {
x = (x1 + x2 - m + 1) / 2;
y = x1 - x;
x += 1;y += 1;
cout << "! " << x << ' ' << y << endl;
}
else {
y = (x1 + x3 - n + 1) / 2;
x = x1 - y;
x += 1;y += 1;
cout << "! " << x << " " << y << endl;
}
return;
}
y = (x1 + x3 - n + 1) / 2;
x = x1 - y;
x += 1;y += 1;
if (x < 1 || x > n || y < 1 || y > m) {
f = true;
}
if (!f) {
int x4 = ask(x, y);
if (f) { return; }
}
x = (x1 + x2 - m + 1) / 2;
y = x1 - x;
x += 1;y += 1;
cout << "! " << x << ' ' << y << endl;
}
|
