RC-u1

热҈热҈热҈……最近热得打的字都出汗了！

幸好某连锁餐厅开启了气温大于等于 35 度即可获得一杯免费雪碧的活动。但不知为何，在每个星期四的时候，这个活动会暂停一天……

现在给定连续的若干天的气温情况以及给定的第一天是星期几，请你算出有多少天你可以喝到免费的雪碧，又有多少天是因为星期四而导致你喝不到雪碧的。

输入格式:

输入第一行是两个正整数 N, W (1≤N≤50,1≤W≤7)，表示给定连续的 N 天，下面给定的第一天是星期 W（7 等于星期天）。

接下来的一行给出 N 个用一个空格隔开的、小于 60 的整数，第 i 个数表示第 i 天的温度。保证温度大于等于 -273 度。

输出格式:

输出两个数，第一个是你能喝到免费雪碧的天数，第二个是你本来能喝到免费雪碧、但因为是星期四而无法喝到的天数。

输入样例:

15 3
33 35 34 36 37 40 32 31 30 29 28 29 33 38 40

输出样例:

5 3

思路：

        简单模拟题，简单说一下我的周数处理，将w % 7， 这样w就只有0~6个取值，0表示周一， 6表示周日，所以在执行循环前w先减去1，因为我是每次循环开始前w++，所以w再减去1，对w的预处理为w - 2。

AC CODE：

#include <iostream>
using namespace std;
const int N = 55;
int main()
{
    int n, w;
    cin >> n >> w;
    w -= 2;
    int a = 0, b = 0;
    for(int i = 1; i <= n; i ++)
    {
        w ++;
        int x;
        cin >> x;
        w = w % 7;
        if(x >= 35 && w == 3) b ++;
        else if(x >= 35) a ++;
    }
    cout << a << " " << b << endl;
}

RC-u2

Xepa Legends 是一个第一人称射击类大逃杀（“吃鸡”）游戏，每轮游戏共有 20 支 3 人小队参加，最后获胜的队伍被称为“捍卫者”。

最近 Xepa Legends 举行了亚太地区南赛区的线上比赛，争夺 7 个前往德国曼海姆参加线下赛的资格，国内共有 14 支队伍参与到了其中。因为比赛十分激烈，直到最后谁进了线下仍有巨大的疑问。小 K 喜欢的国内知名战队 DreamTear 因其队内选手杀马特表现不佳，正好卡在出线分数前后，请你赶紧帮帮小 K，计算一下最后的分数情况，看看他喜欢的战队出线了没有吧！

Xepa Legends 的比赛共进行 N 场游戏，在每场游戏中，每支队伍在游戏中会获得一个排名和一个杀敌数（击败其他队伍玩家的数量），一支队伍在一场游戏的得分为杀敌数+排名分，排名分由队伍当场的排名根据以下表格求得：

排名	分数
第一名	12 分
第二名	9 分
第三名	7 分
第四名	5 分
第五名	4 分
第六名至第七名	3 分
第八名至第十名	2 分
第十一名至第十五名	1 分
第十六名至第二十名	0 分

例如，

• DreamTear 战队在第三场比赛获得了第三名、有 6 个杀敌数，那么他们将获得 7 + 6 = 13 分；
• KV 战队在第二场比赛获得了第 19 名、有 1 个杀敌数，那么他们将获得 0 + 1 = 1 分；
• SRN 战队在第四场比赛获得了第 1 名、有 9 个杀敌数，那么他们将获得 12 + 9 = 21 分。

注：本题与实际情况无关，所有比赛规则、队伍、队员名称均为虚构。

输入格式:

输入第一行是一个正整数 N (≤20)，表示有 N 场比赛。

接下来有 N 部分输入，每部分是一场比赛的情况。对每一场比赛，信息共分 20 行，第 i 行（i=1,⋯,20）给出的两个非负整数 p 和 k 表示第 i 支队伍在这场比赛里获得了第 p 名、杀敌数为 k。

