Kyooma's Blog

2022CCPC桂林

  • ~9.50K 字

题目来自: 2022 China Collegiate Programming Contest (CCPC) Guilin Site

vp四题打铜了……

C - Array Concatenation

SOLUTION

骗骗题，实际只有两种情况。

CODE
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
const int N=2e5+10;
const int INF=2e9;

ll a[N],b[N];
void solve(){
    ll n,m,i,sum,ans=0,p=1e9+7,res;
    cin>>n>>m;
    for(i=1;i<=n;i++){
        scanf("%lld",a+i);
    }
    for(i=1;i<=n;i++) a[i+n]=a[i];
    for(i=1;i<=n;i++) b[i]=a[n-i+1];
    for(i=1;i<=n;i++) b[i+n]=a[i+n];
    __int128 x,y;
    x=y=0;
    n*=2;
    m--;
    for(i=1;i<=n;i++){
        x+=(n-i+1)*a[i];
        y+=(n-i+1)*b[i];
    }
    ll len=n;
    sum=res=0;
    for(i=1;i<=n;i++){
        sum=(sum+a[i])%p;
        res=(res+(n-i+1)*a[i])%p;
    }
    sum%=p;
    res%=p;
    for(i=1;i<=m;i++){
        res=(len*sum+2*res)%p;
        sum=sum*2%p;
        len=len*2%p;
    }
    ans=max(ans,res);

    len=n;
    sum=res=0;
    for(i=1;i<=n;i++){
        sum=(sum+b[i])%p;
        res=(res+(n-i+1)*b[i])%p;
    }
    sum%=p;
    res%=p;
    for(i=1;i<=m;i++){
        res=(len*sum+2*res)%p;
        sum=sum*2%p;
        len=len*2%p;
    }
    ans=max(ans,res);
    printf("%lld",ans);
}

int main() {
    int T=1;
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    //cout.tie(nullptr);
//    cin>>T;
    //init();
    for(int i=1;i<=T;i++) {
        solve();
    }
}

E - Draw a triangle

SOLUTION

推出式子发现与$gcd$有关系，可以用$exgcd$求解然后分类讨论。

CODE
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
113
114
115
116
117
118
119
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
const int N=3e5+10;
const int M=6e5+10;
const int INF=2e9;
const int p=10;

ll exgcd(ll a, ll b, ll &x, ll &y){
    if(!b){
        x = 1;
        y = 0;
        return a;
    }
    ll g = exgcd(b, a % b, x, y);
    ll t = x;
    x = y;
    y = t - a / b * y;
    return g;
}

ll calc(pll p1, pll p2, pll p3){
//    ll res = 1ll * (p1.second - p2.second) * p3.first + (p2.first - p1.first) * p3.second - p2.first * p1.second + p1.first * p2.second;
    ll res = (p1.first - p3.first) * (p2.second - p3.second) - (p2.first - p3.first) * (p1.second - p3.second);
    if(res == 0) res = 1e18;
    return abs(res);
}

pll ans{};
ll sum = 1e18;

void run1(int x1, int y1, int x2, int y2){
    ll a = abs(y1 - y2), b = abs(x1 - x2), x, y;
    ll g = exgcd(a, b, x, y);
    x %= b / g;
    if(x <= 0) x += b / g;
//    cout << a << ' ' << b << " ans:: " << x << '\n';
    pll pi[2] = {{x1, y1}, {x2, y2}};
    if(y1 < y2){
        ll tm = (a * x);
        if(tm % b == 0) tm = tm / b - 1;
        else tm = tm / b;
        pll tp = {x1 + x, y1 + tm};
        ll tmp = calc(pi[0], pi[1], tp);
        if(tmp < sum){
            ans = tp;
        }
    }else{
        ll tm = (a * x);
        if(tm % b == 0) tm = tm / b - 1;
        else tm = tm / b;
        pll tp = {x2 - x, y2 + tm};
        ll tmp = calc(pi[0], pi[1], tp);
        if(tmp < sum){
            ans = tp;
        }
    }
}

void run2(int x1, int y1, int x2, int y2){
    ll a = abs(x1 - x2), b = abs(y1 - y2), x, y;
    ll g = exgcd(a, b, x, y);
    x %= b / g;
    if(x <= 0) x += b / g;
//    cout << a << ' ' << b << " ans:: " << x << '\n';
    pll pi[2] = {{x1, y1}, {x2, y2}};
    if(y1 < y2){
        ll tm = (a * x);
        if(tm % b == 0) tm = tm / b - 1;
        else tm = tm / b;
        pll tp = {x2 - tm, y2 - x};
        ll tmp = calc(pi[0], pi[1], tp);
        if(tmp < sum){
            ans = tp;
        }
    }else{
        ll tm = (a * x);
        if(tm % b == 0) tm = tm / b - 1;
        else tm = tm / b;
        pll tp = {x1 + tm, y1 - x};
        ll tmp = calc(pi[0], pi[1], tp);
        if(tmp < sum){
            ans = tp;
        }
    }
}

