2024 保研夏令营机试刷题记录

🤖AI Summary

2024年夏令营机试中，nova分享了她的经验和做题记录，她主要刷了2023的推免题和2019的上机题。

在处理题目时，她注重题目的做题量，保持速度，以适应不同难度题目。以下是一些她具体的题目和解决方式：

1. 2023 推免题：

   • 全在其中：此题采用双指针法，通过简单遍历判断一个字符串是否为另外一个字符串的子列。
   • 最接近的分数：解决此题，采用暴力扫描分子和分母并结合乘法防止除法精度的问题。
   • 踩方格：用 DFS 和 DP 方法分别尝试不同解法，通过回溯来计算所有不同的路径。
   • 核电站：使用了动态规划来解决不同的放置核物质方案数目的计算问题。

2. 2019 上机题：

   • 寻找特殊年号：通过存储特殊年号并使用二分查找快速确定答案。
   • 图片处理：直接通过遍历和平均相邻像素来模糊处理图片。
   • 括号生成：使用 DFS 方法生成所有合法括号组合，并按字典序输出。
   • 二叉树形态种类：通过卡特兰数来计算不同结点的二叉树形态数量。
   • 酒鬼问题：此题通过动态规划来计算最优的选择方案。
   • 最短路径：采用经典图算法，如 Dijkstra 解决有向图最短路径问题。

她在总结中提到，这一系列题目并不十分困难，可以通过多次练习提升熟练度和速度。此外，她还建议针对经典算法进行专门的练习，以确保在各种考试中保持良好的表现。

刷 leetcode 还是没什么意思，准备一天来一套真题（笑，不做特别难的题和特别麻烦的大模拟，确保做题速度。

会按照一个顺序选择刷题。

2023 研究生推免 （5/14）

全在其中

A:全在其中

总时间限制: 1000ms 内存限制: 65536kB 描述 你设计了一个新的加密技术，可以用一种聪明的方式在一个字符串的字符间插入随机的字符串从而对信息进行编码。由于专利问题，我们将不会详细讨论如何在原有信息中产生和插入字符串。不过，为了验证你的方法，有必要写一个程序来验证原来的信息是否全在最后的字符串之中。

给定两个字符串s和t，你需要判断s是否是t的“子列”。也就是说，如果你去掉t中的某些字符，剩下字符将连接而成为s。

输入 输入包括多个测试样例。每一个都是由空格分隔的由字母数字ASCII字符组成的两个特定的字符串s和t。s和t的长度不超过100000。

输出 对于每个测试样例，如果s是t的“子列”，则输出”Yes”，否则输出”No”

签到题。双指针扫一遍即可。

#include <iostream>
#include <string>

using namespace std;

int n;

bool isSub(string str, string sub) {
    int i = 0, l = 0;
    while (i < sub.size() && l < str.size()) {
        if (str[l] == sub[i]) i++, l++;
        else l++;
    }
    return i == sub.size();
}


int main() {
    string substr, str;
        
    while (cin >> substr >> str) {
        cout << (isSub(str, substr) ? "Yes" : "No" ) << endl;
    }
}

最接近的分数

B:最接近的分数 总时间限制: 1000ms 内存限制: 65536kB 描述

分母不超过 N 且 小于 A/B 的最大最简分数是多少？

输入

三个正整数N，A，B，相邻两个数之间用单个空格隔开。$1 \le A < B < N \le 1000$。

输出

两个正整数，分别是所求分数的分子和分母，中间用单个空格隔开。

从 1~N 扫一遍，选择分子和分母。因为 $N \le 1000$，所以 $O(n^2)$ 可以接受。

注意就是用乘法防止除法精度问题。最大 1000*1000，爆不了 int

#include <iostream>
using namespace std;

int n, a, b;


int main() {
    cin >> n >> a >> b;
    // 分母小于等于 n，小于 a / b
    int mxi = -1, mxj = -1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            // j/i
            if (j*b < a *i) {
                if (mxi == -1 || mxj == -1 || j * mxi > mxj * i) mxj = j, mxi = i;
            }
        }
    }
    cout << mxj << " " << mxi << endl;
}

踩方格

踩方格

总时间限制: 1000ms 内存限制: 65536kB 描述

有一个方格矩阵，矩阵边界在无穷远处。我们做如下假设： a. 每走一步时，只能从当前方格移动一格，走到某个相邻的方格上； b. 走过的格子立即塌陷无法再走第二次； c. 只能向北、东、西三个方向走；

请问：如果允许在方格矩阵上走n步，共有多少种不同的方案。2种走法只要有一步不一样，即被认为是不同的方案。

输入 允许在方格上行走的步数n(n \le 20)

输出 计算出的方案数量

一眼 DP 或者 dfs，用 DFS 写的回溯，最多运行 20 * 3 次。这里开了个 41 * 21 的数组，然后从 20 开始走，数组用于判断走没走过。

#include <iostream>

using namespace std;

int mat[42][21];
int res;
int n;

int dx[3] = {0, 1, 0};
int dy[3] = {-1, 0, 1};

void dfs(int x, int y, int u) {
    if (u == n) {
        res ++;
        return;
    }
    
    for (int i = 0; i < 3; i++) {
        int xx = x + dx[i];
        int yy = y + dy[i];

        if (mat[xx][yy]) continue;
        mat[xx][yy] = 1;
        dfs(xx, yy, u + 1);
        mat[xx][yy] = 0;
    }
}

int main() {
    cin >> n;
    mat[20][0] = 1;
    dfs(20, 0, 0);
    cout << res;
}

核电站

D:核电站

总时间限制: 5000ms 单个测试点时间限制: 1000ms 内存限制: 131072kB 描述 一个核电站有 N 个放核物质的坑，坑排列在一条直线上。如果连续 M 个坑中放入核物质，则会发生爆炸，于是，在某些坑中可能不放核物质。

任务：对于给定的 N 和 M ，求不发生爆炸的放置核物质的方案总数。

输入 只有一行，两个正整数 N，M (1 < N < 50, $2 \le M \le 5$)。

输出 一个正整数 S，表示方案总数。

2 \le M \le 5最卡的一题。一开始也用了一个 DFS，每个位置摆和不摆两种。写完发现是 $O(2^n)$ 的复杂度，寄！不过如果真遇到应该可以骗几个测例的分。

选择 DP，一开始写了一个二维 DP，但是一直没有想清楚转移方程。

$f\[i]\[j]$ 代表到 i 位置合法的个数，j 是二维的，代表第 i 位置放或者不放。对于 i < m 的情况，直接加就完事了；对于 i == m 的情况，减掉第一个位置放的一种情况；对于 i > m 的情况，这里一直没想清楚，后面突然理解了，我们要去掉的情况是明朗的：i-m+1 ~ i 共 m - 1 个位置都放，i-m 这个位置不放，而对于前面 i-m-1 个位置，我们怎么放都可以，因此不合法的个数是 1 * f[i-m-1] 个。

然后就是要注意爆 int 的问题，假设 m 不存在，那么我们就有 2^n 个方案，就算有 m 这个限制条件，也不会减特别多，所以用 long long 最保险。

/* O(2^n) */

void dfs(int x, int u, int p) {
    // u 当前已放置的个数
    // x 当前放置的位置
    // p 当前连续放置多少个
    if (p >= m) return;

    if (x == n) {
        res ++;
        return;
    }

    dfs(x + 1, u, 0);  // 不在这里放
    dfs(x + 1, u + 1, p + 1);  // 在这里放

    return;
}

long long f[55];

int main() {
    cin >> n >> m;

    // f[i][0/1] 代表在 i 位置放和不放的总数情况 (合法的)
    // f[n][0] + f[n][1]
    // f[i][0] = f[i-1][0] + f[i-1][1]
    // f[i][1] = f[i-1][0] + f[i-1][1] - 不合法方案
    
    // 对于 i == m 的情况，我们仅需减去一种方案，即全放的方案
    // 对于 i > m 的情况，我们需要减去的是这样一种方案：i-m+1~i 共 m - 1 个位置都放，i-m 没有放。但是 i - m - 1 前的方案是不确定的，因此乘法原理处理。


    f[0][0] = 1;
    for (int i = 1; i < m; i++) f[i][1] = f[i][0] = f[i-1][0] + f[i-1][1];
    for (int i = m; i <= n;) {
        f[i][0] = f[i-1][0] + f[i-1][1];
        f[i][1] = f[i-1][0] + f[i-1][1] - 1;
        break;
    }
    for (int i = m + 1; i <= n; i++) {
        f[i][0] = f[i-1][0] + f[i-1][1];
        f[i][1] = f[i-1][0] + f[i-1][1] - f[i-1-m][1] - f[i-1-m][0];
    }

    cout << f[n][0] + f[n][1];
}

之后，可以发现其实我们用一维合并一下更好。

long long f[55];

int main() {
    cin >> n >> m;	
	// 可以发现我们能够压缩一维
    // f[i][1] + f[i][0] = 2*(f[i-1][0] + f[i-1][1]) - 不合法方案

    f[0] = 1;
    for (int i = 1; i <= n; i++) {
        f[i] = 2 * f[i-1];
        if (i == m) f[i] -= 1;
        if (i > m) f[i] -= f[i-1-m];
    }

    cout << f[n];
    
}

Highways

G:Highways 总时间限制: 1000ms 内存限制: 65536kB 描述 The island nation of Flatopia is perfectly flat. Unfortunately, Flatopia has no public highways. So the traffic is difficult in Flatopia. The Flatopian government is aware of this problem. They're planning to build some highways so that it will be possible to drive between any pair of towns without leaving the highway system.

Flatopian towns are numbered from 1 to N. Each highway connects exactly two towns. All highways follow straight lines. All highways can be used in both directions. Highways can freely cross each other, but a driver can only switch between highways at a town that is located at the end of both highways.

The Flatopian government wants to minimize the length of the longest highway to be built. However, they want to guarantee that every town is highway-reachable from every other town.

输入 The first line of input is an integer T, which tells how many test cases followed. The first line of each case is an integer N ($3 \le N \le 500$), which is the number of villages. Then come N lines, the i-th of which contains N integers, and the j-th of these N integers is the distance (the distance should be an integer within [1, 65536]) between village i and village j. There is an empty line after each test case.

输出 For each test case, you should output a line contains an integer, which is the length of the longest road to be built such that all the villages are connected, and this value is minimum.

概括一下题意，就是说要建高速，从 1~n 个点之间两两建，输出可以修建的方案里最长高速最小的距离。其实翻译一下就是找最小生成树。这里也有贪心性质，可以证明下。假设现在有一颗最小生成树，它的边权值最大为 x，假设存在另一颗生成树，其边权值最大为 y，且满足 x > y，由于两两连通，那么一定通过这条权值边生成一个更小的生成树，矛盾，因此最小生成树的边权值最大即为题目所要求的。

理解之后就是 Prim 或者 KRUSKAL 的板子题了。注意读入的时候，它到自身的边权值为 0，改成无穷大就好。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int n;

void prim(vector<vector<int>>& mat) {
    vector<int> dist(mat.size(), 0x3f3f3f3f);
    vector<bool> st(mat.size(), false);

    dist[1] = 0;
    int res = INT_MIN;
    for (int i = 1; i < mat.size(); i++) {
        int v = -1;
        for (int j = 1; j < mat.size(); j++) if (!st[j] && (v == -1 || dist[j] < dist[v] )) v = j;

        st[v] = true;

        res = max(res, dist[v]);

        for (int j = 1; j < mat.size(); j++) {
            if (!st[j] && dist[j] > mat[v][j]) dist[j] = mat[v][j];
        }
    }

    cout << res << endl;
}

int main() {
    scanf("%d", &n);
    
    while (n--) {
        string tmp;
        getline(cin, tmp);
        int m;
        scanf("%d", &m);
        vector<vector<int>> mat(m + 1, vector<int>(m + 1));

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= m; j ++) {
                scanf("%d", &mat[i][j]);
                if (i == j) mat[i][j] = 0x3f3f3f3f;
            }
        }
        prim(mat);
    }
}

2023 研究生上机 （5/15）

寻找特殊年号

A:寻找特殊年号

查看提交统计提问

总时间限制: 1000ms 内存限制: 65535kB

描述

年号中的每个数之和为20的年号是特殊年号。例如：2099、1991、1892是特殊的年号，而2021则不是。给定一个年号，找出严格大于给定年号的最小特殊年号。

输入

年号：整数y(1000≤y≤9000)。

输出

特殊年号：严格意义上大于y的最小年号，并且它的每个数之和为20。

不知道有没有更聪明的做法，一开始是直接每个往上找，感觉会 TLE，就首先存了特殊的，然后二分去找第一个大于当前的。

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

vector<int> spe;

int getSum(int i) {
    int sum = 0;
    while (i) {
        sum += i % 10;
        i /= 10;
    }
    return sum;
}

void gen() {
    for (int i = 1000; i < 10000; i++) {
        if (getSum(i) == 20) spe.push_back(i);
    }
    sort(spe.begin(), spe.end());
}

int main() {
    gen();
    int n;
    while (cin >> n) {
        auto nxt = upper_bound(spe.begin(), spe.end(), n);
        cout << *nxt << endl;
    }
}

图像模糊处理

B:图像模糊处理

查看提交统计提问

总时间限制: 1000ms 内存限制: 65536kB

描述

给定n行m列的图像各像素点的灰度值，要求用如下方法对其进行模糊化处理：

1. 四周最外侧的像素点灰度值不变；
2. 中间各像素点新灰度值为该像素点及其上下左右相邻四个像素点原灰度值的平均（舍入到最接近的整数）。

输入

第一行包含两个整数n和m，表示图像包含像素点的行数和列数。1 ≤ n ≤ 100，1 ≤ m ≤ 100。

接下来n行，每行m个整数，表示图像的每个像素点灰度。相邻两个整数之间用单个空格隔开，每个元素均在0~255之间。

输出

n行，每行m个整数，为模糊处理后的图像。相邻两个整数之间用单个空格隔开。

没看懂，直接做就完了？

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


int n, m;
int mat[110][110];


int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &mat[i][j]);
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (i == 1 || i == n || j == 1 || j == m) {
                cout << mat[i][j];
                if (i == n && j == m) continue;
                if (j == m) cout << endl;
                else cout << " ";
                continue;
            }
            int sum = mat[i-1][j] + mat[i][j] + mat[i+1][j] + mat[i][j-1] + mat[i][j+1];
            cout << sum / 5 << " ";
        }
    }
}

括号生成

C:括号生成

查看提交统计提问

总时间限制: 1000ms 内存限制: 65536kB

描述

Paul是一名数学专业的同学，在课余选修了C++编程课，现在他能够自己写程序判断判断一个给定的由'('和')'组成的字符串是否是正确匹配的。可是他不满足于此，想反其道而行之，设计一个程序，能够生成所有合法的括号组合，请你帮助他解决这个问题。

