发表更新ICPC/CCPC / Contests / Codeforces13 分钟读完 (大约1938个字)

Educational Codeforces Round 85

比赛链接 / 官方题解链接

A. Level Statistics

Solution

显然，$p$ 和 $c$ 必须非降， $c$ 不大于 $p$ 且 $c$ 增幅不大于 $p$.

Code

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

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

int T, n, p[105], c[105];

int main(){
	read(T);
	while(T--){
		read(n);
		for(int i = 1; i <= n; i++)	read(p[i], c[i]);
		bool ok = true;
		for(int i = 1; i <= n; i++){
			if(p[i] < p[i-1]){
				ok = false;
				break;
			}
			if(c[i] < c[i-1]){
				ok = false;
				break;
			}
			if(c[i] > p[i]){
				ok = false;
				break;
			}
			if(p[i] - p[i-1] < c[i] - c[i-1]){
				ok = false;
				break;
			}
		}
		puts(ok ? "YES" : "NO");
	}
	return 0;
}

B. Middle Class

Solution

从大到小排个序，不断把多的削成 $x$ 移给下一个即可。容易知道这样做其实和均分答案是相同的（可以削平成 $x$ 的数均分后一定也不小于 $x$，不能削平成 $x$ 的数均分后一定都小于 $x$）。

Code

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

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 100005;

int T, n;
LL x, a[N];

bool cmp(int A, int B){ return A > B; }

int main(){
	read(T);
	while(T--){
		read(n, x);
		for(int i = 1; i <= n; i++)	read(a[i]);
		sort(a+1, a+n+1, cmp);
		LL rem = 0;
		for(int i = 1; i <= n; i++){
			if(a[i] < x)	break;
			rem = a[i] - x;
			a[i+1] += rem;
		}
		int cnt = 0;
		for(int i = 1; i <= n; i++)
			cnt += a[i] >= x;
		printf("%d\n", cnt);
	}
	return 0;
}

C. Circle of Monsters

Soution

对于每个怪物来说，它的 $a$ 减去它前一个怪物的 $b$ 是一定需要我们开枪打死的血量，把它们加起来之后，枚举第一个打死的怪物，取代价最小者。

Code

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

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 300005;

int T, n;
LL a[N], b[N], c[N];

int main(){
	read(T);
	while(T--){
		read(n);
		for(int i = 1; i <= n; i++)	read(a[i], b[i]);
		LL ans = 0;
		for(int i = 1; i <= n; i++){
			int j = i + 1; if(j == n + 1) j = 1;
			c[j] = max(0ll, a[j] - b[i]);
			ans += c[j];
		}
		LL mn = 1e16;
		for(int i = 1; i <= n; i++)
			mn = min(mn, a[i] - c[i]);
		printf("%lld\n", ans + mn);
	}
	return 0;
}

D. Minimum Euler Cycle

Solution

路线一定是这样的：$[1,2,1,3,1,4,\cdots,1,n],[2,3,2,4,\cdots,2,n],[3,4,\cdots,3,n],\cdots,[n-1,n],1$（为了体现出规律，用括号把序列分段了）。所以根据该规律，给出位置 $x$，就能找到对应的数。

Code

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

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 100005;

int T, n;
LL l, r, s[N];

inline LL get(LL x){
    LL k = lower_bound(s+1, s+n, x) - s;
    x -= s[k-1];
    LL t = (x + 1) / 2; // k, k+t
    if(x & 1)   return k;
    else    return k + t;
}

int main(){
    read(T);
    while(T--){
        bool ok = false;
        read(n, l, r);
        for(LL i = 1; i <= n - 1; i++)
            s[i] = 2 * (n - i) + s[i-1];
        for(LL i = l; i <= r; i++)
            printf("%lld ", i == 1ll * n * (n - 1) + 1 ? 1 : get(i));
        puts("");
    }
    return 0;
}

E. Divisor Paths

Solution

【参考：dls的视频】

由于所有数都是 $D$ 的因数，设 $D$ 的质因数有 $k$ 个，那么把每个数质因数分解后可以看成一个 $k$ 维向量。$x$ 与 $y$ 之间有边表明这两个向量有且仅有一维差 $1$，于是原图其实是一个 $k$ 维空间的网格图。

设 $d(x)$ 表示 $x$ 的因数个数，那么对于路径 $a_1\rightarrow a_2\rightarrow\cdots\rightarrow a_l$，其长度就是 $d(a_l)-d(a_1)$. 考虑 $u,v$ 两点之间的最短路，发现应该是 $u\rightarrow gcd(u,v)\rightarrow v$ 这么一条路径。于是问题转化成如何求出 $u\rightarrow gcd(u,v)$ 和 $v\rightarrow gcd(u,v)$ 的路径数量，二者乘积就是答案。

这其实是一个多重集的排列数问题，对于 $n_1$ 个 $1$，$n_2$ 个 $2$，$\cdots$，$n_t$ 个 $t$，$n_1+\cdots+n_t=n$，排列总数是 $C(n;n_1,\cdots,n_t)=\frac{n!}{n_1!\cdots n_t!}$.

Code

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

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<LL, LL> pll;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const LL MOD = 998244353;

LL gcd(LL a, LL b){ return b == 0 ? a : gcd(b, a % b); }
LL fpow(LL bs, LL idx){
	LL res = 1;
	while(idx){
		if(idx & 1)	(res *= bs) %= MOD;
		(bs *= bs) %= MOD;
		idx >>= 1;
	}
	return res;
}
vector<pll> getPrimeFactors(LL x){
	vector<pll> res;
	for(LL i = 2; i * i <= x; i++){
		int cnt = 0;
		while(x % i == 0){
			x /= i;
			cnt++;
		}
		if(cnt)	res.pb(mp(i, cnt));
	}
	if(x > 1)	res.pb(mp(x, 1));
	return res;
}

