文章目录
A 身份证合法性检查
B 田径排名
C永远的七日之都
题目来源：牛客网
考试题型：3道程序题
考试时间：(北京时间,UTC+08:00)08月07日 19:30:00 -- 22:00:00
考试时长：150分钟
A 身份证合法性检查
题目描述：
身份证号码的第18位是由前17位和相应系数所决定。
权重系数a = {7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2}。第18位= (各个位上的数 x对应位的系数)之和模11，若为10则为'X'。
/pmd/350196.html 但是由于身份证被污染了，导致15-17位部分看不清，用*表示，可能取值为0-9，小易想知道合法的身份证一共有多少种。
输入描述：
输入第一行为一个正整数T(T<=100)，表示有T组数据。
每组数据一行，包含一个18位的身份证号，其中在第15-17位可能存在数字缺失，用*表示。第18位除了数字0-9，也可能是x。
输出描述：
对于每一组数据，输出合法的身份证号的个数。
示例：
输入：
34088119480815*6635301169**4输出：
19
思路：
直接模拟
#include<iostream>#include<string>using namespace std;int a[18] = { 7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2 };int f[11] = { 1,0,10,9,8,7,6,5,4,3,2 };void solve() {string s;cin >> s;int q[3] = { -1,-1,-1 };int qnum = 0;for (int i = 14; i < 17; i++) {if (s[i] == '*') {q[qnum++] = i;}}int sum = 0;for (int i = 0; i < 17; i++) {if (i != q[0] && i != q[1] && i != q[2]) {int n = s[i] - '0';sum += (n*a[i]);sum %= 11;}}int flag;if (s[17] >= '0' && s[17] <= '9')flag = s[17] - '0';elseflag = 10;int cnt = 0;if (qnum == 1) {for (int i = 0; i <= 9; i++) {if ((sum + i * a[q[0]]) % 11 == f[flag]) {cnt++;}}}else if (qnum == 2) {for (int i = 0; i <= 9; i++) {for (int j = 0; j <= 9; j++) {if ((sum + i * a[q[0]] + j * a[q[1]]) % 11 == f[flag]) {cnt++;}}}}else if (qnum == 3) {for (int i = 0; i <= 9; i++) {for (int j = 0; j <= 9; j++) {for (int k = 0; k <= 9; k++) {if ((sum + i * a[q[0]] + j * a[q[1]] + k * a[q[2]]) % 11 == f[flag]) {cnt++;}}}}}cout << cnt << endl;}int main() {int T;cin >> T;while (T--) {solve();}return 0;}
B 田径排名
题目描述：
小易在看完奥运男子百米飞人大战后，深深地迷上了创造历史的中国飞人苏炳添。他想起了在中学时期他们学校举行的一次百米大赛，参加比赛的总共有N个运动员，在比赛结束后裁判们却不小心把成绩单弄丢了。虽然运动员的具体时间已经无法复原,但作为裁判之一的小易还是希望能给出一个运动员的最终排名。于是，小易依次询问了M个现场观众，每个观众由于也不是非常确定，所以他们只能告诉小易他们所关心的某几位运动员的冲过终点的先后情况。假设观众提供的信息都是准确的。小易想知道，根据这M个现场观众提供的信息，能否确定最后的运动员的成绩排名。
输入描述：
输入第一行为一个正整数T（T <= 10），表示有T组数据。
每组数据第一行，输入两个正整数N，M（1 < N <= 1000，1 <= M <= 10000），以下M行，每行代表一位观众提供的信息，第一个数是C（2 <= C <= N)，表示他所记得的c位运动员的信息后面是C个整数Xi(1 <= Xi <= N)，表示C位运动员冲过终点的顺序，排在前面的为先冲过终点的运动员。
输出描述：
对于每组数据，如果能唯一确定比赛排名，则输出比赛排名。否则输出NO。
示例：
输入：
43 22 1 32 1 24 33 1 2 32 1 32 1 44 14 1 2 3 44 33 1 2 43 1 3 42 3 2输出：
NONO1 2 3 41 3 2 4
思路：
拓扑排序
#include <bits/stdc++.h>using namespace std;const int N = 1e3 + 5;vector<int> g[N];//存储第i个人前面有哪些人int deg[N];int main() {int T;cin >> T;while (T--) {int n, m;cin >> n >> m;for (int i = 1; i <= n; i++) {g[i].clear();//初始化g[N]deg[i] = 0;//初始化deg[N]}set<int> st;//存储运动员序号while (m--) {int c; cin >> c;vector<int> v(c);//存储一个人看到的顺序for (auto &i : v) {cin >> i;st.insert(i);//输入一个人看见的运动员序号}//一个人看见的运动员序号输入完毕for (int i = 1; i < v.size(); i++) {g[v[i]].push_back(v[i - 1]);//i-1为排在i前面的人，将i-1运动员的序号加入到g[i]中deg[v[i - 1]]++;//v[i-1]运动员的位序+1}}if (st.size() == n) {//输入运动员个数与人们给与的个数相符合stack<int> ans;//存储最后输出的次序queue<int> Q;for (int i = 1; i <= n; i++) if (deg[i] == 0) Q.push(i);//deg[i]为0说明i是最后一名 取deg=0的人加入队列Qint num = 0; bool ok = 1;while (!Q.empty()) {if (Q.size() > 1) ok = 0;//最后一个人的个数大于1 不符合 无法判断所有运动员次序int x = Q.front();//取出队首元素Q.pop();//弹出队首元素num++;//弹出的运动员个数+1ans.push(x);//记录最后输出次序for (auto v : g[x]) {deg[v]--;//排在x前面的所有人的位次序-1；if (deg[v] == 0) Q.push(v);//此时排名最后的加入Q}}if (ok == 1) {while (!ans.empty()) {cout << ans.top() << " ";//输出最终排序ans.pop();}cout << endl;}else {puts("NO");}}else {puts("NO");}}}
C永远的七日之都
题目描述：
小易最近在玩《永远的七日之都》。游戏中的人物伤害加成属性多种多样，暴击率，连斩率，穿透率…....每项属性都是独立概率触发事件，触发之后会对总伤害乘上一个该项属性相应的系数。作为游戏高玩，小易当然要做到最完美的加点，让期望伤害达到最高，但是他只有K单位钱。已知基础伤害为1，每花费单位钱能使得某项属性的触发概率提高1%(提升绝对数值1%，而非使触发率乘101%，如原来触发的概率是X%，提高后为(X+1)%)，小易想知道最优的加点方案下的期望伤害是多少。
输入描述：
输入第一行为一个正整数T，表示数据组数。
对于接下来每组数据，第二行为两个正整数N和K，分别表示伤害加成属性的数量和蚀日拥有的钱。
接下来N行，每行2个整数Ai和Wi，表示第i项属性的触发概率为Ai%，触发后会使最终伤害乘以Wi。
注意:同一项属性可以提高多次；当触发概率超过100%后，视为100%触发。
数据范围：
对于所有数据，满足1<=T<=5，1<=N，K<=100000，0<=Ai<=100，1<=Wi<=1000。
输出描述：
对于每组数据，为了回避精度问题，输出一行一个正整数表示最优加点方案能得到的最高期望伤害乘以100^(N)再对1000000007取模的结果。
示例：
输入：
33 20 20 30 43 20 40 41 45 60 40 40 40 40 4输出：
10600001092727930393309
思路：
贪心
#include <bits/stdc++.h>using namespace std;typedef long long ll;const int M = 1e9 + 7;struct node {int a;int w;node(int _a, int _w) {a = _a;w = _w;}bool operator < (const node & b)const {if (a == 100)return false;if (b.a == 100)return true;if (w == b.w)return a > b.a;return (100 - (a + 1) + (a + 1)*w) * (100 - b.a + b.a*b.w)< (100 - a + a*w) * (100 - (b.a + 1) + (b.a + 1)*b.w);}};int main() {int T; cin >> T;while (T--) {int n, k;ll ans = 1;cin >> n >> k;priority_queue<node> q;for (int i = 0; i < n; i++){int a, w;cin >> a >> w;q.push(node(a, w));}while (k && !q.empty()) {node t = q.top();q.pop();if (t.a < 100) {t.a++;k--;q.push(t);}else {ans = (ans * t.w) % M;}}while (!q.empty()) {node t = q.top();q.pop();if (t.a) ans = (ans * (100 - t.a + t.a*t.w)) % M;else ans *= 100;}cout << ans % M << endl;}}
