# 79 条题解

• @ 2020-02-07 21:55:05

#include<bits/stdc++.h>
using namespace std;
//char a[30];//不能用cin读整个数组
//string a;//但是可以cin一个string
//因为一个string不算一个数组，算是一个封装好的struct，可以直接用cin读的
int f[30];
int a[200];//新的a数组存每一个字母的新字典序大小
//a['a']=0;a['b']=1;
string b;
char sum;
string d[1005];
int s;
//cmp（a，b），cmp的返回值为0或者1，代表当a在排序后放在b的前面，需要符合什么条件
int cmp(string a1,string a2){//希望a1的字典序小于a2的字典序
int l1=a1.length(),l2=a2.length();
for (int i=0;i<min(l1,l2);i++){
//i=1;a1[i]='a' a2[i]='b';k1=0,k2=1;k1<k2
//aabc<abbc
if (a[a1[i]]!=a[a2[i]]) return a[a1[i]]<a[a2[i]];
}
return l1<l2;
}
int main(){
cin>>b;
for (int i=0;i<26;i++) a[b[i]]=i;
int n;
//cout<<a['a'-'a']<<endl; a[97]
//cout<<a['z'-'a']<<endl; a[98]
cin>>n;
for(int i=0;i<n;i++) cin>>d[i];
//for (int i=0;i<n;i++) cout<<d[i]<<endl;
cin>>s;
sort(d,d+n,cmp);
if (s==1) for (int i=0;i<n;i++) cout<<d[i]<<endl;
else for (int i=n-1;i>=0;i--) cout<<d[i]<<endl;
//cout<<int('A')<<endl;
return 0;
}

• @ 2017-02-01 14:17:15

var n,i,j,k:longint; s,t:string;
a:array[1..3000] of string;
function judge(x,y:string):boolean;
var l,l1,l2,i:longint;
begin
l1:=length(x); l2:=length(y);
if l1>l2 then l:=l2 else l:=l1;
for i:=1 to l do
begin
if (pos(x[i],s)>pos(y[i],s)) and (k=1) then exit(true)
else if (pos(x[i],s)>pos(y[i],s)) and (k=0) then exit(false)
else if (pos(x[i],s)<pos(y[i],s)) and (k=1) then exit(false)
else if (pos(x[i],s)<pos(y[i],s)) and (k=0) then exit(true);
end;
if k=1 then exit(l1>l2) else exit(l1<l2);
end;
begin
for i:=1 to n do
for i:=1 to n-1 do
for j:=i+1 to n do
if judge(a[i],a[j]) then
begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
end;
for i:=1 to n do writeln(a[i]);
end.

//累爆了 ^+^

• @ 2022-05-06 12:00:07

发个我自认为简单点的（巨佬勿喷）
```c
#pragma warning (disable : 4996)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define max_size 1000 + 1

char change[26 + 1][2];
char dictionary[26 + 1];
char word[max_size][max_size];

int cmp(const void* p1, const void* p2) {
char* a = (char*)p1;
char* b = (char*)p2;
return strcmp(a, b);
}

int main(void) {

gets(dictionary);
char temp = 'A';
int len_dictionary = strlen(dictionary);
for (int i = 0; i < len_dictionary; i++) {
change[i][0] = dictionary[i];
change[i][1] = temp++;
}
int word_num = 0;
scanf("%d\n", &word_num);
for (int i = 0; i < word_num; i++) {
gets(word[i]);
for(int k = 0; k < strlen(word[i]); k++)
for (int j = 0; j < 26; j++)
if (word[i][k] == change[j][0])
word[i][k] = change[j][1];
}
qsort(word, word_num, sizeof(word[0]), cmp);
for (int i = 0; i < word_num; i++)
for (int k = 0; k < strlen(word[i]); k++)
for (int j = 0; j < 26; j++)
if (word[i][k] == change[j][1])
word[i][k] = change[j][0];
int type = 0;
scanf("%d", &type);
if (type == 1)
for (int i = 0; i < word_num; i++)
printf("%s\n", word[i]);
else
for (int i = word_num - 1; i >= 0; i--)
printf("%s\n", word[i]);
return 0;
}
```

• @ 2017-09-26 21:47:25

