D

  • 题意: 以l-c的形式给定两个串,l表示数量,c表示一个字母,问第二个串在第一个串中出现了多少次

KMP

先将两个串游程编码。
第二个串去掉头和尾,剩余部分在第一个串内做kmp,然后再比较头尾是否匹配。
若第二个串只有一位和两位则特殊处理

复杂度$O(n+m)$

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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int maxn = 2e5 + 10;

struct S{
char c;
LL l;
bool operator==(const S& rhs) const
{
return c == rhs.c && l == rhs.l;
}
bool operator>=(const S& rhs) const
{
return c == rhs.c && l >= rhs.l;
}
} t[maxn],s[maxn];

int n,m;
int f[maxn];

int main()
{
//freopen("test.txt","r",stdin);
scanf("%d %d",&n,&m);
for(int i=0;i<n;++i) scanf("%lld-%c",&t[i].l,&t[i].c);
for(int i=0;i<m;++i) scanf("%lld-%c",&s[i].l,&s[i].c);
int cnt = 0;
for(int i=0;i<n;++i)
{
t[cnt].c = t[i].c;
t[cnt].l = t[i].l;
while(i+1 < n && t[cnt].c == t[i+1].c)
{
t[cnt].l += t[i+1].l;
++i;
}
++cnt;
}
n = cnt;
cnt = 0;
for(int i=0;i<m;++i)
{
s[cnt].c = s[i].c;
s[cnt].l = s[i].l;
while(i+1 < m && s[cnt].c == s[i+1].c)
{
s[cnt].l += s[i+1].l;
++i;
}
++cnt;
}
m = cnt;
LL res = 0;
if(m == 1)
{
for(int i=0;i<n;++i) if(t[i] >= s[0]) res += t[i].l - s[0].l + 1;
}
else if(m == 2)
{
for(int i=0;i+1<n;++i) if(t[i] >= s[0] && t[i+1] >= s[1]) ++res;
}
else
{
f[1] = 0;
for(int i=2;i<m-1;++i)
{
int j = f[i-1];
while(j && !(s[i] == s[j+1])) j = f[j];
f[i] = s[j+1] == s[i]?j+1:0;
}
int j = 0;
for(int i=1;i<n-1;++i)
{
while(j && !(t[i] == s[j+1])) j = f[j];
if(t[i] == s[j+1]) ++j;
if(j == m-2)
{
if(t[i-j] >= s[0] && t[i+1] >= s[j+1]) ++res;
j = f[j];
}
}
}
printf("%lld\n",res);
return 0;
}

E

  • 题意: 给n个数,最多移动一个数的位置,使$ \sum_{i=1}^{n} ia_i$最大

维护凸包

sum表示前缀和,我们考虑当前数在r,向左移动到l,值的变化为
$sum_{r-1} - sum_{l} - (r-l)a_r = sum_{r-1} + ra_r + (la_r - sum_{l})$

我们枚举r,维护直线$y = lx - sum_{l}$,其中$x = a_r$,用维护凸包的方法可以求其最大值:

直线的斜率一只在增加,所以我们可以二分求其最大值,这样的复杂度已经满足这道题
然而有个优化,就是在加入一条新的直线时,若其交点与倒数第二条直线的交点在其与最后一条直线的交点的左边,则最后一条直线可以去掉,因为其不再影响最优值。

向右移同理

复杂度$O(nlog(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
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<LL,LL> pll;
#define fi first
#define se second

const int maxn = 2e5 + 10;
LL sum[maxn],a[maxn],ans;
int n;

vector<pll> V;

bool check(pll a,pll b,pll c)
{
return (a.fi - b.fi)*(b.se - c.se) >= (b.se - a.se)*(c.fi - b.fi);
}

void add(LL k,LL b)
{
pll p(k,b);
while(V.size() >= 2 && check(V[V.size()-2],V[V.size()-1],p)) V.pop_back();
V.push_back(p);
}

LL cal(LL x,int i)
{
return x*V[i].fi + V[i].se;
}

LL query(LL x)
{
int l = -1,r = V.size()- 1;
while(r - l > 1)
{
int m = (l+r)/2;
if(cal(x,m+1) >= cal(x,m)) l = m;
else r = m;
}
return cal(x,r);
}

int main()
{
// freopen("test.txt","r",stdin);
scanf("%d",&n);
ans = 0;
for(int i=1;i<=n;++i) scanf("%lld",a+i),ans += i*a[i],sum[i] = sum[i-1] + a[i];
LL res = 0;
for(int r=2;r<=n;++r)
{
add(r-1,-sum[r-2]);
res = max(res,query(a[r])+sum[r-1]-r*a[r]);
//printf("%d %d\n",res,r);
}
V.clear();
for(int l=n-1;l>=1;--l)
{
add(-(l+1),-sum[l+1]);
res = max(res,query(-a[l])+sum[l]-l*a[l]);
//printf("%d %d\n",res,l);
}
printf("%lld\n",ans+res);
return 0;
}