第一题:小中大
在数据分析中,最小值最大值以及中位数是常用的统计信息。
老师给了你 n 个整数组成的测量数据,保证有序(可能为升序或降序),可能存在重复的数据。
请统计出这组测量数据中的最大值、中位数以及最小值,并按照从大到小的顺序输出这三个数。
输入格式
第一行输入一个整数 n。
第二行中存在 n 个有序的整数,表示测量数据,可能为升序或降序排列,可能存在连续多个整数相等,整数与整数之间使用空格隔开。
输出格式
包含一行,包括最大值、中位数以及最小值共三个数,并按照从大到小的顺序输出。
数据与数据之间使用空格隔开。
对于整数请直接输出整数,对于可能出现的分数,请输出四舍五入保留 1 位小数的结果。
数据范围
测试点 n 测量数据的绝对值 测量数据是否均相同 1,2 ≤1e3 ≤1e7 是 3,4,5,6 ≤1e3 ≤1e7 否 7,8 ≤1e5 ≤1e7 是 9∼20 ≤1e5 ≤1e7 否 输入样例1:
3 -1 2 4
输出样例1:
4 2 -1
样例1解释
4 为最大值,2 为中位数,−1 为最小值。
输入样例2:
4 -2 -1 3 4
输出样例2:
4 1 -2
样例2解释
4 为最大值,(−1+3)÷2=1 为中位数,−2 为最小值。
#include<iostream>using namespace std;const int N = 1e5 + 10;
int n;
int a[N];
int _max = -0x3f3f3f3f , _min = 0x3f3f3f3f;int main()
{cin >> n;for(int i = 0;i < n;i ++) cin >> a[i] , _max = max(_max , a[i]) , _min = min(_min , a[i]);double x = 0;if(n & 1) x = a[n / 2];else x = (a[n / 2] + a[n / 2 - 1]) * 1.0 / 2;if((int)x == x)printf("%d %d %d" , _max , (int)x , _min);else printf("%d %.1lf %d" ,_max , x , _min);return 0;
}
n = int(input())
l = list(map(int , input().split()))
x = 0
if n & 1:x = l[n // 2]
else:x = (l[n // 2 - 1] + l[n // 2]) / 2
print(max(l) , end = ' ')
if int(x) == x:print(int(x) , end = ' ')
else:print("%.1lf" %(x) , end = ' ')
print(min(l))
第二题:二十四点
二十四点是一款著名的纸牌游戏,其游戏的目标是使用 3 个加减乘除运算使得 4 张纸牌上数字的运算结果为 24。
定义每一个游戏由 4 个从 1−9 的数字和 3 个四则运算符组成,保证四则运算符将数字两两隔开,不存在括号和其他字符,运算顺序按照四则运算顺序进行。
其中加法用符号
+
表示,减法用符号-
表示,乘法用小写字母x
表示,除法用符号/
表示。在游戏里除法为整除(向下取整),例如 2/3=0,3/2=1,4/2=2,−3/7=−1。
老师给了你 n 个游戏的解,请你编写程序验证每个游戏的结果是否为 24。
输入格式
第一行输入一个整数 n。
从第 2 行开始到第 n+1 行中,每一行包含一个长度为 7 的字符串,为上述的 24 点游戏,保证数据格式合法。
输出格式
包含 n 行,对于每一个游戏,如果其结果为 24 则输出字符串
Yes
,否则输出字符串No
。数据范围
输入样例:
10 9+3+4x3 5+4x5x5 7-9-9+8 5x6/5x4 3+5+7+9 1x1+9-9 1x9-5/9 8/5+6x9 6x7-3x6 6x4+4/5
输出样例:
Yes No No Yes Yes No No No Yes Yes
样例解释
9+3+4×3=24 5+4×5×5=105 7-9-9+8=-3 5×6/5×4=24 3+5+7+9=24 1×1+9-9=1 1×9-5/9=9 8/5+6×9=55 6×7-3×6=24 6×4+4/5=24
解题思路:
使用python的eval函数进行求解
for _ in range(int(input())):s = input()s = s.replace("x" , "*")s = s.replace("/" , "//")if eval(s) == 24:print("Yes")else:print("No")
第三题:损坏的RAID5(这一次的最难的)
大模拟
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;typedef unsigned int UI;
const int N = 1010, M = 40 * 1024 * 8 + 10;int n, s, l;
UI disk[N][M / 8];
bool st[N];
char str[M];
int len;inline UI get(char c)
{if (c <= '9') return c - '0';return c - 'A' + 10;
}inline char get(UI x)
{if (x <= 9) return x + '0';return x - 10 + 'A';
}inline string u2s(UI x)
{string res;for (int i = 7; i >= 0; i -- )res += get(x >> (i << 2) & 15);return res;
}inline int get_real_col(int r, int c)
{r %= n;r = n - 1 - r;return (r + 1 + c) % n;
}int main()
{scanf("%d%d%d", &n, &s, &l);for (int u = 0; u < l; u ++ ){int k;scanf("%d", &k);getchar();fgets(str, M, stdin);int sz = strlen(str) - 1;for (int i = 0; i < sz; i += 8){UI x = 0;for (int j = 0; j < 8; j ++ )x = (x << 4) + get(str[i + j]);disk[k][i >> 3] = x;}st[k] = true;len = max(len, sz >> 3);}int m;scanf("%d", &m);while (m -- ){int b;scanf("%d", &b);if (b >= len * (n - 1)) puts("-");else{int k = b / s;int row = k / (n - 1), col = get_real_col(row, k % (n - 1));int r = row * s + b % s;if (st[col])puts(u2s(disk[col][r]).c_str());else if (l == n - 1){UI x = 0;for (int i = 0; i < n; i ++ ) x ^= disk[i][r];puts(u2s(x).c_str());}else puts("-");}}return 0;
}。
第四题:消息传递接口
解题思路:使用队列进行模拟,信息传递接口
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <sstream>using namespace std;const int N = 10010;int n;
struct Op
{// 0代表S 1代表R -1代表等待int p, id;
};
queue<Op> q[N];
bool st[N];// 判断该进程是否在等待// 功能: PD pid进程当前指令能否执行完毕, 目前pid执行到{!type, oid}, 即期望对方是type
bool dfs(int p, int id, int pid)
{// 若等待的对方也在等待,则死锁if (st[id]) return false;st[id] = true;// 对方进入等待队列while (q[id].size()){auto t = q[id].front();// 如果对方等的那个刚刚好是自己,且刚刚好是自己所期待的if (t.p == p && t.id == pid){st[id] = false;q[id].pop();return true;}// PD 对方当前指令能否完成else if (dfs(t.p ^ 1, t.id, id)) q[id].pop();else return false;}st[id] = false;return p == -1;
}int main()
{int T;cin >> T >> n;getchar();while (T -- ){string str;for (int i = 0; i < n; i ++ ){st[i] = false;q[i] = queue<Op>();getline(cin, str);stringstream ssin(str);while (ssin >> str)if (str[0] == 'S') q[i].push({0, stoi(str.substr(1))});else q[i].push({1, stoi(str.substr(1))});}// 添加一个-1进程,等待所有0~n-1进程执行完bool success = true;for (int i = 0; i < n; i ++ )if (!dfs(-1, i, -1)){success = false;break;}if (success) puts("0");else puts("1");}return 0;
}
第五题:317号子问题
经典的图论问题(SPFA 或 迪杰斯特拉)
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>using namespace std;
const int N = 1e4 + 10 , M = 2e5 + 10 , INF = 0x3f3f3f3f;
typedef pair<int , int>PII;
int h[M] , ne[M] , w[M] , e[M] , idx;void add(int a , int b , int c)
{e[idx] = b , w[idx] = c , ne[idx] = h[a] , h[a] = idx ++;
}
int solor[N];
int n , m , k;
bool st[N];
int dist[N] , cnt = 0;
int d[N][1010];void dij(int s)
{memset(dist , 0x3f , sizeof dist);memset(st , 0 , sizeof st);dist[s] = 0;priority_queue<PII , vector<PII> , greater<PII>>q;q.push({0 , s});while(!q.empty()){auto t = q.top();q.pop();int x = t.second;if(st[x]) continue;st[x] = true;for(int i = h[x];~i;i = ne[i]){int j = e[i];if(dist[j] > dist[x] + w[i]){dist[j] = dist[x] + w[i];q.push({dist[j] , j});}}}for (int i = 1; i <= n; i ++ ) d[i][cnt] = dist[i];
}void spfa(int start)
{int hh = 0, tt = 1;memset(dist, 0x3f, sizeof dist);int q[N];q[0] = start, dist[start] = 0;while (hh != tt){int t = q[hh ++ ];if (hh == N) hh = 0;st[t] = false;for (int i = h[t]; ~i; i = ne[i]){int j = e[i];if (dist[j] > dist[t] + w[i]){dist[j] = dist[t] + w[i];if (!st[j]){q[tt ++ ] = j;if (tt == N) tt = 0;st[j] = true;}}}}for (int i = 1; i <= n; i ++ ) d[i][cnt] = dist[i];
}int main()
{memset(h , -1 , sizeof h);scanf("%d %d %d" ,&n ,&m ,&k);for(int i = 1;i <= n;i ++)scanf("%d" ,&solor[i]);while(m --){int a , b , c;scanf("%d %d %d" ,&a ,&b ,&c);add(a , b , c) , add(b , a , c);}for(int i = 1;i <= n;i ++)if(solor[i]){// dij(i);spfa(i);cnt ++;}for(int i = 1;i <= n;i ++){sort(d[i] , d[i] + cnt);int res = 0;for(int j = 0;j < cnt && j < k;j ++)if(d[i][j] != INF) res += d[i][j];else break;printf("%d\n" , res);}return 0;
}