输入

输入只有一行N，代表生成括号的对数（1 ≤ N ≤ 10)。

输出

输出所有可能的并且有效的括号组合，按照字典序进行排列，每个组合占一行。

dfs，让左括号数量大于右括号即可。

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

int n;
vector<char> res;

void dfs(int l, int r, int u) {
    if (l > n || r > n || r > l) return;
    if (u == 2*n) {
        for (auto i : res) {
            cout << i;
        }
        cout << endl;
        return;
    }

    res.push_back('(');
    dfs(l + 1, r, u + 1);
    res.pop_back();

    res.push_back(')');
    dfs(l, r + 1, u + 1);
    res.pop_back();
    
}

int main() {
    cin >> n;
    dfs(0, 0, 0);
}

有多少种二叉树

D:有多少种二叉树

查看提交统计提问

总时间限制: 1000ms 内存限制: 65536kB

描述

输入n(1<n<13)，求n个结点的二叉树有多少种形态

输入

整数n

输出

答案

卡特兰数

#include <iostream>
using namespace std;

int n;

long long C(int n, int m) {
    long long res = 1, p = 1;
    for (int i = n, j = 1; j <= m; i--, j++) {
        res *= i;
        p *= j;
    }

    return res / p;
}

int main() {
    cin >> n;
    cout <<  C(2*n, n) / (n + 1) << endl;
}

酒鬼

E:酒鬼

查看提交统计提问

总时间限制: 2000ms 单个测试点时间限制: 1000ms 内存限制: 131072kB

描述

Santo 刚刚与房东打赌赢得了一间在 New Clondike 的大客厅。今天，他来到这个大客厅欣赏他的奖品。房东在酒吧上摆了一排瓶子，瓶子里都装有不同体积的酒。令 Santo 高兴的是，瓶子中的酒都有不同的味道。房东说道：“你可以喝尽可能多的酒，但是一旦打开酒盖你就必须把它喝完，喝完一瓶后把它放回原处。还有一件最重要的事，你必须从左至右依次喝，但不能连续三瓶或以上，不然会给你带来坏运气。” 现在可怜的 Santo 站在酒吧前努力地想着，他到底应该喝哪几瓶才能使喝的酒最多呢？请帮助他找出他应该喝的酒瓶号，因为思考让他感到不安。

输入

第一行一个整数 N (1≤N≤700) 表示有 N 个酒瓶。接下有 N 行，第 i+1 行的整数 Ai (1≤Ai≤10000) 代表酒瓶 i 中酒的体积。

输出

一个整数，表示 Santo 能喝的酒的最大总体积。遵守以上规则，使得任意连续三个瓶子中至少一个瓶子是满的。

一个动态规划，当时写了注释了就不说了。

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

int n;
int s[710];
int f[710];

int main() {
    // f[i] 代表喝的体积的集合
    // max
    // f[i] 满足最多喝连续两瓶，因此对于 f[i+1]，我们不能喝，才能确保合法。
    // f[i] 仅与包含 i 的前三个有关即可处理。
    // f[i] = f[i-3] + 连续喝 i-1 和 i
    //      = f[i-2] + 只喝 i
    //      = f[i-1] + 不喝
    cin >> n;
    for (int i = 1; i <= n; i++) scanf("%d", &s[i]);
    f[0] = 0;
    for (int i = 1; i <= n; i++) {
        if (i <= 2) f[i] = f[i-1] + s[i];
        f[i] = max({f[i-3] + s[i-1] + s[i], f[i-2] + s[i], f[i-1]});
    }
    cout << f[n] << endl;
}

最短路

F:最短路

查看提交统计提问

总时间限制: 2000ms 内存限制: 65536kB

描述

给定一个n个点, m条边的有向图, 求从点S出发, 到其它所有点的最短路径.

输入

第一行一个整数T, 表示有T组数据

对于每组测试数据, 第一行三个整数n, m, S, 表示有n个点, m条边, 起点为S.

接下来m行, 每行三个整数x, y, z, 代表从x到y有长度为z的边

点的编号从1到n

T ≤ 10, n ≤ 10000, m ≤ 20000, |z| ≤ 10000. 所有数据的n之和 ≤ 30000, 所有数据的m之和 ≤ 60000.

输出

对于每组数据:

如果从S点出发可以走入负圈 (即到某些点的最短路径可以无限小), 那么输出一行Error.

否则, 输出一行用空格分隔的n个整数, 其中第i个整数表示从S点到i点的最短路长度. 如果从S点无法到达i点, 则第i个输出为”null”.

模板题，有负权回路，走 spfa 就好

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
typedef pair<int, int> PII;

const int N = 2e4 + 10;

int e[N], ne[N], w[N], h[N];
int idx;
int T, n, m, S;

void add(int a, int b, int weight) {
    e[++idx] = b;
    ne[idx] = h[a];
    h[a] = idx;
    w[idx] = weight;
}

void spfa(int S) {
    queue<PII> q;
    vector<int> dist(N, 0x3f3f3f3f), cnt(N, 0);
    vector<bool> st(N, false);
    q.push({0, S});  // dist, node;
    dist[S] = 0;
    while(q.size()) {
        auto &[d, nn] = q.front();
        q.pop();
        
        st[nn] = false;
        for (int i = h[nn]; i; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[nn] + w[i]) {
                dist[j] = dist[nn] + w[i];
                cnt[j] = cnt[nn] + 1;
                if (cnt[j] >= n) {
                    cout << "Error" << endl;
                    return;
                }
                if (!st[j]) {
                    st[j] = true;
                    q.push({dist[j], j});
                }
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (dist[i] > 0x3f3f3f3f / 2) cout << "null";
        else cout << dist[i];
        cout << " ";
    }
    cout << endl;
}

int main() {
    cin >> T;
    while (T--) {
        memset(e, 0, sizeof e);
        memset(ne, 0, sizeof ne);
        memset(w, 0, sizeof w);
        memset(h, 0, sizeof h);
        idx = 0;
        cin >> n >> m >> S;

        for (int i = 0; i < m; i++) {
            int a, b, c;
            cin >> a >> b >> c;
            add(a, b, c);
        }
        spfa(S);
    }
}

摆放玩具

G:玩具摆放

查看提交统计提问

总时间限制: 10000ms 单个测试点时间限制: 1000ms 内存限制: 524288kB

描述

在一个4*4的方框内摆放了若干个相同的玩具。

某人想通过移动玩具，将这些玩具重新摆放成为他心中理想的状态。要求每次移动时，只能将某一个玩具向上下左右四个方向之一移动一步。不能将玩具移出方框，并且移动的目标位置不能已经放置有玩具。

请你用最少的移动次数将初始的玩具状态移动到他心中的目标状态。

输入

前4行表示玩具的初始状态，每行4个数字1或0，1表示方格中放置了玩具，0表示没有放置玩具。

接着是一个空行。接下来4行表示玩具的目标状态，每行4个数字1或0，意义同上。

输出

一个整数，所需要的最少移动次数。保证初始状态可以达到目标状态。

提示

可以考虑将玩具局面表示为一个16 bit的整数，设置一个标志数组用来判重，用这个整数做下标找其对应标志位

根据提示，用 BFS 来做，一个 set 用于存。

位运算稍微处理了一下

#include <iostream>
#include <unordered_set>
#include <vector>
#include <queue>
#include <string>

using namespace std;

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

void bfs(int raw, int res) {
    unordered_set<int> set;
    queue<pair<int, int>> q;
    set.insert(raw);
    q.push({raw, 0});
    while (!q.empty()) {
        auto &[now, cnt] = q.front();
        q.pop();

        if (now == res) {
            cout << cnt << endl;
            return;
        }

        for (int i = 15; i >= 0; i--) {
            if ((now >> i) & 1) {
                int x = (15-i) % 4;
                int y = (15-i) / 4;
                
                for (int k = 0; k < 4; k++) {
                    int xx = x + dx[k];
                    int yy = y + dy[k];
                    
                    if (xx < 0 || xx > 3 || yy < 0 || yy > 3) continue;
                    int l = 15 - 4*yy - xx;
                    if ((now >> l) & 1) continue;
                    int nxt = (now ^ (1 << i)) | (1 << l);
                    if (set.count(nxt)) continue;
                    set.insert(nxt);
                    q.push({nxt, cnt + 1});
                }
            }
        }
    }
}

int main() {
    int raw = 0;
    int res = 0;
    for (int i = 0; i < 4; i++) {
        string tmp;
        cin >> tmp;
        for (auto c : tmp) {
            raw <<= 1;
            raw |= c-'0';
        }
    }
    for (int i = 0; i < 4; i++) {
        string tmp;
        cin >> tmp;
        for (auto c : tmp) {
            res <<= 1;
            res |= c-'0';
        }
    }
    bfs(raw, res);
}

2019 研究生推免（5/16）

感觉这次很简单。

有趣的跳跃

A:有趣的跳跃

查看提交统计提问

总时间限制: 1000ms 内存限制: 65536kB

描述

一个长度为n（n>0）的序列中存在“有趣的跳跃”当前仅当相邻元素的差的绝对值经过排序后正好是从1到(n-1)。例如，1 4 2 3存在“有趣的跳跃”，因为差的绝对值分别为3,2,1。当然，任何只包含单个元素的序列一定存在“有趣的跳跃”。你需要写一个程序判定给定序列是否存在“有趣的跳跃”。

输入

一行，第一个数是n（0 < n < 3000），为序列长度，接下来有n个整数，依次为序列中各元素，各元素的绝对值均不超过1,000,000,000。

输出

一行，若该序列存在“有趣的跳跃”，输出"Jolly"，否则输出"Not jolly"。

签到题，直接判断就完事了。

#include <iostream>
#include <cmath>

using namespace std;


int n;

int main() {
    cin >> n;
    int pre = -1;
    int tmp;
    cin >> tmp;
    while (n-- > 1) {
        int tmp2;
        cin >> tmp2;
        if (pre >= 0 && abs(tmp2-tmp) != pre - 1) { cout << "Not jolly" << endl; return 0; }
        pre = abs(tmp2-tmp);
        tmp = tmp2;
    }
    cout << "Jolly" << endl;
    return 0;

玛雅历

B:玛雅历

查看提交统计提问

总时间限制: 1000ms 内存限制: 65536kB

描述

上周末，M.A. Ya教授对古老的玛雅有了一个重大发现。从一个古老的节绳（玛雅人用于记事的工具）中，教授发现玛雅人使用了一个一年有365天的叫做Haab的历法。这个Haab历法拥有19个月，在开始的18个月，一个月有20天，月份的名字分别是pop, no, zip, zotz, tzec, xul, yoxkin, mol, chen, yax, zac, ceh, mac, kankin, muan, pax, koyab, cumhu。这些月份中的日期用0到19表示。Haab历的最后一个月叫做uayet，它只有5天，用0到4表示。玛雅人认为这个日期最少的月份是不吉利的，在这个月法庭不开庭，人们不从事交易，甚至没有人打扫屋中的地板。

因为宗教的原因，玛雅人还使用了另一个历法，在这个历法中年被称为Tzolkin(holly年)，一年被分成13个不同的时期，每个时期有20天，每一天用一个数字和一个单词相组合的形式来表示。使用的数字是1~13，使用的单词共有20个，它们分别是：imix, ik, akbal, kan, chicchan, cimi, manik, lamat, muluk, ok, chuen, eb, ben, ix, mem, cib, caban, eznab, canac, ahau。注意：年中的每一天都有着明确唯一的描述，比如，在一年的开始，日期如下描述： 1 imix, 2 ik, 3 akbal, 4 kan, 5 chicchan, 6 cimi, 7 manik, 8 lamat, 9 muluk, 10 ok, 11 chuen, 12 eb, 13 ben, 1 ix, 2 mem, 3 cib, 4 caban, 5 eznab, 6 canac, 7 ahau, ，8 imix, 9 ik, 10 akbal ……也就是说数字和单词各自独立循环使用。

Haab历和Tzolkin历中的年都用数字0，1，……表示，数字0表示世界的开始。所以第一天被表示成：

Haab: 0. pop 0

Tzolkin: 1 imix 0

请帮助M.A. Ya教授写一个程序可以把Haab历转化成Tzolkin历。

输入

Haab历中的数据由如下的方式表示：

日期. 月份 年数

输入中的第一行表示要转化的Haab历日期的数据量。下面的每一行表示一个日期，年数小于5000。

输出

Tzolkin历中的数据由如下的方式表示：

天数字 天名称 年数

第一行表示输出的日期数量。下面的每一行表示一个输入数据中对应的Tzolkin历中的日期。

一个简单的模拟。计算出总天数，然后转换就好。

#include <iostream>
#include <string>
#include <unordered_map>
#include <sstream>

using namespace std;

unordered_map<string, int> Haab = {
    {"pop", 0}, 
    {"no", 1}, 
    {"zip", 2}, 
    {"zotz", 3}, 
    {"tzec", 4}, 
    {"xul", 5}, 
    {"yoxkin", 6}, 
    {"mol", 7}, 
    {"chen", 8},
    {"yax", 9}, 
    {"zac", 10},
    {"ceh", 11}, 
    {"mac", 12}, 
    {"kankin", 13}, 
    {"muan", 14}, 
    {"pax", 15}, 
    {"koyab", 16}, 
    {"cumhu", 17}, 
    {"uayet", 18}
};

unordered_map<int, string> Tzolkin = {
    {0, "imix"}, 
    {1, "ik"}, 
    {2, "akbal"}, 
    {3, "kan"}, 
    {4, "chicchan"}, 
    {5, "cimi"}, 
    {6, "manik"}, 
    {7, "lamat"}, 
    {8, "muluk"}, 
    {9, "ok"}, 
    {10, "chuen"}, 
    {11, "eb"}, 
    {12, "ben"}, 
    {13, "ix"}, 
    {14, "mem"}, 
    {15, "cib"}, 
    {16, "caban"}, 
    {17, "eznab"}, 
    {18, "canac"}, 
    {19, "ahau"}
};

int n;

int haab_to_day(string tmp) {
    stringstream ss(tmp);
    int day, year;
    string month;
    ss >> day;
    ss.ignore();
    ss >> month;
    ss >> year;
    return year * 365 + Haab[month] * 20 + day;
}

void day_to_tzolkin(int day) {
    int year = day / 260;
    int day_in_year = day % 260;
    
    int day_num = day_in_year % 13 + 1;
    string day_string = Tzolkin[day_in_year % 20];

    cout << day_num << " " << day_string << " " << year << endl;

}

int main() {
    cin >> n;
    // cin.ignore();
    string tmp;
    getline(cin, tmp);
    cout << n << endl;
    while (n--) {
        getline(cin, tmp);
        int day = haab_to_day(tmp);
        day_to_tzolkin(day);
    }
}

走迷宫

C:走迷宫

查看提交统计提问

总时间限制: 1000ms 内存限制: 65536kB

描述

一个迷宫由R行C列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走。

给定一个迷宫，求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走，不能斜着走。

输入

第一行是两个整数，Ｒ和Ｃ，代表迷宫的长和宽。（ 1≤ R，C ≤ 40)

接下来是Ｒ行，每行Ｃ个字符，代表整个迷宫。

空地格子用'.'表示，有障碍物的格子用'#'表示。

迷宫左上角和右下角都是'.'。

输出

输出从左上角走到右下角至少要经过多少步（即至少要经过多少个空地格子）。计算步数要包括起点和终点。

BFS 模板题感觉是。

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


int R, C;
int mat[41][41];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};

