这篇文章是关于SDNU_ACM_ICPC_2019_Winter_Practice_2nd的题解.
缓慢更新题中,,第二场比赛我就回家了,边吸猫边打的比赛,傻猫现在都瘦了,让我给它买点零食。当初怎么就去阿里云申请域名了呢,,,以为国内实名认证应该很快,,结果一周了还没认证完成,,,不知什么时候才能重启博客域名,,,
还是继续题解系列吧
A - Partition
CodeForces - 946A
题意:给你一个序列,让你把它分为两个序列,让这两个序列的和相减最大;
题解:把正的数加起来,负的数加起来,相减;
B - A/B
HDU - 1576
题意:求(A/B)%9973的值
题解:除法取模,用逆元解决 刚学的东西,求逆元方法还挺多的,等会总结下逆元(我开了多少坑来着??咕咕咕
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 <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define LL long long using namespace std ;const int Mod = 9973 ;LL ny (LL a, LL b) { LL s = 1 ; while (b) { if (b & 1 )s = s * a % Mod; a = a * a % Mod; b >>= 1 ; } return s; } int main () { int T; scanf ("%d" , &T); while (T--){ LL A, B; scanf ("%lld %lld" , &A, &B); printf ("%lld\n" , A * ny(B, Mod - 2 ) % Mod); } return 0 ; }
C - Rightmost Digit
HDU - 1061
题意:输入n,求n^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 #include <cstdio> #include <iostream> #define LL long long using namespace std ;LL solve (LL n) { LL N = n, sum = 1 ; n = n % 10 ; while (N){ if (N & 1 ) sum *= n % 10 ; n = n * n % 10 ; N /= 2 ; } return sum % 10 ; } int main () { LL t; while (~scanf ("%d" , &t)){ while (t--){ LL n; scanf ("%lld" , &n); printf ("%lld\n" , solve(n)); } } return 0 ; }
D - Tempter of the Bone
HDU - 1010
题意:走二维迷宫,给定一个时间,必须在那个时间走到门
题解:,,,这道题诱惑我用bfs,,,好难受,,,乍一看就是基础迷宫题,再仔细一读题,,只有在t时门才开,所以只能在t时恰好到,那么bfs找出所有路径,如果时间恰好为t就行,行吧,tle了。。。思路没错的话那就是剪枝的问题了,用上百年不变的边界剪枝,超时的也剪一下,以及奇偶剪枝,终于剪到1s以内了,,,多么想+1s
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 <cstdio> #include <iostream> #include <queue> #include <cstring> #define LL long long using namespace std ;const int Ma = 10 ;char maze[Ma][Ma];bool visit[Ma][Ma];int n, m, T, zx, zy;bool zd = false ;void dfs (int dx, int dy, int dt) { int xzou[] = {1 , -1 , 0 , 0 }; int yzou[] = {0 , 0 , 1 , -1 }; if (zd)return ; if (dx >= n || dx < 0 || dy >= m || dy < 0 || dt > T)return ; if (dx == zx && dy == zy && dt == T){ printf ("YES\n" ); zd = true ; return ; } int lost = abs (zx - dx) + abs (zy - dy); if (T - dt < lost)return ; if ((T - dt - lost) % 2 )return ; for (int i = 0 ; i < 4 ; i++){ if (maze[dx + xzou[i]][dy + yzou[i]] != 'X' ){ maze[dx + xzou[i]][dy + yzou[i]] = 'X' ; dfs(dx + xzou[i], dy + yzou[i], dt + 1 ); maze[dx + xzou[i]][dy + yzou[i]] = '.' ; } } return ; } int main () { while (~scanf ("%d%d%d" , &n, &m, &T)){ zd = false ; if (n == 0 && m == 0 && T == 0 )continue ; memset (visit, 1 , sizeof (visit)); int xx, yy; for (int i = 0 ; i < n; i++){ for (int j = 0 ; j < m; j++){ cin >> maze[i][j]; if (maze[i][j] == 'S' )xx = i, yy = j; else if (maze[i][j] == 'D' ) zx = i, zy = j; } } maze[xx][yy] = 'X' ; dfs(xx, yy, 0 ); if (!zd)cout << "NO\n" ; } return 0 ; }
E - Pie
HDU - 1969
题意:给你n个高度都为1的派,和f个小伙伴,要分给小伙伴和你自己一人一块派,要求没人获得的派一样大
题解:二分,当初没注意一人一块,,我那时想把派加起来平均分就行了嘛,,但有了一人一块的要求后,,每个人获得的派大小的上界就得出了,二分答案可得, 注意把你自己加上,话说二分也得总结,,管挖不管埋
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 #include <bits/stdc++.h> using namespace std ;const int Ma = 1e4 + 10 ;const double TT = acos (-1.0 );double num[Ma];int n, f;const double Mi = 1e-7 ;bool check (double q) { int s = 0 ; for (int i = 0 ; i < n; i++){ s += (int )(TT * num[i] * num[i] / q); } if (s < f + 1 )return true ; return false ; } int main () { int T; scanf ("%d" , &T); while (T--){ scanf ("%d%d" , &n, &f); double sum = 0 ; for (int i = 0 ; i < n; i++){ scanf ("%lf" , &num[i]); sum += (num[i] * num[i] * TT); } double r = sum / (double )(f + 1 ); double l = 0 ; while (r - l > Mi){ double mid = (r + l) / 2 ; if (check(mid))r = mid; else l = mid; } printf ("%.4f\n" , r); } return 0 ; }
F - Ticket to Ride
HDU - 1970
题意:票,路,游戏,火车,轨道;
题解:???
G - What Are You Talking About
HDU - 1075
题意:对上一道题的解释 首先由一个start和一个end中间给你一个字典,下一个start和end中间给你一串火星文,让你按照字典翻译火星文,翻译不了就直接输出
题解:map记录字典,读入火星文,能在字典上找到就输出翻译的,不能就直接输出,,话说我之前说整理stl来着???
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 main () { string be = "START" , en = "END" ; string te; map <string , string >m; while (cin >> te && te != be); while (cin >> te && te != en){ string huo; cin >> huo; m[huo] = te; } map <string , string >::iterator it = m.end(); while (cin >> te && te != be); getchar(); while (getline(cin , te) && te != en){ int le = te.length(); for (int i = 0 , j; i < le; i++){ j = i; for (; i < le && te[i] <= 'z' && te[i] >= 'a' ; i++); if (i != j){ string tm = te.substr(j, i - j); if (m.find(tm) != it){ cout << m[tm]; cout << te[i]; } else for (;j <= i; j++)cout << te[j]; } else cout << te[i]; } putchar ('\n' ); } return 0 ; }
H - 水果
HDU - 1263
题意:水果真好吃,话说sd的橙子🍊真的好吃,cq的橙子🍊好小
题解:map的应用,装入map的元素会按字典序排好,stl真好用系列,对了,还有多维map的应用,记录在还在咕咕咕的stl总结里面
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 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <map> using namespace std ;int main () { int T; bool kg = false ; scanf ("%d" , &T); while (T--){ if (kg)putchar ('\n' ); int M; scanf ("%d" , &M); map <string , map <string , int >>m; for (int i = 0 ; i < M; i++){ string t, tt; cin >> t >> tt; int num; scanf ("%d" , &num); m[tt][t] += num; } map <string , map <string , int >>::iterator it = m.begin(); for (it; it != m.end(); it++){ cout << it -> first <<'\n' ; map <string , int >::iterator ii = it -> second .begin(); for (ii; ii != it -> second.end(); ii++) cout <<" |----" << ii -> first << '(' << ii -> second << ')' << '\n' ; } if (!kg)kg = true ; } return 0 ; }
I - 最大连续子序列
HDU - 1231
题意:中文题意,找到最大连续子序列并输出和以及序列的第一个数和最后一个个数
题解:dp解决,sum记录dp中的最大值,同时记录此时的第一个数和最后一个数,如果dp时第一个数为负数那么直接跳过,以为如果这个序列减去首位数字就能得到比他大的序列,注意找不到输出0和最大和为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 #include <cstdio> #include <cstring> #include <iostream> using namespace std ;int num[10010 ];int dp[10010 ];int main () { int k; while (~scanf ("%d" , &k)){ if (k == 0 )continue ; for (int i = 0 ; i < k; i++) scanf ("%d" , &num[i]); memset (dp, 0 , sizeof (dp)); int first = 0 , last = 0 , sum = -1 ; int i, j; for (i = 0 ; i < k; i++){ dp[i] = 0 ; if (num[i] < 0 )continue ; for (j = i; j < k; j++){ dp[i] += num[j]; if (dp[i] > sum){ sum = dp[i]; first = num[i]; last = num[j]; } } } if (sum != -1 )cout << sum << ' ' << first << ' ' << last << '\n' ; else cout << 0 <<' ' << num[0 ] <<' ' << num[k - 1 ]<< '\n' ; } return 0 ; }
J - Unimodal Array
CodeForces - 831A
题意:给你一个长度为n的序列,问你这个序列是否为单增不变单减
题解:走一遍单增,不变,单减,看走了几个单位,若和序列长度一样就输出YES,否则输出NO
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include <cstdio> #include <cstring> #include <iostream> using namespace std ;int num[110 ];int main () { int n; scanf ("%d" , &n); for (int i = 0 ; i < n; i++){ cin >> num[i]; } int i = 0 ; while (num[i + 1 ] > num[i])i++; while (num[i + 1 ] == num[i])i++; while (num[i + 1 ] < num[i])i++; if (i >= n)cout << "YES\n" ; else cout << "NO\n" ; return 0 ; }
最近到处过年,,我要学习,不要红包/(ㄒoㄒ)/~~ 快开学了,,还是菜鸡状态,,什么时候才能升级啊,,,好想回去专心敲代码.jpg