B

求字符串a与b的所有子串的Hamming Distance Sum

滑窗
我们分析a中每个字符与b中的一段字符串匹配
而且我们可以O(n)更新出这些串与分别与0/1匹配的距离

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

const int maxn = 2e5 + 10;
char a[maxn],b[maxn];
int res[maxn][2];

int main()
{
//freopen("test.txt","r",stdin);
scanf("%s %s",a,b);
int na = strlen(a),nb = strlen(b);
for(int i=0;i<=nb-na;++i)
if(b[i]-'0') ++res[0][0];
else ++res[0][1];
LL ans = res[0][a[0]-'0'];
for(int i=1;i<na;++i)
{
res[i][0] = res[i-1][0];
res[i][1] = res[i-1][1];
if(b[i-1]-'0') --res[i][0];
else --res[i][1];
if(b[i+(nb-na)]-'0') ++res[i][0];
else ++res[i][1];
ans += res[i][a[i]-'0'];
}
printf("%lld\n",ans);
return 0;
}

C

有一些烤肉,从左向右排列,有对应位置a和能量b
每次激活一块儿烤肉,则会熏黑左边距离b(inclusive)以内的烤肉
熏黑的烤肉不能激活,我们选择在最右边的任意位置放置一块烤肉并激活
求最少多少烤肉被熏黑。

DP

$d_{i[0..1]}$ 表示位置i上的烤肉未激活(0)/激活(1)后的最多被激活烤肉数
若激活,我们每次二分找上一个未被熏黑位置转移,否则直接从上一个位置转移。

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

const int maxn = 1e5 + 10;
int d[maxn][2];
vector<pair<int,int> > V;


int main()
{
//freopen("test.txt","r",stdin);
int n;
scanf("%d",&n);
for(int i=0;i<n;++i)
{
int a,b;
scanf("%d%d",&a,&b);
V.push_back(make_pair(a,b));
}
sort(V.begin(),V.end());
d[0][0] = 0;
d[0][1] = 1;
int ans = 1;
for(int i=0;i<V.size();++i)
{
ans = max(ans,d[i][1]);
if(i == V.size()-1) break;
d[i+1][0] = d[i][1];
int p = lower_bound(V.begin(),V.begin()+i+1,make_pair(V[i+1].first - V[i+1].second,0)) - V.begin();
if(V[p].first < V[i+1].first - V[i+1].second) d[i+1][1] = d[p][1]+1;
else if(p != 0) d[i+1][1] = d[p-1][1]+1;
else d[i+1][1] = 1;
}
printf("%d\n",n - ans);
return 0;
}

D

区间DP

给定一个字符串,每次选择一个回文串消去,问最少消除次数。

根据回文串的特点,若当前区间的两边相等,则可以直接转移到dp(L+1,R-1) (因为他们总可以和包含的区间匹配)
然后枚举分割位置

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

const int maxn = 510;
const int INF = 0x3f3f3f3f;
int d[maxn][maxn],a[maxn];


int dp(int L,int R)
{
if(L == R) return 1;
if(L+1==R) return 2-(a[L] == a[R]);
int &ans = d[L][R];
if(ans != -1) return ans;
ans = INF;
if(a[L] == a[R]) ans = dp(L+1,R-1);
for(int i=L;i<R;++i)
{
ans = min(ans,dp(L,i)+dp(i+1,R));
}
return ans;
}

int main()
{
//freopen("test.txt","r",stdin);
int n;
scanf("%d",&n);
for(int i=0;i<n;++i) scanf("%d",a+i);
memset(d,-1,sizeof d);
printf("%d\n",dp(0,n-1));
return 0;
}