Sakana~
0%

SZUACM 2022组队积分赛1-6 题解+总结

发表于 更新于 分类于

菜鸟爬回来补题了www

把能做的补了（我都做出来了的题就不放了）

SZUACM 2022组队积分赛1-6 题解+总结

A. Great Graphs

No. 1 – A 构造题

https://codeforces.com/problemset/problem/1540/A

题意

给出 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
32
33
34
35
36
37
38
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int n;
ll d[N];

void solve () {
    scanf ("%d", &n);
    int neg = 0;
    for (int i = 1; i <= n; i++) {
        scanf ("%lld", &d[i]);
        if (d[i] < 0)   neg ++;
    }
    sort (d + 1, d + n + 1);
    
    ll ans = 0, sum = 0;
    if (d[n] > 0)   ans += d[n];
    neg ++; //第一个>=0的数
    for (int i = 1; i <= n; i++) {
        if (d[i] < 0)   ans += d[i];
        else {
            ans -= (d[i] * (i-neg) - sum);
            sum += d[i];
        }
    }

    printf ("%lld\n", ans);
}

signed main () {
    int t;
    scanf ("%d", &t);
    while (t --)    solve ();
}

//找到第一个>=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 N = 1e5 + 5;
int n;
ll d[N], b[N];

void solve () {
    scanf ("%d", &n);
    for (int i = 1; i <= n; i++)    scanf ("%lld", &d[i]);
    sort (d + 1, d + n + 1);
    
    ll ans = 0, sum = 0;
    for (int i = 1; i <= n; i++)    b[i] = d[i] - d[i-1], sum += b[i];
    for (int i = 1; i <= n; i++)    ans += b[i] * (i-1) * (n-i+1);
    printf ("%lld\n", sum - ans);
}

signed main () {
    int t;
    scanf ("%d", &t);
    while (t --)    solve ();
}

//找到第一个>=0的边

B - Median Pyramid Easy

https://atcoder.jp/contests/agc006/tasks/agc006_b?lang=en

No. 1 – F 构造题

题意

给你n，总共n层，每层 i 方块数量为 2i-1，最底层必须要是全排列。然后构造规则是：当前块b等于b下方三个的中位数。输入层数和最顶端的那个数字，问能不能构造出最底层

分析

由构造规则 当前块b等于b下方三个的中位数 得，

只要保证最底行的中间三个是 m-1 m m+1 即可实现最顶层是m

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 <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;
int a[N];

int main () {
    int n, m;
    scanf ("%d%d", &n, &m);
    if (m == 1 || m == 2*n - 1) {
        printf ("No\n");
    }
    else {
        printf ("Yes\n");
        set <int> s;
        for (int i = 1; i < 2*n; i++) {
            if (i != m && i != m-1 && i != m+1) 
                s.insert (i);
        }
        a[n-1] = m-1, a[n] = m, a[n+1] = m+1;
        for (int i = 1; i < 2*n; i++) {
            if (i != n && i != n-1 && i != n+1) {
                a[i] = *s.begin();
                s.erase(a[i]);
            }
        }
        
        for (int i = 1; i < 2*n; i++)   printf ("%d\n", a[i]);
    }
}

//b等于b下方三个的中位数

B. Destruction of a Tree

https://codeforces.com/problemset/problem/963/B

No. 1 – D 构造题

题意

给定一个 n 个节点的树，每次可以从树上选择一个度为偶数的节点进行删除，每删除一个节点，与这个节点相连的所有边都被删除，问能否删除整棵树。

分析

考察边与点的关系。

树中，若点数为偶数，则边数为奇数，不可能删完。

对于每个点，如果他得父亲能被摧毁，那么要先摧毁父亲。否则先摧毁儿子的话，会使得父亲得度数变为奇数，就没法摧毁父亲了。

跑一遍拓扑排序

B. Mike and Feet

https://codeforces.com/problemset/problem/547/B

No. 1 – C 单调栈

题意

给定序列a，求长度分别为1,2,3,…,n 的连续子序列中最大的最小值

分析

