算法题汇总：其一

TeX格式

在TeX中，左引号是 ``，右引号是 ‘’。将文本转化为TeX格式。
该题涉及字符串的转化，需要将原文中的双引号转化为另一种格式。可以边读边处理,遇到双引号时进行替换。

#include <stdio.h>
int main()
{
    int c, q = 1;
    while ((c = getchar()) != EOF) // 读取到文件结束后结束
    {
        if (c == '"')
        {
            printf("%s", q ? "``" : "''"); // p为真时为一个值，假为另一个值
            q = !q;
        }
        else
            printf("%c", c);
    }
    return 0;
}

WERTYU

输出键盘上往右错一位的字符串原先的样子。
此题并不难，但如果使用switch，代码量会比较大。可以使用字符数组存储字符序，然后在输入中寻找位置，再输出正确的字母。

#include<stdio.h>
char s[] = "1234567890-=QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./";
int main()
{
    int i,c;
    while ((c = getchar()) != EOF)
    {
        for(i = 1; s[i] && s[i] != c; i++); // 没有操作的循环，用于寻找输入字母的位置
        if(s[i]) // 找到了
            putchar(s[i - 1]);
        else
            putchar(c);
    }
    return 0;
}

生成元

若x加上各个数字之和得到y，就说x是y的生成元。给出n < 1e6，求最小生成元。先输入个数，再输入元素。
此处一次性枚举1e6内所有的的正整数，标记其生成元，最后查表即可。

#include <stdio.h>
#include <string.h>
#define maxn 100005
int ans[maxn];

int main()
{
    int T, n;
    memset(ans, 0, sizeof(ans)); // 将该块内容全部设定成指定的值
    for (int m = 1; m < maxn; m++) // 枚举所有正整数
    {
        int x = m, y = m;
        while (x > 0) // x是y的生成元
        {
            y += x % 10;
            x /= 10;
        }
        if (ans[y] == 0 || m < ans[y])
            ans[y] = m; // 在生成元位进行标记
    }
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        printf("%d\n", ans[n]);
    }
    return 0;
}

环状序

指定一串字符串环装序列，找出其字典串最小的排序（指定其开头）。
字典序比较示例：

• 在abandon和abuse中，因为前两个字母相同，abandon中第三个字母a比abuse中的u大，因此前者字典序比后者前；
• 在can和canteen中，二者前面字母相同，但前者字母较少，则前者字典序较前。但在这题中给出的顺序是确定的，不需要考虑该状况。

可以使用a[(p + i) % n]来表示环状数据。

#include <stdio.h>
#include <string.h>
#define max 105

// 环状串s的表示法p是否比表示法q的字典序小
int less(const char *s, int p, int q)
{
    int n = strlen(s);
    for (int i = 0; i < n; i++)
        if (s[(p + i) % n] != s[(q + i) % n])   // 达到上限后又会回到第一位
            return s[(p + i) % n] < s[(q + i) % n];
    return 0;
}

int main()
{
    int T;
    char s[max];
    scanf("%d", &T);
    while (T--)
    {
        scanf("%s", s);
        int ans = 0;    // 表示目前为止字典序最小串的位置
        int n = strlen(s);
        for (int i = 0; i < n; i++)
            if (less(s, i, ans))
                ans = i;
        for (int i = 0; i < n; i++)
            putchar(s[(i + ans) % n]);
        putchar('\n');
    }
    return 0;
}