1001 收集金币

Sample Input

2 
3 
LOST 10 
GET 20 
LOST 5 
3 
GET 20 
LOST 5 
LOST 10 

Sample Output

20 
15 

思路

/*
直接确定跳过哪次可能不太好确定，考虑设f[i][0/1]为考虑前i个事件
中，是否已经使用跳过操作，能获得的最多金币个数。
转移的时候枚举当前位置是否选择跳过。
对于LOST事件：
    f[i][1] = max(f[i - 1][0], max(f[i - 1][1] - w, 0));
    f[i][0] = max(f[i - 1][0] - w, 0);
对于GET事件：
    f[i][1] = f[i - 1][1] + w;
    f[i][0] = f[i - 1][0] + w;
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#define INF 0x3f3f3f3f
using namespace std;

typedef long long LL;
const int N = 20010;
int n;
char op[5];
LL f[N][2];

int main() {
    int T;
    scanf("%d", &T);

    while (T -- ) {
        scanf("%d", &n);
        LL ans = 0;
        int w;
        f[0][0] = 0;
        f[0][1] = -1e15;

        for (int i = 1; i <= n; i ++ ) {

            scanf("%s %d", op, &w);

            if (op[0] == 'L') {
                f[i][1] = max(f[i - 1][0], max(f[i - 1][1] - w, 0LL));
                f[i][0] = max(0LL, f[i - 1][0] - w);
            } else {
                f[i][1] = f[i - 1][1] + w;
                f[i][0] = f[i - 1][0] + w;
            }
        }

        printf("%lld\n", max(f[n][0], f[n][1]));
    }

    return 0;
}

1002 使用技能

Sample Input

2 
5 4 
8 4 

Sample Output

10 
22 

1003 欢度佳节

Sample Input

2 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
10 
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 
100 

Sample Output

10 
17 

1005 闯关游戏

Sample Input

2 
2 8 
2 2 1 2 
1 4 3 3 
4 9 
3 1 3 2 
2 2 2 2 
4 3 3 1 
2 4 2 1 

Sample Output

6 
7 

1006 军训

Sample Input

5 
52 
13 
17 
63 
81 

Sample Output

0 
0 
0 
3 
1 

1007 数“X”

Sample Input

1 
4 
3 4 3 1 
1 4 2 4 
4 4 1 3 
3 3 3 4 

Sample Output

18 

1008 小y爱数数

Sample Input

5 
10 3 
1 0 
2 0 
3 1 
4 2 

Sample Output

13459 
其中每组询问答案分别为7700，15834，7778，8750

1009 神奇的魔法

Sample Input

1 
2 3 2 
2 3 4 
3 4 5 
1 2 
2 3 

Sample Output

19 

1010 小凯的书架

Sample Input

1 
10 3 
852273206 148560760 979303226 716148781 133605412 464797992 315860976 653152358 898884753 545164585 

Sample Output

-1 
-1 
-1 
-1 
148560760 
852273206 
979303226 
852273206 
-1 
716148781 

思路

/*
由于数据随机，对于每本书，暴力往左找第k本满足条件的书，复杂度为O(n*k)
*/
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;

const int N = 1e5 + 10;
int a[N];

int solve(int x, int k) {
    for (int i = x - 1; i >= 1; i -- ) {

        if (a[i] > a[x])
            k -- ;

        if (k == 0)
            return a[i];
    }

    return -1;
}

int main() {
    int T;
    scanf("%d", &T);

    while (T -- ) {
        int n, k;
        scanf("%d%d", &n, &k);

        for (int i = 1; i <= n; i ++ )

            scanf("%d", &a[i]);

        for (int i = 1; i <= n; i ++ )

            printf("%d\n", solve(i, k));
    }

    return 0;
}

1011 未成年人之友

Sample Input

3 
18 Mon 08:00 
17 Sun 23:00 
1 Sat 20:30 

Sample Output

Yes 
No 
Yes 

思路

/*
签到题，别搞错输入就行
*/
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int age, H, M;
char week[5];

int main() {
    int T;
    scanf("%d", &T);

    while (T -- ) {
        scanf("%d%s%d:%d", &age, week, &H, &M);

        if (age >= 18)
            puts("Yes");
        else {
            if ((*week == 'F' || *week == 'S') && H == 20)
                puts("Yes");
            else
                puts("No");
        }
    }

    return 0;
}

1012 黑曜石

Sample Input

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

Sample Output

1 
1 
4 

思路

/*
签到题。可知，只有水和岩浆相邻，或者水和岩浆中间只隔了空气，才可
能生成新的黑曜石。因此答案为 一开始的黑曜石数 + 按高度排序后水和岩
浆相邻的个数。
*/
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

struct node {
    int size;
    int h;
} a[N];

bool cmp(node A, node B) {
    return A.h > B.h;
}

int main() {
    int T;
    scanf("%d", &T);

    while (T -- ) {
        int n;
        scanf("%d", &n);
        int res = 0;

        for (int i = 1; i <= n; i ++ ) {

            scanf("%d%d", &a[i].size, &a[i].h);

            if (a[i].size == 3)
                res ++ ;
        }

        sort(a + 1, a + 1 + n, cmp);

        for (int i = 1; i < n; i ++ )

            if ((a[i].size + a[i + 1].size) == 3)
                res ++ ;
        printf("%d\n", res);
    }

    return 0;
}