void bfs() {
    queue<vector<int>> q;
    q.push({1, 1, 1});
    while (!q.empty()) {
        auto t = q.front();
        int x = t[0], y = t[1], c = t[2];
        q.pop();

        if (x == R && y == C) { cout << c << endl; return; }
        mat[x][y] = 2;
        
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (xx <= 0 || xx > R || yy <= 0 || yy > C) continue;
            if (!mat[xx][yy]) q.push({xx, yy, c+1});
        }
    }
}

int main() {
    cin >> R >> C;
    char ch;
    for (int i = 1; i <= R; i++) {
        scanf("\r\n");
        for (int j = 1; j <= C; j++) {
            scanf("%c", &ch);
            mat[i][j] = ch == '#';
        }
    }
    bfs();
}

最大上升子序列和

D:最大上升子序列和

查看提交统计提问

总时间限制: 1000ms 内存限制: 65536kB

描述

一个数的序列bi，当b1 < b2 < ... < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, ...,aN)，我们可以得到一些上升的子序列(ai1, ai2, ..., aiK)，这里1 ≤ i1 < i2 < ... < iK ≤ N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中序列和最大为18，为子序列(1, 3, 5, 9)的和.

你的任务，就是对于给定的序列，求出最大上升子序列和。注意，最长的上升子序列的和不一定是最大的，比如序列(100, 1, 2, 3)的最大上升子序列和为100，而最长上升子序列为(1, 2, 3)

输入

输入的第一行是序列的长度N (1 ≤ N ≤ 1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000（可能重复）。

输出

最大上升子序列和

第一时间想成了最大上升子序列，不过二者答案是有区别的，转义方程倒是大同小异。

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

int n;
int s[1010];
int f[1010];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) scanf("%d", &s[i]);

    // f[i] 代表子序列和
    // maxx
    // f[i] = max(f[i-k] + (a[i-k] < a[i] ? a[i] : 0))

    int res = -0x3f3f3f3f;
    for (int i = 1; i <= n; i++) f[i] = s[i];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <i; j++) {
            if (s[i-j] < s[i]) f[i] = max(f[i], f[i-j] + s[i]);
        }
        res = max(res, f[i]);
    }
    cout << res << endl;
    return 0;
}

Yogurt Factory

E:Yogurt factory

查看提交统计提问

总时间限制: 1000ms 内存限制: 65536kB

描述

The cows have purchased a yogurt factory that makes world-famous Yucky Yogurt. Over the next N (1 ≤ N ≤ 10,000) weeks, the price of milk and labor will fluctuate weekly such that it will cost the company C_i (1 ≤ C_i ≤ 5,000) cents to produce one unit of yogurt in week i. Yucky's factory, being well-designed, can produce arbitrarily many units of yogurt each week.

Yucky Yogurt owns a warehouse that can store unused yogurt at a constant fee of S (1 ≤ S ≤ 100) cents per unit of yogurt per week. Fortuitously, yogurt does not spoil. Yucky Yogurt's warehouse is enormous, so it can hold arbitrarily many units of yogurt.

Yucky wants to find a way to make weekly deliveries of Y_i (0 ≤ Y_i ≤ 10,000) units of yogurt to its clientele (Y_i is the delivery quantity in week i). Help Yucky minimize its costs over the entire N-week period. Yogurt produced in week i, as well as any yogurt already in storage, can be used to meet Yucky's demand for that week.

输入

* Line 1: Two space-separated integers, N and S.

* Lines 2..N+1: Line i+1 contains two space-separated integers: C_i and Y_i.

输出

* Line 1: Line 1 contains a single integer: the minimum total cost to satisfy the yogurt schedule. Note that the total might be too large for a 32-bit integer.

看这个数据范围就觉得是贪心，但是居然没有想出来怎么贪心... 在那考虑 A 买几个 B 买几个（这还算贪心吗）。后面遭不住了去看了一眼，算最低单价不就完事了。。。我是傻逼。

注意数据范围爆 int

#include <iostream>
#include <vector>

using namespace std;

int N, S;
long long res;

int main() {
    cin >> N >> S;
    
    long long res = 0;
    vector<int> prices(N, 0), want(N, 0);
    for (int i = 0; i < N; i++) {
        cin >> prices[i] >> want[i];
    }
    
    for (int i = 0; i < N; i++) {
        int minCost = prices[i];
        for (int j = 1; j <= i; j++) minCost = min(prices[i-j] + S*j, minCost);
        res += minCost * want[i];
    }

    cout << res << endl;
    return 0;
}

Wireless Network

F:Wireless Network

查看提交统计提问

总时间限制: 10000ms 内存限制: 65536kB

描述

An earthquake takes place in Southeast Asia. The ACM (Asia Cooperated Medical team) have set up a wireless network with the lap computers, but an unexpected aftershock attacked, all computers in the network were all broken. The computers are repaired one by one, and the network gradually began to work again. Because of the hardware restricts, each computer can only directly communicate with the computers that are not farther than d meters from it. But every computer can be regarded as the intermediary of the communication between two other computers, that is to say computer A and computer B can communicate if computer A and computer B can communicate directly or there is a computer C that can communicate with both A and B.

In the process of repairing the network, workers can take two kinds of operations at every moment, repairing a computer, or testing if two computers can communicate. Your job is to answer all the testing operations.

输入

The first line contains two integers N and d (1 ≤ N ≤ 1001, 0 ≤ d ≤ 20000). Here N is the number of computers, which are numbered from 1 to N, and D is the maximum distance two computers can communicate directly. In the next N lines, each contains two integers xi, yi (0 ≤ xi, yi ≤ 10000), which is the coordinate of N computers. From the (N+1)-th line to the end of input, there are operations, which are carried out one by one. Each line contains an operation in one of following two formats:

1. "O p" (1 ≤ p ≤ N), which means repairing computer p.
2. "S p q" (1 ≤ p, q ≤ N), which means testing whether computer p and q can communicate.

The input will not exceed 300000 lines.

输出

For each Testing operation, print "SUCCESS" if the two computers can communicate, or "FAIL" if not.

这题很简单，图随便一下建模出来，但是一时间居然没想到用并查集来做，准备自己写链表了甚至。

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

int find(vector<int>& p, int u) {
    if (p[u] != u) p[u] = find(p, p[u]);
    return p[u];
}

int main() {
    int n, d;
    cin >> n >> d;
    vector<vector<int>> mat(n + 1, vector<int>(2));
    vector<int> p(n+1);
    unordered_set<int> fixed;
    for (int i = 1; i <= n; i++) p[i] = i;
    for (int i = 1; i <= n; i++) {
        cin >> mat[i][0] >> mat[i][1];
    }

    char ch;
    while (cin >> ch) {
        int a, b;
        if (ch == 'O') {
            cin >> a;
            if (fixed.count(a)) continue;

            for (auto b: fixed) {
                int x = abs(mat[a][0] - mat[b][0]);
                int y = abs(mat[a][1] - mat[b][1]);
                int dst = x*x + y*y;
                if (dst <= d*d) {
                    p[find(p, b)] = find(p, a);
                }
            }
            

            fixed.insert(a);
        }
        else if (ch == 'S') {
            cin >> a >> b;
            if (find(p, a) == find(p, b)) {
                cout << "SUCCESS" << endl;
            }
            else {
                cout << "FAIL" << endl;
            }
        }
    }
}

—— Summary

这次题非常简单，可以看到通过率都是 75%+。遇到这种题感觉还是得刷速度和熟练度。第七题是 KRUSKAL，由于 Yogurt Factory 浪费了一些时间，再加上下课了，所以没写，摆了。

后面要专门的练一练这些经典算法。

2019 夏令营上机（5/20）

17、18、19 在做 PPT，没时间看题

A:数与字符串

A:数与字符串 查看提交统计提问 总时间限制: 1000ms 内存限制: 65536kB 描述 定义一个字符串序列 s[1]="1",s[2]="2", ..., s[n] = 数字 n 转化成字符串后的结果

输出 s[1] 到 s[n] 中，（字典序）最大的那个字符串

输入 输入包含多组数据。

每组数据输入一行一个整数 n(n≤1e6)。

输入以 n=0 结束。 输出 对于每组数据，输出一行一个整数表示答案

主要考虑字典序的问题：先判断每一位，再判断长度。 99 > 100，因为 9 和 1 比的时候就 return true 了

对于一个数，如果它位数有 n 位，前 n-1 位不为 9 的话，字典序都小于 999...9 (n-1 个 9)

如果前 n-1 位为 9 的话，那么它的字典序最大的就是它本身。

因此，判断一个数的位数 n，然后判断它是不是位于 $[10^n- 10, 10^n)$ 里。

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

int main() {
    while (true) {
        cin >> n;
        if (!n) return 0;
        int tmp = n;
        int bit = 0;
        while (tmp) {
            tmp /= 10;
            bit ++;
        }
        if (n >= pow(10, bit) - 10 && n < pow(10, bit)) cout << n;
        else for (int i = 0; i < bit - 1; i++) cout << "9";
        cout << endl;
    }
}

B:打印月历

B:打印月历

查看提交统计提问

总时间限制: 1000ms 内存限制: 65536kB

描述

给定年月，打印当月的月历表。

输入

输入为一行两个整数，第一个整数是年份year（1900 ≤ year ≤ 2099），第二个整数是月份month（1 ≤ month ≤ 12），中间用单个空格隔开。

输出

输出为月历表。月历表第一行为星期表头，如下所示：

Sun Mon Tue Wed Thu Fri Sat

其余各行一次是当月各天的日期，从1日开始到31日（30日或28日）。

日期数字应于星期表头右对齐，即各位数与星期表头相应缩写的最后一个字母对齐。日期中间用空格分隔出空白。

样例输入

2006 5

样例输出

Sun Mon Tue Wed Thu Fri Sat

​ 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

提示

闰年判断方法：能被4整除但不能被100整除，或者能被400整除。

1900年1月1日是周一。

模拟，挺麻烦。

思路就是获取当月第一天是星期几，然后把星期对齐就好。

星期几判断，先算出经过了多少天，然后余 7 算出它和

#include <iostream>
using namespace std;

int year, month;

int getDay(int year, int month) {
    long long days = 0;
    for (int i = 1990; i < year; i++) {
        if (i % 400 == 0 || (i % 4 == 0 && i % 100 != 0)) days += 366;
        else days += 365;
    }
    for (int i = 1; i < month; i++) {
        if (i == 1 || i == 3 || i == 5 || i == 7 || i == 8 || i == 10 || i == 12) days += 31;
        else if (i == 2) {
            if (year % 400 == 0 || (year % 4 == 0 && year % 100 != 0)) days += 29;
            else days += 28;
        }
        else days += 30;
    }
    return (days + 1) % 7;
}

int main() {
    cout << "Sun Mon Tue Wed Thu Fri Sat" << endl;
    cin >> year >> month;

    int day = getDay(year, month);
    for (int i = 0; i < day; i++)
        cout << "    ";

    int thisMonth = 0;
    if (month == 1 || month == 3 || month == 5 || month == 7 || month == 8 || month == 10 || month == 12) thisMonth = 31;
    else if (month == 2) {
        if (year % 400 == 0 || (year % 4 == 0 && year % 100 != 0)) thisMonth = 29;
        else thisMonth = 28;
    }
    else thisMonth = 30;

    for (int i = 1; i <= thisMonth; i++) {
        if (i >= 10) cout << " ";
        else cout << "  ";
        cout << i;
        if ((day + i) % 7 == 0) cout << endl;
        else cout << " ";
    }
    return 0;
}

C:Hopscotch

C:Hopscotch

总时间限制:

1000ms

内存限制:

65536kB

描述

Hopscotch(跳房子) is a popular game. The rule is very simple: we draw some houses on the ground and then throw a stone. Based on the position of the stone, we decide which house to jump to. Here, we use consecutive positive integer coordinates on the x-axis to represent the houses,the coordinate of the ith house is i. We also assume that there are infinite number of houses.Then, we define the new rules as follows, each time we throw a stone,

if the stone falls into a house (marked as H), we can jump from the current house i to the house 3*i;

if the stone falls outside the house (marked as O), we can jump from the current house i to house i/2.(round down).

For example, initially at house 1, and in order to go to house 6, we can throw the stones in two ways：HHHOO or HHOHO.Now,your task is to compute the least number of jumps (k) needed to jump from a source house (n) and a destination house (m). You should also output the corresponding way of throwing the stones. If there are multiple ways, please output the smallest way in alphabet order.

输入

There are multiple test cases. For each test case, there are two integers n and m (1≤n, m≤1000), representing the source house and destination house. The input ends with 0 0.

输出

For each test case, the first line of output is an integer, which is the minimal number of jumps (k). The testing data guarantees that there is a solution and k ≤ 25. The second line outputs the corresponding way of throwing the stone.

做这题的时候百炼维护了，网上搜题干不小心看到思路了。。。

一开始没觉得能用 BFS，但是后面想一想，用 BFS 能保证答案最小，所以其实是正解。一开始认为时间复杂度很高，因为最多 2^25 个状态，但是仔细一想，因为 n 和 m 有限制，再加上 k 的限制，其实状态完全没有这么多。如果再判断一下当前位置有没有处理过就好很多了。我这里因为做题用了 2h 了就没有再加优化（其实也没有，搜题干用了一点时间）。

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

int m, n;

typedef struct State {
    int pos;
    int steps;
    string path;
} State;

int main() {
    while (cin >> n >> m) {
        if (n == 0 && m == 0) return 0;
        queue<State> q;
        string bsts;

        q.push({n, 0, ""});
        unordered_set<int> visited;
        while (q.size() && bsts.empty()) {
            State now = q.front(); q.pop();
            int pos = now.pos;
            int steps = now.steps;
            string path = now.path;
            
            if (visited.count(pos)) continue;
            
            int new_pos = 3 * pos;
            if (new_pos == m) {
                path += "H";
                if (bsts < path) bsts = path;
            }
            else q.push({new_pos, steps + 1, path + "H"});

            new_pos = pos / 2;
            if (new_pos == m) {
                path += "O";
                if (bsts < path) bsts = path;
            }
            else q.push({new_pos, steps + 1, path + "O"});
        }

        cout << bsts.size() << endl << bsts << endl;
    }
}

