hdvsyu's blog

Zhejiang University has 8 campuses and a lot of gates. From each gate we can collect the in/out times and the plate numbers of the cars crossing the gate. Now with all the information available, you are supposed to tell, at any specific time point, the number of cars parking on campus, and at the end of the day find the cars that have parked for the longest time period.

Input Specification:

Each input file contains one test case. Each case starts with two positive integers N (≤104), the number of records, and K (≤8×104) the number of queries. Then N lines follow, each gives a record in the format:

plate_number hh:mm:ss status

where plate_number is a string of 7 English capital letters or 1-digit numbers; hh:mm:ss represents the time point in a day by hour:minute:second, with the earliest time being 00:00:00 and the latest 23:59:59; and status is either in or out.

Note that all times will be within a single day. Each in record is paired with the chronologically next record for the same car provided it is an out record. Any in records that are not paired with an out record are ignored, as are out records not paired with an in record. It is guaranteed that at least one car is well paired in the input, and no car is both in and out at the same moment. Times are recorded using a 24-hour clock.

Then K lines of queries follow, each gives a time point in the format hh:mm:ss. Note: the queries are given in accending order of the times.

Output Specification:

For each query, output in a line the total number of cars parking on campus. The last line of output is supposed to give the plate number of the car that has parked for the longest time period, and the corresponding time length. If such a car is not unique, then output all of their plate numbers in a line in alphabetical order, separated by a space.

Sample Input:

16 7
JH007BD 18:00:01 in
ZD00001 11:30:08 out
DB8888A 13:00:00 out
ZA3Q625 23:59:50 out
ZA133CH 10:23:00 in
ZD00001 04:09:59 in
JH007BD 05:09:59 in
ZA3Q625 11:42:01 out
JH007BD 05:10:33 in
ZA3Q625 06:30:50 in
JH007BD 12:23:42 out
ZA3Q625 23:55:00 in
JH007BD 12:24:23 out
ZA133CH 17:11:22 out
JH007BD 18:07:01 out
DB8888A 06:30:50 in
05:10:00
06:30:50
11:00:00
12:23:42
14:00:00
18:00:00
23:59:00

Sample Output:

1
4
5
2
1
0
1
JH007BD ZD00001 07:20:09

将题目给出的数据按找车牌进行排序，时间早的在前面，这样排列得到的顺序可以很方便的找到合法的车辆进出时间。提取出正确的车辆进出的顺序，再根据时间进行查询当前时间车辆的个数。 这里可以将时间转化成秒来判断时间的先后顺序。

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

#include <cstdio>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <cstring>
#include <cstdlib>
#include <algorithm>

using namespace std;

struct node {
    char plate[8];
    int time, status;
};

int cmpByName(const void *a, const void *b) {
    struct node ai = *static_cast<const struct node *>(a);
    struct node bi = *static_cast<const struct node *>(b);
    int res = strcmp(ai.plate, bi.plate);
    return res == 0 ? (ai.time - bi.time) : (res < 0 ? -1 : 1);
}

bool cmpByTime(struct node a, struct node b) {
    if (a.time == b.time) return strcmp(a.plate, b.plate) < 0;
    return a.time < b.time;
}

vector<struct node> car;

int query(int &startIndex, int time, int cnt) {
    for (int i = startIndex; i < car.size(); i++) {
        if (car[i].time <= time) {
            if (car[i].status == 1) {
                cnt++;
            } else if (car[i].status == 0) {
                cnt--;
            }
        } else {
            startIndex = i;
            break;
        }
    }
    return cnt;
}

