8.14集训

Posted on Edited on In

做题做题做题

PS:时间紧，码风没时间调,题解稍后补上 ### 生成树

click

代码：

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
#include <bits/stdc++.h>
#define int long long
#define debug
using namespace std;
//东方之珠 整夜未眠！
const int mod = 2007;

inline int ksm(int a, int b) {
    int res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
    }
    return res%mod;
}

inline int work(int x){
    return 4 * x * ksm(5, x - 1)%mod;
}

inline int thestars() {
    int x, T;
    cin >> T;
    while (T --) {
        cin >> x;
        cout << work(x) << '\n';
    }
    return 0;
}

int youngore = thestars();

signed main() {;}

硬币购物

click

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>
#define N 100001
using namespace std;
//男儿有胆气 仗剑走天涯

int i, j, T, sum;
long long res, dp[N+10], t;
int c[5], d[5];

int main () {
    for (i = 1; i <= 4; ++ i) cin >> c[i];
    dp[0] = 1;
    for (i = 1; i <= 4; ++ i)
        for (j = c[i]; j <= N; ++ j)
            dp[j] += dp[j-c[i]];
    cin >> T;
    while (T --> 0) {
        res = 0;
        for (i = 1; i <= 4; ++ i) cin >> d[i];
        cin >> sum;
        for (i = 0; i <= 15; ++ i) {
            t = sum;
            int cnt(0);
            for (j = 1; j <= 4; ++ j) if ((i>>(j-1))&1) t -= c[j]*(d[j]+1), cnt^=1;
            if (t<0) continue;
            if (!cnt) res += dp[t];
            else res -= dp[t];
        }
        cout << res << '\n';
    }
    return 0;
}

玉蟾宫

click

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>
#define LL long long
#define debug
using namespace std;
//东方之珠 整夜未眠！
const int N = 1e3+10;

int a[N][N], sta[N], lp[N], rp[N];
char str[5];

inline int thestars() {
    int i, j, n, m, res(0), dadada(0);
    scanf ("%d%d", &n, &m);
    for (i = 1; i <= n; ++ i) {
        for (j = 1; j <= m; ++ j) {
            scanf ("%s", str);
            if (str[0] == 'F') {
                a[i][j] = a[i - 1][j] + 1;
            }
        }
        res = 0, sta[0] = 0;
        for (j = 1; j <= m; ++ j) {
            while (res && a[i][j] <= a[i][sta[res]]) -- res;
            lp[j] = sta[res], sta[++ res] = j;
        }
        res = 0, sta[res] = m + 1;
        for (j = m; j; -- j) {
            while (res && a[i][j] <= a[i][sta[res]]) -- res;
            rp[j] = sta[res], sta[++ res] = j;
        }
        for (j = 1; j <= m; ++ j) {
            dadada = max(dadada, a[i][j]*(rp[j] - lp[j] - 1));
        }
    }
    cout << dadada*3;
    return 0;
}

int youngore = thestars();

signed main() {;}

最大数

click

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>
#define LL long long
#define debug
using namespace std;
//东方之珠 整夜未眠！
const int N = 1e5+66;

char str[5];

struct node {int num, pos;}sta[N]; int top;
inline bool operator < (int x, node y) {return x < y.pos;}

inline void Insert(int num, int pos) {
    node x;
    x.num = num, x.pos = pos;
    while (top && num > sta[top].num) sta[top --] = sta[0];
    sta[++ top] = x;
}

inline int thestars() {
    int n, M, D, res(0), t(0);
    cin >> M >> D;
    while (M --) {
        scanf ("%s%d", str, &n);
        if (str[0] == 'A') {
            n += t, n %= D;
            Insert(n, ++ res);
        } else{
            t = upper_bound(sta + 1, sta + top + 1, res - n) -> num;
            cout << t << '\n';
        }
    }
    return 0;
}

int youngore = thestars();

signed main() {;}

矩阵

click

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
#include <bits/stdc++.h>
#define LL long long
#define debug
using namespace std;
//东方之珠 整夜未眠！
const int N = 1e5+66;

int x[N], y[N], z[N], f[N], r[N];

inline int fin(int x) {
    if (f[x] == x) return x;
    int t = f[x];
    f[x] = fin(t);
    r[x] += r[t];
    return f[x];
}

inline int thestars() {
    int T; cin >> T;
    while (T --) {
        int i, j, n, m, k;
        scanf ("%d%d%d", &n, &m, &k);
        for (i = 1; i <= k; ++ i) {
            scanf ("%d%d%d", x + i, y + i, z + i);
            y[i] += n;
        }
        for (i = 1; i <= n+m; ++ i) f[i] = i, r[i] = 0;
        int fx, fy;
        for (i = 1; i <= k; ++ i) {
            fx = fin(x[i]), fy = fin(y[i]);
            if (fx != fy) f[fx] = fy, r[fx] = z[i] + r[y[i]] - r[x[i]];
            else if (r[x[i]] - r[y[i]] != z[i]) break;
        }
        if (i > k) puts("Yes");
        else puts("No");
    }
    return 0;
}