对于每一个 ai 可以找到最左边和最右边满足 ai>aj 的j，并记录答案：li = j, ri = j，（若未找到则记录 li=0, ri=n+1）代表**(li, ri)** 区间内的最小值是 ai。而这一过程可以用 单调栈 实现。

然后就可以记录长度为len的区间的最大值，即 ans[len] = max (ans[len], a[i]);

又因为 ans[1]>=ans[2]>=…>=ans[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
29
30
31
32
33
34
#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;
int n, a[N];
int l[N], r[N]; //最左边小于ai的aj的下标,最右边小于ai的aj的下标
int ans[N];

int main () {
    cin >> n;
    for (int i = 1; i <= n; i++)    cin >> a[i], l[i] = 0, r[i] = n+1;
    
    stack <int> s;
    for (int i = 1; i <= n; i++) {
        while (!s.empty() && a[i] <= a[s.top()])   s.pop();
        if (!s.empty())     l[i] = s.top();
        s.push (i);
    }
    while (!s.empty())  s.pop();

    for (int i = n; i >= 1; i--) {
        while (!s.empty() && a[i] <= a[s.top()])    s.pop();
        if (!s.empty())     r[i] = s.top();
        s.push (i);
    }

    for (int i = 1; i <= n; i++) {
        int len = r[i] - l[i] - 1; //开区间
        ans[len] = max (ans[len], a[i]);
    }

    for (int i = n-1; i >= 1; i--)  ans[i] = max (ans[i], ans[i+1]);
    for (int i = 1; i <= n; i++)    cout << ans[i] << ' ';
}

田忌赛马

https://www.luogu.com.cn/problem/P1650

No. 2 – A 线性dp

分析

如果马的实力不相等的话可以直接贪心，但是相等的话，就要考虑 dp

最优策略一定是按照齐王的马从强到弱来排的，那么田忌可以选择使用dp来安排马，则有

f[k][i][j]:还剩k+1轮,用了i~j匹马;因为j-i+1=n-k+1,可以不开k

区间dp

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
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 1005;

int n, a[N], b[N];
int f[N][N], c[N][N]; 
//f[i][j]:还剩n-(j-i)轮时,用了i-j匹马; c[i][j]:a[i]与b[j]对战后田忌会获得多少

int main () {
    while (cin >> n, n) {
        for (int i = 1; i <= n; i++)    cin >> a[i];
        for (int i = 1; i <= n; i++)    cin >> b[i];
        sort (a+1, a+n+1), sort (b+1, b+n+1);

        memset (f, 0, sizeof f);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (a[i] > b[j])    c[i][j] = 200;
                else if (a[i] < b[j])   c[i][j] = -200;
                else    c[i][j] = 0;
            }
        }

        //区间dp
        for (int len = 1; len <= n; len++) {
            for (int l = 1; l + len - 1 <= n; l++) {
                int r = l + len - 1;
                if (len == 1)   f[l][r] = c[l][len];
                else    f[l][r] = max (f[l+1][r] + c[l][len], f[l][r-1] + c[r][len]);
            }
        }

        cout << f[1][n] << endl;
    }
}

D. Very Suspicious

https://codeforces.com/problemset/problem/1670/D

No. 2 – C 找规律

题意

给定无限大的六边形区域（蜂巢），每次可以沿着六边形的任意一条边画一条直线，问最少需要多少条直线能划分出 n 个三角形。注意得到的正三角形内部不能再有直线。

分析

三角形数 = 交点数*2

交点数公式：n 条直线相交，最多有 n*(n-1)/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
#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N = 1e5 + 5, M = 1e9;
int a[N], b[N], n;

void solve () {
    int x;
    cin >> x;
    cout << lower_bound (a + 1, a + n + 1, x) - a << endl;
}

void pre () {
    while (a[n ++] <= M) {
        if (n % 3 == 1)     b[n] = b[n-1];
        else    b[n] = b[n-1] + 2;
        a[n] = a[n-1] + b[n];
    }
}

signed main () {
    pre ();
    int t;
    cin >> t;
    while (t --)    solve ();
}

D. Round Subset

https://codeforces.com/problemset/problem/837/D