int main() {
    int n = 0, k = 0;
    scanf("%d %d", &n, &k);
    struct node *input = new struct node[n];
    for (int i = 0; i < n; i++) {
        char temp[4];
        int hour, minute, second;
        scanf("%s %d:%d:%d %s", input[i].plate, &hour, &minute, &second, temp);
        input[i].time = hour * 3600 + minute * 60 + second;
        strcmp(temp, "in") == 0 ? input[i].status = 1 : input[i].status = 0;
    }
    qsort(input, n, sizeof(*input), cmpByName);

    map<string, int> parkTime;
    int longestTime = 0;
    for (int i = 1; i < n; i++) {
        if (strcmp(input[i - 1].plate, input[i].plate) == 0 &&
            input[i - 1].status == 1 && input[i].status == 0) {
            car.push_back(input[i - 1]);
            car.push_back(input[i]);
            parkTime[input[i].plate] += input[i].time - input[i - 1].time;
            if (longestTime < parkTime[input[i].plate]) {
                longestTime = parkTime[input[i].plate];
            }
        }
    }
    sort(car.begin(), car.end(), cmpByTime);

    int cnt = 0, startIndex = 0;
    for (int i = 0; i < k; i++) {
        int hour = 0, minute = 0, second = 0;
        scanf("%d:%d:%d", &hour, &minute, &second);
        int time = hour * 3600 + minute * 60 + second;
        cnt = query(startIndex, time, cnt);
        printf("%d\n", cnt);
    }

    for (auto it : parkTime) {
        if (it.second == longestTime) {
            printf("%s ", it.first.c_str());
        }
    }
    printf("%02d:%02d:%02d", longestTime / 3600, longestTime % 3600 / 60, longestTime % 60);
    return 0;
}

参考：https://www.liuchuo.net/archives/2951

Given N integers, you are supposed to find the smallest positive integer that is NOT in the given list.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<= 105). Then N integers are given in the next line, separated by spaces. All the numbers are in the range of int.

Output Specification:

Print in a line the smallest positive integer that is missing from the input list.

Sample Input:

10
5 -25 9 6 1 3 4 2 5 17

Sample Output:

7

保留给出序列中的所有正数，将其排列，判断是否与下标+1相等，不等即找到这个没有在输入序列中出现的最小正整数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include <iostream>
#include <set>

int main() {
    int n = 0, t = 0, idx = 1;
    scanf("%d", &n);
    std::set<int> v;
    for (int i = 0; i < n; i++) {
        scanf("%d", &t);
        if (t > 0) v.insert(t);
    }
    
    for (auto it = v.begin(); it != v.end(); it++, idx++) {
        if (*it != idx) break;
    }
    printf("%d", idx);
    return 0;
}

A clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. A maximal clique is a clique that cannot be extended by including one more adjacent vertex. (Quoted from https://en.wikipedia.org/wiki/Clique_(graph_theory)) Now it is your job to judge if a given subset of vertices can form a maximal clique.

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers Nv (<= 200), the number of vertices in the graph, and Ne, the number of undirected edges. Then Ne lines follow, each gives a pair of vertices of an edge. The vertices are numbered from 1 to Nv. After the graph, there is another positive integer M (<= 100). Then M lines of query follow, each first gives a positive number K (<= Nv), then followed by a sequence of K distinct vertices. All the numbers in a line are separated by a space.

Output Specification:

For each of the M queries, print in a line “Yes” if the given subset of vertices can form a maximal clique; or if it is a clique but not a maximal clique, print “Not Maximal”; or if it is not a clique at all, print “Not a Clique”.

Sample Input:

8 10
5 6
7 8
6 4
3 6
4 5
2 3
8 2
2 7
5 3
3 4
6
4 5 4 3 6
3 2 8 7
2 2 3
1 1
3 4 3 6
3 3 2 1

Sample Output:

Yes
Yes
Yes
Yes
Not Maximal
Not a Clique

满足两两之间有边连接的顶点的集合，被称为该无向图的团。 因为要频繁的判断两个点是否连通，所以使用邻接矩阵来存储。 judge函数即判断给出的一系列是是否是团、以及最大团。 judge函数的第一块for循环是判断给出的点本身是否两两相通，如果存在不相通的两个点，则它不是一个团。 judge函数的第二块for循环是判断是否在图中一个其他结点与给出的结点序列中的所有结点都相通。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include <iostream>

int vt[210][210];

void judge(int *arr, int n, int nv) {
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (!vt[arr[i]][arr[j]]) {
                printf("Not a Clique\n");
                return;
            }
        }
    }
    for (int i = 1; i <= nv; i++) {
        int cnt = 0;
        for (int j = 0; j < n; j++) {
            if (vt[i][arr[j]]) {
                cnt++;
            }
        }
        if (cnt == n) {
            printf("Not Maximal\n");
            return;
        }
    }
    printf("Yes\n");
}

