毕业之前心血来潮开了一场vp，就当作是追忆青春了吧（大雾
平时比较懒，打了这么多cf都没写过题解，还是蛮可惜的，如果再多写点，说不定还能给还在校队的学弟们参考参考，也不知道以后是否还会再登录cf，也许这篇博客就是休止符？希望我某天还是再上号打打吧，毕竟当年立下的上红名的flag还没实现呢…
从2022年12月杭州站结束后退役算起，已经过了快一年了，会看过去的题解博客，颇有一番悲凉的感觉。自己就像是推石头的西西弗斯，做着很多毫无意义的事情————虽然自己乐在其中。
“是谁来自山河湖海，却囿于昼夜厨房与爱”。不论自己有多么多不切实际的幻想，但总是要面对现实的呀。
只需要考虑每个字母的最左和最右出现的位置即可。
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
| #include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef double db;
typedef long double ldb;
const ll mod = 998244353;
const int maxn = 2e5 + 5;
const double eps = 1e-10;
string s;
int ans, mi[5];
void check(int x) {
for (int i = 0; i < 5; ++i) {
s[x] = i + 'A';
char mx = 'A';
int res = 0;
for (int j = s.size() - 1; j >= 0; --j) {
if (s[j] >= mx)
res += mi[s[j] - 'A'];
else res -= mi[s[j] - 'A'];
mx = max(mx, s[j]);
}
ans = max(ans, res);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int T = 1;
cin >> T;
mi[0] = 1;
for (int i = 1; i < 5; ++i) mi[i] = mi[i - 1] * 10;
while (T--) {
cin >> s;
ans = -2e9;
map<int, int> mp;
for (int i = 0; i < s.size(); ++i) {
char ch = s[i];
if (!mp[ch])
check(i);
mp[ch] = 1;
s[i] = ch;
}
mp.clear();
for (int i = s.size() - 1; i >= 0; --i) {
char ch = s[i];
if (!mp[ch])
check(i);
mp[ch] = 1;
s[i] = ch;
}
cout << ans << '\n';
}
return 0;
}
|
提前得到所有区间之间两两合并得到的新区间，由于每一个新区间之间都不能相交，故在对新区间进行操作时不需要判断原区间的重用。
这样一来，问题变为“在若干区间中，选取尽可能多的不相交的区间”，通过简单的贪心即可求解。
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
| #include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef double db;
typedef long double ldb;
const ll mod = 998244353;
const int maxn = 2e3 + 5;
const int inf = 1e9 + 5;
const double eps = 1e-10;
int n;
pii seg[maxn];
vector<pii> vec;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int T = 1;
cin >> T;
while (T--) {
cin >> n;
for (int i = 1; i <= n; ++i) {
int l, r;
cin >> l >> r;
seg[i] = make_pair(l, r);
}
sort(seg + 1, seg + n + 1);
vec.clear();
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
if (seg[i].second < seg[j].first) continue;
vec.push_back(make_pair(seg[i].first, max(seg[j].second, seg[i].second)));
}
}
sort(vec.begin(), vec.end());
int lst = -1, ans = 0;
for (auto it: vec) {
if (it.first > lst)
lst = it.second, ans++;
else lst = min(lst, it.second);
}
cout << n - ans * 2 << '\n';
}
return 0;
}
|
如果我们能得到在水平方向上尽可能长的所有连续段，就能通过从大到小填满这些段的方式，得到最终结果。但是这些段的数量级能达到n2个，乍一看是不可维护的。经过观察可以发现，一个长的连续段会被黑色块分割为若干小的连续段，且在分割之前，其长度保持不变。
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
| #include <iostream>
#include <set>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef double db;
typedef long double ldb;
const ll mod = 998244353;
const int maxn = 2e5 + 5;
const double eps = 1e-10;
set<pair<int, pii> > s;
int n, a[maxn];
ll m;
int pre[maxn], nxt[maxn];
ll seg[maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int T = 1;
cin >> T;
while (T--) {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i], a[i] = n - a[i];
cin >> m;
s.clear();
for (int i = 1; i <= n; ++i) seg[i] = 0;
int lst = 1;
for (int i = 2; i <= n; ++i) {
if (a[i] != a[i - 1]) {
s.insert(make_pair(a[i - 1], make_pair(lst, i - 1)));
pre[i - 1] = lst;
nxt[lst] = i - 1;
lst = i;
}
}
pre[n] = lst;
nxt[lst] = n;
s.insert(make_pair(a[n], make_pair(lst, n)));
ll ans = 0;
a[0] = a[n + 1] = -1;
while (!s.empty()) {
auto it = s.end();
it--;
if (it->second.first == 1 && it->second.second == n) {
seg[n] += it->first;
break;
}
int candi_left = it->second.first - 1, candi_right = it->second.second + 1;
seg[it->second.second - it->second.first + 1] += it->first - max(a[candi_left], a[candi_right]);
if (a[candi_left] >= a[candi_right]) {
s.erase(make_pair(a[candi_left], make_pair(pre[candi_left], candi_left)));
pre[it->second.second] = pre[candi_left];
nxt[pre[it->second.second]] = it->second.second;
s.insert(make_pair(a[candi_left], make_pair(pre[candi_left], it->second.second)));
a[it->second.second] = a[candi_left];
}
else {
s.erase(make_pair(a[candi_right], make_pair(candi_right, nxt[candi_right])));
nxt[it->second.first] = nxt[candi_right];
pre[nxt[it->second.first]] = it->second.first;
s.insert(make_pair(a[candi_right], make_pair(pre[nxt[candi_right]], nxt[candi_right])));
a[it->second.first] = a[candi_right];
}
s.erase(it);
}
for (int i = n; i >= 1; --i) {
if (!seg[i]) continue;
if (1ll * seg[i] * i <= m) {
m -= 1ll * seg[i] * i;
ans += 1ll * seg[i] * (i - 1);
}
else {
ans += 1ll * (m / i) * (i - 1);
m -= 1ll * (m / i) * i;
if (m) ans += m - 1;
break;
}
}
cout << ans << '\n';
}
return 0;
}
|
这个题目一起vp的校队的同学做出来了，我没做出来，嘶，我好菜呀QAQ
问题等价于，给定n个二维向量，从其中选择某个子集，使得这些向量之和得到的新向量的模长最大。
算是一个很经典的闵可夫斯基和的应用场景了，由于题目特性，有简单写法，详见代码不过我没意识到，还是看了题解才发现
按照极角排序后，依次加入向量计算答案即可，唯一需要注意的是，所有向量都应该正反方向都加一遍，保证不漏解。
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
| #include<iostream>
#include<vector>
using namespace std;
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
typedef pair<ll,ll> pll;
typedef double db;
typedef long double ldb;
const ll mod = 998244353;
const int maxn = 3e5+5;
const double eps = 1e-10;
int n;
vector<pii> vec;
int section(pii x) {
if (x.first > 0 && x.second >= 0) return 0;
if (x.first <= 0 && x.second > 0) return 1;
if (x.first < 0 && x.second <= 0) return 2;
return 3;
}
bool cmp(pii pre, pii nxt) {
if (section(pre) != section(nxt)) return section(pre) < section(nxt);
return 1ll * pre.first * nxt.second - 1ll * pre.second * nxt.first > 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int T = 1;
while (T--) {
cin >> n;
pair<db, db> start_point = make_pair(0, 0);
vec.clear();
for(int i = 1; i <= n; ++i) {
int a, b, c, d;
cin >> a >> b >> c >> d;
if (a == b && c == d) continue;
vec.push_back(make_pair(b - a, d - c));
vec.push_back(make_pair(a - b, c - d));
if (d - c < 0 || (d == c && b < a)) {
start_point.first += b - a;
start_point.second += d - c;
}
}
sort(all(vec), cmp);
db ans = 0;
for (auto it: vec) {
start_point.first += it.first;
start_point.second += it.second;
ans = max(ans, start_point.first * start_point.first + start_point.second * start_point.second);
}
printf("%.10lf\n", ans);
}
return 0;
}
|