No. 2 – E 线性dp

题意

n 个数中任选 k 个相乘，问其积的后缀0最多为多少

分析

易得2*5=10，所以要统计每个数字能分解出的2和5的数量，然后答案就是要使得 min(sum_cnt2, sum_cnt5) 最大

然后直接 dp，f[i][j][k]表示选到第i个数，选了j个数时，cnt5=k 时，cnt2 的数量

第一维可以用 vector 的 swap 操作来滚掉

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
#include <bits/stdc++.h>
#define int long long

using namespace std;
typedef pair<int, int> pii;
const int N = 205, M = 6005;
int n, k;
pii p[N]; //cnt2, cnt5

void test () {
    for (int i = 1; i <= n; i++)    printf ("%lld %lld\n", p[i].first, p[i].second);
}

signed main () {
    scanf ("%lld%lld", &n, &k);
    for (int i = 1; i <= n; i++)  {
        int t;  scanf ("%lld", &t);
        while (t % 2 == 0)   p[i].first ++, t /= 2;
        while (t % 5 == 0)   p[i].second ++, t /= 5;
    }
    //test (); 
    vector <vector<int>> f (k+1, vector<int>(n*30, -1));
    f[0][0] = 0; //f[i][j]:选了i个数,cnt5=j时的cnt2数

    for (int i = 1; i <= n; i++) {
        int c2 = p[i].first, c5 = p[i].second;
        auto g = f;
        for (int j = 0; j <= min (k, i); j++) { //选了多少个数
            for (int k = 0; k < 30*n; k++) { //cnt5
                if (j == 0 || k - c5 < 0 || f[j-1][k-c5] == -1)     continue;
                g[j][k] = max (g[j][k], f[j-1][k-c5] + c2);   
            }
        }
        f.swap(g);
    }

    int ans = 0;
    for (int i = 0; i < n*30; i++) {
        if (f[k][i] == -1)  continue;
        ans = max (ans, min (i, f[k][i]));
    }
    printf ("%lld\n", ans);
}

//分解, 计2,5的个数
//min(sum_cnt2, sum_cnt5)最大

B. Appleman and Tree

https://codeforces.com/problemset/problem/461/B

No. 2 – B 树形dp

题意

给出一棵树，每个节点有黑色或白色，现在要求删掉一些边后形成的联通块每个块内都恰好有一个黑点，求方案数。

分析

请看大佬的讲解：

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
#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N = 1e5 + 5, mod = 1e9 + 7;
int h[N], e[N*2], ne[N*2], idx;
int n, f[N*2][2]; //0表i放入白块,1表放入黑块的合法方案

void add (int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs (int u, int fa) {
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (v == fa)    continue;
        dfs (v, u);

        f[u][1] = (f[u][1] % mod * (f[v][0] % mod + f[v][1] % mod) + f[u][0] * f[v][1] % mod) % mod;
        f[u][0] = (f[u][0] % mod * (f[v][0] % mod + f[v][1] % mod) % mod) % mod;
    }
}

signed main () {
    memset (h, -1, sizeof h);
    cin >> n;
    for (int i = 1; i < n; i++) {
        int x;  cin >> x;
        add (i, x), add (x, i);
    }
    for (int i = 0; i < n; i++) {
        int x;  cin >> x;
        f[i][x] = 1;
    }
    dfs (0, -1);
    cout << f[0][1];
}

D. Deleting Divisors

https://codeforces.com/problemset/problem/1537/D

No. 3 – C 博弈论

题意

现有一个数字 x，A 和 B 轮流操作，每次可以减去非1且非n的x的因数，最终不能操作者输

分析

博弈论的提最重要的就是考虑清楚各种情况，不能有遗漏

  • x为奇数
    • x为质数，A必输
    • x为合数，可表示为奇数×奇数的形式，A操作之后变为奇数×偶数，B可以选择再取偶因子，又变为奇数×奇数的形式，即使得先手始终面临奇数×奇数的状态，不难得出先手的最终态为1×质数，A必输。
  • x为偶数
    • x不是2的幂次，则可表示为奇数×2的幂 的形式，先手抽走一个奇数，变为奇数×（2的幂-1），即奇数×奇数的状态，对应上述必输态，则A必胜。
    • x是2的奇数次幂，A操作之后变为奇数×2的幂 的形式，对应上述必胜态，则B必胜
    • x是2的偶数次幂，A操作之后x变为2的奇数次幂，对应上述必胜态，则A必胜