LL D, fact[60] = {1}, invfact[60] = {1};
int q;
vector<pll> d;

LL solve(LL x, LL y){
	LL res = 1, sum = 0;
	for(auto k: d){
		int cntx = 0, cnty = 0;
		while(x % k.first == 0)	x /= k.first, cntx++;
		while(y % k.first == 0)	y /= k.first, cnty++;
		(res *= invfact[cntx - cnty]) %= MOD;
		sum += cntx - cnty;
	}
	(res *= fact[sum]) %= MOD;
	return res;
}

int main(){
	for(int i = 1; i <= 50; i++){
		fact[i] = fact[i-1] * i % MOD;
		invfact[i] = fpow(fact[i], MOD - 2);
	}
	read(D, q);
	d = getPrimeFactors(D);
	while(q--){
		LL u, v; read(u, v);
		LL g = gcd(u, v);
		printf("%lld\n", solve(u, g) * solve(v, g) % MOD);
	}
	return 0;
}

F. Strange Function

Solution

【参考：dls的视频】

设 $dp[i][j]$ 表示考虑 $a$ 中前 $i$ 个数，匹配了 $b$ 中前 $j$ 个数的最小代价，则转移如下：

  • 若 $b[j]==a[i]$，$dp[i][j]$ 可以从 $dp[i-1][j]$ 转移而来，代价加上 $\min(0,p[i])$（即可选可不选）；也可以从 $dp[i-1][j-1]$ 转移而来，此时必选。
  • 若 $b[j]>a[i]$，$dp[i][j]$ 从 $dp[i-1][j]$ 转移而来，代价加上 $\min(0,p[i])$（即可选可不选）。
  • 若 $b[j]<a[i]$，$dp[i][j]$ 从 $dp[i-1][j]$ 转移而来且 $a[i]$ 一定不能选，所以代价加上 $p[i]$。

$dp$ 数组的第一维可以滚掉，空间问题解决；转移无非就是区间加和单点查询，所以线段树维护 $dp$ 数组。

时间复杂度：$O(n\lg m)$

Code

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

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

const LL INF = 1e18;
const int N = 500005;

struct segTree{
    int l, r;
    LL lazy, mn;
}tr[N<<2];
#define lid id<<1
#define rid id<<1|1
#define mid ((tr[id].l+tr[id].r)>>1)
inline void pushup(int id){
    tr[id].mn = min(tr[lid].mn, tr[rid].mn);
}
inline void pushdown(int id){
    if(tr[id].l == tr[id].r)    return;
    if(tr[id].lazy){
        tr[lid].lazy += tr[id].lazy;
        tr[lid].mn += tr[id].lazy;
        tr[rid].lazy += tr[id].lazy;
        tr[rid].mn += tr[id].lazy;
        tr[id].lazy = 0;
    }
}
void build(int id, int l, int r){
    tr[id].l = l, tr[id].r = r;
    tr[id].lazy = 0, tr[id].mn = INF;
    if(tr[id].l == tr[id].r)    return;
    build(lid, l, mid);
    build(rid, mid+1, r);
    pushup(id);
}
void add(int id, int l, int r, LL val){
    if(l > r)   return;
    pushdown(id);
    if(tr[id].l == l && tr[id].r == r){
        tr[id].lazy += val;
        tr[id].mn += val;
        return;
    }
    if(r <= mid)    add(lid, l, r, val);
    else if(l > mid)    add(rid, l, r, val);
    else    add(lid, l, mid, val), add(rid, mid+1, r, val);
    pushup(id);
}
LL query(int id, int pos){
    pushdown(id);
    if(tr[id].l == tr[id].r)    return tr[id].mn;
    if(pos <= mid)  return query(lid, pos);
    else    return query(rid, pos);
}

int n, a[N], m, b[N];
LL p[N];

int main(){
    read(n);
    for(int i = 1; i <= n; i++) read(a[i]);
    for(int i = 1; i <= n; i++) read(p[i]);
    read(m);
    for(int i = 1; i <= m; i++) read(b[i]);
    build(1, 0, m);
    add(1, 0, 0, -INF);
    b[m+1] = 1e6;
    for(int i = 1; i <= n; i++){
        int pos = lower_bound(b+1, b+m+1, a[i]) - b;
        int posl = pos - 1;
        if(a[i] == b[pos]){
            LL now = query(1, pos), x = query(1, pos-1);
            add(1, pos, pos, min(now + min(0ll, p[i]), x) - now);
            pos++;
        }
        if(pos <= m)    add(1, pos, m, min(0ll, p[i]));
        if(posl >= 0)   add(1, 0, posl, p[i]);
    }
    LL res = query(1, m);
    if(res >= 1e16)    puts("NO");
    else    puts("YES"), printf("%lld\n", res);
    return 0;
}

Educational Codeforces Round 85

http://xyfjason.github.io/blog-xcpc/2020/04/11/Educational-Codeforces-Round-85/

作者

xyfJASON

发布于

2020-04-11

更新于

2020-12-20

许可协议

#

评论

关注我

分类

最新文章

标签

AtCoder2
CCPC2
Codeforces57
EOJ1
GMCPC1
HDU11
ICPC3
Nowcoder12
POI1
hihoCoder1
学习笔记17
随笔1
×