Educational Codeforces Round 151 (Rated for Div. 2)(C,D)
C(dp,子序列自动机)
题目大意就就是给你一个字符串\(s\),还给出两个边界字符串\(l\)和\(r\),长度为\(m\),问我们是否可以构造满足一下条件的字符串
\(1\),第\(i\)个字符必须在\(l_i\)和\(r_i\)的双闭区间里面
\(2\),这个获得的字符串不可以是\(s\)的序列(\(s\)里面删除任意个字符得到的字符串)
这一场我是\(vp\)的,结果惨不忍睹,但是,这个题我在\(vp\)时有思路,后面虽然时间过了,但是还是过了
既然是求不是\(s\)的子序列,我当时是求出以\(s\)的子序列,满足\(l,r\)要求的数量的字符串的数量(每一个位置可以是不同的字符),我们可以求出所有的数量,然后拿我们求得这个序列得到的字符串的数量,如果数量比所有的数量少,那么一定存在满足以上条件,否则,不满足
然后我就想出来状态转移方程
\[dp[i][j]=sum[i-1];\\sum[i]=\sum_{j=1}^{j=9}dp[i][j] \]\(dp[i] [j]\)代表第\(i\)个字符是\(j\)的数量,\(sum[i]\)是\(dp[i]\)的\(1-9\)的和
但是我后面发现第\(i\)个字符为\(j\)可以存在\(s\)的多个不同位置,但是第\(i\)个字符为\(j\)的贡献只有\(1\),然后我每次得到一个最新的第\(i\)个字符为\(j\),我都会减去前面的值,然后再加上此时获得的值(一定大于等于前面的值),这样第\(i\)个字符为\(j\)的字符串数量一定是最大的数量
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
#include <bitset>
#include <numeric>
using namespace std;
#define int long long
#define LL long long
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define eps 1e-6
#define mem(a,b) memset((a),(b),sizeof(a))
const int maxn=3e5+10;
const int mod=998244353;
int t;
int dp[maxn][10];
int sum[maxn];
int m,n;
string s,l,r;
void solve()
{
cin>>s>>m>>l>>r;
int cnt=1;
n=s.size();
s=" "+s;
l=" "+l;
r=" "+r;
for (int i=1;i<=m;i++)
{
int tot=r[i]-l[i]+1;
if(tot)
{
cnt=cnt*tot;
}
else
{
cnt=0;
break;
}
for (int j=0;j<=9;j++)
{
dp[i][j]=0;
}
sum[i]=0;
}
if(cnt==0)
{
cout<<"NO\n";
return ;
}
for (int i=1;i<=n;i++)
{
int now=s[i]-'0';
for (int j=m;j>=1;j--)
{
if(s[i]>=l[j]&&s[i]<=r[j])
{
int last=dp[j][now];
if(j==1)
{
dp[j][now]=1;
}
else
{
dp[j][now]=sum[j-1];
}
sum[j]-=last;
sum[j]+=dp[j][now];
}
}
}
if(sum[m]>=cnt)
{
cout<<"NO\n";
}
else
{
cout<<"YES\n";
}
return ;
}
signed main ()
{
//ios;
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
然后我后面看到有大佬利用子序列自动机来解决这个问题
这里使用子序列自动机来查找满足\(l,r\)条件的的字符串是否是\(s\)的子序列
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
#include <bitset>
#include <numeric>
using namespace std;
#define int long long
#define LL long long
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define eps 1e-6
#define mem(a,b) memset((a),(b),sizeof(a))
const int maxn=3e5+10;
const int mod=998244353;
int t;
string s,l,r;
int n,m;
void solve()
{
cin>>s;
n=s.size();
vector<vector<int>>nxt(n+2,vector<int>(10));
for (int i=0;i<=9;i++)
{
nxt[n+1][i]=n+10;
}
s=" "+s;
cin>>m>>l>>r;
l=" "+l;
r=" "+r;
for (int i=n;i>=1;i--)
{
int now=s[i]-'0';
nxt[i]=nxt[i+1];
nxt[i][now]=i+1;
}
int last=1;
for (int i=1;i<=m;i++)
{
int cur=0;
int ll=l[i]-'0',rr=r[i]-'0';
for (int j=ll;j<=rr;j++)
{
cur=max(cur,nxt[last][j]);
}
last=cur;
if(last>n+1)
{
cout<<"YES\n";
return ;
}
}
cout<<"NO\n";
return ;
}
signed main ()
{
//ios;
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
D(思维)
这个题目的题意很好懂,大意就是给你一个长度为\(n\)的数组,每一个\(a_i\)都代表着一种变化(\(a_i\)可以小于\(0\)),把\(pre\)变成\(pre+a_i\),我们可以任意选择一个\(k\),这样后面要是遇到变化后如果\(pre\)小于\(k\)了,但是它可以不用变得那么小,而是直接变成\(k\),我们需要知道选择\(k\)为多少时,在经过\(n\)次变化之后得到的数最大
我们要让这个数最大,主要是靠那些变小的\(a_i\),我们可以把某一个在当前可以为最大的\(pre\)作为\(k\),然后后面我们要让这个\(k\)减小负数对\(pre\)的影响,那么就是\(premax\)和\(sum[i]\)(一切正常到了这个操作后的数字),让这两个数字之间的差值越大,那么主观下来,好像,可以让这些负数的操作使\(pre\)变小的数值更小
以上只是个人拙见
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
#include <bitset>
#include <numeric>
using namespace std;
#define int long long
#define LL long long
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define eps 1e-6
#define mem(a,b) memset((a),(b),sizeof(a))
const int maxn=3e5+10;
const int mod=998244353;
int t;
int n,a[maxn],sum[maxn];
void solve()
{
cin>>n;
int ans=0;
for (int i=1;i<=n;i++)
{
cin>>a[i];
sum[i]=sum[i-1]+a[i];
}
int premax=0;
int flag=0;
for (int i=1;i<=n;i++)
{
if(sum[i]-premax<flag)
{
flag=sum[i]-premax;
ans=premax;
}
premax=max(premax,sum[i]);
}
cout<<ans<<"\n";
return ;
}
signed main ()
{
//ios;
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
还发现了一个大佬的一个题解
标签:151,Educational,Rated,int,sum,long,maxn,include,define From: https://www.cnblogs.com/righting/p/17517595.html