AtCoder Beginning Contest 186
pE 讓我卡了一下，於是就掉分了。pF 想到了一個假解，浪費了不少時間。可能是因為剛打完 CF，所以狀態不好。
A. Brick
1#include<bits/stdc++.h>
2using namespace std;
3int main() {
4 int n, w; cin >> n >> w;
5 cout << n / w << "\n";
6 return 0;
7}B. Blocks on Grid
1#include<bits/stdc++.h>
2using namespace std;
3int main() {
4 ios_base::sync_with_stdio(0); cin.tie(0);
5 int h, w; cin >> h >> w;
6 int sum = 0, m = 105;
7 for (int i = 0; i < h; i++) {
8 for (int j = 0; j < w; j++) {
9 int x; cin >> x;
10 sum += x;
11 m = min(m, x);
12 }
13 }
14 cout << sum - m * h * w << "\n";
15 return 0;
16}C. Unlucky 7
求 1 ~ n 中，有多少個數的十進位和八進位都沒有 7。
1#include<bits/stdc++.h>
2using namespace std;
3bool check(int n, int k) {
4 while (n) {
5 if (n % k == 7) return false;
6 n /= k;
7 } return true;
8}
9int main() {
10 int n; cin >> n;
11 int cnt = 0;
12 for (int i = 1; i <= n; i++)
13 cnt += check(i, 10) & check(i, 8);
14 cout << cnt << "\n";
15 return 0;
16}D. Sum of difference
求 |ai - aj|, i < j 的總和。
1#include<bits/stdc++.h>
2using namespace std;
3typedef long long ll;
4int main() {
5 ios_base::sync_with_stdio(0); cin.tie(0);
6 int n; cin >> n;
7 vector<ll> a(n);
8 for (int i = 0; i < n; i++)
9 cin >> a[i];
10 sort(a.begin(), a.end());
11 vector<ll> sum(n + 1);
12 for (int i = n - 1; i >= 0; i--)
13 sum[i] = sum[i + 1] + a[i];
14 ll ans = 0;
15 for (int i = 0; i < n; i++)
16 ans += sum[i + 1] - a[i] * (n - i - 1);
17 cout << ans << "\n";
18 return 0;
19}E. Throne
先用 extgcd(k, n) 求 xk + bn = gcd(k, n)，再求 xk % n = s 的最小整數解。
1#include<bits/stdc++.h>
2using namespace std;
3typedef long long ll;
4typedef pair<ll, ll> pii;
5ll gcd (int a, int b) {
6 return b ? gcd(b, a % b) : a;
7}
8pii extgcd(ll a, ll b) {
9 if (!b) return {1, 0};
10 ll k = a / b;
11 pii p = extgcd(b, a - k * b);
12 return {p.second, p.first - k * p.second};
13}
14int main() {
15 ios_base::sync_with_stdio(0); cin.tie(0);
16 int T; cin >> T;
17 while (T--) {
18 ll n, s, k; cin >> n >> s >> k;
19 ll g = gcd(n, k);
20 if (s % g) {
21 cout << "-1\n"; continue;
22 }
23 ll ans = -extgcd(k, n).first * s / g;
24 ans %= n / g;
25 if (ans <= 0) ans += n / g;
26 cout << ans << "\n";
27 }
28 return 0;
29}F. Rook on Grid
給定一個 H x W 的棋盤，以及 M 個障礙物。 (H, W, M ≤ 2e5)
求從 (1, 1) 出發 Rook 能在兩步內到達的格子有幾個？
1#include<bits/stdc++.h>
2using namespace std;
3typedef long long ll;
4typedef pair<int, int> pii;
5#define x first
6#define y second
7#define maxn 200005
8class RangeUpdateBIT {
9 private:
10 ll d[maxn], dd[maxn];
11 ll sum(int i) {
12 ll s = 0, ss = 0;
13 int c = i + 1;
14 while (i > 0) s += d[i], ss += dd[i], i -= i & -i;
15 return c * s - ss;
16 }
17 void add(int i, ll v) {
18 int c = i;
19 while (i < maxn)
20 d[i] += v, dd[i] += c * v, i += i & -i;
21 }
22 public:
23 RangeUpdateBIT() {
24 memset(d, 0, sizeof(d));
25 memset(dd, 0, sizeof(dd));
26 }
27 ll sum(int l, int r) { return sum(r) - sum(l - 1); }
28 void add(int l, int r, ll v) {
29 add(l, v), add(r + 1, -v);
30 }
31};
32int main() {
33 ios::sync_with_stdio(0); cin.tie(0);
34 int h, w, m; cin >> h >> w >> m;
35 vector<pii> p(m);
36 vector<int> col(w + 1, h + 1), row(h + 1, w + 1);
37 for (int i = 0; i < m; i++) {
38 cin >> p[i].x >> p[i].y;
39 col[p[i].y] = min(col[p[i].y], p[i].x);
40 row[p[i].x] = min(row[p[i].x], p[i].y);
41 }
42 sort(p.begin(), p.end());
43 ll ans = 0;
44 for (int i = 1; i <= w && col[i] > 1; i++)
45 ans += col[i] - 1;
46 RangeUpdateBIT T;
47 T.add(row[1], w + 1, 1);
48 for (int j = 2, pi = 0; j <= h && row[j] > 1; j++) {
49 while (pi < m && p[pi].x < j) pi++;
50 int R = (pi < m && p[pi].x == j) ? p[pi].y : w + 1;
51 ans += T.sum(1, R - 1);
52 while (pi < m && p[pi].x ==j) {
53 if (!T.sum(p[pi].y, p[pi].y))
54 T.add(p[pi].y, p[pi].y, 1);
55 pi++;
56 }
57 }
58 cout << ans << "\n";
59 return 0;
60}