Kyooma's Blog

2021CCPC广州

  • ~10.27K 字

题目来自: The 2021 CCPC Guangzhou Onsite

F - Cactus

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

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

ll f[N];

void solve(){
	int n;
	scanf("%d", &n);
	printf("%lld\n", f[n]);
}

int main(){
	int T = 1;
	f[1] = 1;
	f[2] = 1;
	for(int i = 3; i <= N - 10; i++){
		f[i] = (f[i - 1] + f[i - 2]) % mod;
	}
//	scanf("%d", &T);
	while(T--) solve();
	return 0;
}

H - Three Integers

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

using namespace std;
typedef long long ll;
const int N = 3e5 + 10, mod = 998244353;
void solve(){
	ll n,a,b,c,x,y,z;
	scanf("%lld%lld%lld",&a,&b,&c);
	if(a+b+c==0){
		puts("YES");
		printf("1 1 1\n");
		return;
	}
	if(a==b){
		if(c==a){
			puts("NO");
			return;
		}
		if(c>a){
			z=c;
			y=z+a;
			x=y+a;
			if(a==0){
				z=c;
				x=y=2*c;
			}
		}
		else{
			x=b;
			y=2*b+c;
			z=b+c;
			if(c==0) x=a,y=3*a,z=2*a;
		}
		puts("YES");
		printf("%lld %lld %lld\n",x,y,z);
		return;
	}
	if(a==c){
		if(b==a){
			puts("NO");
			return;
		}
		if(b>a){
			y=b;
			x=y+a;
			z=x+a;
			if(a==0){
				y=b;
				x=z=2*b;
			}
		}
		else{
			y=b+c;
			x=2*c+b;
			z=c;
			if(b==0) x=3*a,y=2*a,z=a;
		}
		puts("YES");
		printf("%lld %lld %lld\n",x,y,z);
		return;
	}
	if(b==c){
		if(a==b){
			puts("NO");
			return;
		}
		if(a>b){
			x=a;
			z=x+b;
			y=z+b;
			if(b==0){
				x=a;
				y=z=2*a;
			}
		}
		else{
			x=a+c;
			y=c;
			z=2*c+a;
			if(a==0) x=2*b,y=b,z=3*b;
		}
		puts("YES");
		printf("%lld %lld %lld\n",x,y,z);
		return;
	}
	if(a>b&&a>c){
		x=a;
		z=a+c;
		y=a+b+c;
	}
	if(b>a&&b>c){
		y=b;
		x=a+b;
		z=a+b+c;
	}
	if(c>a&&c>b){
		z=c;
		y=b+c;
		x=a+b+c;
	}
	puts("YES");
	printf("%lld %lld %lld\n",x,y,z);
}

int main(){
	int T = 1;
	cin>>T;
//	scanf("%d", &T);
	while(T--) solve();
	return 0;
}

C - Necklace

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

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

ll a[N], n, m;

bool check(ll p){
	ll l = 1, r = 1;
	for(int i = 1; i <= m; i++){
		ll lt = l + 1, rt = r + p;
		lt = max(lt, a[i] + 1);
		rt = min(rt, a[i + 1]);
		if(lt > rt) return false;
		l = lt, r = rt;
	}
	if(r == n + 1) return true;
	ll t = n + 1 - r;
	l = r = 1 - t;
	for(int i = 1; i <= m; i++){
		ll lt = l + 1, rt = r + p;
		lt = max(lt, a[i] + 1);
		rt = min(rt, a[i + 1]);
		if(lt > rt) return false;
		l = lt, r = rt;
	}
	return r >= n + 1 - t;
}

void solve(){
//	read(n);read(m);
//	for(int i = 1; i <= m; i++) read(a[i]);
	cin >> n >> m;
	for(int i = 1; i <= m; i++) cin >> a[i];
	for(int i = m; i >= 1; i--){
		a[i] = a[i] - a[1] + 1;
	}
	a[m + 1] = n + 1;
	ll l = 1, r = 1e18;
	while(l <= r){
		ll mid = (l + r) >> 1;
		if(check(mid)) r = mid - 1;
		else l = mid + 1;
	}
	printf("%lld\n", l);
}

int main(){
	int T = 1;
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	//cin>>T;
//	scanf("%d", &T);
	while(T--) solve();
	return 0;
}

G - Slope

SOLUTION

看了题解才知道原来莫队真正的复杂度。

时间复杂度 $O(\frac{n^2}{S} + mS)$, $n$为长度, $m$个询问, 块长为 $S$ (一般取 $\sqrt{n}$ 或 $\frac{n}{\sqrt{m}}$)

线段树部分我感觉还是非常简单的，直接维护左端和右端暴力合并即可（可能是cf评测姬比较快才让我过了）。

update: 原来之前跑的慢是因为块长写了70忘记开更号了，哈哈。

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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
#include <bits/stdc++.h>

using namespace  std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 7e5 + 10, M = 7e3 + 10;

#define gc()(is==it?it=(is=in)+fread(in,1,Q,stdin),(is==it?EOF:*is++):*is++)
const int Q=(1<<24)+1;
char in[Q],*is=in,*it=in,c;
void read(int &n){
    int f = 1;
    for(n=0, c = gc(); c<'0'||c>'9';){
        if(c == '-') f = -f;
    }
    for(;c<='9'&&c>='0';c=gc())n=n*10+c-48;
    n *= f;
}

