2021年就这么结束了，不管是失败还是悲伤还是焦虑，亦或者是欢乐还是欣喜还是怀念，都已经过去了。
可能会写点文字来怀念？
不过现在应该做的事情只有一件
补题。
D. Keep the Average High
将式子变形一下
al+al+1+…+ar≥x⋅(r−l+1)⇒(al−x)+(al+1−x)+…+(ar−x)≥0
然后就是挑一些最多的数让他满足所有连续子段和非负
然后就有一个很nb的结论
要满足上边的条件
只需要所有长度为2和3的子段满足条件即可
可以这样考虑：
所有长度大于2或者3的子段都可以拆成一些2和3不相交子段的和
稍微想一下奇偶应该就可以懂了
然后我们是不是就可以用用DP了呢（
转移就直接看代码吧 巨巧妙
反正我这个智力是不太能想到的（
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
| #include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#include<cstring>
#include<map>
#include<unordered_map>
typedef long long ll;
using namespace std;
ll T;
ll n;
ll x;
ll dat[50000 + 5];
ll dp[50000 + 5][2][2];
int main() {
cin >> T;
while (T--)
{
cin >> n;
for (int i = 0; i < n; i++)cin >> dat[i];
cin >> x;
for (int i = 0; i < n; i++)dat[i] -= x;
memset(dp, 0, sizeof(dp));
dp[0][0][1] = 1;
for (int i = 1; i < n; i++) {
dp[i][0][0] = max(dp[i - 1][0][0], dp[i - 1][1][0]);
dp[i][0][1]=1LL+ max(dp[i - 1][0][0], dp[i - 1][1][0]);
dp[i][1][0] = max(dp[i - 1][0][1], dp[i - 1][1][1]);
if (dat[i - 1] + dat[i] >= 0) {
dp[i][1][1] = 1LL + dp[i-1][0][1];
if (i > 1 && dat[i - 2] + dat[i - 1] + dat[i] >= 0) {
dp[i][1][1] = max(dp[i][1][1], 1 + dp[i - 1][1][1]);
}
}
}
ll ans = max(dp[n - 1][0][0], max(dp[n - 1][0][1], max(dp[n - 1][1][0], dp[n - 1][1][1])));
printf("%lld\n", ans);
}
}
|
E. Lexicographically Small Enough
这B题说简单不简单，说难不难
但是我看题解都想了好久
我是废物！
给你个字符串s和字符串t
可以交换相邻的s字符，问最少次数令s字典序比t小
其实他的本质就是让s按照某种意义重新排序，然后问冒泡排序的交换次数呗
用树状数组维护逆序对
然后对于每个t[i]我们有两种思路
维护一个cur是到当前令其前缀相同的花费
然后我从后边拉字符他的花费其实就是逆序对
我们就可以跑贪心了 也许
这玩意数据太大了 ans设成1e9+7居然都会挂掉
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
| #include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#include<cstring>
#include<map>
#include<unordered_map>
typedef long long ll;
using namespace std;
ll T;
ll n;
ll x;
vector<ll>pos[26];
ll sum[100000 + 5];
char s[100000 + 5], t[100000 + 5];
ll lob(ll i) {
return i & -i;
}
void init() {
for (int i = 0; i <= n; i++)sum[i] = 0;
}
void add(ll i) {
for (; i < n; i = i | (i + 1)) {
sum[i] += 1;
}
}
ll q(ll i) {
ll res = 0;
for (;i>=0; i=(i & (i + 1)) - 1)
res += sum[i];
return res;
}
int main() {
cin >> T;
while (T--)
{
cin >> n;
init();
cin >> s>>t;
for (int i = 0; i < 26; i++)pos[i].clear();
for (int i = 0; i <n; i++)pos[s[i] - 'a'].push_back(i);
for (int i = 0; i < 26; i++)reverse(pos[i].begin(),pos[i].end());
ll ans = 1e11 + 7;
ll cur = 0;
for (int i = 0; i <n; i++) {
ll c = t[i] - 'a';
ll m = 1e11+7;
for (int j = 0; j < c; j++) {
if (pos[j].empty())continue;
m = min(m, pos[j].back());
}
if (m <n)
ans = min(ans, cur + m - q(m));
if (pos[c].empty())break;
m = pos[c].back();
cur += m - q(m);
pos[c].pop_back();
add(m);
}
if (ans == 1e11 + 7)printf("-1\n");
else printf("%lld\n", ans);
}
}
|