int main() {
    int nv = 0, ne = 0, a = 0, b = 0, m = 0, k = 0;
    scanf("%d %d", &nv, &ne);
    for (int i = 0; i < ne; i++) {
        scanf("%d %d", &a, &b);
        vt[a][b] = vt[b][a] = 1;
    }
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        scanf("%d", &k);
        int *arr = new int[k];
        for (int j = 0; j < k; j++) {
            scanf("%d", &arr[j]);
        }
        judge(arr, k, nv);
    }
    return 0;
}

Given an integer with no more than 9 digits, you are supposed to read it in the traditional Chinese way. Output Fu first if it is negative. For example, -123456789 is read as Fu yi Yi er Qian san Bai si Shi wu Wan liu Qian qi Bai ba Shi jiu. Note: zero (ling) must be handled correctly according to the Chinese tradition. For example, 100800 is yi Shi Wan ling ba Bai.

Input Specification:

Each input file contains one test case, which gives an integer with no more than 9 digits.

Output Specification:

For each test case, print in a line the Chinese way of reading the number. The characters are separated by a space and there must be no extra space at the end of the line.

Sample Input 1:

-123456789

Sample Output 1:

Fu yi Yi er Qian san Bai si Shi wu Wan liu Qian qi Bai ba Shi jiu

Sample Input 2:

100800

Sample Output 2:

yi Shi Wan ling ba Bai

先将数字对应字符串的值和位对应字符串的值构造出来。如果0位置的字符是负号，就将字符串的0位置去掉。每次去输出0位置的值，如果0位置的值是零并且是万位，就输出Wan；如果0位置的值不是零，查看当前位置的前几次有没有零值，有就要输出ling，然后输出0位置的值和所在的位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

#include <iostream>
#include <map>
#include <string>

using namespace std;

map<char, string> initMap() {
    map<char, string> res;
    res['0'] = "ling";
    res['1'] = "yi";
    res['2'] = "er";
    res['3'] = "san";
    res['4'] = "si";
    res['5'] = "wu";
    res['6'] = "liu";
    res['7'] = "qi";
    res['8'] = "ba";
    res['9'] = "jiu";
    return res;
}

map<int, string> initSiteMap() {
    map<int, string> res;
    res[2] = "Shi";
    res[3] = "Bai";
    res[4] = "Qian";
    res[5] = "Wan";
    res[6] = "Shi";
    res[7] = "Bai";
    res[8] = "Qian";
    res[9] = "Yi";
    return res;
}

int main() {
    string num;
    cin >> num;
    if (num[0] == '-') {
        cout << "Fu ";
        num = num.substr(1);
    }
    map<char, string> unit = initMap();
    map<int, string> site = initSiteMap();
    bool isZero = false;
    cout << unit[num[0]];
    if (num.length() > 1) {
        cout << " " << site[num.length()];
    }
    num = num.substr(1);
    while (num.length() > 0) {
        if (num[0] == '0') {
            isZero = true;
            if (num.length() == 5) {
                cout << " " << site[5];
            }
        } else {
            if (isZero) {
                cout << " ling";
            }
            isZero = false;
            cout << " " << unit[num[0]];
            if (num.length() > 1) {
                cout << " " << site[num.length()];
            }
        }
        num = num.substr(1);
    }
    cout << "Hello World." << endl;
    return 0;
}

In the big cities, the subway systems always look so complex to the visitors. To give you some sense, the following figure shows the map of Beijing subway. Now you are supposed to help people with your computer skills! Given the starting position of your user, your task is to find the quickest way to his/her destination.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (≤ 100), the number of subway lines. Then N lines follow, with the i-th (i=1,⋯,N) line describes the i-th subway line in the format:

M S[1] S[2] … S[M]

