锐客网

  1. 首页 > it技术 > >

第八届Nuist程序设计大赛 题解

第八届Nuist程序设计大赛 A: 当然是选择AC它了! 题目描述:

听闻第八届程序设计大赛马上就要开始了, 已经报名的童鞋们都纷纷去OJ刷题。
但你的女朋友(tan90°)想知道她写的”A+B问题”是否可以一次AC(Accepted),
所以她请你来写一个程序帮她判断她的程序的输入输出是否正确。
(题外话: 如果你AC此题,你的女朋友会托付我们交给你一个惊喜,所以一定要AC它哟!)
输入描述:
有多组测试数据,对于每组测试数据,第一行有一个整数n,代表该组测试数据共有 n个表达式需要判断,接下来的n行每行一个A+B=C的表达式(0 =< A,B,C <= 50000)

输出描述:
对于每组测试数据,如果n个表达式全都正确,输出Accepted,反之,如果有至少一个 表达式错误,输出Wrong Answer

样例输入:
1 1+1=2 2 1+1=2 1+1=3

样例输出:
Accepted Wrong Answer

题解
比较简单，用scanf按照特定格式输入就可以了
#include int main() { int n, a, b, c, flag; char str[1000]; while(scanf("%d", &n) != EOF) { flag = 1; while(n--){ scanf("%d+%d=%d", &a, &b, &c); if(a + b != c) flag = 0; } if(flag) printf("Accepted\n"); else printf("Wrong Answer\n"); } return 0; }

B: guguguagua? 题目描述
正在赛场上做题的你突然听到了奇怪的声音,”咕咕呱呱呱……”,
聪明的你大胆猜测这是咕呱星人传来的信息,你还一口咬定咕呱星人
使用二进制进行交流,咕(gu)代表1,呱(gua)代表0。你把这件事
告诉了你的朋友,可你不懂二进制的朋友认为你失了智……
为了证明你是对的,你需要把”gu”、”gua”组成的序列写一个程序
转化成十进制的形式。
输入描述:
有多组测试数据, 每组输入一行只由 gu、gua 组成的字符串序列 每行长度不超过100个字符。

输出描述:
对于每组测试数据,输出其对应的十进制数

样例输入:
guguguaguagua gu

样例输出:
24 1

题解
把gu和gua对应成1, 0,然后转成十进制即可。
#include #include int main() { char str[50]; while(scanf("%s", str) != EOF) { int ans = 0; int a[50]={0}; int len = strlen(str); for(int i = 0; i < len; i++) { if (str[i] == 'a') { a[i-2] = 1; } } for(int i = 0; i < len; ) { if (a[i] == 0) { ans = ans*2 + 1; i = i + 2; } else { ans = ans * 2; i = i + 3; } } printf("%d\n", ans); } return 0; }

C: 买戒指 题目描述
你和你的女朋友(tan90°)去买戒指，店里有好多戒指，编号为1,2,3…，戒指上的钻石大小各不相同。你们从一堆戒指中随机抽取两枚并比较它们钻石的大小。在比较m次之后，你们看中了两枚戒指a和b。现在请你根据之前比较的信息判断这两枚戒指哪一枚的钻石更大。
输入
多组输入 每组第一行三个整数，a,b,m(1<= a, b, c <= 1000) a和b是最终要比较的两枚戒指，m表示比较的次数 接下来m行，每行两个整数u, v，表示第u个戒指的钻石比第v个大

输出
如果戒指a的钻石比b大，则输出1 如果戒指a的钻石比b小，则输出-1 如果根据现有信息，戒指a和b无法比较，则输出0

样例输入
2 3 4 1 2 2 4 1 3 4 3

样例输出
1

题解
本题改编自网易笔试题
简单拓扑序的应用，两次深搜即可。从u深搜，如果能搜到v则说明u>v, 如果能从v搜到u则说明v>u, 如果各自都搜索不到对方，则u和v根据现有的拓扑信息无法比较
#include #include #include #define MAXN 1000 using namespace std; vector adj[MAXN]; int x, y, m; bool vis[MAXN]; int dfs(int s, int aim) { if (s == aim) return 1; int len = adj[s].size(); for (int i = 0; i < len; i++) { int v = adj[s][i]; if (!vis[v]) { vis[v] = true; int ans = dfs(v, aim); if (ans) return ans; } } return 0; }int main() { while (cin >> x >> y >> m) { for (int i = 0; i < MAXN; i++) { adj[i].clear(); } for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; adj[a].push_back(b); } memset(vis, false, sizeof(vis)); vis[x] = true; if (dfs(x, y)) { cout << 1 << endl; } else { memset(vis, false, sizeof(vis)); vis[y] = true; if (dfs(y, x)) cout << -1 << endl; else { cout << 0 << endl; } } } return 0; }

