好吧,神奇的题目。。

原题传送门

这道题目,神奇的字符单调栈。。

首先预处理出1~n个数(大家都会。)

然后塞进字符串里,输出答案(水~)

然后。。

我们需要将所有的字符存入单调栈中,然后乱搞,就可以输出啦。

不过注意:有的题目可能在单调栈中没有把所有的字符删完,即后面的所有字符都一样,那么此时我们需要直接把后面的多出来的位数减去即可。

还有,单调栈中如果已经减了m位之后就不能再减了

在维护单调队列时我们要尽量让排名靠前的数字被删除(贪心)

这样得到的答案才最优

(这道题我一开始做的时候没有维护单调队列,而是维护上升子序列,导致一部分(80)的点WA,我的锅。。。)

果然还是我太弱了。。

%180 Rank 1的大神zxyer

下面贴代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int k,m;
unsigned long long num[];
unsigned long long qaq[];
int num1=-,num2=-;
char ans1[];
char zc[];
char ans[];
int main(){
//freopen("number.in","r",stdin);
//freopen("number.out","w",stdout);
memset(ans,,sizeof(ans));
memset(ans1,,sizeof(ans1));
scanf("%d%d",&k,&m);
int tot=;
num[]=;
int tail1=,tail2=;
while(k>tot)
{
if(num[tail1]*+>num[tail2]*+)num[++tot]=num[tail2]*+,tail2++;
else num[++tot]=num[tail1]*+,tail1++;
}
int tt=-;
for(int i=;i<=k;i++)
{
tt=-;
while(num[i])
{
int tmp=num[i]%;
qaq[tmp]++;
zc[++tt]=tmp+;
num[i]/=;
}
for(int i=tt;i>=;i--)
ans1[++num1]=zc[i];
}
printf("%s\n",ans1);
int cnt=;
int total=m;
for(int i=;i<=num1;i++)
{
while(m&&cnt&&ans1[i]>ans[cnt])cnt--,m--;
ans[++cnt]=ans1[i];
}
if(cnt>num1-total+)cnt=num1-total+;
for(int i=;i<=cnt;i++)
printf("%c",ans[i]);
printf("\n");
return ;
//fclose(stdin);
//fclose(stdout);
}
05-15 03:03
查看更多