PAT FOR ALL

#ifdef ONLINE_JUDGE

#else
freopen(“C:\Users\DD\Desktop\input.txt”, “r”, stdin);
freopen(“C:\Users\DD\Desktop\output.txt”,”w”,stdout);

#endif

// #ifdef ONLINE_JUDGE
// #else
// freopen(“/home/master/MOVE/doc/Documents/C/inandout/in.txt”, “r”, stdin);
// freopen(“/home/master/MOVE/doc/Documents/C/inandout/out.txt”, “w”, stdout);
// #endif

✔ 1001 A+B Format Score 20 0001

题目要求：
计算A+B的和，以每三位一个”,”的格式输出。
用s数组记录每3位的数字，然后按照格式输出。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a, b, sum = 0;
    cin >> a;
    cin >> b;
    sum = a + b;
    if (sum == 0) printf("0\n");
    else {
        if (sum < 0) {
            printf("-");
            sum = -sum;
        }
        int s[10], index = 0;
        while (sum) {
            s[index++] = sum % 1000;
            sum /= 1000;
        }
        printf("%d", s[--index]);
        while (index) {
            printf(",%03d", s[--index]);
        }
        printf("\n");
    }
    return 0;
}


-1000000 9
-999,991

还有个留着参考：
#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    string s = to_string(a + b);
    int len = s.length();
    for (int i = 0; i < len; i++) {
        cout << s[i];
        if (s[i] == '-') continue;
        if ((i + 1) % 3 == len % 3 && i != len - 1) cout << ",";
    }
    return 0;
}

✔ 1002 A+B for Polynomials Score 25 0001

相同次数的系数合并，统计系数不为0的项，输出。
a[exp] += num; 比如a[2]也就是x的平方的系数。exp = 0也就是常数项。
因为没有说同一行输入不会出现相同次数的项，因此要+=，当然+=也能很好地处理系数不同的问题。

求8x²－7x+5与3x²－4x+1的差。
解: (8x²－7x+5)－(3x²－4x+1)
=8x²－7x+5－3x²+4x－1
=5x²－3x+4

#include <bits/stdc++.h>
using namespace std;

int main() {
    int k1, k2, exp;
    float num, a[1001] = {0.0};
    scanf("%d", &k1);
    while (k1--) {
        scanf("%d%f", &exp, &num);
        a[exp] += num;
    }
    scanf("%d", &k2);
    while (k2--) {
        scanf("%d%f", &exp, &num);
        a[exp] += num;
    }
    int cnt = 0;
    for (int i = 1000; i >= 0; i--) {
        if (a[i]) cnt++;
    } 
    printf("%d", cnt);
    for (int i = 1000; i >= 0; i--) {
        if (a[i])
            printf(" %d %.1f", i, a[i]);
    }

    return 0;
}


2 1 2.4 0 3.2
2 2 1.5 1 0.5
3 2 1.5 1 2.9 0 3.2

1003 Emergency (25 分)

#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXV = 510;
const int INF = 0x3fffffff;

int n, m, st, ed, G[MAXV][MAXV], weight[MAXV];
int d[MAXV], w[MAXV], num[MAXV];
bool vis[MAXV] = {false};

void Dijkstra(int s) {
    fill(d, d + MAXV, INF);
    memset(num, 0, sizeof(num));
    memset(w, 0, sizeof(w));
    d[s] = 0;
    w[s] = weight[s];
    num[s] = 1;
    for (int i = 0; i < n; i++) {
        int u = -1, MIN = INF;
        for (int j = 0; j < n; j++) {
            if (vis[j] == false && d[j] < MIN) {
                u = j;
                MIN = d[j];
            }
        }
        if (u == -1) {
            return;
        }
        vis[u] = true;
        for (int v = 0; v < n; v++) {
            if (vis[v] == false && G[u][v] != INF) {
                if (d[u] + G[u][v] < d[v]) {
                    d[v] = d[u] + G[u][v];
                    w[v] = w[u] + weight[v];
                    num[v] = num[u];
                } else if (d[u] + G[u][v] == d[v]) {
                    if (w[u] + weight[v] > w[v]) {
                        w[v] = w[u] + weight[v];
                    }
                    num[v] += num[u];
                }
            }
        }
    }
}

int main() {
    scanf("%d%d%d%d", &n, &m, &st, &ed);
    for (int i = 0; i < n; i++) {
        scanf("%d", &weight[i]);
    }
    int u, v;
    fill(G[0], G[0] + MAXV * MAXV, INF);
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &u, &v);
        scanf("%d", &G[u][v]);
        G[v][u] = G[u][v];
    }
    Dijkstra(st);
    printf("%d %d", num[ed], w[ed]);

    return 0;
}


5 6 0 2
1 2 1 5 3
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1

2 4

1004 Counting Leaves

✔ 1005 Spell It Right Score 20 0001

题目大意：
输入一个数字，把数字的每一位相加，用英文输出最后总和的每一位数字。
因为输入的数字可能很大，所以用字符串的形式输入。即使每一位是9，和也不过是900罢了。
之后转换为字符串，输出每一位的数字。

#include <bits/stdc++.h>
using namespace std;

int main() {
    string str;
    cin >> str;
    int sum = 0;
    for (int i = 0; i < str.length(); i++)
        sum += (str[i] - '0');
    string s = to_string(sum);
    string digits[10] =
    {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
    cout << digits[s[0] - '0'];
    for (int i = 1; i < s.length(); i++) {
        cout << " " << digits[s[i] - '0'];
    }

    return 0;
}


12345
one five

✔1006 Sign In and Sign Out 0001

题目大意：
告诉你M个工作人员的出入记录，最早进门的人负责开门，最晚出门的负责关门。
请问，谁开的门和谁关的门。

总体思想是把所有人的进出时间统一到一个可以比较的刻度上，比如，进出时间是当天的第几秒。
之后用2个临时变量保存当前着的进出时间和最早和最晚比，更新最早和最晚时间。
输出最后结果。

#include <bits/stdc++.h>
using namespace std;

int f(int h, int m, int s) {
    return h * 3600 + m * 60 + s;
}

int main() {
    int M, minIN = INT32_MAX, maxOUT = INT32_MIN;
    scanf("%d", &M);
    string unlocked, locked;
    for (int i = 0; i < M; i++) {
        string p;
        cin >> p;
        int h1, m1, s1, h2, m2, s2;
        scanf("%d:%d:%d %d:%d:%d", &h1, &m1, &s1, &h2, &m2, &s2);
        int tempIN = f(h1, m1, s1);
        int tempOUT = f(h2, m2, s2);
        if (tempIN < minIN) {
            unlocked = p;
            minIN = tempIN;
        }
        if (tempOUT > maxOUT) {
            locked = p;
            maxOUT = tempOUT;
        }
    }
    cout << unlocked << " " << locked << endl;

    return 0;
}



3
CS301111 15:30:28 17:00:10
SC3021234 08:00:00 11:25:25
CS301133 21:45:00 21:58:40

SC3021234 CS301133

✔ 1007 Maximum Subsequence Sum 0001

题目大意：
输出最大子序列和，以及首尾元素。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int len;
    scanf("%d", &len);
    int num[len + 1];
    int left = 0, right = len - 1, temp = 0, tempIndex = 0, sum = -1;
    for (int i = 0; i < len; i++) {
        scanf("%d", &num[i]);
        temp += num[i];
        if (temp < 0) {
            temp = 0;
            tempIndex = i + 1;
        } else if (temp > sum) {
            sum = temp;
            left = tempIndex;
            right = i;
        }
    }
    if (sum < 0) sum = 0;
    printf("%d %d %d\n", sum, num[left], num[right]);

    return 0;
}

10
-10 1 2 3 4 -5 -23 3 7 -21

10 1 4

由于In case that the maximum subsequence is not unique, output the one with the smallest indices i and j (as shown by the sample case). 上面的temp要大于sum才更新。

✔ 1008 Elevator (20分) 0001

题目大意：
电梯的初始维持在0层，上升一层需要6秒，下降一层需要4秒，停止所花时间是4秒，问走完所给楼层需要多少时间。
往上是6秒/层，往下是4秒/层，每到一层要停5秒。第一个数字输入的是从0开始开门的次数。然后依次输入n个数计算即可。

#include <bits/stdc++.h>
using namespace std;

int main() {    
    int n, sum = 0, now = 0, floor;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> floor;
        if (floor > now) 
            sum += (floor - now) * 6;
        else 
            sum += (now - floor) * 4;
        sum += 5;
        now = floor;
    }
    cout << sum << endl;

    return 0;
}

✔ 1009 Product of Polynomials (25 分) 0000

题目大意：
求2个多项式A*B后的结果。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int k1, k2, cnt = 0, exp;
    double coe, arr[1001] = {0.0}, ans[2001] = {0.0};
    scanf("%d", &k1);
    for (int i = 0; i < k1; i++) {
        scanf("%d %lf", &exp, &coe);
        arr[exp] += coe;
    }
    scanf("%d", &k2);
    for (int i = 0; i < k2; i++) {
        scanf("%d %lf", &exp, &coe);
        for (int j = 0; j <= 1000; j++) {
            ans[j + exp] += arr[j] * coe;
        }
    }
    for (int i = 2000; i >= 0; i--) {
        if (ans[i]) cnt++;
    }
    printf("%d", cnt);
    for (int i = 2000; i >= 0; i--) {
        if (ans[i])
            printf(" %d %.1f", i, ans[i]);
    }

    return 0;
}


2 1 2.4 0 3.2
2 2 1.5 1 0.5

3 3 3.6 2 6.0 1 1.6

❌❌ 1010 Radix (25 分)

输入N1 N2 tag radix，tag指向第一个数字或则是第二个数字，radix是所选数字的进制数。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cctype>
using namespace std;

// 给定一个数值和一个进制，将它转化为10进制。转化过程中可能产生溢出
long long convert(string n, long long radix) {
    long long sum = 0;
    int index = 0, temp = 0;
    for (auto it = n.rbegin(); it != n.rend(); it++) {
        temp = isdigit(*it) ? *it - '0' : *it - 'a' + 10;
        sum += temp * pow(radix, index++);
    }
    return sum;
}

long long find_radix(string n, long long num) {
    char it = *max_element(n.begin(), n.end());
    long long low = (isdigit(it) ? it - '0' : it - 'a' + 10) + 1;
    long long high = max(num, low);
    while (low <= high) {
        long long mid = (low + high) / 2;
        long long temp = convert(n, mid);
        if (temp < 0 || temp > num) high = mid - 1;
        else if (temp == num) return mid;
        else low = mid + 1;
    }
    return -1;
}

int main() {
    string n1, n2;
    long long tag = 0, radix = 0, result_radix;
    cin >> n1 >> n2 >> tag >> radix;
    result_radix = tag == 1 ? find_radix(n2, convert(n1, radix)) : find_radix(n1, convert(n2, radix));
    if (result_radix != -1) {
        printf("%lld", result_radix);
    } else {
        printf("Impossible");
    }

    return 0;
} 



6 110 1 10

2

✔ 1011 World Cup Betting (20分) 0001

计算彩票最高的获利，在胜平败中选赔率最高的，并输出所选，最后计算获利。

#include <bits/stdc++.h>
using namespace std;

int main() {
    char c[4] = {"WTL"};
    double res = 1.0;
    for (int i = 0; i < 3; i++) {
        double maxVal = 0.0;
        int maxChar = 0;
        for (int j = 0; j < 3; j++) {
            double temp;
            scanf("%lf", &temp);
            if (temp > maxVal) {
                maxVal = temp;
                maxChar = j;
            }
        }
        res *= maxVal;
        printf("%c ", c[maxChar]);
    }
    printf("%.2f", (res * 0.65 - 1) * 2);

    return 0;
}


1.1 2.5 1.7
1.2 3.1 1.6
4.1 1.2 1.1

T T W 39.31

❌ 1012 The Best Rank (25 分)

重点在于：
For each of the M students, print in one line the best rank for him/her, and the symbol of the corresponding rank, separated by a space.

全局变量，初始值为0，用i+1可以保证0输出N/A，对应的学生信息在stu[i-1]。
因为exist[stu[i].id] = i + 1;这一句。

#include <iostream>
#include <algorithm>
using namespace std;

struct student {
    int id, best;
    int score[4], rank[4];
}stu[2005];

int exist[1000000], flag = -1;

bool cmp(student x, student y) {
    return x.score[flag] > y.score[flag];
}

int main() {
    int n, m, id;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%d %d %d %d", &stu[i].id, &stu[i].score[1], &stu[i].score[2], &stu[i].score[3]);
        stu[i].score[0] = (stu[i].score[1] + stu[i].score[2] + stu[i].score[3]) / 3.0 + 0.5;
    }
    // 输入数据，计算平均值
    for (flag = 0; flag <= 3; flag++) {
        sort(stu, stu + n, cmp);
        stu[0].rank[flag] = 1;
        for (int i = 1; i < n; i++) {
            stu[i].rank[flag] = i + 1;
            if (stu[i].score[flag] == stu[i - 1].score[flag]) {
                stu[i].rank[flag] = stu[i - 1].rank[flag];
            }
        }
    }
    // 按照A > C > M > E排序
    for (int i = 0; i < n; i++) {
        exist[stu[i].id] = i + 1;
        stu[i].best = 0;
        int minnum = stu[i].rank[0];
        for (int j = 1; j <= 3; j++) {
            if (stu[i].rank[j] < minnum) {
                minnum = stu[i].rank[j];
                stu[i].best = j;
            }
        }
    }
    // best保存哪门课排名更好
    char c[5] = {'A', 'C', 'M', 'E'};
    for (int i = 0; i < m; i++) {
        scanf("%d", &id);
        int t = exist[id];
        if (t) {
            int best = stu[t - 1].best;
            printf("%d %c\n", stu[t- 1].rank[best], c[best]);
        } else {
            printf("N/A\n");
        }
    }
    
    return 0;
} 

5 6
310101 98 85 88
310102 70 95 88
310103 82 87 94
310104 91 91 91
310105 85 90 90
310101
310102
310103
310104
310105
999999

1 C
1 M
1 E
1 A
3 A
N/A

---------------------------------
3 4
310101 10 85 88
310102 20 95 88
310103 0  87 94
310101
310102
310103
999999

2 A
1 A
1 E
N/A

1013 Battle Over Cities (25 分)

1014 Waiting in Line (30分)

✔1015 Reversible Primes (20 分)

给一个数和进制，判断此数字和翻转后是否依旧是素数。

#include <bits/stdc++.h>
using namespace std;

bool isPrime(int n) {
    if (n <= 1) return false; // 1不是素数
    int sqr = (int)sqrt(1.0 * n);
    for (int i = 2; i <= sqr; i++)
        if (n % i == 0) return false;
    return true;
}

int reverseN(int n, int d) {
    int arr[100] = {0}, len = 0;
    while (n) {
        arr[len++] = n % d;
        n /= d;
    }
    // 10进制的n转为d进制
    int res = 0;
    for (int i = 0; i < len; i++) {
        res = res * d + arr[i];
    }
    // d进制的数的翻转（10进制下）
    return res;
}

int main() {
    int n, d;
    while (scanf("%d", &n) != EOF && n > 0) {
        scanf("%d", &d);
        if (!isPrime(n)) {
            printf("No\n");
            continue;
        }
        n = reverseN(n, d);
        printf("%s", isPrime(n) ? "Yes\n" : "No\n");
    }

    return 0;
}


73 10
23 2
23 10
-2

Yes
Yes
No

1016 Phone Bills (25 分) UN

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
struct node {
    string name;
    int status, month, time, day, hour, minute;
};
bool cmp(node a, node b) {
    return a.name != b.name ? a.name < b.name : a.time < b.time;
}
double billFromZero(node call, int *rate) {
    double total = rate[call.hour] * call.minute + rate[24] * 60 * call.day;
    for (int i = 0; i < call.hour; i++)
        total += rate[i] * 60;
    return total / 100.0;
}
int main() {
    int rate[25] = {0}, n;
    for (int i = 0; i < 24; i++) {
        scanf("%d", &rate[i]);
        rate[24] += rate[i];
    }
    scanf("%d", &n);
    vector<node> data(n);
    for (int i = 0; i < n; i++) {
        cin >> data[i].name;
        scanf("%d:%d:%d:%d", &data[i].month, &data[i].day, &data[i].hour, &data[i].minute);
        string temp;
        cin >> temp;
        data[i].status = (temp == "on-line") ? 1 : 0;
        data[i].time = data[i].day * 24 * 60 + data[i].hour * 60 + data[i].minute;
    }
    sort(data.begin(), data.end(), cmp);
    map<string, vector<node> > custom;
    for (int i = 1; i < n; i++) {
        if (data[i].name == data[i - 1].name && data[i - 1].status == 1 && data[i].status == 0) {
            custom[data[i - 1].name].push_back(data[i - 1]);
            custom[data[i].name].push_back(data[i]);
        }
    }
    for (auto it : custom) {
        vector<node> temp = it.second;
        cout << it.first;
        printf(" %02d\n", temp[0].month);
        double total = 0.0;
        for (int i = 1; i < temp.size(); i += 2) {
            double t = billFromZero(temp[i], rate) - billFromZero(temp[i - 1], rate);
            printf("%02d:%02d:%02d %02d:%02d:%02d %d $%.2f\n", temp[i - 1].day, temp[i - 1].hour, temp[i - 1].minute, temp[i].day, temp[i].hour, temp[i].minute, temp[i].time - temp[i - 1].time, t);
            total += t;
        }
        printf("Total amount: $%.2f\n", total);
    }
    return 0;
}

10 10 10 10 10 10 20 20 20 15 15 15 15 15 15 15 20 30 20 15 15 10 10 10
10
CYLL 01:01:06:01 on-line
CYLL 01:28:16:05 off-line
CYJJ 01:01:07:00 off-line
CYLL 01:01:08:03 off-line
CYJJ 01:01:05:59 on-line
aaa 01:01:01:03 on-line
aaa 01:02:00:01 on-line
CYLL 01:28:15:41 on-line
aaa 01:05:02:24 on-line
aaa 01:04:23:59 off-line

CYJJ 01
01:05:59 01:07:00 61 $12.10
Total amount: $12.10
CYLL 01
01:06:01 01:08:03 122 $24.40
28:15:41 28:16:05 24 $3.85
Total amount: $28.25
aaa 01
02:00:01 04:23:59 4318 $638.80
Total amount: $638.80

