Kyooma's Blog

2022-10-23周赛

  • ~12.79K 字

题目来自: 2019 ICPC Universidad Nacional de Colombia Programming Contest

这场发挥的巨拉胯，连简单dp都不会了…感觉其他题都是会做的可是都没看。

C - Common Subsequence

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
#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, M = 1e3 + 10;

char s[N], t[N];
int dp[M][M];

void solve() {
    scanf("%s%s", s + 1, t + 1);
    int n = strlen(s + 1), ans = 0;
    int p = min(n, n / 100);
    for(int i = 0; i <= p; i++){
        for(int j = 0, m; j <= p; j++){
            for(m = dp[i][j];m + i < n && m + j < n && s[m + i + 1] == t[m + j + 1];m++);
            ans = max(ans, m);
            dp[i + 1][j] = max(dp[i + 1][j], m);
            dp[i][j + 1] = max(dp[i][j + 1], m);
        }
    }
    if(ans * 100 >= 99 * n) puts("Long lost brothers D:");
    else puts("Not brothers :(");
}

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

A - Amazon

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
#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;

struct line{
    ll a, b, c;
    bool operator < (const line &p) const{
        if(a != p.a) return a < p.a;
        if(b != p.b) return b < p.b;
        return c < p.c;
    }
};

pii calc(ll x, ll y){
    ll g = __gcd(y, x);
    if(g) y /= g, x /= g;
    if(x < 0) x = -x, y = -y;
    return {y, x};
}

void solve() {
    map<line, int> mp;  
    map<pii, int> vp;
    int n;
    cin >> n;
    ll ans = 0;
    for(int i = 0; i < n; i++){
        int x1, x2, y1, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        ll a = x2 - x1, b = y2 - y1, c = y1 * (x2 - x1) - (y2 - y1) * x1;
        ll g = __gcd(a, b);
        g = __gcd(g, c);
        if(g) a /= g, b /= g, c /= g;
        if(mp.count(line{a, b, c})) continue;
        mp[line{a, b, c}]++;
        ll y = y2 - y1, x = x2 - x1;
        pii p = calc(x, y);
        vp[p]++;
        x = -x;
        p = calc(y, x);
        if(vp.count(p)){
            ans += vp[p];
        }
    }
    cout << ans << '\n';
}

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

J - Jail Destruction

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
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;
const int N = 1e5 + 10, Log = 20, inf = 0x3f3f3f3f;

int a[N];

struct Info{
    ll sum, lz;
    int h, cnt;
    void merge(Info &p1, Info &p2){
        sum = p1.sum + p2.sum;
        h = min(p1.h, p2.h);
        cnt = p1.cnt + p2.cnt;
    }
}info[N << 2];

void apply(int k, ll lz){
    info[k].sum -= lz * info[k].cnt;
    info[k].lz += lz;
    info[k].h -= lz;
    if(info[k].sum == 0){
        info[k].cnt = 0;
    }
}

void pd(int k){
    if(!info[k].lz) return;
    apply(k << 1, info[k].lz);
    apply(k << 1 | 1, info[k].lz);
    info[k].lz = 0;
}

void build(int k, int l, int r){
    if(l == r){
        info[k] = {a[l], 0, a[l], 1};
        return;
    }
    int mid = (l + r) >> 1;
    build(k << 1, l, mid);
    build(k << 1 | 1, mid + 1, r);
    info[k].lz = 0;
    info[k].merge(info[k << 1], info[k << 1 | 1]);
}

void upd(int k, int l, int r, int ql, int qr, int x){
    if(r < ql || l > qr) return;
    if(info[k].cnt == 0) return;
    if(l >= ql && r <= qr){
        if(info[k].h >= x){
            info[k].sum -= 1ll * x * info[k].cnt;
            info[k].lz += x;
            info[k].h -= x;
            if(info[k].sum == 0){
                info[k].cnt = 0;
                info[k].h = inf;
            }
            return;
        }
        if(l == r){
            info[k] = {0, 0, inf, 0};
            return;
        }
    }
    pd(k);
    int mid = (l + r) >> 1;
    upd(k << 1, l, mid, ql, qr, x);
    upd(k << 1 | 1, mid + 1, r, ql, qr, x);
    info[k].merge(info[k << 1], info[k << 1 | 1]);
}

ll qry(int k, int l, int r, int ql, int qr){
    if(l > qr || r < ql) return 0;
    if(l >= ql && r <= qr){
        return info[k].sum;
    }
    pd(k);
    int mid = (l + r) >> 1;
    return qry(k << 1, l, mid, ql, qr) + qry(k << 1 | 1, mid + 1, r, ql, qr);
}

void solve() {
    int n, q;
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while(q--){
        int op, l, r, x;
        cin >> op >> l >> r;
        if(op == 1){
            ll sum = 0;
            if(l <= r){
                sum = qry(1, 1, n, l, r);
            }else{
                sum = qry(1, 1, n, l, n) + qry(1, 1, n, 1, r);
            }
            cout << sum << '\n';
        }else{
            cin >> x;
            if(l <= r){
                upd(1, 1, n, l, r, x);
            }else{
                upd(1, 1, n, l, n, x);
                upd(1, 1, n, 1, r, x);
            }
        }
    }
}

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

L - Liquid X

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
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>

using namespace std;

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

bool v[N];
int f[N], a[N], n, c[N];

int ask(int p){
    while(p){
        int now = f[p];
        c[now]++;
        p -= a[now];
    }
    cout << "1\n";
    for(int i = 0; i < n; i++){
        cout << c[i] << ' ';
        c[i] = 0;
    }
    cout << endl;
    string res;
    cin >> res;
    if(res == "red") return 2;
    if(res == "green") return 0;
    return 1;
}