int unit = 9;
vector<int> py;

struct Info{
    ll xl, yl, xr, yr;
    int fz, fm;
    int cnt;
}info[M << 2];

void Min(int &fz, int &fm, int z, int m){
    if(1ll * fz * m > 1ll * fm * z){
        fz = z;
        fm = m;
    }
}

Info merge(Info &p, Info &q){
    if(p.cnt == 0 && q.cnt == 0) return {0, 0, 0, 0, 1, 0, 0};
    if(p.cnt == 0) return q;
    if(q.cnt == 0) return p;
    if(p.fz == 0 || q.fz == 0){
        return {p.xl, p.yl, q.xr, q.yr, 0, 1, p.cnt + q.cnt};
    }
    int fz = abs(p.yr - q.yl), fm = abs(p.xr - q.xl);
    Min(fz, fm, p.fz, p.fm);
    Min(fz, fm, q.fz, q.fm);
    return {p.xl, p.yl, q.xr, q.yr, fz, fm, p.cnt + q.cnt};
}

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

void upd(int k, int l, int r, int p, int x, int op){
    if(l > p || r < p) return;
    if(l == r){
        info[k].xl += x * op;
        info[k].xr += x * op;
        info[k].cnt += op;
        if(info[k].cnt > 1){
            info[k].fz = 0;
            info[k].fm = 1;
        }else{
            info[k].fz = 1;
            info[k].fm = 0;
        }
        return;
    }
    int mid = (l + r) >> 1;
    upd(k << 1, l, mid, p, x, op);
    upd(k << 1 | 1, mid + 1, r, p, x, op);
    info[k] = merge(info[k << 1], info[k << 1 | 1]);
}

Info res;

void qry(int k, int l, int r, int ql, int qr){
    if(l > qr || r < ql) return;
    if(l >= ql && r <= qr){
        res = merge(res, info[k]);
        return;
    }
    int mid = (l + r) >> 1;
    qry(k << 1, l, mid, ql, qr);
    qry(k << 1 | 1, mid + 1, r, ql, qr);
}

struct node{
    int l, r, yl, yr, id;

    bool operator < (const node &k) const{
        if(l / unit != k.l / unit) return l / unit < k.l / unit;
        return r < k.r;
    }
}query[N];

vector<pii> point;
pii ans[N];
int id[N], len, tot;

void add(int i){
    upd(1, 0, len, id[i], point[i].first, 1);
}

void sub(int i){
    upd(1, 0, len, id[i], point[i].first, -1);
}

void solve(){
    int n, q;
//    scanf("%d%d", &n, &q);
//    cin >> n >> q;
    read(n);read(q);
    for(int i = 0, x, y; i < n; i++){
//        scanf("%d%d", &x, &y);
//        cin >> x >> y;
        read(x);read(y);
        point.emplace_back(x, y);
        py.push_back(y);
    }
    sort(point.begin(), point.end());
    sort(py.begin(), py.end());
    py.erase(unique(py.begin(), py.end()), py.end());
    for(int i = 0, xl, xr, yl, yr; i < q; i++){
//        scanf("%d%d%d%d", &xl, &xr, &yl, &yr);
//        cin >> xl >> xr >> yl >> yr;
        read(xl);read(xr);read(yl);read(yr);
        int pl = (int)(lower_bound(point.begin(), point.end(), pii{xl, -2e9}) - point.begin());
        int pr = (int)(upper_bound(point.begin(), point.end(), pii{xr, 2e9}) - point.begin()) - 1;

        int ql = (int)(lower_bound(py.begin(), py.end(), yl) - py.begin());
        int qr = (int)(upper_bound(py.begin(), py.end(), yr) - py.begin()) - 1;
        if(pl <= pr){
            query[tot++] = {pl, pr, ql, qr, i};
        }else{
            ans[i] = {1, 0};
        }
    }
    for(int i = 0; i < n; i++){
        id[i] = (int)(lower_bound(py.begin(), py.end(), point[i].second) - py.begin());
    }
    sort(query, query + tot);
    len = (int)py.size() - 1;
    build(1, 0, len);
    int L = 0, R = -1;
    for(int i = 0; i < tot; i++){
        while(R < query[i].r){
            R++;
            add(R);
        }
        while(R > query[i].r){
            sub(R);
            R--;
        }
        while(L > query[i].l){
            L--;
            add(L);
        }
        while(L < query[i].l){
            sub(L);
            L++;
        }
        res = {0, 0, 0, 0, 1, 0, 0};
        if(query[i].yl <= query[i].yr){
            qry(1, 0, len, query[i].yl, query[i].yr);
        }
        ans[query[i].id] = {res.fz, res.fm};
    }
    for(int i = 0; i < q; i++){
        int g = __gcd(ans[i].first, ans[i].second);
        if(g){
            ans[i].first /= g;
            ans[i].second /= g;
        }
//        printf("%d %d\n", ans[i].first, ans[i].second);
        cout << ans[i].first << ' ' << ans[i].second << '\n';
    }
}

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