D: 最长回文长度 题目描述
回文字符串就是从前往后读和从后往前读都一样的字符串，比如abcba, aaa, QoQ。现在给你一个字符串，你可以从中删去一些字符，在不改变原来字符相对顺序的情况下，得到一个最长的回文字符串。
比如abxdba, 删去字符x后，可以得到abdba，是一个回文字符串。你的任务就是求出给定的字符串删去若干字符后可以得到的最长的回文字符串的长度。字符串长度不超过1000,字符范围为 ‘a’ 到 ‘z’。
输入
多组输入 每组一行字符串

输出
每组测试数据输出一个整数，表示可以得到的最长的回文字符串的长度

样例输出
aabbaabb computer abzla samhita

样例输入
6 1 3 3

题解
本题来源： 腾讯笔试题

解法一：
动态规划，令dp[i][j]为str[i...j]的最长回文子序列的长度。如果 str[i]=str[j]，则 dp[i][j]=dp[i+1][j?1]+2 ,否则 dp[i][j]=max(dp[i+1][j],dp[i][j?1])
#include #include #define MAXN 1010 using namespace std; char str[MAXN]; int dp[MAXN][MAXN]; int main() { while (cin >> str) { memset(dp, 0, sizeof(dp)); int len = strlen(str); for (int i = 0; i < len; i++) dp[i][i] = 1; for (int i = 0; i < len-1; i++) { if (str[i] == str[i+1]) { dp[i][i+1] = 2; } else { dp[i][i+1] = 1; } } for (int k = 3; k <= len; k++) { for (int i = 0; i < len - k + 1; i++) { int j = i + k - 1; if (str[i] == str[j]) { dp[i][j] = dp[i+1][j-1] + 2; } else { dp[i][j] = max(dp[i+1][j], dp[i][j-1]); } } } cout << dp[0][len-1] << endl; } return 0; }

解法二：
字符串为str，把字符串倒序，记为rev，然后找str和rev的最长公共子序列的长度，就是str的最长回文子序列的长度。正确性的证明可以参考知乎上的一个回答：
字符串的 最长回文子序列（lps） 长度等于其自身与反转的 最长公共子序列（lcs）长度吗？
E: 通天塔 题目描述
大魔王抓走了你的女朋友(tan90°)，并对你的女朋友说：“你叫破喉咙也不会有人来救你的～”。你的女朋友开始呼救：“破喉咙！破喉咙！”。你听到了女朋友的呼救，马上赶来营救。在你面前有一座直上云霄的通天塔，你的女朋友就被大魔王关在塔顶。塔的形状可以看一个作圆柱体。塔的侧面展开，可以看作一个m*n的矩形。塔一共有n层，每层都有m个房间，每个房间里都有小怪看守，击败它们需要的消耗一定的体力值（甚至有可能是负数，表示恢复体力值）。你只能往上走，不能回头，且每次只能爬一层，到达直接相邻的上方的房间，或者对角线方向的两个斜上方的房间。为了保存体力，到了塔顶还需要和大魔王打一架，你需要花费最少的体力到达塔顶。请计算出从塔底到塔顶需要消耗的最少的体力值(甚至可以为负数)。你可以从塔底的任意一个房间开始登塔，从最顶层的任意一个房间到达塔顶。
输入
多组输入。 每组第一行为两个整数m,n。(1<=m<=10, 1<=n<=100) 接下来m行，每行n个数字。表示打败第n层第m个房间的小怪需要消耗的体力值。 注意：输入的n表示塔的层数，m是每层的房间数，不要搞混，输入的每一列是一层，第一列表示塔底，最后一列表示塔顶。

对于下面的前两个样例，你可以走的方向是：
第八届Nuist程序设计大赛 题解
文章图片

你可以走的路线是：
第八届Nuist程序设计大赛 题解
文章图片

