https://acm.hdu.edu.cn/showproblem.php?pid=7311 gcd

题目大意

给定 $n$ 个二元组（称为 $N_i$），$q$ 次询问，每次询问给出二元组 $(A, B)$ ，每次操作可让 $(A, B)$ 变成 $(A + B, B)$ 或 $(A, A + B)$，最多能够到达几个 $N_i$。

题解

发现给定的 $N_i$ 可以进行辗转相减，且存在唯一的前驱和后驱，例如： $$ (17, 12) \rightarrow (5, 12) \rightarrow (5, 7) \rightarrow (5, 2) \rightarrow (3,2) \rightarrow (1, 2) \rightarrow (1, 1) $$

然而二元组的值域范围给得很大，这样做显然过不了，但是由辗转相减很容易想到辗转相除，这样的复杂度就降到了 $O(log\ w)$。上面的例子就会被压缩成：

$$ (17, 12) \rightarrow (5, 12) \rightarrow (5, 2) \rightarrow (1, 2) \rightarrow (1, 1) $$

将上述二元组每一个看成一个单独的节点，然后存放他们所有的后继，因为每一个后继对应一个 $N_i$，因此对于这样的一个二元组而言，后继的个数即是能够到达 $N_i$ 的个数。

对于每次询问，只要在对应的二元组中找到位次就能轻松计算答案。

参考代码

 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

typedef pair<ll, ll> PLL;
void solve() {
    map<PLL, vector<PLL>> mp;
    int n, q;
    cin >> n >> q;
    for(int i = 0; i < n; i ++) {
        ll a, b;
        cin >> a >> b;
        while(a && b) {
            if(a > b) {
                mp[{a % b, b}].push_back({a, b});
                a %= b;
            } else {
                mp[{a, b % a}].push_back({a, b});
                b %= a;
            }
        }
    }
    for(auto &[a, b] : mp) {
        sort(b.begin(), b.end());
    }
    for(int i = 0; i < q; i ++) {
        ll a, b;
        cin >> a >> b;
        int res = 0;
        if(a >= b) {
            res += mp[{a % b, b}].end() - lower_bound(mp[{a % b, b}].begin(), mp[{a % b, b}].end(), make_pair(a, b));
        } 
        if(b >= a) {
            res += mp[{a, b % a}].end() - lower_bound(mp[{a, b % a}].begin(), mp[{a, b % a}].end(), make_pair(a, b));
        }
        cout << res << '\n';
    }
}

https://acm.hdu.edu.cn/showproblem.php?pid=7318 mobius

https://acm.hdu.edu.cn/showproblem.php?pid=7308 2-sat

题目大意

给定 $2n$ 个三元组 $A_i(a_i,b_i,c_i)$ 和 $A_i’(a_i’,b_i’,c_i’)$，保证 $a_i \leq a_i’, b_i \leq b_i’, c_i \leq c_i’$，对于$\forall i$，可以选择 $A_i$或者 $A_i’$，求任意两个三元组每项差的最大可能的最小值。

题解

由于 $a_i \leq a_i’, b_i \leq b_i’, c_i \leq c_i’$ 的存在，可以首先让每个人选择 $A_i$ ，每次贪心地将极值最大的那个人换成 $A_i’$，记录过程中答案的最小值。

复杂度 $O(n log n)$。但是这个贪心的正确性难以证明。

更能说明正确性的是二分答案， 优化建图，$2-sat$ check 的方法。

参考代码

 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

typedef pair<int, int> PII;
void solve() {
    int n;
    cin >> n;
    struct Z {
        int a, b, c;
    };
    
    vector<Z> A(n), B(n);
    for(int i = 0; i < n; i ++) {
        cin >> A[i].a >> A[i].b >> A[i].c >> B[i].a >> B[i].b >> B[i].c;
    }
    vector<bool> vis(n);
    set<PII> sa, sb, sc;
    for(int i = 0; i < n; i ++) {
        sa.insert({A[i].a, i});
        sb.insert({A[i].b, i});
        sc.insert({A[i].c, i});
    }
    int res = INF;
    do {
        int id = -1;
        int difa = sa.rbegin() -> first - sa.begin() -> first;
        int difb = sb.rbegin() -> first - sb.begin() -> first;
        int difc = sc.rbegin() -> first - sc.begin() -> first;
        res = min(res, max({difa, difb, difc}));
        if(difa >= difb && difa >= difc) {
            id = sa.begin() -> second;
        } else if (difb >= difa && difb >= difc) {
            id = sb.begin() -> second;
        } else if (difc >= difa && difc >= difb) {
            id = sc.begin() -> second;
        }
        if(id == -1 || vis[id]) break;
        vis[id] = true;
        sa.erase({A[id].a, id});
        sb.erase({A[id].b, id});
        sc.erase({A[id].c, id});
        sa.insert({B[id].a, id});
        sb.insert({B[id].b, id});
        sc.insert({B[id].c, id});
    } while(true);
    cout << res << '\n';
}

https://ac.nowcoder.com/acm/contest/57358/J

题目大意

构造一个长度为 $n$ 的数组，满足

$$ \forall\ i, -m\leq a_i\leq m\ \forall\ 1 \leq l < r \leq n, \sum_{i=l}^r a_i \geq 0\ $$

求所有可能的数组的个数。

题解

考虑一个线性 $dp$，发现第 $i$ 位的选数只与之前的后缀最小值有关，因此可以设计一个二维的$dp$，第一维度表示选数，第二维表示当前选数状态下的后缀最小值。

可以写出 $dp$ 递推关系

$$ dp_{i,j} \rightarrow dp_{i + 1, x}, 0 \leq j, j - m \leq x \leq j + m \\ dp_{i,j} \rightarrow dp_{i + 1, x} 0 > j, 0 \leq x \leq j + m \\ $$

利用差分前缀和优化就能 $O(n^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

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<ll>> dp(n, vector<ll> (2 * m + 1));
    for(int i = 0; i <= 2 * m; i ++) dp[0][i] = 1;
    for(int i = 1; i < n; i ++) {
        for(int j = - m; j <= m; j ++) {
            if(j >= 0) {
                dp[i][m - j] += dp[i - 1][j + m];
            } else {
                dp[i][m - 0] += dp[i - 1][j + m];
                dp[i][2 * m + j + 1] -= dp[i - 1][j + m];
            }
        }
        (dp[i][0] += mod) %=mod;
        for(int j = -m + 1; j <= m; j ++) {
            (dp[i][j + m] += mod) %= mod;
            (dp[i][j + m] += dp[i][j + m - 1]) %= mod;
        }
    }
    ll res = 0;
    for(int i = 0; i <= 2 * m; i ++) {
        res += dp[n - 1][i];
    }
    cout << res % mod << '\n';
}

https://ac.nowcoder.com/acm/contest/57356/H

https://ac.nowcoder.com/acm/contest/57357/B

https://ac.nowcoder.com/acm/contest/57357/E https://acm.hdu.edu.cn/showproblem.php?pid=7309

https://acm.hdu.edu.cn/showproblem.php?pid=7301 https://acm.hdu.edu.cn/showproblem.php?pid=7294

https://acm.hdu.edu.cn/showproblem.php?pid=7320 https://acm.hdu.edu.cn/showproblem.php?pid=7319