where M (≤ 100) is the number of stops, and S[i]’s (i=1,⋯,M) are the indices of the stations (the indices are 4-digit numbers from 0000 to 9999) along the line. It is guaranteed that the stations are given in the correct order – that is, the train travels between S[i] and S[i+1] (i=1,⋯,M−1) without any stop.

Note: It is possible to have loops, but not self-loop (no train starts from S and stops at S without passing through another station). Each station interval belongs to a unique subway line. Although the lines may cross each other at some stations (so called “transfer stations”), no station can be the conjunction of more than 5 lines.

After the description of the subway, another positive integer K (≤ 10) is given. Then K lines follow, each gives a query from your user: the two indices as the starting station and the destination, respectively.

The following figure shows the sample map.

Note: It is guaranteed that all the stations are reachable, and all the queries consist of legal station numbers.

Output Specification:

For each query, first print in a line the minimum number of stops. Then you are supposed to show the optimal path in a friendly format as the following:

1
2
3

Take Line#X1 from S1 to S2.
Take Line#X2 from S2 to S3.
......

where Xi’s are the line numbers and Si’s are the station indices. Note: Besides the starting and ending stations, only the transfer stations shall be printed.

If the quickest path is not unique, output the one with the minimum number of transfers, which is guaranteed to be unique.

Sample Input:

1
2
3
4
5
6
7
8
9

4
7 1001 3212 1003 1204 1005 1306 7797
9 9988 2333 1204 2006 2005 2004 2003 2302 2001
13 3011 3812 3013 3001 1306 3003 2333 3066 3212 3008 2302 3010 3011
4 6666 8432 4011 1306
3
3011 3013
6666 2001
2004 3001

Sample Output:

1
2
3
4
5
6
7
8
9
10

2
Take Line#3 from 3011 to 3013.
10
Take Line#4 from 6666 to 1306.
Take Line#3 from 1306 to 2302.
Take Line#2 from 2302 to 2001.
6
Take Line#2 from 2004 to 1204.
Take Line#1 from 1204 to 1306.
Take Line#3 from 1306 to 3001.

用深搜每次去找路径，每找到一条，就判断是否满足更新的条件，满足就更新 后面的点与前面的点不在同一条地铁线路上就打印换乘 代码中函数的作用，都已经注释好了，如果还有不懂的，欢迎评论~

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

#include <cstdio>
#include <vector>

using namespace std;

// MAX表示边界，path是用作dfs的临时路径，finalPath是更新之后的最终路径
// subway是地铁图
// minCnt是经过站的最少次数，minTranf是换成的最少次数，line是图中两点的地铁线号，isVisited是dfs用的标记
const int MAX = 10010;
vector<int> path, finalPath;
vector<vector<int> > subway(MAX);
int minCnt = MAX, minTranf = MAX, line[MAX][MAX], isVisited[MAX];

// 打印换成路径
void printTrace() {
    printf("%d\n", minCnt);
    int sourceIndex = 0, preLine = line[finalPath[0]][finalPath[1]];
    for (int i = 1; i < finalPath.size(); i++) {
        int tempLine = line[finalPath[i - 1]][finalPath[i]];
        if (tempLine != preLine) {
            printf("Take Line#%d from %04d to %04d.\n", preLine, finalPath[sourceIndex], finalPath[i - 1]);
            sourceIndex = i - 1;
            preLine = tempLine;
        }
    }
    printf("Take Line#%d from %04d to %04d.\n", preLine, finalPath[sourceIndex], finalPath[finalPath.size() - 1]);
}

// 获取换乘的次数
int getTransf(vector<int> a) {
    int cnt = 0, preLine = 0;
    for (int i = 1; i < a.size(); i++) {
        int tempLine = line[a[i - 1]][a[i]];
        if (preLine != tempLine) {
            cnt++;
            preLine = tempLine;
        }
    }
    return cnt;
}

