这篇文章是关于SDNU_ACM_ICPC_2019_Winter_Practice_5th的题解.
水题欢乐赛,,可惜没赶上,,,去走亲戚错过了寒假礼物,,/(ㄒoㄒ)/~~
这场比赛后面大都是3题下场了,,不好补不好补,,,,
A - Easy Marks
SPOJ - EASYMRKS
题意:给你n个数字,和一个数k问你再加上哪个数字可以让整个序列的平均数等于k;
题解:输出k*(n + 1) - 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 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std ;const int Ma = 1e4 + 10 ;int num[Ma];int main () { int T; scanf ("%d" , &T); int y = 0 ; while (T--){ int n, k; scanf ("%d%d" , &n, &k); int sum = 0 , ans = k * (n + 1 ); for (int i = 0 ; i < n; i++){ int t; scanf ("%d" , &t); sum += t; } printf ("Case %d: %d\n" , ++y, ans - sum); } return 0 ; }
B - Candy I
SPOJ - CANDY
题意:你要分糖果,你有n个包裹里面分别装了些糖果,你要让每个包裹里面的糖果都一样多,问你需要的步骤数,如果不能就输出-1;
题解:记录总共有多少个糖果,如果这些糖果不能被n整除直接输出-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 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std ;const int Ma = 1e4 + 10 ;int num[Ma];int main () { int n; while (~scanf ("%d" , &n) && n != -1 ){ int sum = 0 ; for (int i = 0 ; i < n; i++){ scanf ("%d" , &num[i]); sum += num[i]; } if (sum % n)printf ("-1\n" ); else { int a = sum / n; int ans = 0 ; for (int i = 0 ; i < n; i++){ if (num[i] < a)ans += (a - num[i]); } printf ("%d\n" , ans); } } return 0 ; }
C - Rectangles
SPOJ - AE00
题意:给你n个小方块,问你你能堆出多少个不同的矩形;
题解:要让矩形不重样,枚举列到sqrt(n)就行了,再多就能通过列行互换而重样了,直接枚举判断;
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include <cstdio> #include <cmath> #include <iostream> using namespace std ;int main () { int n; scanf ("%d" , &n); int a = sqrt (n); int cont = a; for (int i = 1 ; i <= a; i++) for (int j = i + 1 ; j * i <= n; j++) ++cont; cout << cont << '\n' ; return 0 ; }
D - Alchemy
URAL - 1573
题意:你是一个炼金术士,给你蓝红黄三种颜色的药水,再给你一个配方,包含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 #include <cstdio> #include <cstring> #include <cmath> #include <iostream> #include <algorithm> using namespace std ;int main () { int r, y, b; while (~scanf ("%d%d%d" , &b, &r, &y)){ int n; scanf ("%d" , &n); int ans = 1 ; while (n--){ char s[10 ]; scanf ("%s" ,s); if (s[0 ] == 'R' ) ans *= r; if (s[0 ] == 'B' ) ans *= b; if (s[0 ] == 'Y' ) ans *= y; } cout << ans << '\n' ; } return 0 ; }
E - Genealogical Tree
URAL - 1022
题意:给你n个序列,每个序列以0结尾,下面第i列代表i这个数字前有哪些数字,不计0,请你以此将1到n排序并输出;
题解:拓扑排序裸题,Albert_s的拓扑排序教程里面有;
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 <bits/stdc++.h> using namespace std ;vector <int >top[110 ];vector <int >ans;bool visit[110 ];void topu (int x) { visit[x] = true ; for (auto i : top[x]) if (!visit[i])topu(i); vector <int >::iterator it = ans.begin(); ans.insert(it, x); } int main () { int n; scanf ("%d" , &n); visit[0 ] = true ; for (int i = 1 ; i <= n; i++){ int k; do { scanf ("%d" , &k); top[i].push_back(k); } while (k != 0 ); } for (int i = 1 ; i <= n; i++) if (!visit[i])topu(i); for (auto i : ans){ if (i != ans[0 ]) putchar (' ' ); cout << i ; } putchar ('\n' ); return 0 ; }
F - GCD The Largest
UVA - 12708
题意:UVA崩了又,,日常gg,给你一个数n,问你 i, j ∈ [1, n]时,最大的gcd(i, j);
题解:逻辑问题,i和j最大只能为n,设i > j,要gcd最大肯定元素要尽量大,那么设i为n,这时候i分出最小的素因子为2,此时j为n/2便可使gcd(i, j)最大,且等于j,当n为奇数时减一即可;
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include <cstdio> #include <cstring> #include <cmath> #include <iostream> #include <algorithm> using namespace std ;typedef long long ll;int main () { int T; scanf ("%d" , &T); while (T--){ ll n; scanf ("%lld" , &n); if (n % 2 )--n; cout << n / 2 << '\n' ; } return 0 ; }
G - Peter's Smokes
UVA - 10346
题意:给Peter n根香烟, 给你一个数k,Peter每抽k根香烟就能再获得一根新的香烟,而你什么都没有 问你Peter能抽多少根香烟;
题解:记录Peter每次能获得多少根香烟和剩余香烟数,模拟;
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 <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std ;const int Ma = 1e4 + 10 ;typedef long long ll;int main () { int n, k; while (scanf ("%d%d" , &n, &k) != EOF){ int cia = n, butt = 0 , ans = n; while (n >= k){ ans += (n / k); n = n / k + n % k; } printf ("%d\n" , ans); } return 0 ; }
H - Blown Garland
CodeForces - 758B
题意:让你来修灯,!表示坏了的灯,且四个颜色的灯需要满足一个顺序,不能变,问你需要的灯泡数量,并按r b y g的顺序输出;
题解:用一个数组来存四个颜色灯泡的顺序,一个数组来存需要四个灯泡的个数,在最后按r b y g的顺序输出;
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 <cstdio> #include <cstring> #include <cmath> #include <map> #include <iostream> #include <algorithm> using namespace std ;int main () { string light; map <char , char >m; while (cin >> light){ char li[5 ]; int lli[5 ] = {0 , 0 , 0 , 0 }; int n = light.length(); for (int i = 0 ; i < n; i ++){ if (light[i] == '!' )++lli[(i + 1 )%4 ]; else li[(i + 1 )%4 ] = light[i]; } char ri[] = {'R' , 'B' , 'Y' , 'G' }; for (int i = 0 ; i < 4 ; i++){ if (i != 0 )putchar (' ' ); for (int j = 0 ; j < 4 ; j++){ if (li[j] == ri[i])cout << lli[j]; } } putchar ('\n' ); } return 0 ; }
I - Pythagorean Theorem II
CodeForces - 304A
题意:问你1 ≤ a ≤ b ≤ c ≤ n下有多少个由a, b, c组成的直角三角形;
题解:枚举a, b判断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 #include <cstdio> #include <cstring> #include <cmath> #include <iostream> #include <algorithm> using namespace std ;int main () { int n; scanf ("%d" , &n); int cont = 0 ; for (int a = 1 ; a <= n; a++) for (int b = a; b <= n; b++){ int c = a * a + b * b; int C = sqrt (c) + 0.5 ; if (C * C == c && C >= b && a + b > C) ++cont; else if (C >= n)break ; } printf ("%d\n" , cont); return 0 ; }
J - Calendar
CodeForces - 304B
题意:给你两个日期,问你差多少天;
题解:模拟 (偷懒打了个表 ;
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 #include <bits/stdc++.h> using namespace std ;int yea, mon, da;int year, month, day;bool judge (int n) { return n % 400 == 0 ? true : n % 100 != 0 ? n % 4 == 0 : false ; } int run[] = {0 , 31 , 60 , 91 , 121 , 152 , 182 , 213 , 244 , 274 , 305 , 335 , 366 };int nian[] = {0 , 31 , 59 , 90 , 120 , 151 , 181 , 212 , 243 , 273 , 304 , 334 , 365 };void change () { int t; t = yea, yea = year, year = t; t = mon, mon = month, month = t; t = da, da = day, day = t; } int main () { while (~scanf ("%d:%d:%d" , &yea, &mon, &da)){ scanf ("%d:%d:%d" , &year, &month, &day); if (year < yea)change(); else if (year == yea && mon > month)change(); else if (year == yea && mon == month && da > day)change(); else if (year == yea && mon == month && da == day){ cout << 0 << '\n' ; continue ; } if (year != yea){ int ans = 0 ; if (judge(yea))ans += (run[12 ] - run[mon - 1 ] - da); else ans += (nian[12 ] - nian[mon - 1 ] - da); for (int i = yea + 1 ; i < year; i++){ if (judge(i))ans += run[12 ]; else ans += nian[12 ]; } if (judge(year))ans += (run[month - 1 ] + day); else ans += (nian[month - 1 ] + day); cout << ans << '\n' ; } else if (month != mon){ if (judge(yea))cout << (run[month - 1 ] - run[mon - 1 ] - da + day) << '\n' ; else cout << (nian[month - 1 ] - nian[mon - 1 ] - da + day) <<'\n' ; } else cout << day - da << '\n' ; } return 0 ; }