2019亚洲区域赛（南昌）网络赛
- 一场比赛下来发现自身水平远远不够
- 一共做了三道题 AC一道签到题（丢人了哈）
- 本篇文章分析一道关于字符串的题目，同时对比我和AC的代码，希望通过模仿来提升自己的算法水平
题意
- 定义了good ：当串中包含9102子串并且不包含8102子串
- 截取串的一段，如果通过删除（0 or more）数字可以使串成为good则输出至少要删除的字符个数，若不能则输出-1
- 输入： 字符串长度 测试数，要截取字符串的左右区间
- 输出 至少要删除的字符个数/-1；
我的题解（回答错误/超时）
我的思路很简单，先根据l,r分割字符串，找到字符串中最后一个2，再从2往前找0，以此类推直到找到9和8为止，此时判断各个数字的位置，若出现-1则说明数字不存在，即输出-1，若满足9102，则去遍历字符串寻找所有的8并计数输出。
#include<iostream>
#include <stdio.h>
#include <string>
#include <set>
#include<list>
using namespace std;
int n,q;
string s = "";
int main()
{
cin >> n >> q;
cin >> s;
while(q--)
{
int l,r,ans = 0;
cin >> l >> r;
string S(s,l - 1,(r - l + 1));
int one,zero,two,nine,eight;
two = S.find_last_of('2');
zero = S.find_last_of('0',two);
one = S.find_last_of('1'),zero;
nine = S.find_last_of('9',one);
eight = S.find_last_of('8',one);
if(nine != -1 && one != -1 && two != -1 && zero != -1)
{
if(eight < 0)
{
cout << '0' << endl;
// cout << nine << one << zero << two << endl;
}else
{
for(int i = 0;i <= eight;i++){
if(S[i] == '8'){
ans++;
}
}
cout << ans << endl;
// cout << nine << one << zero << two << endl;
}
}else
{
cout << "-1" << endl;
// cout << nine << one << zero << two << endl;
}
}
return 0;
}
Accept的题解
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
const int inf=0x3f3f3f3f;
char a[maxn];
struct node
{
int dp[5][5];
void init(){
memset(dp,inf,sizeof(dp));
for(int i=0;i<5;i++) dp[i][i]=0;
}
friend node operator * (node a,node b){
node tmp;//tmp.init();
memset(tmp.dp,inf,sizeof(tmp.dp));
for(int i=0;i<5;i++){
for(int j=0;j<5;j++){
for(int k=0;k<5;k++){
tmp.dp[i][j]=min(tmp.dp[i][j],a.dp[i][k]+b.dp[k][j]);
}
}
}
return tmp;
}
}tr[maxn<<2];
void build(int i,int l,int r)
{
if(l==r)
{
tr[i].init();
int c=a[l]-'0';
if(c==2) tr[i].dp[0][0]=1,tr[i].dp[0][1]=0;
if(c==0) tr[i].dp[1][1]=1,tr[i].dp[1][2]=0;
if(c==1) tr[i].dp[2][2]=1,tr[i].dp[2][3]=0;
if(c==9) tr[i].dp[3][3]=1,tr[i].dp[3][4]=0;
if(c==8) tr[i].dp[3][3]=1,tr[i].dp[4][4]=1;
return;
}
int mid=(l+r)>>1;
build(2*i,l,mid);
build(2*i+1,mid+1,r);
tr[i]=tr[2*i]*tr[2*i+1];
}
node query(int i,int l,int r,int x,int y)
{
node ans;
ans.init();
if(x<=l&&r<=y) return tr[i];
int mid=(l+r)>>1;
if(x<=mid) ans=ans*query(2*i,l,mid,x,y);
if(y>mid) ans=ans*query(2*i+1,mid+1,r,x,y);
return ans;
}
int main()
{
int n,q,l,r;
scanf("%d%d",&n,&q);
scanf("%s",a+1);
reverse(a+1,a+1+n);
build(1,1,n);
for(int i=1;i<=q;i++)
{
scanf("%d%d",&l,&r);
l=n+1-l;
r=n+1-r;
int ans=query(1,1,n,r,l).dp[0][4];
printf("%d\n",ans==inf?-1:ans);
}
return 0;
}
