杭电2019多校第一场,Problem I,String 2019
2024-10-06 20:53:22
题目描述
Tom has a string containing only lowercase letters. He wants to choose a subsequence of the string whose length is k and lexicographical order is the smallest. It's simple and he solved it with ease.
But Jerry, who likes to play with Tom, tells him that if he is able to find a lexicographically smallest subsequence satisfying following 26 constraints, he will not cause Tom trouble any more.
The constraints are: the number of occurrences of the ith letter from a to z (indexed from 1 to 26) must in [Li,Ri].
Tom gets dizzy, so he asks you for help.
But Jerry, who likes to play with Tom, tells him that if he is able to find a lexicographically smallest subsequence satisfying following 26 constraints, he will not cause Tom trouble any more.
The constraints are: the number of occurrences of the ith letter from a to z (indexed from 1 to 26) must in [Li,Ri].
Tom gets dizzy, so he asks you for help.
输入
The input contains multiple test cases. Process until the end of file.
Each test case starts with a single line containing a string S(|S|≤105)and an integer k(1≤k≤|S|).
Then 26 lines follow, each line two numbers Li,Ri(0≤Li≤Ri≤|S|).
It's guaranteed that S consists of only lowercase letters, and ∑|S|≤3×105.
Each test case starts with a single line containing a string S(|S|≤105)and an integer k(1≤k≤|S|).
Then 26 lines follow, each line two numbers Li,Ri(0≤Li≤Ri≤|S|).
It's guaranteed that S consists of only lowercase letters, and ∑|S|≤3×105.
输出
Output the answer string.
If it doesn't exist, output −1.
If it doesn't exist, output −1.
样例输入
aaabbb 3
0 3
2 3
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
样例输出
abb
题解:
将字母下标按字母从前往后依次抽取出来;
然后从前往后依次确定k的每一位应该放的字母;
对于每一位,枚举字母的顺序应该是从a到z,接着判断该字母放上去后是否符合条件,符合则去确定k的下一位字母,不符合则继续循环;
时间复杂度应该是O(26*26*n)。
AC代码:
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+;
int suf_sum[maxn][],l[],r[],used[],n,k,last;
char str[maxn],res[maxn];
vector<int> letter_index[];
int main()
{
while(scanf("%s %d",str,&k)!=EOF)
{
for(int i=;i<=;i++){
scanf("%d %d",&l[i],&r[i]);
letter_index[i].clear();
}
vector<int> ::iterator head[];
memset(used,,sizeof(used));
n=strlen(str);last=-;
for(int i=;i<=n;i++) for(int j=;j<=;j++) suf_sum[i][j]=;
for(int i=n-;i>=;i--){
for(int j=;j<=;j++){
if(str[i]=='a'+j) suf_sum[i][j]=suf_sum[i+][j]+;
else suf_sum[i][j]=suf_sum[i+][j];
}
}
for(int i=;i<=n-;i++){
letter_index[str[i]-'a'].push_back(i);
}
for(int i=;i<=;i++){
head[i]=letter_index[i].begin();
}
bool ans=true;
for(int i=;i<=k-;i++){
bool flag=false;
for(int j=;j<=;j++){
if(used[j]==r[j]) continue;
while(head[j]!=letter_index[j].end() && (*head[j])<=last) head[j]++;
if(head[j]==letter_index[j].end()) continue;
used[j]++;
bool tag=true;
int cnt=,tmp=,pos=(*head[j]);
for(int t=;t<=;t++){
if(suf_sum[pos+][t]+used[t]<l[t]) tag=false;
cnt+=max(,l[t]-used[t]);
tmp+=min(suf_sum[pos+][t],r[t]-used[t]);
}
if(cnt>k--i || tmp<k--i) tag=false;
if(!tag) used[j]--;
else{
res[i]='a'+j;
last=pos;
flag=true;
break;
}
}
if(!flag){
ans=false;
printf("-1\n");
break;
}
}
if(ans){
res[k]='\0';
printf("%s\n",res);
}
}
return ;
}
/*
aaccddaa 6
2 4
0 0
2 2
0 2
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
*/
最新文章
- Linux下查看某进程相关进程
- 我的面经(ing)
- 20145320《Java程序设计》第4周学习总结
- 20145211 《Java程序设计》实验报告五————Java网络编程及安全实验报告
- [转]-Android Studio 快捷键整理分享-SadieYu
- PHP实例 表单数据插入数据库及数据提取 用户注册验证
- 使用Intellij IDEA从零使用Spring MVC
- 解析mysql索引
- win7+64安装PLSQL Developer 32位
- 可以供MFC调用的,QT实现的DLL(qtwinmigrate实现)
- Android-PullToRefresh下拉刷新库基本用法
- 通过linux的iso镜像安装(RPM)扩展工具包
- android4.0下如何判断手机是否有底部物理按键(menu物理按键)
- Centos7下用FastDFS搭建图片服务器
- JVM垃圾收集器-Serial收集器
- centos7安装rabbitmq3.7.9
- ssh多台主机实现互相认证
- 安装centos6.5
- [调试][程序打印]当printf不能用时,使用C++的不定参数来搞定OutputDebugString打印
- windows 自动copy远程服务器文件