// 深搜所有的路径，找到目的点的时候，记录将满足题目限制的路径
void dfs(int current, int dest, int cnt) {
    if (dest == current) {
        int tempMinTransf = getTransf(path);
        if (cnt < minCnt || (cnt == minCnt && tempMinTransf < minTranf)) {
            minCnt = cnt;
            finalPath = path;
            minTranf = tempMinTransf;
        }
        return;
    }
    for (int i = 0; i < subway[current].size(); i++) {
        int temp = subway[current][i];
        if (!isVisited[temp]) {
            isVisited[temp] = true;
            path.push_back(temp);
            dfs(temp, dest, cnt + 1);
            path.pop_back();
            isVisited[temp] = false;
        }
    }
}

int main() {
    int n = 0, k = 0, m = 0, pre = 0, temp = 0, source = 0, dest = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &m, &pre);
        for (int j = 1; j < m; j++) {
            scanf("%d", &temp);
            line[temp][pre] = line[pre][temp] = i;
            subway[pre].push_back(temp);
            subway[temp].push_back(pre);
            pre = temp;
        }
    }
    scanf("%d", &k);
    for (int i = 0; i < k; i++) {
        scanf("%d %d", &source, &dest);
        minCnt = MAX;
        isVisited[source] = true;
        path.push_back(source);
        dfs(source, dest, 0);
        printTrace();
        path.clear();
        isVisited[source] = false;
        finalPath.clear();
    }
    return 0;
}

Recommendation system predicts the preference that a user would give to an item. Now you are asked to program a very simple recommendation system that rates the user’s preference by the number of times that an item has been accessed by this user.

Input Specification:

Each input file contains one test case. For each test case, the first line contains two positive integers: N (≤ 50,000), the total number of queries, and K (≤ 10), the maximum number of recommendations the system must show to the user. Then given in the second line are the indices of items that the user is accessing – for the sake of simplicity, all the items are indexed from 1 to N. All the numbers in a line are separated by a space.

Output Specification:

For each case, process the queries one by one. Output the recommendations for each query in a line in the format:

1

query: rec[1] rec[2] ... rec[K]

where query is the item that the user is accessing, and rec[i] (i=1, … K) is the i-th item that the system recommends to the user. The first K items that have been accessed most frequently are supposed to be recommended in non-increasing order of their frequencies. If there is a tie, the items will be ordered by their indices in increasing order.

Note: there is no output for the first item since it is impossible to give any recommendation at the time. It is guaranteed to have the output for at least one query.

Sample Input:

12 3
3 5 7 5 5 3 2 1 8 3 8 12

Sample Output:

5: 3
7: 3 5
5: 3 5 7
5: 5 3 7
3: 5 3 7
2: 5 3 7
1: 5 3 2
8: 5 3 1
3: 5 3 1
8: 3 5 1
12: 3 5 8

这个题目做起来还是有点艰辛的，想了好久。 一开始用的map，超时了。后来用set，插入的时候先删除，AC了。主要是用map不能直接按值排序，变相的方法是放在一个线性的容器中，用sort或者qsort去排序，依然超时。用set，插入的时候，先查找元素是否存在，存在则删除，插入一个新的值。这样构造出来的set是按元素出现的次数排好序的，可以直接输出set元素的前k(k > set.size)个，否则就输出set的全部元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

#include <cstdio>
#include <set>
#include <vector>

using namespace std;

struct node {
    int item, cnt;

    node(int a, int b) : item(a), cnt(b) {}

    bool operator<(const struct node a) const {
        if (cnt > a.cnt) return true;
        if (cnt < a.cnt) return false;
        if (item < a.item) return true;
        return false;
    }
};

set<node> query;
vector<int> times(50010);

void printQuery(int k) {
    int i = 0;
    for (auto it = query.begin(); i < k && it != query.end(); it++, i++) {
        printf(" %d", it->item);
    }
    printf("\n");
}

int main() {
    int n = 0, k = 0, pre = 0, item = 0;;
    scanf("%d %d %d", &n, &k, &pre);
    for (int i = 1; i < n; i++) {
        scanf("%d", &item);
        printf("%d:", item);
        auto f = query.find(node(pre, times[pre]));
        if (f != query.end()) {
            query.erase(f);
        }
        times[pre]++;
        query.insert(node(pre, times[pre]));
        printQuery(k);
        pre = item;
    }
    return 0;
}