数据保证所有给定的情况中，排名永远大于等于 1 且小于等于 20，杀敌数小于等于 57。

输出格式:

输出 20 行，按编号从小到大依次输出队伍的编号及该队全部游戏结束时的总分。

输入样例:

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

输出样例:

1 9
2 13
3 27
4 30
5 33
6 25
7 4
8 27
9 24
10 12
11 19
12 18
13 8
14 18
15 4
16 17
17 16
18 8
19 12
20 6

思路：

        模拟题，用数组将对应排名分数记录，计算每队分数时直接取出对应排名的得分+杀敌数，最后输出结果即可。

AC CODE：

#include <iostream>
using namespace std;

const int N = 25;

int a[N];
int s[21] = {0, 12, 9, 7, 5, 4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0};

int main()
{
    int n;
    cin >> n;
    while(n --)
    {
        for(int i = 1; i <= 20; i ++)
        {
            int p, k;
            cin >> p >> k;
            a[i] += s[p] + k;
        }
    }

    for(int i = 1; i <= 20; i ++) cout << i << " " << a[i] << endl;
}

RC-u3

PapiCon（@PapilloteContet）出了许多有意思的谜题，其中有一道关于水豚的谜题是这样的：

来源：x.com/PapilloteContet

在一个 N×M 的矩阵中有若干水豚以及暖炉，暖炉可以辐射以它自身为中心的 3×3 范围里的水豚，使其变得暖呼呼的。谜题里存在一只冷的要命的水豚，你需要移动其中的一个暖炉，使所有水豚都变得暖呼呼的。

在往下读题前，如果你有兴趣的话，不妨思考一下如何解答这个谜题。（思考结果与题目无关，可跳过。）

这个谜题的关键在于，单纯从图中能看到的暖炉来说是无解的，但如果注意到，第 3 行第 6 列的水豚明明周围没有暖炉，却也处于暖呼呼的状态，就能推测出来图中的那个对话框挡住了一个暖炉，只要移动这个暖炉就可以完成题目的要求。

现在我们将谜题一般化，对于给定的一个 N×M 的矩阵、对应的所有水豚状态、以及能看到的暖炉摆放情况，已知最多只有一只水豚的状态不太对劲（周围没有暖炉却暖呼呼的），你需要推测有哪些格子可能藏了暖炉。一个空格可能藏了暖炉可以理解为：当前空格设置暖炉后整个矩阵的状态会从不合法变为合法。

输入格式:

输入第一行是两个正整数 N, M (1≤N,M≤1000)，表示矩阵的大小。

接下来的 N 行，每行有 M 个字符，第 i 行的第 j 个字符表示矩阵中对应位置的状态，其中：

• . 表示空格（或者说，看上去是空格的格子）；
• c 表示很冷的水豚；
• w 表示暖呼呼的水豚；
• m 表示暖炉。

输出格式:

输出若干行，每行两个正整数 r 和 c，表示第 r 行第 c 列有可能藏了一个暖炉，有多个可能时，先按 r 从小到大输出，r 相同时再按 c 从小到大输出。如果没有一个格子可能藏了暖炉， 则在一行中输出Too cold!。
行与列均从 1 开始编号。

输入样例:

6 8
wm....mw
.w..ww..
..wm.wwm
w.w....w
.m.c.m..
w.....w.

输出样例:

2 7
3 5
4 6
4 7

思路：

        这题让我们找出可能有暖炉的位置，先将有暖炉的地方四周标记出来，然后遍历每个空格，如果他的四周有温暖的水豚并且水豚的位置没有被暖炉标记，说明当前位置可以放暖炉， 但是如果当前位置四周存在冷的水豚那它就不可能放暖炉。

AC CODE：

#include <iostream>
using namespace std;

const int N = 1e3 + 10;
int type[N][N]; // 1表示此处收到暖炉的温暖
int mov[8][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, -1}, {1, 1}, {-1, 1}, {-1, -1}};
//偏移量
char a[N][N];
int n, m;