由此分析完毕，注意各个状态之间是可以灵活转移的

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
#include <bits/stdc++.h>

using namespace std;

void solve () {
    int n;
    scanf ("%d", &n);
    bool A;
    if (n & 1)  A = false;
    else {
        int cnt = 0;
        while (n % 2 == 0) {
            cnt ++;
            n /= 2;
        }
        if (n > 1)  A = true; //1 !!
        else if (cnt & 1)   A = false;
        else    A = true;
    }
    
    if (!A)     printf ("Bob\n");
    else        printf ("Alice\n");
}

int main () {
    int t;
    scanf ("%d", &t);
    while (t --)    solve ();
}

Muddy Fields

http://poj.org/problem?id=2226

No. 3 – D 二分图最小点覆盖

学了二分图之后来写

Snowflake Snow Snowflakes

http://poj.org/problem?id=3349

No. 4 – F 字符串哈希

（早该刷刷蓝书了！）

题意

因为雪花的形状是封闭的环形，所以从任何一个角开始顺时针或逆时针往后记录长度，得到的六元组都代表形状相同的雪花。

给出n片雪花，判断有无两片相等

分析

（这题似乎有些问题？？逃

C. Meximum Array

https://codeforces.com/problemset/problem/1629/C

No. 4 – A 数据结构 mex

题意

给定一个长度为 N 的数组 a ，你可以将 a 的前缀的 mex 放入数组 b 中，并且在 a 中删除前缀。

问 b 的最大的字典序是多少。

分析

对于mex的一些基操，可以看看ygg的mex笔记

策略：每次选则最大的第一个mex值，从他开始切断。

我写了一个暴力更新的，然后TLE了， 其实只要加个小小的优化，也就是记录一个mex后缀就能很快更新出来了。

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
#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;
int a[N], l[N], n, maxn;

struct mex {
    vector <int> s; //未出现过的数
    int cnt [N];
    int id = 0;
    
    void add (int x) {
        s.push_back (x);
        cnt[x] ++;
    }

    int Mex () {
        while (cnt[id]) id ++;
        return id;
    }

    void clear () {
        id = 0;
        for (auto i : s)    cnt[i] --;
        s.clear ();
    }
}lst, pre;

void solve () {
    memset (l, 0, sizeof l);
    scanf ("%d", &n);
    for (int i = 1; i <= n; i++)    scanf ("%d", &a[i]);
    
    pre.clear(), lst.clear();
    for (int i = n; i >= 1; i--)    lst.add (a[i]), l[i] = lst.Mex();

    int mx = l[1];
    vector <int> ans;
    for (int i = 1; i <= n; i++) {
        pre.add (a[i]);
        if (pre.Mex() == mx) {
            ans.push_back (mx);
            mx = l[i+1];
            pre.clear();
        }
    }
    
    printf ("%d\n", ans.size());
    for (auto i : ans)  printf ("%d ", i);
    printf ("\n");
}

int main () {
    int t;
    scanf ("%d", &t);
    while (t --)    solve ();
}


//前缀mex
//每次都在sum_mex里面找到最大的sum_mex[i], 
//再从i+1开始求sum_mex,直至i==n (该过程相当于删去mex)
//优化:mex的更新方式

C. Anu Has a Function

https://codeforces.com/problemset/problem/1300/C

No. 5 – D 数学 + 二进制

其实这题我是想出来了但是不咋会实现，果然码力太弱

题意

定义操作，f(x,y)=(x|y)-y，现将数列 a 重新排序，使得f(f(…f(f(a1,a2),a3),…an−1),an)最大。

分析

二进制的题最好按位去分析，不难列出只有下述四种情况：

0|0-0=0; 1|1-1=0; 0|1-1=0; 1|0-0=1

