14070: 【原4070】字符串删除与排序

题目描述

author: 程序设计思想与方法助教组蒋永康 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4070

输入输出描述

输入

• 第一行输入英文字符ch
• 每一行输入一个字符串
• 最后一行单独输入特殊字符@做为结束标志

输出

• 删除ch的新字符串按字典逆序输出
• 每行输出一个字符串

程序运行示例

Sample Input 1

``````e
shangejiao
fudean
teongji
shangcai
@
``````

Sample Output 1

``````tongji
shangjiao
shangcai
fudan
``````

注意

• 不要显示多余的提示信息，避免输出判定错误
• 输出结束后不要输出任何内容，包括空格和换行
• 注意判断输出信息是否符合要求。

BugenZhao's solution

``````//
// Created by BugenZhao on 2019/5/29.
//

//
// Created by BugenZhao on 2019/5/12.
//

#ifndef SBL_BQSORT_H
#define SBL_BQSORT_H

#ifndef SBL_BSORT_H
#define SBL_BSORT_H

namespace bsort {
template<typename Item>
struct greater {
bool operator()(const Item &a, const Item &b) {
return a > b;
}
};

template<typename Item>
struct less {
bool operator()(const Item &a, const Item &b) {
return a < b;
}
};
}

#endif //SBL_BSORT_H

template<typename Item, typename Comparator=bsort::less<Item>>
class BQSort {
static Comparator comparator;

private:
static bool less(Item v, Item w) {
return comparator(v, w);
}

static void exch(Item *a, int i, int j) {
Item t = a[i];
a[i] = a[j];
a[j] = t;
}

public:
static inline void sort(Item *a, int n) {
sort(a, 0, n - 1);
}

static inline void sort(Item *a, int lo, int hi) {
if (hi <= lo) return;
int mid = partition(a, lo, hi);
sort(a, lo, mid - 1);
sort(a, mid + 1, hi);
}

static int partition(Item *a, int lo, int hi) {
Item v = a[lo];
while (true) {
while (lo < hi && less(v, a[hi])) --hi;
if (lo < hi) a[lo] = a[hi], ++lo;
while (lo < hi && less(a[lo], v)) ++lo;
if (lo < hi) a[hi] = a[lo], --hi;
if (lo >= hi) break;
}
a[lo] = v;
return lo;
}
};

template<typename Item, typename Comparator>
Comparator BQSort<Item, Comparator>::comparator = Comparator();

#endif //SBL_BQSORT_H

#include <iostream>
#include <cstring>

using std::ios, std::cin, std::cout, std::endl;
using ll = long long;

struct cmp {
bool operator()(char *a, char *b) {
return strcmp(a, b) > 0;
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
char **strs = new char *[35];
for (int i = 0; i < 35; ++i) {
strs[i] = new char[35];
}
char tmp[35];
char ch;
cin >> ch;
int i = 0;
for (i = 0; i < 35; ++i) {
cin >> tmp;
if (tmp[0] == '@') break;
int len = strlen(tmp);
int q = 0;
for (int p = 0; p <= len; ++p) {
if (tmp[p] == ch) continue;
strs[i][q++] = tmp[p];
}
}
BQSort<char *, cmp>::sort(strs, i);
for (int j = 0; j < i; ++j) {
cout << strs[j];
if (j != i - 1) cout << '\n';
}
return 0;
}
``````

ligongzzz's solution

``````#include "iostream"
#include "cstdio"
#include "cstring"
using namespace std;

int main() {

}
``````

skyzh's solution

``````#include <iostream>
#include <cstring>
using namespace std;

struct String {
char x[50];
};

bool operator<(const String& a, const String& b) {
return strcmp(a.x, b.x) < 0;
}

int partition(String *x, int l, int r) {
String pivot = x[r];
int i = l;
for (int j = l; j < r; j++) {
if (x[j] < pivot) {
swap(x[j], x[i++]);
}
}
swap(x[r], x[i]);
return i;
}

void _quicksort(String *x, int l, int r) {
if (l >= r) return;
int mid = partition(x, l, r);
_quicksort(x, l, mid - 1);
_quicksort(x, mid + 1, r);
}

void shuffle(String *x, int N) {
for (int i = N - 1; i > 0; i--) {
int j = rand() % (i + 1);
swap(x[i], x[j]);
}
}

void quicksort(String *x, int N) {
shuffle(x, N);
_quicksort(x, 0, N - 1);
}

const int MAX_BUF = 100000;
String buffer[MAX_BUF];
int N = 0;

int main() {
char ch;
char tmp[50];
cin >> ch; cin.get();
while(true) {
cin.getline(tmp, 50);
if (strcmp(tmp, "@") == 0) break;
else {
const int size = strlen(tmp);
int j = 0;
for(int i = 0; i < size; i++) {
if (tmp[i] != ch) buffer[N].x[j++] = tmp[i];
}
buffer[N].x[j] = 0;
++N;
}
}
quicksort(buffer, N);
for (int i = N - 1; i >= 0; i--) {
cout << buffer[i].x;
if (i != 0) cout << endl;
}
return 0;
}
``````