There is a public bike service in Hangzhou City which provides great convenience to the tourists from all over the world. One may rent a bike at any station and return it to any other stations in the city. The Public Bike Management Center (PBMC) keeps monitoring the real-time capacity of all the stations. A station is said to be in perfect condition if it is exactly half-full. If a station is full or empty, PBMC will collect or send bikes to adjust the condition of that station to perfect. And more, all the stations on the way will be adjusted as well. When a problem station is reported, PBMC will always choose the shortest path to reach that station. If there are more than one shortest path, the one that requires the least number of bikes sent from PBMC will be chosen.

Figure 1 illustrates an example. The stations are represented by vertices and the roads correspond to the edges. The number on an edge is the time taken to reach one end station from another. The number written inside a vertex S is the current number of bikes stored at S. Given that the maximum capacity of each station is 10. To solve the problem at S3, we have 2 different shortest paths: 1. PBMC -> S1 -> S3. In this case, 4 bikes must be sent from PBMC, because we can collect 1 bike from S1 and then take 5 bikes to S3, so that both stations will be in perfect conditions. 2. PBMC -> S2 -> S3. This path requires the same time as path 1, but only 3 bikes sent from PBMC and hence is the one that will be chosen.

Input Specification:

Each input file contains one test case. For each case, the first line contains 4 numbers: Cmax (<= 100), always an even number, is the maximum capacity of each station; N (<= 500), the total number of stations; Sp, the index of the problem station (the stations are numbered from 1 to N, and PBMC is represented by the vertex 0); and M, the number of roads. The second line contains N non-negative numbers Ci(i=1,…N) where each Ci is the current number of bikes at Si respectively. Then M lines follow, each contains 3 numbers: Si, Sj, and Tij which describe the time Tij taken to move betwen stations Si and Sj. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print your results in one line. First output the number of bikes that PBMC must send. Then after one space, output the path in the format: 0->S1->…->Sp. Finally after another space, output the number of bikes that we must take back to PBMC after the condition of Sp is adjusted to perfect. Note that if such a path is not unique, output the one that requires minimum number of bikes that we must take back to PBMC. The judge’s data guarantee that such a path is unique.

Sample Input:

10 3 3 5
6 7 0
0 1 1
0 2 1
0 3 3
1 3 1
2 3 1

Sample Output:

3 0->2->3 0

用Dijkstra查找最短路径，在更新路径的同时更新结点的sent和take back的状态。如果存在多条路径的长度相等，选择需要从0结点携带的自行车的数目最少的路径。如果存在多条路径的长度相等且需要携带的自行车数目也相等，那么需要选择从问题结点带回的自行车数目最少的路径。 case 7 没有过。问题在于Dijkstra算法的执行过程中，更新的sent和take back的状态不具有最有子结构，即局部最优无法得到全局最优。 对于测试用例： 10 4 4 5 4 8 9 0 0 1 1 1 2 1 1 3 2 2 3 1 3 4 1 在3号结点更新的时候，应该选择2号结点，而不是1号结点，虽然从1号结点过来可以得到最少的take back的自行车的数目，但是不是全局最优的。代码如下：

正确的代码，使用DFS的方式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <vector>

using namespace std;

const int inf = 99999999;
int graph[510][510];
int weight[510];
bool visited[510];

void initGraph() {
    for (int i = 0; i < 510; i++)
        for (int j = 0; j < 510; j++)
            graph[i][j] = inf;
}

vector<int> path, tPath;
int sent = inf, back = inf, shortest = inf;

