2019 Multi-University Training Contest 8
补题链接:2019 Multi-University Training Contest 8
题意
定义 $f(d, n)$ 为十进制下 $1$ 到 $n$ 所有数的数位中数字 $d$ 出现的次数。给定 $x$,找出最大的 $n(n \le x)$ 满足 $f(d, n) = n$。
题解 看到了一个神仙做法。
显然如果 $f(d, x) = x$ 时就直接输出。
否则,需要缩小 $x$。令 $f(d, x) = y$,则需要将 $x$ 缩小 $\lceil \frac{|x - y|}{18} \rceil$。即 $x = x - abs(f(d, x) - x) / 18$。原因是 $f(d, x)$ 与 $f(d, x - 1)$ 最多相差 $18$ 个 $d$ $ (e.g. f(9, 10^{18}-1) to f(9, 10^{18}-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 #include <bits/stdc++.h> using namespace std ;typedef long long ll;ll f (ll d, ll n) { ll cnt = 0 , k; for (ll i = 1 ; k = n / i; i *= 10 ) { cnt += (k / 10 ) * i; int cur = k % 10 ; if (cur > d) { cnt += i; } else if (cur == d) { cnt += n - k * i + 1 ; } } return cnt; } int main () { ios::sync_with_stdio(0 ); cin .tie(0 ); cout .tie(0 ); int T; cin >> T; while (T--) { ll d, x; cin >> d >> x; while (true ) { ll num = f(d, x); if (num == x) { cout << x << endl ; break ; } else { x -= max(1L L, abs (num - x) / 18 ); } } } return 0 ; }
参考 2019 Multi-University Training Contest 8——Acesrc and Good Numbers(数学 想法)
题意: 给出两个矩形,求矩形把平面分割成几块。
思路 分类讨论
听说只要离散化到 $5*5$ 的格子里然后 $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 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 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 #include <bits/stdc++.h> using namespace std ;typedef long long ll;const ll inf = 0x3f3f3f3f ;struct Point { ll x, y; }p[10 ]; int main () { int T; cin >> T; while (T--) { ll maxx = 0 , maxy = 0 , minx = inf, miny = inf; for (int i = 1 ; i <= 2 ; ++i) { scanf ("%lld%lld" , &p[i].x, &p[i].y); } p[3 ].x = p[1 ].x; p[3 ].y = p[2 ].y; p[4 ].x = p[2 ].x; p[4 ].y = p[1 ].y; ll s1 = (p[2 ].x - p[1 ].x) * (p[2 ].y - p[1 ].y); for (int i = 5 ; i <= 6 ; ++i) { scanf ("%lld%lld" , &p[i].x, &p[i].y); } p[7 ].x = p[5 ].x; p[7 ].y = p[6 ].y; p[8 ].x = p[6 ].x; p[8 ].y = p[5 ].y; ll s2 = (p[6 ].x - p[5 ].x) * (p[6 ].y - p[5 ].y); for (int i = 1 ; i <= 8 ; ++i) { maxx = max(maxx, p[i].x); maxy = max(maxy, p[i].y); minx = min(minx, p[i].x); miny = min(miny, p[i].y); } if (p[1 ].x == p[5 ].x && p[1 ].y == p[5 ].y && p[3 ].x == p[7 ].x && p[3 ].y == p[7 ].y && p[6 ].x == p[2 ].x && p[6 ].y == p[2 ].y && p[4 ].x == p[8 ].x && p[4 ].y == p[8 ].y) { printf ("2\n" ); continue ; } ll s = (maxx - minx) * (maxy - miny); if (s1 == s || s2 == s) { if ((p[1 ].x == p[5 ].x && p[2 ].x == p[6 ].x)) { if (p[5 ].y == p[1 ].y || p[6 ].y == p[2 ].y) printf ("3\n" ); else printf ("4\n" ); } else if ((p[1 ].y == p[5 ].y && p[2 ].y == p[6 ].y)) { if (p[5 ].x == p[1 ].x || p[6 ].x == p[2 ].x) printf ("3\n" ); else printf ("4\n" ); } else printf ("3\n" ); } else if (p[4 ].y >= p[7 ].y || p[8 ].y >= p[3 ].y || p[5 ].x >= p[2 ].x || p[1 ].x >= p[6 ].x) { printf ("3\n" ); } else if ((p[2 ].x - p[1 ].x) * (p[6 ].y - p[5 ].y) == s) { if (p[6 ].y > p[2 ].y && p[5 ].y < p[1 ].y && p[1 ].x < p[5 ].x && p[2 ].x > p[6 ].x) { printf ("6\n" ); } else if (p[1 ].x == p[5 ].x && p[1 ].y == p[5 ].y) { printf ("4\n" ); } else if (p[3 ].x == p[7 ].x && p[3 ].y == p[7 ].y) { printf ("4\n" ); } else if (p[2 ].x == p[6 ].x && p[2 ].y == p[6 ].y) { printf ("4\n" ); } else if (p[4 ].x == p[8 ].x && p[4 ].y == p[8 ].y) { printf ("4\n" ); } else { printf ("5\n" ); } } else if ((p[6 ].x - p[5 ].x) * (p[2 ].y - p[1 ].y) == s) { if (p[2 ].y > p[6 ].y && p[1 ].y < p[5 ].y && p[5 ].x < p[1 ].x && p[6 ].x > p[2 ].x) { printf ("6\n" ); } else if (p[1 ].x == p[5 ].x && p[1 ].y == p[5 ].y) { printf ("4\n" ); } else if (p[3 ].x == p[7 ].x && p[3 ].y == p[7 ].y) { printf ("4\n" ); } else if (p[2 ].x == p[6 ].x && p[2 ].y == p[6 ].y) { printf ("4\n" ); } else if (p[4 ].x == p[8 ].x && p[4 ].y == p[8 ].y) { printf ("4\n" ); } else { printf ("5\n" ); } } else { printf ("4\n" ); } } return 0 ; }
1010 Quailty and CCPC HDU 6666 签到题。
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 ;typedef long long ll;const int maxn = 1e6 + 10 ;struct Team { char name[20 ]; ll p, t; } te[maxn]; int cmp (Team t1, Team t2) { if (t1.p == t2.p) return t1.t < t2.t; return t1.p > t2.p; } int main () { int T; cin >> T; while (T--) { int n; int d; scanf ("%d%d" , &n, &d); for (int i = 0 ; i < n; ++i) { scanf ("%s%lld%lld" , &te[i].name, &te[i].p, &te[i].t); } sort(te, te + n, cmp); if ((d * n) % 10 == 5 ) { int ans = d * n / 10 ; printf ("%s\n" , te[ans].name); } else { printf ("Quailty is very great\n" ); } } return 0 ; }
题意: 有 $n$ 个班级,每个班有 $a_i$ 个人,做了 $b_i$ 杯奶茶,每个班的每个人最多喝一杯奶茶且不能和自己班做的奶茶,问最多共有多少人喝到奶茶。
思路 最初的想法是用一个 $sum$ 记录所有剩余的奶茶数,然后每个组能喝的奶茶数为 $sum -$ 该组的奶茶(自己不能喝自己的) $+$ 上一组做的奶茶 (上一组减掉的加回来)。后来发现有点问题,就是中间一步减掉自己的奶茶可能是减多的,也就是上一组喝掉的可能就是当前组的奶茶,那么当前组剩余的奶茶是比原来少的,于是就用 $tmp2$ 保存上一组喝掉的奶茶数,每次让上一组喝掉当前组的奶茶,如果不够喝再用 $tmp$ 保存还要喝掉的奶茶数,往下迭代。
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 #include <bits/stdc++.h> using namespace std ;typedef long long ll;const int maxn = 1e6 + 10 ;struct Team { ll m, n; } t[maxn]; int cmp (Team t1, Team t2) { return t1.m > t2.m; } int main () { int T; cin >> T; while (T--) { int n; scanf ("%d" , &n); ll sum = 0 ; for (int i = 0 ; i < n; ++i) { scanf ("%lld%lld" , &t[i].m, &t[i].n); sum += t[i].n; } sort(t, t + n, cmp); ll ans = 0 ; ll tmp = t[0 ].n; ll tmp2 = 0 ; for (int i = 0 ; i < n; ++i) { if (i) { if (t[i].n < tmp2 + tmp) { t[i].n = 0 ; tmp = tmp2 + tmp - t[i].n; } else { t[i].n = t[i].n - (tmp2 + tmp); tmp = 0 ; } } sum -= t[i].n; if (i) sum += t[i - 1 ].n; if (sum >= t[i].m) { ans += t[i].m; sum -= t[i].m; tmp2 = t[i].m; } else { ans += sum; sum -= sum; tmp2 = sum; } } printf ("%lld\n" , ans); } 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 ;typedef long long ll;const int maxn = 1e6 + 10 ;ll a[maxn], b[maxn]; int main () { int T; scanf ("%d" , &T); while (T--) { int n; scanf ("%d" , &n); ll sum = 0 ; for (int i = 0 ; i < n; ++i) { scanf ("%lld%lld" , &a[i], &b[i]); sum += b[i]; } ll ans = 0 ; for (int i = 0 ; i < n; ++i) { ans += min(a[i], sum - b[i]); } printf ("%lld\n" , min(ans, sum)); } return 0 ; }