输出
每组测试数据输出一个整数，表示最少需要消耗的体力

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

Sample Output
16 11 19

题解：
本题改编自 uva 116 Unidirectional TSP
改编后比原题简单，原题还需要输出最小字典序的路径
动态规划，对于每个房间，如果要走到这里，只可能从上一层的相邻的三个房间走过来。可以根据这个来写出动归方程。需要注意的是，通天塔是一个圆柱，侧面的一圈都是连通的。令dp[i][j]为到达第i层第j个房间最少需要消耗多少体力。动归方程

dp[i][j]=min{dp[(i?1+m)%m][j?1], dp[i][j?1], dp[(i+1)%m][j?1]}
#include #include #define MAXM 11 #define MAXN 101 using namespace std; int a[MAXM][MAXN]; int dp[MAXM][MAXN]; int m, n; int main(){ while (cin >> m >> n) { memset(a, 0, sizeof(a)); memset(dp, 0, sizeof(dp)); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { cin >> a[i][j]; } } for (int i = 0; i < m; i++) { dp[i][n-1] = a[i][n-1]; } for (int j = 0; j < n; j++) { for (int i = 0; i < m; i++) { int min_w; int t1 = i; int t2 = (i-1+m) % m; int t3 = (i+1) % m; min_w = dp[t1][j-1]; min_w = dp[t2][j-1] < min_w ? dp[t2][j-1] : min_w; min_w = dp[t3][j-1] < min_w ? dp[t3][j-1] : min_w; dp[i][j] = min_w + a[i][j]; } } int t = 0, ans = dp[0][n-1]; for (int i = 1; i < m; i++) { if (dp[i][n-1] < ans) { ans = dp[i][n-1]; } }cout << ans << endl; } return 0; }

F: 推箱子 题目描述
大家的童年一定少不了“推箱子”这个经典的游戏。具体规则就是在一个N*M的地图上，有1个玩家、1个箱子、1个目的地以及若干障碍，其余是空地。玩家可以往上下左右4个方向移动，但是不能移动出地图或者移动到障碍里去。如果往这个方向移动推到了箱子，箱子也会按这个方向移动一格，当然，箱子也不能被推出地图或推到障碍里。当箱子被推到目的地以后，游戏目标达成。现在告诉你游戏开始是初始的地图布局，请你求出玩家最少需要移动多少步才能够将游戏目标达成。
输入
多组输入 对于每组测试数据，第一行输入两个数字N，M表示地图的大小。其中0

输出
对于每组输入，输出一个数字表示玩家最少需要移动多少步才能将游戏目标达成。当无论如何达成不了的时候，输出-1。

样例输入:
4 4 .... ..\*@ .... .X.. 6 6 ...#.. ...... #\*##.. ..##.# ..X... .@#...

样例输出:
3 11

