Though life is hard, I want it to be boiling.
L2-2:懂蛇语
在《一年一度喜剧大赛》第二季中有一部作品叫《警察和我之蛇我其谁》，其中“毒蛇帮”内部用了一种加密语言，称为“蛇语”。蛇语的规则是，在说一句话 A 时，首先提取 A 的每个字的首字母，然后把整句话替换为另一句话 B，B 中每个字的首字母与 A 中提取出的字母依次相同。例如二当家说“九点下班哈”，对应首字母缩写是 JDXBH，他们解释为实际想说的是“京东新百货”……
本题就请你写一个蛇语的自动翻译工具，将输入的蛇语转换为实际要表达的句子。
输入格式：
输入第一行给出一个正整数 N（≤105），为蛇语词典中句子的个数。随后 N 行，每行用汉语拼音给出一句话。每句话由小写英文字母和空格组成，每个字的拼音由不超过 6 个小写英文字母组成，两个字的拼音之间用空格分隔。题目保证每句话总长度不超过 50 个字符，用回车结尾。注意：回车不算句中字符。
随后在一行中给出一个正整数 M（≤103），为查询次数。后面跟 M 行，每行用汉语拼音给出需要查询的一句话，格式同上。
输出格式：
对每一句查询，在一行中输出其对应的句子。如果句子不唯一，则按整句的字母序输出，句子间用 | 分隔。如果查不到，则将输入的句子原样输出。
注意：输出句子时，必须保持句中所有字符不变，包括空格。
输入样例：
8
yong yuan de shen
yong yuan de she
jing dong xin bai huo
she yu wo ye hui shuo yi dian dian
liang wei bu yao chong dong
yi dian dian
ni hui shuo she yu a
yong yuan de sha
7
jiu dian xia ban ha
shao ye wu ya he shui you dian duo
liu wan bu yao ci dao
ni hai shi su yan a
yao diao deng
sha ye ting bu jian
y y d s
输出样例：
jing dong xin bai huo
she yu wo ye hui shuo yi dian dian
liang wei bu yao chong dong
ni hui shuo she yu a
yi dian dian
sha ye ting bu jian
yong yuan de sha|yong yuan de she|yong yuan de shen
思路
思路一：大模拟类型题目，思路很简单，就是准备两个数组，第一个数组存放的是缩写之后的，第二个存放的是所写前的。紧接着需要转换的蛇语简化看看前面的数组中是否存在相同的，如果存在相同的，则需要以
|为界输出多条对应的蛇语。这样会超时，18/25。 思路二：。。。
代码
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
string a[N], b[N];
int main()
{
int n, m, k = 0;
cin >> n;
string kkk;
getline(cin, kkk);
for (int i = 1; i <= n;i ++) {
string s;
getline(cin, s);
// cout << s << '\n';
b[i] = s;
string ss;
for (int j = 0; j < s.length(); j++) {
if (s[j] != ' ') ss += s[j];
else {
if (ss != "") a[i] += ss[0];
// cout << a[i] << '\n';
ss = "";
}
}
if (ss != "") a[i] += ss[0];
// cout << a[i] << '\n';
}
cin >> m;
getline(cin, kkk);
while (m--) {
string s;
getline(cin, s);
string ss, sss;
string c[N];
for (int i = 0; i < s.length(); i++) {
if (s[i] != ' ') ss += s[i];
else {
if (ss != "") sss += ss[0];
ss = "";
}
}
if (ss != "") sss += ss[0];
bool flag = false;
int k = 1;
for (int i = 1; i <= n; i++) {
if (sss == a[i]) {
flag = true;
// cout << b[i] << '\n';
c[k++] = b[i];
}
}
if(!flag) cout << s << '\n';
else {
sort(c + 1, c + k);
cout << c[1];
for (int i = 2; i < k; i++) cout << "|" << c[i];
puts("");
}
}
return 0;
}
L2-3：满树的遍历
一棵“k 阶满树”是指树中所有非叶结点的度都是 k 的树。给定一棵树，你需要判断其是否为 k 阶满树，并输出其前序遍历序列。
注：树中结点的度是其拥有的子树的个数，而树的度是树内各结点的度的最大值。
输入格式：
输入首先在第一行给出一个正整数 n（≤105），是树中结点的个数。于是设所有结点从 1 到 n 编号。
随后 n 行，第 i 行（1≤i≤n）给出第 i 个结点的父结点编号。根结点没有父结点，则对应的父结点编号为 0。题目保证给出的是一棵合法多叉树，只有唯一根结点。
输出格式：
首先在一行中输出该树的度。如果输入的树是 k 阶满树，则加 1 个空格后输出 yes，否则输出 no。最后在第二行输出该树的前序遍历序列，数字间以 1 个空格分隔，行首尾不得有多余空格。
注意：兄弟结点按编号升序访问。
输入样例 1：
7
6
5
5
6
6
0
5
L2-3：满树的遍历
一棵“k 阶满树”是指树中所有非叶结点的度都是 k 的树。给定一棵树，你需要判断其是否为 k 阶满树，并输出其前序遍历序列。
注：树中结点的度是其拥有的子树的个数，而树的度是树内各结点的度的最大值。输出样例 1：
3 yes
6 1 4 5 2 3 7
输入样例 2：
7
6
5
5
6
6
0
4
输出样例 2：
3 no
6 1 4 7 5 2 3
代码长度限制
思路
一道经典的树的题目，使用vector来构造一颗树，随后我们就看看每个非叶子节点的度是否相同，随后先输出树的度（也就是所有节点度的最大值），然后如果所有非叶子节点的度相同，则输出
yes，反之则输出no，最后再前序遍历一下这颗树就ok了。这里需要注意下这里的空格细节处理。否则会报一堆的格式错误。
代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
int n;
bool st[N];
vector<int> A[N];
bool flag;
string s;
void dfs(int k) {
if (st[k]) return;
st[k] = true;
s += " " + to_string(k);
for (auto kk : A[k]) {
if (!st[kk]) {
dfs(kk);
}
}
}
int main()
{
int n;
cin >> n;
int kk = 0;
for (int i = 1; i <= n; i++) {
int k;
cin >> k;
if (k) A[k].push_back(i);
else kk = i;
}
for (int i = 1; i <= n; i++) {
sort(A[i].begin(), A[i].end());
}
int ans = 0;
for (int i = 1; i <= n; i++) {
int res = A[i].size();
if (res != 0) {
if (ans == 0) ans = res;
else if (ans != res) {
flag = true;
ans = max(ans, res);
}
}
}
cout << ans << " ";
if (flag) cout << "no\n";
else cout << "yes\n";
dfs(kk);
cout << s.substr(1);
return 0;
}
L2-4：吉利矩阵
所有元素为非负整数，且各行各列的元素和都等于 7 的 3×3 方阵称为“吉利矩阵”，因为这样的矩阵一共有 666 种。
本题就请你统计一下，把 7 换成任何一个 [2,9] 区间内的正整数 L，把矩阵阶数换成任何一个 [2,4] 区间内的正整数 N，满足条件“所有元素为非负整数，且各行各列的元素和都等于 L”的 N×N 方阵一共有多少种？
输入格式：
输入在一行中给出 2 个正整数 L 和 N，意义如题面所述。数字间以空格分隔。
输出格式：
在一行中输出满足题目要求条件的方阵的个数。
输入样例：
7 3
输出样例：
666
思路
思路：这里我们就是最基本的DFS的思路，但是这里我们直接死遍历可能会超时，所以我们这里需要进行剪枝操作。具体请看下面代码。
代码（over）
#include <iostream>
using namespace std;
int l,n,row[10],col[10],ans;
void dfs(int x){
if(x == n * n){
for(int i=0;i<n;i++){
if(row[i]!=l) return;
if(col[i]!=l) return;
}
ans++;
return;
}
for(int i=0;i<=l;i++){//能填的数最小是0，最大是l
//剪枝1：当前行或列值超过l
if(row[x / n] + i > l || col[x % n] + i > l) break;
row[x / n] += i;//对应行和更新
col[x % n] += i;//对应列和更新
//剪枝2：加上其他没有填的数（取最大）能达到l
if(row[x / n] + l * (n - 1 - x % n) >= l && col[x % n] + l * (n - 1 - x / n)>=l)
bfs(x + 1);
row[x / n]-=i;//还原现场
col[x % n]-=i;
}
}
int main(){
cin >> l >> n;
dfs(0);
cout << ans;
return 0;
}
L3-1：夺宝大赛
夺宝大赛的地图是一个由 n×m 个方格子组成的长方形，主办方在地图上标明了所有障碍、以及大本营宝藏的位置。参赛的队伍一开始被随机投放在地图的各个方格里，同时开始向大本营进发。所有参赛队从一个方格移动到另一个无障碍的相邻方格（“相邻”是指两个方格有一条公共边）所花的时间都是 1 个单位时间。但当有多支队伍同时进入大本营时，必将发生火拼，造成参与火拼的所有队伍无法继续比赛。大赛规定：最先到达大本营并能活着夺宝的队伍获得胜利。
假设所有队伍都将以最快速度冲向大本营，请你判断哪个队伍将获得最后的胜利。
输入格式：
输入首先在第一行给出两个正整数 m 和 n（2<m,n≤100），随后 m 行，每行给出 n 个数字，表示地图上对应方格的状态：1 表示方格可通过；0 表示该方格有障碍物，不可通行；2 表示该方格是大本营。题目保证只有 1 个大本营。
接下来是参赛队伍信息。首先在一行中给出正整数 k（0<k<m×n/2），随后 k 行，第 i（1≤i≤k）行给出编号为 i 的参赛队的初始落脚点的坐标，格式为 x y。这里规定地图左上角坐标为 1 1，右下角坐标为 n m，其中 n 为列数，m 为行数。注意参赛队只能在地图范围内移动，不得走出地图。题目保证没有参赛队一开始就落在有障碍的方格里。
输出格式：
在一行中输出获胜的队伍编号和其到达大本营所用的单位时间数量，数字间以 1 个空格分隔，行首尾不得有多余空格。若没有队伍能获胜，则在一行中输出 No winner.
输入样例 1：
5 7
1 1 1 1 1 0 1
1 1 1 1 1 0 0
1 1 0 2 1 1 1
1 1 0 0 1 1 1
1 1 1 1 1 1 1
7
1 5
7 1
1 1
5 5
3 1
3 5
1 4
输出样例 1：
7 6
样例 1 说明：
七支队伍到达大本营的时间顺次为：7、不可能、5、3、3、5、6，其中队伍 4 和 5 火拼了，队伍 3 和 6 火拼了，队伍 7 比队伍 1 早到，所以获胜。
输入样例 2：
5 7
1 1 1 1 1 0 1
1 1 1 1 1 0 0
1 1 0 2 1 1 1
1 1 0 0 1 1 1
1 1 1 1 1 1 1
7
7 5
1 3
7 1
1 1
5 5
3 1
3 5
输出样例 2：
No winner.
思路（多源BFS）
思路一：就是每给一个起点就走一次，搜索一次记录到达目的地的最短距离，同时记录一下每只队伍到达大本营的最短距离和对应的队伍编号，最后只需要排个序然后根据题目的意思判断一下即可得出答案来。但是这样的写法会超时，18/30.
思路二：其实就是稍微优化一点点，我们可以选择从终点出发，算出终点到各个位置的最小距离，最后我们在枚举起点的时候直接赋值即可。这样就可以AC了。
代码一
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
const int N = 110;
int n, m;
int a[N][N];
pair<int, int> p[N];
int xx, yy;
int vis[N][N];
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
bool cmp(pair<int, int> A,pair<int, int> B){
return A.first < B.first;
}
int dfs(int x,int y){
memset(vis, -1, sizeof vis);
queue<pair<int, int>> q;
vis[x][y] = 0;
q.push({x, y});
while (q.size()){
auto t = q.front();
q.pop();
int x1 = t.first;
int y1 = t.second;
// cout << x1 << " " << y1 << '\n'
if (x1 == xx && y1 == yy) {
return vis[xx][yy];
}
for (int i = 0; i < 4; i++) {
int x2 = x1 + dx[i], y2 = y1 + dy[i];
if (x2 >= 1 && x2 <= m && y2 >= 1 && y2 <= n && vis[x2][y2] == -1 && a[x2][y2] == 1) {
vis[x2][y2] = vis[x1][y1] + 1;
q.push({x2, y2});
}
// cout << x2 << " " << y2 << '\n';
}
}
return vis[xx][yy];
}
int main()
{
cin >> m >> n;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
if (a[i][j] == 2) {
xx = i;
yy = j;
a[i][j] = 1;
}
}
}
int k;
cin >> k;
for (int i = 1; i <= k; i++){
int x, y;
cin >> x >> y;
p[i].first = dfs(y, x);
p[i].second = i;
}
sort (p + 1, p + k + 1, cmp);
// for (int i = 1; i < k; i++){
// cout << p[i].first << " " << p[i].second << '\n';
// }
bool flag = false;
for (int i = 1; i < k; i++){
int x = p[i].first, y = p[i].second;
if (x == p[i + 1].first || (x == p[i - 1].first && i != 1) || x == -1) continue;
else {
cout << y << " " << x;
return 0;
}
}
cout << "no winner";
return 0;
}
代码二（优化）
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
const int N = 210, M = 4010;
int n, m;
int a[N][N];
pair<int, int> p[M];
int xx, yy;
int vis[N][N];
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
bool cmp(pair<int, int> A,pair<int, int> B){
return A.first < B.first;
}
void bfs(int x,int y){
memset(vis, -1, sizeof vis);
queue<pair<int, int>> q;
vis[x][y] = 0;
q.push({x, y});
while (q.size()){
auto t = q.front();
q.pop();
int x1 = t.first;
int y1 = t.second;
// cout << x1 << " " << y1 << '\n'
for (int i = 0; i < 4; i++) {
int x2 = x1 + dx[i], y2 = y1 + dy[i];
if (x2 >= 1 && x2 <= m && y2 >= 1 && y2 <= n && vis[x2][y2] == -1 && a[x2][y2] == 1) {
vis[x2][y2] = vis[x1][y1] + 1;
q.push({x2, y2});
}
// cout << x2 << " " << y2 << '\n';
}
}
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin >> m >> n;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
if (a[i][j] == 2) {
xx = i;
yy = j;
a[i][j] = 1;
}
}
}
bfs(xx, yy);
int k;
cin >> k;
for (int i = 1; i <= k; i++){
int x, y;
cin >> x >> y;
p[i].first = vis[y][x];
p[i].second = i;
}
sort (p + 1, p + k + 1, cmp);
// for (int i = 1; i < k; i++){
// cout << p[i].first << " " << p[i].second << '\n';
// }
bool flag = false;
for (int i = 1; i < k; i++){
int x = p[i].first, y = p[i].second;
if (x == p[i + 1].first || (x == p[i - 1].first && i != 1) || x == -1) continue;
else {
cout << y << " " << x;
return 0;
}
}
cout << "No winner.\n";
return 0;
}