void dfs(int cur, int sp, int n, int tlen, int tSent, int tBack) {
    if (cur == sp) {
        if (shortest > tlen) {
            shortest = tlen;
            path = tPath;
            sent = tSent;
            back = tBack;
        } else if (shortest == tlen) {
            if (sent > tSent) {
                sent = tSent;
                back = tBack;
                path = tPath;
            } else if (sent == tSent) {
                if (back > tBack) {
                    back = tBack;
                    path = tPath;
                }
            }
        }
    } else {
        for (int i = 1; i <= n; i++) {
            if (visited[i] == false && graph[cur][i] != inf) {
                visited[i] = true;
                tPath.push_back(i);
                if (weight[i] <= 0) {
                    if (abs(weight[i]) <= tBack) {
                        dfs(i, sp, n, tlen + graph[cur][i], tSent, tBack - abs(weight[i]));
                    } else {
                        dfs(i, sp, n, tlen + graph[cur][i], tSent + abs(weight[i]) - tBack, 0);
                    }
                } else {
                    dfs(i, sp, n, tlen + graph[cur][i], tSent, tBack + abs(weight[i]));
                }
                visited[i] = false;
                tPath.pop_back();
            }
        }
    }
}

int main() {
    int cmax = 0, n = 0, sp = 0, m = 0, si = 0, sj = 0, tij = 0;;
    scanf("%d %d %d %d", &cmax, &n, &sp, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &weight[i]);
        weight[i] -= cmax / 2;
    }
    initGraph();
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &si, &sj, &tij);
        graph[si][sj] = graph[sj][si] = tij;
    }
    dfs(0, sp, n, 0, 0, 0);
    printf("%d ", sent);
    printf("0");
    for (int i = 0; i < path.size(); i++) {
        printf("->%d", path[i]);
    }
    printf(" %d\n", back);
    return 0;
}

A number that will be the same when it is written forwards or backwards is known as a Palindromic Number. For example, 1234321 is a palindromic number. All single digit numbers are palindromic numbers. Although palindromic numbers are most often considered in the decimal system, the concept of palindromicity can be applied to the natural numbers in any numeral system. Consider a number N > 0 in base b >= 2, where it is written in standard notation with k+1 digits ai as the sum of (aibi) for i from 0 to k. Here, as usual, 0 <= ai < b for all i and ak is non-zero. Then N is palindromic if and only if ai = ak-i for all i. Zero is written 0 in any base and is also palindromic by definition. Given any non-negative decimal integer N and a base b, you are supposed to tell if N is a palindromic number in base b.

Input Specification:

Each input file contains one test case. Each case consists of two non-negative numbers N and b, where 0 <= N <= 109 is the decimal number and 2 <= b <= 109 is the base. The numbers are separated by a space.

Output Specification:

For each test case, first print in one line “Yes” if N is a palindromic number in base b, or “No” if not. Then in the next line, print N as the number in base b in the form “ak ak-1 … a0”. Notice that there must be no extra space at the end of output.

Sample Input 1:

27 2

Sample Output 1:

Yes
1 1 0 1 1

Sample Input 2:

121 5

Sample Output 2:

No
4 4 1

题意：判断一个数是否是回文数 先将n转换成b进制，用vector<int>储存转换后的数字，判断从前向后的vector和从后向前的vector是否相等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <cstdio>
#include <vector>

int main() {
    int n = 0, b = 0;
    scanf("%d %d", &n, &b);
    std::vector<int> v;
    do {
        v.push_back(n % b);
        n /= b;
    } while (n != 0);
    bool equal = true;
    for (int i = 0; i < v.size() / 2; i++) {
        if (v[i] != v[v.size() - i - 1]) {
            equal = false;
        }
    }
    printf("%s\n", equal ? "Yes" : "No");
    for (auto it = v.rbegin(); it != v.rend(); it++) {
        if (it == v.rbegin()) printf("%d", *it);
        else printf(" %d", *it);
    }
    return 0;
}

The lowest common ancestor (LCA) of two nodes U and V in a tree is the deepest node that has both U and V as descendants. A binary search tree (BST) is recursively defined as a binary tree which has the following properties:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
• Both the left and right subtrees must also be binary search trees.

Given any two nodes in a BST, you are supposed to find their LCA.

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers: M (<= 1000), the number of pairs of nodes to be tested; and N (<= 10000), the number of keys in the BST, respectively. In the second line, N distinct integers are given as the preorder traversal sequence of the BST. Then M lines follow, each contains a pair of integer keys U and V. All the keys are in the range of int.

Output Specification:

