admin管理员组文章数量:1666598
Promote Code
Time Limit: 1 Sec Memory Limit: 128 Mb
题目链接http://acm.csu.edu:20080/csuoj/problemset/problem?pid=2329
Description
一天,limojin在eBay上浏览着喜爱的商品,尽管如此,一个Switch对他来说还是太贵了。limojin了解到一种按照升序排列的数字串,称为促销码(promote code),可以使他以更低的价格购入一个Switch。这个时候,Wells神秘兮兮地发过来一串字符。(“NeNohuiroNNiNeteefrsixe”) Wells声称这串字母是他将一串促销码经过加密得到的。
现在已知加密的流程如下:
1.用数字的英文来代替数字(如:134699 -> onethreefoursixninenine)
2.用加密算法对上步得到的字符串进行处理。
不幸的是,健忘的Wells忘记了2中加密算法的具体步骤,只记得加密算法仅仅改变了字符串中字母的排列顺序和大小写。(如:onethreefoursixninenine ->NeNohuiroNNiNeteefrsixe)
对于Wells发来的字符串,你能帮帮limojin恢复促销码吗?limojin能否成功买到开关(switch)来修理家中电器取决于你的决定!
Input
多组数据,数据组数不超过100组,每组数据一行
每行表示一个Wells发送过来的经过加密的促销码
Output
每组数据输出一行表示答案
保证答案长度在1000位以内
Sample Input
onethreefoursixninenine
NeNohuiroNNiNeteefrsixe
Sample Output
134699
134699
emmm,这是一个有技巧的暴力模拟题。。。
我们先将所有字母转化为小写,然后我们从零开始扣:
while (nb['z'-'a'] && nb['e'-'a'] && nb['r'-'a'] && nb['o'-'a']) {
a[0]++;
nb['z'-'a']--;
nb['e'-'a']--;
nb['r'-'a']--;
nb['o'-'a']--;
}
以此类推。。。然后我们发现答案是11369(好像是。。。)然后看看没有开SpeciallJudge。。。也就是说我们的想法有误,必须要将字母全部用上。。。那么我们只能找特殊的了,零独有‘z’,2独有‘w’,4独有‘u’,6独有‘x’:
while (nb['z'-'a'] && nb['e'-'a'] && nb['r'-'a'] && nb['o'-'a']) {
int p=nb['z'-'a'];
a[0]+=p;
nb['z'-'a']-=p;
nb['e'-'a']-=p;
nb['r'-'a']-=p;
nb['o'-'a']-=p;
}
删去这些之后又有一些字母是剩下每个数独有的然后就这样一直下去就好了。。。
以下是AC代码:
#include <bits/stdc++.h>
using namespace std;
char s[10005];
int nb[60],a[1005];
int main()
{
while (~scanf ("%s",s)){
int len=strlen(s);
memset(nb,0,sizeof(nb));
for (int i=0; i<len; i++) if (s[i]>='A' && s[i]<='Z') s[i]+=32;
for (int i=0; i<len; i++)
nb[s[i]-'a']++;
while (nb['z'-'a'] && nb['e'-'a'] && nb['r'-'a'] && nb['o'-'a']) {
int p=nb['z'-'a'];
a[0]+=p;nb['z'-'a']-=p;nb['e'-'a']-=p;
nb['r'-'a']-=p;nb['o'-'a']-=p;
}
while (nb['t'-'a'] && nb['w'-'a'] && nb['o'-'a']) {
int p=nb['w'-'a'];
a[2]+=p;nb['t'-'a']-=p;
nb['w'-'a']-=p;nb['o'-'a']-=p;
}
while (nb['f'-'a'] && nb['u'-'a'] && nb['r'-'a'] && nb['o'-'a']) {
int p=nb['u'-'a'];
a[4]+=p;nb['f'-'a']-=p;nb['u'-'a']-=p;
nb['r'-'a']-=p;nb['o'-'a']-=p;
}
while (nb['s'-'a'] && nb['i'-'a'] && nb['x'-'a']) {
int p=nb['x'-'a'];
a[6]+=p;nb['s'-'a']-=p;
nb['i'-'a']-=p;nb['x'-'a']-=p;
}
while (nb['f'-'a'] && nb['i'-'a'] && nb['v'-'a'] && nb['e'-'a']) {
int p=nb['f'-'a'];
a[5]+=p;nb['f'-'a']-=p;nb['i'-'a']-=p;
nb['v'-'a']-=p;nb['e'-'a']-=p;
}
while (nb['s'-'a'] && nb['e'-'a']>=2 && nb['v'-'a'] && nb['n'-'a']) {
int p=nb['v'-'a'];
a[7]+=p;nb['s'-'a']-=p;nb['n'-'a']-=p;
nb['e'-'a']-=2*p;nb['v'-'a']-=p;
}
while (nb['i'-'a'] && nb['e'-'a'] && nb['g'-'a'] && nb['h'-'a'] && nb['t'-'a']) {
int p=nb['g'-'a'];
a[8]+=p;nb['i'-'a']-=p;nb['g'-'a']-=p;
nb['e'-'a']-=p;nb['h'-'a']-=p;nb['t'-'a']-=p;
}
while (nb['t'-'a'] && nb['h'-'a'] && nb['r'-'a'] && nb['e'-'a']>=2) {
int p=nb['h'-'a'];
a[3]+=p;nb['t'-'a']-=p;nb['e'-'a']-=2*p;
nb['r'-'a']-=p;nb['h'-'a']-=p;
}
while (nb['e'-'a'] && nb['n'-'a'] && nb['o'-'a']) {
int p=nb['o'-'a'];
a[1]+=p;nb['e'-'a']-=p;
nb['n'-'a']-=p;nb['o'-'a']-=p;
}
while (nb['i'-'a'] && nb['e'-'a'] && nb['n'-'a']>=2) {
int p=nb['i'-'a'];
a[9]+=p;nb['i'-'a']-=p;nb['n'-'a']-=2*p;
nb['e'-'a']-=p;
}
for (int i=0; i<=9; i++){
while (a[i]){
printf ("%d",i);a[i]--;
}
}
printf ("\n");
}
return 0;
}
版权声明:本文标题:F.Promote Code---有技巧的模拟 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dianzi/1730074855a1221642.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论