void warm(int x, int y) // 用于标记暖炉四周的位置
{
    type[x][y] = 1;
    for(int i = 0; i < 8; i ++)
    {
        int nx = x + mov[i][0];
        int ny = y + mov[i][1];
        if(nx > n || nx < 1 ||ny < 1 || ny > m) continue; // 超出矩阵返回
        type[nx][ny] = 1; // 标记此处受到暖炉的影响
    }
}

int check(int x, int y)
{
    int flag = 0;
    for(int i = 0; i < 8; i ++)
    {
        int nx = x + mov[i][0];
        int ny = y + mov[i][1];
        if(nx > n || nx < 1 ||ny < 1 || ny > m) continue;
        if(a[nx][ny] == 'w' && type[nx][ny] != 1) flag = 1; // 如果当前水豚温暖并且此处没有暖炉影响
        if(a[nx][ny] == 'c') return false; // 如果四周有寒冷的水豚，则此处不可能放暖炉
    }
    if(flag == 1) return true; // 可以放置暖炉
    else return false;
}
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
        {
            cin >> a[i][j];
        }
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
        {
            if(a[i][j] == 'm')
            {
                warm(i, j); // 更新暖炉四周的位置
            }
        }
    int flag = 0;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
        {
            if(a[i][j] == '.')
            {
                if(check(i, j)) // 当前位置可以放暖炉就直接输出坐标
                {
                    cout << i << " " << j << endl;
                    flag = 1;
                }
            }
        }
    if(flag == 0) cout << "Too cold!" << endl; // 没有可能存在的暖炉输出cool
}

RC-u4

对于无向图 G=(V,E)，我们将有且只有一个环的、大于 2 个顶点的无向连通图称之为章鱼图，因为其形状像是一个环（身体）带着若干个树（触手），故得名。

给定一个无向图，请你判断是不是只有一个章鱼子图存在。

输入格式:

输入第一行是一个正整数 T (1≤T≤5)，表示数据的组数。

每组数据的第一行是两个正整数 N,M (1≤N,M≤105)，表示给定的无向图有 N 个点，M 条边。

接下来的 M 行，每行给出一条边两个端点的顶点编号。注意：顶点编号从 1 开始，并且题目保证任何边不会重复给出，且没有自环。

输出格式:

对于每组数据，如果给定的图里只有一个章鱼子图，则在一行中输出 Yes 和章鱼子图环的大小（及环中顶点数），其间以 1 个空格分隔。

否则，则在一行中输出 No 和图中章鱼子图的个数，其间以 1 个空格分隔。

输入样例:

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

输出样例:

Yes 5
No 0
No 2

思路：

        这题是求图中环的数量，可以想到用并查集来维护，核心思路（这段话得好好理解一下）：如果当前连接的两个节点是同一个祖先的话，此时两节点建边就会产生一个环，然后用这个大环的祖先节点表示此环，记录此环的章鱼子图个数，如果只有一个环的话可以用bfs求最短路径来表示环中的节点（顶点）数。如果思路看起来比较模糊具体实现配合代码及注释食用。

AC CODE：

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

const int N = 1e5 + 10;

vector<int> g[N];
int f[N], cnt[N]; // 记章鱼子图个数
int dist[N];

int find(int x)
{
    if(x != f[x]) return f[x] = find(f[x]);
    else return f[x];
}
// 并查集基础函数