❌ 1017 Queueing at Bank (25 分)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct node {
    int come, time;
} tempcustomer;
bool cmp1(node a, node b) {
    return a.come < b.come;
}
int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    vector<node> custom;
    for(int i = 0; i < n; i++) {
        int hh, mm, ss, time;
        scanf("%d:%d:%d %d", &hh, &mm, &ss, &time);
        int cometime = hh * 3600 + mm * 60 + ss;
        if(cometime > 61200) continue;
        tempcustomer = {cometime, time * 60};
        custom.push_back(tempcustomer);
    }
    sort(custom.begin(), custom.end(), cmp1);
    vector<int> window(k, 28800);
    double result = 0.0;
    for(int i = 0; i < custom.size(); i++) {
        int tempindex = 0, minfinish = window[0];
        for(int j = 1; j < k; j++) {
            if(minfinish > window[j]) {
                minfinish = window[j];
                tempindex = j;
            }
        }
        if(window[tempindex] <= custom[i].come) {
            window[tempindex] = custom[i].come + custom[i].time;
        } else {
            result += (window[tempindex] - custom[i].come);
            window[tempindex] += custom[i].time;
        }
    }
    if(custom.size() == 0)
        printf("0.0");
    else
        printf("%.1f", result / 60.0 / custom.size());
    return 0;
}

1018 Public Bike Management (30分)

1019 General Palindromic Number (20 分)

备注：arr数组里是从低位到高位的数字。所以输出得从后到前。十进制转b进制也是取余。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, b;
    scanf("%d %d", &n, &b);
    int arr[100] = {0}, len = 0;
    while (n) {
        arr[len++] = n % b;
        n /= b;
    }
    bool flag = true;
    for (int i = 0; i < len / 2; i++) {
        if (arr[i] != arr[len - 1 - i]) {
            printf("No\n");
            flag = false;
            break;
        }
    }
    if (flag) printf("Yes\n");
    for (int i = len - 1; i >= 0; i--) {
        printf("%d", arr[i]);
        if (i) printf(" ");
    }

    return 0;
}


27 2
Yes
1 1 0 1 1

1020 Tree Traversals (25 分)

定义结构体变量时，关键字struct可以省略吗？
在C++中可以bai，但在duc中不行zhi。

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

struct LNode {
    ElemType data;
    struct LNode *next;
};
typedef struct LNode LNode；
typedef struct LNode* LinkList;

#include <bits/stdc++.h>
using namespace std;

const int maxn = 50;

int n, post[maxn], in[maxn];

typedef struct LNode {
    int data;
    struct LNode* lc;
    struct LNode* rc;
}LNode, *Tree;

Tree creatTree(int postL, int postR, int inL, int inR) {
    if (postL > postR || inL > inR) return NULL;
    LNode* root = new LNode;
    root->data = post[postR];
    int indexRoot;
    for (indexRoot = inL; indexRoot <= inR; indexRoot++) {
        if (in[indexRoot] == post[postR])
            break;
    }
    int lengthOfLeftTree = indexRoot - inL;
    root->lc = creatTree(postL, postL + lengthOfLeftTree - 1, inL, indexRoot - 1);
    root->rc = creatTree(postL + lengthOfLeftTree, postR - 1, indexRoot + 1, inR);
    return root;
}

void BFS(Tree root) {
    int num = 0;
    queue<LNode*> q;
    q.push(root);
    while (!q.empty()) {
        LNode* now = q.front();
        q.pop();
        printf("%d", now->data);
        num++;
        if (num < n) printf(" ");
        if (now->lc != NULL) q.push(now->lc);
        if (now->rc != NULL) q.push(now->rc);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &post[i]);
    }
    // 后序
    for (int i = 0; i < n; i++) {
        scanf("%d", &in[i]);
    }
    // 中序
    Tree root = creatTree(0, n - 1, 0, n - 1);
    BFS(root);

    return 0;
}


7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

4 1 6 3 5 7 2

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct node {
    int index, value;
};
bool cmp(node a, node b) {
    return a.index < b.index;
}
vector<int> post, in;
vector<node> ans;
void pre(int root, int start, int end, int index) {
    if (start > end) return;
    int i = start;
    while (i < end && in[i] != post[root]) i++;
    ans.push_back({index, post[root]});
    pre(root - 1 - end + i, start, i - 1, 2 * index + 1);
    pre(root - 1, i + 1, end, 2 * index + 2);
}
int main() {
    int n;
    scanf("%d", &n);
    post.resize(n);
    in.resize(n);
    for (int i = 0; i < n; i++) scanf("%d", &post[i]);
    for (int i = 0; i < n; i++) scanf("%d", &in[i]);
    pre(n - 1, 0, n - 1, 0);
    sort(ans.begin(), ans.end(), cmp);
    for (int i = 0; i < ans.size(); i++) {
        if (i != 0) cout << " ";
        cout << ans[i].value;
    }
    return 0;
}

❌ 1021 Deepest Root (25 分)

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
int n, maxheight = 0;
vector<vector<int>> v;
bool visit[10010];
set<int> s;
vector<int> temp;
void dfs(int node, int height) {
    if(height > maxheight) {
        temp.clear();
        temp.push_back(node);
        maxheight = height;
    } else if(height == maxheight){
        temp.push_back(node);
    }
    visit[node] = true;
    for(int i = 0; i < v[node].size(); i++) {
        if(visit[v[node][i]] == false)
            dfs(v[node][i], height + 1);
    }
}
int main() {
    scanf("%d", &n);
    v.resize(n + 1);
    int a, b, cnt = 0, s1 = 0;
    for(int i = 0; i < n - 1; i++) {
        scanf("%d%d", &a, &b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int i = 1; i <= n; i++) {
        if(visit[i] == false) {
            dfs(i, 1);
            if(i == 1) {
                if (temp.size() != 0) s1 = temp[0];
                for(int j = 0; j < temp.size(); j++)
                    s.insert(temp[j]);
            }
            cnt++;
        }
    }
    if(cnt >= 2) {
        printf("Error: %d components", cnt);
    } else {
        temp.clear();
        maxheight = 0;
        fill(visit, visit + 10010, false);
        dfs(s1, 1);
        for(int i = 0; i < temp.size(); i++)
            s.insert(temp[i]);
        for(auto it = s.begin(); it != s.end(); it++)
            printf("%d\n", *it);
    }
    return 0;
}

1022 Digital Library (30分)

1023 Have Fun with Numbers (20 分)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int book[10] = {0};
    char s[50];
    scanf("%s", s);
    int flag1 = 0; // 是否进一位
    int flag = 1; // 是否是原数字的重新排列
    int len = strlen(s);
    for (int i = len - 1; i >= 0; i--) {
        int t = s[i] - '0';
        book[t]++;
        t = t * 2 + flag1;
        flag1 = 0;
        if (t >= 10) {
            flag1 = 1;
            t = t - 10;
        }
        s[i] = t + '0';
        book[t]--;
    }
    for (int i = 0; i < 10; i++) {
        if (book[i] != 0) {
            flag = 0;
            break;
        }
    }
    printf("%s", (flag1 == 1 || flag == 0) ? "No\n" : "Yes\n");
    if (flag1) printf("1");
    printf("%s", s);

    return 0;
}


123456789
Yes
246913578

1024 Palindromic Number (25分)

题目大意：

1025 PAT Ranking (25 分)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct student {
    long long no;
    int score, finrank, local, localrank;
};

bool cmp(student a, student b) {
    return a.score != b.score ? a.score > b.score : a.no < b.no;
}

int main() {
#ifdef ONLINE_JUDGE
#else
    freopen("C:\\Users\\DD\\Desktop\\input.txt", "r", stdin);
    freopen("C:\\Users\\DD\\Desktop\\output.txt","w",stdout);
#endif
     
    int n, m;
    scanf("%d", &n);
    vector<student> fin;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &m);
        vector<student> v(m);
        for (int j = 0; j < m; j++) {
            scanf("%lld %d", &v[j].no, &v[j].score);
            v[j].local = i;
        }
        sort(v.begin(), v.end(), cmp);
        v[0].localrank = 1;
        fin.push_back(v[0]);
        for (int j = 1; j < m; j++) {
            v[j].localrank = (v[j].score == v[j - 1].score) ? (v[j - 1].localrank) : (j + 1);
            fin.push_back(v[j]);
        }
    }
    sort(fin.begin(), fin.end(), cmp);
    fin[0].finrank = 1;
    for (int j = 1; j < fin.size(); j++) {
        fin[j].finrank = (fin[j].score == fin[j - 1].score) ? (fin[j - 1].finrank) : (j + 1);
    }
    printf("%d\n", fin.size());
    for (int i = 0; i < fin.size(); i++) {
        printf("%013lld %d %d %d\n", fin[i].no, fin[i].finrank, fin[i].local, fin[i].localrank);
    }

    return 0;
} 

2
5
1234567890001 95
1234567890005 100
1234567890003 95
1234567890002 77
1234567890004 85
4
1234567890013 65
1234567890011 25
1234567890014 100
1234567890012 85

9
1234567890005 1 1 1
1234567890014 1 2 1
1234567890001 3 1 2
1234567890003 3 1 2
1234567890004 5 1 4
1234567890012 5 2 2
1234567890002 7 1 5
1234567890013 8 2 3
1234567890011 9 2 4

题目要求:The locations are numbered from 1 to N. The output must be sorted in nondecreasing order of the final ranks. The testees with the same score must have the same rank, and the output must be sorted in nondecreasing order of their registration numbers.

也就是说，学生的排名和学号都是非递减。那么排名优先是按照分数高在前，低在后。
因此用return a.score != b.score ? a.score > b.score : a.no < b.no;也就说，分数不同时，分数高优先，分数相同时，学号小优先。

1026 Table Tennis (30分)

1027 Colors in Mars (20 分)

#include <iostream>
using namespace std;

int main() {
    char c[14] = {"0123456789ABC"};
    printf("#");
    for (int i = 0; i < 3; i++) {
        int num;
        scanf("%d", &num);
        printf("%c%c", c[num / 13], c[num % 13]);
    }

    return 0;
}

15 43 71
#123456

// 2位的13进制最多可以表示169个数（13*13）从0到168（CC）

1028 List Sorting (25 分)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

const int maxn = 100001;

struct student {
    int no, score;
    char name[10];
};

student s[maxn];

int c;
bool cmp(student a, student b) {
    if (c == 1) {
        return a.no < b.no; // 升序，b严格大于a
    } else if (c == 2) {
        if (strcmp(a.name, b.name) == 0) return a.no < b.no;
        return strcmp(a.name, b.name) <= 0; // 不降序，b大于等于a
    } else {
        if (a.score == b.score) return a.no < b.no;
        return a.score <= b.score; // 不降序，同上
    }
}

int main() {    
    int n;
    scanf("%d%d", &n, &c);
    for (int i = 0; i < n; i++) {
        scanf("%d %s %d", &s[i].no, &s[i].name, &s[i].score);
    }
    sort(s, s + n, cmp);
    for (int i = 0; i < n; i++) {
        printf("%06d %s %d\n", s[i].no, s[i].name, s[i].score);
    }

    return 0;
} 

4 3
000007 James 85
000010 Amy 90
000001 Zoe 60
000002 James 90

1029 Median (25 分)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

const int maxn = 200001;
int num[maxn];

int main() {
    int n, m, t, cnt = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &num[i]);
    }
    num[n + 1] = INT32_MAX;
    cin >> m;
    int midpos = (n + m + 1) / 2, i = 1;
    for (int j = 1; j <= m; j++) {
        scanf("%d", &t);
        while (num[i] < t) {
            cnt++;
            if (cnt == midpos) cout << num[i];
            i++;
        }
        // 如果n数组中的数字小于m数组中的，先放，并计数
        cnt++;
        if (cnt == midpos) cout << t;
        // 否则放m数组中的数，并计数
        // n数组最后一个数放max可以保证跳过上面的while循环
    }
    while (i <= n) {
        cnt++;
        if (cnt == midpos) cout << num[i];
        i++;
    }
    // 如果m数组中的数字用完，还没到中位数的位置，放n数组的数知道满足数量
    // midpos后面是什么都不重要。

    return 0;
} 

4 11 12 13 14
5 9 10 15 16 17

13

1030 Travel Plan (30分)

1031 Hello World for U (20 分)

#include <iostream>
#include <string.h>
using namespace std;

char c[81], u[29][29];

int main() {
    memset(u, ' ', sizeof(u));
    scanf("%s", c);
    int len = strlen(c) + 2;
    int n1 = len / 3, n2 = len / 3 + len % 3, index = 0;
    // 保证n1 = n2 = max {k | k <= n2 for all 3 <= n2 < N } with n1 + n2 + n3 -2 = N
    for (int i = 0; i < n1; i++) u[i][0] = c[index++]; 
    // 输出完整的左列
    for (int i = 1; i <= n2 - 1; i++) u[n1 - 1][i] = c[index++]; 
    // 输出从第二个开始的底
    for (int i = n1 - 2; i >= 0; i--) u[i][n2 - 1] = c[index++]; 
    // 输出从倒数第二个开始的右列
    for (int i = 0; i < n1; i++) {
        for (int j = 0; j < n2; j++) {
            printf("%c", u[i][j]);
        }
        printf("\n");
    }

    return 0;
}

helloworld!
h   !
e   d
l   l
lowor

1032 Sharing (25 分)

#include <cstdio>
using namespace std;
struct NODE {
    char key;
    int next;
    bool flag;
}node[100000];
int main() {
    int s1, s2, n, a, b;
    scanf("%d%d%d", &s1, &s2, &n);
    char data;
    for(int i = 0; i < n; i++) {
        scanf("%d %c %d", &a, &data, &b);
        node[a] = {data, b, false};
    }
    for(int i = s1; i != -1; i = node[i].next)
        node[i].flag = true;
    for(int i = s2; i != -1; i = node[i].next) {
        if(node[i].flag == true) {
            printf("%05d", i);
            return 0;
        }
    }
    // 走过的路为true，s2走到第一个true即为岔路口。
    printf("-1");
    return 0;
}

❌ 1033 To Fill or Not to Fill (25 分)

For each test case, print the cheapest price in a line, accurate up to 2 decimal places. It is assumed that the tank is empty at the beginning. If it is impossible to reach the destination, print The maximum travel distance = X where X is the maximum possible distance the car can run, accurate up to 2 decimal places.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

const int INF = 99999999;

struct station {
    double price, distance;
};

bool cmp(station a, station b) {
    return a.distance < b.distance;
}

int main() {
    double cmax, d, davg;
    int n;
    scanf("%lf %lf %lf %d", &cmax, &d, &davg, &n);
    vector<station> sta(n + 1);
    sta[0].price = 0.0, sta[0].distance = d;
    // sta[0] = {0.0, d}; 
    for (int i = 1; i <= n; i++) {
        scanf("%lf %lf", &sta[i].price, &sta[i].distance);
    }
    sort(sta.begin(), sta.end(), cmp);
    double nowdis = 0.0, maxdis = 0.0, nowprice = 0.0, totalPrice = 0.0, leftdis = 0.0;
    if (sta[0].distance != 0.0) {
        printf("The maximum travel distance = 0.00");
        // 如果起点没有加油站，那压根出不了门
        return 0;
    } else {
        nowprice = sta[0].price;
    }
    while (nowdis < d) {
        maxdis = nowdis + cmax * davg;
        double minPriceDis = 0, minPrice = INF;
        int flag = 0;
        for (int i = 1; i <= n && sta[i].distance <= maxdis; i++) {
            if (sta[i].distance <= nowdis) continue;
            if (sta[i].price < nowprice) {
                totalPrice += (sta[i].distance - nowdis - leftdis) * nowprice / davg;
                leftdis = 0.0;
                nowprice = sta[i].price;
                nowdis = sta[i].distance;
                flag = 1;
                break;
            }
            if (sta[i].price < minPrice) {
                minPrice = sta[i].price;
                minPriceDis = sta[i].distance;
            }
        }
        if (flag == 0 && minPrice != INF) {
            totalPrice += (nowprice * (cmax - leftdis / davg));
            leftdis = cmax * davg - (minPriceDis - nowdis);
            nowprice = minPrice;
            nowdis = minPriceDis;
        }
        if (flag == 0 && minPrice == INF) {
            nowdis += cmax * davg;
            printf("The maximum travel distance = %.2f", nowdis);
            return 0;
        }
    }
    printf("%.2f", totalPrice);

    return 0;
} 

50 1300 12 8
6.00 1250
7.00 600
7.00 150
7.10 0
7.20 200
7.50 400
7.30 1000
6.85 300

749.17

1034 Head of a Gang (30分)

​​

1035 Password (20 分)

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    vector<string> res;
    for (int i = 0; i < n; i++) {
        string name, s;
        cin >> name >> s;
        int len = s.length(), flag = 0;
        for (int j = 0; j < len; j++) {
            if (s[j] == '1') {
                s[j] = '@';
                flag = 1;
            } else if (s[j] == '0') {
                s[j] = '%';
                flag = 1;
            } else if (s[j] == 'l') {
                s[j] = 'L';
                flag = 1;
            } else if (s[j] == 'O') {
                s[j] = 'o';
                flag = 1;
            } else {
                continue;
            }
        }
        if (flag) {
            string t = name + " " + s;
            res.push_back(t);
        }
    }
    int cnt = res.size();
    if (cnt) {
        printf("%d\n", cnt);
        for (int i = 0; i < cnt; i++) {
            cout << res[i] << endl;
        }
    } else if (n == 1) {
        printf("There is 1 account and no account is modified");
    } else {
        printf("There are %d accounts and no account is modified", n);
    }

    return 0;
}

3
Team000002 Rlsp0dfa
Team000003 perfectpwd
Team000001 R1spOdfa

2
Team000002 RLsp%dfa
Team000001 R@spodfa

#　1036 Boys vs Girls (25 分)

#include <iostream>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    string female, male;
    int femalescore = -1, malescore = 101;
    for (int i = 1; i <= n; i++) {
        string name, sex, num;
        int score;
        cin >> name >> sex >> num;
        scanf("%d", &score);
        if (sex == "F") {
            if (femalescore < score) {
                femalescore = score;
                female = name + " " + num;
            }
        } else if (malescore > score) {
            malescore = score;
            male = name + " " + num;
        }
    }
    if (femalescore != -1) {
        cout << female << endl;
    } else {
        printf("Absent\n");
    }
    if (malescore != 101) {
        cout << male << endl;
    } else {
        printf("Absent\n");
    }
    if (femalescore != -1 && malescore != 101) {
        printf("%d", femalescore - malescore);
    } else {
        printf("NA");
    }
    
    return 0;
}

3
Joe M Math990112 89
Mike M CS991301 100
Mary F EE990830 95

Mary EE990830
Joe Math990112
6

1037 Magic Coupon (25 分)