所以要尽可能把当前为只有一个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
32
33
34
35
36
#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;
int a[N], cnt[31], n; //cnt[i]:第i位上是1的数有cnt[i]个

int main () {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        for (int j = 0; j < 30; j++) {
            if (a[i] >> j & 1)  cnt[j] ++;
        }
    }   

    int maxn = -1, maxn_id = 1;
    for (int i = 1; i <= n; i++) {
        int cur = 0;
        for (int j = 0; j < 30; j++) {
            if (cnt[j] == 1 && (a[i] >> j & 1))   cur += 1 << j;
        }
        
        if (maxn < cur) {
            maxn = cur, maxn_id = i;
        }
    }

    swap (a[1], a[maxn_id]); //字典序最大
    for (int i = 1; i <= n; i++)    cout << a[i] << ' ';
}



//0|0-0=0; 1|1-1=0; 0|1-1=0; 1|0-0=1
//(1, 0)->1
//从高位到低位按照10排序

Feel Good

http://poj.org/problem?id=2796

No. 5 – B 单调栈

题意

找出 区间和×区间最小值 最大的一段

分析

和第四题 B. Mike and Feet 挺像的

对于每一个 ai 可以找到最左边和最右边满足 ai>aj 的j，并记录答案 li = j, ri = j，表示 (li, ri) 的最小值是 ai，前缀和预处理从而得区间和。

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
#include <iostream>
#include <algorithm>
#include <stack>
#define int long long

using namespace std;
const int N = 100005;
int a[N], sum[N], n;
int l[N], r[N];

signed main () {
    scanf ("%lld", &n);
    for (int i = 1; i <= n; i++) {
        scanf ("%lld", &a[i]);
        sum[i] = sum[i-1] + a[i];
        l[i] = 0, r[i] = n + 1;
    }

    stack <int> s;
    for (int i = n; i >= 1; i--) {
        while (!s.empty() && a[s.top()] >= a[i])    s.pop();
        if (!s.empty())     r[i] = s.top();
        s.push (i);
    }
    while (!s.empty())  s.pop();
    for (int i = 1; i <= n; i++) {
        while (!s.empty() && a[s.top()] >= a[i])    s.pop();
        if (!s.empty())     l[i] = s.top();
        s.push (i);
    }

    int ans = -1, L, R;
    for (int i = 1; i <= n; i++) {
        int len = (sum[r[i]-1] - sum[l[i]]) * a[i]; //开区间
        if (len > ans) {
            L = l[i] + 1, R = r[i] - 1;
            ans = len;
        }
    }

    printf ("%lld\n%lld %lld", ans, L, R);
    //cout << ans << endl << L << ' ' << R;
}

//(s[r]-s[l-1])*min(s[l], s[l+1], ..., s[r])最大

//单调栈+前缀和

（呃呃我很生气。。。一模一样的代码把G++换成C++就过了，害我想了贼久为什么）

AreYouBusy

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

No. 5 – E 背包dp

题意

给出了多组工作，每组工作的选择规则不同。

组0至少要选一项，组1最多选一项，组2任意选。

分析

f[i][j]:选到第i组,容量为j的最大值

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
#include <bits/stdc++.h>

using namespace std;
const int N = 105;
int n, t;
int f[N][N]; //f[i][j]:选到第i组,容量为j的最大值
int v[N], w[N];

void solve () {
    memset (f, 0, sizeof f);
    for (int i = 1; i <= n; i++) {
        int m, s;
        cin >> m >> s;
        for (int j = 1; j <= m; j++)    cin >> v[j] >> w[j];
        if (s == 0) {
            for (int j = 0; j <= t; j++)    f[i][j] = -1e9;
            for (int j = 1; j <= m; j++) {
                for (int k = t; k >= v[j]; k--) {
                    f[i][k] = max (f[i][k], max (f[i-1][k-v[j]] + w[j], f[i][k-v[j]] + w[j]));
                }
            }
        }

        else if (s == 1) {
            for (int j = 0; j <= t; j++)    f[i][j] = f[i-1][j];
            for (int j = 1; j <= m; j++) {
                for (int k = t; k >= v[j]; k--) {
                    f[i][k] = max (f[i][k], f[i-1][k-v[j]] + w[j]);
                }
            }
        }

        else {
            for (int j = 0; j <= t; j++)    f[i][j] = f[i-1][j];
            for (int j = 1; j <= m; j++) {
                for (int k = t; k >= v[j]; k--) {
                    f[i][k] = max (f[i][k], f[i][k-v[j]] + w[j]);
                }
            }
        }
    }
    cout << max (-1, f[n][t]) << endl;
}