D:上楼梯

D:上楼梯 查看提交统计提问 总时间限制: 1000ms 内存限制: 128kB 描述 小S在玩一个叫上楼梯的游戏。楼梯一共有n层台阶。

因为腿长的限制，小S每次最多只能上k层台阶。

小S是一个迷信的人，所以他不希望自己某一步走的步数的数字里有"4"，（比如4，14，44都含有数字"4"）。

现在，小S想要知道，有多少种走完这n层台阶的方案？

输入 输入包含多组数据。

每组数据第一行输入一个整数 n, k(1 ≤k ≤ n ≤ 50)。

输入以 n,k=0 结束。 输出 对于每组数据，输出一行一个整数，表示答案。

简单 DP。这里不知道有没有的用了个记忆化搜索，因为它会有多组数据。

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

int n, k;
unordered_map<int, bool> h4;

bool check4(int num) {
    if (h4.count(num)) return h4[num];
    int old = num;
    while (num) {
        if (num % 10 == 4) { h4[old] = true; return true; }
        num /= 10;
    }
    h4[old] = false;
    return false;
}

int main() {
    // f[i] 代表方案总数
    while (true) {
        cin >> n >> k;
        if (n == 0 && k == 0) return 0;
        vector<long long>f(n + 1, 0);
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                if (check4(j) || i-j < 0) continue;
                f[i] += f[i-j];
            }
        }
        cout << f[n] << endl;
    }
    return 0;
}

F:跳蛙

F:跳蛙 查看提交统计提问 总时间限制: 1000ms 内存限制: 65536kB 描述 在一个 1*n 的棋盘上生活着若干只青蛙：有恰好一只青蛙王和若干只（可能没有）普通青蛙。我们用 A 表示青蛙王，B 表示普通青蛙，. 表示空地。

有一天，青蛙王醒来的时候发现它处在棋盘的最左侧，它想要跳到棋盘的最右侧。它可以指挥青蛙们来行动。每一时刻可以选择下列操作中的一个进行操作：

1. 对于青蛙王，如果它右侧相邻的格子是普通青蛙，且它右侧有空地的话，它可以跳到右侧第一个空地。

2. 对于青蛙王，如果它左侧相邻的格子是普通青蛙，且它的左侧有空地的话，它可以跳到左侧第一个空地。

3. 对于普通青蛙，如果它右侧相邻的格子是空地，它可以移动到这个空地。

4. 对于普通青蛙，如果它左侧相邻的格子是空地，它可以移动到这个空地。

在移动的过程中，任意两只青蛙都不能同时移动，且任意一只青蛙不能移动出棋盘。

现在给出初始时每一只青蛙的位置，问青蛙王能否到达棋盘的最右侧。

输入 输入包含多组数据。

每组数据第一行是一个整数 n(2≤n ≤ 10) 表示棋盘的大小。

第二行是一个长度为 n 的字符串从左到右表示棋盘的状态。保证第一个字符是 A，字符串只可能包含 AB. 三种字符，且恰好包含一个 A。

输入以 n=0 结束。 输出 对于每组数据，如果青蛙王能到达最右边，则输出 Y，否则输出 N。

按理来说应该是右边只要有两只及以上青蛙，再加上有一个空地就可以了，特判一下三就好了。

因为它可以使得青蛙王位于任意位置。

但是懒得证明，这个数据量也不是很多，就用 DFS 写就好。

好吧，我来证明了。

我们确保青蛙数量 >= 2。

在 n >= 4 的情况下，如果只有一个空地，那么可以直接到达，得证。

如果有两个及以上空地（也就是 n >= 5），因为一开始的时候 A 在最左边，我们 B-2 个青蛙放置在 A 的右边，然后放置一个空格，再放置剩下两只青蛙，进行一次跳跃，我们便可以把多于两个的 B 全部放在 A 的左边，使得右边成为 ABB__..._ 的形式。

此时，进行转移 ABB__->AB_B_->_BAB_->_B_BA->__BBA->_ABB_，我们可以将序列窗口向后移动一格，从而组成新的 ABB__ 序列，直到最终 _ABB_ 窗口已无法向后移动，进行一次跳跃，即可到达 __BBA 结尾状态。

这里一开始理解错了题目，以为相邻的青蛙只能是一只，发现第一个样例错的。于是又重新改成找到连续的最后一支青蛙了。

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;
unordered_set<string> h;
int n;

bool dfs(string& s, int u, int n) {
    if (s[n-1] == 'A') {
        return true;
    }

    if (h.count(s)) return false;

    // cout << "Available: " << s << endl;
    h.insert(s);

    for (int i = 0; i < n; i++) {
        if (s[i] == 'A') {
            int idx = i + 1;
            while (idx < n && s[idx] == 'B') {
                idx ++;
            }
            if (idx != i + 1 && idx < n && s[idx] == '.') {
                swap(s[i], s[idx]);
                if (dfs(s, idx, n)) return true;
                swap(s[i], s[idx]);
            }

            idx = i - 1;
            while (idx >= 0 && s[idx] == 'B') {
                idx --;
            }
            if (idx != i - 1 && idx >= 0 && s[idx] == '.') {
                swap(s[i], s[idx]);
                if (dfs(s, idx, n)) return true;
                swap(s[i], s[idx]);
            }
        }
        else if (s[i] == 'B') {
            if (i + 1 < n && s[i + 1] == '.') {
                swap(s[i], s[i+1]);
                if (dfs(s, i, n)) return true;
                swap(s[i], s[i+1]);
            }
            if (i - 1 >= 0 && s[i - 1] == '.') {
                swap(s[i], s[i-1]);
                if (dfs(s, i, n)) return true;
                swap(s[i], s[i-1]);
            }
        }
    }
    return false;

}


int main() {
    while (true) {
        h.clear();
        cin >> n;
        if (!n) return 0;
        string s;
        cin >> s;
        if (dfs(s, 0, n)) cout << "Y" << endl;
        else cout << "N" << endl;
    }
}

G:Falling Leaves

G:Falling Leaves

总时间限制:

1000ms

内存限制:

65536kB

描述

A tree like the one in Figure 1 is also a binary search tree of letters. A binary search tree of letters is a binary tree of letters in which each node satisfies: The root’s data comes later in the alphabet than all the data in the nodes in the left subtree. The root’s data comes earlier in the alphabet than all the data in the nodes in the right subtree.

The problem: Consider the following sequence of operations on a binary search tree of letters: Remove the leaves and list the data; removed; Repeat this procedure until the tree is empty

Starting from the tree below on the left, we produce the sequence of trees shown, and then the empty tree by removing the leaves with data

BDHPY

CM

GQ

K

Your problem is to start with such a sequence of lines of leaves from a binary search tree of letters and output the preorder traversal of the tree.

输入

The input will contain one or more data sets. Each data set is a sequence of one or more lines of capital letters. The lines contain the leaves removed from a binary search tree in the stages described above. The letters on a line will be listed in increasing alphabetical order.

Data sets are separated by a line containing only an asterisk (‘*’). The last data set is followed by a line containing only a dollar sign (‘$’). There are no blanks or empty lines in the input.

输出

For each input data set, there is a unique binary search tree that would produce the sequence of leaves. The output is a line containing only the preorder traversal of that tree, with no blanks.

让你根据输入构建一颗二分搜索树然后前序输出，非常简单。

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

class Node {
private:
    char val;
    Node* left;
    Node* right;
public:
    Node(char val) : val(val), left(nullptr), right(nullptr) {}

    void insert(char v) {
        if (val >= v) {
            if (left == nullptr) left = new Node(v);
            else left->insert(v);
        }
        else {
            if (right == nullptr) right = new Node(v);
            else right->insert(v);
        }
    }

    void preorder() {
        cout << val;
        if (left != nullptr) left->preorder();
        if (right != nullptr) right->preorder();
    }
};

int main() {
    
    while (true) {
        stack<string> s;
        string tmp;
        while (true) {
            cin >> tmp;
            if (tmp == "*" || tmp == "$") {
                char n = s.top()[0];
                s.pop();
                Node node(n);
                while (s.size()) {
                    string oo = s.top();
                    s.pop();
                    for (char k : oo) node.insert(k);
                }

                node.preorder();
                cout << endl;
                if (tmp == "$") return 0;
                continue;
            }
            
            s.push(tmp);
        }
        
    }

    
}

—— Summary

在这个难度的话，两个小时大概可以做 6 题，我认为是非常好的，这样机试排名应该在 50/250 左右，应该是不会拖后腿。

2018 夏令营上机 (5/21)

今天的题做不出来，寄。

A:计算两个日期之间的天数

A:计算两个日期之间的天数

查看提交统计提问

总时间限制: 1000ms 内存限制: 65536kB

描述

给定两个日期，计算相差的天数。比如2010-1-1和2010-1-3相差2天。

输入

共两行：

第一行包含三个整数startYear，startMonth，startDay，分别是起始年、月、日。

第二行包含三个整数endYear，endMonth，endDay，分别是结束年、月、日。

相邻两个整数之间用单个空格隔开。

年份范围在1~3000。保证日期正确且结束日期不早于起始日期。

输出

输出一个整数，即是两个日期相差的天数。

样例输入

模拟题，和昨天那题差不多。

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

int sy, sm, sd, ey, em, ed;
int days;

unordered_map<int, int> comp({
    {1, 31},
    {3, 31},
    {4, 30},
    {5, 31},
    {6, 30},
    {7, 31},
    {8, 31},
    {9, 30},
    {10, 31},
    {11, 30},
    {12, 31}
});


bool isRun(int i) {
   return (i % 4 == 0 && i % 100 != 0) || i % 400 == 0;
}

int main() {
    cin >> sy >> sm >> sd;
    cin >> ey >> em >> ed;

    if (sy != ey) {
        for (int i = 12; i >= sm; i--) {
            if (i == 2) days += isRun(sy) ? 29 : 28;
            else days += comp[i];
        }
        days -= sd;

        for (int i = sy + 1; i < ey; i++) {
            if (isRun(i)) days += 366;
            else days += 365;
        }

        for (int i = 1; i < em; i++) {
            if (i == 2) days += isRun(ey) ? 29 : 28;
            else days += comp[i];
        }
        days += ed;
    }

    // 相同年
    else {
        for (int i = sm; i < em; i++) {
            if (i == 2) days += isRun(sy) ? 29 : 28;
            else days += comp[i];
        }

        days -= sd;
        days += ed;
    }

    cout << days << endl;
}

B:回文子串

B:回文子串

查看提交统计提问

总时间限制: 1000ms 内存限制: 65536kB

描述

给定一个字符串，寻找并输出字符串中最长回文子串。回文串即从左到右和从右到左读都一样的字符串。

如果字符串中包含多个回文子串，则返回第一个。

输入

第一行是整数n,字符串的个数(n < 20)

输出

接下来n行，每行一个字符串

字符串的长度不超过100

记得是 DP，但是忘了转移方程了，或者说和最长公共子序列混了。这个 DP 要记得用长度来做外层递归。那个 O(n) 的算法就不记了，算了算了。

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

int n;

int main() {
    cin >> n;
    string s;
    while (n--) {
        cin >> s;
        // f[i][j] 代表 i, j 是不是回文子串
        vector<vector<bool>> f(s.size() + 1, vector<bool>(s.size()  + 1, false));

        int mxLen = 1, start = 0;
        for (int i = 0; i < s.size(); i++) f[i][i] = true;
        for (int L = 2; L <= s.size(); L ++) {
            for (int i = 0; i < s.size(); i++) {
                int j = i + L - 1;
                if (j >= s.size()) break;

                if (s[i] != s[j]) continue;
                f[i][j] = f[i+1][j-1];

                if (f[i][j] && L > mxLen) {
                    mxLen = L;
                    start = i;
                }
            }
        }

        cout << s.substr(start, mxLen) << endl;
    }
}

E:重要逆序对

查看提交统计提问

总时间限制: 10000ms 单个测试点时间限制: 1000ms 内存限制: 65536kB

描述

给定N个数的序列a1,a2,...aN，定义一个数对(ai, aj)为“重要逆序对”的充要条件为 i < j 且 ai > 2aj。求给定序列中“重要逆序对”的个数。

输入

第一行为序列中数字的个数N（1 ≤ N ≤ 200000）。

第二行为序列a1, a2 ... aN(0 ≤a ≤ 10000000)，由空格分开。

输出

输出一个整数，为给序列中“重要逆序对”的个数。

提示

如果使用printf输出long long类型，请用%lld

数据范围

对于40%的数据，有N ≤ 1000。

记得做过逆序对的题目，但是忘了。搜索之后想起来是归并排序的过程中来做。

对于重要逆序对，我们需要在 mergeSort 前首先统计一次重要逆序对的数量。

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

int n;

long long mergeSort(vector<int>& a, int l, int r) {
    if (l == r) return 0;
    int mid = (l + r) >> 1;
    long long cnt = mergeSort(a, l, mid);
    cnt += mergeSort(a, mid + 1, r);

    // 必须重新写，不然可能存在 a[i] > a[j] 但是不到 a[i] > 2*a[j] 的情况，导致 j++，使得 a[i+1] > 2*a[j] 的情况被忽略。
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
        if (a[i] > 2 *a[j]) cnt += mid - i + 1, j++;
        else i++;
    }
    i = l, j = mid + 1;
    vector<int> tmp(r-l+1);
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            tmp[k++] = a[i++];
        }
        else {
            tmp[k++] = a[j++];
        }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];

    for (int i = l; i <= r; i++) a[i] = tmp[i-l];
    return cnt;
}

int main() {
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    cout << mergeSort(a, 0, n-1);
}

C:The Die Is Cast

C:The Die Is Cast

查看提交统计提问

总时间限制: 1000ms 内存限制: 65536kB

描述

InterGames is a high-tech startup company that specializes in developing technology that allows users to play games over the Internet. A market analysis has alerted them to the fact that games of chance are pretty popular among their potential customers. Be it Monopoly, ludo or backgammon, most of these games involve throwing dice at some stage of the game.

Of course, it would be unreasonable if players were allowed to throw their dice and then enter the result into the computer, since cheating would be way to easy. So, instead, InterGames has decided to supply their users with a camera that takes a picture of the thrown dice, analyzes the picture and then transmits the outcome of the throw automatically.

For this they desperately need a program that, given an image containing several dice, determines the numbers of dots on the dice.

We make the following assumptions about the input images. The images contain only three different pixel values: for the background, the dice and the dots on the dice. We consider two pixels connected if they share an edge - meeting at a corner is not enough. In the figure, pixels A and B are connected, but B and C are not.