题解
本题来源： 网易笔试题
宽搜题。不过需要记录的状态比较多。
有两种bfs的策略，一种是直接搜索人移动的状态，另一种是搜索箱子移动的状态。我这里写的是第二种，bfs箱子的移动状态。
box结构体中x,y为箱子的位置,last_push记录上一次是怎么被推到这个位置的。这样可以推算出当前的人应该在什么位置。
每一次bfs箱子的状态时，都需要判断一下，下一个要搜索的状态是否可达。即推箱子的人，能不能从现在的位置，移动到可以把箱子推到下一个要搜索的状态的位置。判断是否可达的这个过程由函数is_connected()来计算，并且返回最少需要的步数。
bfs中的vis数组是3维的，前两维用来记录箱子的位置x,y,第三维用来判断这个箱子是怎么被推过来的。vis[i][j][k]存储的是最后一步是沿着k方向把箱子推到i,j处，推箱子的人一共走了多少步。我们搜索所有可能的情况，然后取最小值就是答案。
#include #include #include #define INF 0x3f3f3f3f #define MAXN 11 using namespace std; struct box { int x, y; int last_push; int step; box() {} box(int x, int y, int last, int step) : x(x), y(y), last_push(last), step(step) {} box(int x, int y, int step) : x(x), y(y), step(step) {} }; queue que; int N, M; char a[MAXN][MAXN]; int aim_x, aim_y; int player_x, player_y; int box_x, box_y; int fx[] = {0, 0, 1, 0, -1}; int fy[] = {0, 1, 0, -1, 0}; int is_connected(int from_x, int from_y, int to_x, int to_y) { if (from_x == to_x && from_y == to_y) return 0; queue q; bool vis[MAXN][MAXN]; memset(vis, false, sizeof(vis)); q.push(box(from_x, from_y, 0)); vis[from_x][from_y] = true; while (!q.empty()) { box b = q.front(); q.pop(); for (int i = 1; i <= 4; i++) { int tx = b.x + fx[i]; int ty = b.y + fy[i]; if (tx > 0 && tx <= N && ty > 0 && ty <= M) { if (a[tx][ty] == '.'&& !vis[tx][ty]) { if (tx == to_x && ty == to_y) { return b.step + 1; } vis[tx][ty] = true; q.push(box(tx, ty, b.step+1)); } } } } return -1; }int bfs() { if (box_x == aim_x && box_y == aim_y) return 0; long long vis[MAXN][MAXN][5]; long long ans = INF; memset(vis, false, sizeof(vis)); while (!que.empty()) que.pop(); que.push(box(box_x, box_y, 0, 0)); vis[box_x][box_y][0] = true; while (!que.empty()) { struct box b = que.front(); que.pop(); for (int i = 1; i <= 4; i++) { int tx = b.x + fx[i]; int ty = b.y + fy[i]; int to_x = b.x - fx[i]; int to_y = b.y - fy[i]; if (tx > 0 && tx <= N && ty > 0 && ty <= M && to_x > 0 && to_x <= N && to_y > 0 && to_y <= M) { if (a[tx][ty] == '.') { int from_x= b.x - fx[b.last_push]; int from_y= b.y - fy[b.last_push]; a[b.x][b.y] = '#'; if (!b.last_push) { from_x = player_x; from_y = player_y; } int step = is_connected(from_x, from_y, to_x, to_y); a[b.x][b.y] = '.'; if (step >= 0) { if (tx == aim_x && ty == aim_y) { long long tmp = b.step + step + 1; ans = min(ans, tmp); } else { step += b.step + 1; if (step < vis[tx][ty][i] || !vis[tx][ty][i]) { que.push(box(tx, ty, i, step)); vis[tx][ty][i] = step; } } } } } } } return ans == INF ? -1 : ans; }int main() { while (cin >> N >> M) { memset(a, 0, sizeof(a)); for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { char c; cin >> c; if (c == '@') { aim_x = i; aim_y = j; c = '.'; } else if (c == 'X') { player_x = i; player_y = j; c = '.'; } else if (c == '*') { box_x = i; box_y = j; c = '.'; } a[i][j] = c; } } cout << bfs() << endl; } }

G: 供电站 题目描述
你一个程序员，不知为何就当上了你们镇的镇长。你们镇有N(3<=N<=35)个村，分别标号为1,2,…,N，有些村常年供电不足。现在你需要重新规划镇上的供电站的选址。现在的要求是，对于镇里的每个村，要么这个村有个供电站，要么这个村相邻的村中有一个供电站。你最少需要建几个供电站？
输入
多组输入。 对于每组测试数据，第一行两个数N, M，分别表示村子数量和直接相连的村子关系的数量 接下来M行，每行两个数，表示这两个村子直接相连。注意：最后一组测试数据为N=0, M=0,是一个标记，表示输入结束，无需计算和输出任何东西

输出
每组测试数据输出一个整数，表示最少需要建的供电站数量

样例输入
8 12 1 2 1 6 1 8 2 3 2 6 3 4 3 5 4 5 4 7 5 6 6 7 6 8 0 0

样例输出
2