int bfs(int st, int ed) // bfs求最短路径模板
{
    queue<int> q;
    q.push(st);
    while(q.size())
    {
        int t = q.front();
        q.pop();
        for(auto x : g[t])
        {
            if(dist[x]) continue; // 用dist代替vist数组的标记功能
            if(t == st && x == ed) continue; // 这里是环上最短的点应该跳过
            // 这里是一个圆，最短路求出来一定是1，所以这条路径不能要
            dist[x] = dist[t] + 1;
            q.push(x);
            
        }
    }
    return dist[ed];
    
}
int main()
{
    int T;
    cin >> T;
    while(T --)
    {
        int n, m;
        cin >> n >> m;
        for(int i = 1; i <= n; i ++)
        {
            cnt[i] = 0;
            dist[i] = 0;
            g[i].clear();
            f[i] = i;
        } // 初始化
        int st, ed;
        while(m --)
        {
            int a, b;
            cin >> a >> b;
            g[a].push_back(b);
            g[b].push_back(a);
            
            int fa = find(a);
            int fb = find(b);
            
            if(fa == fb) // 两个点在同一条链上
            {
                cnt[fb] ++; // 此时相连环数加1
                st = a, ed = b; // 记录环的起点和终点为求顶点数做铺垫
            }
            else
            {
                f[fa] = fb; 
                cnt[fb] += cnt[fa]; // 更新章鱼图中的子图个数
            }
        }
        int ans = 0;
        for(int i = 1; i <= n; i ++)
        {
            if(f[i] == i && cnt[i] == 1) ans ++;
            // 只有一个环的的章鱼图
        }
        if(ans != 1) cout << "No" << " " << ans << endl;
        else cout << "Yes" << " " << bfs(st, ed) + 1 << endl;
    }
}

RC-u5

小 K 有 N 项工作等待完成，第 i 项工作需要花 ti​ 单位时间，必须在 di​ 时刻或之前完成，报酬为 pi​。假设小 K 工作时刻从 0 开始，且同一时刻只能做一项工作、工作一旦开始则不可中断或切换至其他工作，请你帮小 K 规划一下如何选择合适的工作，使小 K 可以获得最多的报酬。

输入格式:

输入第一行是一个正整数 T (≤5)，表示数据的组数。

接下来有 T 组数据，每组数据第一行是一个正整数 N (≤5000)，表示待完成工作的数量。接下来的 N 行，每行三个非负整数 ti​、di​、pi​ (均 ≤5000；1≤i≤N)，表示第 i 项工作需要花费的时间、截止时间以及报酬。

输出格式:

对于每组数据，输出小 K 能获得最多的报酬是多少。

输入样例:

3
5
1 2 50
3 3 100
1 5 1
3 2 5000
4 5 30
5
1 2 50
3 3 20
1 5 1
3 2 5000
4 5 30
5
1 2 50
3 3 100
1 5 1
3 2 5000
5 5 800

输出样例:

101
80
800

思路：

        这题是一个01背包＋贪心思路的问题，将所有工作首先按照截止时间排序，再按照花费时间，最后按照收入排序，这样可以保证是按照时间顺序算出每一个时间点可能得到的报酬。注：最大报酬不一定是在最大时间出得到的，所以得比较每个时间求出报酬的最大值。dp数组表示第j时刻处可以获得的最大报酬。状态转移方程为dp[j] = max(dp[j], dp[j - a[i].t] + a[i].p)。

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


const int N = 5e3 + 10;
typedef long long ll;

typedef struct Node
{
    int t, d, p;

    bool operator<(const Node &x) const
    {
        if(d != x.d) return d < x.d;
        else if(t != x.t) return t < x.t;
        else return p > x.p;
    }
    // 这里不清楚的可以看一下结构体排序
}A;

int main()
{
    int t;
    cin >> t;
    while(t --)
    {
        int n;
        cin >> n;
        A a[N];
        for(int i = 1; i <= n; i ++)
        {
            cin >> a[i].t >> a[i].d >> a[i].p;
        }
        ll dp[N];
        memset(dp, 0, sizeof dp);
        sort(a + 1, a + 1 + n);
        for(int i = 1; i <= n ; i ++)
        {
            for(int j = a[i].d; j >= a[i].t; j --)
            {
                dp[j] = max(dp[j], dp[j - a[i].t] + a[i].p);
            }
        }

        ll res = 0;
        for(int i = 0; i < N; i ++) res = max(res, dp[i]);
        cout << res << endl;
    }
}