H.Instructions Substring
题目大意：给出一段长为 \(n\) 的字符串，其中WASD分别代表向上下左右走，给出目的地 \((x,y)\) ，选择一段连续子序列使得从 \((0,0)\) 出发可以经过目的地，求这样的子序列的总数。
思路：用前缀和记录到 \(i\) 为止到达的位置，从前往后遍历右端点 \(r\) ，找到恰好到达目的地的 \(l\) 的数量，即 \(prex[i]-x,prey[i]-y\) 的数量，这些数量可以使 \(r\) 到 \(n\) 的所有右端点成立（经过目的地）。做完后将这些已经用过的前端点归0，防止后面的后端点再次使用而重复。
注意：由于一开始就在（0，0），若目的地为（0，0）则需特判；
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
const int N = 9e6 + 10;
using namespace std;
const int mod = 998244353;
int prex[200005],prey[200005];
map<pair<int,int> ,int>mp;
void solve(){
int n,x,y;cin>>n>>x>>y;
for(int i=1;i<=n;i++){
char c;cin>>c;
if(c=='D'){
prex[i]=prex[i-1]+1;
prey[i]=prey[i-1];
}
else if(c=='A'){
prex[i]=prex[i-1]-1;
prey[i]=prey[i-1];
}
else if(c=='S'){
prex[i]=prex[i-1];
prey[i]=prey[i-1]-1;
}else {
prex[i]=prex[i-1];
prey[i]=prey[i-1]+1;
}
}
if(x!=0||y!=0) mp[{0,0}]++;
int ans=0;
for(int i=1;i<=n;i++){
mp[{prex[i], prey[i]}]++;
ans+=mp[{prex[i]-x,prey[i]-y}]*(n-i+1);
mp[{prex[i]-x,prey[i]-y}]=0;
}
cout<<ans<<'\n';
}
signed main(){
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int _=1;
// cin>>_;
while(_--)solve();
}
I：Red Playing Cards
题目大意：有 \(2*n\) 张牌，牌上数字为 \(1-n\) 的牌每种两张，你可以选择数字相同的两张牌将他们以及他们中间的牌删去，并获得选择的数字乘删去牌的数量的贡献，求删到不可删为止的最大贡献。
思路：用 \(mx[num]\) 表示 \(num.l\) 到 \(num.r\) 可实现的最大贡献，用 \(dp[i]\) 表示 \(i\) 到 \(num.l\) 的最大贡献。从大到小更新 \(mx[num]\) 的值， \(date[i]\) 存储 \(i\) 位置上的数。
1.如果两 \(num\) 之间的牌的值都比 \(num\) 小，那么一定删去这两个相同数字，并得到 \(dp[num.r]\) 的贡献。E：5123412345，一定删去5，得到50的贡献。
2.如果两 \(num\) 之间 \(i\) 位置上出现一张牌的值为 \(k\) ，且 \(k>num\) 那么就判断是删去这个大数的最大贡献大还是不删更大。\(dp[i]=max(dp[i],dp[date[i].l]+dp[k])\) 。
3.由于数字0的贡献与长度无关，在原数列两头加上0，就可以得到 \(1\) 到 \(2*n\) 的最大贡献 \(mx[0]\) 。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
const int N = 9e6 + 10;
using namespace std;
const int mod = 998244353;
struct num{
int l,r;
}a[N];
vector<int>mx(N),dp(N),date(N);
void solve() {
int n;
cin >> n;
for(int i=2;i<=2*n+1;i++){
int num;
cin >> num;
date[i]=num;
if(a[num].l) a[num].r=i;
else a[num].l=i;
}
a[0].l=1;
a[0].r=2*n+2;
date[1]=date[2*n+2]=0;
for(int i=n;i>=0;i--){
int l=a[i].l,r=a[i].r;
dp[l-1]=0;
for(int j=l;j<=r;j++){
dp[j]=dp[j-1]+i;
if(date[j]>i&&a[date[j]].l>l&&a[date[j]].r==j){
dp[j]=max(dp[j],dp[a[date[j]].l-1]+mx[date[j]]);
}
}
mx[i]=dp[r];
}
cout << mx[0];
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int _ = 1;
// cin>>_;
while (_--)solve();
}