int youngore = thestars();

signed main() {;}

管农场

click

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
#include <bits/stdc++.h>
#define LL long long
#define debug
using namespace std;
//东方之珠 整夜未眠！
const int N = 3e5+66;

int a[N], f[N], ans[N], pd[N];

struct edge{int to, nex;}e[N<<1]; int head[N<<1], cnt;

inline void add(int x, int y) {
    e[++ cnt].to = y;
    e[cnt].nex = head[x];
    head[x] = cnt;
}

inline int fin(int x) {return f[x] == x ? x : f[x] = fin(f[x]);}

inline int thestars() {
    int i, j, k, n, m, res(0);
    //res shi lian tong kuai de shu liang
    int x, y;
    cin >> n >> m;
    for (i = 1; i <= m; ++ i) {
        scanf ("%d%d", &x, &y);
        add(x, y), add(y, x);
    }
    for (i = 1; i <= n; ++ i) {
        scanf ("%d", a+i);
        f[i] = i;
    }
    for (k = n; k >= 1; -- k) {
        x = a[k], pd[x] = 1;
        ++ res;
        for (i = head[x]; i; i = e[i].nex) {
            y = e[i].to;
            if (pd[y]) {
                int fx = fin(x), fy = fin(y);
                if (fx != fy) {
                    f[fx] = fy;
                    -- res;
                }
            }
        }
        ans[k] = (res == 1);
    }
    for (i = 1; i <= n; ++ i) {
        cout << (ans[i] ? "Yes" : "NO") << '\n';
    }
    return 0;
}

int youngore = thestars();

signed main() {;}

小白逛公园

click

数组版本！！！！,特别鸣谢gzh大佬

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

const int N = 5e5+66;

int n, m, ans;
int a[N], d[N<<6], zuo[N<<6], you[N<<6], duo[N<<6],tot;

inline void build (int s, int t, int p) {
    if (s == t) {
        d[p] = zuo[p] = you[p] = duo[p] = a[s];
        return;
    }
    int m = (s+t)>>1;
    build (s, m, p<<1), build (m+1, t, (p<<1)|1);
    d[p] = (d[p<<1] + d[(p<<1)|1]);
    zuo[p] = max (zuo[p<<1], d[p<<1]+zuo[(p<<1)|1]);
    you[p] = max (you[(p<<1)|1], d[(p<<1)|1]+you[p<<1]);
    duo[p] = max (max(duo[p<<1], duo[(p<<1)|1]), you[p<<1]+zuo[(p<<1)|1]);
}

inline void chenge (int x, int c, int s, int t, int p) {
    if (s == t) {
        d[p] = zuo[p] = you[p] = duo[p] = c;
        return;
    }
    int m = (s+t)>>1;
    if (x <= m) chenge (x, c, s, m, p<<1);
    if (x > m) chenge (x, c, m+1, t, (p<<1)|1);
    d[p] = (d[p<<1] + d[(p<<1)|1]);
    zuo[p] = max (zuo[p<<1], d[p<<1]+zuo[(p<<1)|1]);
    you[p] = max (you[(p<<1)|1], d[(p<<1)|1]+you[p<<1]);
    duo[p] = max (max(duo[p<<1], duo[(p<<1)|1]), you[p<<1]+zuo[(p<<1)|1]);
}

inline int get_sum (int l, int r, int s, int t, int p) {
    if(l <= s && t <= r) return p;
    int m = (s + t)>>1, sum(0);
    if(r <= m) return get_sum (l, r, s, m, p<<1);
    if(l > m) return get_sum (l, r, m+1, t, (p<<1)|1);
    int t1 = get_sum (l, r, s, m, p<<1), t2 = get_sum (l, r, m+1,t, (p<<1)|1);
    int ans = ++ tot;
    d[ans] = d[t1] + d[t2];
    zuo[ans] = max (zuo[t1], d[t1] + zuo[t2]);
    you[ans] = max (you[t2], d[t2] + you[t1]);
    duo[ans] = max (max (duo[t1], duo[t2]), you[t1] + zuo[t2]);
    return ans;
}

main () {
    // freopen("test.out", "w", stdout);
    cin >> n >> m;
    tot=(n<<3)+1;
    for (int i = 1; i <= n; ++ i) cin >> a[i];
    build (1, n, 1);
    for (int i = 1; i <= m; ++ i) {
        int opt, x, y;
        cin >> opt >> x >> y;
        if (opt == 1) {
            if (x > y) swap (x, y);
            cout << duo[get_sum(x, y, 1, n, 1)] << '\n';
        } else chenge (x, y, 1, n, 1);
    }
    return 0;
}