题解
本题来源： uva 10160 Servicing Stations
dfs+剪枝。
用邻接矩阵来存储图，相邻的村庄之间标为1,不相邻的标为0。这样，对于每一个村庄，都对应这一行01串，可以理解为该村庄的覆盖范围。现在问题可以转化为，从n个长度为n的01串中，取最少个数的01串，让它们做“或”运算，得到的结果为n位都是1。可以用dfs,搜索1层，2层,…n层。中途发现解就可以直接跳出。
这里有一个重要的剪枝策略。转化问题后，我们就不需要再考虑原图的连通问题了，所以我们可以从1到n，按顺序搜索。当搜索到第i个村庄的时候，表示从第1到第i-1的村庄如何放供电站的策略是已经确定了的。这时候，如果把从第i到第n个村庄都建供电站，也无法做到所有村庄全覆盖，则可以直接放弃当前的策略，无须继续搜索。
#include #include #define MAXN 40 using namespace std; typedef long long ll; ll b[MAXN]; ll f[MAXN]; ll full_one, one = 1; int n, m; bool dfs(int depth, int step, int start, ll ans) { if (ans == full_one) return true; if (step == depth) return false; if (start > n) return false; for (int i = start; i <= n; i++) { if ((ans | f[i]) != full_one) break; ll tmp = ans | b[i]; if (tmp == ans) continue; if (dfs(depth, step+1, i+1, tmp)) return true; } return false; }int main() { while (cin >> n >> m) { if (!n && !m) break; full_one = (one << n) - 1; memset(b, 0, sizeof(b)); memset(f, 0, sizeof(f)); for (int i = 1; i <= n; i++) b[i] |= (one << (i-1)); for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; b[u] |= (one << (v-1)); b[v] |= (one << (u-1)); }f[n] = b[n]; for (int i = n-1; i >= 1; i--) { f[i] = b[i]; f[i] |= f[i+1]; }for (int i = 1; i <= n; i++) { if (dfs(i, 0, 1, 0)) { cout << i << endl; break; } } } return 0; }

H: 青蛙跳荷叶 题目描述
校园的池塘里有m片荷叶，刚好围成一个圈，且相邻的荷叶之间间距相等。给这些荷叶编号为1, 2, …, m。有两只小青蛙A和B在荷叶上嬉戏玩耍。他们guguguagua一番之后，决定玩个游戏。起始时，A在第s1位置上，每次可以跳v1片荷叶的距离，B在s2位置上，每次可以跳v2片荷叶的距离。两只青蛙朝着相同的方向同时顺时针跳荷叶，且跳的频率相等，当它们同时跳在同一片荷叶时，游戏结束。你知道它们最少需要跳多少次才能在同一片荷叶上相遇么？
输入
多组输入。 每组测试数据输入5个整数s1,s2,v1,v2,m，其中 0≤v1,v2≤m≤1,000,000,000。0≤s1,s2

输出
每组测试数据输出1个整数，表示解，若该组数据无解则输出-1

样例输入
0 1 1 2 6

样例输出
5

题解
题目来源： hihocoder hiho一下 第95周
扩展欧几里德算法。 首先可以我俩现在的情况列出一个式子：s1+v1*k=s2+v2*k-t*m (v10。 物理意义上，A+=B,就是 v1+=m，就是把v1变快，每次多跳一圈，效果是一样的。 数学意义上，A+=B,只是改变了最后解出来的y的值。不影响最后我们需要计算的k若解出来的k<0，则不断累加B/gcd(A,B)，直到x>0为止。A'x'+B'y'+(u+(-u))A'B'=C =>(x' + uB')*A' + (y' - uA')*B' = C =>X = x' + uB', Y = y' - uA'

【第八届Nuist程序设计大赛 题解】关于扩展欧几里德算法的讲解，可以参考出题人的博客：
扩展欧几里德算法 递归和非递归实现及证明
#include #include using namespace std; typedef long long ll; ll exgcd(ll m, ll n, ll &x, ll &y) { if (n == 0) { x = 1; y = 0; return m; } int a, a1, b, b1, c, d, q, r, t; a1 = b = 1; a = b1 = 0; c = m; d = n; q = c/d; r = c%d; while (r) { c = d; d = r; t = a1; a1 = a; a = t - q * a; t = b1; b1 = b; b = t - q * b; q = c/d; r = c%d; } x = a; y = b; return d; }int main() { ll s1, s2, v1, v2, m; ll A, B, C; ll k, t; int P; cin >> P; for (int p = 0; p < P; p++) { cin >> s1 >> s2 >> v1 >> v2 >> m; A = v1-v2; B = m; C = s2-s1; if (A < 0) A += B; ll d = exgcd(A, B, k, t); if (C % d) cout << -1 << endl; else { k = (k * (C/d)) % B; while (k < 0) { k += B/d; } cout << k << endl; } }return 0; }

    推荐阅读


    上一篇：apollo|使用.net core操作Apollo

    下一篇：OpenGL学习笔记3（变换，矩阵，更多对象）