var
a:array[1..26,1..1000] of string;
b:array[1..1000] of string;
ch1,ch2:char;
i,j,k,n:longint;
s:string;
p:0..1;
begin
for i:=1 to 26 do
a[i,1]:=s[i];
for n:=1 to n do
k:=1;
for i:=1 to 26 do
for j:=1 to 1000 do
begin
ch1:=a[i,1][1];
ch2:=b[j][1];
if ord(ch1)=ord(ch2) then
begin
k:=k+1;
a[i,k]:=b[j];
end;
end;
if p=1 then
begin
for i:=1 to 26 do
for j:=2 to 1000 do
if a[i,j]<>'' then writeln(a[i,j]);
end
else
begin
for i:=26 downto 1 do
for j:=2 to 1000 do
if a[i,j]<>'' then writeln(a[i,j]);
end;
end.

求解哪里有错？基本思想桶排序。

• @ 2017-04-12 10:31:26
``````
char a[1001][256];
int num[1001];
map<char,int>mp;
bool cmp(int x,int y)
{
for(int i=0; ;i++){
if(mp[a[x][i]]<mp[a[y][i]]) return 1;
if(mp[a[x][i]]>mp[a[y][i]]) return 0;
}
return 0;
}
int main()
{
int n,k;
char t;
for (int i=1;i<=26;i++) {
cin>>t;
mp[t]=i;
}
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%s",a[i]);
num[i]=i;
}
scanf("%d",&k);
sort(num+1,num+n+1,cmp);
if(k==1) for(int i=1;i<=n;i++) printf("%s\n",a[num[i]]);
else for(int i=n;i>=1;i--) printf("%s\n",a[num[i]]);
return 0;
}
/*

abcdefghijklmnopqrstuvwxyz
2
big
small
1

*/
``````
• @ 2017-03-25 18:09:59

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<map>
using namespace std;
int n,h;
string f;
map<char,int>dp;
bool cmp(string a,string b)
{
for(int i=0;i<min(a.size(),b.size());i++)
if(dp[a[i]]<dp[b[i]])
return true;
else if(dp[a[i]]>dp[b[i]])
return false;
return a.size()==min(a.size(),b.size());
}
bool cmp1(string a,string b)
{
for(int i=0;i<min(a.size(),b.size());i++)
if(dp[a[i]]>dp[b[i]])
return true;
else if(dp[a[i]]<dp[b[i]])
return false;
return a.size()!=min(a.size(),b.size());
}
int main()
{
cin>>f;
cin>>n;
string s[n+1];
for(int i=0;i<n;i++)
cin>>s[i];
cin>>h;
for(int i=0;i<26;i++)
dp.insert(make_pair(f[i],i));
if(h==0)
sort(s,s+n,cmp1);
if(h==1)
sort(s,s+n,cmp);
for(int i=0;i<n;i++)
cout<<s[i]<<endl;
return 0;
}
谁编的

• @ 2017-03-21 19:35:19

用map很方便啊

``````#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

vector<string> words;
map<char, int> dictionary;

bool cmp(string a, string b){
for (unsigned i = 0; i < min(a.size(), b.size()); ++i){
if (dictionary[a.at(i)] < dictionary[b.at(i)])
return true;
else if (dictionary[a.at(i)] > dictionary[b.at(i)])
return false;
}
return a.size() == min(a.size(), b.size());
}

bool cmpR(string a, string b){
return !cmp(a, b);
}

int main() {
string dict;
cin >> dict;
for (unsigned i = 0; i < dict.size(); ++i)
dictionary[dict.at(i)] = i;
int n;
cin >> n;
for (int i = 0; i < n; ++i){
string tmp;
cin >> tmp;
words.push_back(tmp);
}
int order;
cin >> order;
order == 1 ? sort(words.begin(), words.end(), cmp) : sort(words.begin(), words.end(), cmpR);
for (const auto i : words)
cout << i << endl;
return 0;
}
``````
• @ 2016-08-23 15:53:17
``````#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;
char word[1001][256],t;
int pos[1001];
int n,k;
map<char,int> dict;
bool cmp(int a,int b)
{
for(int i=0;;i++)
{
if(dict[word[a][i]]<dict[word[b][i]])return true;
if(dict[word[a][i]]>dict[word[b][i]])return false;
}
return false;
}
int main(){
for (int i=1;i<=26;i++) {
t=getchar();
dict[t]=i;
}
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",word[i]);
pos[i]=i;
}
sort(pos+1,pos+n+1,cmp);
scanf("%d",&k);
if(k==1)
for(int i=1;i<=n;i++)
puts(word[pos[i]]);
else
for (int i=n;i>=1;i--)
puts(word[pos[i]]);
}
``````

