第一题
一位冒险者进入了一个迷宫中寻宝。他手上已经拥有了一份这个迷宫的地图，其中标注了迷宫的完整结构以及迷宫中每个宝箱所在的位置。
迷宫的地图是一个由m*n个格子组成的平面图，纵向的上下方向上每列有m个格子，横向的左右方向上每行有n个格子，其中每个格子为不能进入的障碍格或可以进入的通行格。如果有两个上下相邻或左右相邻的通行格，则可以从其中一个通行格走到另一个通行格。每个宝箱放置在不同的通行格中。
他的目标是收集到这个迷宫里的所有宝箱，因此他给自己在这个迷宫中寻宝制定了如下策略：
-
计算出离他当前位置曼哈顿距离最小的未收集宝箱，如果有多个就选定最小编号那个，记为k号宝箱；
-
如果他当前位置无法到达k号宝箱，则收集失败，流程结束；否则，计算出他当前位置到k号宝箱的最短路径长度，并且按上下左右的次序依次计算出如果向这个方向走一格通行格之后，到k号宝箱的最短路径长度是否有缩短，如果有缩短则往这个方向走一格；
-
如果他当前所在位置有未收集宝箱，就收集这个宝箱。如果所有宝箱已经被收集，则收集完成。否则回到第1步并重复执行。
其中迷宫中两个位置的曼哈顿距离，是指这两个位置在上下方向的行差，加上左右方向的列差。如果用公式表示，如果两个位置分别为(x, y)和(u, v)，则这两个位置的曼哈顿距离为|x-u|+|y-v|。
两个位置间的一条路径，是指从其中一个位置开始，通过若干个相邻通行格，走到另一个位置，其中经过的通行格顺序。两个位置的最短路径，是指这两个位置的所有路径中，通过的通行格数量最少的路径。两个位置的最短路径长度，是指沿这两个位置的最短路径走的格数。
问在这种策略下收集所有宝箱，他需要走多少格？
点击查看代码
#include<iostream>
#include<string.h>
#include<vector>
#include<queue>
#include<math.h>
using namespace std;
#define nullptr NULL
struct Pos
{
int x = 0, y = 0, d = 0;
Pos& set(int _x, int _y, int _d = 0)
{
x = _x;
y = _y;
d = _d;
return *this;
}
}node[10];
// 宝箱到每个点的最小距离
int ***dp = nullptr;
char map[50][50];
bool vis[50][50];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
void InitDp(int boxn, int x, int y)
{
if(dp != nullptr)
delete[] dp;
dp = new int**[x];
for(int i = 0; i < x; ++i)
dp[i] = new int*[y];
for(int i = 0; i < x; ++i)
{
for(int j = 0; j < y; ++j)
{
dp[i][j] = new int[boxn];
memset(dp[i][j], 0, sizeof(int) * boxn);
}
}
}
// 计算宝箱与每个点的最小距离
void Bfs(int no, Pos pos, const Pos& s)
{
memset(vis, 0, sizeof(vis));
queue<Pos> tmp;
tmp.push(pos);
vis[pos.x][pos.y] = true;
int nx, ny;
while(!tmp.empty())
{
Pos &pos = tmp.front();
tmp.pop();
for(int i = 0; i < 4; ++i)
{
nx = pos.x + dx[i];
ny = pos.y + dy[i];
if(nx >= 0 && nx < s.x && ny >= 0 && ny < s.y && !vis[nx][ny] && map[nx][ny] != '#')
{
vis[nx][ny] = true;
dp[nx][ny][no] = pos.d + 1;
tmp.push(Pos().set(nx,ny,pos.d+1));
}
}
}
/*for(int i = 0; i < s.x; ++i)
{
for(int j = 0; j < s.y; ++j)
cout << dp[i][j][no] << ends;
cout << endl;
}
cout << endl;*/
}
int CheackSearch(Pos& per, int d, const Pos& s, const int& boxn)
{
memset(vis, 0, sizeof(vis));
queue<Pos> tmp;
tmp.push(per);
vis[per.x][per.y] = true;
int srh = 0;
int nx, ny;
while(!tmp.empty())
{
Pos &pos = tmp.front();
tmp.pop();
if(isalnum(map[pos.x][pos.y]))
{
if(node[map[pos.x][pos.y] - '0'].d == 0)
{
memset(vis, 0, sizeof(vis));
// 宝箱i被收集
node[map[pos.x][pos.y] - '0'].d = 1;
vis[pos.x][pos.y] = true;
++srh;
}
}
if(srh == boxn)
return pos.d;
int no;
int maxMhd = 10000;
// 查找与当前位置曼哈顿距离最小的宝箱
for(int i = 0; i < boxn; ++i)
{
int m = abs(pos.x - node[i].x) + abs(pos.y - node[i].y);
if(node[i].d != 1 && m < maxMhd)
{
maxMhd = m;
no = i;
}
}
for(int i = 0; i < 4; ++i)
{
nx = pos.x + dx[i];
ny = pos.y + dy[i];
if(nx >= 0 && nx < s.x && ny >= 0 && ny < s.y)
{
if(!vis[nx][ny]
&& map[nx][ny] != '#'
&& dp[nx][ny][no] < dp[pos.x][pos.y][no]) // 判断下一步走的最小点是否为必当前最小路径更小
{
vis[nx][ny] = true;
tmp.push(Pos().set(nx, ny, pos.d+1));
}
}
}
}
return -1;
}
int main()
{
int n, boxcnt;
Pos per, size;
cin >> n;
while(n--)
{
boxcnt = 0;
scanf("%d %d\n", &size.x, &size.y);
// 初始化本轮map
memset(map, 0, sizeof(map));
for(int i = 0; i < size.x; ++i)
{
for(int j = 0; j < size.y; ++j)
{
cin >> map[i][j];
if(map[i][j] == '*')
per.set(i, j);
else if(isalnum(map[i][j]))
{
node[map[i][j] - '0'].set(i, j);
++boxcnt;
}
}
}
InitDp(boxcnt, size.x, size.y);
for(int i = 0; i < boxcnt; ++i)
Bfs(i, node[i], size);
int ans = CheackSearch(per, 0, size, boxcnt);
cout << ans << endl;
}
delete[] dp;
return 0;
}
第二题
游戏工程师小明购买了VR设备之后爱上了体感游戏，而最近他把他的业余时间花在了一款叫十字斩的游戏里。当你戴上VR眼镜启动游戏后，先选择一首音乐，然后会发现有一个NN的方阵呈现在你的眼前，方阵的每个格子上都有一个数字。然后伴随着音乐节拍，你需要按照时机对方阵进行一次十字斩击（同时斩掉一行和一列，而且选好了行列后不能斩到选定行列之外的格子）。斩击完了之后，矩阵会收缩成一个（N-1）（N-1）的方阵。
特别的，若该次十字斩斩到的格子数字和是本次所有十字可能里最大的，则会获得一个Perfect，如果N次十字斩都是Perfect，则可以获得FullCombo的成就。但小明的心算能力不行，至今还未能获得FullCombo的成就。所幸初始数字方阵与音乐是一一对应的，所以小明可以通过预先计算十字斩的位置然后背下来，游玩的时候根据记忆去进行十字斩位置的选择即可。
小明上了一天班已经不想写代码了，所以他拜托你来写一个程序为他计算出十字斩的方案。
点击查看代码
#include<iostream>
#include<string.h>
using namespace std;
int main()
{
int n;
cin >> n;
unsigned int **p = new unsigned int*[n];
unsigned int *rowSum = new unsigned int[n];
unsigned int *colSum = new unsigned int[n];
memset(rowSum, 0, n * sizeof(unsigned int));
memset(colSum, 0, n * sizeof(unsigned int));
for(int i = 0; i < n; ++i)
p[i] = new unsigned int[n];
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < n; ++j)
{
cin >> p[i][j];
rowSum[i] += p[i][j];
colSum[j] += p[i][j];
}
}
bool *cutRow = new bool[n];
bool *cutCol = new bool[n];
memset(cutRow, 0, n * sizeof(bool));
memset(cutCol, 0, n * sizeof(bool));
for(int k = 0; k < n; k++)
{
int mx = 0, my = 0, max = 0;
for(int i = 0; i < n; ++i)
{
if(cutRow[i])
continue;
for(int j = 0; j < n; ++j)
{
if(cutCol[j])
continue;
int tmp = rowSum[i] + colSum[j] - p[i][j];
if(tmp > max)
{
max = tmp;
mx = i;
my = j;
}
}
}
int ax = 0, ay = 0;
for(int i = 0; i < n; ++i)
{
if(!cutCol[i])
{
colSum[i] -= p[mx][i];
if(i < my) ay++;
}
if(!cutRow[i])
{
rowSum[i] -= p[i][my];
if(i < mx) ax++;
}
}
cutRow[mx] = cutCol[my] = true;
rowSum[mx] = colSum[my] = 0;
printf("%d %d\n", ax + 1, ay + 1);
}
delete[] cutRow;
delete[] cutCol;
}
第三题
七星不靠是中国麻将竞赛规则的番种，胡牌时由东南西北中发白7张，外加其他花色的147、258、369不相连的牌型，且没有将牌而组成。
--百度百科
七星不靠中的七星是指：东西南北中发白，也就是牌中必须有这七张。而其它牌按下述的来拼全：
东西南北中发白+147万+258饼+369条
东西南北中发白+147万+258条+369饼
东西南北中发白+147条+258万+369饼
东西南北中发白+147条+258饼+369万
东西南北中发白+147饼+258条+369万
东西南北中发白+147饼+258万+369条
由于胡牌时只需要14张牌，而上述组合均有16张，那么除了东西南北中发白必须有外，其它三色可以随便去掉两张，都可以组成七星不靠。
我们的任务是，假设我们的14张牌中已经包含了东西南北中发白这7张牌，另外的牌都是万饼条的序数牌，给出另外的这7张牌，判断是否能组成七星不靠。
点击查看代码
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int main()
{
int n;
cin >> n;
const char *ans = "YES";
//FILE* fp;
//fopen_s(&fp, "1.h", "w");
while (n--)
{
char pai[10] = { 0 };
short tmp = 0, t, b, w;
t = b = w = 0;
for (int i = 0; i < 7; i++)
{
int c;
char a;
scanf("%d%c", &c, &a);
pai[c] = a;
switch (a)
{
case 'W': w++;break;
case 'B': b++;break;
case 'T': t++;break;
}
}
for (int i = 1; i < 10; ++i)
{
if (pai[i] != 0 && pai[i] == pai[i - 1])
ans = "NO";
if (pai[i] != 0)
tmp++;
}
if (tmp < 7 || w > 3 || b > 3 || t > 3)
ans = "NO";
std::cout << ans << endl;
//fwrite(ans, strlen(ans), 1, fp);
//fwrite("\n", 1, 1, fp);
ans = "YES";
}
system("pause");
}
第四题
明明最近迷上了《明日之后》这款游戏。在这款游戏中有一个配方制造系统，玩家可以利用手中的资源和材料，来制造武器和道具。例如，玩家如果需要制造一个小木柜，需要3块木板，而制造一块木板，又需要120个木头和2个小树枝，并且需要走到建筑加工台前制作。而采集木头和小树枝又需要一定的时间。
玩了一段时间之后，明明开始好奇在游戏中做什么最花时间。虽然游戏中已经有标明每个物品的制造时间，但是明明更想通过自己的游戏经历来统计实际需要的时间。明明根据自己的操作，记录下了自己游戏中每个操作事件的开始和结束时间，按时间顺序汇总成了一张表，如下所示：
从上表可以看出，“制造1个小木柜”这个操作，总共用时2000-1=1999秒时间，其中包含两部分：制造3块木板的耗时（1000-5=995秒）和自身的耗时（1999-995=1004秒）。同样的，制造3块木板的995秒耗时中，也包括3部分：收集360个木头的耗时（20-10=10秒）、收集6个小树枝的耗时（40-25=15秒）以及自身耗时（995-10-15=970秒）。在这些操作当中，“制造1个小木柜”自身耗时1004秒，是所有操作中自身耗时最多的一个操作。
明明想知道自己做的这些操作中，哪个操作自身所花的时间是最多的。给出这张事件记录表，你可以帮明明计算一下吗？
点击查看代码
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
struct Data
{
unsigned int time;
unsigned int id;
};
int main()
{
int n;
cin >> n;
while(n--)
{
int cnt;
cin >> cnt;
stack<Data> data;
vector<Data> dataFin;
for(int i = 0; i < cnt; ++i)
{
Data t;
int flag;
scanf("%d %d %d", &t.time, &t.id, &flag);
//cin >> t.time >> t.id >> flag;
if(flag == 0)
data.push(t);
else
{
unsigned int tweenTime = 0;
while(data.top().id != t.id)
{
Data &tmp = data.top();
tweenTime += tmp.time;
data.pop();
}
Data tmp = data.top();
data.pop();
tmp.time = t.time - tmp.time;
data.push(tmp);
tmp.time -= tweenTime;
dataFin.push_back(tmp);
}
}
unsigned int max = 0;
for(int i = 1; i < dataFin.size(); ++i)
{
if(dataFin[i].time > dataFin[max].time || dataFin[i].time == dataFin[max].time && dataFin[i].id < dataFin[max].id)
max = i;
}
cout << dataFin[max].id << endl;
}
}