这东西……勉强能算是个做题记录?有些恶心的模拟题用了非常规的解法,这里就不放代码了
训练作业一
众数
每组数据均以递增顺序输入,故从左到右扫描输入序列,记录最多连续 出现的数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include <bits/stdc++.h> using namespace std;int main () { int n; cin >> n; while (n) { int cnt; int last = -1 ; int grp = 0 , record = 0 ; for (int i = 0 ; i < n; i++) { int tmp; cin >> tmp; (last != tmp) && (cnt = 0 ); cnt++; if (cnt > record) { record = cnt; grp = tmp; } last = tmp; } cout << grp << endl; cin >> n; } return 0 ; }
错误的里程表
不出现 3 和 8,则原来的十进制降为八进制,那么将 01245679
还原为 01234567
后再作 八进制 → 十进制 转换
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #include <bits/stdc++.h> using namespace std;int main () { int n; cin >> n; char digit[] = {0 , 1 , 2 , 0 , 3 , 4 , 5 , 6 , 0 , 7 }; while (n--) { string str; cin >> str; int real = 0 ; for (char ch : str) { real = real * 8 + digit[ch-'0' ]; } cout << real << endl; } return 0 ; }
拳王阿里
设比赛的总天数为 7 k + d ( k ∈ Z ) 7k+d\quad(k\in Z) 7 k + d ( k ∈ Z ) ,那么 d d d 可由开始和结束的星期数确定;由于 L L L 、R R R 差值较小,直接遍历 [ L , R ] [L, R] [ L , R ] 求解
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include <bits/stdc++.h> using namespace std;map<string, int > day = { {"monday" , 1 }, {"tuesday" , 2 }, {"wednesday" , 3 }, {"thursday" , 4 }, {"friday" , 5 }, {"saturday" , 6 }, {"sunday" , 7 } }; int main () { int T; cin >> T; while (T--) { string begin, end; int L, R; cin >> begin >> end >> L >> R; int d = (day[end] - day[begin] + 8 ) % 7 ; int ans, count = 0 ; for (int i = L; i <= R; i++) { if ((i - d) % 7 == 0 ) { ans = i; count++; } } if (count == 0 ) { cout << "impossible" << endl; } else if (count >= 2 ) { cout << "many" << endl; } else { cout << ans << endl; } } return 0 ; }
不妨设阿里比赛的总天数为 7 k + d ∈ [ L , R ] 7k+d\in[L, R] 7 k + d ∈ [ L , R ] ,简单整理可得:
k ∈ [ L − d 7 , R − d 7 ] k\in[\frac{L-d}{7}, \frac{R-d}{7}]
k ∈ [ 7 L − d , 7 R − d ]
其中 d d d 的值可由比赛开始和结束的星期数计算而得,那么只需要确定在上述区间中有几个整数 k k k 即可;由于除法可能产生小数数值,判断的时候需要对区间左端点向上取整,右端点向下取整,再比较左右端点的大小,记 k 1 = ⌈ L − d 7 ⌉ k_1=\lceil\frac{L-d}{7}\rceil k 1 = ⌈ 7 L − d ⌉ ,k 2 = ⌊ R − d 7 ⌋ k_2=\lfloor\frac{R-d}{7}\rfloor k 2 = ⌊ 7 R − d ⌋ ,那么当 k 1 = k 2 k_1=k_2 k 1 = k 2 时,有唯一解,k 1 < k 2 k_1 < k_2 k 1 < k 2 时,有多解,否则没有解。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include <bits/stdc++.h> using namespace std;map<string, int > day = { {"monday" , 1 }, {"tuesday" , 2 }, {"wednesday" , 3 }, {"thursday" , 4 }, {"friday" , 5 }, {"saturday" , 6 }, {"sunday" , 7 } }; int main () { int T; cin >> T; while (T--) { string begin, end; int L, R; cin >> begin >> end >> L >> R; int d = (day[end] - day[begin] + 8 ) % 7 - 7 ; int k1 = (L - d + 6 ) / 7 , k2 = (R - d) / 7 ; if (k1 == k2) { cout << 7 *k1 + d << endl; } else if (k1 < k2) { cout << "many" << endl; } else { cout << "impossible" << endl; } } return 0 ; }
欧洲冠军联赛
模拟即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 from collections import defaultdictT = int (input ()) for i in range (T): count = defaultdict(lambda : [0 , 0 ]) for j in range (12 ): teamA, scoreA, _, scoreB, teamB = input ().split() scoreA, scoreB = int (scoreA), int (scoreB) if scoreA == scoreB: count[teamA][0 ] += 1 count[teamB][0 ] += 1 else : count[teamA][0 ] += 3 if scoreA - scoreB > 0 else 0 count[teamA][1 ] += scoreA - scoreB count[teamB][0 ] += 3 if scoreB - scoreA > 0 else 0 count[teamB][1 ] += scoreB - scoreA tops = [] for name in count: tops.append((name, count[name])) tops.sort(key=lambda x: x[1 ][0 ]*100 + x[1 ][1 ]) print (tops[-1 ][0 ], tops[-2 ][0 ])
合法的括号串
维护一个存放左括号的栈,当遇到右括号时尝试对与其匹配的左括号出栈,若无法完成此操作或最后栈不为空,则认为输入的字符串不合法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include <bits/stdc++.h> using namespace std;map<char , char > rev = {{'>' , '<' }, {')' , '(' }, {']' , '[' }, {'}' , '{' }}; void judge (string str) { stack<char > st; for (char ch : str) { if (ch == '<' || ch == '[' || ch == '(' || ch == '{' ) { st.push (ch); } else { if (st.empty ()) { cout << "No" << endl; return ; } if (st.top () == rev[ch]) { st.pop (); } else { cout << "No" << endl; return ; } } } cout << (st.empty () ? "Yes" : "No" ) << endl; } int main () { int T; cin >> T; while (T--) { string str; cin >> str; judge (str); } return 0 ; }
世界杯来了
与第四题大同小异,改改就能用:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 import recount = {} n = int (input ()) for i in range (n): count[input ()] = [0 , 0 , 0 ] for i in range (n*(n-1 )//2 ): teamA, teamB, scoreA, scoreB = re.findall('([A-Za-z]+)-([A-Za-z]+) ([0-9]+):([0-9]+)' , input ())[0 ] scoreA, scoreB = int (scoreA), int (scoreB) if scoreA == scoreB: count[teamA][0 ] += 1 count[teamB][0 ] += 1 else : count[teamA][0 ] += 3 if scoreA - scoreB > 0 else 0 count[teamA][1 ] += scoreA - scoreB count[teamB][0 ] += 3 if scoreB - scoreA > 0 else 0 count[teamB][1 ] += scoreB - scoreA count[teamA][2 ] += scoreA count[teamB][2 ] += scoreB tops = [] for name in count: tops.append((name, count[name])) tops.sort(key=lambda x: x[1 ][0 ]*10000 + x[1 ][1 ]*100 + x[1 ][2 ]) tops = sorted (tops[n//2 :], key=lambda x: x[0 ]) for item in tops: print (item[0 ])
F1 方程式冠军
结构体记录每位选手的名字、赢的次数和积分,先通过 map 统计得分情况,最后转入 vector 中排序输出:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 #include <bits/stdc++.h> using namespace std;const int extras[] = {25 , 18 , 15 , 12 , 10 , 8 , 6 , 4 , 2 , 1 , 0 };struct Player { string name; int extra = 0 ; int rank[100 ] = {0 }; Player () { } Player (const Player& src) { name = src.name, extra = src.extra; for (int i = 0 ; i < 100 ; i++) { rank[i] = src.rank[i]; } } }; int main () { int T; cin >> T; map<string, Player> score; while (T--) { int n; cin >> n; for (int i = 0 ; i < n; i++) { string name; cin >> name; score[name].name = name; score[name].extra += extras[min (i, 10 )]; score[name].rank[i]++; } } vector<Player> arr; for (auto item : score) { arr.push_back (item.second); } sort (arr.begin (), arr.end (), [] (Player a, Player b) { if (a.extra != b.extra) { return a.extra > b.extra; } for (int i = 0 ; i < 100 ; i++) { if (a.rank[i] != b.rank[i]) { return a.rank[i] > b.rank[i]; } } return false ; }); cout << arr[0 ].name << endl; sort (arr.begin (), arr.end (), [] (Player a, Player b) { if (a.rank[0 ] != b.rank[0 ]) { return a.rank[0 ] > b.rank[0 ]; } if (a.extra != b.extra) { return a.extra > b.extra; } for (int i = 1 ; i < 100 ; i++) { if (a.rank[i] != b.rank[i]) { return a.rank[i] > b.rank[i]; } } return false ; }); cout << arr[0 ].name << endl; return 0 ; }
买房与选房 —— 🈚️
二叉树遍历,从前序、中序到后序
从前序遍历可以得出当前区间的根节点,再在中序遍历中定位该根节点位置,从而划分出两颗子树,递归求解:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 #include <bits/stdc++.h> using namespace std;int n;char pre[100 ], mid[100 ];void dfs (int root, int l, int r) { if (l >= r) { return ; } int m = -1 ; for (int i = l; i < r; i++) { if (mid[i] == pre[root]) { m = i; break ; } } dfs (root+1 , l, m); dfs (root+(m-l)+1 , m+1 , r); putchar (pre[root]); } int main () { cin >> n; while (n) { for (int i = 0 ; i < n; i++) { cin >> pre[i]; } for (int i = 0 ; i < n; i++) { cin >> mid[i]; } dfs (0 , 0 , n); cout << endl; cin >> n; } return 0 ; }
内存管理
纯模拟题,使用链表完成,审清楚题目、标好注释一般不会错~~(就是可能超时)~~
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 #include <bits/stdc++.h> using namespace std;struct block { int id, L, R; block* next = NULL ; block (int id_, int L_, int R_) { id = id_, L = L_, R = R_; } }; int main () { int T, m; cin >> T >> m; int index = 1 ; block* head = new block (0 , -1 , 0 ); while (T--) { string opt; int arg; cin >> opt; if (opt == "alloc" ) { cin >> arg; bool flag = false ; for (block* ptr = head; ptr; ptr = ptr->next) { if (ptr -> next) { if (ptr->next->L - ptr->R >= arg) { block* tmp = new block (index++, ptr->R, ptr->R + arg); tmp -> next = ptr -> next; ptr -> next = tmp; cout << (tmp -> id) << endl; flag = true ; break ; } } else { if (ptr->R + arg <= m) { block* tmp = new block (index++, ptr->R, ptr->R + arg); ptr -> next = tmp; cout << (tmp -> id) << endl; flag = true ; break ; } } } if (!flag) { cout << "NULL" << endl; } } else if (opt == "erase" ) { cin >> arg; bool flag = false ; for (block* ptr = head; ptr->next; ptr = ptr->next) { if (ptr->next->id == arg) { block* tmp = ptr->next; ptr -> next = ptr -> next -> next; delete tmp; flag = true ; break ; } } if (!flag) { cout << "ILLEGAL_ERASE_ARGUMENT" << endl; } } else if (opt == "defragment" ) { for (block* ptr = head; ptr->next; ptr = ptr->next) { if (ptr->next->L > ptr->R) { int dist = ptr->next->L - ptr->R; ptr -> next -> L -= dist; ptr -> next -> R -= dist; } } } } return 0 ; }
平均方差
没啥难度,直接计算即可,注意输出时要强制转 int 而不能 printf("%.0lf", S/n - 0.5);
,否则会出现输出 -0
的问题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include <bits/stdc++.h> using namespace std;double sum, arr[10000 ];int main () { int n; cin >> n; while (n) { sum = 0 ; for (int i = 0 ; i < n; i++) { cin >> arr[i]; sum += arr[i]; } double avg = sum / n, S = 0 ; for (int i = 0 ; i < n; i++) { S += (arr[i]-avg)*(arr[i]-avg); } cout << (int )(S / n) << endl; cin >> n; } return 0 ; }
IP 地址
使用位运算是最快的解法,具体位运算的使用参考汉明距离 一章
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include <bits/stdc++.h> using namespace std;int count (int n) { int ans = 0 ; while (n) { n ^= (n & -n); ans++; } return ans; } int main () { int n; cin >> n; while (n--) { int arr[4 ]; scanf ("%d.%d.%d.%d" , &arr[0 ], &arr[1 ], &arr[2 ], &arr[3 ]); int sum = 0 ; for (int i = 0 ; i < 4 ; i++) { sum += count (arr[i]); } cout << sum << endl; } return 0 ; }
开关与灯
将输入矩阵纵向相加,得到「每个灯所对应的开关数」数组,然后使用一重循环,判断上述数组减去单个开关后,新的「每个灯对应的开关数」数组中是否存在 0,如果存在,则说明该开关不可去除,否则输出 Yes 并返回
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #include <bits/stdc++.h> using namespace std;int arr[2000 ] = {0 };bool button[2000 ][2000 ] = {0 };int main () { int n, m; cin >> n >> m; for (int i = 0 ; i < n; i++) { string str; cin >> str; for (int j = 0 ; j < m; j++) { if (str[j] == '1' ) { button[i][j] = 1 ; arr[j] += 1 ; } } } for (int i = 0 ; i < n; i++) { bool flag = true ; for (int j = 0 ; j < m; j++) { if (arr[j] <= button[i][j]) { flag = false ; break ; } } if (flag) { cout << "YES" << endl; return 0 ; } } cout << "NO" << endl; return 0 ; }
可删除的点
分别统计横坐标大于零和小于零的点的数量,并记为 L L L 、R R R ,只要 L L L 、R R R 不全大于 1 则有解
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #include <bits/stdc++.h> using namespace std;int main () { int n; cin >> n; int L = 0 , R = 0 ; for (int i = 0 ; i < n; i++) { int x, _; cin >> x >> _; x > 0 ? R++ : L++; } printf ((L <= 1 || R <= 1 ) ? "Yes" : "No" ); return 0 ; }
字符串反转3
最初的实现方式,直接用了 Python 现成的语法特性和内置函数:
1 2 3 4 5 n = int (input ()) for i in range (n): print (' ' .join(map (lambda x: x[::-1 ], input ().split())))
提交之后有一个点报超时,猜测可能存在卡常,遂改用 C++ 实现。维护一个字符栈,每次读入一个字符,如果不是空格或回车,则直接入栈;否则边出栈边输出,直到将整个栈清空,然后如果是回车,则退出循环
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include <bits/stdc++.h> using namespace std;int main () { int T; cin >> T; getchar (); while (T--) { stack<char > st; char ch; while (true ) { ch = getchar (); if (ch == '\n' || ch == ' ' ) { while (!st.empty ()) { putchar (st.top ()); st.pop (); } putchar (' ' ); if (ch == '\n' ) { putchar ('\n' ); break ; } } else { st.push (ch); } } } return 0 ; }
n, 还是n
STL 真好用 ,直接暴搜就能过(话说一百万真的不会超时嘛
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include <bits/stdc++.h> using namespace std;int main () { int n, m; cin >> m >> n; string n_str = to_string (n); for (int i = 1 ; i <= m; i++) { if (i % n == 0 ) { cout << i << " " ; } else if (~to_string (i).find (n_str)) { cout << i << " " ; } } return 0 ; }
字符串排序
虽然 n, m 都不大,但是保险起见,还是用一下缓存优化(防止 cmp 函数每次都计算无序度导致超时),外加 STL 中的 stable_sort(稳定排序)即可 AC
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #include <bits/stdc++.h> using namespace std;int n, m;struct pack { string str; int chaos = 0 ; void init () { for (int i = 0 ; i < n-1 ; i++) { for (int j = i+1 ; j < n; j++) { if (str[j] < str[i]) { chaos += 1 ; } } } } bool operator < (const pack& other) const { return chaos < other.chaos; } bool operator == (const pack& other) const { return str == other.str; } } arr[100 ]; int main () { cin >> n >> m; for (int i = 0 ; i < m ; i++) { cin >> arr[i].str; arr[i].init (); } stable_sort (arr, arr+m); for (int i = 0 ; i < m; i++) { cout << arr[i].str << endl; } return 0 ; }
三角形的面积
简单计算几何,下面给出计算公式(可计算任意多边形):
S = ∣ O P i → × O P i + 1 → 2 ∣ S = |\frac{\overrightarrow{OP_i}\times\overrightarrow{OP_{i+1}}}{2}|
S = ∣ 2 O P i × O P i + 1 ∣
其中 P i P_i P i 为该多边形第 i i i 个顶点的坐标 ( i ∈ [ 0 , n ) , P n = P 0 ) (i\in[0, n), P_n = P_0) ( i ∈ [ 0 , n ) , P n = P 0 ) ,直接套用公式算出答案:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include <bits/stdc++.h> using namespace std;double P[3 ][2 ]; int main () { while (true ) { for (int i = 0 ; i < 3 ; i++) { for (int j = 0 ; j < 2 ; j++) { scanf ("%lf" , &P[i][j]); } } if (!(P[0 ][0 ] || P[0 ][1 ] || P[1 ][0 ] || P[1 ][1 ] || P[2 ][0 ] || P[2 ][1 ])) { break ; } double sum = 0 ; for (int i = 0 ; i < 3 ; i++) { sum += P[i][0 ] * P[(i+1 )%3 ][1 ] - P[(i+1 )%3 ][0 ] * P[i][1 ]; } printf ("%.6lf\n" , abs (sum / 2 )); } return 0 ; }
或者直接对三角形的两条边做叉乘:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 #include <bits/stdc++.h> using namespace std;int main () { while (true ) { double x1, y1, x2, y2, x3, y3; scanf ("%lf %lf %lf %lf %lf %lf" , &x1, &y1, &x2, &y2, &x3, &y3); if (!(x1 || y1 || x2 || y2 || x3 || y3)) { break ; } double sum = (x2-x1) * (y3-y1) - (x3-x1) * (y2-y1); printf ("%.6lf\n" , abs (sum) / 2 ); } return 0 ; }
循环数
根据循环数的性质判断,循环数乘上它自己的 位数+1 会得到一串 9 【Wiki 传送门 】,另外特判一个 0 即可:
1 2 3 4 5 6 7 8 9 10 num = input () if int (num): if set (str (int (num) * (len (num)+1 ))) == {'9' }: print ('Yes' ) else : print ('No' ) else : print ('Yes' )
电能消耗
l i l_i l i 、r i r_i r i 均不大于 1440,无需使用数学计算加速,直接暴力模拟每分钟的电量消耗即可。此外题目描述有误,汤姆使用电脑的时间周期应为左闭合区间 [ l 1 , r 1 ) [l_1, r_1) [ l 1 , r 1 ) 、[ l 2 , r 2 ) [l_2, r_2) [ l 2 , r 2 ) 、……、[ l n , r n ) [l_n, r_n) [ l n , r n )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 #include <bits/stdc++.h> using namespace std;bool work[2000 ] = {0 }; int main () { int n, p1, p2, p3, t1, t2; cin >> n >> p1 >> p2 >> p3 >> t1 >> t2; int L, R; for (int i = 0 ; i < n; i++) { int l, r; cin >> l >> r; (i == 0 ) && (L = l); (i == n-1 ) && (R = r); for (int j = l; j < r; j++) { work[j] = 1 ; } } int sum = 0 , idle; for (int i = L; i < R; i++) { if (work[i]) { idle = 0 ; sum += p1; } else { if (idle >= t1 + t2) { sum += p3; } else if (idle >= t1) { sum += p2; } else { sum += p1; } idle++; } } cout << sum << endl; return 0 ; }
计算校验码
根据题目最后的 Tips,不难发现无论输入的 N
是几进制数,都不会对各位数字之和产生影响,不妨设各位数字之和为 x x x ,校验码为 m m m ,可得:
m = [ ( B − 1 ) − x mod ( B − 1 ) ] mod ( B − 1 ) m = [(B-1) - x \text{ mod } (B-1) ]\text{ mod }(B-1)
m = [( B − 1 ) − x mod ( B − 1 )] mod ( B − 1 )
据此编写代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 #include <bits/stdc++.h> using namespace std;int sum_count (string str) { int sum = 0 ; for (char ch : str) { if ('0' <= ch && ch <= '9' ) { sum += ch - '0' ; } else { sum += 10 + ch - 'a' ; } } return sum; } int main () { int T; cin >> T; const string digits = "0123456789abcdef" ; while (T--) { int B; string N; cin >> B >> N; int m = ((B-1 ) - sum_count (N) % (B-1 )) % (B-1 ); cout << digits[m] << endl; } return 0 ; }
训练作业二
字符串反转2
依旧先试 Python 硬怼,这一次没有超时:
1 2 3 4 5 try : while True : print (' ' .join(input ().split()[::-1 ])) except EOFError: pass
487-3279
每次输入电话号码后先格式化,然后使用 STL 中的 map 统计频次,最后选取频次大于 1 的输出即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include <bits/stdc++.h> using namespace std;int main () { int n; cin >> n; map<string, int > count; while (n--) { string str, wrap; cin >> str; for (char ch : str) { if ('A' <= ch && ch <= 'Z' ) { (ch >= 'Q' ) && ch--; wrap += (ch-'A' )/3 + '2' ; } else if ('0' <= ch && ch <= '9' ) { wrap += ch; } } count[wrap] += 1 ; } for (auto item : count) { if (item.second > 1 ) { for (int i = 0 ; i < 3 ; i++) { putchar (item.first[i]); } putchar ('-' ); for (int i = 3 ; i < 7 ; i++) { putchar (item.first[i]); } cout << " " << item.second << endl; } } return 0 ; }
缺席考试的是谁?
对所有名字作一次异或运算,最后剩下的即为缺席学生的姓名,很神奇吧
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include <bits/stdc++.h> using namespace std;int main () { int n; cin >> n; while (n) { char name[64 ] = {0 }; for (int i = 0 ; i < 2 *n-1 ; i++) { char tmp[64 ]; scanf ("%s" , tmp); for (int j = 0 ; tmp[j]; j++) { name[j] ^= tmp[j]; } } printf ("%s\n" , name); cin >> n; } return 0 ; }
电话号码
使用字典树存储电话号码的逆,可以很方便的去除重复的电话号码,对所有朋友分别建一棵字典树,存入逆序的电话号码后直接排序输出即可(注意题目要求是先按长度,再按数字大小排序)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 #include <bits/stdc++.h> using namespace std;struct Trie { char ch = '\0' ; Trie* next[10 ] = {0 }; void insert (const string& str, int pos=0 ) { if (pos < str.size ()) { int index = str[pos] - '0' ; if (!next[index]) { next[index] = new Trie; next[index] -> ch = str[pos]; } next[index] -> insert (str, pos+1 ); } } void count (vector<string>& arr, string str="" ) { bool flag = false ; for (int i = 0 ; i < 10 ; i++) { if (next[i]) { flag = true ; next[i] -> count (arr, ch ? ch + str : str); } } if (!flag) { arr.push_back (ch+str); } } }; map<string, Trie> book; int main () { int T; cin >> T; while (T--) { string name; int n; cin >> name >> n; for (int i = 0 ; i < n; i++) { string phone; cin >> phone; reverse (phone.begin (), phone.end ()); book[name].insert (phone); } } cout << book.size () << endl; for (auto record : book) { vector<string> arr; record.second.count (arr); sort (arr.begin (), arr.end (), [] (const string& a, const string& b) { if (a.size () < b.size ()) return true ; return atoi (a.c_str ()) < atoi (b.c_str ()); }); cout << record.first << " " << arr.size () << " " ; for (auto name : arr) { cout << name << " " ; } cout << endl; } return 0 ; }
点球大战
模拟即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 #include <bits/stdc++.h> using namespace std;int main () { int n; cin >> n; while (n) { char result[10 ][2 ] = {0 }; for (int i = 0 ; i < n; i++) { string str; do { cin >> str; } while (str != "no" && str != "good" ); if (str == "no" ) { result[i >> 1 ][i & 1 ] = 'X' ; cin >> str; } else { result[i >> 1 ][i & 1 ] = 'O' ; } } for (int i = 0 ; i < (n + 1 )/2 ; i++) { cout << (i + 1 ) << " " ; } cout << "Score" << endl; for (int i = 0 ; i < 2 ; i++) { int cnt = 0 ; for (int j = 0 ; j < (n + 1 )/2 ; j++) { if (result[j][i]) { cnt += result[j][i] == 'O' ; cout << result[j][i] << " " ; } else { cout << "- " ; } } cout << cnt << endl; } cin >> n; } return 0 ; }
飞行棋
模拟题,一个比较方便的技巧是将棋盘直接初始化为应该跳转到的格
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 #include <bits/stdc++.h> using namespace std;struct Random { int a, b, f; Random (int a_, int b_, int c_) { a = a_, b = b_, f = c_; } int operator () () { f = (a*f + b) % 6 + 1 ; return f; } }; int main () { int n, a, b, c; while (cin >> n >> a >> b >> c) { int gmap[200 ] = {0 }; for (int i = 0 ; i < n; i++) { string str; cin >> str; if (str[0 ] == 'N' ) { gmap[i] = i; } else { gmap[i] = atoi (str.substr (1 , string::npos).c_str ()); } } auto dice = Random (a, b, c); int pos[2 ] = {0 }; for (int i = 0 , i_ = 0 ; ; i_++, i = i_ & 1 ) { pos[i] += dice (); while (pos[i] >= n || pos[i] < 0 ) { (pos[i] >= n) && (pos[i] = 2 *(n-1 )-pos[i]); (pos[i] < 0 ) && (pos[i] = -pos[i]); } pos[i] = gmap[pos[i]]; if (pos[i] == n-1 ) { printf ("%s\n" , i & 1 ? "Yueyue" : "Lele" ); break ; } if (pos[i] == pos[!i]) { pos[!i] = 0 ; } } } return 0 ; }
棋盘
动态规划题,用 map[][]
存储输入数据,数组 F1[i][j]
表示以 [i, j]
为右下角的最大黑色网格(主对角线为黑色)大小,类似地 F2[i][j]
表示最大白色网格的大小,那么可以导出递推式:
F 1 [ i , 0 ] = F 1 [ 0 , j ] = F 2 [ i , 0 ] = F 2 [ 0 , j ] = 0 F_1[i, 0] = F_1[0, j] = F_2[i, 0] = F_2[0, j] = 0
F 1 [ i , 0 ] = F 1 [ 0 , j ] = F 2 [ i , 0 ] = F 2 [ 0 , j ] = 0
F 1 [ i , j ] = { min ( F 1 [ i − 1 , j − 1 ] , F 2 [ i − 1 , j ] , F 2 [ i , j − 1 ] ) + 1 0 , ( m a p [ i ] [ j ] = 0 ) F_1[i, j] = \begin{cases}
\min(F_1[i-1, j-1], F_2[i-1, j], F_2[i, j-1]) + 1 \\
0, (map[i][j] = 0)
\end{cases}
F 1 [ i , j ] = { min ( F 1 [ i − 1 , j − 1 ] , F 2 [ i − 1 , j ] , F 2 [ i , j − 1 ]) + 1 0 , ( ma p [ i ] [ j ] = 0 )
F 2 [ i ] [ j ] = { min ( F 2 [ i − 1 , j − 1 ] , F 1 [ i − 1 , j ] , F 1 [ i , j − 1 ] ) + 1 0 , ( m a p [ i ] [ j ] = 0 ) F_2[i][j] = \begin{cases}
\min(F_2[i-1, j-1], F_1[i-1, j], F_1[i, j-1]) + 1 \\
0, (map[i][j] = 0)
\end{cases}
F 2 [ i ] [ j ] = { min ( F 2 [ i − 1 , j − 1 ] , F 1 [ i − 1 , j ] , F 1 [ i , j − 1 ]) + 1 0 , ( ma p [ i ] [ j ] = 0 )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 #include <bits/stdc++.h> using namespace std;bool gmap[2001 ][2001 ] = {0 };int F1[2001 ][2001 ] = {0 }, F2[2001 ][2001 ] = {0 }; int main () { int n; cin >> n; getchar (); for (int i = 1 ; i <= n; i++) { for (int j = 1 ; j <= n; j++) { gmap[i][j] = getchar () - '0' ; } getchar (); } int max_size = 0 ; for (int i = 1 ; i <= n; i++) { for (int j = 1 ; j <= n; j++) { if (gmap[i][j]) { F1[i][j] = min (F1[i-1 ][j-1 ], min (F2[i-1 ][j], F2[i][j-1 ])) + 1 ; F2[i][j] = 0 ; } else { F2[i][j] = min (F2[i-1 ][j-1 ], min (F1[i-1 ][j], F1[i][j-1 ])) + 1 ; F1[i][j] = 0 ; } max_size = max (max_size, F1[i][j]); } } int count = 0 ; for (int i = 1 ; i <= n; i++) { for (int j = 1 ; j <= n; j++) { if (F1[i][j] == max_size) { count++; } } } cout << max_size << " " << count << endl; return 0 ; }
Engine-字符串
模拟题,直接 Python 过了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Paper (object ): def __init__ (self ): self.title = input () self.keys = set (s.lower() for s in self.title.split()) self.refers = int (input ()) def query (keywords ): return lambda p: all (word in p.keys for word in keywords) def main (): n = int (input ()) while n: papers = [] for i in range (n): papers.append(Paper()) m = int (input ()) for i in range (m): title = input () keywords = [word.lower() for word in title.split()] for p in sorted (filter (query(keywords), papers), key=lambda x: -x.refers): print (p.title) print ('***' ) print ('---' ) n = int (input ()) if __name__ == '__main__' : main()
字符串压缩
动态规划题,如果用数组 F 1 [ i ] F_1[i] F 1 [ i ] 表示以第 i i i 个字符结尾的子串所需的最小钱币数,那么不难想到下面的递推式:
F [ i ] = min ( F [ i − 1 ] + a , min { F [ i − l e n ] } + b ) F[i] = \min(F[i-1] + a, \min\{F[i-len]\} + b)
F [ i ] = min ( F [ i − 1 ] + a , min { F [ i − l e n ]} + b )
解释:
此时发现题目的一个 bug 点,题目描述中没有说明 b ≤ a b\leq a b ≤ a ,那么如果 b > a b > a b > a ,就没有办法证明取最长公共后缀的最优子结构性质,于是没法在 O ( n 2 ) O(n^2) O ( n 2 ) 的时间内解决问题,导致超时(也许是我太菜了没想到)
由于我太懒了,不想慢慢研究最长公共后缀的 DP(O ( n 2 ) O(n^2) O ( n 2 ) 解法),这里放一个传送门 ,然后我将使用 O ( n 3 ) O(n^3) O ( n 3 ) 的暴力方法求解:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include <bits/stdc++.h> using namespace std;int main () { int n, a, b; string str; cin >> n >> a >> b >> str; vector<int > F (n) ; F[0 ] = a; for (int i = 1 ; i < n; i++) { F[i] = F[i-1 ] + a; for (int j = 1 ; j*2 <= i+1 ; j++) { string&& L = str.substr (0 , i+1 -j); string&& R = str.substr (i+1 -j, j); if (L.find (R) != string::npos) { F[i] = min (F[i], F[i-j] + b); } } } cout << F[str.size () - 1 ] << endl; return 0 ; }
拼写检查
经典动态规划问题——编辑距离,稍微做些优化直接搬上来用就行了,它的状态转移方程为:
F [ 0 , i ] = F [ i , 0 ] = i F[0, i] = F[i, 0] = i
F [ 0 , i ] = F [ i , 0 ] = i
F [ i , j ] = min ( F [ i − 1 ] [ j ] + 1 , F [ i ] [ j − 1 ] + 1 , F [ i − 1 ] [ j − 1 ] + ( a [ i ] ! = b [ j ] ) ) F[i, j] = \min(F[i-1][j] + 1, F[i][j-1] + 1, F[i-1][j-1] + (a[i] != b[j]))
F [ i , j ] = min ( F [ i − 1 ] [ j ] + 1 , F [ i ] [ j − 1 ] + 1 , F [ i − 1 ] [ j − 1 ] + ( a [ i ]! = b [ j ]))
其中 F [ i , j ] F[i,j] F [ i , j ] 表示字符串 a
的前 i
个字符组成的子串和字符串 b+1
的前 j+1
个字符
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 #include <bits/stdc++.h> using namespace std;bool canfix (string src, string dst) { int F[20 ][20 ] = {0 }; int s_len = src.size (), d_len = dst.size (); for (int i = 0 ; i < 20 ; i++) { F[i][0 ] = F[0 ][i] = i; } for (int i = 0 ; i < s_len; i++) { for (int j = 0 ; j < d_len; j++) { F[i+1 ][j+1 ] = min (F[i][j], min (F[i][j+1 ], F[i+1 ][j])) + 1 ; if (src[i] == dst[j]) { F[i+1 ][j+1 ] = min (F[i+1 ][j+1 ], F[i][j]); } } } return F[s_len][d_len] <= 1 ; } vector<string> dict; int main () { string word; cin >> word; while (word != "#" ) { dict.push_back (word); cin >> word; } cin >> word; while (word != "#" ) { if (find (dict.begin (), dict.end (), word) != dict.end ()) { cout << word << " is correct" << endl; } else { cout << word << ": " ; for (string str : dict) { if (canfix (word, str)) { cout << str << " " ; } } cout << endl; } cin >> word; } return 0 ; }
更新:BK 树解法(最后一个排序做得比较随意,懒得慢慢改树了)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 #include <bits/stdc++.h> using namespace std;int edt (const string& src, const string& dst) { int F[20 ][20 ] = {0 }; int s_len = src.size (), d_len = dst.size (); for (int i = 0 ; i < 20 ; i++) { F[i][0 ] = F[0 ][i] = i; } for (int i = 0 ; i < s_len; i++) { for (int j = 0 ; j < d_len; j++) { F[i+1 ][j+1 ] = min (F[i][j], min (F[i][j+1 ], F[i+1 ][j])) + 1 ; if (src[i] == dst[j]) { F[i+1 ][j+1 ] = min (F[i+1 ][j+1 ], F[i][j]); } } } return F[s_len][d_len]; } struct bk_tree { string word; map<int , bk_tree> child; void insert (const string& str) { int ed_root = edt (word, str); if (child.find (ed_root) == child.end ()) { child[ed_root] = {str}; } else { child[ed_root].insert (str); } } void query (const string& str, vector<string>& res) { int ed_root = edt (word, str); if (ed_root <= 1 ) res.push_back (word); for (auto item : child) { if (item.first >= ed_root - 1 && ed_root <= ed_root + 1 ) { item.second.query (str, res); } } } }; int main () { string str; cin >> str; bk_tree dict = {"#:#:#" }; set<string> cnt; map<string, int > weight; int index = 0 ; while (str != "#" ) { dict.insert (str), cnt.insert (str); weight[str] = index++; cin >> str; } cin >> str; while (str != "#" ) { if (cnt.find (str) != cnt.end ()) { cout << str << " is correct" << endl; } else { cout << str << ": " ; vector<string> arr; dict.query (str, arr); sort (arr.begin (), arr.end (), [&weight] (const string& a, const string& b) { return weight[a] < weight[b]; }); for (auto fix : arr) { cout << fix << " " ; } cout << endl; } cin >> str; } return 0 ; }
最小的 K 个数
按题目提示做即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include <bits/stdc++.h> using namespace std;set<int > data; int main () { int n, k; cin >> n >> k; while (n--) { int tmp; cin >> tmp; data.insert (tmp); } for (auto it = data.begin (); k-- && it != data.end (); it++) { cout << *it << " " ; } return 0 ; }
绩点计算
按题目意思算即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #include <bits/stdc++.h> using namespace std;float mark2point (int mark) { if (mark >= 90 ) return 4.0 ; if (mark >= 85 ) return 3.7 ; if (mark >= 82 ) return 3.3 ; if (mark >= 78 ) return 3.0 ; if (mark >= 75 ) return 2.7 ; if (mark >= 72 ) return 2.3 ; if (mark >= 68 ) return 2.0 ; if (mark >= 64 ) return 1.5 ; if (mark >= 60 ) return 1.0 ; return 0 ; } int main () { int n; cin >> n; int weight[1000 ]; float sum_weight = 0 , sum_mp = 0 ; for (int i = 0 ; i < n; i++) { cin >> weight[i]; sum_weight += weight[i]; } for (int i = 0 ; i < n; i++) { int mark; cin >> mark; sum_mp += weight[i] * mark2point (mark); } printf ("%.2f" , sum_mp / sum_weight); return 0 ; }
xxx定律
直接模拟
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include <bits/stdc++.h> using namespace std;int main () { int n; cin >> n; while (n) { int step = 0 ; while (n != 1 ) { if (n & 1 ) { n = 3 *n + 1 ; } n >>= 1 ; step++; } cout << step << endl; cin >> n; } return 0 ; }
数的距离差
对题中距离差定义简单整理,可知 x 是数组中与 m a x + m i n 2 \frac{max+min}{2} 2 ma x + min 最接近的那个数,这里直接 O ( n log n ) O(n\log n) O ( n log n ) 求解:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include <bits/stdc++.h> using namespace std;int main () { int n; cin >> n; vector<int > arr; for (int i = 0 ; i < n; i++) { int tmp; cin >> tmp; arr.push_back (tmp); } sort (arr.begin (), arr.end ()); float m = (float ) (arr[0 ] + arr[arr.size ()-1 ]) / 2 ; for (auto it = arr.rbegin (); it != arr.rend (); it++) { if (*it <= m) { cout << *it << endl; break ; } } return 0 ; }
亲和数
直接暴力:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 #include <bits/stdc++.h> using namespace std;int factor_sum (int n) { int sum = 0 ; for (int i = 1 ; i*2 <= n; i++) { if (n % i == 0 ) { sum += i; } } return sum; } int main () { int A, B; while (cin >> A >> B) { if (factor_sum (B) == A && factor_sum (A) == B) { cout << "YES" << endl; } else { cout << "NO" << endl; } } return 0 ; }
金币
暴力计算即可,但要注意将之前的计算结果保存下来,防止重复计算导致超时
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include <bits/stdc++.h> using namespace std;int now = 0 ;vector<int > arr = {0 }; void update (int n) { while (arr.size () <= n) { now += 1 ; for (int i = 0 ; i < now; i++) { arr.push_back (*arr.rbegin () + now); } } } int main () { int n; while (cin >> n) { update (n); cout << n << " " << arr[n] << endl; } return 0 ; }
小 A 的计算器
不必写进制转换,直接在数组上做加法,逆序存储(个位在最前)可以大幅优化进位效率
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include <bits/stdc++.h> using namespace std;int main () { int n; cin >> n; while (n--) { string a, b; cin >> a >> b; int len_a = a.size (), len_b = b.size (); int ans[1000 ] = {0 }; for (int i = 0 ; i < len_a; i++) { ans[i] += a[len_a-i-1 ] - 'a' ; } for (int i = 0 ; i < len_b; i++) { ans[i] += b[len_b-i-1 ] - 'a' ; } stack<char > st; for (int i = 0 ; ans[i]; i++) { if (ans[i] >= 26 ) { ans[i+1 ] += ans[i] / 26 ; ans[i] %= 26 ; } st.push (ans[i] + 'a' ); } while (!st.empty ()) { putchar (st.top ()); st.pop (); } cout << endl; } return 0 ; }
小丑排序
从头开始,每次走两步并输出,碰到数组尾端后返回,继续输出之前没输出过的名字:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include <bits/stdc++.h> using namespace std;int main () { string arr[20 ]; int n, T = 1 ; cin >> n; while (n) { cout << "set-" << T++ << endl; for (int i = 0 ; i < n; i++) { cin >> arr[i]; } int vst[20 ] = {0 }; for (int i = 0 ; i < n; i += 2 ) { cout << arr[i] << endl; vst[i] = 1 ; } for (int i = n-1 ; i > 0 ; i--) { if (!vst[i]) { cout << arr[i] << endl; } } cin >> n; } return 0 ; }
数圈
先求出中心坐标,然后向外旋转填数,最后整体输出
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #include <bits/stdc++.h> using namespace std;int arr[11 ][11 ] = {0 };int ways[4 ][2 ] = {{1 , 0 }, {0 , -1 }, {-1 , 0 }, {0 , 1 }}, dir = 3 ;void fill (int n) { int x, y, cnt = 1 ; x = y = (n-1 )/2 ; for (int i = 1 ; ; i++) { for (int j = 0 ; j < 2 ; j++) { for (int k = 0 ; k < i; k++) { arr[x][y] = cnt++; if (cnt > n * n) { return ; } x += ways[dir][0 ], y += ways[dir][1 ]; } dir = (dir + 1 ) % 4 ; } } } int main () { int n; cin >> n; fill (n); for (int i = 0 ; i < n; i++) { for (int j = 0 ; j < n; j++) { cout << arr[i][j] << " " ; } cout << endl; } return 0 ; }
锤子剪刀布
直接模拟并记录比赛结果,这题代码写得比较长,但应该逻辑都挺清晰
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 #include <bits/stdc++.h> using namespace std;inline char read () { char ch = getchar (); while (ch < 'A' || ch > 'Z' ) { ch = getchar (); } return ch; } int win_A[3 ] = {0 }, win_B[3 ] = {0 };int main () { int n; cin >> n; for (int i = 0 ; i < n; i++) { char A = read (), B = read (); if (A == 'B' && B == 'C' ) { win_A[0 ]++; } else if (A == 'C' && B == 'J' ) { win_A[1 ]++; } else if (A == 'J' && B == 'B' ) { win_A[2 ]++; } if (B == 'B' && A == 'C' ) { win_B[0 ]++; } else if (B == 'C' && A == 'J' ) { win_B[1 ]++; } else if (B == 'J' && A == 'B' ) { win_B[2 ]++; } } int sum_A = win_A[0 ] + win_A[1 ] + win_A[2 ]; int sum_B = win_B[0 ] + win_B[1 ] + win_B[2 ]; printf ("%d %d %d\n" , sum_A, n-sum_A-sum_B, sum_B); printf ("%d %d %d\n" , sum_B, n-sum_A-sum_B, sum_A); char most_A, most_B; int max_A = -1 , max_B = -1 ; for (int i = 0 ; i < 3 ; i++) { if (win_A[i] > max_A) { max_A = win_A[i]; most_A = "BCJ" [i]; } if (win_B[i] > max_B) { max_B = win_B[i]; most_B = "BCJ" [i]; } } cout << most_A << " " << most_B; return 0 ; }
新型冠状病毒(COVID19)传播
想要直接计算出所有的感染者难度过大,那么不妨反向思考,找出不可能被感染的人,然后用总人数减去,同样也可以得到最终答案
不难发现,以下两类人一定会被感染:
开始时跑在感染者后面,且速度大于感染者
开始时跑在感染者前面,且速度小于感染者
当这两类人被感染之后,又成为新的感染者,随着时间的推进,已经被感染的人又会去感染其他人;有没有新的人被感染,是根据当前已经被感染的人的最大和最小速度决定的,随之可以注意到,以下两类人永远不会被感染:
通过一次循环统计出最大和最小速度,然后再用一重循环统计不可能感染的人数即可:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 #include <bits/stdc++.h> #define inf 0x7fffffff using namespace std;int main () { int n, k; cin >> n >> k; k--; vector<int > s (n) , v (n) ; for (int i = 0 ; i < n; i++) { cin >> s[i]; } for (int i = 0 ; i < n; i++) { cin >> v[i]; } int v_min = inf, v_max = 0 ; for (int i = 0 ; i < n; i++) { if (s[i] <= s[k]) { v_max = max (v_max, v[i]); } if (s[i] >= s[k]) { v_min = min (v_min, v[i]); } } int impossible = 0 ; for (int i = 0 ; i < n; i++) { if (s[i] > s[k] && v[i] >= v_max) { impossible++; } if (s[i] < s[k] && v[i] <= v_min) { impossible++; } } cout << (n - impossible) << endl; return 0 ; }
训练作业三
部分 A + B
先按字符串读入,然后遍历取出 P A P_A P A 和 P B P_B P B ,最后相加
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include <bits/stdc++.h> using namespace std;int main () { string sA, dA, sB, dB; cin >> sA >> dA >> sB >> dB; int A = 0 , B = 0 ; for (char ch : sA) { if (ch == dA[0 ]) { A = A * 10 + ch - '0' ; } } for (char ch : sB) { if (ch == dB[0 ]) { B = B * 10 + ch - '0' ; } } cout << A + B << endl; return 0 ; }
导弹防御系统
经典动态规划问题,定义 F [ i ] F[i] F [ i ] 表示必须拦截第 i i i 颗导弹的前提下最多能拦截的导弹数,易得状态转移方程:
F [ i ] = max ( 1 , max ( F [ i − j ] ) + 1 ) , ( a r r [ j ] > = a r r [ i ] ) ) F[i] = \max(1, \max(F[i-j]) + 1), (arr[j] >= arr[i]))
F [ i ] = max ( 1 , max ( F [ i − j ]) + 1 ) , ( a rr [ j ] >= a rr [ i ]))
初始化数组 F[]
为 1,然后按上述方程演算:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include <bits/stdc++.h> using namespace std;int main () { int n; cin >> n; vector<int > arr (n) ; for (int i = 0 ; i < n; i++) { cin >> arr[i]; } vector<int > F (n, 1 ) ; for (int i = 1 ; i < n; i++) { for (int j = 0 ; j < i; j++) { if (arr[j] >= arr[i]) { F[i] = max (F[i], F[j] + 1 ); } } } cout << *max_element (F.begin (), F.end ()) << endl; return 0 ; }
魔咒词典
字符串处理的题当然要用 Python 啦 ,使用正则表达式 从输入字符串提取出魔咒和功能说明,然后正反向均建立映射,查询时输出即可(其实 C++ 也有正则表达式相关的库澳):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 import rebook = {} while True : line = input () if line == '@END@' : break word, func = re.findall(r'(\[.*]) (.*)' , line)[0 ] book[word] = func book[func] = word[1 :-1 ] n = int (input ()) for i in range (n): line = input () if line in book: print (book[line]) else : print ('what?' )
打牌
首先统计每种牌的数量,然后每次输入一行对手的出牌,如果不是顺子(长度 < 5),则按普通规则,否则按顺子规则判断,具体实现看下面代码中的注释:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 raw = input () my_cards = [raw.count(str (x)) for x in range (1 , 10 )] try : while True : line = input () first, length, ans = line[0 ], len (line), [] if length < 5 : for i in range (int (first), 9 ): if my_cards[i] >= length: ans.append(str (i+1 ) * length) else : for i in range (int (first), 5 ): if all (my_cards[i:i+5 ]): ans.append(str (i * 11111 + 12345 )) if ans: print ('YES' , ' ' .join(ans)) else : print ('NO' ) except EOFError: pass
最大报销额
题目描述不清不楚的,不想写了
带通配符的数
递归求解,主要逻辑有三条(其实就是整数比较大小的规则):
如果 W W W 的某一位与 X X X 的相同,那么他们的大小由后面的位决定
如果 W W W 的某一位比 X X X 的小,那么后面无论怎么取都不可能使 W > X W > X W > X
如果 W W W 的某一位比 X X X 的大,那么后面的所有「?」都可以随意取值(0 ~ 9)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include <bits/stdc++.h> using namespace std;int dfs (const string& str, const string& raw, int index=0 ) { if (index > str.size ()) { return 0 ; } if (str[index] == '?' ) { int sum = 0 , cnt = 1 ; for (int i = index + 1 ; i < str.size (); i++) { (str[i] == '?' ) && (cnt *= 10 ); } sum += cnt * ('9' - raw[index]); sum += dfs (str, raw, index + 1 ); return sum; } else { if (str[index] == raw[index]) { return dfs (str, raw, index + 1 ); } if (str[index] > raw[index]) { int cnt = 1 ; for (int i = index + 1 ; i < str.size (); i++) { (str[i] == '?' ) && (cnt *= 10 ); } return cnt; } return 0 ; } } int main () { string str, raw; while (cin >> str >> raw) { cout << dfs (str, raw) << endl; } return 0 ; }
愚人节的礼物
遍历字符串,遇左括号计数器 +1,右括号 -1,礼物 B 出现时计数器的值即为层数:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 #include <bits/stdc++.h> using namespace std;void unpack (string str) { int cnt = 0 ; for (char ch : str) { if (ch == '(' ) { cnt += 1 ; } else if (ch == ')' ) { cnt -= 1 ; } else { cout << cnt << endl; return ; } } } int main () { string str; while (cin >> str) { unpack (str); } return 0 ; }
ab 串
这是一道动态规划题(虽然不知道为啥算法标签是前缀和,可能有更妙的方法?)。将 dp 过程中查找的字符串分为 3 个状态,状态 A 为只有 a 的串(aa……a),状态 B 为 a 和 b 的串(aa……aabb……bb),状态 C 为题目要求的串(aaa……aabb……bbaa……aaa)。
设 F [ i , j ] F[i, j] F [ i , j ] 表示在状态 i 下,前 j 个字符中所能取到的最大长度,那么对于状态 A,从 0 到 j 位中字符 'a'
的个数即为其值;而对于状态 B 和 C,分两种情况讨论:
第 j 个字符为对应状态的最后一个字符(状态 B 为 'b'
,状态 C 为 'a'
):
直接从左边转移,即 F [ i , j ] = F [ i , j − 1 ] + 1 F[i, j] = F[i, j-1] + 1 F [ i , j ] = F [ i , j − 1 ] + 1
从左边和上一状态转移,即: F [ i , j ] = max ( F [ i , j − 1 ] , F [ i − 1 , j ] ) F[i, j] = \max(F[i, j-1], F[i-1, j]) F [ i , j ] = max ( F [ i , j − 1 ] , F [ i − 1 , j ])
依照上述三条规则,将数组 F[][]
推演到 F[2][len]
即可得到答案:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #include <bits/stdc++.h> using namespace std;int F[3 ][5001 ] = {0 };int main () { string str; cin >> str; int length = str.size (); for (int i = 1 ; i <= length; i++) { F[0 ][i] = F[0 ][i-1 ] + (str[i-1 ] == 'a' ); } for (int i = 1 ; i <= length; i++) { if (str[i-1 ] == 'b' ) { F[1 ][i] = F[1 ][i-1 ] + 1 ; } else { F[1 ][i] = max (F[1 ][i-1 ], F[0 ][i]); } } for (int i = 1 ; i <= length; i++) { if (str[i-1 ] == 'a' ) { F[2 ][i] = F[2 ][i-1 ] + 1 ; } else { F[2 ][i] = max (F[2 ][i-1 ], F[1 ][i]); } } cout << F[2 ][length] << endl; return 0 ; }
占座位
与 1-10 的内存管理 几乎如出一辙,直接拿来改改交了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 #include <bits/stdc++.h> using namespace std;struct block { int id, L, R; block* next = NULL ; block (int id_, int L_, int R_) { id = id_, L = L_, R = R_; } }; int main () { int n, _, T; cin >> n >> _ >> T; block* head = new block (0 , -1 , 0 ); set<int > record; while (T--) { string opt; int id; cin >> opt >> id; if (opt == "in" ) { int arg; cin >> arg; if (record.find (id) != record.end ()) { cout << "no" << endl; continue ; } record.insert (id); bool flag = false ; for (block* ptr = head; ptr; ptr = ptr->next) { if (ptr -> next) { if (ptr->next->L - ptr->R >= arg) { block* tmp = new block (id, ptr->R, ptr->R + arg); tmp -> next = ptr -> next; ptr -> next = tmp; cout << "yes" << endl; flag = true ; break ; } } else { if (ptr->R + arg <= n*n) { block* tmp = new block (id, ptr->R, ptr->R + arg); ptr -> next = tmp; cout << "yes" << endl; flag = true ; break ; } } } if (!flag) { record.erase (id); cout << "no" << endl; } } else if (opt == "out" ) { bool flag = false ; for (block* ptr = head; ptr->next; ptr = ptr->next) { if (ptr->next->id == id) { block* tmp = ptr->next; ptr -> next = ptr -> next -> next; delete tmp; flag = true ; record.erase (id); break ; } } if (flag) { cout << "yes" << endl; } else { cout << "no" << endl; } } } return 0 ; }
Maya 历法
字符串题怎么能不用 Python 呢?先根据 Haab 历法的日期算出从世界的开始到现在的总天数,然后再转为 Tzolkin 历法的日期输出:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 import reHaab = [ 'pop' , 'no' , 'zip' , 'zotz' , 'tzec' , 'xul' , 'yoxkin' , 'mol' , 'chen' , 'yax' , 'zac' , 'ceh' , 'mac' , 'kankin' , 'muan' , 'pax' , 'koyab' , 'cumhu' , 'uayet' ] Tzolkin = [ 'imix' , 'ik' , 'akbal' , 'kan' , 'chicchan' , 'cimi' , 'manik' , 'lamat' , 'muluk' , 'ok' , 'chuen' , 'eb' , 'ben' , 'ix' , 'mem' , 'cib' , 'caban' , 'eznab' , 'canac' , 'ahau' ] n = int (input ()) for _ in range (n): day, month, year = re.search(r'(\d+)\.([a-z]+) (\d+)' , input ()).groups() total = int (year)*365 + 20 *Haab.index(month) + int (day) day, month, year = total % 13 + 1 , Tzolkin[total % 20 ], total // 260 print (day, month, year)
数码管
使用一个七位二进制数 表示字符在数码管中的形状(对应位点亮为 1,否则为 0),然后若两个数字仅通过加减笔画的方式转换,设它们的段码分别为 A A A 、B B B ,则有:
A\text{ | }B = \max(A, B)
\qquad
A\text{ & }B = \min(A, B)
依此性质编写代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include <bits/stdc++.h> using namespace std;const int digits[] = { 0b1110111 , 0b0100100 , 0b1011101 , 0b1101101 , 0b0101110 , 0b1101011 , 0b1111011 , 0b0100101 , 0b1111111 , 0b1101111 }; int main () { while (true ) { int now; cin >> now; if (!~now) break ; bool flag = true ; for (int i = 1 ; i < 10 ; i++) { int tmp; cin >> tmp; if ((digits[now] & digits[tmp]) != min (digits[now], digits[tmp]) || (digits[now] | digits[tmp]) != max (digits[now], digits[tmp])) { flag = false ; } now = tmp; } cout << (flag ? "YES" : "NO" ) << endl; } return 0 ; }
多项式加法
用 map 处理次数和系数的对应关系,注意输出的时候排除掉相加后正好为 0 的项即可:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include <bits/stdc++.h> using namespace std;int main () { int x, c; map<int , int , greater<int >> ans; for (int i = 0 ; i < 2 ; i++) { cin >> x >> c; while (x | c) { ans[x] += c; cin >> x >> c; } } for (auto item : ans) { if (item.second) { cout << item.first << " " << item.second << endl; } } return 0 ; }
数字统计
直接用 map 计数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 #include <bits/stdc++.h> using namespace std;int main () { string str; cin >> str; map<char , int > cnt; for (char ch : str) { cnt[ch]++; } for (auto item : cnt) { cout << item.first << ":" << item.second << endl; } return 0 ; }
A 除以 B
不会吧不会还有人不知道 Python 的 int 没有上限吧(
1 2 a, b = map (int , input ().split()) print (a // b, a % b)
公交系统
假设原来车上有 x x x 个人,在某站有 p p p 个人上车,车厢容量为 w w w ;不难推出:
x ∈ [ max ( 0 , − p ) , m i n ( w , w − p ) ] x \in [\max(0, -p), min(w, w-p)]
x ∈ [ max ( 0 , − p ) , min ( w , w − p )]
按此规则,将上车的人数序列从左到右依次累加,每次将加和 sum 作为上面的 p 值更新上下限:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include <bits/stdc++.h> using namespace std;int main () { int n, w; cin >> n >> w; vector<int > arr (n) ; for (int i = 0 ; i < n; i++) { cin >> arr[i]; } int sum = 0 , L = 0 , R = w; for (int x : arr) { sum += x; L = max (L, max (0 , -sum)); R = min (R, min (w, w-sum)); } cout << max (R-L+1 , 0 ) << endl; return 0 ; }
成绩大排队
结构体排序……
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include <bits/stdc++.h> using namespace std;struct Student { string name, id; int mark; }; int main () { int n; cin >> n; vector<Student> arr (n) ; for (int i = 0 ; i < n; i++) { cin >> arr[i].name >> arr[i].id >> arr[i].mark; } sort (arr.begin (), arr.end (), [] (const Student& a, const Student& b) { return a.mark > b.mark; }); cout << arr[0 ].name << " " << arr[0 ].id << endl; cout << arr[n-1 ].name << " " << arr[n-1 ].id << endl; return 0 ; }
字符串数字置换
用 stringstream 做缓冲,构造出目标字符串:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include <bits/stdc++.h> using namespace std;string num[] = {"(Zero)" , "(One)" , "(Two)" , "(Three)" , "(Four)" , "(Five)" , "(Six)" , "(Seven)" , "(Eight)" , "(Nine)" }; int main () { string str; getline (cin, str); stringstream out; vector<int > repl (10 ) ; for (char ch : str) { if ('0' <= ch && ch <= '9' ) { out << num[ch - '0' ]; repl[ch - '0' ]++; } else { out << ch; } } cout << out.str () << endl; for (int i = 0 ; i < 10 ; i++) { cout << repl[i] << " " ; } return 0 ; }
写出来吧
Python 直接怼
1 2 3 4 5 pinyin = ["ling" , "yi" , "er" , "san" , "si" , "wu" , "liu" , "qi" , "ba" , "jiu" ] total = sum (int (ch) for ch in input ()) print (' ' .join(pinyin[int (i)] for i in str (total)))
到底买不买
分别统计商家提供的和小红需要的珠子数量,依次比对即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 #include <bits/stdc++.h> using namespace std;int main () { string str[2 ]; map<char , int > material, target; cin >> str[0 ]; for (char ch : str[0 ]) { material[ch] += 1 ; } cin >> str[1 ]; for (char ch : str[1 ]) { target[ch] += 1 ; } int diff = 0 , flag = true ; for (auto item : target) { if (item.second > material[item.first]) { diff += item.second - material[item.first]; flag = false ; } } if (flag) { cout << "Yes " << (str[0 ].size () - str[1 ].size ()) << endl; } else { cout << "No " << diff; } return 0 ; }
挖掘机技术哪家强
依题意使用 map 实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include <bits/stdc++.h> using namespace std;int main () { int n; cin >> n; map<int , int > count; while (n--) { int id, mark; cin >> id >> mark; count[id] += mark; } int winner, score = -1 ; for (auto item : count) { if (item.second > score) { winner = item.first; score = item.second; } } cout << winner << " " << score; return 0 ; }
Web 导航
模拟题,直接按题意写
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include <bits/stdc++.h> using namespace std;int main () { stack<string> front, back; string url = "http://www.game.org/" ; while (true ) { string opt; cin >> opt; if (opt == "VISIT" ) { back.push (url); stack<string>().swap (front); cin >> url; } else if (opt == "BACK" ) { if (back.empty ()) { cout << "Ignored" << endl; continue ; } front.push (url); url = back.top (), back.pop (); } else if (opt == "FORWARD" ) { if (front.empty ()) { cout << "Ignored" << endl; continue ; } back.push (url); url = front.top (), front.pop (); } else if (opt == "QUIT" ) { break ; } cout << url << endl; } return 0 ; }
训练作业四
在霍格沃茨找零钱
1 2 3 4 5 6 7 8 9 10 11 import regp, sp, kp, ga, sa, ka = map (int , re.findall(r'(\d+)\.(\d+)\.(\d+) (\d+)\.(\d+)\.(\d+)' , input ())[0 ]) diff = (17 *29 *ga + 29 *sa + ka) - (17 *29 *gp + 29 *sp + kp) if diff < 0 : pre = '-' diff = -diff else : pre = '' print (f'{pre} {diff // (17 *29 )} .{diff % (17 *29 ) // 29 } .{diff % 29 } ' )
最简单的计算机
先建立好 5 个变量 M1、M2、R1、R2、R3,然后依题意模拟:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #include <bits/stdc++.h> using namespace std;int main () { int M1, M2, R1, R2, R3; while (cin >> M1 >> M2) { R1 = R2 = R3 = 0 ; string cmd; cin >> cmd; for (char ch : cmd) { switch (ch) { case 'A' : { R1 = M1; break ; } case 'B' : { R2 = M2; break ; } case 'C' : { M1 = R3; break ; } case 'D' : { M2 = R3; break ; } case 'E' : { R3 = R1 + R2; break ; } case 'F' : { R3 = R1 - R2; break ; } } } printf ("%d,%d\n" , M1, M2); } return 0 ; }
相同生日
很适合用 map 的一道题,将月和日组合进一个 int
中即可自动按日期顺序排序:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include <bits/stdc++.h> using namespace std;int main () { int n; cin >> n; map<int , vector<string>> record; while (n--) { string id; int month, date; cin >> id >> month >> date; record[(month << 8 ) | date].push_back (id); } for (auto item : record) { printf ("%d %d " , item.first >> 8 , item.first & 0xff ); for (string str : item.second) { cout << str << " " ; } cout << endl; } return 0 ; }
日历问题
为什么不用神奇的 Python 呢?(狗头)
1 2 3 4 5 6 7 8 9 10 11 12 13 import calendarfrom datetime import datetimefrom datetime import timedeltastart = datetime(2000 , 1 , 1 ) delta = int (input ()) while delta != -1 : future = start + timedelta(days=delta) print (future.date(), calendar.day_name[future.weekday()]) delta = int (input ())
小希的数表
暂时没想到 O ( n 2 ) O(n^2) O ( n 2 ) 的解法
数塔
经典动态规划问题,由倒数第二层向上计算,将下层的最大值累加到自身:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include <bits/stdc++.h> using namespace std;int main () { int n; cin >> n; vector<vector<int >> arr; for (int i = 1 ; i <= n; i++) { vector<int > line (i) ; for (int j = 0 ; j < i; j++) { cin >> line[j]; } arr.push_back (line); } vector<vector<int >> from (n, vector<int >(n)); for (int i = n - 2 ; i >= 0 ; i--) { for (int j = 0 ; j <= i; j++) { if (arr[i+1 ][j] < arr[i+1 ][j+1 ]) { from[i][j] = 1 ; } arr[i][j] += max (arr[i+1 ][j], arr[i+1 ][j+1 ]); } } cout << arr[0 ][0 ] << endl; int index = 0 ; for (int i = 0 ; i < n - 1 ; i++) { int next = index + from[i][index]; cout << (arr[i][index] - arr[i+1 ][next]) << " " ; index = next; } cout << arr[n-1 ][index] << endl; return 0 ; }
斯诺克台球 —— 🈚️
最少钱币数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #include <bits/stdc++.h> #define inf 1e9 using namespace std;int main () { int money; while (cin >> money, money) { int K; cin >> K; vector<int > val (K) ; for (int i = 0 ; i < K; i++) { cin >> val[i]; } sort (val.begin (), val.end ()); vector<int > F (money + 1 , inf) ; F[0 ] = 0 ; for (int i = 1 ; i <= money; i++) { for (int x : val) { if (i - x < 0 ) continue ; F[i] = min (F[i], F[i - x] + 1 ); } } if (F[money] >= inf) { cout << "Impossible" << endl; } else { cout << F[money] << endl; } } return 0 ; }
相等的多项式
把 x = − 1 , 0 , 1 x = -1, 0, 1 x = − 1 , 0 , 1 代进去,如果全部成立则判断小明计算正确(骗,都可以骗)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 #include <bits/stdc++.h> using namespace std;int pi (int x, const vector<int >& arr) { int ans = 1 ; for (int n : arr) { ans *= (x + n); } return ans; } int sigma (int x, const vector<int >& arr) { int ans = 1 ; for (int n : arr) { ans = ans * x + n; } return ans; } int main () { int n; while (cin >> n, n) { vector<int > A (n) , B (n) ; for (int i = 0 ; i < n; i++) { cin >> A[i]; } for (int i = 0 ; i < n; i++) { cin >> B[i]; } bool flag = true ; for (int x = -1 ; x <= 1 ; x++) { if (pi (x, A) != sigma (x, B)) { flag = false ; break ; } } cout << (flag ? "Y" : "N" ) << endl; } return 0 ; }
选美比赛
蛇行矩阵
将输出矩阵顺时针旋转 45°,不难发现规律
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include <bits/stdc++.h> using namespace std;const int maxn = 102 ;int main () { int n; cin >> n; int arr[maxn][maxn] = {0 }, cnt = 0 ; for (int i = 0 ; i < n; i++) { for (int j = 0 ; j <= i; j++) { arr[i][j] = ++cnt; } } for (int i = 0 ; i < n; i++) { for (int j = 0 ; i + j < n; j++) { cout << arr[i+j][j] << " " ; } cout << endl; } return 0 ; }
疫情期间
动态规划,F[i][j]
表示第 i+1
天进行了活动 j
,前 i+1
天的最少休息天数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #include <bits/stdc++.h> using namespace std;int main () { int n; cin >> n; vector<int > arr (n) ; for (int i = 0 ; i < n; i++) { cin >> arr[i]; } vector<vector<int >> F (n + 1 , vector<int >(3 , n)); for (int i : {1 , 2 }) { (arr[0 ] & i) && (F[0 ][i] = 0 ); } F[0 ][0 ] = 1 ; for (int i = 1 ; i < n; i++) { for (int j : {1 , 2 }) { if (arr[i] & j) { F[i][j] = min (F[i - 1 ][0 ], F[i - 1 ][j ^ 3 ]); } } F[i][0 ] = *min_element (F[i - 1 ].begin (), F[i - 1 ].end ()) + 1 ; } cout << *min_element (F[n - 1 ].begin (), F[n - 1 ].end ()) << endl; return 0 ; }
7,还是 7
组个最小数
字频统计
逆序数
最小钱币数
身份证校验
最长连续递增子序列
恺撒 Caesar 密码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include <bits/stdc++.h> using namespace std;int main () { string str, _; while (cin >> _, _ != "ENDOFINPUT" ) { getchar (); getline (cin, str); for (int i = 0 ; i < str.size (); i++) { if (str[i] < 'A' || str[i] > 'Z' ) { continue ; } int ord = str[i] - 'A' ; ord = (ord + 21 ) % 26 ; str[i] = 'A' + ord; } cout << str << endl; cin >> _; } return 0 ; }
回文串
训练作业五
Dijkstra?
算法以传统 dijkstra 为基础,但在优先队列中以 pair<int, string>
代替原本的 int
形式存储当前距离最短的未探索节点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 #include <bits/stdc++.h> using namespace std;const int maxn = 100002 ;struct Edge { int to, val; }; int n, m;vector<vector<Edge>> head (maxn); vector<int > from (maxn) ; void dijkstra () { struct Node { int dst; pair<int , string> val; bool operator < (const Node& other) const { return val < other.val; } }; priority_queue<Node> task; vector<pair<int , string>> dis (maxn, {0x7fffffff , "" }); task.push ({1 , {0 , "1" }}); dis[1 ] = {0 , "1" }; while (!task.empty ()) { Node top = task.top (); task.pop (); if (top.val > dis[top.dst]) continue ; for (Edge edg : head[top.dst]) { pair<int , string> nxt = {top.val.first + edg.val, top.val.second + (char )(edg.to + '0' )}; if (nxt < dis[edg.to]) { from[edg.to] = top.dst; dis[edg.to] = nxt; task.push ({edg.to, nxt}); } } } } int output (int index) { if (from[index] == 0 ) { printf ("%d " , index); return 0 ; } output (from[index]); printf ("%d " , index); return 0 ; } int main () { cin >> n >> m; for (int i = 0 ; i < m; i++) { int src, dst, val; cin >> src >> dst >> val; head[src].push_back ({dst, val}); head[dst].push_back ({src, val}); } dijkstra (); from[n] ? output (n) : printf ("-1" ); return 0 ; }
0-1 串
使用前缀和数组,能将求某个区间中 0 或 1 的数量的操作优化到 O ( 1 ) O(1) O ( 1 ) ,接下来暴力遍历所有区间 [ L , R ] [L, R] [ L , R ] 求解即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include <bits/stdc++.h> using namespace std;git int main () { int n; cin >> n; vector<int > sum (n+1 ) ; for (int i = 1 ; i <= n; i++) { cin >> sum[i]; sum[i] += sum[i-1 ]; } int max_z = 0 ; for (int i = 1 ; i <= n; i++) { for (int j = i; j <= n; j++) { max_z = max (max_z, sum[n] + (j-i+1 ) - 2 *(sum[j]-sum[i-1 ])); } } cout << max_z << endl; return 0 ; }
良心树
简单观察可以发现,删除一个节点时,并不会改变其父节点和所有儿子的「可删除」状态(即可删除节点的数量不会因为删除一个节点而增加或减少),那么先按照输入数据建树,建树后通过一次深度优先遍历找出所有待删除的节点,排序后输出即可 AC
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 #include <bits/stdc++.h> using namespace std;struct Node { int id, flag; vector<int > child; bool operator < (const Node& other) const { return id > other.id; } }; int n;vector<Node> arr; bool judge (int index) { if (!arr[index].flag) return false ; for (int ptr : arr[index].child) { if (!arr[ptr].flag) { return false ; } } return true ; } int main () { cin >> n; arr = vector<Node>(n+1 ); for (int i = 1 ; i <= n; i++) { int p, c; cin >> p >> c; arr[i].id = i, arr[i].flag = c; if (~p) arr[p].child.push_back (i); } priority_queue<Node> task; for (int i = 1 ; i <= n; i++) { if (judge (i)) task.push (arr[i]); } if (task.empty ()) { cout << "-1" << endl; return 0 ; } while (!task.empty ()) { cout << task.top ().id << " " ; task.pop (); } return 0 ; }
最昂贵的旅行
从「n n n 个城市,n − 1 n-1 n − 1 条边,没有环」可以推出该国所有城市间道路为树形结构,将编号为 0 0 0 的城市作为根,执行一次 dfs 找出最「远」的城市即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #include <bits/stdc++.h> using namespace std;struct Edge { int to, val; }; int n;vector<vector<Edge>> head; vector<bool > vst; int dfs (int src, int cost=0 ) { vst[src] = true ; int max_len = cost; for (Edge nxt : head[src]) { if (!vst[nxt.to]) { max_len = max (max_len, dfs (nxt.to, cost + nxt.val)); } } return max_len; } int main () { cin >> n; head = vector<vector<Edge>>(n); for (int i = 0 ; i < n-1 ; i++) { int src, dst, val; cin >> src >> dst >> val; head[src].push_back ({dst, val}); head[dst].push_back ({src, val}); } vst = vector<bool >(n); cout << dfs (0 ) << endl; return 0 ; }
猫与餐厅的故事
对于非叶子节点,统计其路径上连续有猫的节点数量,如果大于 m m m 则返回 0;对于叶子节点,直接返回 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include <bits/stdc++.h> using namespace std;const int maxn = 100002 ;int n, m;vector<int > cat (maxn) ;vector<vector<int >> head (maxn); int dfs (int now, int cnt, int par) { if (cnt + cat[now] > m) return 0 ; if (head[now].size () <= 1 ) return 1 ; int sum = 0 ; for (int nxt : head[now]) { if (nxt != par) { sum += dfs (nxt, cat[now] ? cnt + 1 : 0 , now); } } return sum; } int main () { cin >> n >> m; for (int i = 1 ; i <= n; i++) { cin >> cat[i]; } for (int i = 0 ; i < n-1 ; i++) { int src, dst; cin >> src >> dst; head[src].push_back (dst); head[dst].push_back (src); } cout << dfs (1 , 0 , 0 ) << endl; return 0 ; }
旅行的期望值
建树,递归。对于某个节点,其期望值为「其所有孩子节点的期望值取平均 + 1」,对于叶子节点,期望值为 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 #include <bits/stdc++.h> using namespace std;const int maxn = 100002 ;int n;vector<vector<int >> head (maxn); double dfs (int src, int par) { if (head[src].size () <= 1 && src != 1 ) return 0 ; double sum = 0 ; int child = 0 ; for (int nxt : head[src]) { if (nxt == par) continue ; (sum += dfs (nxt, src)); child += 1 ; } return sum / child + 1 ; } int main () { cin >> n; for (int i = 0 ; i < n-1 ; i++) { int src, dst; cin >> src >> dst; head[src].push_back (dst); head[dst].push_back (src); } printf ("%.7lf" , dfs (1 , 0 )); return 0 ; }
有效的 BFS
模拟 bfs 的过程,每次都试图选择输入中给出的节点,如果存在某时刻无法选择,则说明输入不是一个有效的 bfs 序(说白了就是直接模拟)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 #include <bits/stdc++.h> using namespace std;const int maxn = 100002 ;inline int read () { int x; cin >> x; return x; } int n;vector<set<int >> head (maxn); vector<int > parent (maxn) ; void dfs (int now, int par) { parent[now] = par; for (int nxt : head[now]) { if (nxt == par) continue ; dfs (nxt, now); } } bool bfs () { queue<int > task; task.push (read ()); while (!task.empty ()) { int now = task.front (); task.pop (); for (int nxt : head[now]) { if (nxt == parent[now]) continue ; int except = read (); if (head[now].find (except) == head[now].end ()) { return false ; } task.push (except); } } return true ; } int main () { cin >> n; for (int i = 0 ; i < n-1 ; i++) { int src, dst; cin >> src >> dst; head[src].insert (dst); head[dst].insert (src); } dfs (1 , 0 ); printf (bfs () ? "Yes" : "No" ); return 0 ; }
数组跳远
从后向前倒推
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include <bits/stdc++.h> using namespace std;int main () { int T; cin >> T; while (T--) { int n; cin >> n; vector<int > arr (n) ; for (int i = 0 ; i < n; i++) { cin >> arr[i]; } int ans = 0 ; vector<int > sum (n) ; for (int i = n-1 ; i >= 0 ; i--) { sum[i] = arr[i]; if (i + arr[i] < n) { sum[i] += sum[i + arr[i]]; } ans = max (ans, sum[i]); } cout << ans << endl; } return 0 ; }
踩点上课
将「不使用折跃门而能互相到达的块」称为一个连通区域,考虑以下两种情况:
1. 对起点和终点所在的连通块分别做 BFS,找出「路径长 + 折跃代价」最小的折跃门
2. 将上述两次 BFS 的结果相加即为答案,如果没有这样的折跃门,输出 -1
1. 与在不同连通块时相同
2. 计算从起点直接走到终点的代价(即不使用折跃门)
3. 在第 1 步和第 2 步中选择最小的代价输出
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 #include <bits/stdc++.h> #define inf (1LL << 60) using namespace std;typedef long long LL;const int ways[4 ][2 ] = {{0 , 1 }, {0 , -1 }, {1 , 0 }, {-1 , 0 }};int n, m, w;vector<vector<int >> gmap; vector<vector<LL>> dst; LL direct = inf; void init () { scanf ("%d %d %d" , &n, &m, &w); gmap = vector<vector<int >> (n + 2 , vector<int >(m + 2 , -1 )); dst = vector<vector<LL>>(n + 2 , vector<LL>(m + 2 , inf)); for (int i = 1 ; i <= n; i++) { for (int j = 1 ; j <= m; j++) { scanf ("%d" , &gmap[i][j]); } } } LL bfs (int x0, int y0) { struct pos { int x, y;; }; LL min_cost = inf; queue<pos> task; task.push ({x0, y0}); dst[x0][y0] = 0 ; while (!task.empty ()) { auto now = task.front (); task.pop (); int x = now.x, y = now.y; if (gmap[x][y] && gmap[x][y] + dst[x][y] < min_cost) { min_cost = gmap[x][y] + dst[x][y]; } for (int i = 0 ; i < 4 ; i++) { int nx = x + ways[i][0 ], ny = y + ways[i][1 ]; if (~gmap[nx][ny] && dst[x][y] + w < dst[nx][ny]) { dst[nx][ny] = dst[x][y] + w; task.push ({nx, ny}); } } } return min_cost; } int main () { init (); LL path = 0 ; path += bfs (1 , 1 ); direct = dst[n][m]; path += bfs (n, m); LL ans = min (path, direct); if (ans >= inf) { printf ("-1" ); } else { printf ("%lld" , ans); } return 0 ; }
树的优化
参考「最大子段和」算法,进行第一次 dfs,统计从根节点开始的每一条路径上的最大子段和,找出所有「导致瑕疵」的节点;再进行第二次 dfs,统计数中不包含「导致瑕疵」节点的最大部分,即为删除后剩下节点的数量;最后与 n 作减法输出即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 #include <bits/stdc++.h> using namespace std;const int maxn = 100002 ;struct Edge { int dst, val; }; int n;vector<vector<Edge>> head (maxn); vector<int > arr (maxn) ; vector<bool > flag (maxn) ; void find_all_bad (int now, int par, int sum) { flag[now] = sum > arr[now]; for (Edge nxt : head[now]) { if (nxt.dst == par) continue ; find_all_bad (nxt.dst, now, max (sum + nxt.val, nxt.val)); } } int count_not_bad (int now, int par) { if (flag[now]) return 0 ; int sum = 0 ; for (Edge nxt : head[now]) { if (nxt.dst == par) continue ; sum += count_not_bad (nxt.dst, now); } return sum + 1 ; } int main () { cin >> n; for (int i = 1 ; i <= n; i++) { cin >> arr[i]; } for (int i = 1 ; i < n; i++) { int src = i + 1 , dst, val; cin >> dst >> val; head[src].push_back ({dst, val}); head[dst].push_back ({src, val}); } find_all_bad (1 , 0 , 0 ); cout << (n - count_not_bad (1 , 0 )) << endl; return 0 ; }