For example, given a set of coupons { 1 2 4 −1 }, and a set of product values { 7 6 −2 −3 } (in Mars dollars M$) where a negative value corresponds to a bonus product. You can apply coupon 3 (with N being 4) to product 1 (with value M$7) to get M$28 back; coupon 2 to product 2 to get M$12 back; and coupon 4 to product 4 to get M$3 back. On the other hand, if you apply coupon 3 to product 4, you will have to pay M$12 to the shop.

2个数组排序，然后负数乘负数，正数乘正数，累加。注意2个指针的边界问题。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int len1, len2, ans = 0, p = 0, q = 0;
    scanf("%d", &len1);
    vector<int> v1(len1);
    for (int i = 0; i < len1; i++) {
        scanf("%d", &v1[i]);
    }
    scanf("%d", &len2);
    vector<int> v2(len2);
    for (int i = 0; i < len2; i++) {
        scanf("%d", &v2[i]);
    }
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    while (p < len1 && q < len2 && v1[p] < 0 && v2[q] < 0) {
        ans += v1[p] * v2[q];
        p++; q++;
    }
    p = len1 - 1, q = len2 - 1;
    while (p >= 0 && q >= 0 && v1[p] > 0 && v2[q] > 0) {
        ans += v1[p] * v2[q];
        p--; q--;
    }
    printf("%d", ans);

    return 0;
}

4
1 2 4 -1
4
7 6 -2 -3

43

1038 Recover the Smallest Number (30分)

1039 Course List for Student (25 分)

告诉你有多少学生，多少门课，然后是每一门课的报考学生。输出每个学生的报考科目。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int getid(char *name) {
    int id = 0;
    for(int i = 0; i < 3; i++)
        id = 26 * id + (name[i] - 'A');
    id = id * 10 + (name[3] - '0');
    return id;
}
const int maxn = 26 * 26 * 26 * 10 + 10;
vector<int> v[maxn];

int main() {
    int n, k, no, num, id = 0;
    char name[5];
    scanf("%d %d", &n, &k);
    for(int i = 0; i < k; i++) {
        scanf("%d %d", &no, &num); // no门课，num个学生
        for(int j = 0; j < num; j++) {
            scanf("%s", name);
            id = getid(name);
            v[id].push_back(no);
        }
    }
    for(int i = 0; i < n; i++) {
        scanf("%s", name);
        id = getid(name);
        sort(v[id].begin(), v[id].end());
        printf("%s %lu", name, v[id].size());
        for(int j = 0; j < v[id].size(); j++)
            printf(" %d", v[id][j]);
        printf("\n");
    }
    return 0;
}

❌⭕ 1040 Longest Symmetric String (25 分) 对递推方程还是有疑虑

#include <iostream>
#include <algorithm>
using namespace std;

int dp[1010][1010];

int main() {
    string s;
    getline(cin, s);
    int len = s.length(), ans = 1;
    for (int i = 0; i < len; i++) {
        dp[i][i] = 1;
        if (i < len - 1 && s[i] == s[i + 1]) {
            dp[i][i + 1] = 1;
            ans = 2;
        }
    }
    // 有左右相邻2个相同
    for (int l = 3; l <= len; l++) { // 从3个字符开始
        for (int i = 0; i + l - 1 < len; i++) { // i是头j是尾
            int j = i + l - 1;
            if (s[i] == s[j] && dp[i + 1][j - 1] == 1) { 
                // 头尾同且头尾往里缩进一个也相同
                dp[i][j] = 1; // dp[i][j]表示i到j对称
                ans = l;
            }
        }
    }
    printf("%d", ans);
    
    return 0;
} 

Is PAT&TAP symmetric?

11

1041 Be Unique (20 分)

#include <iostream>
using namespace std;

int num[100001], cnt[100001];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &num[i]);
        cnt[num[i]]++;
    }
    // 统计每个数字出现的次数
    for (int i = 0; i < n; i++) {
        if (cnt[num[i]] == 1) {
            printf("%d", num[i]);
            return 0;
        }
        // 第一个出现一次的数字即为所求，并立刻结束程序
    }
    printf("None");

    return 0;
}

7 5 31 5 88 67 88 17
31

1042 Shuffling Machine (20 分)

#include <iostream>
using namespace std;

int main() {
    int cnt;
    scanf("%d", &cnt);
    int start[55], end[55], order[55];
    for (int i = 1; i < 55; i++) {
        scanf("%d", &order[i]);
        end[i] = i;
    }
    for (int i = 0; i < cnt; i++) {
        for (int j = 1; j < 55; j++) {
            start[j] = end[j];
        }
        for (int j = 1; j < 55; j++) {
            end[order[j]] = start[j];
        }
    }
    char c[6] = {"SHCDJ"};
    for (int i = 1; i < 55; i++) {
        end[i] = end[i] - 1;
        printf("%c%d", c[end[i] / 13], end[i] % 13 +1);
        // 数字1表示S1，因此13表示S13,13/13 = 1就不再是0位的S了，所以要先-1
        if (i != 54) printf(" ");
    }

    return 0;
}

❌ 1043 Is It a Binary Search Tree (25 分)

#include <cstdio>
#include <vector>
using namespace std;
bool isMirror;
vector<int> pre, post;
void getpost(int root, int tail) {
    if(root > tail) return ;
    int i = root + 1, j = tail;
    if(!isMirror) {
        while(i <= tail && pre[root] > pre[i]) i++;
        while(j > root && pre[root] <= pre[j]) j--;
    } else {
        while(i <= tail && pre[root] <= pre[i]) i++;
        while(j > root && pre[root] > pre[j]) j--;
    }
    if(i - j != 1) return ;
    getpost(root + 1, j);
    getpost(i, tail);
    post.push_back(pre[root]);
}
int main() {
    int n;
    scanf("%d", &n);
    pre.resize(n);
    for(int i = 0; i < n; i++)
        scanf("%d", &pre[i]);
    getpost(0, n - 1);
    if(post.size() != n) {
        isMirror = true;
        post.clear();
        getpost(0, n - 1);
    }
    if(post.size() == n) {
        printf("YES\n%d", post[0]);
        for(int i = 1; i < n; i++)
            printf(" %d", post[i]);
    } else {
        printf("NO");
    }
    return 0;
}

1044 Shopping in Mars (25 分)

给一串数字，子序列之和为M。
For each test case, print i-j in a line for each pair of i ≤ j such that Di + … + Dj = M. Note that if there are more than one solution, all the solutions must be printed in increasing order of i.
如果没有符合条件，使子序列之和-M最小。
If there is no solution, output i-j for pairs of i ≤ j such that Di + … + Dj >M with (Di + … + Dj −M) minimized. Again all the solutions must be printed in increasing order of i.

#include <iostream>
#include <vector>
using namespace std;
vector<int> sum, resultArr;
int n, m;
void Func(int i, int &j, int &tempsum) {
    int left = i, right = n;
    while(left < right) {
        int mid = (left + right) / 2;
        if(sum[mid] - sum[i-1] >= m)
            right = mid;
        else
            left = mid + 1;
            // 为什么直接从mid+1开始，因为下面的循环会一次以每个元素为头
            // 为什么不是mid，因为这时候i到mid的和小于m，那么至少要多一个mid+1才会变大
    }
    j = right;
    tempsum = sum[j] - sum[i-1];
}
int main() {
    scanf("%d%d", &n, &m);
    sum.resize(n+1);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &sum[i]);
        sum[i] += sum[i-1];
    }
    // sum[i]表示1～i的所有数字的和
    int minans = sum[n];
    for(int i = 1; i <= n; i++) {
        int j, tempsum;
        Func(i, j, tempsum);
        if(tempsum > minans) continue;
        if(tempsum >= m) {
            if(tempsum < minans) {
                resultArr.clear();
                minans = tempsum;
                // 如果发现更贴近M的子序列和，清空输出结果
            }
            resultArr.push_back(i);
            resultArr.push_back(j);
        }
    }
    for(int i = 0; i < resultArr.size(); i += 2)
        printf("%d-%d\n", resultArr[i], resultArr[i+1]);
    return 0;
}

1045 Favorite Color Stripe (30分)

重点在Eva is trying to make her own color stripe out of a given one. She would like to keep only her favorite colors in her favorite order by cutting off those unwanted pieces and sewing the remaining parts together to form her favorite color stripe.
从给的例子可以看出，要求保持喜欢颜色的先后顺序，并且使最后条纹的长度尽可能长。（喜欢的颜色可以不出现）

以
6
5 2 3 1 5 6
12 2 2 4 1 5 5 6 3 1 1 5 6
为列，6表示总共6种颜色，5表示喜欢5中颜色，之后是喜欢颜色的优先级顺序。
12表示原条纹的颜色排列，之后依次是12种颜色。

#include <iostream>
#include <vector>
using namespace std;
int book[201], a[10001], dp[10001];
int main() {
    int n, m, x, l, num = 0, maxn = 0;
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; i++) {
        scanf("%d", &x);
        book[x] = i;
    }
    // book[x] = i表示x颜色的下标为i
    scanf("%d", &l);
    for(int i = 0; i < l; i++) {
        scanf("%d", &x);
        if(book[x] >= 1)
            a[num++] = book[x];
    }
    for(int i = 0; i < num; i++) {
        dp[i] = 1;
        for(int j = 0; j < i; j++)
            if(a[i] >= a[j])
                dp[i] = max(dp[i], dp[j] + 1);
        maxn = max(dp[i], maxn);
    }
    printf("%d", maxn);
    return 0;
}

1046 Shortest Distance (20 分)

地铁环状线两点之间的距离为t，最小值为t或则是周长-t。（t为按起点到终点由小到大，大减小而来）

#include <iostream>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    int dis[n + 2] = {0};
    int sum = 0, left, right, cnt;
    for (int i = 1; i <= n; i++) {
        int t;
        scanf("%d", &t);
        sum += t;
        dis[i + 1] = sum;
    } // dis[i]表示i点的绝对距离，dis[1] = 0，dis[n+1]意思是走一圈的距离
    scanf("%d", &cnt);
    for (int i = 0; i < cnt; i++) {
        scanf("%d %d", &left, &right);
        if (left > right) { swap(left, right); }
        int t = dis[right] - dis[left];
        printf("%d\n", min(t, dis[n + 1] - t));
    }

    return 0;
}

5 1 2 4 14 9
3
1 3
2 5
4 1

3
10
7

// 也可以用
    for(int i = 1; i <= n; i++) {
        int temp;
        scanf("%d", &temp);
        sum += temp;
        dis[i] = sum;
    }
// 表示的是从第一个点到i下一个点的距离
// 所以dis[n]是从第一点到n点再毁1点的距离（即总长）
// 两点距离得用int temp = dis[right - 1] - dis[left - 1];来表示。
// 比如2 6，temp = dis[2-1]-dis[6-1]，
// 因为dis[1]表示从1点到2点的距离，dis[5]表示从1点到6点的距离

1047 Student List for Course (25分)

给出学生人数N和学科数K。
接着是N行，每一行是每个学生报名的科目。
输出每一门课有几个学生报名，分别是谁。

#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
char name[40010][5];
vector<int> course[2510];
bool cmp1(int a, int b) {
    return strcmp(name[a], name[b]) < 0;
}
// cmp1的功能是把学生名按照字典序从小到大排列
int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    for(int i = 0; i < n; i++) {
        int cnt, temp;
        scanf("%s %d", name[i], &cnt);
        for(int j = 0; j < cnt; j++) {
            scanf("%d", &temp);
            course[temp].push_back(i);
        }
    }
    for(int i = 1; i <= k; i++) {
        printf("%d %d\n", i, course[i].size());
        sort(course[i].begin(), course[i].end(), cmp1);
        for(int j = 0; j < course[i].size(); j++)
            printf("%s\n", name[course[i][j]]);
    }
    return 0;
}

1048 Find Coins (25 分)

输入N和M，N是你手尚有的硬币数量，M为要求支付的金额。
接下来是N个数字，为硬币的面额。

注意相同金额的硬币可能有多个。输出要求V1+V2=M，V1<=V2，有多种结果取V1最小的。
面额不大于1000，所以从0到1000开始遍历，当前面额银币有，用掉，用掉的必须小于需要支付的金额。
再看，剩下金额的硬币手里是否有，有责直接输出，结束。
如果行不通，当然，拿出来的硬币要放回去。

#include <iostream>
using namespace std;
int a[1001];
int main() {
    int n, m, temp;
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++) {
        scanf("%d", &temp);
        a[temp]++;
    }
    for(int i = 0; i < 1001; i++) {
        if(a[i]) {
            a[i]--;
            if(m > i && a[m-i]) {
                printf("%d %d", i, m - i);
                return 0;
            }
            a[i]++;
        }
    }
    printf("No Solution");
    return 0;
}

1049 Counting Ones (30分)

给一个数N，问再十进制下，从1到N，出现1的次数。

？？？？？？
题目大意：给出一个数字n，求1~n的所有数字里面出现1的个数
分析：这是一道数学问题。从第一位（个位）到最高位，设now为当前位的数字，left为now左边的所有数字构成的数字，right是now右边的所有数字构成的数字。只需要一次次累加对于当前位now来说可能出现1的个数，然后把它们累加即可。a表示当前的个位为1，十位为10，百位为100类推。
对于now，有三种情况：
1.now == 0 : 那么 ans += left a; //因为now==0说明now位只有在left从0~left-1的时候会产生1，所以会产生left次，但是又因为右边会重复从0~999…出现a次
2.now == 1 : ans += left a + right + 1;//now = 1的时候就要比上一步多加一个当now为1的时候右边出现0~right个数导致的now为1的次数
3.now >= 2 : ans += (left + 1) * a;//now大于等于2就左边0~left的时候会在now位置产生1，所以会产生left次，但是又因为右边会重复从0~999…出现a次

#include <iostream>
using namespace std;
int main() {
    int n, left = 0, right = 0, a = 1, now = 1, ans = 0;
    scanf("%d", &n);
    while(n / a) {
        left = n / (a * 10), now = n / a % 10, right = n % a;
        if(now == 0) ans += left * a;
        else if(now == 1) ans += left * a + right + 1;
        else ans += (left + 1) * a;
        a = a * 10;
    }
    printf("%d", ans);
    return 0;
}

1050 String Subtraction (20 分)

#include <iostream>
#include <string.h>
using namespace std;

char s1[10001], s2[10001];
int main() {
    cin.getline(s1, 10001);
    cin.getline(s2, 10001);
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    bool ASCII[300] = {false};
    for (int i = 0; i< len2; i++) {
        ASCII[s2[i]] = true;
    }
    for (int i = 0; i < len1; i++) {
        if (ASCII[s1[i]] == false) {
            printf("%c", s1[i]);
        }
    }

    return 0;
}

// 因为输入会有空格，所以用cin.getline()来读取一行，用scanf遇到空格会停止

They are students.
aeiou

Thy r stdnts.

1051 Pop Sequence (25 分)

M，栈的最大容量，N出栈序列的长度，K个出栈序列等待检查。

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

int main() {
    int m, n, k;
    scanf("%d %d %d", &m, &n, &k);
    for (int i = 0; i < k; i++) {
        bool flag = false;
        stack<int> s;
        vector<int> v(n + 1);
        for (int j = 1; j <= n; j++) {
            scanf("%d", &v[j]);
        }
        int cur = 1;
        for (int j = 1; j <= n; j++) {
            s.push(j);
            if (s.size() > m) break;
            while (!s.empty() && s.top() == v[cur]) {
                s.pop();
                cur++;
            }
        }
        if (cur == n + 1) flag = true;
        if (flag) printf("YES\n");
        else printf("NO\n");
    }
    
    return 0;
} 

5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2

YES
NO
NO
YES
NO

1052 Linked List Sorting (25分)

给出n个节点，把链表中的节点按照key值从小到大排列。

#include <iostream>
#include <algorithm>
using namespace std;
struct NODE {
    int address, key, next;
    bool flag;
}node[100000];
int cmp1(NODE a, NODE b) {
    return !a.flag || !b.flag ? a.flag > b.flag : a.key < b.key;
    // !a.flag || !b.flag为真即有节点不在链表里，往后放a.flag > b.flag，真1在前,假0在后
    // 然后按照递增排列
}
int main() {
    int n, cnt = 0, s, a, b, c;
    scanf("%d%d", &n, &s);
    for(int i = 0; i < n; i++) {
        scanf("%d%d%d", &a, &b, &c);
        node[a] = {a, b, c, false};
    }
    // 输入数据n个节点，s为root
    for(int i = s; i != -1; i = node[i].next) {
        node[i].flag = true;
        cnt++;
    }
    // 链表中的节点标为true，因为可能节点并不存在于链上
    if(cnt == 0) {
        printf("0 -1");
    } else {
        sort(node, node + 100000, cmp1);
        printf("%d %05d\n", cnt, node[0].address);
        for(int i = 0; i < cnt; i++) {
            printf("%05d %d ", node[i].address, node[i].key);
            if(i != cnt - 1)
                printf("%05d\n", node[i + 1].address);
            else
                printf("-1\n");
        }
    }
    return 0;
}

1053 Path of Equal Weight (30分)

1054 The Dominant Color (20 分)

注意输入的分辨率是M列N行，虽然和平时输入有点不一样但和像素是一样的，1024x768，1024是长，768是宽。

#include <iostream>
#include <map>
using namespace std;

int main() {
    int m, n;
    scanf("%d %d", &m, &n);
    map<int, int> pixel;
    int half = n * m / 2;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) { //m列，即每行有m个
            int t;
            scanf("%d", &t);
            pixel[t]++;
            if (pixel[t] > half) {
                printf("%d", t);
                return 0;
            }
        }
    }
    
    return 0;
}

5 3
0 0 255 16777215 24
24 24 0 0 24
24 0 24 24 24

24

1055 The World’s Richest (25 分)

模拟一个福布斯分类排行榜。给N个人的名字，年龄，财富。
给K个筛选标准，包括M最大输出人数（最多100人），年龄范围。

之后按照：The outputs must be in non-increasing order of the net worths. In case there are equal worths, it must be in non-decreasing order of the ages. If both worths and ages are the same, then the output must be in non-decreasing alphabetical order of the names. It is guaranteed that there is no two persons share all the same of the three pieces of information. In case no one is found, output None.输出。

钱多的优先，年龄小的优先，名字字典序小的优先。

为什么vt[i].name没有&？
首先说明 %s格式符 表示用来输入出一个字符串 而字符串是以数组的形式的存储的
c语言中数组名代表该数组的起始地址。 此处,a为数组名 代表的是首地址，所以就不用取地址符了， 再用取地址符号 就重复了 请注意与%c的区别 理解就好啦。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

struct rich {
    char name[10];
    int age, money;
};

