这次测试题题目中规中矩，不是很难也不是很简单。在这里给出一些题解，有的我也不一定会，毕竟实验室大佬很多。
熊文静的抖音密码
这题很简单，简单的模拟题直接给出代码
C 代码
#include <stdio.h>
int main()
{
char s[100];
int n;
scanf("%d", &n);
getchar();
gets(s);
for (int i = 0; s[i] != '\0'; i++)
s[i] = (s[i] - 'a' + n) % 26 + 'a';
puts(s);
}
许钟乐的诛心算比赛
这题就是一个暴力搜，数据范围很小，我的做法是先把 a 数组所有的能加的情况加起来放到另一个数组 b，然后 a 数组与 b 数组里的数一一比较。
下面给出代码
C 代码
#include <iostream>
using namespace std;
int main()
{
int n;
scanf("%d", &n);
int a[105], b[10005], cot = 0;
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++)
b[cot++] = a[i] + a[j];
int ans = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < cot; j++)
if (a[i] == b[j])
{
ans++;
break;
}
}
printf("%d", ans);
return 0;
}
C++代码
#include <iostream>
#include <vector>
using namespace std;
vector<int> v;
int main()
{
int n, a[1000];
cin >> n;
int cot = 0;
vector<int> v(n);
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++)
v.push_back(a[i] + a[j]);
for (int i = 0; i < n; i++)
for (auto j : v)
if (a[i] == j)
{
cot++;
break;
}
cout << cot << endl;
}
函数方程
这题由于数据过小，直接暴力搜，当数据大了的话，可以用二分。
由于这题数据比较小。所以直接暴力搜。
C 代码
#include <stdio.h>
#define INF 1E-6
int check(double x)
{
if (x * x * x * x * x - 15 * x * x * x * x + 85 * x * x * x - 225 * x * x + 274 * x - 121 < INF)
return 1;
return 0;
}
int main()
{
for (double i = 1.5; i <= 2.4; i += 0.00001)
if (check(i))
{
printf("%.5lf", i);
break;
}
}
或者这题直接写答案就可以
#include <stdio.h>
int main(){
printf("1.84902");
}
A+B
这题一看就不能用long long因为long long的范围就是$-2^{63}$ ~ $2^{63}-1$化简一下就是-9223372036854775808 ~ 9223372036854775807 所以这个范围肯定超了long long，所以我们要用字符串模拟。
C 代码
#include <stdio.h>
#include <string.h>
const int N = 10005;
void reverse(char s[])
{
int len = strlen(s);
for (int i = 0, j = len - 1; i < j; i++, j--)
{
char t = s[i];
s[i] = s[j];
s[j] = t;
}
}
void add(char s1[], char s2[], char ans[])
{
int len1 = strlen(s1);
int len2 = strlen(s2);
reverse(s1);
reverse(s2);
int hex = 0, i;
int len = len1 > len2 ? len1 : len2;
for (i = 0; i < len; i++)
{
int a = 0;
int b = 0;
if (i < len1)
a = s1[i] - '0';
if (i < len2)
b = s2[i] - '0';
ans[i] = (a + b + hex) % 10 + '0';
hex = (a + b + hex) / 10;
}
if (hex)
ans[i++] = hex + '0';
ans[i] = '\0';
reverse(ans);
}
int main()
{
char s1[N], s2[N], ans[N];
scanf("%s%s", s1, s2);
add(s1, s2, ans);
printf("%s\n", ans);
}
C++ 代码
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string add(string a, string b)
{
int hex = 0;
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
int len1 = a.length();
int len2 = b.length();
string ans;
for (int i = 0, j = 0; i < len1 || j < len2; i++, j++)
{
int num1 = 0, num2 = 0;
if (i < len1)
num1 = a[i] - '0';
if (j < len2)
num2 = b[i] - '0';
ans = char((num1 + num2 + hex) % 10 + '0') + ans;
hex = (num1 + num2 + hex) / 10;
}
if (hex)
ans = char(hex + '0') + ans;
return ans;
}
int main()
{
string a, b;
while (cin >> a >> b)
cout << add(a, b) << endl;
}
这种高精度算法是很常见的算法，希望大家一定牢记在心。
解密数字
这题是一题找规律题，给了一个表格可以得出来很简单的规律，首先进行 n 的转换$n\rightarrow n+1$，然后将$n+1$转成二进制然后除去最高位进制。
下面直接给代码
C 代码
#include <stdio.h>
#include <string.h>
const int N = 10005;
int ans[N];
int main()
{
int n;
while (~scanf("%d", &n))
{
int cot = 0;
++n;
while (n)
{
ans[cot++] = (n % 2);
n >>= 1;
}
for (int i = cot - 2; i >= 0; i--)
printf("%d", ans[i]);
printf("\n");
}
}
C++ 代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
int s;
while (cin >> s)
{
++s;
string ans;
while (s)
{
ans = (s & 1 ? '1' : '0') + ans;
s >>= 1;
}
cout << ans.substr(1) << '\n';
}
}
后缀表达式
这题是数据结构上的东西，要用到栈，想学的就去查一下。
我直接上 C++代码
C++代码
#include <iostream>
#include <cctype>
#include <stack>
using namespace std;
using ll = long long;
string RPN(string s)
{
stack<char> st;
string ans;
for (int j = 0; j < s.size(); j++)
{
char i = s[j];
if (isdigit(i) || isalpha(i))
{
while (isdigit(s[j]))
{
ans += s[j];
j++;
}
ans += '#';
j--;
continue;
}
if (i == '(')
st.push('(');
else if (i == ')')
{
while (!st.empty() && st.top() != '(')
{
ans += st.top();
st.pop();
}
st.pop();
}
else if (i == '+' || i == '-')
{
while (!st.empty() && st.top() != '(')
{
ans += st.top();
st.pop();
}
st.push(i);
}
else if (i == '*' || i == '/')
{
while (!st.empty())
{
if (st.top() == '*' || st.top() == '/')
{
ans += st.top();
st.pop();
}
else
break;
}
st.push(i);
}
}
while (!st.empty())
{
ans += st.top();
st.pop();
}
return ans;
}
double slove(string s)
{
ll a = 0;
stack<double> st;
for (auto i : s)
{
if (isdigit(i))
{
a = a * 10 + (i - '0');
}
else if (i == '#')
{
st.push(a);
a = 0;
}
else
{
if (i == '+')
{
double a = st.top();
st.pop();
double b = st.top();
st.pop();
st.push(a + b);
}
if (i == '-')
{
double a = st.top();
st.pop();
double b = st.top();
st.pop();
st.push(b - a);
}
if (i == '*')
{
double a = st.top();
st.pop();
double b = st.top();
st.pop();
st.push(a * b);
}
if (i == '/')
{
double a = st.top();
st.pop();
double b = st.top();
st.pop();
st.push(b * 1.0 / a);
}
}
}
return st.top();
}
int main()
{
string s;
while (cin >> s)
{
printf("%.4lf\n", slove(RPN(s)));
}
}
小文的烤鸡
这题是实验室的贾佬憨出的，虽然看了像在骂我，但是我不介意。这题直接暴力搜就好，没什么问题。
C 语言
#include <stdio.h>
int main()
{
int t[5005][10];
int a, b, c, d, e, f, g, h, i, j, n,ans=0;
scanf("%d", &n);
for (a = 1; a <= 3; a++)
for (b = 1; b <= 3; b++)
for (c = 1; c <= 3; c++)
for (d = 1; d <= 3; d++)
for (e = 1; e <= 3; e++)
for (f = 1; f <= 3; f++)
for (g = 1; g <= 3; g++)
for (h = 1; h <= 3; h++)
for (i = 1; i <= 3; i++)
for (j = 1; j <= 3; j++)
if(a + b + c + d + e + f + g + h + i + j == n){
t[ans][0]=a;
t[ans][1]=b;
t[ans][2]=c;
t[ans][3]=d;
t[ans][4]=e;
t[ans][5]=f;
t[ans][6]=g;
t[ans][7]=h;
t[ans][8]=i;
t[ans][9]=j;
ans++;
}
printf("%d\n", ans);
if(ans == 0)
printf("%d", 0);
else
for(int i=0; i < ans; i++)
printf("%d %d %d %d %d %d %d %d %d %d\n", t[i][0], t[i][1], t[i][2], t[i][3], t[i][4], t[i][5], t[i][6], t[i][7], t[i][8], t[i][9]);
}
吐了，写了这么多循环。
探险日志
大佬的题真的强，我不会，我哭辽。明天找叶大佬交易一波，让他教我怎么写，我在把这题补全。
今天找大佬交易了一波，叶大佬把代码传授于我。我转发到了这。
这题是一题 BFS(广度优先搜索)
首先将地图中的所有门及所对应的钥匙用一个数组存储数量，用于判断在搜索过程中当前拥有的钥匙是否满足打开某个门的条件。BFS 从起点开始搜索，在搜索过程中用一个 bool 型变量标记在此次搜索中是否寻找到了新钥匙。搜索中，可能遇到门后由于该门所对应的钥匙不足而打不开，所以一旦找到了新钥匙，就重新从起点开始再次搜索判断之前未打开的门是否能够新获得的钥匙打开。然后，每次打开心得门可能又会获得新的钥匙，所以除非找不到新钥匙，BFS 每次都从起点重新搜索，最后结束之后，判断是否找到终点就可以了。
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
char road[22][22]; //存储迷宫
bool book[22][22], flag,k; //book用来标记寻找终点时的路径标记
int Next[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; //四个方向
int M, N, x1, Y1, x2, y2; //M行，N列，起始点坐标和终点坐标
int key[5], allkey[5]; //已找到的钥匙数和钥匙总数
struct node
{
int x, y; //广搜所用结构体，存储当前点的坐标
} door[5];
queue<node> q;
void bfs(node temp)
{
book[x1][Y1] = book[x2][y2] = true; //起点和终点标记为已走过
while (!q.empty())
{ //如果队列不为空，清空队列
q.pop();
}
q.push(temp); //将起点入队
while (!q.empty())
{ //队列不为空时循环
for (int i = 0; i < 4; ++i)
{ //枚举四个方向
int nextx = q.front().x + Next[i][0];
int nexty = q.front().y + Next[i][1];
if (nextx < 0 || nexty < 0 || nextx >= M || nexty >= N)
{ //越界则尝试下一个方向
continue;
}
if (road[nextx][nexty] >= 97)
{ //如果下一个位置是钥匙
key[road[nextx][nexty] - 97]++; //已找到的钥匙数加一
k = true;
if (key[road[nextx][nexty] - 97] == allkey[road[nextx][nexty] - 97])
{
road[door[road[nextx][nexty] - 97].x][door[road[nextx][nexty] - 97].y] = '.';
}
road[nextx][nexty] = '.'; //将该钥匙点变为可走的路
}
if (!book[nextx][nexty] && (road[nextx][nexty] < 65 || road[nextx][nexty] > 90))
{ //如果该点没走过且能走
book[nextx][nexty] = true; //将该点标记为已走过
node t = {nextx, nexty};
q.push(t); //将该点入队
}
if (nextx == x2 && nexty == y2)
{
flag = true;
return;
}
}
q.pop(); //将队首出队
}
memset(book, false, sizeof(book)); //清空路径标记
}
int main()
{
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
while (cin >> M && cin >> N)
{ //循环输入M,N
if (M == 0 && N == 0)
{ //全为零时退出
break;
}
flag = false;
k = false;
memset(road, '\0', sizeof(road)); //每次清空路径数组
memset(book, false, sizeof(book)); //清空路径标记
memset(key, 0, sizeof(key)); //清空已找到钥匙标记
memset(allkey, 0, sizeof(allkey)); //清空全部钥匙标记
for (int i = 0; i < M; ++i)
{ //双重循环输入
for (int j = 0; j < N; ++j)
{
cin >> road[i][j];
if (road[i][j] >= 97)
{ //如果输入的是钥匙
allkey[road[i][j] - 97]++; //该种钥匙总数加一
}
else if (road[i][j] == 'S')
{ //如果输入了起点
x1 = i; //将起始点存储
Y1 = j;
}
else if (road[i][j] == 'G')
{ //如果输入了终点
x2 = i; //将终点存储
y2 = j;
}
else if (road[i][j] >= 65 && road[i][j] <= 69)
{
door[road[i][j] - 65].x = i;
door[road[i][j] - 65].y = j;
}
}
}
node temp = {x1, Y1}; //根据起点坐标创建结构体变量
bfs(temp);
while(k) { //如果此次搜索到了新钥匙，就再次搜索能否通过这个钥匙打开新的门
k = false;
bfs(temp);
}
book[x1][Y1] = true; //起点标记为已走过
if (flag)
{
cout << "YES\n";
}
else
{
cout << "NO\n";
}
}
return 0;
}
