”To be or not to be，” quoth the Bard， ”that
is the question”.
【样例输出】
``To be or not to be， ‘’ quoth the Bard， ``that
is the question‘’.
【代码实现】
// 陈锋
#include
int main() {
int c， first = 1;
char s[2][4] = {”‘’”， ”``”};
while ((c = getchar()) != EOF) {
if (c == ‘”’)
printf(”%s”， s[first])， first ^= 1;
else
printf(”%c”， c);
}
return 0;
}
/*
算法分析请参考:《算法竞赛入门经典（第2版）》例题3-1
注意：本题是如何使用first变量及其xor运算来控制是否为首次输出的
*/
例1-2 【计数排序与IO优化】年龄排序（Age Sort， UVa 11462）
给定n（0＜n≤2 000 000）个居民的年龄（都是1～100的整数），把它们按照从小到大的顺序输出。
【代码实现】
// 陈锋
#include
using namespace std;
#define _for(i， a， b) for (int i = (a); i < (b); i)
typedef long long LL;
const int MAXN = 100;
int main() {
int n， a， cnt[MAXN 4];
while (scanf(”%d”， &n) == 1 && n) {
fill_n(cnt， MAXN 4， 0); _for(i， 0， n) scanf(”%d”， &a)， cnt[a];
_for(i， 0， MAXN) _for(j， 0， cnt[i])
printf(”%d%s”， i， (i == MAXN - 1 && j == cnt[i] - 1) ? ”” : ” ”);
puts(””);
}
}
/*
算法分析请参考:《算法竞赛入门经典—训练指南》升级版1.3节例题17
注意：本题中的fill_n函数比memset更方便，性能更好
*/
如果还要精益求精，可以优化输入输出，进一步降低运行时间，程序如下。
// 刘汝佳
#include
#include
#include // 为了使用isdigit宏
inline int readint() {
char c = getchar(); while(!isdigit(c)) c = getchar();
int x = 0; while(isdigit(c)) { x = x * 10 c - ‘0’; c = getchar(); } return x;
}
int buf[10]; // 声明为全局变量可以减小开销
inline void writeint(int i) { int p = 0;if(i < 0) putchar(‘-’)， i = -i; if(i == 0) p ; // 特殊情况：i等于0时需要输出0，而不是什么也不输出 else while(i) { buf[p ] = i % 10，i /= 10; } for(int j = p - 1; j >= 0; j--) putchar(‘0’ buf[j]); // 逆序输出 }
int main() {
int n， x， c[101];
while(n = readint()) {
memset(c， 0， sizeof(c));
for(int i = 0; i < n; i ) c[readint()] ;
int first = 1;
for(int i = 1; i <= 100; i )
for(int j = 0; j < c[i]; j ) {
if(!first) putchar(‘ ’);
first = 0;
writeint(i);
}
putchar(‘\’);
}
return 0;
}
例1-3 【字符函数；常量数组】回文词（Palindromes， UVa 401）
输入一个字符串，判断它是否为回文串以及镜像串。输入字符串保证不含数字0。所谓回文串，就是反转以后和原串相同，如abba和madam。所谓镜像串，就是左右镜像之后和原串相同，如2S和3AIAE。注意，并不是每个字符在镜像之后都能得到一个合法字符。在本题中，每个字符的镜像如图1-1所示（空白项表示该字符镜像后不能得到一个合法字符）。
图1-1 镜像字符
输入的每行包含一个字符串（保证只有上述字符，不含空白字符），判断它是否为回文串和镜像串（共4种组合）。每组数据之后输出一个空行。
【样例输入】
NOTAPALINDROME
ISAPALINILAPASI
2A3MEAS
ATOYOTA
【样例输出】
NOTAPALINDROME -- is not a palindrome.
ISAPALINILAPASI -- is a regular palindrome.
2A3MEAS -- is a mirrored string.
ATOYOTA -- is a mirrored palindrome.
【代码实现】
// 刘汝佳
#include
using namespace std;
string rev = ”A 3 HIL JM O 2TUVWXY51SE Z 8 ”，
msg[] = {
”not a palindrome”，
”a regular palindrome”，
”a mirrored string”，
”a mirrored palindrome”
};
char r(char c) {
if (isalpha(c)) return rev[c - ‘A’];
return rev[c - ‘0’ 25];
}
int main() {
char s[32];
while (scanf(”%s”， s) == 1) {
int len = strlen(s)， p = 1， m = 1;
for (int i = 0; i < (len 1) / 2; i ) { if (s[i] != s[len - 1 - i]) p = 0; // 不是回文串 if (r(s[i]) != s[len - 1 - i]) m = 0; // 不是镜像串 }
printf(”%s -- is %s.\”， s， msg[m * 2 p]);
}
return 0;
}
/*
算法分析请参考:《算法竞赛入门经典（第2版）》例题3-3
注意：本题中输入字符串应该使用scanf而不是gets，以避免出现读入空行的问题
*/
例1-4 【字典序】环状序列（Circular Sequence， ACM/ICPC Seoul 2004， UVa 1584）
长度为n的环状串有n种表示方法，分别为从某个位置开始顺时针得到的字母序列。例如，图1-2所示的环状串有10种表示方法：CGAGTCAGCT、GAGTCAGCTC、AGTCAGCTCG等。在这些表示法中，字典序小的称为“小表示”。
输入一个长度为n（n≤100）的环状DNA串（只包含A、C、G、T这4种字符）。输入样式对应该串所有表示方法中的一种表示法，你的任务是输出该环状串的小表示。例如， CTCC的小表示是CCCT，CGAGTCAGCT的小表示为AGCTCGAGTC。
【代码实现】
// 刘汝佳
#include
using namespace std;
// 环状串s的表示法p是否比表示法q的字典序小 int less_than(const string& s， int p， int q) { int n = s.length(); for (int i = 0; i < n; i ) { char cp = s[(p i) % n]， cq = s[(q i) % n]; if (cp != cq) return cp < cq; } return 0; // 相等 }
int main() {
ios::sync_with_stdio(false)， cin.tie(0);
int T;
string s;
cin >> T;
while (T--) {
cin >> s;
int ans = 0， n = s.length();
for (int i = 1; i < n; i )
if (less_than(s， i， ans)) ans = i;
for (int i = 0; i < n; i ) cout << (s[(ans i) % n]);
cout << endl;
}
return 0;
}
/*
算法分析请参考:《算法竞赛入门经典（第2版）》例题3-6
注意：main()函数的行可以加速STL的IO操作，但不能再和stdio中的printf混用
同类问题：Periodic Strings， UVa 455
*/
購物車/收銀台(
0
) | 在線留言板
| 付款方式
| 運費計算
| 聯絡我們
| 幫助中心 |
加入書簽
HOME
新書上架