int cmp(rich a, rich b) {
    if (a.money != b.money) {
        return a.money > b.money;
    } else if (a.age != b.age) {
        return a.age < b.age;
    } else {
        return (strcmp(a.name, b.name) < 0);
    }
}

int main() {
    int n, k, num, amin, amax;
    scanf("%d %d", &n, &k);
    vector<rich> vt(n), v;
    vector<int> book(205, 0);
    for (int i = 0; i < n; i++) {
        scanf("%s %d %d", vt[i].name, &vt[i].age, &vt[i].money);
    }
    sort(vt.begin(), vt.end(), cmp);
    // 输入数据，排序
    for (int i = 0; i < n; i++) {
        if (book[vt[i].age] < 100) { // book[vt[i].age]为100说明有100个人了
            v.push_back(vt[i]);
            book[vt[i].age]++;
        }
    }
    // 筛去每个年龄层100名后的人以及统计各年龄富豪人数
    for (int i = 0; i < k; i++) {
        scanf("%d %d %d", &num, &amin, &amax);
        vector<rich> t;
        for (int j = 0; j < v.size(); j++) {
            if (v[j].age >= amin && v[j].age <= amax) {
                t.push_back(v[j]);
            }
        }
        // 符合要求的放入临时向量t
        if (i != 0) printf("\n");
        printf("Case #%d:", i + 1);
        int flag = 0;
        for (int j = 0; j < num && j < t.size(); j++) {
            printf("\n%s %d %d", t[j].name, t[j].age, t[j].money);
            flag = 1;
        }
        if (flag == 0) printf("\nNone");
    }

    return 0;

} 

12 4
Zoe_Bill 35 2333
Bob_Volk 24 5888
Anny_Cin 95 999999
Williams 30 -22
Cindy 76 76000
Alice 18 88888
Joe_Mike 32 3222
Michael 5 300000
Rosemary 40 5888
Dobby 24 5888
Billy 24 5888
Nobody 5 0
4 15 45
4 30 35
4 5 95
1 45 50

Case #1:
Alice 18 88888
Billy 24 5888
Bob_Volk 24 5888
Dobby 24 5888
Case #2:
Joe_Mike 32 3222
Zoe_Bill 35 2333
Williams 30 -22
Case #3:
Anny_Cin 95 999999
Michael 5 300000
Alice 18 88888
Cindy 76 76000
Case #4:
None

1056 Mice and Rice (25 分)

输入n为老鼠数量，g为每一组老鼠的最大值，之后从0到n-1个老鼠的体重，最后是老鼠体重的比较序列。
对于每一组老鼠，选出最重的那个，晋级下一轮，本轮的其他老鼠名次相同，直到选出第一名。

结构体node表示老鼠，里面包括weight重量，index是按照排名后的顺序的老鼠的下标，index0是排名前老鼠的下标。rank是最终要输出的老鼠的排名。

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
struct node {
    int weight, index, rank, index0;
};
bool cmp1(node a, node b) {
    return a.index0 < b.index0;
}
int main() {
    int n, g, num;
    scanf("%d%d", &n, &g);
    vector<int> v(n);
    vector<node> w(n);
    for(int i = 0; i < n; i++)
        scanf("%d", &v[i]);
    for(int i = 0; i < n; i++) {
        scanf("%d", &num);
        w[i].weight = v[num];
        w[i].index = i;
        w[i].index0 = num;
    }
    queue<node> q;
    for(int i = 0; i < n; i++)
        q.push(w[i]);
    while(!q.empty()) {
        int size = q.size();
        if(size == 1) {
            node temp = q.front();
            w[temp.index].rank = 1;
            break;
        }
        int group = size / g;
        if(size % g != 0)
            group += 1;
        node maxnode;
        int maxn = -1, cnt = 0;
        for(int i = 0; i < size; i++) {
            node temp = q.front();
            w[temp.index].rank = group + 1;
            q.pop();
            cnt++;
            if(temp.weight > maxn) {
                maxn = temp.weight;
                maxnode = temp;
            }
            if(cnt == g || i == size - 1) {
                cnt = 0;
                maxn = -1;
                q.push(maxnode);
            }
            // 把本组的获胜者放入比较队列，并且重置准备检查下一组
        }
    }
    sort(w.begin(), w.end(), cmp1);
    for(int i = 0; i < n; i++) {
        if(i != 0) printf(" ");
        printf("%d", w[i].rank);
    }
    return 0;
}

另一个参考：

#include <iostream>
#include <vector>
using namespace std;

int main(){
	int n, m, x;
	cin >> n >> m;
	vector<int> mice(n);
	vector<int> order(n);
	int rank[n];
	fill(rank,rank+n,0);
	
	for (int i = 0; i < n; ++i) {
		cin>>mice[i];
	}
	for (int i = 0; i < n; ++i) {
		cin>>order[i];
	}
	vector<int> res;
	int Max, idex, group;
	while (order.size()>1) {
		group = order.size() / m + 1;
		if ((order.size() % m != 0) ) ++group;
		for (int i = 0; i < order.size(); ++i) {
			if (i%m == 0) {
				Max = -1;
				if (i != 0) {
					res.push_back(idex);
				}
			}
			if (Max < mice[order[i]]) {
				Max = mice[order[i]];
				idex = order[i];
			}
			rank[order[i]] = group;
		}
		res.push_back(idex);
		order = res;
		res.clear();
	}
	rank[order[0]] = 1;
	for (int i = 0; i < n; ++i) {
		if (i != 0) cout << ' ';
		cout << rank[i];
	}
	return 0;
}

原文链接：https://blog.csdn.net/CV_Jason/java/article/details/85238006

1057 Stack (30分)

实现一种特殊的栈，增加一种“查找中位数”的功能，返回栈中所有元素的中值。如果n为偶数，则为第n/2的数字，若n是奇数，则是(n+1)/2的数字。

#include <stack>
#include <iostream>
#define lowbit(i) ((i) & (-i))
const int maxn = 100010;
using namespace std;
int c[maxn];

stack<int> s;
void update(int x, int v) {
    for(int i = x; i < maxn; i += lowbit(i))
        c[i] += v;
}
int getsum(int x) {
    int sum = 0;
    for(int i = x; i >= 1; i -= lowbit(i))
        sum += c[i];
    return sum;
}
void PeekMedian() {
    int left = 1, right = maxn, mid, k = (s.size() + 1) / 2; // 偶数加1除2后不改结果
    while(left < right) {
        mid = (left + right) / 2;
        if(getsum(mid) >= k)
            right = mid;
        else
            left = mid + 1;
    }
    printf("%d\n", left);
}
int main() {
#ifdef ONLINE_JUDGE
#else
    freopen("C:\\Users\\DD\\Desktop\\input.txt", "r", stdin);
    freopen("C:\\Users\\DD\\Desktop\\output.txt","w",stdout);
#endif
    int n, temp;
    scanf("%d", &n);
    char str[15];
    for(int i = 0; i < n; i++) {
        scanf("%s", str);
        if(str[1] == 'u') {
            scanf("%d", &temp);
            s.push(temp);
            update(temp, 1);
        } else if(str[1] == 'o') {
            if(!s.empty()) {
                update(s.top(), -1);
                printf("%d\n", s.top());
                s.pop();
            } else {
                printf("Invalid\n");
            }
        } else {
            if(!s.empty())
                PeekMedian();
            else
                printf("Invalid\n");
        }
    }
    return 0;
}

1058 A+B in Hogwarts (20 分)

货币转换，“Seventeen silver Sickles to a Galleon and twenty-nine Knuts to a Sickle, it’s easy enough.”
sum = sum % (17 29)的值最大为28+1629 < 17*29。

#include <iostream>
using namespace std;

int main() {
    long long a, b, c, d, e, f;
    scanf("%lld.%lld.%lld %lld.%lld.%lld", &a, &b, &c, &d, &e, &f);
    long long sum = c + b * 29 + a * 17 * 29 + f + e * 29 + d * 17 * 29;
    long long g = sum / (17 * 29);
    sum = sum % (17 * 29);
    printf("%lld.%lld.%lld", g, sum / 29, sum % 29);

    return 0;
}

3.2.1 10.16.27
14.1.28

1059 Prime Factors (25 分)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
    
vector<int> prime(50000, 1);

int main() {
    for (int i = 2; i * i < 50000; i++) {
        for (int j = 2; j * i < 50000; j++) {
            prime[i * j] = 0;
        }
    }
    // 1到50000的素数   
    long int num;
    scanf("%ld", &num);
    printf("%ld=", num);
    if (num == 1) printf("1");
    bool state = false;
    for (int i = 2; i < 50000 && num >= 2; i++) {
        int cnt = 0, flag = 0;
        while (prime[i] == 1 && num % i == 0) {
            cnt++;
            num /= i;
            flag = 1;
        }
        if (flag) {
            if (state) printf("*");
            printf("%d", i);
            state = true;
        }
        if (cnt >= 2) printf("^%d", cnt);
    } 
    // if (num > 1) printf("%s%ld", state ? "*" : "", num);
    // 为什么会有这一句？果然可以没有
    
    return 0;
} 


97532468

97532468=2^2*11*17*101*1291

输出十万内的素数。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std;
    
vector<int> prime(100000, 1);

int main() {
#ifdef ONLINE_JUDGE
#else
//  freopen("1.txt", "r", stdin);
    freopen("out.txt","w",stdout);
#endif

    for (int i = 2; i * i < 100000; i++) {
        for (int j = 2; j * i < 100000; j++) {
            prime[i * j] = 0;
        }
    }   
    printf("2");
    for (int i = 3; i < 100000; i++) {
        if (prime[i]) printf(" %d", i);
    }
    
    return 0;
}

5万以后的素质：

49939 49943 49957 49991 49993 49999 50021 50023 50033 50047 50051 50053 50069 50077 50087 50093 50101 50111 50119 50123 50129 50131 50147 50153 50159 50177 50207 50221 50227 50231 50261 50263 50273 50287 50291 50311 50321 50329 50333 50341 50359 50363 50377 50383 50387 50411 50417 50423 50441 50459 50461 50497 50503 50513 50527 50539 50543 50549 50551 50581 50587 50591 50593 50599 50627 50647 50651 50671 50683 50707 50723 50741 50753 50767 50773 50777 50789 50821 50833 50839 50849 50857 50867 50873 50891 50893 50909 50923 50929 50951 50957 50969 50971 50989 50993 51001 51031 51043 51047 51059 51061 51071 51109 51131 51133 51137 51151 51157 51169 51193 51197 51199 51203 51217 51229 51239 51241 51257 51263 51283 51287 51307 51329 51341 51343 51347 51349 51361 51383 51407 51413 51419 51421 51427 51431 51437 51439 51449 51461 51473 51479 51481 51487 51503 51511 51517 51521 51539 51551 51563 51577 51581 51593

sqrt(1.0 * INT32_MAX)的值。

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int res = sqrt(1.0 * INT32_MAX);
    printf("%d", res);

    return 0;
}

46340

会出现重复情况吗？会的。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <stack>
#include <cmath>
using namespace std;
    
vector<int> prime(100000, 1);

int main() {
#ifdef ONLINE_JUDGE
#else
//  freopen("1.txt", "r", stdin);
    freopen("out.txt","w",stdout);
#endif
    
    int cnt = 0;
    for (int i = 2; i * i < 100; i++) {
        for (int j = 2; j * i < 100; j++) {
            prime[i * j] = 0;
            printf("%2d %2d %3d ", i, j, i * j);
            cnt++;
            if (cnt % 5 == 0) printf("\n");
        }
    }   
    printf("\n");
    printf("cnt = %d\n\n", cnt);
    printf("2");
    for (int i = 3; i < 100; i++) {
        if (prime[i]) printf(" %d", i);
    }
    
    return 0;
}

2 2 4 2 3 6 2 4 8 2 5 10 2 6 12
2 7 14 2 8 16 2 9 18 2 10 20 2 11 22
2 12 24 2 13 26 2 14 28 2 15 30 2 16 32
2 17 34 2 18 36 2 19 38 2 20 40 2 21 42
2 22 44 2 23 46 2 24 48 2 25 50 2 26 52
2 27 54 2 28 56 2 29 58 2 30 60 2 31 62
2 32 64 2 33 66 2 34 68 2 35 70 2 36 72
2 37 74 2 38 76 2 39 78 2 40 80 2 41 82
2 42 84 2 43 86 2 44 88 2 45 90 2 46 92
2 47 94 2 48 96 2 49 98 3 2 6 3 3 9
3 4 12 3 5 15 3 6 18 3 7 21 3 8 24
3 9 27 3 10 30 3 11 33 3 12 36 3 13 39
3 14 42 3 15 45 3 16 48 3 17 51 3 18 54
3 19 57 3 20 60 3 21 63 3 22 66 3 23 69
3 24 72 3 25 75 3 26 78 3 27 81 3 28 84
3 29 87 3 30 90 3 31 93 3 32 96 3 33 99
4 2 8 4 3 12 4 4 16 4 5 20 4 6 24
4 7 28 4 8 32 4 9 36 4 10 40 4 11 44
4 12 48 4 13 52 4 14 56 4 15 60 4 16 64
4 17 68 4 18 72 4 19 76 4 20 80 4 21 84
4 22 88 4 23 92 4 24 96 5 2 10 5 3 15
5 4 20 5 5 25 5 6 30 5 7 35 5 8 40
5 9 45 5 10 50 5 11 55 5 12 60 5 13 65
5 14 70 5 15 75 5 16 80 5 17 85 5 18 90
5 19 95 6 2 12 6 3 18 6 4 24 6 5 30
6 6 36 6 7 42 6 8 48 6 9 54 6 10 60
6 11 66 6 12 72 6 13 78 6 14 84 6 15 90
6 16 96 7 2 14 7 3 21 7 4 28 7 5 35
7 6 42 7 7 49 7 8 56 7 9 63 7 10 70
7 11 77 7 12 84 7 13 91 7 14 98 8 2 16
8 3 24 8 4 32 8 5 40 8 6 48 8 7 56
8 8 64 8 9 72 8 10 80 8 11 88 8 12 96
9 2 18 9 3 27 9 4 36 9 5 45 9 6 54
9 7 63 9 8 72 9 9 81 9 10 90 9 11 99

cnt = 170

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

PS:

打印素数的几种方法及其优化

https://blog.csdn.net/aixiaodeshushu/article/details/81429285

1060 Are They Equal (25 分)

#include <iostream>
#include <cstring> 
using namespace std;
int main() {
    int n, p = 0, q = 0;
    char a[10000], b[10000], A[10000], B[10000];
    scanf("%d%s%s", &n, a, b);
    int cnta = strlen(a), cntb = strlen(b);
    for(int i = 0; i < strlen(a); i++) {
        if(a[i] == '.') {
            cnta = i;
            break;
        }
    }
    for(int i = 0; i < strlen(b); i++) {
        if(b[i] == '.') {
            cntb = i;
            break;
        }
    }
    // cnta和cntb为a和b两个字符串的小数点下标，初始值为字符串长度
    int indexa = 0, indexb = 0;
    while(a[p] == '0' || a[p] == '.') p++;
    while(b[q] == '0' || b[q] == '.') q++;
    // p和q为非0非小数点的下标
    if(cnta >= p)
        cnta = cnta - p;
    else
        cnta = cnta - p + 1;
    if(cntb >= q)
        cntb = cntb - q;
    else
        cntb = cntb - q + 1;
    if(p == strlen(a))
        cnta = 0;
    if(q == strlen(b))
        cntb = 0;
    while(indexa < n) {
        if(a[p] != '.' && p < strlen(a))
            A[indexa++] = a[p];
        else if(p >= strlen(a))
            A[indexa++] = '0';
        p++;
    }
    while(indexb < n) {
        if(b[q] != '.' && q < strlen(b))
            B[indexb++] = b[q];
        else if(q >= strlen(b))
            B[indexb++] = '0';
        q++;
    }
    // index从0到n-1保存有效数字(有效数字不够用0补)
    // b[q] != '.'是有必要的，比如10.或则是10.1
    if(strcmp(A, B) == 0 && cnta == cntb)
        printf("YES 0.%s*10^%d", A, cnta);
    else
        printf("NO 0.%s*10^%d 0.%s*10^%d" , A, cnta, B, cntb);
    return 0;
}

1061 Dating (20 分)

#include <iostream>
using namespace std;

int main() {
    string a, b, c, d;
    cin >> a >> b >> c >> d;
    char t[2];
    int pos, i = 0, j = 0;
    while (i < a.length() && i < b.length()) {
        if (a[i] == b[i] && (a[i] >= 'A' && a[i] <= 'G')) {
            t[0] = a[i];
            break;
        }
        i++;
    }
    i = i + 1;
    while (i < a.length() && i < b.length()) {
        if (a[i] == b[i] && ((a[i] >= 'A' && a[i] <= 'N') || isdigit(a[i]))) {
            t[1] = a[i];
            break;
        }
        i++;
    }
    // 首先必须相同字符，第二必须满足要么是A到N要么是数字
    while (j < c.length() && j < d.length()) {
        if (c[j] == d[j] && isalpha(c[j])) {
            pos = j;
            break;
        }
        j++;
    }
    string week[7] = {"MON", "TUE", "WED", "THU", "FRI", "SAT", "SUN"};
    int m = isdigit(t[1]) ? t[1] - '0' : t[1] - 'A' + 10;
    cout << week[t[0] - 'A'] << " ";
    printf("%02d:%02d", m, pos);
    return 0;
}

3485djDkxh4hhGE 
2984akDfkkkkggEdsb 
s&hgsfdk 
d&Hyscvnm

THU 14:04

1062 Talent and Virtue (25分)

题目要求，输入N，参与排名的人数，L,参与排名的及格分数要求，H，参与排名优秀非分数要求。德与才均不低于H的成为圣人，按总分由高到低排列（will be ranked in non-increasing order according to their total grades.）才低于H,而德不低于者成为君子，德才均低于H，但德不低于才的成为愚人，剩下的称为小人，按照圣人君子愚人小人排列，同一种人按照总分非递增排列。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct node {
    int num, de, cai;
};
int cmp(struct node a, struct node b) {
    if ((a.de + a.cai) != (b.de + b.cai))
        return (a.de + a.cai) > (b.de + b.cai);
    else if (a.de != b.de)
        return a.de > b.de;
    else
        return a.num < b.num;
}
// 为什么这里是>而不是>=呢，因为总分相同，按德分，德分同，看序号。所以=的情况会下放到下一个判断语句里去。
int main() {
    int n, low, high;
    scanf("%d %d %d", &n, &low, &high);
    vector<node> v[4];
    node temp;
    int total = n;
    for (int i = 0; i < n; i++) {
        scanf("%d %d %d", &temp.num, &temp.de, &temp.cai);
        if (temp.de < low || temp.cai < low)
            total--;
        else if (temp.de >= high && temp.cai >= high)
            v[0].push_back(temp);
        else if (temp.de >= high && temp.cai < high)
            v[1].push_back(temp);
        else if (temp.de < high && temp.cai < high && temp.de >= temp.cai)
            v[2].push_back(temp);
        else
            v[3].push_back(temp);
    }
    printf("%d\n", total);
    for (int i = 0; i < 4; i++) {
        sort(v[i].begin(), v[i].end(), cmp);
        for (int j = 0; j < v[i].size(); j++)
            printf("%d %d %d\n", v[i][j].num, v[i][j].de, v[i][j].cai);
    }
    return 0;
}