int main () {
    while (cin >> n >> t) {
        solve ();
    }
}

//组0至少要选一项，组1最多选一项，组2任意选

C - The Majority

https://atcoder.jp/contests/arc134/tasks/arc134_c?lang=en

No. 5 – A 组合数学

题意

有 k 个盒子，ai 个球 i，现在要把球安排到盒子里去，使得每个盒子里面球1的数量都占优势。

分析

一个巧妙的思路：先每个盒子放一个1，然后其他球放入的时候每个在捆绑一个1即可

大于2e7了，要用 Lucas

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
#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 1e5 + 10, mod = 998244353;

int binpow(int b, int k) {
    int res = 1;
    while (k) {
        if (k & 1)
            res = (LL)res * b % mod;
        b = (LL)b * b % mod;
        k >>= 1;
    }
    return res;
}

int C(int a, int b) {
    if (a < b)  return 0;
    int res = 1, inv = 1;
    for (int i = a; i > a - b; i--)
        res = (LL)res * i % mod;
    for (int i = b; i; i--)
        inv = (LL)inv * i % mod;
    return (LL)res * binpow(inv, mod - 2) % mod;
}

int lucas(int a, int b) {
    if (!a || !b)
        return 1;
    return (LL)C(a % mod, b % mod) * lucas(a / mod, b / mod) % mod;
}
 
signed main () {
    int n, k, a1;
    LL ans = 1;
    cin >> n >> k >> a1;
    a1 -= k;
    for (int i = 1; i < n; i++) {
        int x;
        cin >> x;   
        a1 -= x;
        if (a1 < 0) {
            cout << 0;
            return 0;
        }
        ans = (ans * lucas (x+k-1, k-1)) % mod;
    }
    ans = (ans * lucas (a1+k-1, k-1)) % mod;
    cout << ans;
}


//每个先放一个1，然后其他序号的捆绑一个1进去

Exploration

https://vjudge.net/problem/HDU-5222

No. 5 – C 缩点

题意

给你n个点，m1条无向边，m2条有向边的图，问存不存在环

分析

无向图部分用并查集判断，然后重新缩点建一个有向图用强连通去判断。

感觉是比较经典的题，但是我的缩点不是很熟，所以不太会写

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
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <iostream>
#include <cstring>
#include <stack>
#include <algorithm>
#pragma comment(linker, "/STACK:102400000,102400000") 

using namespace std;
typedef pair<int, int> pii;
const int N = 1000005, M = N*3;

int h[N], e[M], ne[M], idx;
int n, m1, m2;
int fa[N], dfn[N], low[N];
bool in_stk[N], suc;
stack <int> stk;
int timestamp, scc_cnt;

void init () {
    memset (h, -1, sizeof h);
    idx = timestamp = scc_cnt = 0;
    for (int i = 1; i <= n; i++)    fa[i] = i;
    suc = false;
    memset (dfn, 0, sizeof dfn);
    memset (in_stk, false, sizeof in_stk);
}

int find (int x) {
    if (x != fa[x]) {
        fa[x] = find (fa[x]);
    }
    return fa[x];
}

void add (int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void tarjan (int u) {
    if (suc)    return ;
    dfn[u] = low[u] = ++ timestamp;
    stk.push (u), in_stk[u] = true;

    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (!dfn[j]) {
            tarjan(j);
            low[u] = min (low[u], low[j]);
        }
        else if (in_stk[j])     low[u] = min (low[u], dfn[j]);
    }

    if (dfn[u] == low[u]) {
        int cnt = 0, y;
        scc_cnt ++;
        do {
            y = stk.top();
            stk.pop();
            cnt ++;
            in_stk[y] = false;
        } while (y != u);

        if (cnt >= 2) {
            suc = true;
            return ;
        }
    }
}