测试数据 #0: Accepted, time = 15 ms, mem = 808 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 812 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 812 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 812 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 816 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 812 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 812 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 812 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 816 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 812 KiB, score = 10
Accepted, time = 30 ms, mem = 816 KiB, score = 100
map乱入，居然还挺快

• @ 2016-08-13 17:36:02

动态开点的trie居然比快排还慢！！不可理喻
留一个trie代码
n*tle/wa路过
```
#include <bits/stdc++.h>
using namespace std;

void input(char str[])
{
int c, i = 0;
do c = getchar(); while(!isalpha(c));
while (isalpha(c)) {
str[i++] = c;
c = getchar();
}
str[i] = '\0';
}

char table[30];
char str[300];
string strs[1005];
int k = 0;
int md;
class trie {
struct node {
size_t mark;
node *children[26];
node()
{
mark = 0;
for (size_t i = 0; i < 26; i++)
children[i] = NULL;
}
};
node *root;
inline void push(node * &nd, const char *str)
{
// cout << str << endl;
if (!nd) nd = new node;
if (*str == '\0') nd->mark++;
else push(nd->children[*str-'a'], str+1);
}
inline void print(node *nd, const char str[], size_t len)
{
//cout << str << endl;
if (!nd) return;
if (nd->mark)
for (size_t i = 1; i <= nd->mark; i++)
strs[++k] = str;
char *str1 = new char[len+1];
str1 = '\0';
strcpy(str1, str);
str1[len] = '\0';
for (size_t i = 0; i < 26; i++)
if (nd->children[table[i]-'a']) {
str1[len-1] = table[i];
print(nd->children[table[i]-'a'], str1, len+1);
}
}
inline void del(node
&nd)
{
if (!nd) return;
for (size_t i = 0; i < 26; i++)
del(nd->children[i]);
delete nd;
}
public:
inline void push(const char str)
{
push(root, str);
}
inline void print()
{
print(root, "\0", 1);
}
/
~trie()
{
del(root);
}*/
}tree;

int main()
{
input(table);
size_t n;
scanf("%d", &n);
for (size_t i = 1; i <= n; i++) {
//getline(cin, str);
input(str);
tree.push(str);
}
scanf("%d", &md);
tree.print();
if (md)
for (int i = 1; i <= n; i++)
cout << strs[i] << endl;
else
for (int i = n; i >= 1; i--)
cout << strs[i] << endl;
return 0;
}

• @ 2016-08-10 14:54:08

按照题目模拟即可。
```c++ #include<iostream> #include<cstdio> #include<algorithm> #include<string> using namespace std; char c[128],cc[128]; string s[1003]; bool cmp(string a,string b){return a>b;} int main(){ for(char i='a';i<='z';i++){ char c; scanf("%c",&c); ::c[i]=c; cc[c]=i; } int n; scanf("%d",&n); for(int i=0;i<n;i++){ cin>>s[i]; for(int j=0;j<s[i].length();j++) s[i][j]=cc[s[i][j]]; } int p; cin>>p; if(p)sort(s,s+n); else sort(s,s+n,cmp); for(int i=0;i<n;i++){ for(int j=0;j<s[i].length();j++) s[i][j]=c[s[i][j]]; cout<<s[i]<<endl; } return 0; } ```

• @ 2016-07-05 08:55:29

好像没问题

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string.h>
using namespace std;
#define MAX 100000
#define LEN 300

int Book[28];
char Words[MAX][LEN];

int ABiggerB(int a,int b)
{
int i;
for(i=0;;i++)
{
if(Book[Words[a][i]-'a'+1]>Book[Words[b][i]-'a'+1])
{
return 1;
}
else if(Book[Words[a][i]-'a'+1]<Book[Words[b][i]-'a'+1])
{
return 0;
}
else
{
;
}
}
return -1;
}