void solve(){
    int x1, y1, x2, y2;
    scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
    if(x1 == x2){
        printf("%d %d\n", x1 - 1, 114514);
        return;
    }
    if(y1 == y2){
        printf("%d %d\n", 114514, y1 - 1);
        return;
    }
    if(x1 > x2){
        swap(x1, x2);
        swap(y1, y2);
    }
    run1(x1, y1, x2, y2);
    run2(x1, y1, x2, y2);
    printf("%lld %lld\n", ans.first, ans.second);
}

int main() {
    int T=1;
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    //cout.tie(nullptr);
    scanf("%d", &T);
    for(int i=1;i<=T;i++) {
        solve();
    }
}

L - Largest Unique Wins

SOLUTION

聪明构造题，我是笨比。

CODE
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>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 10, Log = 20, inf = 0x3f3f3f3f;

void solve() {
    int n, m, c = 0, now;
    cin >> n >> m;
    now = m;
    for(int i = 1; i <= n; i++){
        c++;
        for(int j = 1; j <= m; j++){
            if(j == now) cout << "1 ";
            else cout << "0 ";
        }
        cout << '\n';
        if(c == 2){
            c = 0;
            now = max(1, now - 1);
        }
    }
}

int main() {
    int T = 1;
    ios::sync_with_stdio(false);
    // cin >> T;
    while (T--) solve();
    return 0;
}

G - Group Homework

SOLUTION

换根dp，找不相交的两条最长带权路径，和最大的四条链。

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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int N = 2e5 + 10, Log = 20, inf = 0x3f3f3f3f;

int dp0[N], a[N], dp1[N];// 0 表示u子树内的最长路径  1 表示u子树内最长链

int ans;

vector<int> e[N];

void dfs(int u, int fa){
    vector<pii> p;
    dp1[u] = dp0[u] = a[u];
    int res = 0;
    for(int i : e[u]){
        if(i == fa) continue;
        dfs(i, u);
        dp1[u] = max(dp1[u], dp1[i] + a[u]);
        res = max(res, dp0[i]);
        p.push_back({dp1[i], i});
    }
    sort(p.begin(), p.end());
    int m = (int)p.size();
    if(!m) return;
    if(m == 1){
        dp0[u] += p[0].first;
    }else{
        dp0[u] += p[m - 1].first + p[m - 2].first;
    }
    dp0[u] = max(dp0[u], res);
}

void dfs(int u, int fa, int mx, int maxline){
    vector<pii> p, q;
    ans = max(ans, maxline + dp0[u]);
    p.push_back({mx, fa});
    q.push_back({0, 0});
    for(int i : e[u]){
        if(i == fa) continue;
        p.push_back({dp1[i], i});
        q.push_back({dp0[i], i});
    }
    sort(p.begin(), p.end());
    sort(q.begin(), q.end());
    int m = (int)p.size(), res = 0, pm = (int)q.size();
    for(int i = m - 1; i >= m - 4 && i >= 0; i--){ // 四条链
        res += p[i].first;
    }
    ans = max(ans, res);
    res = 0;
    for(int i = pm - 1; i >= pm - 2 && i >= 0; i--){ // 两条最大路径
        res += q[i].first;
    }
    ans = max(ans, res);
    for(int i : e[u]){
        if(i == fa) continue;
        int px = 0, py = maxline;
        for(int j = m - 1; j >= 0; j--){
            if(p[j].second != i){
                px = p[j].first;
                break;
            }
        }
        for(int j = pm - 1; j >= 0; j--){
            if(q[j].second != i){
                py = max(py, q[j].first);
                break;
            }
        }
        for(int j = m - 1, c = 0, pr = 0; j >= 0; j--){
            if(p[j].second != i){
                c++;
                pr += p[j].first;
                if(c == 2){
                    py = max(py, pr + a[u]);
                    break;
                }
            }
        }
        dfs(i, u, px + a[u], py);
    }
}

void solve() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    if(n == 1){
        cout << "0\n";
        return;
    }
    for(int i = 1, u, v; i < n; i++){
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1, 0);
    dfs(1, 0, 0, 0);
    cout << ans << '\n';
}

int main() {
    int T = 1;
    ios::sync_with_stdio(false);
    // cin >> T;
    while (T--) solve();
    return 0;
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可