void solve () {
    scanf ("%d%d%d", &n, &m1, &m2);
    init ();
    for (int i = 0; i < m1; i++)  {
        int u, v;
        scanf ("%d%d", &u, &v);
        int x = find (u), y = find (v);
        if (x == y)     suc = true;
        fa[x] = y;
    }

    for (int i = 0; i < m2; i++)  {
        int u, v;
        scanf ("%d%d", &u, &v);
        int x = find (u), y = find (v);
        if (x == y)     suc = true;
        if (suc)    continue;
        add (x, y);
    }

    if (suc) {
        printf ("YES\n");
        return ;
    }

    for (int i = 1; i <= n; i++) {
        if (suc)    break;
        if (fa[i] == i && !dfn[i])  tarjan (i);
    }

    if (suc)    printf ("YES\n");
    else    printf ("NO\n");
    
}

int main () {
    int t;
    scanf ("%d", &t);
    while (t --)    solve ();
}

//找一个环
//无向图部分用并查集判断，然后重新缩点建一个有向图用强连通去判断。

Can you answer these queries III

https://www.spoj.com/problems/GSS3/en/

No. 6 – F 线段树

题意

单点修改，查询区间最大连续字段和

分析

十分经典的题，没做出来的我实在是欠打

最大连续子段和可以在 前缀最大子段和，后缀最大子段和，左右合并中间的最大子段和 中取最大的。

横跨两区间的最大子段和 = 左子区间最大后缀 + 右子区间最大前缀

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
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 5e5 + 5;
int n, m, k, x, y;
int a[N];

struct tree{
    int l, r, sum;
    int lmax, rmax, tmax;//最大前后缀和, 最大子段和
}st[4 * N];

void pushup (tree &u, tree &l, tree &r){
    u.sum = l.sum + r.sum;
    u.lmax = max (l.lmax, l.sum + r.lmax);//左半段中的最大 or 左半段和+右半段中的最大
    u.rmax = max (r.rmax, r.sum + l.rmax);//右半段中的最大 or 右半段和+左半段中的最大
    u.tmax = max (max (l.tmax, r.tmax), l.rmax + r.lmax);//左半段中的最大 or 右半段中的最大 or 左半段后缀和+右半段前缀和
}

void pushup (int u){
    pushup (st[u], st[u << 1], st[u << 1 | 1]);
}

void build (int u, int l, int r){
    if (l == r){
        st[u] = {l, r, a[r], a[r], a[r], a[r]};
        return;
    }
    st[u] ={l, r};
    int mid = l + r >> 1;
    build (u << 1, l, mid), build (u << 1 | 1, mid + 1, r);
    pushup (u);
}

void modify (int u, int x, int v){
    if (st[u].l == x && st[u].r == x)
        st[u] = {x, x, v, v, v, v};
    else{
        int mid = st[u].l + st[u].r >> 1;
        if (x <= mid)
            modify (u << 1, x, v);
        else    
            modify (u << 1 | 1, x, v);
        pushup (u);
    }
}

tree query (int u, int l, int r){
    if (st[u].l >= l && st[u].r <= r)
        return st[u];
    int mid = st[u].l + st[u].r >> 1;
    if (r <= mid)
        return query (u << 1, l, r);
    else if (l > mid)
        return query (u << 1 | 1, l, r);
    else{
        auto le = query (u << 1, l, r);
        auto ri = query (u << 1 | 1, l, r);
        tree ans;
        pushup (ans, le, ri);
        return ans;
    }

}

int main(){
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];
    build (1, 1, n);
    
    cin >> m;
    while (m --){
        cin >> k >> x >> y;
        if (k == 0)
            modify (1, x, y);
        else{
            if (x > y)
                swap (x, y);
            cout << query (1, x, y).tmax << endl;
        }
        
    }

}
//维护和
//对于横跨两区间的最大子段和 = 左子区间最大后缀 + 右子区间最大前缀