int main()
{
char sth;
int num;
int forward;
int pos[MAX];
char tmp[LEN];

int f=0;

for(int i=1;i<=26;i++)
{
sth = getchar();
if(sth<='Z'&&sth>='A')
{
Book[sth-'A'+1]=i;
}
else if(sth<='z'&&sth>='a')
{
Book[sth-'a'+1]=i;
}
}
cin >> num;

for(int j=1;j<=num;j++)
{
cin >> Words[j];
pos[j]=j;
}

cin >> forward;

//sort(pos+1,pos+num+1,ABiggerB);

for(int i=num-1;i>=1;i--)
{
f=0;
for(int j=1;j<=i;j++)
{
//cout <<ABiggerB(j,j+1);
if(ABiggerB(j,j+1)==1)
{
f=1;
memmove(tmp,Words[j+1],sizeof(Words[j+1]));
memmove(Words[j+1],Words[j],sizeof(Words[j]));
memmove(Words[j],tmp,sizeof(tmp));
}
}
if(f==0){break;
}
}

if(forward==1)
{
for(int i=1;i<=num;i++)
{
cout << Words[i] << endl;
}
}
else if(forward==0)
{
for(int i=num;i>=1;i--)
{
cout << Words[i] << endl;
}
}

}

• @ 2015-09-10 16:04:01

###哈哈哈哈哈！！！！！
记录信息
评测状态 Accepted
题目 P1500 笨笨的单词排序
递交时间 2015-09-10 16:02:46
代码语言 C++
评测机 VijosEx
消耗时间 124 ms
消耗内存 780 KiB
评测时间 2015-09-10 16:02:48
评测结果
编译成功

测试数据 #0: Accepted, time = 8 ms, mem = 776 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 772 KiB, score = 10
测试数据 #2: Accepted, time = 35 ms, mem = 768 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 772 KiB, score = 10
测试数据 #4: Accepted, time = 10 ms, mem = 768 KiB, score = 10
测试数据 #5: Accepted, time = 3 ms, mem = 776 KiB, score = 10
测试数据 #6: Accepted, time = 1 ms, mem = 772 KiB, score = 10
测试数据 #7: Accepted, time = 4 ms, mem = 780 KiB, score = 10
测试数据 #8: Accepted, time = 14 ms, mem = 772 KiB, score = 10
测试数据 #9: Accepted, time = 19 ms, mem = 776 KiB, score = 10
Accepted, time = 124 ms, mem = 780 KiB, score = 100
代码
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
char s[30];
int dic[30];
char word[1010][260];
int pos[1010];
bool cmp(int a,int b)
{
for(int i=0;;i++)
{
if(dic[word[a][i]-'a'+1]<dic[word[b][i]-'a'+1])return true;
if(dic[word[a][i]-'a'+1]>dic[word[b][i]-'a'+1])return false;
}
return false;
}
int main()
{
scanf("%s",s+1);
for(int i=1;i<=26;i++) dic[s[i]-'a'+1]=i;
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",word[i]);
pos[i]=i;
}
sort(pos+1,pos+n+1,cmp);
int k;
scanf("%d",&k);
if(k==1)
for(int i=1;i<=n;i++)
puts(word[pos[i]]);
else
for(int i=n;i>=1;i--)
puts(word[pos[i]]);
}

• @ 2015-08-04 14:29:47

重定义比较规则，转为普通方式比较，排序即可

• @ 2014-08-20 15:55:54

记得我说过Pascal一长就各种恶心……

var
dic:array['a'..'z']of integer;
word:array[1..1011,1..2]of string;
n,i,j,k,l:integer;
letter:char;

procedure qsort(l,r:integer);
var
i,j:integer;
mid,s:string;
begin
i:=l; j:=r;
mid:=word[(i+j)div 2,2];
repeat
while word[i,2]<mid do inc(i);
while word[j,2]>mid do dec(j);
if i<=j then begin
s:=word[i,1]; word[i,1]:=word[j,1]; word[j,1]:=s;
s:=word[i,2]; word[i,2]:=word[j,2]; word[j,2]:=s;
inc(i); dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if l<j then qsort(l,j);
end;

begin
for i:=1to 26do begin
dic[letter]:=i;
end;
for i:=1to n do begin
l:=length(word[i,1]);
word[i,2]:=word[i,1];
for j:=1to l do
word[i,2][j]:=chr(dic[word[i,1][j]]+ord('a')-1);
end;
qsort(1,n);
if k=1then for i:=1to n do writeln(word[i,1])
else for i:=n downto 1 do writeln(word[i,1]);
end.

• @ 2013-12-04 22:37:29

终于A掉了，之前一直re,,太艰辛了！
为何我看不懂插排？只好重载了一下运算符，用std::sort

###
#include <cstdio>
#include <cstring>
#include <algorithm>

const int MAXN = 255;

char dic[27];
int opt,n;

