Sgu/296 2015年2月19日 (四) 21:17云璟月（讨论 | 贡献）的版本 (差异) ←上一版本 | 最后版本 (差异) | 下一版本→ (差异)

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	需要注意
Sasha vs. Kate	★☆☆☆☆	答案正确	100	2015-2-19 21:08:48	3

（AC 1212）

题意

给一个数，求去掉k位后的最大值。

题解

• 设该数n位，由题意显然是要使得答案的最高位尽量大，即取原数第1位到n-(n-k)+2位(保证后面位数够）之间的最大值，而之后每一位都取上一位位置到n-(n-k)+i+1位的最大值即可。区间最值可以用线段树处理。
• 另一种可行的弹性策略是：每次从最高位遇到非递减的字符则删除（如果整个序列都是递减的，则删除最后一个数），直到够为止。如，19192，遇到连续上升的19则删除一个1，贪心正确性待证明。

代码

296.cpp代码已折叠 展开折叠内容

#include<cstdio> #include<string> #include<iostream> #include<algorithm> #define si(n) scanf("%d",&n) #define dsi(n) int n;si(n) using namespace std; string str; class ch { public: char p; int index; ch():p(0),index(0){}; friend bool operator <(const ch&a,const ch&b){return a.p==b.p?a.index>b.index:a.p<b.p;} }; template<size_t N> class SegmentTree { //模板：线段树// public: ch tree[N]; #define cm int m=(l+r)>>1 #define lp p<<1 #define rp p<<1|1 #define lc lp,l,m #define rc rp,m+1,r #define stdp int p,int l,int r ch build(stdp) { if(l==r) { tree[p].p=str[l-1]; tree[p].index=l; return tree[p]; } cm; return tree[p]=max(build(lc),build(rc)); } ch query(int L,int R,stdp) { if(L<=l&&r<=R) return tree[p]; ch ret; ret.p=0; cm; if(L<=m)ret=max(query(L,R,lc),ret); if(R>m)ret=max(query(L,R,rc),ret); return ret; } }; SegmentTree<20000> st; int n; int main() { cin>>str; int n=str.size(); st.build(1,1,n); dsi(k); k=n-k;//fixed// string a; int lastIndex=0; for(int i=0;i<k;++i) { ch ret=st.query(lastIndex+1,n-k+i+1,1,1,n); cout<<ret.p; lastIndex=ret.index; } cout<<a; }