发表于

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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;
}

发表于

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

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
#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;
}

发表于

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

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 <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点的距离

发表于

重点在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种颜色。

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 <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;
}

发表于

给一串数字，子序列之和为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.

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>
#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;
}