1063 Set Similarity (25分)

#include <cstdio>
#include <vector>
#include <set>
using namespace std;
int main() {
    int n, m, k, temp, a, b;
    scanf("%d", &n);
    vector<set<int>> v(n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &m);
        set<int> s;
        for(int j = 0; j < m; j++) {
            scanf("%d", &temp);
            s.insert(temp);
        }
        v[i] = s;
    }
    scanf("%d", &k);
    for(int i = 0; i < k; i++) {
        scanf("%d %d", &a, &b);
        int nc = 0, nt = v[b-1].size();
        for(auto it = v[a-1].begin(); it != v[a-1].end(); it++) {
            if(v[b-1].find(*it) == v[b-1].end())
                nt++;
            else
                nc++;
        }
        double ans = (double)nc / nt * 100;
        printf("%.1f%%\n", ans);
    }
    return 0;
}

1064 Complete Binary Search Tree (30分)

1065 A+B and C (64bit) (20 分)

#include <iostream>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        long long a, b, c;
        scanf("%lld %lld %lld", &a, &b, &c);
        long long sum = a + b;
        if (a > 0 && b > 0 && sum < 0) {
            printf("Case #%d: true\n", i + 1);
        } else if (a < 0 && b < 0 && sum >= 0) {
            printf("Case #%d: false\n", i + 1);
        } else if (sum > c) {
            printf("Case #%d: true\n", i + 1);
        } else {
            printf("Case #%d: false\n", i + 1);
        }
    }

    return 0;
}

3
1 2 3
2 3 4
9223372036854775807 -9223372036854775808 0

Case #1: false
Case #2: true
Case #3: false

因为A、B的大小为[-2^63, 2^63]，用long long 存储A和B的值，以及他们相加的值sum：
如果A > 0, B < 0 或者 A < 0, B > 0，sum是不可能溢出的
如果A > 0, B > 0，sum可能会溢出，sum范围理应为(0, 2^64 – 2]，最大难道不是2的64次方吗为什么还有-2？溢出得到的结果应该是[-2^63, -2]是个负数，所以sum < 0时候说明溢出了
如果A < 0, B < 0，sum可能会溢出，同理，sum溢出后结果是大于0的，所以sum > 0 说明溢出了

1066 Root of AVL Tree (25分)

1067 Sort with Swap(0, i) (25分)

#include <iostream>
using namespace std;
int main() {
    int n, t, cnt = 0, a[100010];
    cin >> n;
    for(int i = 0; i < n; i++){
    	cin >> t;
    	a[t] = i;
    }
    for(int i = 1; i < n; i++) {
        if(i != a[i]) {
            while(a[0] != 0) {
                swap(a[0],a[a[0]]);
                cnt++;
            }
            if(i != a[i]) {
                swap(a[0],a[i]);
                cnt++;
            }
        }
    }
    cout << cnt;
    return 0;
}

cin >> t; a[t] = i; 表示数字t的位置在i。

1068 Find More Coins (30分)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int dp[10010], w[10010];
bool choice[10010][110];
int cmp1(int a, int b){return a > b;}
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
    sort(w + 1, w + n + 1, cmp1);
    for(int i = 1; i <= n; i++) {
        for(int j = m; j >= w[i]; j--) {
            if(dp[j] <= dp[j-w[i]] + w[i]) {
                choice[i][j] = true;
                dp[j] = dp[j-w[i]] + w[i];
            }
        }
    }
    if(dp[m] != m) printf("No Solution");
    else {
        vector<int> arr;
        int v = m, index = n;
        while(v > 0) {
            if(choice[index][v] == true) {
                arr.push_back(w[index]);
                v -= w[index];
            }
            index--;
        }
        for(int i = 0; i < arr.size(); i++) {
            if(i != 0) printf(" ");
            printf("%d", arr[i]);
        }
    }
    return 0;
}

1069 The Black Hole of Numbers

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

bool cmp(int a, int b) {
    return a > b;
}

void to_array(int n, int num[]) {
    for (int i = 0; i < 4; i++) {
        num[i] = n % 10;
        n /= 10;
    }
}

int to_num(int num[]) {
    int sum = 0;
    for (int i = 0; i < 4; i++) {
        sum  = sum * 10 + num[i];
    }
    return sum;
}

int main() {
    int n, MIN, MAX;
    scanf("%d", &n);
    int num[5];
    for (; ;) { // 也可以用while (1)
        to_array(n, num);
        sort(num, num + 4);
        MIN = to_num(num);
        sort(num, num + 4, cmp);
        MAX = to_num(num);
        n = MAX - MIN;
        printf("%04d - %04d = %04d\n", MAX, MIN, n);
        if (n == 0 || n == 6174) break;
    }

    return 0;
}

6767

7766 - 6677 = 1089
9810 - 0189 = 9621
9621 - 1269 = 8352
8532 - 2358 = 6174

1070 Mooncake (25分)

给出仓库容量，不同种类月饼的库存和总价值，问把仓库装满后，最高的货值是多少。采购单价高的，若有空余，采购次高者，以此类推。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct mooncake {
    float price, amount, unitPrice;
};

int cmp(mooncake a, mooncake b) {
    return a.unitPrice > b.unitPrice;
}

int main() {
    int n, total;
    cin >> n >> total;
    vector<mooncake> cake(n);
    for (int i = 0; i < n; i++) cin >> cake[i].amount;
    for (int i = 0; i < n; i++) cin >> cake[i].price;
    for (int i = 0; i < n; i++) {
        cake[i].unitPrice = cake[i].price / cake[i].amount;
    }
    sort(cake.begin(), cake.end(), cmp);
    float res = 0.0;
    for (int i = 0; i < n; i++) {
        if (total >= cake[i].amount) {
            res += cake[i].price;
        } else {
            res += cake[i].unitPrice * total;
            break;
        }
        total -= cake[i].amount;
    }
    printf("%.2f", res);

    return 0;
}

1071 Speech Patterns (25分)

输出出现最多的那个字符串（字母和数字的组合），不区分大小写。
因为输入中可能有空格，因此用getline(cin, s);输入。
空字符串的个数不应该被统计，因此t长度不为0。

#include <iostream>
#include <cctype>
#include <map>
using namespace std;

int main() {
    string s, t;
    map<string, int> m;
    getline(cin, s);
    for (int i = 0; i < s.length(); i++) {
        if (isalnum(s[i])) {
            s[i] = tolower(s[i]);
            t += s[i];
        }
        if (!isalnum(s[i]) || i == s.length() - 1) {
            if (t.length() != 0) m[t]++;
            t = "";
        }
    }
    int resultMax = 0;
    string resultStr = "";
    for (auto it = m.begin(); it != m.end(); it++) {
        if (it->second > resultMax) {
            resultMax = it->second;
            resultStr = it->first;
        }
    }
    cout << resultStr << " " << resultMax << endl;

    return 0;
}

1072 Gas Station (30分)

1073 Scientific Notation (20 分)

stoi（字符串，起始位置，n进制），将 n 进制的字符串转化为十进制。

string str = "1010";
int a = stoi(str, 0, 2);

结果是10。

题目大意：题目给出科学计数法的格式的数字A，要求输出普通数字表示法的A，并保证所有有效位都被保留，包括末尾的0

分析：n保存E后面的字符串所对应的数字，t保存E前面的字符串，不包括符号位。当n<0时表示向前移动，那么先输出0. 然后输出abs(n)-1个0，然后继续输出t中的所有数字；当n>0时候表示向后移动，那么先输出第一个字符，然后将t中尽可能输出n个字符，如果t已经输出到最后一个字符(j == t.length())那么就在后面补n-cnt个0，否则就补充一个小数点。 然后继续输出t剩余的没有输出的字符～

#include <iostream>
using namespace std;
int main() {
    string s;
    cin >> s;
    int i = 0;
    while (s[i] != 'E') i++;
    string t = s.substr(1, i-1);
    int n = stoi(s.substr(i+1));
    if (s[0] == '-') cout << "-";
    if (n < 0) {
        cout << "0.";
        for (int j = 0; j < abs(n) - 1; j++) cout << '0';
        // 科学计数法第一位有个数字，因此少输出一个0
        for (int j = 0; j < t.length(); j++)
            if (t[j] != '.') cout << t[j];
    } else {
        cout << t[0];
        int cnt, j;
        for (j = 2, cnt = 0; j < t.length() && cnt < n; j++, cnt++) cout << t[j];
        if (j == t.length()) {
            for (int k = 0; k < n - cnt; k++) cout << '0';
        } else {
            cout << '.';
            for (int k = j; k < t.length(); k++) cout << t[k];
        }
    }
    return 0;
}

1074 Reversing Linked List (25分)

分析：把地址为temp的数的数值存入data[temp]中，把temp的下一个结点的地址存入next[temp]中。
注意：不一定所有的输入的结点都是有用的，加个计数器sum

#include <iostream>
using namespace std;
int main() { 
    int first, k, n, sum = 0;
    cin >> first >> n >> k;
    int temp, data[100005], next[100005], list[100005], result[100005];
    for (int i = 0; i < n; i++) {
        cin >> temp;
        cin >> data[temp] >> next[temp];
    }
    while (first != -1) {
        list[sum++] = first;
        first = next[first];
    }
    for (int i = 0; i < sum; i++) result[i] = list[i];
    // 初始化
    for (int i = 0; i < (sum - sum % k); i++)
        result[i] = list[i / k * k + k - 1 - i % k];
        // 重中之重在这句
    for (int i = 0; i < sum - 1; i++)
        printf("%05d %d %05d\n", result[i], data[result[i]], result[i + 1]);
    printf("%05d %d -1", result[sum - 1], data[result[sum - 1]]);
    return 0;
}

1075 PAT Judge (25分)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct node {
    int rank, id, total = 0;
    vector<int> score;
    int passnum = 0;
    bool isshown = false;
};
bool cmp1(node a, node b) {
    if(a.total != b.total)
        return a.total > b.total;
    else if(a.passnum != b.passnum)
        return a.passnum > b.passnum;
    else
        return a.id < b.id;
}
 
int main() {
    int n, k, m, id, num, score;
    scanf("%d %d %d", &n, &k, &m);
    vector<node> v(n + 1);
    for(int i = 1; i <= n; i++)
        v[i].score.resize(k + 1, -1);
    vector<int> full(k + 1);
    for(int i = 1; i <= k; i++)
        scanf("%d", &full[i]);
    for(int i = 0; i < m; i++) {
        scanf("%d %d %d", &id, &num, &score);
        v[id].id = id;
        v[id].score[num] = max(v[id].score[num], score);
        if(score != -1)
            v[id].isshown = true;
        else if(v[id].score[num] == -1)
            v[id].score[num] = -2;
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= k; j++) {
            if(v[i].score[j] != -1 && v[i].score[j] != -2)
                v[i].total += v[i].score[j];
            if(v[i].score[j] == full[j])
                v[i].passnum++;
        }
    }
    sort(v.begin() + 1, v.end(), cmp1);
    for(int i = 1; i <= n; i++) {
        v[i].rank = i;
        if(i != 1 && v[i].total == v[i - 1].total)
            v[i].rank = v[i - 1].rank;
    }
    for(int i = 1; i <= n; i++) {
        if(v[i].isshown == true) {
            printf("%d %05d %d", v[i].rank, v[i].id, v[i].total);
            for(int j = 1; j <= k; j++) {
                if(v[i].score[j] != -1 && v[i].score[j] != -2)
                    printf(" %d", v[i].score[j]);
                else if(v[i].score[j] == -1)
                    printf(" -");
                else
                    printf(" 0");
            }
            printf("\n");
        }
    }
    return 0;
}

1076 Forwards on Weibo (30分)

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
int n, l, m, k;
struct node {
    int id, layer;
};
vector<vector<int>> v;
int bfs(node tnode) {
    bool inq[1010] = {false};
    queue<node> q;
    q.push(tnode);
    inq[tnode.id] = true;
    int cnt = 0;
    while(!q.empty()) {
        node top = q.front();
        q.pop();
        int topid = top.id;
        for(int i = 0; i < v[topid].size(); i++) {
            int nextid = v[topid][i];
            if(inq[nextid] == false && top.layer < l) {
                node next = {nextid, top.layer + 1};
                q.push(next);
                inq[next.id] = true;
                cnt++;
            }
        }
    }
    return cnt;
}
 
int main() {
    scanf("%d %d", &n, &l);
    v.resize(n + 1);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &m);
        for(int j = 0; j < m; j++) {
            int temp;
            scanf("%d", &temp);
            v[temp].push_back(i);
        }
    }
    scanf("%d", &k);
    int tid;
    for(int i = 0; i < k; i++) {
        scanf("%d", &tid);
        node tnode = {tid, 0};
        printf("%d\n", bfs(tnode));
    }
    return 0;
}

1077 Kuchiguse (20 分)

重点在于For each test case, print in one line the kuchiguse of the character, i.e., the longest common suffix of all N lines. If there is no such suffix, write nai.
求给出字符串的公共后缀。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    string result;
    scanf("%d\n", &n);
    for (int i = 0; i < n; i++) {
        string s;
        getline(cin, s);
        int len = s.length();
        reverse(s.begin(), s.end());
        if (i == 0) {
            result = s;
        }
        else {
            int lenResult = result.length();
            int minlen = min(len, lenResult);
            for (int j = 0; j < minlen; j++) {
                if (result[j] != s[j]) {
                    result = s.substr(0, j);
                    break;
                }
            }
        }
    }
    reverse(result.begin(), result.end());
    if (result.length() == 0) {
        cout << "nai";
    }
    else {
        cout << result;
    }
    cout << endl;

    return 0;
}

// scanf“%d”少了个\n出错

3
Itai nyan~
Ninjin wa iyadanyan~
uhhh nyan~

nyan~

1078 Hashing (25 分)

给出散列表长度以及插入的元素，问插入位置。
重点在于判断是否为素数（保证散列表长度为素数），以及二次探测法（寻找元素插入位置）。

#include <bits/stdc++.h>
using namespace std;

int m, n, hashTable[10010];

bool isPrime (int num) {
    if (num == 1) return false;
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) return false;
    }
    return true;
}

void insert(int key) {
    for (int step = 0; step < m; step++) {
        int index = (key + step * step) % m;
        if (hashTable[index] == 0) {
            hashTable[index] = 1;
            cout << index;
            return;
        }
    }
    cout << "-";
}

int main() {
    cin >> m >> n;
    while (!isPrime(m)) m++;
    for (int i = 0; i < n; i++) {
        int key;
        cin >> key;
        if (i != 0) cout << " ";
        insert(key);
    }

    return 0;
}

1079 Total Sales of Supply Chain (25分)

pow()函数:求x的y次方的值。
叶子节点为零售商，data保存销售商品的数量，child向量保存子节点。
DFS深度搜索查找叶子节点，累加销售额。
最后再乘以价格p。

#include <bits/stdc++.h>
using namespace std;

double res = 0.0, p, r;

struct node {
    int data;
    vector<int> child;
};

vector<node> v;

void DFS(int index, int depth) {
    if (v[index].child.size() == 0) {
        res += v[index].data * pow(1 + r, depth);
        return;
    }
    else {
        for (int i = 0; i < v[index].child.size(); i++) {
            DFS(v[index].child[i], depth + 1);
        }
    }
}

int main() {
    int n, k, c;
    scanf("%d %lf %lf", &n, &p, &r);
    r = r / 100;
    v.resize(n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &k);
        if (k == 0) {
            scanf("%d", &v[i].data);
        }
        else {
            for (int j = 0; j < k; j++) {
                scanf("%d", &c);
                v[i].child.push_back(c);
            }
        }
    }
    DFS(0, 0);
    printf("%.1f", res * p);

    return 0;
}

1080 Graduate Admission (30分)

1081 Rational Sum (20 分)

每计算一次都计算分子分母的最大公约数，再约分。

#include <bits/stdc++.h>
using namespace std; 

long long gcd(long long a, long long b) {
    return b == 0 ? abs(a) : gcd(b, a % b);
}

int main() {
    int n;
    long long a, b, suma = 0, sumb = 1, GCD;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%lld/%lld", &a, &b);
        GCD = gcd(a, b);
        a = a / GCD;
        b = b / GCD;
        suma = suma * b + a * sumb;
        sumb = sumb * b;
        GCD = gcd(suma, sumb);
        suma = suma / GCD;
        sumb = sumb / GCD;
    }
    long long integer = suma / sumb;
    suma = suma - integer * sumb;
    if (integer != 0) {
        printf("%lld", integer);
        if (suma != 0) {
            printf(" ");
        }
    }
    if (suma != 0) {
        printf("%lld/%lld", suma, sumb);
    }
    if (integer == 0 && suma == 0) {
        printf("0");
    }

    return 0;
}

1082 Read Number in Chinese (25分)

#include <bits/stdc++.h>
using namespace std; 

string num[10] = { "ling","yi", "er", "san", "si", "wu", "liu", "qi", "ba", "jiu" };
string c[6] = { "Ge","Shi", "Bai", "Qian", "Yi", "Wan" };
int J[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000};
vector<string> res;
int main() {
    int n;
    cin >> n;
    if (n == 0) {
        cout << "ling";
        return 0;
    }
    if (n < 0) {
        cout << "Fu ";
        n = -n;
    }
    int part[3];
    part[0]= n / 100000000; 
    part[1]= (n % 100000000) / 10000;
    part[2] = n % 10000;
    bool zero = false; //是否在非零数字前输出合适的ling
    int printCnt = 0; //用于维护单词前没有空格，之后输入的单词都在前面加一个空格。
    for (int i = 0; i < 3; i++) {
        int temp = part[i]; //三个部分，每部分内部的命名规则都一样，都是X千X百X十X
        for (int j = 3; j >= 0; j--) {
            int curPos = 8 - i * 4 + j; //当前数字的位置
            if (curPos >= 9) continue; //最多九位数
            int cur = (temp / J[j]) % 10;//取出当前数字
            if (cur != 0) {
                if (zero) {
                    printCnt++ == 0 ? cout<<"ling" : cout<<" ling";
                    zero = false;
                }
                if (j == 0)
                    printCnt++ == 0 ? cout << num[cur] : cout << ' ' << num[cur]; //在个位，直接输出
                else                             
                    printCnt++ == 0 ? cout << num[cur] << ' ' << c[j] : cout << ' ' << num[cur] << ' ' << c[j]; //在其他位，还要输出十百千
            } else {
                if (!zero && j != 0 && n / J[curPos] >= 10) zero = true;   //注意100020这样的情况
            }
        }
        if (i != 2 && part[i]>0) cout << ' ' << c[i + 4]; //处理完每部分之后，最后输出单位，Yi/Wan
    }
    return 0;
}