void solve() {
    cin >> n;
    v[0] = true;
    for(int i = 0, x; i < n; i++){
        cin >> x;
        a[i] = x;
        for(int j = x; j <= M; j++){
            if(v[j - x] && !v[j]){
                v[j] = true;
                f[j] = i;
            }
        }
    }
    vector<int> b;
    for(int i = 1; i <= M; i++){
        if(v[i]) {
            b.push_back(i);
        }
    }
    int l = 0, r = (int)b.size() - 1;
    while(l <= r){
        int mid = (l + r) >> 1;
        int res = ask(b[mid]);
        if(res == 0) l = mid + 1;
        else if(res == 1){
            cout << "2\n" << b[mid] << endl;
            return;
        }else{
            r = mid - 1;
        }
    }
    if(r < 0 && b[0] == 2){
        cout << "2\n1" << endl;
    }else if(l >= b.size() && b.back() == M - 1){
        cout << "2\n" << M << endl;
    }else if(b[l] - b[r] == 2){
        cout << "2\n" << b[r] + 1 << endl;
    }else{
        cout << "2\n-1" << endl;
    }
}

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

H - Hardest Challenge

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>

using namespace std;

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

ll pw[2][N], ans[2] = {mod, mod};
string s[2][3];
vector<ll> v;

void run(int now, int tar, int p, ll sum){
	if(now == tar){
		v.push_back(sum);
		return;
	}
	for(int i = 0; i < 3; i++){
		ll tsum = (ll)s[p][i][now] * pw[p][now] % mod + sum;
		if(tsum >= mod) tsum -= mod;
		run(now + 1, tar, p, tsum);
	}
}

void calc(int now, int tar, int p, ll sum){
	if(now == tar){
		ll t = mod - sum;
		auto pt = lower_bound(v.begin(), v.end(), t);
		if(pt != v.end()){
			t = sum + (*pt);
			if(t >= mod) t -= mod;
			ans[p] = min(ans[p], t);
		}
		t = sum + v[0];
		if(t >= mod) t -= mod;
		ans[p] = min(ans[p], t);
		return;
	}
	for(int i = 0; i < 3; i++){
		ll tsum = (ll)s[p][i][now] * pw[p][now] % mod + sum;
		if(tsum >= mod) tsum -= mod;
		calc(now + 1, tar, p, tsum);
	}
}

void solve() {
	int A, B;
	cin >> A >> B;
	for(int i = 0; i < 3; i++) cin >> s[0][i];
	for(int i = 0; i < 3; i++) cin >> s[1][i];
	pw[0][A - 1] = 1;
	for(int i = A - 2; i >= 0; i--){
		pw[0][i] = pw[0][i + 1] * 127 % mod;
	}
	pw[1][B - 1] = 1;
	for(int i = B - 2; i >= 0; i--){
		pw[1][i] = pw[1][i + 1] * 127 % mod;
	}
	run(0, A / 2, 0, 0);
	sort(v.begin(), v.end());
	calc(A / 2, A, 0, 0);
	v.clear();
	run(0, B / 2, 1, 0);
	sort(v.begin(), v.end());
	calc(B / 2, B, 1, 0);
//	dbg(ans[0], ans[1]);
	if(ans[0] < ans[1]){
		cout << "Owls\n";
	}else if(ans[0] == ans[1]){
		cout << "Tie\n";
	}else{
		cout << "Goats\n";
	}
}

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

E - Extreme Image

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#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, M = 72000;

int sum[N << 2], lz[N << 2];

void apply(int k, int x){
    sum[k] += x;
    lz[k] += x;
}

void pd(int k){
    if(!lz[k]) return;
    apply(k << 1, lz[k]);
    apply(k << 1 | 1, lz[k]);
    lz[k] = 0;
}

void upd(int k, int l, int r, int ql, int qr, int x){
    if(l > qr || r < ql) return;
    if(l >= ql && r <= qr){
        sum[k] += x;
        lz[k] += x;
        return;
    }
    pd(k);
    int mid = (l + r) >> 1;
    upd(k << 1, l, mid, ql, qr, x);
    upd(k << 1 | 1, mid + 1, r, ql, qr, x);
    sum[k] = max(sum[k << 1], sum[k << 1 | 1]);
}

struct P{
    int d, r;
    bool operator < (const P &p) const{
        return d < p.d;
    }
}a[N];

void upd(int r, int rx, int x){
    int tl = max(rx - r, 0), tr = rx;
    // dbg(tl, tr, x);
    upd(1, 0, M, tl, tr, x);
}

void solve() {
    int n, d, r, fz, fm;
    scanf("%d %d %d.%d", &n, &d, &fz, &fm);
    r = fz * 100 + fm;
    for(int i = 0, dx, rx; i < n; i++){
        scanf("%d %d.%d", &dx, &fz, &fm);
        rx = fz * 100 + fm;
        a[i] = {dx, rx};
    }
    sort(a, a + n);
    // for(int i = 0; i < n; i++){
    //     dbg(a[i].d, a[i].r);
    // }
    int rt = 0, ans = 0;
    for(int lt = 0; lt < n; lt++){
        while(rt < n && a[rt].d <= a[lt].d + d){
            upd(r, a[rt].r, 1);
            upd(r, a[rt].r + 36000, 1);
            rt++;
        }
        // dbg(lt, rt, cnt);
        ans = max(ans, sum[1]);
        upd(r, a[lt].r, -1);
        upd(r, a[lt].r + 36000, -1);
    }
    printf("%d\n", ans);
}

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