AtCoder Regular Contest 111

A. Simple Math 2

題意

$$1 \leq n \leq 10^{18}, 1 \leq m \leq 10^4, \text{find }\lfloor \frac{10^n}{m}\rfloor \mod m.$$

解法

求 (10 ** n) % (m * m) // m。
紀錄餘數的循環節。
卡題原因：
- 忘記循環不一定從一開始。
- 用了 unordered_map 判斷餘數是否出現過導致 TLE，換成 array 就變很快了。

Code

 1#include<bits/stdc++.h>
 2using namespace std;
 3typedef long long ll;
 4#define pb push_back
 5int s[100000008];
 6int main() {
 7    ll n, m, mm;
 8    cin >> n >> m;
 9    mm = m * m;
10    ll r, d = 1;
11    vector<int> v; // 紀錄餘數
12    for (int i = 0; i <= n; i++) {
13        r = d % mm;
14        if (s[r] || (i && r == v[0])) break;
15        s[r] = i;
16        v.pb(r);
17        d = r * 10;
18    }
19    if (n < v.size()) {
20        cout << v[n] / m << "\n";
21        return 0;
22    }
23    int t = s[r]; // 循環節起點
24    int id = t + (n - t) % (v.size() - t);
25    cout << v[id] / m << '\n';
26    return 0;
27}

B. Reversible Cards

題意

給定 N 張卡（≤2e5），每張卡上正反面各有一個數字（1~4e5），讓你每張牌只能選擇一面，問最多有幾個相異數字？

解法

建立一個 Source，給每張牌 cap = 1 的邊，然後每張牌建立到正反兩面的數字 cap = 1 到邊，每個數字建立到 Sink cap = 1 的邊，之後求最大流 max-flow 即為答案

因為是二分圖，所以用 Dinic 複雜度約為 O(sqrt(V)E) ~ 2e8。

Code

 1#include<bits/stdc++.h>
 2using namespace std;
 3typedef long long ll;
 4typedef pair<int, int> pii;
 5#define pb push_back
 6#define inf 1e9
 7#define maxn 200000
 8#define maxk 400000
 9class Dinic {
10   private:
11    struct edge { int d, r; ll c; };
12    vector<vector<edge>> adj; vector<int> lv, ve; int n;
13    bool mklv(int s, int d) {
14        lv.assign(n, -1); lv[s] = 0; queue<int> q({s});
15        while (!q.empty()) {
16            int v = q.front(); q.pop();
17            for (auto& e : adj[v]) {
18                if (e.c == 0 || lv[e.d] != -1) continue;
19                lv[e.d] = lv[v] + 1, q.push(e.d);
20            }
21        }
22        return lv[d] > 0;
23    }
24    ll aug(int v, ll f, int d) {
25        if (v == d) return f;
26        for (; ve[v] < adj[v].size(); ve[v]++) {
27            auto& e = adj[v][ve[v]];
28            if (lv[e.d] != lv[v] + 1 || !e.c) continue;
29            ll sent = aug(e.d, min(f, e.c), d);
30            if (sent > 0) {
31                e.c -= sent, adj[e.d][e.r].c += sent; 
32                return sent;
33            }
34        } 
35        return 0;
36    }
37   public:
38    Dinic(int n) : n(n + 1) { clear(); }
39    void clear() { adj.assign(n, {}); }
40    void add_edge(int src, int dst, ll cap) {
41        edge ss{dst, (int)adj[dst].size(), cap};
42        edge dd{src, (int)adj[src].size(), 0};
43        adj[src].push_back(ss), adj[dst].push_back(dd);
44    }
45    ll max_flow(int s, int d) {
46        ll ret = 0;
47        while (mklv(s, d)) {
48            ve.assign(n, 0);
49            while (ll f = aug(s, inf, d)) ret += f;
50        } 
51        return ret;
52    }
53};
54int main() {
55    ios::sync_with_stdio(0), cin.tie(0);
56    int n; cin >> n;
57    Dinic D(maxn + maxk + 2);
58    int dst = maxn + maxk + 1;
59    for (int i = 1; i <= n; i++) {
60        int a, b; cin >> a >> b;
61        D.add_edge(0, i, 1);
62        D.add_edge(i, maxn + a, 1);
63        D.add_edge(i, maxn + b, 1);
64    }
65    for (int i = 1; i <= maxk; i++)
66        D.add_edge(maxn + i, dst, 1);
67    cout << D.max_flow(0, dst) << "\n";
68    return 0;
69}