int pos(char sch){
for (int i=0;i<26;i++){
if (dic[i]==sch)
return i;
}
}

int min(int egA,int egB){
return egA>egB ? egB : egA;
}

struct Word{
char w[MAXN];
int len;

bool operator > (const Word &b) const{
for (int i=0;i<min(b.len,len);i++){
int t1 = pos(w[i]),t2=pos(b.w[i]);
if (t1<t2)
return true;
else if (t1>t2)
return false;
}

return b.len>len;
}

}word[1001];

bool com2(const Word a,const Word b){
return b>a;
}

bool com1(const Word a,const Word b){
return a>b;
}

void solve(){
scanf("%s",dic);
scanf("%d",&n);
for (int i=0;i<n;i++){
scanf("%s",word[i].w);
word[i].len = strlen(word[i].w);
}

scanf("%d",&opt);
if (opt==1)
std::sort(word,word+n,com1);
else
std::sort(word,word+n,com2);

for (int i=0;i<n;i++)
printf("%s\n",word[i].w);
}

int main(){
solve();
return 0;
}

• @ 2013-12-04 22:39:50

为什么这么丑。。

• @ 2013-11-08 10:14:46

var
a:array[0..1000] of string;
data:array['a'..'z'] of longint;
t:string;
pp,i,n,j:longint;
x:char;
function min(a,b:longint):longint;
begin
if a<b then exit(a);
exit(b);
end;
function ok(s1,s2:string):boolean;
var
i,l1,l2,l:longint;
begin
l1:=length(s1);l2:=length(s2);
l:=min(l1,l2);
for i:=1 to l do
if data[s1[i]]<data[s2[i]] then exit(true)
else if data[s1[i]]>data[s2[i]] then exit(false);
if l1<l2 then exit(true);
exit(false);
end;
begin
for i:=1 to 26 do
begin
data[x]:=i;
end;
for i:=1 to n do
if pp=1 then
begin
for i:=1 to n-1 do
for j:=i+1 to n do
if ok(a[j],a[i]) then
begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
end;
end
else
begin
for i:=1 to n-1 do
for j:=i+1 to n do
if ok(a[i],a[j]) then
begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
end;
end;
for i:=1 to n do
writeln(a[i]);
end.
一遍AC。
PS:水题一遍AC也是要实力的！！
这题就是比较时需变通一下。

• @ 2013-11-07 20:24:33

var s:ansistring;
a:array[1..1000]of ansistring;
b:array['a'..'z']of 1..26;
i,j,n,m,k:longint;
c:char;

procedure change;
var t:ansistring;
begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
end;

begin
for i:=1 to 26 do
begin
b[c]:=i;
end;
for i:=1 to n do readln(a[i]);

for i:=1 to n do
for j:=1 to n do
if i<>j then
begin
k:=1;
while a[i][k]=a[j][k] do inc(k);
if (b[a[i][k]]<b[a[j][k]])then change;
end;

if m=1 then
for i:=1 to n do writeln(a[i])
else for i:=n downto 1 do writeln(a[i]);
end.

这个程序哪里不对了？ 同样的程序刷多几次就可以AC了？？

• @ 2009-11-11 17:42:12

rp不错，还好没给输入输出卡住

• @ 2009-11-09 19:27:13

做了水王争霸后觉得用快排，不用插排就挺简单的

不过这样第一次交的时候

max函数在 比如apple，appled或者是appled,apple都是true，但实际上我要的是后者为true.

program p1500;

var str:string;

n,k:longint;

a:array[1..26] of byte;

b:array[1..2000] of string;

procedure init;

var i:longint;

begin

for i:=1 to 26 do a[ord(str[i])-ord('a')+1]:=i;

for i:=1 to n do readln(b[i]);

end;

function max(str1,str2:string):boolean;

var i:longint;

begin

i:=1;

while (a[ord(str1[i])-ord('a')+1]=a[ord(str2[i])-ord('a')+1]) and (ii) do dec(j);

if j>i then sweap(i,j);

while (max(str,b[i])) and (j>i) do inc(i);

if j>i then sweap(i,j);

until i=j;

b[i]:=str;

dec(i); inc(j);

if l

• @ 2009-10-19 22:05:45

交了5次，，，5次输入输出问题，，，我不玩了，不跟1500完了。。我受不了这个输入输出了啊啊啊啊啊啊啊啊啊。..

ID
1500

6

2871

720

25%

2