For each given pair of U and V, print in a line “LCA of U and V is A.” if the LCA is found and A is the key. But if A is one of U and V, print “X is an ancestor of Y.” where X is A and Y is the other node. If U or V is not found in the BST, print in a line “ERROR: U is not found.” or “ERROR: V is not found.” or “ERROR: U and V are not found.”.

Sample Input:

6 8
6 3 1 2 5 4 8 7
2 5
8 7
1 9
12 -3
0 8
99 99

Sample Output:

LCA of 2 and 5 is 3.
8 is an ancestor of 7.
ERROR: 9 is not found.
ERROR: 12 and -3 are not found.
ERROR: 0 is not found.
ERROR: 99 and 99 are not found.

给出两个结点，找他们的最近的祖先结点。 把所有的结点值放到set中，便于查找没有出现的结点。 如果两个结点的值比当前子树的根结点的值小，则左递归；如果两个结点的值比当前子树的根结点的值大，则右递归。否则，当前子树的根结点就是最近的公共祖先。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

#include <iostream>
#include <set>

using namespace std;

int *pre;

int idx(int l, int r, int x) {
    for (int i = l; i <= r; i++)
        if (pre[i] >= x) return i;
    return -1;
}

int find_lca(int l, int r, int a, int b) {
    if (a < pre[l] && b < pre[l]) return find_lca(l + 1, idx(l + 1, r, pre[l]) - 1, a, b);
    if (a > pre[l] && b > pre[l]) return find_lca(idx(l + 1, r, pre[l]), r, a, b);
    return pre[l];
}

int main() {
    int m = 0, n = 0, a = 0, b = 0;
    scanf("%d %d", &m, &n);
    pre = new int[n + 1];
    set<int> s;
    for (int i = 0; i < n; i++) {
        scanf("%d", &pre[i]);
        s.insert(pre[i]);
    }
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &a, &b);
        if (s.find(a) == s.end() && s.find(b) == s.end()) {
            printf("ERROR: %d and %d are not found.\n", a, b);
        } else if (s.find(a) == s.end()) {
            printf("ERROR: %d is not found.\n", a);
        } else if (s.find(b) == s.end()) {
            printf("ERROR: %d is not found.\n", b);
        } else {
            int ac = find_lca(0, n - 1, a, b);
            if (ac == a) {
                printf("%d is an ancestor of %d.\n", a, b);
            } else if (ac == b) {
                printf("%d is an ancestor of %d.\n", b, a);
            } else {
                printf("LCA of %d and %d is %d.\n", a, b, ac);
            }
        }
    }
    return 0;
}

Look-and-say sequence is a sequence of integers as the following:

D, D1, D111, D113, D11231, D112213111, …

where D is in [0, 9] except 1. The (n+1)st number is a kind of description of the nth number. For example, the 2nd number means that there is one D in the 1st number, and hence it is D1; the 2nd number consists of one D (corresponding to D1) and one 1 (corresponding to 11), therefore the 3rd number is D111; or since the 4th number is D113, it consists of one D, two 1’s, and one 3, so the next number must be D11231. This definition works for D = 1 as well. Now you are supposed to calculate the Nth number in a look-and-say sequence of a given digit D.

Input Specification:

Each input file contains one test case, which gives D (in [0, 9]) and a positive integer N (<=40), separated by a space.

Output Specification:

Print in a line the Nth number in a look-and-say sequence of D.

Sample Input:

1 8

Sample Output:

1123123111

用字符串描述上一个字符串，即从左往右，每个数连续出现的次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <iostream>
#include <string>

using namespace std;

string read(string source) {
    string result;
    int cnt = 1;
    for (int i = 1; i < source.size(); i++) {
        if (source[i] != source[i - 1]) {
            result += to_string(source[i - 1] - '0') + to_string(cnt);
            cnt = 0;
        }
        cnt++;
    }
    result += to_string(*source.rbegin() - '0') + to_string(cnt);
    return result;
}

int main() {
    int d = 0, n = 0;
    scanf("%d %d", &d, &n);
    string s = to_string(d);
    for (int i = 1; i < n; i++)
        s = read(s);
    printf("%s", s.c_str());
    return 0;
}