2024牛客暑期多校训练营2 HI
2024牛客暑期多校训练营2
H.Instructions Substring
题意：
有一个字符串序列，有WSAD四种操作，可以上下左右移动。可以选取一段连续的子序列，从（0,0）出发，经过连续子序列操作后可以经过点(x,y)，问这样的子序列有多少个
思路：
若一个子序列能够实现到达点（x,y），那么在这个子序列后面加任意字符都符合要求，因此只需要找到一个最短的合法子序列即可。一个完整的字符串序列可以形成一个路径，若截去前面一段子序列，形成的新路径只需要将原有路径加个前缀和的偏移量即可。我们可以记录下整个序列路径中经过每个点时的下标；然后枚举子序列的起始下标，将(x,y)加上移动路径前缀和的偏移量，看原路径是否经过这个点，经过这个点时的下标是否大于此时的起始下标，若满足则可以二分得到最短合法子序列，然后加上这个贡献n-右边界+1
代码：
#include <bits/stdc++.h>
using namespace std ;
const int MAXN=1e5+7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
#define endl "\n"
void solve(){
int n,x,y;
cin>>n>>x>>y;
string s;
cin>>s;
if(x==0&&y==0){
ll ans=n*(n+1)/2;
cout<<ans<<endl;
return ;
}
map<pair<int ,int >,vector<int > > mp;
int prex=0,prey=0;
for(int i=0;i<n;i++){
if(s[i]=='W'){
prey++;
}else if(s[i]=='S'){
prey--;
}else if(s[i]=='A'){
prex--;
}else{
prex++;
}
mp[{prex,prey}].push_back(i);
}
prex=0,prey=0;
ll ans=0;
for(int i=0;i<n;i++){
if(!mp[{x+prex,y+prey}].empty()){
int left=0,right=mp[{x+prex,y+prey}].size();
while(left<right){
int mid=(left+right)/2;
if(mp[{x+prex,y+prey}][mid]<i){
left=mid+1;
}else{
right=mid;
}
}
if(left<mp[{x+prex,y+prey}].size()&&mp[{x+prex,y+prey}][left]<n){
ans+=n-mp[{x+prex,y+prey}][left];
}
}
if(s[i]=='W'){
prey++;
}else if(s[i]=='S'){
prey--;
}else if(s[i]=='A'){
prex--;
}else{
prex++;
}
}
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
// cin>>t;
while(t--){
solve();
}
return 0;
}
I.Red Playing Cards
题意：
有2n张卡牌，1到n的所有数字都恰好出现2次。
每次操作，可以选择相同数字的两张牌，删去这两张牌之间的区间（包含这两张牌），其贡献为这个数字大小区间的牌数，问怎样操作可以使贡献最大
思路：
对于两个区间，若两个区间有重叠部分，则两个区间只能二选一；若两个区间是包含关系，则可以选择先取里面的小区间，再取外面的大区间；若两个区间没有任何重叠，则可以都选取。
区间的贡献为“边界数字大小*区间的牌数”，那么可以看作这个区间每个数的贡献为“边界的数字大小”.对于两个区间是包含关系的情况，可以知道若“小区间的数字大小”大于“大区间的数字大小”，那么先取小区间再取大区间可以最大化贡献，反之没有意义。
因此我们可以先预处理出每个数字的左右边界，从大到小遍历这些数字，得出每个数字的区间的最大贡献，最后考虑没有重叠的区间的贡献相加（增加0的区间来实现）。
\(f_i\)为数字i的区间的最大贡献，\(dp_j\)为数字i区间内部的每张牌的贡献的前缀和。
状态转移方程为：
\(dp_j\)=\(dp_{j-1}\)+i
\(dp_{r[a[j]]}\)=\(dp_{j-1}\)+\(f_{a[j]}\) （如果\(j=l[a[j]]\)并且\(r[a[j]]<r[i]\)）
代码：
#include <bits/stdc++.h>
using namespace std ;
const int MAXN=1e5+7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
#define endl "\n"
void solve(){
int n;
cin>>n;
int a[2*n+1];
for(int i=1;i<=2*n;i++){
cin>>a[i];
}
vector<int > l(n+1,-1),r(n+1);
for(int i=1;i<=2*n;i++){
if(l[a[i]]==-1){
l[a[i]]=i;
}else{
r[a[i]]=i;
}
}
l[0]=0;
r[0]=2*n+1;
vector<int > f(n+1,0);
for(int i=n;i>=0;i--){
vector<int > dp(2*n+1,0);
for(int j=l[i]+1;j<r[i];j++){
dp[j]=max(dp[j],dp[j-1]+i);
if(j==l[a[j]]&&r[a[j]]<r[i]){
dp[r[a[j]]]=max(dp[r[a[j]]],dp[j-1]+f[a[j]]);
}
}
f[i]=2*i+dp[r[i]-1];
}
cout<<f[0]<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
// cin>>t;
while(t--){
solve();
}
return 0;
}