A set S of pixels is connected if for every pair (a,b) of pixels in S, there is a sequence a1, a2, ..., ak in S such that a = a1 and b = ak , and ai and ai+1 are connected for 1 ≤ i < k.

We consider all maximally connected sets consisting solely of non-background pixels to be dice. `Maximally connected' means that you cannot add any other non-background pixels to the set without making it dis-connected. Likewise we consider every maximal connected set of dot pixels to form a dot.

输入

The input consists of pictures of several dice throws. Each picture description starts with a line containing two numbers w and h, the width and height of the picture, respectively. These values satisfy 5 ≤ w, h ≤ 50.

The following h lines contain w characters each. The characters can be: "." for a background pixel, "*" for a pixel of a die, and "X" for a pixel of a die's dot.

Dice may have different sizes and not be entirely square due to optical distortion. The picture will contain at least one die, and the numbers of dots per die is between 1 and 6, inclusive.

The input is terminated by a picture starting with w = h = 0, which should not be processed.

输出

For each throw of dice, first output its number. Then output the number of dots on the dice in the picture, sorted in increasing order.

Print a blank line after each test case.

没看懂这题表示的意思，理解了半天懂了，就是判断有几个骰子然后骰子是几点。利用 DFS/BFS 消骰子和消点数就好。

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

int n, m;

int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};

void getPoint(vector<vector<char>>& f, int x, int y) {
    f[x][y] = '*';
    for (int i = 0; i < 4; i++) {
        int xx = x + dx[i], yy = y + dy[i];
        if (xx < 0 || xx >= m || yy < 0 || yy >= n) continue;

        if (f[xx][yy] == '.' || f[xx][yy] == '*') continue;
        getPoint(f, xx, yy);
    }
}

void getDice(vector<vector<char>>& f, vector<int>& nums, int diceIdx, int x, int y) {
    f[x][y] = '.';
    for (int i = 0; i < 4; i++) {
        int xx = x + dx[i], yy = y + dy[i];
        if (xx < 0 || xx >= m || yy < 0 || yy >= n) continue;

        if (f[xx][yy] == '.') continue;
        if (f[xx][yy] == 'X') getPoint(f, xx, yy), nums[diceIdx] ++;
        if (f[xx][yy] == '*') getDice(f, nums, diceIdx, xx, yy);
        
    }
}

int main() {
    int idx = 0;
    while (cin >> n >> m) {
        if (n == 0 && m == 0) return 0;
        vector<vector<char>> f(m, vector<char>(n));
        vector<int> nums;
        int diceIdx = 0;
        char ch;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                { cin >> ch; f[i][j] = ch; }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (f[i][j] == '*') {
                    nums.push_back(0);
                    getDice(f, nums, diceIdx, i, j);
                    diceIdx ++;
                }
            }
        }

        

        sort(nums.begin(), nums.end());
        if (idx) cout << endl;
        idx ++;
        cout << "Throw " << idx << endl;
        for (int i = 0; i < nums.size(); i++) {
            cout << nums[i];
            if (i != nums.size()-1) cout << " ";
        }
        cout << endl;
    }
}

G:食物链

G:食物链

查看提交统计提问

总时间限制: 1000ms 内存限制: 65536kB

描述

动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。

现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。

有人用两种说法对这N个动物所构成的食物链关系进行描述：

第一种说法是"1 X Y"，表示X和Y是同类。

第二种说法是"2 X Y"，表示X吃Y。

此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

1） 当前的话与前面的某些真的话冲突，就是假话；

2） 当前的话中X或Y比N大，就是假话；

3） 当前的话表示X吃X，就是假话。

你的任务是根据给定的N（1 ≤ N ≤ 50,000）和K句话（0 ≤ K ≤ 100,000），输出假话的总数。

输入

第一行是两个整数N和K，以一个空格分隔。

以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。

若D=1，则表示X和Y是同类。

若D=2，则表示X吃Y。

输出

只有一个整数，表示假话的数目。

用扩展并查集来做。ACWing 原题。

—— Summary

今天的题寄了。就做出来一题。其它或多或少都进行了搜索辅助 :(

用了一个半小时左右写了 4 题，然后上体育课去了。

2017 夏令营上机 (5/23)

17 年有 10 题，不过难度较低。2.5h 做了 7 题。

A:判决素数个数

A:判决素数个数

查看提交统计提问

总时间限制: 1000ms 内存限制: 65536kB

描述

输入两个整数X和Y，输出两者之间的素数个数（包括X和Y）。

输入

两个整数X和Y（1 ≤ X,Y ≤ 105）。

输出

输出一个整数，表示X，Y之间的素数个数（包括X和Y）。

素数检测，到根号就可以

#include <iostream>
using namespace std;

int a, b;

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

int main() {
    cin >> a >> b;
    int cnt = 0;
    for (int i = a; i <= b; i++) {
        cnt += isPrime(i);
    }

    cout << cnt << endl;
}

B:编码字符串

B:编码字符串(string)

查看提交统计提问

总时间限制: 1000ms 内存限制: 65536kB

描述

在数据压缩中，一个常用的方法是行程长度编码压缩。对于一个待压缩的字符串，我们可以依次记录每个字符及重复的次数。例如，待压缩的字符串为"aaabbbbcbb"，压缩结果为(a,3)(b,4)(c,1)(b,2)。这种压缩对于相邻数据重复较多的情况有效，如果重复状况较少，则压缩的效率较低。

现要求根据输入的字符串，首先将字符串中所有大写字母转化为小写字母，然后将字符串进行压缩。

输入

一个字符串，长度大于0，且不超过1000，全部由大写或小写字母组成。

输出

输出为编码之后的字符串，形式为：(a,3)(b,4)(c,1)(d,2)，即每对括号内分别为小写字符及重复的次数，不含任何空格。

双指针或者说滑动窗口

#include <iostream>
using namespace std;

int main() {
    string tmp;
    cin >> tmp;
    int l = 0, r = 0;
    char now = tmp[0];
    while (r < tmp.length()) {
        char ch = tmp[r] < 'a' ? tmp[r] - 'A' + 'a' : tmp[r];
        if (ch != now) {
            cout << "(" << now << "," << r - l << ")";
            now = ch;
            l = r;
        }
        else r++;
    }
    cout << "(" << now << "," << r - l << ")";
}

C:岛屿周长

C:岛屿周长(matrix)

查看提交统计提问

总时间限制: 1000ms 内存限制: 65536kB

描述

用一个nm的二维数组表示地图，1表示陆地，0代表海水，每一格都表示一个11的区域。地图中的格子只能横向或者纵向连接（不能对角连接），连接在一起的陆地称作岛屿，同时整个地图都被海水围绕。假设给出的地图中只会有一个岛屿，并且岛屿中不会有湖（即不会有水被陆地包围的情况出现）。请判断所给定的二维地图中岛屿的周长。

输入

第一行为n和m，表示地图的大小(1≤n≤100, 1≤m≤100)。接下来n行，每行有m个数，分别描述每一格的数值。数值之间均用空格隔开。

输出

只有一行，即岛屿的周长（正整数）。

BFS，一个岛屿默认周长 4，连接一边就少 1

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

int n, m;
long long res;

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

void bfs(vector<vector<int>>& mat, int x, int y) {
    mat[x][y] = 2;
    int o = 4;
    
    for (int i = 0; i < 4; i++) {
        int xx = x + dx[i], yy = y + dy[i];
        if (xx < 0 || xx >= n || yy < 0 || yy >= m) continue;

        if (mat[xx][yy] == 2 || mat[xx][yy] == 1) o --;
        if (mat[xx][yy] == 1) bfs(mat, xx, yy);
    }
    res += o;
}


int main() {
    cin >> n >> m;
    int x = -1, y = -1;
    vector<vector<int>> mat(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> mat[i][j];
            if (mat[i][j] == 1) x = i, y = j;
        }
    }
    if (x == -1 || y == -1) {
        cout << 0 << endl;
        return 0;
    }
    bfs(mat, x, y);
    cout << res << endl;
}

D:Safecracker

D:Safecracker

查看提交统计提问

总时间限制: 1000ms 内存限制: 65536kB

描述

"The item is locked in a Klein safe behind a painting in the second-floor library. Klein safes are extremely rare; most of them, along with Klein and his factory, were destroyed in World War II. Fortunately old Brumbaugh from research knew Klein's secrets and wrote them down before he died. A Klein safe has two distinguishing features: a combination lock that uses letters instead of numbers, and an engraved quotation on the door. A Klein quotation always contains between five and twelve distinct uppercase letters, usually at the beginning of sentences, and mentions one or more numbers. Five of the uppercase letters form the combination that opens the safe. By combining the digits from all the numbers in the appropriate way you get a numeric target. (The details of constructing the target number are classified.) To find the combination you must select five letters v, w, x, y, and z that satisfy the following equation, where each letter is replaced by its ordinal position in the alphabet (A=1, B=2, ..., Z=26). The combination is then vwxyz. If there is more than one solution then the combination is the one that is lexicographically greatest, i.e., the one that would appear last in a dictionary."

v - w2+ x3- y4+ z5= target

"For example, given target 1 and letter set ABCDEFGHIJKL, one possible solution is FIECB, since 6 - 92+ 53- 34+ 25= 1. There are actually several solutions in this case, and the combination turns out to be LKEBA. Klein thought it was safe to encode the combination within the engraving, because it could take months of effort to try all the possibilities even if you knew the secret. But of course computers didn't exist then."

"Develop a program to find Klein combinations in preparation for field deployment. Use standard test methodology as per departmental regulations.

输入

Input consists of one or more lines containing a positive integer target less than twelve million, a space, then at least five and at most twelve distinct uppercase letters. The last line will contain a target of zero and the letters END; this signals the end of the input.

输出

For each line output the unique Klein combination, or 'no solution' if there is no correct combination. Use the exact format shown below."

题意好像就是一个暴力破解，我想了很久，没想到什么好办法优化。就还是说首先预计算然后再排序一次？最多 12^5，应该可以接受。

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

vector<vector<int>> h(27);

int main() {
    for (int i = 1; i <= 26; i++) {
        int r = 1;
        for (int j = 0; j < 5; j++) {
            r *= i;
            h[i].push_back(r);
        }
    }

    int target;
    string str;

    while (true) {
        cin >> target >> str;
        if (target == 0 && str == "END") return 0;
        vector<int> nums;
        for (char c : str) {
            nums.push_back(c-'A'+1);
        }
        sort(nums.begin(), nums.end(), [](auto l, auto r) {
            return l > r;
        });

        int n = nums.size();
        for (int a = 0; a < n; a ++) {
            for (int b = 0; b < n; b ++) {
                if (a == b) continue;
                for (int c = 0; c < n; c++) {
                    if (a == c || b == c) continue;
                    for (int d = 0; d < n; d++) {
                        if (a == d || b == d || c == d) continue;
                        for (int e = 0; e < n; e++) {
                            if (a == e || b == e || c == e || d == e) continue;
                            if (h[nums[a]][0] - h[nums[b]][1] + h[nums[c]][2] - h[nums[d]][3] + h[nums[e]][4] == target)  {
                                printf("%c%c%c%c%c\n", nums[a] + 'A' - 1, nums[b] + 'A' - 1, nums[c] + 'A' - 1, nums[d] + 'A' - 1, nums[e] + 'A' - 1);
                                goto find;
                            }
                        }
                    }
                }
            }
        }
        
        cout << "no solution" << endl;
        find:
        continue;
    }
}

E:怪盗基德的滑翔翼

E:怪盗基德的滑翔翼

查看提交统计提问

总时间限制: 1000ms 内存限制: 65536kB

描述

怪盗基德是一个充满传奇色彩的怪盗，专门以珠宝为目标的超级盗窃犯。而他最为突出的地方，就是他每次都能逃脱中村警部的重重围堵，而这也很大程度上是多亏了他随身携带的便于操作的滑翔翼。

有一天，怪盗基德像往常一样偷走了一颗珍贵的钻石，不料却被柯南小朋友识破了伪装，而他的滑翔翼的动力装置也被柯南踢出的足球破坏了。不得已，怪盗基德只能操作受损的滑翔翼逃脱。

假设城市中一共有N幢建筑排成一条线，每幢建筑的高度各不相同。初始时，怪盗基德可以在任何一幢建筑的顶端。他可以选择一个方向逃跑，但是不能中途改变方向（因为中森警部会在后面追击）。因为滑翔翼动力装置受损，他只能往下滑行（即：只能从较高的建筑滑翔到较低的建筑）。他希望尽可能多地经过不同建筑的顶部，这样可以减缓下降时的冲击力，减少受伤的可能性。请问，他最多可以经过多少幢不同建筑的顶部（包含初始时的建筑）？

输入

输入数据第一行是一个整数K（K < 100），代表有K组测试数据。

每组测试数据包含两行：第一行是一个整数N(N < 100)，代表有N幢建筑。第二行包含N个不同的整数，每一个对应一幢建筑的高度h（0 < h < 10000），按照建筑的排列顺序给出。

输出

对于每一组测试数据，输出一行，包含一个整数，代表怪盗基德最多可以经过的建筑数量。

最长上升子序列。不过要从左到右和从右到左跑，它测例表现了这一点。

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

int k;

int main() {
    cin >> k;
    while (k--) {
        int n;
        cin >> n;
        int res = 0;
        vector<int> height(n), f(n), ff(n);
        for (int i = 0; i < n; i++) {
            cin >> height[i];
        }
        for (int i = 0; i < n; i++) {
            f[i] = 1;
            for (int j = 0; j < i; j++) {
                if (height[j] > height[i]) f[i] = max(f[i], f[j] + 1);
            }
            res = max(res, f[i]);
        }
        for (int i = n - 1; i >= 0; i--) {
            ff[i] = 1;
            for (int j = n - 1; j > i; j--) {
                if (height[j] > height[i]) ff[i] = max(ff[i], ff[j] + 1);
            }
            res = max(res, ff[i]);
        }
        cout << res << endl;
    }
}

G:实现堆结构

G:实现堆结构

查看提交统计提问

总时间限制: 3000ms 内存限制: 65535kB

描述

定义一个数组，初始化为空。在数组上执行两种操作：

1、增添1个元素，把1个新的元素放入数组。

2、输出并删除数组中最小的数。

使用堆结构实现上述功能的高效算法。

输入

第一行输入一个整数t，代表测试数据的组数。

对于每组测试数据，第一行输入一个整数n，代表操作的次数。

每次操作首先输入一个整数type。

当type=1，增添操作，接着输入一个整数u，代表要插入的元素。

当type=2，输出删除操作，输出并删除数组中最小的元素。

1≤n≤100000。

输出

每次删除操作输出被删除的数字。

自己实现一个小根堆，那么就实现 down 和 up 方法就好。用一个 size 标明大小。

#include <iostream>
#include <vector>

using namespace std;
int k;
int s;

void down(vector<int>& heap, int idx) {
    int t = idx;
    if (2*idx <= s && heap[2*idx] < heap[t]) t = 2 * idx;
    if (2*idx + 1 <= s && heap[2*idx+1] < heap[t]) t = 2 * idx + 1;
    if (t != idx) {
        swap(heap[t], heap[idx]);
        down(heap, t);
    }
}

void up(vector<int>& heap, int idx) {
    while (idx / 2 > 0 && heap[idx / 2] > heap[idx]) {
        swap(heap[idx], heap[idx / 2]);
        idx /= 2;
    }
}

void insert(vector<int>& heap, int num) {
    s++;
    heap[s] = num;
    up(heap, s);
}

void printRemove(vector<int>& heap) {
    cout << heap[1] << endl;
    swap(heap[1], heap[s]);
    s--;
    down(heap, 1);
}

int main() {
    cin >> k;
    while (k--) {
        int n;
        s = 0;
        cin >> n;
        vector<int> heap(n + 1);
        int type;
        for (int i = 0; i < n; i++) {
            cin >> type;
            if (type == 1) {
                int num;
                cin >> num;
                insert(heap, num);
            }
            else if (type == 2) {
                printRemove(heap);
            }
        }
    }
}

H:Subway

H:Subway

查看提交统计提问

总时间限制: 1000ms 内存限制: 65536kB

描述

You have just moved from a quiet Waterloo neighbourhood to a big, noisy city. Instead of getting to ride your bike to school every day, you now get to walk and take the subway. Because you don't want to be late for class, you want to know how long it will take you to get to school.

You walk at a speed of 10 km/h. The subway travels at 40 km/h. Assume that you are lucky, and whenever you arrive at a subway station, a train is there that you can board immediately. You may get on and off the subway any number of times, and you may switch between different subway lines if you wish. All subway lines go in both directions.

输入

Input consists of the x,y coordinates of your home and your school, followed by specifications of several subway lines. Each subway line consists of the non-negative integer x,y coordinates of each stop on the line, in order. You may assume the subway runs in a straight line between adjacent stops, and the coordinates represent an integral number of metres. Each line has at least two stops. The end of each subway line is followed by the dummy coordinate pair -1,-1. In total there are at most 200 subway stops in the city.

输出

Output is the number of minutes it will take you to get to school, rounded to the nearest minute, taking the fastest route.

最短路。思路就是每条地铁线里连点，然后脚走任意两个点，权重就是时间。

最大的问题可能还是代码编写的问题，一开始在那用邻接表写，但是不知道要开多大的数组，后面摆烂了用 vector 了。还有数据读入的问题，如何区分地铁站很烦。

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

const double WALK_SPEED = 10 / 60.0;
const double SUBWAY_SPEED = 40 / 60.0;

class Point {
public:
    int x, y;

    Point(int a, int b) : x(a), y(b) {}
};

double distance(Point &a, Point &b) {
    return sqrt(pow(a.x-b.x, 2) + pow(a.y-b.y, 2)) / 1000.0;
}

class Edge {
public:
    int to;
    double weight;

    Edge(int to, double weight) : to(to), weight(weight) {}
};


void djikstra(vector<vector<Edge>>& graph) {
    vector<double> dist(graph.size(), 0x3f3f3f3f);
    priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> heap;
    
    dist[0] = 0;
    heap.push({0, 0});

    while (!heap.empty()) {
        double d = heap.top().first;
        int u = heap.top().second;
        heap.pop();

        if (d > dist[u]) continue;

        for (auto edge : graph[u]) {
            if (dist[u] + edge.weight < dist[edge.to]) {
                dist[edge.to] = dist[u] + edge.weight;
                heap.push({dist[edge.to], edge.to});
            }
        }
    }

    cout << round(dist[1]);
}


int main() {
    int home_x, home_y, school_x, school_y;
    cin >> home_x >> home_y >> school_x >> school_y;

    vector<Point> points;
    points.push_back(Point(home_x, home_y));
    points.push_back(Point(school_x, school_y));

    vector<vector<Edge>> graph;
    graph.resize(2);  // 0: home、1: school

    int x, y;
    vector<int> subways;
    while (cin >> x >> y) {
        while (x != -1 && y != -1) {
            points.push_back({x, y});
            subways.push_back(points.size() - 1);
            cin >> x >> y;
        }

        for (int i = 0; i < subways.size(); i++) {
            graph.push_back(vector<Edge>());
        }

        for (int i = 0; i < subways.size() - 1; i++) {
            double dist = distance(points[subways[i]], points[subways[i+1]]) / SUBWAY_SPEED;
            graph[subways[i]].emplace_back(Edge(subways[i+1], dist));
            graph[subways[i+1]].emplace_back(Edge(subways[i], dist));
        }
    }

    for (int i = 0; i < points.size(); i++) {
        for (int j = i + 1; j < points.size(); j++) {
            double dist = distance(points[i], points[j]) / WALK_SPEED;
            graph[i].emplace_back(Edge(j, dist));
            graph[j].emplace_back(Edge(i, dist));
        }
    }

    djikstra(graph);
}

—— Summary

如果是这个难度，那么至少 50% 是可以拿到的。加油吧。

2018 软件工程学科夏令营 (6/12)

A:最简真分数

A:最简真分数 查看提交统计提问 总时间限制: 1000ms 内存限制: 65536kB 描述 给出n个正整数，任取两个数分别作为分子和分母组成最简真分数，编程求共有几个这样的组合。

输入 第一行是一个正整数n（n≤600）。 第二行是n个不同的整数，相邻两个整数之间用单个空格隔开。整数大于1且小于等于1000。 输出 一个整数，即最简真分数组合的个数。

水题

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

int N;

int gcd(int a, int b) {
    if (!b) return a;
    return gcd(b, a % b);
}

int main() {
    cin >> N;
    int ans = 0;
    vector<int> s(N);
    for (int i = 0; i < N; i++) cin >> s[i];
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            if (gcd(s[i], s[j]) == 1) ans += 1;
        }
    }
    cout << ans;
}

B:n-gram串频统计

B:n-gram串频统计 查看提交统计提问 总时间限制: 1000ms 内存限制: 65536kB 描述 在文本分析中常用到n-gram串频统计方法，即，统计相邻的n个单元（如单词、汉字、或者字符）在整个文本中出现的频率。假设有一个字符串，请以字符为单位，按n-gram方法统计每个长度为 n 的子串出现的频度，并输出最高频度以及频度最高的子串。所给的字符串只包含大小写字母，长度不多于500个字符，且 1 < n < 5。

如果有多个子串频度最高，则根据其在序列中第一次出现的次序依次输出，每行输出一个，如果最高频度不大于1，则输出NO。

输入 第一行为n； 第二行为字符串。 输出 输出最高频度以及频度最高的所有子串。若最高频度不大于1，只输出一行NO。

全部统计一边就完事了，用个 hash 存次数。主要就是它这个依次输出很烦，所以再用一个 vector 首先去存。

#include <iostream>
#include <stack>
#include <unordered_map>
#include <queue>
#include <string>

using namespace std;

int sz;

int main() {
    string str;
    cin >> sz;
    cin >> str;
    vector<string> result(510);
    int ans = 0;
    unordered_map<string, int> hash;

    string now = str.substr(0, sz);
    result.push_back(now);
    hash[now] ++;
    for (int i = sz; i < str.size(); i++) {
        now = now.substr(1) + str[i];
        result.push_back(now);
        hash[now] ++;
        ans = max(ans, hash[now]);
    }

    if (ans == 1) {
        cout << "NO";
        return 0;
    }

    cout << ans << endl;

    for (auto i : result) {
        if (hash[i] == ans) {
            cout << i << endl;
            hash[i] = 0;
        }
    }

}

C:垂直直方图

C:垂直直方图 查看提交统计提问 总时间限制: 1000ms 内存限制: 65536kB 描述 输入4行全部由大写字母组成的文本，输出一个垂直直方图，给出每个字符出现的次数。注意：只用输出字符的出现次数，不用输出空白字符，数字或者标点符号的输出次数。

输入 输入包括4行由大写字母组成的文本，每行上字符的数目不超过80个。 输出 输出包括若干行。其中最后一行给出26个大写英文字母，这些字母之间用一个空格隔开。前面的几行包括空格和星号，每个字母出现几次，就在这个字母的上方输出一个星号。注意：输出的第一行不能是空行。

小模拟

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

int n = 4;

int main() {
    vector<int> s(26, 0);
    int ans = 0;
    while (n --) {
        string tmp;
        getline(cin, tmp, '\n');
        for (auto c : tmp) {
            if (c >= 'A' && c <= 'Z') s[c-'A'] ++, ans = max(ans, s[c-'A']);
        }
    }

    do {
        for (auto c : s) {
            if (c >= ans) cout << "*";
            else cout << " ";
            cout << " ";
        }
        cout << endl;
    } while (--ans);

    for (int i = 0; i < 26; i++) {
        char ch = 'A' + i;
        cout << ch << (i == 25 ? "" : " ");
    }
}

D:Word-Search Wonder

D:Word-Search Wonder 查看提交统计提问 总时间限制: 1000ms 内存限制: 65536kB 描述 The Pyrates Restaurant was starting to fill up as Valentine McKee walked in. She scanned the crowd for her sister, brother-in-law, and nephew. Seeing her sister waving from the far end of the restaurant, she made her way back to their booth. Hi, Valentine,'' her sister and brother-in-law, Niki and Dennis Chapman, greeted her. Hi, guys,'' she replied. ``What are you doing, Wade?'' she asked her nephew. He was busy working on one of the restaurant's activity sheets with a crayon.

I'm doing a word search game,'' Wade explained. I have to find all of these words in this big mess of letters. This is really hard.'' Wade looked intently at the paper in front of him.

``Can I help?'' asked Valentine, looking across the table at the activity sheet.

``Sure. These are the words we're looking for. They're the names of different kinds of Planes, Trains, and Automobiles.'' 输入 The first line of input will specify the length (in characters) of the sides of the letter matrix (the matrix of letters will be square). The length, l, will be in the range 1 ≤ l ≤ 100. The next l lines of input will be the matrix itself, each line will contain l uppercase letters.

A list of words will follow. Each word will be on a line by itself; there will be 100 or fewer words. Each word will be 100 or fewer characters long, and will only contain uppercase letters.

The final line of input will contain a single zero character. 输出 Your program should attempt to find each word from the word list in the puzzle. A word is found'' if all the characters in the word can be traced in a single (unidirectional) horizontal, vertical, or diagonal line in the letter matrix. Words may not wrap around'' rows or columns, but horizontal and diagonal words may proceed from right to left (``backwards''). For each word that is found, your program should print the coordinates of its first and last letters in the matrix on a single line, separated by a single space. Coordinates are pairs of comma-separated integers (indexed from 1), where the first integer specifies the row number and the second integer specifies the column number.

If a word is not found, the string ``Not found'' should be output instead of a pair of coordinates.

Each word from the input can be ``found'' at most once in the puzzle.

就是要找它怎么出现过嘛，方向固定，遍历一下就完事了。这里我省事，把所有字符的出现位置都存了。

出问题的地方在读不懂这个题，它说 Words may not ``wrap around'' rows or columns, but horizontal and diagonal words may proceed from right to left (``backwards'').，但是我既要从上到下，又要从下到上从右到左。

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

int n;
bool flag;

int dx[8] = {1, 1, 1, 0, 0, -1, -1, -1};
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

int main() {
    cin >> n;
    vector<vector<char>> mat(n + 1, vector<char>(n + 1));
    vector<vector<pair<int, int>>> hash(26);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> mat[i][j];
            hash[mat[i][j] - 'A'].push_back({i, j});
        }
    }
    string str;
    while (cin >> str) {
        if (str == "0") return 0;
        flag = false;

        for (auto &[x, y] : hash[str[0]-'A']) {
            if (flag) break;
            for (int i = 0; i < 8; i++) {
                if (flag) break;
                int xx = x, yy = y;
                for (int j = 1; j < str.size(); j++) {
                    xx = xx + dx[i], yy = yy + dy[i];
                    if (xx < 0 || xx >= n || yy < 0 || yy >= n) break;
                    if (mat[xx][yy] != str[j]) break;

                    if (j == str.size() - 1) {
                        cout << x+1 << "," << y+1 << " " << xx+1 << "," << yy+1 << endl;
                        flag = true;
                    }
                }
            }
        }
        if (!flag) cout << "Not found" << endl;

    }
}

E:A Mini Locomotive

E:A Mini Locomotive 查看提交统计提问 总时间限制: 1000ms 内存限制: 65536kB 描述 A train has a locomotive that pulls the train with its many passenger coaches. If the locomotive breaks down, there is no way to pull the train. Therefore, the office of railroads decided to distribute three mini locomotives to each station. A mini locomotive can pull only a few passenger coaches. If a locomotive breaks down, three mini locomotives cannot pull all passenger coaches. So, the office of railroads made a decision as follows:

1. Set the number of maximum passenger coaches a mini locomotive can pull, and a mini locomotive will not pull over the number. The number is same for all three locomotives.
2. With three mini locomotives, let them transport the maximum number of passengers to destination. The office already knew the number of passengers in each passenger coach, and no passengers are allowed to move between coaches.
3. Each mini locomotive pulls consecutive passenger coaches. Right after the locomotive, passenger coaches have numbers starting from 1.

For example, assume there are 7 passenger coaches, and one mini locomotive can pull a maximum of 2 passenger coaches. The number of passengers in the passenger coaches, in order from 1 to 7, is 35, 40, 50, 10, 30, 45, and 60.

If three mini locomotives pull passenger coaches 1-2, 3-4, and 6-7, they can transport 240 passengers. In this example, three mini locomotives cannot transport more than 240 passengers.

Given the number of passenger coaches, the number of passengers in each passenger coach, and the maximum number of passenger coaches which can be pulled by a mini locomotive, write a program to find the maximum number of passengers which can be transported by the three mini locomotives. 输入 The first line of the input contains a single integer t (1 ≤ t ≤ 11), the number of test cases, followed by the input data for each test case. The input for each test case will be as follows: The first line of the input file contains the number of passenger coaches, which will not exceed 50,000. The second line contains a list of space separated integers giving the number of passengers in each coach, such that the ith number of in this line is the number of passengers in coach i. No coach holds more than 100 passengers. The third line contains the maximum number of passenger coaches which can be pulled by a single mini locomotive. This number will not exceed 1/3 of the number of passenger coaches. 输出 There should be one line per test case, containing the maximum number of passengers which can be transported by the three mini locomotives.

一个动态规划。但其实没想到这样规划，题目看累了，丢给 GPT 翻译，它直接把结果给我了，学习。

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

int main() {
    int N;
    cin >> N;
    while (N--) {
        int n;
        cin >> n;
        vector<int> trains(n);
        vector<int> sums(n);
        int sum = 0;
        for (int i = 0; i < n; i++) {
            cin >> trains[i];
            sum += trains[i];
            sums[i] = sum;
        }
        int lim;
        cin >> lim;

        vector<int> ff(n, 0), fs(n, 0), ft(n, 0);
        // 到达 i 时第一辆车最多装 f[i]
        for (int i = lim - 1; i < n; i++) {
            ff[i] = max(ff[i-1], sums[i] - sums[i-lim]);
        }

        for (int i = lim*2 - 1; i < n; i++) {
            fs[i] = max(fs[i-1], ff[i-lim] + sums[i] - sums[i-lim]);
        }

        for (int i = lim*3 - 1; i < n; i++) {
            ft[i] = max(ft[i-1], fs[i-lim] + sums[i] - sums[i-lim]);
        }

        cout << ft[n-1] << endl;
    }
}

2017 推免 (6/15)

A:因子分解

A:因子分解 查看提交统计提问 总时间限制: 1000ms 内存限制: 65536kB 描述 输入一个数，输出其素因子分解表达式。

输入 输入一个整数 n (2 ≤ n < 100)。 输出 输出该整数的因子分解表达式。 表达式中各个素数从小到大排列。 如果该整数可以分解出因子a的b次方，当b大于1时，写做 a^b ；当b等于1时，则直接写成a。

水题。卡的点在如何让它头没有 * 或者尾没有 *，不然两分钟写完了。

10min

#include <iostream>
using namespace std;

int n;

int main() {
    cin >> n;
    bool flag = false;
    for (int i = 2; i <= n/i; i++) {
        if (n%i) continue;

        int s = 0;
        if (flag) cout << "*";
        cout << i;
        if (!flag) flag = true;
        while (!(n%i)) n/= i, s++;
        if (s != 1) cout << "^" << s;
    }
    if (n > 1) {
        if (flag) cout << "*";
        cout << n << endl;
    }
}

B:ISBN号码

B:ISBN号码 查看提交统计提问 总时间限制: 1000ms 内存限制: 65536kB 描述 每一本正式出版的图书都有一个ISBN号码与之对应，ISBN码包括9位数字、1位识别码和3位分隔符，其规定格式如“x-xxx-xxxxx-x”，其中符号“-”是分隔符（键盘上的减号），最后一位是识别码，例如0-670-82162-4就是一个标准的ISBN码。ISBN码的首位数字表示书籍的出版语言，例如0代表英语；第一个分隔符“-”之后的三位数字代表出版社，例如670代表维京出版社；第二个分隔之后的五位数字代表该书在出版社的编号；最后一位为识别码。

识别码的计算方法如下：

首位数字乘以1加上次位数字乘以2……以此类推，用所得的结果mod 11，所得的余数即为识别码，如果余数为10，则识别码为大写字母X。例如ISBN号码0-670-82162-4中的识别码4是这样得到的：对067082162这9个数字，从左至右，分别乘以1，2，…，9，再求和，即0×1+6×2+„„+2×9=158，然后取158 mod 11的结果4作为识别码。

你的任务是编写程序判断输入的ISBN号码中识别码是否正确，如果正确，则仅输出“Right”；如果错误，则输出你认为是正确的ISBN号码。

输入 只有一行，是一个字符序列，表示一本书的ISBN号码（保证输入符合ISBN号码的格式要求）。 输出 共一行，假如输入的ISBN号码的识别码正确，那么输出“Right”，否则，按照规定的格式，输出正确的ISBN号码（包括分隔符“-”）。

简单题，卡的点也在读输入hhh。

10min

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

int main() {
    string chs;
    string tmp;
    getline(cin, tmp, '\n');

    int idx = 0;
    for (auto c : tmp) {
        if (c == '-') continue;
        chs[idx++] = c;
    }

     int sum = 0;
     for (int i = 0; i < 9; i++) {
        if (chs[i] == 'X' || chs[i] == 'x') sum += 10*(i+1);
        else sum += (chs[i] - '0')*(i+1);
        sum %= 11;
     }
     if (sum == chs[9] - '0' || (sum == 10 && (chs[9] == 'X' || chs[9] == 'x'))) cout << "Right" << endl;
     else {
        for (int i = 0; i < 9; i++) {
            cout << chs[i];
            if (i == 0 || i == 3 || i == 8) cout << '-';
        }
        char ch = (sum == 10 ? 'X' : sum+'0');
        cout << ch;
     }
}

C:肿瘤检测

C:肿瘤检测 查看提交统计提问 总时间限制: 1000ms 内存限制: 65536kB 描述 一张CT扫描的灰度图像可以用一个N*N（0 < N ≤ 100）的矩阵描述，矩阵上的每个点对应一个灰度值（整数），其取值范围是0-255。我们假设给定的图像中有且只有一个肿瘤。在图上监测肿瘤的方法如下：如果某个点对应的灰度值小于等于50，则这个点在肿瘤上，否则不在肿瘤上。我们把在肿瘤上的点的数目加起来，就得到了肿瘤在图上的面积。任何在肿瘤上的点，如果它是图像的边界或者它的上下左右四个相邻点中至少有一个是非肿瘤上的点，则该点称为肿瘤的边界点。肿瘤的边界点的个数称为肿瘤的周长。现在给定一个图像，要求计算其中的肿瘤的面积和周长。

输入 输入第一行包含一个正整数N（0 < N ≤ 100），表示图像的大小；接下来N行，每行包含图像的一行。图像的一行用N个整数表示（所有整数大于等于0，小于等于255），两个整数之间用一个空格隔开。 输出 输出只有一行，该行包含两个正整数，分别为给定图像中肿瘤的面积和周长，用一个空格分开。

难评的题目。读完之后想着岛屿周长直接 DFS 了。后面才发现边界点的定义。然后后面又发现边界点边界也算（笑）

10min 写完，最后 AC 总共用 40min

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


int n;
int cnt;
int total;

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1,  1};

bool checkBoard(vector<vector<int>> mat, int x, int y) {
    if (x < 0 || y < 0 || x >= n || y >= n || mat[x][y] > 50) return false;
    if (!x || x == n - 1 || !y || y == n - 1) return true;
    for (int i = 0; i < 4; i++) {
        int xx = x + dx[i], yy = y + dy[i];
        if (x < 0 || y < 0 || x >= n || y >= n) continue;
        if (mat[xx][yy] > 50) return true;
    }
    return false;
}

int main() {
    cin >> n;
    bool flag = false;
    int ii = 0, jj = 0;
    vector<vector<int>> mat(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> mat[i][j];
            if ( !flag && mat[i][j] <= 50) flag = true, ii = i, jj = j;
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cnt += mat[i][j] <= 50;
            total += checkBoard(mat, i, j);
        }
    }

    cout << cnt << ' ' << total << endl;

}

D:回文素数

D:回文素数 查看提交统计提问 总时间限制: 5000ms 内存限制: 65536kB 描述 一个数如果从左往右读和从右往左读数字是相同的，则称这个数是回文数，如121，1221，15651都是回文数。给定位数n，找出所有既是回文数又是素数的n位十进制数。（注：不考虑超过整型数范围的情况）。 输入 位数n,其中1≤n≤9。 输出 第一行输出满足条件的素数个数。 第二行按照从小到大的顺序输出所有满足条件的素数，两个数之间用一个空格区分。

我是纯粹的傻逼。一开始我想如何构造回文数，但是觉得太麻烦了直接遍历判断回文数算了。

我是纯粹的傻逼，n = 9 的时候那不是要生成 9e9 个数字，生成就爆了...

然而写的时候没反应过来，一直坚持不懈修改判断素数的代码，还打了个表。

最后放弃了，我生成回文数吧，哈哈，我是傻逼。

15min 写完，修改完 AC 总共 60min

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

int n;

long long genP(int i) {
    int original = i, reversed = 0;
    if (n % 2) i /= 10;
    while (i) {
        reversed = reversed * 10 + i % 10;
        i /= 10;
    }
    return original * pow(10, n/2) + reversed;

}

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

bool isPrime2(vector<int>& table, int i) {
    if (i == 1) return false;
    for (auto x : table) {
        if (i == x) return true;
        if (!(i % x)) return false;
    }
    return true;
}

int main() {
    cin >> n;
    vector<int> mat(n);
    vector<int> res;
    vector<int> prime;

    if (n == 1) {
        cout << "4" << endl << "2 3 5 7" << endl;
        return 0;
    }

    for (int i = pow(10, (int) ((n + 1) / 2) - 1); i < pow(10, (int) ((n + 1)/ 2)); i++) {
        long long ii = genP(i);

        if (ii > INT_MAX) continue;
        if (isPrime(ii)) res.push_back(ii);
    }

    cout << res.size() << endl;
    for (auto i : res) {
        cout << i << " ";
    }
}

E:Railway tickets

E:Railway tickets 查看提交统计提问 总时间限制: 1000ms 内存限制: 65536kB 描述 The railway line "Ekaterinburg-Sverdlovsk" with several stations has been built. This railway line can be represented as a line segment, railway stations being points on it. The railway line starts at the station "Ekaterinburg" and finishes at the station "Sverdlovsk", so stations are numbered starting from "Ekaterinburg" (it has number 1) and "Sverdlovsk" is the last station.

Cost of the ticket between any two stations depends only on a distance between them. The prices for the tickets are specified in the following table. distance between stations -X

price for the ticket

0<X≤L1

C1

L1<X≤L2

C2

L2<X≤L3

C3

Direct tickets from one station to another can be booked if and only if the distance between these station does not exceed L3. So sometimes it is necessary to book several tickets to pay for the parts of the whole way between stations.

For example, on the railway line shown at the figure above there are seven stations. The direct ticket from the second station to the sixth one can not be booked. There are several ways to pay for the travel between these stations. One of them is to book two tickets: one ticket at price C2 to travel between the second and the third stations, and other at price C3 to travel between the third and the sixth stations. Note, that though the distance between the second and the sixth stations is equal to 2*L2, the whole travel can not be paid by booking two tickets at price C2, because each ticket is valid for only one travel and each travel should start and end only at stations.

Your task is to write a program, that will find the minimal cost of the travel between two given stations. 输入 The first line of the input file contains 6 integers L1, L2, L3, C1, C2, C3 (1 ≤ L1 < L2 < L3 ≤ 10^9, 1 ≤ C1 < C2 < C3 ≤ 10^9) in the specified order with one space between. The second line contains the amount of stations N (2 ≤ N ≤ 10000). The third line contains two different integers separated by space. They represent serial numbers of stations, the travel between which must be paid. Next N-1 lines contain distances from the first station ("Ekaterinburg") on the railway line to others. These distances are given as different positive integers and are arranged in the ascending order. The distance from "Ekaterinburg" to "Sverdlovsk" does not exceed 10^9. The distance between any neighboring stations does not exceed L3. The minimal travel cost between two given stations will not exceed 10^9. 输出 Program should print to the output file the only number, which is the minimal travel cost between two given stations.

显然的 dp，类似完全背包。对于第 i 个站，他的值就是从始发站转移过来（如果能转移的话）的最小值。

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

int l1, l2, l3, c1, c2, c3, n, p, q;

int main() {
    cin >> l1 >> l2 >> l3 >> c1 >> c2 >> c3;
    cin >> n;
    cin >> p >> q;
    
    if (p > q) swap(p, q);

    vector<int> f(n + 1, 0x3f3f3f3f);
    vector<int> d(n + 1);


    for (int i = 2; i <= n; i++) {
        cin >> d[i];
    }

    f[p] = 0;

    for (int i = p + 1; i <= q; i++) {
        for (int j = p; j < i; j++) {
            // cout << d[i] << " " << d[j] << " " << f[i] << " " << f[j] << endl;
            if (d[i] - d[j] <= l1) {
                f[i] = min(f[i], f[j] + c1);
            }
            else if (d[i] - d[j] <= l2) {
                f[i] = min(f[i], f[j] + c2);
            }
            else if (d[i] - d[j] <= l3) {
                f[i] = min(f[i], f[j] + c3);
            }
        }
    }
    cout << f[q];

}

F:Prime Path

F:Prime Path 查看提交统计提问 总时间限制: 1000ms 内存限制: 65536kB 描述

The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have to change the four-digit room numbers on their offices. — It is a matter of security to change such things every now and then, to keep the enemy in the dark. — But look, I have chosen my number 1033 for good reasons. I am the Prime minister, you know! — I know, so therefore your new number 8179 is also a prime. You will just have to paste four new digits over the four old ones on your office door. — No, it’s not that simple. Suppose that I change the first digit to an 8, then the number will read 8033 which is not a prime! — I see, being the prime minister you cannot stand having a non-prime number on your door even for a few seconds. — Correct! So I must invent a scheme for going from 1033 to 8179 by a path of prime numbers where only one digit is changed from one prime to the next prime.

Now, the minister of finance, who had been eavesdropping, intervened. — No unnecessary expenditure, please! I happen to know that the price of a digit is one pound. — Hmm, in that case I need a computer program to minimize the cost. You don't know some very cheap software gurus, do you? — In fact, I do. You see, there is this programming contest going on... Help the prime minister to find the cheapest prime path between any two given four-digit primes! The first digit must be nonzero, of course. Here is a solution in the case above.

1033 1733 3733 3739 3779 8779 8179 The cost of this solution is 6 pounds. Note that the digit 1 which got pasted over in step 2 can not be reused in the last step – a new 1 must be purchased.

输入 One line with a positive number: the number of test cases (at most 100). Then for each test case, one line with two numbers separated by a blank. Both numbers are four-digit primes (without leading zeros). 输出 One line for each case, either with a number stating the minimal cost or containing the word Impossible.

BFS，先打了一个 1000~9999 的素数表，然后 BFS 转移，用 st 判断有没有判断过就好了。

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

int n;


int change(int num, int i, int j) {
    string s = to_string(num);
    s[i] = j + '0';
    return stoi(s);
}

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

void find_path(unordered_set<int>& primes, int p, int q) {
    queue<pair<int, int>> queue;
    unordered_set<int> st;
    queue.push({p, 0});
    st.insert(p);
    while (queue.size()) {
        auto &[num, cnt] = queue.front();
        queue.pop();
        if (num == q) {
            cout << cnt << endl;
            return;
        }
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 10; j++) {
                int new_num = change(num, i, j);
                if (!st.count(new_num) && primes.count(new_num)) {
                    queue.push({new_num, cnt+1});
                    st.insert(new_num);
                }
            }
        }
    }
}


int main() {
    unordered_set<int> primes;
    for (int i = 1000; i < 10000; i++) if (isPrime(i)) primes.insert(i);

    cin >> n;
    while (n--) {
        int p, q;
        cin >> p >> q;
        find_path(primes, p, q);
    }
}

—— Summary

感觉其实到现在，做简单和中等题已经没啥问题了。主要就是天天出小毛病，debug 浪费很多时间。

2016 夏令营 (6/25)

最后一舞了，刷刷手感。

A: 分段函数

A:分段函数 查看提交统计提问 总时间限制: 1000ms 内存限制: 65536kB 描述 编写程序，计算下列分段函数y=f(x)的值。

y=-x+2.5; 0 ≤ x < 5

y=2-1.5(x-3)(x-3); 5 ≤ x < 10

y=x/2-1.5; 10 ≤ x < 20

输入 一个浮点数N,0 ≤ N < 20 输出 输出N对应的分段函数值：f(N)。结果保留到小数点后三位。

要是今年签到也能这么简单就好了

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

/*
y=-x+2.5; 0 <= x < 5

y=2-1.5(x-3)(x-3); 5 <= x < 10

y=x/2-1.5; 10 <= x < 20
*/

int main() {
    double n, res;
    cin >> n;
    if (n < 5) res = -n + 2.5;
    else if (n < 10) res = 2-1.5*(n-3)*(n-3);
    else res = n/2-1.5;

    cout << fixed << setprecision(3) << res;
}

B:单词翻转

B:单词翻转 查看提交统计提问 总时间限制: 1000ms 内存限制: 65536kB 描述 输入一个句子（一行），将句子中的每一个单词翻转后输出。

输入 只有一行，为一个字符串，不超过500个字符。单词之间以空格隔开。 输出 翻转每一个单词后的字符串，单词之间的空格需与原文一致。

还是签到，感觉不如 Python 快

a = str(input())

print(" ".join(i[::-1] for i in a.split(" ")))

C:反反复复

C:反反复复 查看提交统计提问 总时间限制: 1000ms 内存限制: 65536kB 描述 Mo和Larry发明了一种信息加密方法。他们首先决定好列数，然后将信息（只包含字母）从上往下依次填入各列，并在末尾补充一些随机字母使其成为一个完整的字母矩阵。例如，若信息是“There's no place like home on a snowy night”并且有5列，Mo会写成：

t o i o y h p k n n e l e a i r a h s g e c o n h s e m o t n l e w x 注意Mo只会填入字母，且全部是小写形式。在这个例子中，Mo用字母“x”填充了信息使之成为一个完整的矩阵，当然他使用任何字母都是可以的。

Mo根据这个矩阵重写信息：首先从左到右写下第一行，然后从右到左写下第二行，再从左到右写下第三行……以此左右交替地从上到下写下各行字母，形成新的字符串。这样，例子中的信息就被加密为：toioynnkpheleaigshareconhtomesnlewx。

你的工作是帮助Larry从加密后的信息中还原出原始信息（包括填充的字母）。

输入 第一行包含一个整数（范围2到20），表示使用的列数。 第二行是一个长度不超过200的字符串。 输出 一行，即原始信息。

我感觉我写的很麻烦？也用了 python

n = int(input())
s = str(input())

m = len(s) // n

res = [[0 for _ in range(n)] for _ in range(m)]

for i in range(len(s)):
    x = i // n
    y = i % n
    if x % 2 == 1:
        y = n - y - 1
    res[x][y] = s[i]

for i in range(n):
    for j in range(m):
        print(res[j][i], end='')

D:文件结构“图”

D:文件结构“图” 查看提交统计提问 总时间限制: 1000ms 内存限制: 65536kB 描述 在计算机上看到文件系统的结构通常很有用。Microsoft Windows上面的"explorer"程序就是这样的一个例子。但是在有图形界面之前，没有图形化的表示方法的，那时候最好的方式是把目录和文件的结构显示成一个"图"的样子，而且使用缩排的形式来表示目录的结构。比如：

ROOT | dir1 | file1 | file2 | file3 | dir2 | dir3 | file1 file1 file2 这个图说明：ROOT目录包括三个子目录和两个文件。第一个子目录包含3个文件，第二个子目录是空的，第三个子目录包含一个文件。

输入 你的任务是写一个程序读取一些测试数据。每组测试数据表示一个计算机的文件结构。每组测试数据以'*'结尾，而所有合理的输入数据以'#'结尾。一组测试数据包括一些文件和目录的名字（虽然在输入中我们没有给出，但是我们总假设ROOT目录是最外层的目录）。在输入中,以']'表示一个目录的内容的结束。目录名字的第一个字母是'd'，文件名字的第一个字母是'f'。文件名可能有扩展名也可能没有（比如fmyfile.dat和fmyfile）。文件和目录的名字中都不包括空格,长度都不超过30。一个目录下的子目录个数和文件个数之和不超过30。 输出 在显示一个目录中内容的时候，先显示其中的子目录（如果有的话），然后再显示文件（如果有的话）。文件要求按照名字的字母表的顺序显示（目录不用按照名字的字母表顺序显示，只需要按照目录出现的先后显示）。对每一组测试数据，我们要先输出"DATA SET x:"，这里x是测试数据的编号（从1开始）。在两组测试数据之间要输出一个空行来隔开。

你需要注意的是，我们使用一个'|'和5个空格来表示出缩排的层次。

想起了编译原理，哈哈。

一开始想用栈做，不过想了一会没想明白，继续递归了。

class Explorer:

    def __init__(self, name, l, father):
        self.father = father
        self.name = name
        self.level = l
        self.files = []
        self.dirs = []
    
    def add_file(self, file_name):
        self.files.append(file_name)
    
    def add_directory(self, direct_name):
        d = Explorer(direct_name, self.level + 1, self)
        self.dirs.append(d)
        return d
    
    def print(self):
        prefix = "|     " * self.level
        print(prefix + self.name)
        for d in self.dirs:
            d.print()
        self.files.sort()
        for f in self.files:
            print(prefix + f)


idx = 1
root = Explorer('ROOT', 0, None)
cur = root
while (tmp := input()) != '#':
    if tmp[0] == 'f': cur.add_file(tmp)
    if tmp[0] == 'd': cur = cur.add_directory(tmp)
    if tmp[0] == ']': cur = cur.father
    if tmp[0] == '*':
        print(f"DATA SET {idx}:")
        root.print()
        print()
        idx += 1
        root = Explorer('ROOT', 0, None)
        cur = root
        

F:Dungeon Master

F:Dungeon Master 查看提交统计提问 总时间限制: 1000ms 内存限制: 65536kB 描述 You are trapped in a 3D dungeon and need to find the quickest way out! The dungeon is composed of unit cubes which may or may not be filled with rock. It takes one minute to move one unit north, south, east, west, up or down. You cannot move diagonally and the maze is surrounded by solid rock on all sides.

Is an escape possible? If yes, how long will it take? 输入 The input consists of a number of dungeons. Each dungeon description starts with a line containing three integers L, R and C (all limited to 30 in size). L is the number of levels making up the dungeon. R and C are the number of rows and columns making up the plan of each level. Then there will follow L blocks of R lines each containing C characters. Each character describes one cell of the dungeon. A cell full of rock is indicated by a '#' and empty cells are represented by a '.'. Your starting position is indicated by 'S' and the exit by the letter 'E'. There's a single blank line after each level. Input is terminated by three zeroes for L, R and C. 输出 Each maze generates one line of output. If it is possible to reach the exit, print a line of the form Escaped in x minute(s).

where x is replaced by the shortest time it takes to escape. If it is not possible to escape, print the line Trapped!

三维的 BFS，没啥难度。感觉就是输入烦一点。

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int dk[6] = {0, 0, 0, 0, 1, -1};
int dx[6] = {-1, 1, 0, 0, 0, 0};
int dy[6] = {0, 0, -1, 1, 0, 0};

int main() {
    while (true) {
        int l, m, n;
        cin >> l >> m >> n; 
        if (!l && !m && !n) break;
        cin.ignore();

        vector<vector<vector<char>>> dungeons(l, vector<vector<char>>(m, vector<char>(n, '#')));
        vector<int> st = {-1, -1, -1, -1}, ed = {-2, -2, -2, -2};
        for (int k = 0; k < l; k++) {
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    char ch;
                    cin >> ch;
                    // cout << ch;
                    if (ch == 'S') st = {k, i, j, 0};
                    if (ch == 'E') ed = {k, i, j, 0}, dungeons[k][i][j] = '.';
                    if (ch == '.') dungeons[k][i][j] = ch;
                }
                cin.ignore();
            }
        }

        if (st[0] < 0 || ed[0] < 0) {
            cout << "Trapped" << endl;
            continue;
        }

        //  k, x, y, time;
        queue<vector<int>> q;
        // vector<vector<vector<bool>>> visited(l, vector<vector<bool>>(m, vector<bool>(n, false)));
        q.push(st);
        bool flag = false;
        while (!q.empty()) {
            auto node = q.front();
            q.pop();
            int k = node[0], x = node[1], y = node[2], t = node[3];
            if (k == ed[0] && x == ed[1] && y == ed[2]) {
                flag = true;
                cout << "Escaped in " << t << " minute(s)." << endl;
                break;
            }

            for (int j = 0; j < 6; j++) {
                int kk = k + dk[j];
                int xx = x + dx[j];
                int yy = y + dy[j];
                if (kk < 0 || kk >= l || xx < 0 || xx >= m || yy < 0 || yy >= n || dungeons[kk][xx][yy] == '#') continue;

                // cout << kk << " " << xx << " " << yy << endl;
                dungeons[kk][xx][yy] = '#';
                q.push({kk, xx, yy, t + 1});
            }
        }
        if(!flag) cout << "Trapped" << endl; 
    }
}

G:重建二叉树

G:重建二叉树 查看提交统计提问 总时间限制: 1000ms 内存限制: 65536kB 描述 给定一棵二叉树的前序遍历和中序遍历的结果，求其后序遍历。

输入 输入可能有多组，以EOF结束。 每组输入包含两个字符串，分别为树的前序遍历和中序遍历。每个字符串中只包含大写字母且互不重复。 输出 对于每组输入，用一行来输出它后序遍历结果。

前序 + 中序建树，后序输出树。倒是很清楚，但是 leetcode 把我惯坏了（笑）

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


struct Node {
    Node* left;
    Node* right;
    char val;
};


Node* makeTree(string& preorder, int l, int r, string& inorder, int ll, int rr, unordered_map<char, int>& h) {
    if (l > r || ll > rr) return nullptr;

    // pre: [root] [left] [right]
    // in: [left] [root] [right]

    // [D][BAC][EGF]
    // [ABC][D][EFG]

    Node* root = new Node();

    char ch = preorder[l];
    int lr = h[ch];  //  3 - 0 = 3;
    int leftl = lr - ll;
    
    root->val = ch;
    root->left = makeTree(preorder, l + 1, leftl + l, inorder, ll, lr - 1, h);
    root->right = makeTree(preorder, l + 1 + leftl, r, inorder, lr + 1, rr, h);
    return root;
}

void postOrder(Node* root) {
    if (!root) return;
    postOrder(root->left);
    postOrder(root->right);
    cout << root->val;
}


int main() {
    string tmp;
    while (getline(cin, tmp, '\n')) {
        istringstream ss(tmp);
        string preorder, inorder;
        getline(ss, preorder, ' ');
        getline(ss, inorder);

        unordered_map<char, int> h;
        for (int i = 0; i < inorder.size(); i++) {
            h[inorder[i]] = i;
        }

        Node *root = makeTree(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1, h);
        
        postOrder(root);
        cout << endl;
    }
}

H:丛林中的路

H:丛林中的路 查看提交统计提问 总时间限制: 1000ms 内存限制: 65536kB 描述

热带岛屿Lagrishan的首领现在面临一个问题：几年前，一批外援资金被用于维护村落之间的道路，但日益繁茂的丛林无情的侵蚀着村民的道路，导致道路维修开销巨大，长老会不得不放弃部分道路的维护。上图左侧图显示的是正在使用道路的简图以及每条路每个月的维修费用（单位为aacms）。现在长老会需要提出一种方案，即需要保证村落之间都可以互相到达，又要将每个月的道路维修费用控制在最小。村子编号为从A到I。上图右侧显示的方案最小维修开销为216 aacms每月。

输入 输入包含1~100个数据集，最后一行为0.每个数据集第一行为村落数目n, 1 < n < 27,依次用字母表的前n个字母标记。接下来有n-1行，每行的第一个数据便是按字母顺序排列的村子编号（不包括最后一个村庄）。每个村庄后面的数据k代表该村庄通往编号在其之后的村庄的道路数目，如A 2 B 12 I 25，代表A村庄有2个编号在A之后的村庄和其相连。若k大于0，k后面会依次给出这k个村庄的编号以及各自到起始村庄的道路维修费用，如A 2 B 12 I 25，代表A和B之间道路维修费用为12， A和I之间道路维修费用为25（维修费用为不超过100的正整数）.路的总数目不超过75条，每个村庄到其他村庄不会有超过15条路（包括编号在其之前和之后的）。 输出 每个数据集有一个输出：针对解决方案每个月维修道路的小费用。 提示：蛮力算法虽能找出解决方案，但将会超出时间限制。

MST，点就 27 个，用 Prim 快。

一样的，读入恶心。

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

typedef pair<int, int> PII;

int main() {
    int n;
    while (cin >> n) {
        
        // cout << n << endl;
        if (!n) break;
        vector<vector<PII>> g(n + 1);
        for (int i = 1; i < n; i++) {
            char ch;
            int idx;
            cin >> ch >> idx;
            // cout << ch << " " << idx << endl;
            while (idx--) {
                char to;
                int weight;
                cin >> to >> weight;
                g[ch-'A'].push_back({to-'A', weight});
                g[to-'A'].push_back({ch-'A', weight});
            }
        }

        vector<int> dist(n + 1, 0x3f3f3f3f);
        vector<bool> st(n + 1, false);
        priority_queue<PII, vector<PII>, greater<PII>> q;
        long long res = 0;
        dist[0] = 0;
        q.push({0, 0});
        while (!q.empty()) {
            int d = q.top().first;
            int u = q.top().second;
            q.pop();

            if (st[u]) continue;
            st[u] = true;
            res += d;

            for (auto& e : g[u]) {
                int to = e.first;
                int weight = e.second;
                if (!st[to] && dist[to] > weight) {
                    dist[to] = weight;
                    q.push({weight, to});
                }
            }
        }

        cout << res << endl;
    }

    return 0;
    
}

—— Summary

两个小时做了 6 题，如果明天能做出这个水平我晚上都要笑醒。

但是显然这次的题很简单，毕竟是 8 年前了。

其实刷了这么多，来来回回就那么几个。BFS、DFS、最短路和生成树几乎年年都有。至于 DP，额，感觉好像大部分时候都被我放了。

Anyway，明天在复习一下这几个算法也就去机考了，希望不要爆零。