B. Queue

https://codeforces.com/problemset/problem/91/B

No. 6 – B 二分

题意

输出每个数最右边的严格比他小的距离

分析

维护一个后缀min，然后直接二分

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 <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;
int a[N], b[N], n; //后缀min

int main () {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)    cin >> a[i];
    b[n] = a[n];
    for (int i = n-1; i >= 1; i--)  b[i] = min (b[i+1], a[i]);

    for (int i = 1; i <= n; i++) {
        int l = i, r = n;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (b[mid] < a[i])  l = mid;
            else    r = mid - 1;
        }
        if (a[r] >= a[i])   cout << "-1 ";
        else    cout << r - i - 1 << ' ';
    }
}


//距离最右边的严格比他小的距离
//如何二分出最后一个小于他的数
//倒过来看第一个大于他的数

//a[j] < a[i] && a[j+1] >= a[i]

（1500的题都莫得想法）

A Puzzle for Pirates

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

No. 6 – D 博弈论

题意

有n个海盗，分m块金子，其中他们会按一定的顺序提出自己的分配方案，如果50%以上的人赞成，则方案通过，开始分金子，如果不通过，则把提出方案的扔到海里，下一个人继续。

分金决策的三个标准：保命，拿更多的金子，杀人，优先级是递减的。

分析

这是博弈论的经典问题——海盗分金问题

https://blog.csdn.net/acm_cxlove/article/details/7853916

如果金币够分的时候，最后一个人分的最多，然后隔一个贿赂一人一定最优。

不够分的时候，可以模拟一下过程，发现 必死的人一定会支持后一个人，必活的人一定不支持后一个人。

多写几项找规律得出，2*m+2^k^ 就是决策者，(2*m+2^k-1^, 2*m+2^k) 范围内的人必死，其他人可能分到也可能不分到金币，那么最小就是0。决策者为了活命也一定是0。

操作：预处理1e4范围内的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
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>

using namespace std;
const int N = 1e4 + 5;
int two[15]={2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768};

void solve () {
    int n, m, x;
    scanf ("%d%d%d", &n, &m, &x);
    if (2*m >= n) {
        int ans = m - (n-1)/2;
        if (n & 1) {
            if (x == n) printf ("%d\n", ans);
            else if (x & 1) printf ("1\n");
            else    printf ("0\n");
        }
        else {
            if (x == n) printf ("%d\n", ans);
            else if (x & 1) printf ("0\n");
            else    printf ("1\n");            
        }
    }

    else if (n == 2*m + 1) {
        if (x < 2*m && x & 1)  printf ("1\n");  
        else    printf ("0\n");  
    }

    else {
        int xx = n - 2*m;
        for (int i = 0; i < 14; i++) {
            if (xx == two[i]) {
                printf ("0\n");
                return ;
            }
        }

        for (int i = 1; i < 14; i++) {
            if (xx >= two[i])   continue;
            //找到必死区间
            if (x > 2*m + two[i-1] && x < 2*m + two[i])     printf ("Thrown\n");
            else    printf ("0\n");
            break;
        }
    }
}

int main () {
    int t;
    scanf ("%d", &t);
    while (t --)    solve ();
}

Article

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

No. 6 – C 概率dp

推式子见注释

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
#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;
int n, x;
double f[N], p; //f[i]:输入第i个字符的期望值

void solve () {
    double ans = 1e9;
    cin >> n >> p >> x;
    //f[i]=p*(1+f[i-1]+f[i])+(1-p)*(1+f[i-1]);
    for (int i = 1; i <= n; i++)    f[i] = (1 + f[i-1]) / (1 - p);
    for (int i = 1; i <= n; i++) { //i保存次数
        int k = n / i, cnt = n % i, res = i - cnt;
        ans = min (ans, cnt * f[k+1] + res * f[k] + i * x);
        //cnt个字符分配到r块中，要敲k+1个字符
        //剩余的res块则只需要敲k个字符
    }
    cout << fixed << setprecision (6) << ans << endl;
}

int main () {
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        cout << "Case #" << i << ": ";
        solve ();
    }
}