1083 List Grades (25分)

因为保证每个人的grade不同，所以从高到低排序就可以，不用考虑相同的情况。
不在区间内的，grade赋值-1，往后放，else满足条件的计数cnt++。

#include <bits/stdc++.h>
using namespace std; 

struct student {
    char name[11];
    char id[11];
    int grade;
};

bool cmp1(student a, student b) {
    return a.grade > b.grade;
}

int main() {
    int n, low, high, cnt = 0;
    scanf("%d", &n);
    vector<student> v(n);
    for (int i = 0; i < n; i++) {
         scanf("%s %s %d", &v[i].name, &v[i].id, &v[i].grade);
    }
    scanf("%d %d", &low, &high);
    for (int i = 0; i < n; i++) {
        if (v[i].grade < low || v[i].grade > high) {
            v[i].grade = -1;
        }
        else {
            cnt++;
        }
    }
    sort(v.begin(), v.end(), cmp1);
    if (cnt == 0) printf("NONE");
    else {
        for (int i = 0; i < cnt; i++) {
            printf("%s %s\n", v[i].name, v[i].id);
        }
    }

    return 0;
}

1084 Broken Keyboard (20 分)

s2没有出现s1中的字符，并且转换大写后没有出现在答案中（答案不用重复出现相同），把这个字符加入答案。

#include <bits/stdc++.h>
using namespace std; 

int main() {
    string s1, s2, res;
    cin >> s1 >> s2;
    for (int i = 0; i < s1.length(); i++) {
        if (s2.find(s1[i]) == string::npos && res.find(toupper(s1[i])) == string::npos) {
            res += toupper(s1[i]);
        }
    }
    cout << res << endl;

    return 0;
}

7_This_is_a_test
_hs_s_a_es

7TI

1085 Perfect Sequence (25分)

当res发生变化后，for循环里是用的老res还是新的？？应该是新的。

#include <bits/stdc++.h>
using namespace std; 

int main() {
    int n;
    long long p;
    scanf("%d %lld", &n, &p);
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    sort(v.begin(), v.end());
    int res = 0, temp = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + res; j < n; j++) {
            if (v[j] <= v[i] * p) {
                temp = j - i + 1; // 当j和i是同一个且满足条件时，个数至少为1
                if (temp > res) {
                    res = temp;
                }
            }
            else {
                break; // 之前的v[j]太大了，那么，比v[j+1]更大，就没必要继续往前走
            }
        }
    }
    cout << res;

    return 0;
}

1086 Tree Traversals Again (25分)

入栈顺序是二叉树的前序遍历，出栈顺序是中序遍历。已知这2两个的顺序，就可以确定一颗树。要求输出这一棵树的后序遍历。

root为当前子树的根结点在前序pre中的下标，start和end为当前子树的最左边和最右边的结点在中序in中的下标。用i找到当前子树的根结点root在中序中的下标，然后左边和右边就分别为当前根结点root的左子树和右子树。递归实现

#include <bits/stdc++.h>
using namespace std; 
vector<int> pre, in, post, value;
void postorder(int root, int start, int end) {
    if (start > end) return;
    int i = start;
    while (i < end && in[i] != pre[root]) i++;
    postorder(root + 1, start, i - 1);
    postorder(root + 1 + i - start, i + 1, end);
    post.push_back(pre[root]);
}
int main() {
    int n;
    scanf("%d", &n);
    char str[5];
    stack<int> s;
    int key=0;
    while (~scanf("%s", str)) {
        if (strlen(str) == 4) {
            int num;
            scanf("%d", &num);
            value.push_back(num);
            pre.push_back(key);
            s.push(key++);
        } else {
            in.push_back(s.top());
            s.pop();
        }
    }
    postorder(0, 0, n - 1);
    printf("%d", value[post[0]]);
    for (int i = 1; i < n; i++)
        printf(" %d",value[post[i]]);
    return 0;
}

另外一个

int N,cur;
vector<int> preOrder;
vector<int> inOrder;
 
typedef struct TreeNode *Node;
struct TreeNode{
    int num;
    Node left,right;
 
    TreeNode(){
        left = NULL;
        right = NULL;
    }
 
};
 
int findRootIndex(int rootNum){
 
    for(int i = 0;i < N; i++){
        if(inOrder[i] == rootNum){
            return i;
        }
    }
    return -1;
 
}
 
Node CreateTree(int left, int right){
    if(left > right) return NULL;
    int root = preOrder[cur];
    cur++;
    int rootIndex = findRootIndex(root);
    Node T = new TreeNode();
    T->num = root;
    if(left != right){
        T->left = CreateTree(left,rootIndex-1);
        T->right = CreateTree(rootIndex+1,right);
    }
    return T;
 
}
 
bool firstOutPut = true;
void PostOrder(Node T){
    if(!T) return;
    PostOrder(T->left);
    PostOrder(T->right);
    if(firstOutPut){
        printf("%d",T->num);
        firstOutPut = false;
    }else{
        printf(" %d",T->num);
    }
}
 
 
int main()
{
    stringstream ss;
    string Nstr;
    getline(cin,Nstr);
    ss << Nstr;
    ss >> N;
    ss.clear();
    string input;
    stack<int> stk;
    int value;
    for(int i = 0; i < N * 2; i++){
        getline(cin,input);
        if(input[1] == 'u'){
            string num = input.substr(5);
            ss << num;
            ss >> value;
            ss.clear();
            stk.push(value);
            preOrder.push_back(value);
        }else{
            value = stk.top();
            stk.pop();
            inOrder.push_back(value);
        }
    }
    Node T = CreateTree(0,N-1);
    PostOrder(T);
    return 0;
}

1087 All Roads Lead to Rome (30分)

1088 Rational Arithmetic (20 分) !!!

给2个有理数，分别计算它们的相加相减相乘相处后的结果，并按要求格式输出。
重点在这个格式化有理数的函数f。

#include <bits/stdc++.h>
using namespace std; 

long long a, b, c, d;

long long GCD(long long a, long long b) {
    return b == 0 ? abs(a) : GCD(b, a % b);
}

void f(long long a, long long b) {
    if (a == 0) {
        printf("0");
        return;
    }
    if (b == 0) {
        printf("Inf");
        return;
    }
    int flag = (a < 0 && b > 0) || (a > 0 && b < 0);
    a = abs(a), b = abs(b);
    long long integer = a / b;
    if (flag) {
        printf("(-");
    }
    if (integer) {
        printf("%lld", integer);
    }
    if (a % b == 0) {
        if (flag) {
            printf(")");
        }
        return; 
    }
    if (integer != 0) {
        printf(" ");
    }
    long long gcdval = GCD(a, b);
    a = a - integer * b;
    a = a / gcdval, b = b / gcdval;
    printf("%lld/%lld", a, b);
    if (flag) {
        printf(")");
    }
    // printf("%lld/%lld%s", m, n, flag ?  ")" : ""); 也很不错
}

int main() {
    scanf("%lld/%lld %lld/%lld", &a, &b, &c, &d);
    f(a, b);
    printf(" + ");
    f(c, d);
    printf(" = ");
    f(a * d + b * c, b * d);
    printf("\n");

    f(a, b);
    printf(" - ");
    f(c, d);
    printf(" = ");
    f(a * d - b * c, b * d);
    printf("\n");

    f(a, b);
    printf(" * ");
    f(c, d);
    printf(" = ");
    f(a * c, b * d);
    printf("\n");

    f(a, b);
    printf(" / ");
    f(c, d);
    printf(" = ");
    f(a * d, b * c);
    printf("\n");

    return 0;
}

2/3 -4/2

2/3 + (-2) = (-1 1/3)
2/3 - (-2) = 2 2/3
2/3 * (-2) = (-1 1/3)
2/3 / (-2) = (-1/3)

1089 Insert or Merge (25分)

给一个原始序列和一个用某种排序算法产生的中间序列，问用的是那种排序方法（插入还是并归），并输出最后排序的结果。

直到a模拟到b的状态前，都会一直归并下去，直到a和b一样，这时候，flag为0，再并归一次即是结果。

#include <bits/stdc++.h>
using namespace std;

int n, a[110], b[110];

void printOut() {
    for (int i = 0; i < n; i++) {
        if (i != 0) printf(" ");
        printf("%d", a[i]);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &b[i]);
    }
    int pos1;
    for (int i = 0; i < n - 1; i++) {
        if (b[i] > b[i + 1]) {
            pos1 = i;
            break;
        }
    }
    int pos2 = n; // 这里要先给个初始值，因为如果是插入排序，pos2的值就是随机的
    for (int i = pos1 + 1; i < n; i++) {
        if (a[i] != b[i]) {
            pos2 = i;
        }
    }
    if (pos2 == n) {
        cout << "Insertion Sort" << endl;
        sort(a, a + pos1 + 2);
        printOut();
        return 0;
    }
    else {
        cout << "Merge Sort" << endl;
    }
    int step = 1, flag = 1;
    while(flag) {
        flag = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] != b[i]) flag = 1;
        }
        step = step * 2;
        for (int i = 0; i < n / step; i++) {
            sort(a + i * step, a + (i + 1) * step);
        }
        sort(a + n / step * step, a + n);
    }
    printOut();

    return 0;
}

1090 Highest Price in Supply Chain (25分)

重点在于理解这一句：
each number Si is the index of the supplier for the i-th member.
Si是第i个节点的父节点编号。

#include <bits/stdc++.h>
using namespace std;

int n, maxdepth = 0, maxnum = 0, root, temp;
double p, r;
vector<int> v[100010];

void DFS(int root, int depth) {
    if (v[root].size() == 0) {
        if (maxdepth == depth) {
            maxnum++;
        }
        if (maxdepth < depth) {
            maxdepth = depth;
            maxnum = 1;
        }
        return; // 最好加上
    }
    for (int i = 0; i < v[root].size(); i++) {
        DFS(v[root][i], depth + 1);
    }
}

int main() {
    scanf("%d %lf %lf", &n, &p, &r);
    for (int i = 0; i < n; i++) {
        scanf("%d", &temp);
        if (temp == -1) {
            root = i;
        }
        else {
            v[temp].push_back(i);
        }
    }
    DFS(root, 0);
    printf("%.2f %d", p * pow(1 + r / 100, maxdepth), maxnum);

    return 0;
}

1091 Acute Stroke (30分)

1092 To Buy or Not to Buy (20 分)

#include <iostream>
using namespace std;

int book[300];

int main() {
    string a, b;
    cin >> a >> b;
    for (int i = 0; i < a.length(); i++) {
        book[a[i]]++;
    }
    int res = 0;
    for (int i = 0; i < b.length(); i++) {
        if (book[b[i]] > 0) {
            book[b[i]]--;
        }
        else {
            res++;
        }
    }
    if (res == 0) {
        printf("Yes %d", a.length() - b.length());
    }
    else {
        printf("No %d", res);
    }
    
    return 0;
}

ppRYYGrrYB225
YrR8RrY

No 2

1093 Count PAT’s (25分)

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    int P = 0, T = 0, res = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == 'T') {
            T++;
        }
    }
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == 'P') P++;
        if (s[i] == 'T') T--;
        if (s[i] == 'A') {
            res += P * T;
            res %= 1000000007;
        }
        // 为什么和result = (result + (countp * countt) % 1000000007) % 1000000007结果一样
    }
    cout << res;

    return 0;
}

1094 The Largest Generation (25分)

DPS, 统计树的高度，以及每一层的结点个数，输出结点最多的是多少个以及哪一层。

#include <bits/stdc++.h>
using namespace std;

vector<int> v[101];
int book[101];

void DFS(int root, int level) {
    book[level]++;
    for (int i = 0; i < v[root].size(); i++) {
        DFS(v[root][i], level + 1);
    }
}

int main() {
    int n, m, ID, k, t;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &ID, &k);
        for (int j = 0; j < k; j++) {
            scanf("%d", &t);
            v[ID].push_back(t);
        }
    }
    int maxlevel = 1, maxnum = 0;
    DFS(1, 1);
    for (int i = 1; i < 100; i++) {
        if (book[i] > maxnum) {
            maxnum = book[i];
            maxlevel = i;
        }
    }
    printf("%d %d", maxnum, maxlevel);

    return 0;
}

BFS

vector<int> v[100];
int level[100];
int book[100];
int main() {
    int n, m, a, k, c;
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; i++) {
        scanf("%d %d",&a, &k);
        for(int j = 0; j < k; j++) {
            scanf("%d", &c);
            v[a].push_back(c);
        }
    }
    queue<int> q;
    q.push(1);
    level[1] = 1;
    while(!q.empty()) {
        int index = q.front();
        q.pop();
        book[level[index]]++;
        for(int i = 0; i < v[index].size(); i++) {
            level[v[index][i]] = level[index] + 1;
            q.push(v[index][i]);
        }
        
    }
    int maxnum = 0, maxlevel = 1;
    for(int i = 1; i < 100; i++) {
        if(book[i] > maxnum) {
            maxnum = book[i];
            maxlevel = i;
        }
    }
    printf("%d %d", maxnum, maxlevel);
    return 0;
}

1095 Cars on Campus (30分)

1096 Consecutive Factors (20 分)

输入一个数字，问是否能拆成或干个连续整数的连乘，即连续数字的连乘是否是输入数字的因数。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int num, temp;
    scanf("%d", &num);
    int left = 0, len = 0, maxn = sqrt(num) + 1; // 比如20 4*5
    for (int i = 2; i <= maxn; i++) {
        temp = 1;
        int j;
        for (j = i; j <= maxn; j++) {
            temp *= j;
            if (num % temp != 0) break;
        }
        if (j - i > len) {
            len = j - i;
            left = i;
        }
    }
    if (left == 0) {
        cout << 1 << endl << num;
    }
    else {
        cout << len << endl;
        for (int i = 0; i < len; i++) {
            cout << left + i;
            if (i != len - 1) {
                cout << "*";
            }
        }
    }

    return 0;
}
630

3
5*6*7

1097 Deduplication on a Linked List (25分)

去重（绝对值相等也算）。输出去重后的链表和删除的链表。

很巧妙的做法，给一个初始值的索引，2倍的maxn，然后[0,maxn)放去重后的，[maxn, maxn * 2)放多余的。然后输出。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 100000;

struct node {
    int address, data, next, index = maxn * 2;
}NODE[maxn];

bool exist[maxn];

bool cmp1(node a, node b) {
    return a.index < b.index;
}

int main() {
    int begin, n, cnt1 = 0, cnt2 = 0, cnt = 0, temp;
    scanf("%d %d", &begin, &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &temp);
        scanf("%d %d", &NODE[temp].data, &NODE[temp].next);
        NODE[temp].address = temp;
    }
    for (int i = begin; i != -1; i = NODE[i].next) {
        if (exist[abs(NODE[i].data)] == false) {
            exist[abs(NODE[i].data)] = true;
            NODE[i].index = cnt1;
            cnt1++;
        } 
        else {
            NODE[i].index = maxn + cnt2;
            cnt2++;
        }
    }
    sort(NODE, NODE + maxn, cmp1);
    cnt = cnt1 + cnt2;
    for (int i = 0; i < cnt; i++) {
        if (i != cnt1 - 1 && i != cnt - 1) {
            printf("%05d %d %05d\n", NODE[i].address, NODE[i].data, NODE[i + 1].address);
        }
        else {
            printf("%05d %d -1\n", NODE[i].address, NODE[i].data);
        }
    }

    return 0;
}

1098 Insertion or Heap Sort (25分)

题目大意：给出n和n个数的序列a和b，a为原始序列，b为排序其中的一个步骤，问b是a经过了堆排序还是插入排序的，并且输出它的下一步～

分析：插入排序的特点是：b数组前面的顺序是从小到大的，后面的顺序不一定，但是一定和原序列的后面的顺序相同～所以只要遍历一下前面几位，遇到不是从小到大的时候，开始看b和a是不是对应位置的值相等，相等就说明是插入排序，否则就是堆排序啦～

插入排序的下一步就是把第一个不符合从小到大的顺序的那个元素插入到前面已排序的里面的合适的位置，那么只要对前几个已排序的+后面一位这个序列sort排序即可～while(p <= n && b[p – 1] <= b[p]) p++；int index = p；找到第一个不满足条件的下标p并且赋值给index，b数组下标从1开始，所以插入排序的下一步就是sort(b.begin() + 1, b.begin() + index + 1)后的b数组～

堆排序的特点是后面是从小到大的，前面的顺序不一定，又因为是从小到大排列，堆排序之前堆为大顶堆，前面未排序的序列的最大值为b[1]，那么就可以从n开始往前找，找第一个小于等于b[1]的数字b[p]（while(p > 2 && b[p] >= b[1]) p–；），把它和第一个数字交换（swap(b[1], b[p])；），然后把数组b在1~p-1区间进行一次向下调整（downAdjust(b, 1, p – 1)；）～向下调整，low和high是需要调整的区间，因为是大顶堆，就是不断比较当前结点和自己的孩子结点哪个大，如果孩子大就把孩子结点和自己交换，然后再不断调整直到到达区间的最大值不能再继续了为止～

void downAdjust(vector<int> &b, int low, int high) {
    int i = 1, j = i * 2;
    while(j <= high) {
        if(j + 1 <= high && b[j] < b[j + 1]) j = j + 1;
        if (b[i] >= b[j]) break;
        swap(b[i], b[j]);
        i = j; j = i * 2;
    }
}
int main() {
    int n, p = 2;
    scanf("%d", &n);
    vector<int> a(n + 1), b(n + 1);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for(int i = 1; i <= n; i++) scanf("%d", &b[i]);
    while(p <= n && b[p - 1] <= b[p]) p++;
    int index = p;
    while(p <= n && a[p] == b[p]) p++;
    if(p == n + 1) {
        printf("Insertion Sort\n");
        sort(b.begin() + 1, b.begin() + index + 1);
    } else {
        printf("Heap Sort\n");
        p = n;
        while(p > 2 && b[p] >= b[1]) p--;
        swap(b[1], b[p]);
        downAdjust(b, 1, p - 1);
    }
    printf("%d", b[1]);
    for(int i = 2; i <= n; i++)
        printf(" %d", b[i]);
    return 0;
}

