3 道混合题
CF 631C
首先可以发现，对于某个长度为rk的操作序列来说，在其之前的长度小于rk的操作序列都是无效的，那么可以用栈处理出一个递减的序列
之后我们先把从r[st[0]]到n的数先赋给最后的数组，因为这部分是不变的
之后我们开始对其后的元素操作，我们知道该操作是没有后效行的，也就是说，只对之前的元素有用，那么我们从r[st[0]]遍历到1，按照对应的操作类别进行添加数就可以了
void solve(){
int n,m;cin>>n>>m;
vector<int>a(n+1),t(m+1),r(m+1),st;
for(int i=1;i<=n;++i)cin>>a[i];
for(int i=1;i<=m;++i){
cin>>t[i]>>r[i];
while(st.size()&&r[st.back()]<r[i])st.pop_back();
st.push_back(i);
}
vector<int>ans(n+1);
for(int i=r[st[0]]+1;i<=n;++i)ans[i]=a[i];
sort(a.begin()+1,a.begin()+1+r[st[0]]);
r.push_back(0);
st.push_back(r.size()-1);
int start=1,ed=r[st[0]];
for(int i=0;i<st.size()-1;++i){
for(int j=r[st[i]];j>r[st[i+1]];--j){
if(t[st[i]]==1){
ans[j]=a[ed--];
}else{
ans[j]=a[start++];
}
}
}
for(int i=1;i<=n;++i){
cout<<ans[i]<<" \n"[i==n];
}
return;
}
CF 633C
开始没有思路，看了题解发现是trie+dp
dp的思想很好处理，因为这就和硬币组合一样，那么怎么能把其中O(n)的遍历改成O(logn)呢？用字典树存一下就好惹，然后存一下trace
void solve(){
int n;
string s;
cin>>n>>s;
int k;cin>>k;
vector tree(n<<7,vector<int>(26));//2^7
vector<int>id(n<<7);
int cnt=0;
auto insert=[&](string ss,int now){
int cur=0;
for(int i=0;i<ss.size();++i){
int index=ss[i]>='A'&&ss[i]<='Z'?ss[i]-'A':ss[i]-'a';
if(!tree[cur][index]){
tree[cur][index]=++cnt;
}
cur=tree[cur][index];
if(i==s.size()-1)tree[cur][index]++;
}
id[cur]=now;
};
vector<string>dic(k+1);
for(int i=1;i<=k;++i){
cin>>dic[i];
insert(dic[i],i);
}
vector<int>dp(n+1);
for(int i=0;i<n;++i){
int cur=0;
for(int j=i;j>=0;--j){
int index=s[j]>='A'&&s[j]<='Z'?s[j]-'A':s[j]-'a';
if(!tree[cur][index])break;
cur=tree[cur][index];
if(id[cur]&&(j==0||dp[j-1])){
dp[i]=id[cur];
break;
}
}
}
int status=n-1;
vector<string>ans;
while(status>=0&&dp[status]){
ans.push_back(dic[dp[status]]);
status-=dic[dp[status]].size();
}
for(int i=ans.size()-1;i>=0;--i){
cout<<ans[i]<<" \n"[i==0];
}
return;
}
CF 629D
线段树+dp
题比较水，没太多好说的，注意一开始build的时候不要用原值，直接赋0
const double esp=1e-6;
const double PI=3.1415926;
struct node{
ll v;
int id;
};
ll tree[MAXN<<4];
vector<node>arr;
void build(int l,int r,int c){
if(l==r){
tree[c]=0;
return;
}
int m=(l+r)>>1;
build(l,m,c<<1);
build(m+1,r,c<<1|1);
}
ll query(int l,int r,int ql,int qr,int c){
if(ql<=l&&r<=qr){
return tree[c];
}
int m=(l+r)>>1;
ll ans=0;
if(ql<=m){
ans=max(ans,query(l,m,ql,qr,c<<1));
}
if(qr>m){
ans=max(ans,query(m+1,r,ql,qr,c<<1|1));
}
return ans;
}
void update(int l,int r,int c,int id,ll v){
if(l==r){
tree[c]=v;
return;
}
int m=(l+r)>>1;
if(id<=m)update(l,m,c<<1,id,v);
else if(id>m)update(m+1,r,c<<1|1,id,v);
tree[c]=max(tree[c<<1],tree[c<<1|1]);
}
void solve(){
int n;cin>>n;
arr.resize(n+1);
vector<ll>dp(n+1);//means the answer of cake end with i
dp[0]=1;
for(int i=1;i<=n;++i){
ll r,h;cin>>r>>h;
arr[i].v=r*r*h;
arr[i].id=i;
}
sort(arr.begin()+1,arr.end(),[&](node a,node b){
if(fabs(a.v-b.v)<esp)return a.id>b.id;
return a.v<b.v;
});
double ans=0;
build(1,n,1);
for(int i=1;i<=n;++i){
int id=arr[i].id;
ll res=query(1,n,1,id,1)+arr[i].v;
update(1,n,1,id,res);
ans=max(ans,res*1.0);
}
ans*=PI;
cout.precision(9);
cout<<ans<<'\n';
}
被找实习的逼事搞的够恶心，今天凌晨睡觉阿里打了仨电话都没接到，最近作息有点烂，真不能乱熬夜了，未来坎坷啊少年。