1099 Build A Binary Search Tree (30分)

1100 Mars Numbers (20 分)

题目大意：火星人是以13进制计数的：地球人的0被火星人称为tret。地球人数字1到12的火星文分别为：jan, feb, mar, apr, may, jun, jly, aug, sep, oct, nov, dec。火星人将进位以后的12个高位数字分别称为：tam, hel, maa, huh, tou, kes, hei, elo, syy, lok, mer, jou。例如地球人的数字“29”翻译成火星文就是“hel mar”；而火星文“elo nov”对应地球数字“115”。为了方便交流，请你编写程序实现地球和火星数字之间的互译～

分析：因为给出的可能是数字（地球文）也有可能是字母（火星文），所以用字符串s保存每一次的输入，因为如果是火星文则会出现空格，所以用getline接收一行的输入～计算string s的长度len，判断s[0]是否是数字，如果是数字，表示是地球文，则需要转为火星文，执行func1()；如果不是数字，则说明是火星文，需要转为地球文，执行func2()；

func1(int t)中，传入的值是string转int后的结果stoi(s)，因为数字最大不超过168，所以最多只会输出两位火星文，如果t / 13不等于0，说明有高位，所以输出b[t/13]；如果输出了高位（t/13不等于0）并且t % 13不等于0，说明有高位且有低位，所以此时输出空格；如果t % 13不等于0，说明有低位，此时输出a[t % 13]；注意，还有个数字0没有考虑，因为数字0取余13等于0，但是要特别输出tret，所以在func1的最后一句判断中加一句t == 0，并将a[0]位赋值成tret即可解决0的问题～

func2()中，t1和t2一开始都赋值0，s1和s2用来分离火星文单词，因为火星文字符串只可能一个单词或者两个单词，而且一个单词不会超过4，所以先将一个单词的赋值给s1，即s1 = s.substr(0, 3)；如果len > 4，就将剩下的一个单词赋值给s2，即s2 = s.substr(4, 3)；然后下标j从1到12遍历a和b两个数组，如果a数组中有和s1或者s2相等的，说明低位等于j，则将j赋值给t2；如果b数组中有和s1相等的（b数组不会和s2相等，因为如果有两个单词，s2只可能是低位），说明高位有值，将j赋值给t1，最后输出t1 * 13 + t2即可～

#include <iostream>
#include <string>
using namespace std;

string a[13] = {"tret", "jan", "feb", "mar", "apr", "may", "jun", "jly", "aug", "sep", "oct", "nov", "dec"};
string b[13] = {"####", "tam", "hel", "maa", "huh", "tou", "kes", "hei", "elo", "syy", "lok", "mer", "jou"};
string s;
int len;

void toMars(int n) {
    if (n / 13) cout << b[n / 13];
    if ((n / 13) && (n % 13)) cout << " ";
    if (n % 13 || n == 0) cout << a[n % 13];
}

void toEarth() {
    int t1 = 0, t2 = 0;
    string s1 = s.substr(0, 3), s2;
    if (len > 4) s2 = s.substr(4, 3);
    for (int i = 0; i <= 12; i++) {
        if (s1 == a[i] || s2 == a[i]) t2 = i;
        if (s1 == b[i]) t1 = i;
    }
    cout << t1 * 13 + t2;
}

int main() {
    int n;
    cin >> n;
    getchar(); // 用来接收回车的。
    for (int i = 0; i < n; i++) {
        getline(cin, s);
        len = s.length();
        if (s[0] >= '0' && s[0] <= '9') {
            toMars(stoi(s));
        } else {
            toEarth();
        }
        cout << endl;
    }
    
    return 0;
} 

4
29
5
elo nov
tam

hel mar
may
115
13

1101 Quick Sort (25分)

输入n个不同的数字，问有几个可以当快速排序的分割点pivot。输出个数以及是哪几个数字。左边要么没有要么都比pivot小，右边要么没有要么比pivot大。（题目中已经保证所有输入数字都不同）
pivot的位置与排序后的位置一致。（左小右大，分别排序左右即可，它不用动）并且要求pivot比左边最大的还大，比右边最小的还小。

#include <bits/stdc++.h>
using namespace std;

int res[100010];

int main() {
    int n, cnt = 0, max = -1;
    scanf("%d", &n);
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        b[i] = a[i];
    }
    sort(a.begin(), a.end());
    for (int i = 0; i < n; i++) {
        if (a[i] == b[i] && b[i] > max) {
            res[cnt++] = b[i];
        }
        if (b[i] > max) {
            max = b[i];
        }
    }
    printf("%d\n", cnt);
    for (int i = 0; i < cnt; i++) {
        if (i != 0) printf(" ");
        printf("%d", res[i]);
    }
    printf("\n"); // 不加这个部分会出错

    return 0;
}

5
1 3 2 4 5

3
1 4 5

1102 Invert a Binary Tree (25分)

题目大意：反转一棵二叉树，给出原二叉树的每个结点的左右孩子，输出它的层序和中序遍历～

分析：1. 反转二叉树就是存储的时候所有左右结点都交换。

2. 二叉树使用{id, l, r, index, level}存储每个结点的id, 左右结点,下标值，和当前层数～
3. 根结点是所有左右结点中没有出现的那个结点～
4. 已知根结点，用递归的方法可以把中序遍历的结果push_back到数组v1里面，直接输出就是中序，排序输出就是层序（排序方式，层数小的排前面，相同层数时，index大的排前面）

struct node {
    int id, l, r, index, level;
} a[100];
vector<node> v1;
void dfs(int root, int index, int level) {
    if (a[root].r != -1) dfs(a[root].r, index * 2 + 2, level + 1);
    v1.push_back({root, 0, 0, index, level});
    if (a[root].l != -1) dfs(a[root].l, index * 2 + 1, level + 1);
}
bool cmp(node a, node b) {
    if (a.level != b.level) return a.level < b.level;
    return a.index > b.index;
}
int main() {
    int n, have[100] = {0}, root = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        a[i].id = i;
        string l, r;
        cin >> l >> r;
        if (l != "-") {
            a[i].l = stoi(l);
            have[stoi(l)] = 1;
        } else {
            a[i].l = -1;
        }
        if (r != "-") {
            a[i].r = stoi(r);
            have[stoi(r)] = 1;
        } else {
            a[i].r = -1;
        }
    }
    while (have[root] == 1) root++;
    dfs(root, 0, 0);
    vector<node> v2(v1);
    sort(v2.begin(), v2.end(), cmp);
    for (int i = 0; i < v2.size(); i++) {
        if (i != 0) cout << " ";
        cout << v2[i].id;
    }
    cout << endl;
    for (int i = 0; i < v1.size(); i++) {
        if (i != 0) cout << " ";
        cout << v1[i].id;
    }
    return 0;
}

1103 Integer Factorization (30分)

1104 Sum of Number Segments (20 分)

#include <bits/stdc++.h>
using namespace std;

int main() {
#ifdef ONLINE_JUDGE
#else
    freopen("D:\\Markdown\\Coding\\C++\\temporary\\in.txt", "r", stdin);
    freopen("D:\\Markdown\\Coding\\C++\\temporary\\out.txt","w",stdout);
#endif
    int n;
    cin >> n;
    long long sum = 0;
    double temp;
    for (int i = 1; i <= n; i++) {
        cin >> temp;
        sum += (long long)(temp * 1000) * i * (n - (i - 1));
        cout << (long long)(temp * 1000) * i * (n - (i - 1)) << endl;
        cout << sum << endl;
    }
    cout << sum << endl;
    printf("%.2f", (sum / 1000.0));
    
    return 0;
}


4
0.1 0.2 0.3 0.4
400
400
1200
1600
1794 为什么是1794不是1800？debug了下，0.3居然是0.29999999999
3394
1600
4994
4994
4.99

1105 Spiral Matrix (25分)

int cmp(int a, int b) {return a > b;}
int main() {
    int N, m, n, t = 0;
    scanf("%d", &N);
    for (n = sqrt((double)N); n >= 1; n--) {
        if (N % n == 0) {
            m = N / n;
            break;
        }
    }
    vector<int> a(N);
    for (int i = 0; i < N; i++)
        scanf("%d", &a[i]);
    sort(a.begin(), a.end(), cmp);
    vector<vector<int> > b(m, vector<int>(n));
    int level = m / 2 + m % 2;
    for (int i = 0; i < level; i++) {
        for (int j = i; j <= n - 1 - i && t <= N - 1; j++)
                b[i][j] = a[t++];
        for (int j = i + 1; j <= m - 2 - i && t <= N - 1; j++)
                b[j][n - 1 - i] = a[t++];
        for (int j = n - i - 1; j >= i && t <= N - 1; j--)
                b[m - 1 - i][j] = a[t++];
        for (int j = m - 2 - i; j >= i + 1 && t <= N - 1; j--)
                b[j][i] = a[t++];
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0 ; j < n; j++) {
            printf("%d", b[i][j]);
            if (j != n - 1) printf(" ");
        }
        printf("\n");
    }
    return 0;
}

1106 Lowest Price in Supply Chain (25分)

问到消费者手里最低价是多少，有几个零售商满足要求。也就是是中间商最少的，高度最低的叶子节点。

vector<int> v[100005];
int mindepth = 99999999, minnum = 1;
void dfs(int index, int depth) {
    if(mindepth < depth)
        return ;
    if(v[index].size() == 0) {
        if(mindepth == depth)
            minnum++;
        else if(mindepth > depth) {
            mindepth = depth;
            minnum = 1;
        }
    }
    for(int i = 0; i < v[index].size(); i++)
        dfs(v[index][i], depth + 1);
}
int main() {
    int n, k, c;
    double p, r;
    scanf("%d %lf %lf", &n, &p, &r);
    for(int i = 0; i < n; i++) {
        scanf("%d", &k);
        for(int j = 0; j < k; j++) {
            scanf("%d", &c);
            v[i].push_back(c);
        }
    }
    dfs(0, 0);
    printf("%.4f %d", p * pow(1 + r/100, mindepth), minnum);
    return 0;
}

1107 Social Clusters (30分)

1108 Finding Average (20 分)

#include <iostream>
#include <string.h> 
using namespace std;

int main() {
    int n, cnt = 0;
    char a[60], b[60];
    double sum = 0.0, t;
    cin >> n;
    for (int i = 0; i < n; i++) {
        scanf("%s", a);
        sscanf(a, "%lf", &t);
        sprintf(b, "%.2f", t);
        int flag = 0;
        for (int j = 0; j < strlen(a); j++) {
            if (a[j] != b[j]) flag = 1;
        }
        if (flag || t < -1000 || t > 1000) {
            printf("ERROR: %s is not a legal number\n", a);
            continue;
        } else {
            sum += t;
            cnt++;
            // printf("a = %s, b = %s.\n", a, b);
            // a也可能比b短，比如输入5，a = 5, b = 5.00
            // 所以用j < strlen(a)
        }
    }
    if (cnt == 1) {
        printf("The average of 1 number is %.2f", sum);
    } else if (cnt > 1) {
        printf("The average of %d numbers is %.2f", cnt, sum / cnt);
    } else {
        printf("The average of 0 numbers is Undefined");
    }
    
    return 0;
}

1109 Group Photo (25分)

题目大意：拍集体照时队形很重要，这里对给定的N个人K排的队形设计排队规则如下：
每排人数为N/K（向下取整），多出来的人全部站在最后一排；后排所有人的个子都不比前排任何人矮；每排中最高者站中间（中间位置为m/2+1，其中m为该排人数，除法向下取整）；每排其他人以中间人为轴，按身高非增序，先右后左交替入队站在中间人的两侧（例如5人身高为190、188、186、175、170，则队形为175、188、190、186、170。这里假设你面对拍照者，所以你的左边是中间人的右边）；若多人身高相同，则按名字的字典序升序排列。这里保证无重名。现给定一组拍照人，请编写程序输出他们的队形。输出拍照的队形。即K排人名，其间以空格分隔，行末不得有多余空格。注意：假设你面对拍照者，后排的人输出在上方，前排输出在下方～

分析：建立结构体node，里面包含string类型的姓名name和int类型的身高height～将学生的信息输入到node类型的vector数组stu中～然后对stu数组进行排序（cmp函数表示排序规则，如果身高不等，就按照身高从大到小排列；如果身高相等，就按照名字从小到大的字典序排列～）然后用while循环排列每一行，将每一行应该排列的结果的姓名保存在ans数组中～

因为是面对拍照者，后排的人输出在上方，前排输出在下方，每排人数为N/K（向下取整），多出来的人全部站在最后一排，所以第一排输出的应该是包含多出来的人，所以while循环体中，当row == k时，表示当前是在排列第一行，那么这一行的人数m应该等于总人数n减去后面的k列(k-1)行，即m = n – n / k (k-1)；如果不是第一行，那么m直接等于n / k；最中间一个学生应该排在m/2的下标位置，即ans[m / 2] = stu[t].name；然后排左边一列，ans数组的下标 j 从m/2-1开始，一直往左j–，而对于stu的下标 i，是从t+1开始，每次隔一个人选取（即i = i+2，因为另一些人的名字是给右边的），每次把stu[i]的name赋值给ans[j–]；排右边的队伍同理，ans数组的下标 j 从m/2 + 1开始，一直往右j++，stu的下标 i，从t+2开始，每次隔一个人选取（i = i+2），每次把stu[i]的name赋值给ans[j++]，然后输出当前已经排好的ans数组～每一次排完一列row-1，直到row等于0时退出循环表示已经排列并输出所有的行～

struct node {
    string name;
    int height;
};
int cmp(struct node a, struct node b) {
    return a.height != b.height ? a.height > b.height : a.name < b.name;
}
int main() {
    int n, k, m;
    cin >> n >> k;
    vector<node> stu(n);
    for(int i = 0; i < n; i++) {
        cin >> stu[i].name;
        cin >> stu[i].height;
    }
    sort(stu.begin(), stu.end(), cmp);
    int t = 0, row = k;
    while(row) { 
        if(row == k) {
            m = n - n / k * (k - 1);
        } else {
            m = n / k;
        }
        vector<string> ans(m);
        ans[m / 2] = stu[t].name;
        // 左边一列
        int j = m / 2 - 1;
        for(int i = t + 1; i < t + m; i = i + 2)
            ans[j--] = stu[i].name;
        // 右边一列
        j = m / 2 + 1;
        for(int i = t + 2; i < t + m; i = i + 2)
            ans[j++] = stu[i].name;
        // 输出当前排
        cout << ans[0];
        for(int i = 1; i < m; i++)
            cout << " " << ans[i];
        cout << endl;
        t = t + m;
        row--;
    }
    return 0;
}

1110 Complete Binary Tree (25分)

题目大意：给出一个n表示有n个结点，这n个结点为0~n-1，给出这n个结点的左右孩子，求问这棵树是不是完全二叉树
分析：递归出最大的下标值，完全二叉树一定把前面的下标充满： 最大的下标值 == 最大的节点数；不完全二叉树前满一定有位置是空，会往后挤： 最大的下标值 > 最大的节点数～

using namespace std;
struct node{
    int l, r;
}a[100];
int maxn = -1, ans;
void dfs(int root, int index) {
    if(index > maxn) {
        maxn = index;
        ans = root; // ?????
    }
    if(a[root].l != -1) dfs(a[root].l, index * 2);
    if(a[root].r != -1) dfs(a[root].r, index * 2 + 1);
}
int main() {
    int n, root = 0, have[100] = {0};
    cin >> n;
    for (int i = 0; i < n; i++) {
        string l, r;
        cin >> l >> r;
        if (l == "-") {
            a[i].l = -1;
        } else {
            a[i].l = stoi(l);
            have[stoi(l)] = 1;
        }
        if (r == "-") {
            a[i].r = -1;
        } else {
            a[i].r = stoi(r);
            have[stoi(r)] = 1;
        }
    }
    while (have[root] != 0) root++;
    dfs(root, 1);
    if (maxn == n)
        cout << "YES " << ans;
    else
        cout << "NO " << root;
    return 0;
}

1111 Online Map (30分)

1112 Stucked Keyboard (20分)

键盘的某些按键黏住了，按一次重复k次，找出可能粘住的按键以及输出正确的顺序。

bool sureNoBroken[256]; // 确定不是坏件
int main() {
    int k, cnt = 1; 
    scanf("%d", &k);
    string s;
    cin >> s;
    map<char, bool> m; // 出现的按键是否坏
    set<char> printed;
    char pre = '#';
    s = s + '#';
    for(int i = 0; i < s.length(); i++) {
        if(s[i] == pre) {
            cnt++;
        } else {
            if(cnt % k != 0) {
                sureNoBroken[pre] = true;
            }
            cnt = 1;
        }
        if(i != s.length() - 1) m[s[i]] = (cnt % k == 0);
        pre = s[i];
    }
    for(int i = 0; i < s.length() - 1; i++) {
        if(sureNoBroken[s[i]] == true)
            m[s[i]] = false;
    }
    for(int i = 0; i < s.length() - 1; i++) {
        if(m[s[i]] && printed.find(s[i]) == printed.end()) {
            printf("%c", s[i]);
            printed.insert(s[i]);
        }
    }
    printf("\n");
    for(int i = 0; i < s.length() - 1; i++) {
        printf("%c", s[i]);
        if(m[s[i]])
            i = i + k - 1;
    }
    return 0;
}

1113 Integer Set Partition (25分)

给n个数，分成2个集合，个数为n1，n2，每个集合的和为s1,s2,要求个数相减尽可能小，和相差尽可能大。
排序取一半即可。sum - 2 * halfsum用sum - halfsum - halfsum就更清楚了。

int main() {
    int n, sum = 0, halfsum = 0;
    scanf("%d", &n);
    vector<int> v(n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &v[i]);
        sum += v[i];
    }
    sort(v.begin(), v.end());
    for(int i = 0; i < n / 2; i++)
        halfsum += v[i];
    printf("%d %d", n % 2, sum - 2 * halfsum);
    return 0;
}

1114 Family Property (25分)

题目大意：给定每个人的家庭成员和其自己名下的房产，请你统计出每个家庭的人口数、人均房产面积及房产套数。首先在第一行输出家庭个数（所有有亲属关系的人都属于同一个家庭）。随后按下列格式输出每个家庭的信息：家庭成员的最小编号 家庭人口数 人均房产套数 人均房产面积。其中人均值要求保留小数点后3位。家庭信息首先按人均面积降序输出，若有并列，则按成员编号的升序输出。
分析：用并查集。分别用两个结构体数组，一个data用来接收数据，接收的时候顺便实现了并查集的操作union，另一个数组ans用来输出最后的答案，因为要计算家庭人数，所以用visit标记所有出现过的结点，对于每个结点的父结点，people++统计人数。标记flag == true，计算true的个数cnt就可以知道一共有多少个家庭。排序后输出前cnt个就是所求答案～～

并查集？？？？？？

struct DATA {
    int id, fid, mid, num, area;
    int cid[10];
}data[1005];
struct node {
    int id, people;
    double num, area;
    bool flag = false;
}ans[10000];
int father[10000];
bool visit[10000];
int find(int x) {
    while(x != father[x])
        x = father[x];
    return x;
}
void Union(int a, int b) {
    int faA = find(a);
    int faB = find(b);
    if(faA > faB)
        father[faA] = faB;
    else if(faA < faB)
        father[faB] = faA;
}
int cmp1(node a, node b) {
    if(a.area != b.area)
        return a.area > b.area;
    else
        return a.id < b.id;
}
int main() {
    int n, k, cnt = 0;
    scanf("%d", &n);
    for(int i = 0; i < 10000; i++)
        father[i] = i;
    for(int i = 0; i < n; i++) {
        scanf("%d %d %d %d", &data[i].id, &data[i].fid, &data[i].mid, &k);
        visit[data[i].id] = true;
        if(data[i].fid != -1) {
            visit[data[i].fid] = true;
            Union(data[i].fid, data[i].id);
        }
        if(data[i].mid != -1) {
            visit[data[i].mid] = true;
            Union(data[i].mid, data[i].id);
        }
        for(int j = 0; j < k; j++) {
            scanf("%d", &data[i].cid[j]);
            visit[data[i].cid[j]] = true;
            Union(data[i].cid[j], data[i].id);
        }
        scanf("%d %d", &data[i].num, &data[i].area);
    }
    for(int i = 0; i < n; i++) {
        int id = find(data[i].id);
        ans[id].id = id;
        ans[id].num += data[i].num;
        ans[id].area += data[i].area;
        ans[id].flag = true;
    }
    for(int i = 0; i < 10000; i++) {
        if(visit[i])
            ans[find(i)].people++;
        if(ans[i].flag)
            cnt++;
    }
    for(int i = 0; i < 10000; i++) {
        if(ans[i].flag) {
            ans[i].num = (double)(ans[i].num * 1.0 / ans[i].people);
            ans[i].area = (double)(ans[i].area * 1.0 / ans[i].people);
        }
    }
    sort(ans, ans + 10000, cmp1);
    printf("%d\n", cnt);
    for(int i = 0; i < cnt; i++)
        printf("%04d %d %.3f %.3f\n", ans[i].id, ans[i].people, ans[i].num, ans[i].area);
    return 0;
}

1115 Counting Nodes in a BST (30分)

1116 Come on! Let’s C (20分)

分析：ran数组标记每个id对应的排名，集合ss存储所有已经询问过的id，如果发现当前id已经出现在ss中，则输出“Checked”，如果ran[id] == 0说明当前id不在排名列表中，所以输出“Are you kidding?”，如果ran[id]为1则输出“Minion”，如果ran[id]为素数则输出“Mystery Award”，否则输出“Chocolate”

int ran[10000];
bool isprime(int a) {
    if(a <= 1) return false;
    int Sqrt = sqrt((double)a);
    for(int i = 2; i <= Sqrt; i++) {
        if(a % i == 0)
            return false;
    }
    return true;
}
int main() {
    int n, k;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        int id;
        scanf("%d", &id);
        ran[id] = i + 1;
    }
    scanf("%d", &k);
    set<int> ss;
    for(int i = 0; i < k; i++) {
        int id;
        scanf("%d", &id);
        printf("%04d: ", id);
        if(ran[id] == 0) {
            printf("Are you kidding?\n");
            continue;
        }
        if(ss.find(id) == ss.end()) {
            ss.insert(id);
        } else {
            printf("Checked\n");
            continue;
        }
        if(ran[id] == 1) {
            printf("Mystery Award\n");
        }else if(isprime(ran[id])) {
            printf("Minion\n");
        }else {
            printf("Chocolate\n");
        }
    }
    return 0;
}

6
1111
6666
8888
1234
5555
0001
6
8888
0001
1111
2222
8888
2222

8888: Minion
0001: Chocolate
1111: Mystery Award
2222: Are you kidding?
8888: Checked
2222: Are you kidding?

1117 Eddington Number (25分)

题目大意：英国天文学家爱丁顿很喜欢骑车。据说他为了炫耀自己的骑车功力，还定义了一个“爱丁顿数”E，即满足有E天骑车超过E英里的最大整数E。据说爱丁顿自己的E等于87。
分析：在数组a中存储n天的公里数，对n个数据从大到小排序，根据排序后的数组可得知骑车大于等于 a[i] 英里的天数有 i+1 天，因为题目中要求超过E英里且所有的英里数为整数，所以可得知骑车超过 a[i]-1 英里的天数有 i+1 天，如样例，从大到小排序后结果为10、9、8、8、7、7、6、6、3、2，骑车超过9英里的有1天，超过8英里的有2天，超过7英里的有4天/5天，超过6英里的有5天/6天，超过5英里的有7天/8天…英里数不断减少，天数不断增加，既然已知公里数和天数对应的关系，要想满足题意，必须使超过的英里数a[i]-1大于等于天数i+1（比如样例中，超过6英里的有6天，超过5英里的有7天，前者的天数6满足题意这6天都超过了6英里，后者的天数7不满足因为这7天只满足骑车都超过5英里）即a[i]-1 >= i+1，也就是 a[i] >= i + 2，也就是a[i] > i + 1～从头到尾遍历数组，那么满足a[i] > i+1的最大i+1即为所求

int a[1000000];
int main() {
    int n, e = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    sort(a, a+n, greater<int>());
    while(e < n && a[e] > e+1) e++; // a[e]满足条件，那么之前的更大更满足 个数是e+1
    // 骑车大于等于 a[i] 英里的天数有 i+1 天,所以可得知骑车超过 a[i]-1 英里的天数有 i+1 天
    // 即a[i]-1 >= i+1，也就是 a[i]  >= i + 2，也就是a[i] > i + 1
    printf("%d", e);
    return 0;
}

greater和less
greater表示内置类型从大到小排序，less表示内置类型从小到大排序。

1118 Birds in Forest (25分)

1119 Pre- and Post-order Traversals (30分)

1120 Friend Numbers (20分)

int getFriendNum(int num) {
    int sum = 0;
    while(num != 0) {
        sum += num % 10;
        num /= 10;
    }
    return sum;
}
int main() {
    set<int> s;
    int n, num;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &num);
        s.insert(getFriendNum(num));
    }
    printf("%d\n", s.size());
    for(auto it = s.begin(); it != s.end(); it++) {
        if(it != s.begin()) printf(" ");
        printf("%d", *it);
    }
    return 0;
}

1121 Damn Single (25分)

分析： 设立数组couple[i] = j表示i的对象是j。一开始先设置为都是-1。设立数组isExist表示某人的对象是否来到了派对上。接收数据的时候，对于每一对a和b，将couple的a设置为b，b设置为a，表示他俩是一对。对于每一个需要判断的人，将其存储在guest数组里面，如果它不是单身的（也就是如果它的couple[guest[i]] != -1）那么就将它对象的isExist设置为1，表示他对象的对象（也就是他自己）来到了派对。这样所有isExist不为1的人，对象是没有来到派对的。把所有的人遍历后插入一个集合set里面，set的size就是所求的人数，set里面的所有数就是所求的人的递增排列～～～

int main() {
    int n, a, b, m;
    scanf("%d", &n);
    vector<int> couple(100000);
    for (int i = 0; i < 100000; i++)
        couple[i] = -1;
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &a, &b);
        couple[a] = b;
        couple[b] = a;
    }
    scanf("%d", &m);
    vector<int> guest(m), isExist(100000);
    for (int i = 0; i < m; i++) {
        scanf("%d", &guest[i]);
        if (couple[guest[i]] != -1) // guest[i]有配偶
            isExist[couple[guest[i]]] = 1; // 如果他配偶也在则不是单身狗
    }
    set<int> s;
    for (int i = 0; i < m; i++)
        if (!isExist[guest[i]]) s.insert(guest[i]);
        // 未有配偶 && 配置不在场
    printf("%d\n", s.size());
    for (auto it = s.begin(); it != s.end(); it++) {
        if (it != s.begin()) printf(" ");
        printf("%05d", *it);
    }
    return 0;
}

1122 Hamiltonian Cycle (25分)

题目大意：给出一个图，判断给定的路径是不是哈密尔顿路径

分析：1.设置falg1 判断节点是否多走、少走、或走成环
2.设置flag2 判断这条路能不能走通
3.当falg1、flag2都为1时是哈密尔顿路径，否则不是

int main() {
    int n, m, cnt, k, a[210][210] = {0};
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int t1, t2;
        scanf("%d%d", &t1, &t2);
        a[t1][t2] = a[t2][t1] = 1;
    }
    cin >> cnt;
    while(cnt--) {
        cin >> k;
        vector<int> v(k);
        set<int> s;
        int flag1 = 1, flag2 = 1;
        for(int i = 0; i < k; i++) {
            scanf("%d", &v[i]);
            s.insert(v[i]);
        }
        if(s.size() != n || k - 1 != n || v[0] != v[k-1]) flag1 = 0;
        // 点个数-有没有少走 走过的点个数-是否都走以及是否少走 头尾相连-除了头尾是否成环
        for(int i = 0; i < k - 1; i++)
            if(a[v[i]][v[i+1]] == 0) flag2 = 0;
        printf("%s",flag1 && flag2 ? "YES\n" : "NO\n");
    }
    return 0;
}

1123 Is It a Complete AVL Tree (30分)

1124 Raffle for Weibo Followers (20分)

题目大意：小明PAT考了满分，高兴之余决定发起微博转发抽奖活动，从转发的网友中按顺序每隔N个人就发出一个红包。请你编写程序帮助他确定中奖名单。注意：可能有人转发多次，但不能中奖多次。所以如果处于当前中奖位置的网友已经中过奖，则跳过他顺次取下一位。按照输入的顺序输出中奖名单，每个昵称占一行。如果没有人中奖，则输出“Keep going…”
分析：用mapp存储当前用户有没有已经中奖过～当输入的时候，判断当前字符串是否已经在mapp中出现过，如果出现过就将s+1。每次判断i是否等于s，如果等于s且当前用户没有中过奖，就将它的名字输出，并且s = s + n～并将mapp[str]标记为1，且flag标记为true表示有过人中奖。最后flag如果依然是false说明要输出Keep going…

Note: it is possible that someone would forward more than once, but no one can win more than once. 没得过奖，重复转发还是会提高中奖率。

int main() {
    int m, n, s;
    scanf("%d%d%d", &m, &n, &s);
    string str;
    map<string, int> mapp;
    bool flag = false;
    for (int i = 1; i <= m; i++) {
        cin >> str;
        if (mapp[str] == 1) s = s + 1;
        if (i == s && mapp[str] == 0) {
            mapp[str] = 1;
            cout << str << endl;
            flag = true;
            s = s + n;
        }
    }
    if (flag == false) cout << "Keep going...";
    return 0;
}
``` 




# 1125 Chain the Ropes (25分)
题目大意：给定一段一段的绳子，你需要把它们串成一条绳。每次串连的时候，是把两段绳子对折，再如下图所示套接在一起。这样得到的绳子又被当成是另一段绳子，可以再次对折去跟另一段绳子串连。每次串连后，原来两段绳子的长度就会减半。给定N段绳子的长度，你需要找出它们能串成的绳子的最大长度~
分析：因为所有长度都要串在一起，每次都等于(旧的绳子长度+新的绳子长度)/2，所以越是早加入绳子长度中的段，越要对折的次数多，所以既然希望绳子长度是最长的，就必须让长的段对折次数尽可能的短。所以将所有段从小到大排序，然后从头到尾从小到大分别将每一段依次加入结绳的绳子中，最后得到的结果才会是最长的结果～



```c++
int main() {
    int n;
    scanf("%d", &n);
    vector<int> v(n);
    for (int i = 0; i < n; i++)
        scanf("%d", &v[i]);
    sort(v.begin(), v.end());
    int result = v[0];
    for (int i = 1; i < n; i++)
        result = (result + v[i]) / 2;
    printf("%d", result);
    return 0;
}

1126 Eulerian Path (25分)

题目大意：如果一个连通图的所有结点的度都是偶数，那么它就是Eulerian，如果除了两个结点的度是奇数其他都是偶数，那么它就是Semi-Eulerian，否则就是Non-Eulerian～
分析：用邻接表存储图，判断每个结点的度【也就是每个结点i的v[i].size()】是多少即可得到最终结果～注意：图必须是连通图，所以要用一个深搜判断一下连通性，从结点1开始深搜，如果最后发现统计的连通结点个数cnt != n说明是不是连通图，要输出Non-Eulerian～

vector<vector<int> > v;
vector<bool> visit;
int cnt = 0;
void dfs(int index) {
    visit[index] = true;
    cnt++;
    for (int i = 0; i < v[index].size(); i++)
        if (visit[v[index][i]] == false)
            dfs(v[index][i]);
}
int main() {
    int n, m, a, b, even = 0;
    scanf("%d%d", &n, &m);
    v.resize(n + 1);
    visit.resize(n + 1);
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &a, &b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for (int i = 1; i <= n; i++) {
        if (i != 1) printf(" ");
        printf("%d", v[i].size());
        if (v[i].size() % 2 == 0) even++;
    }
    printf("\n");
    dfs(1);
    if (even == n && cnt == n)
        printf("Eulerian");
    else if(even == n - 2 && cnt == n)
        printf("Semi-Eulerian");
    else
        printf("Non-Eulerian");
    return 0;
}

1127 ZigZagging on a Tree (30分)

1128 N Queens Puzzle (20分)

题目大意：给出一个皇后图，以这样的方式给出：一个数组包含n个数字，每个数字表示该列的皇后所在的行数～判断给出的皇后图是否满足不会互相攻击（任意两个皇后都要不在同一行或者同一列，且不在斜对角线上～）
分析：用v[n]存储一张图给出的数字～对于第j个数字，判断前0～j-1个数字中是否有在同一行的（v[j] == v[t]）和在斜对角线上的（abs(v[j]-v[t]) == abs(j-t)）【因为已经告诉肯定不在同一列了，所以不需要判断是否在同一列啦～】如果发现了不满足的情况，就将result由true标记为false～最后根据result是true还是false输出对应的YES还是NO即可～

int main() {
    int k, n;
    cin >> k;
    for (int i = 0; i < k; i++) {
        cin >> n;
        vector<int> v(n);
        bool result = true;
        for (int j = 0; j < n; j++) {
            cin >> v[j];
            for (int t = 0; t < j; t++) {
                if (v[j] == v[t] || abs(v[j]-v[t]) == abs(j-t)) {
                    result = false;
                    break;
                }
            }
        }
        cout << (result == true ? "YES\n" : "NO\n");
    }
    return 0;
}

1129 Recommendation System (25分)

题目大意：根据用户每次点击的东西的编号，输出他在点当前编号之前应该给这个用户推荐的商品的编号～只推荐k个～也就是输出用户曾经点击过的商品编号的最多的前k个～如果恰好两个商品有相同的点击次数，就输出编号较小的那个～
分析：【并不复杂～只是写的比较详细～不怕不怕～(摸头…】因为每个商品有两个属性：编号value和出现的次数cnt，编号具有唯一性，然后set又会根据大小自动排序，所以我们可以考虑将value和cnt组成一个node属性，把所有商品编号和它对应的次数变成node放入set里面，重载小于号，使<根据set中node的cnt排序，如果cnt相等就按照node的value排序～
这样set里面就是按照出现次数排序好的商品node，每次输出set的前k个node的value值就可以～（要记住，因为是点击前推荐，所以我们在接收完num的值后，应该先输出再插入让set帮忙排序当前num，当前的这个点击编号暂时先不算在输出结果里面的～）
首先在struct node里面重载<号，如果当前cnt不等于a.cnt就将cnt大的排在前，否则将value小的排在前面～
每次输入的时候，先不插入，先输出，当i != 0时候开始输出，因为i==0时候用户才第一次点击，没有可以推荐的～(沮丧脸…) 输出的同时记录输出过的个数tempCnt，当tempCnt < k的时候输出，因为只要前k个～所以就从头到尾依次输出set中的值就可以啦～
book[num]标记num出现的次数，每次寻找set中当前值为num和次数为book[num]的那个值，如果找到了就把他移除，（找到说明这个数已经出现过啦，cnt已经不对啦，先移除掉吧～）然后将book[num]+1，在将node(num, book[num])插入到set中，set会帮忙根据我们自定义的<的规则自动排序哒～

int book[50001];
struct node {
    int value, cnt;
    bool operator < (const node &a) const {
        return (cnt != a.cnt) ? cnt > a.cnt : value < a.value;
    }
};
int main() {
    int n, k, num;
    scanf("%d%d", &n, &k);
    set<node> s;
    for (int i = 0; i < n; i++) {
        scanf("%d", &num);
        if (i != 0) {
            printf("%d:", num);
            int tempCnt = 0;
            for(auto it = s.begin(); tempCnt < k && it != s.end(); it++) {
                printf(" %d", it->value);
                tempCnt++;
            }
            printf("\n");
        }
        auto it = s.find(node{num, book[num]});
        if (it != s.end()) s.erase(it);
        book[num]++;
        s.insert(node{num, book[num]});
    }
    return 0;
}

1130 Infix Expression (25分)

1131 Subway Map (30分)

1132 Cut Integer (20分)

1133 Splitting A Linked List (25分)

1134 Vertex Cover (25分)

1135 Is It A Red-Black Tree (30分)

1136 A Delayed Palindrome (20分)

1137 Final Grading (25分)

1138 Postorder Traversal (25分)

1139 First Contact (30分)

1140 Look-and-say Sequence (20分)

1141 PAT Ranking of Institutions (25分)

1142 Maximal Clique (25分)

1143 Lowest Common Ancestor (30分)

1144 The Missing Number (20分)

1145 Hashing - Average Search Time (25分)

1146 Topological Order (25分)

1147 Heaps (30分)

1148 Werewolf - Simple Version (20分)

1149 Dangerous Goods Packaging (25分)

1150 Travelling Salesman Problem (25分)

1151 LCA in a Binary Tree (30分)

1152 Google Recruitment (20分)

1153 Decode Registration Card of PAT (25分)

1154 Vertex Coloring (25分)

1155 Heap Paths (30分)