发表更新ICPC/CCPC / Contests / 其他21 分钟读完 (大约3164个字)

2020牛客暑期多校训练营（第三场）

比赛链接

收获

  • 若排列 $p$ 满足 $p_{p_i}=i$，那么 $p$ 是由序列 $\{1,2,\cdots,n\}$ 选出 $\frac{n}{2}$ 对两两交换得到的
  • 类似于合并两个 vector 的操作时考虑按秩合并

A Clam and Fish

贪心，只要有鱼就一定捕，因为捕蛤蜊最后还是要用来换鱼，不如现在就捕，所以就只需要考虑没有鱼的情况。没有鱼的情况下，遇到蛤蜊就先存起来，遇到没有蛤蜊的池塘，如果有库存的蛤蜊就用，到最后剩下一些蛤蜊，说明这些蛤蜊捕一半就够了，另一半用来诱鱼。

A.cpp >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
#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 = 2000005;

int T, n;
char s[N];

int main(){
	for(read(T); T; T--){
		read(n);
		scanf("%s", s+1);
		int ans = 0, tot = 0;
		for(int i = 1; i <= n; i++){
			if(s[i] >= '2')	ans++;
			else if(s[i] == '1')	tot++;
			else if(tot > 0)	tot--, ans++;
		}
		ans += tot / 2;
		printf("%d\n", ans);
	}
	return 0;
}

B Classical String Problem

根据题设变换，任意时刻这个字符串一定是从某一位置开始循环填 $s_1,s_2,\cdots,s_n$ 的形式，因此只需要记录好 $s_1$ 在当前时刻的位置即可。

B.cpp >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 = 2000005;

int n, q, x;
char s[N], opt[2];

int main(){
	scanf("%s", s+1);
	n = strlen(s+1);
	int pos = 1;
	for(read(q); q; q--){
		scanf("%s%d", opt, &x);
		if(opt[0] == 'M'){
			if(x < 0)	x += n;
			if(x > pos)	pos += n;
			pos -= x;
		}
		else if(opt[0] == 'A'){
			if(x < pos)	x += n;
			putchar(s[x - pos + 1]); puts("");
		}
	}
	return 0;
}

C Operation Love

把凸包的边长搞出来，如果逆时针方向 $9$ 后面是 $8$ 或者顺时针方向 $9$ 后面是 $6$，那么就是右手；否则左手。

值得注意的是，这道题的精度开低点就够了。

P.S. 根本不用求出凸包……但是复制粘贴模板不香吗（大雾

C.cpp >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
90
91
92
93
94
95
96
97
98
99
100
101
#include<bits/stdc++.h>

using namespace std;

const double eps = 1e-4;
const double PI = 4 * atan2(1, 1);
const double INF = 1e16;
inline int sgn(double x){
	if(fabs(x) < eps)	return 0;
	else if(x > 0)	return 1;
	else	return -1;
}
inline int cmp(double x, double y){ return sgn(x-y); }
double rand01(){ return rand() / (double)RAND_MAX; }
double randeps(){ return (rand01() - 0.5) * eps; }

//------------------------------------ Vector & Point ------------------------------------//
struct Vector{
	double x, y;
	Vector() {}
	Vector(double x, double y):x(x), y(y){}
	void read(){ scanf("%lf%lf", &x, &y); }
};
typedef Vector Point;
Vector operator + (Vector A, Vector B){ return Vector(A.x + B.x, A.y + B.y); }
Vector operator - (Vector A, Vector B){ return Vector(A.x - B.x, A.y - B.y); }
Vector operator * (double k, Vector A){ return Vector(k * A.x, k * A.y); }
Vector operator * (Vector A, double k){ return k * A; }
Vector operator / (Vector A, double k){ return Vector(A.x / k, A.y / k); }
bool operator < (const Vector &A, const Vector &B){
	return cmp(A.x, B.x) == 0 ? cmp(A.y, B.y) < 0 : cmp(A.x, B.x) < 0;
}
bool operator > (const Vector &A, const Vector &B){ return B < A; }
bool operator == (const Vector &A, const Vector &B){ return (cmp(A.x, B.x) == 0) && (cmp(A.y, B.y) == 0); }
bool operator != (const Vector &A, const Vector &B){ return !(A == B); }
// dot product
double operator * (Vector A, Vector B){ return A.x * B.x + A.y * B.y; }
// cross product
double operator ^ (Vector A, Vector B){ return A.x * B.y - A.y * B.x; }
double Length(Vector A){ return sqrt(A * A); }
// test if vector(bc) is to the left of (ab)
bool ToTheLeft(Point A, Point B, Point C){ return sgn((B - A) ^ (C - B)) > 0; }
// test if vector B is to the left of vector A
bool ToTheLeft(Vector A, Vector B){ return sgn(A ^ B) > 0; }
//------------------------------------------------------------------------------//

//------------------------------------ Convex Hull ------------------------------------//
void ConvexHull(int n, Point p[], Point sta[], int &staid){
	// there're n points stored in p[], the points on convex hull will be saved in sta[]
	sort(p+1, p+n+1);
	n = unique(p+1, p+n+1) - (p+1);
	staid = 0;
	for(int i = 1; i <= n; i++){
		// points on edge
		// while(staid > 1 && sgn((sta[staid]-sta[staid-1]) ^ (p[i]-sta[staid-1])) < 0) staid--;
		// no points on edge
		while(staid > 1 && sgn((sta[staid]-sta[staid-1]) ^ (p[i]-sta[staid-1])) <= 0) staid--;
		sta[++staid] = p[i];
	}
	int k = staid;
	for(int i = n-1; i >= 1; i--){
		// points on edge
		// while(staid > k && sgn((sta[staid]-sta[staid-1]) ^ (p[i]-sta[staid-1])) < 0) staid--;
		// no points on edge
		while(staid > k && sgn((sta[staid]-sta[staid-1]) ^ (p[i]-sta[staid-1])) <= 0) staid--;
		sta[++staid] = p[i];
	}
	if(n > 1)   staid--;
}

//-------------------------------------------------------------------------------------------//

Point p[50], ch[50];
double len[50], _len[50];

int main(){
	int T; for(scanf("%d", &T); T; T--){
		for(int i = 1; i <= 20; i++)	p[i].read();
		int n = 0;
		ConvexHull(20, p, ch, n);
		ch[0] = ch[6];
		memset(len, 0, sizeof len);
		memset(_len, 0, sizeof _len);
		for(int i = 1; i <= n; i++)	len[i] = Length(ch[i] - ch[i-1]);
		int id = n;
		int pos = 1;
		for(pos = 1; pos <= n; pos++)
			if(cmp(len[pos], 9) == 0)
				break;
		for(int i = 1; i <= n; i++){
			_len[i] = len[pos];
			pos++;
			if(pos > n)	pos = 1;
		}
		bool counter = ToTheLeft(ch[2] - ch[1], ch[3] - ch[2]);
		if(counter && cmp(_len[2], 8) == 0)	puts("right");
		else if(!counter && cmp(_len[2], 6) == 0)	puts("right");
		else	puts("left");
	}
	return 0;
}

D Points Construction Problem

首先，$m>4n$ 或者 $m$ 是奇数无解。其次，$m$ 的下限是将 $n$ 个黑点组成尽可能方正的矩形缺一个角的形式后的匹配数（例如，$n=11$ 就是一个 $3\times4$ 的矩形缺一个角的形式，此时 $m_\min=14$），当 $m$ 小于这个下限时无解。其他情况有解。

考虑有解时如何构造。我们可以从 $m_\min$ 开始，即刚才所说的“尽可能方正的矩形缺角”。每次从里面拆出来一个点丢到很远的地方，那么分情况我们的匹配数会 $+2$ 或 $+4$（一列一列地丢，如果丢某个点后这一列刚好丢完，那么匹配数 $+2$；否则 $+4$；另外只有一列的时候是 $+2$）。一直丢到匹配数 $\geqslant m$ 的时候，如果是等于，那么我们找到了一个解；如果是大于，只可能是大 $2$，所以取一个丢出去的点加到矩形旁边就好。

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

using namespace std;

int T, n, m;

int main(){
	for(scanf("%d", &T); T; T--){
		scanf("%d%d", &n, &m);
		if(m & 1 || m > 4 * n){ puts("No"); continue; }
		int sql = sqrt(n), sqr = sql;
		if(sql * sqr < n)	sqr++;
		if(sql * sqr < n)	sql++;
		int out = 0, now = 2 * (sql + sqr);
		if(now > m){ puts("No"); continue; }
		puts("Yes");

		int extra = n - sql * (sqr - 1);
		for(int i = sqr; i >= 1; i--){
			if(now >= m)	break;
			for(int j = (i == sqr ? extra : sql); j >= 1; j--){
				if(now >= m)	break;
				if(j == 1 && now < m)	out++, now += 2;
				else if(now < m)	out++, now += i == 1 ? 2 : 4;
			}
		}
		int col = (n - out) / sql;
		extra = n - out  - col * sql;
		for(int i = 1; i <= col; i++)
			for(int j = 1; j <= sql; j++)
				printf("%d %d\n", i, j);
		for(int j = 1; j <= extra; j++)
			printf("%d %d\n", col + 1, j);
		if(now > m)	printf("%d %d\n", 0, 1), out--;
		for(int i = 1; i <= out; i++)
			printf("%d %d\n", i * 2 - 1, 100000000);
	}
	return 0;
}

E Two Matchings

这道题需要转换一长串。。。首先 $p_{p_i}=i$ 意味着 $p$ 序列是由序列 $\{1,2,\cdots,n\}$ 选出 $\frac{n}{2}$ 对两两交换得到的，而 $p$ 和 $q$ 是 combinable 的意味着得到 $p$ 和 $q$ 的时候不能选出相同的一对。又 $\left|a_i-a_{p_i}\right|$ 其实是选出来的一对数的差的绝对值，故 $p$ 序列的代价 $\frac{1}{2}\sum\limits_{i=1}^n\left|a_i-a_{p_i}\right|$ 其实就是选出来的所有对的差的绝对值之和。

于是题意转化成了：给定 $a$ 数组，找两种不同的配对方式（所谓不同，要求没有任何一对数同时出现在两个配对方式中），使得两种配对方式的代价和最小。一种配对方式的代价是所有数对的差的绝对值之和。

显然，我们要找的两种配对方式就是代价最小的和次小的两种配对方式。我们可能会怀疑把最小的配对方式代价增大、而次小的配对方式代价减小是否可行，但是这样答案不会更优：因为把更改了最小的配对方式的那些点拿出来，它们在次小配对方式中一定以最小的代价配对的，于是我们只需要把它们在两个配对方式中交换，就回到了最小配对方式。

代价最小的配对方式很简单，即 $\{(a_i,a_{i+1})\mid i=2k+1\}$，考虑差分序列即可证明。问题主要是代价次小的配对方式。

为了不和最小匹配方式有相同的数对，当 $n=4$ 时，我们只有一种配对方式（其实是两种，但是本质相同），同样的，当 $n=6$ 时，我们也只有一种配对方式；而当 $n\geqslant8$ 时，我们就可以从 $n-4$ 和 $n-6$ 分两种方式转移了，所以这就是一个 $\text{dp}$。$\text{dp}$ 求出次小配对方式后，两代价相加即是答案。

E.cpp >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
#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 = 200005;
const LL INF = 1e16;

int T, n;
LL a[N];

int main(){
	for(read(T); T; T--){
		read(n);
		LL ans = 0;
		for(int i = 1; i <= n; i++)	read(a[i]);
		sort(a+1, a+n+1);
		for(int i = 1; i <= n; i += 2)	ans += a[i+1] - a[i];
		if(n == 4){
			ans += a[4] + a[3] - a[2] - a[1];
			printf("%lld\n", ans);
			continue;
		}
		else if(n == 6){
			ans += a[6] + a[5] - a[4] + a[3] - a[2] - a[1];
			printf("%lld\n", ans);
			continue;
		}
		vector<LL> dp(n+5, INF);
		dp[4] = a[4] + a[3] - a[2] - a[1];
		dp[6] = a[6] + a[5] - a[4] + a[3] - a[2] - a[1];
		for(int i = 8; i <= n; i += 2){
			dp[i] = min(dp[i], dp[i-4] + a[i] + a[i-1] - a[i-2] - a[i-3]);
			dp[i] = min(dp[i], dp[i-6] + a[i] + a[i-1] - a[i-2] + a[i-3] - a[i-4] - a[i-5]);
		}
		printf("%lld\n", ans + dp[n]);
	}
	return 0;
}

F Fraction Construction Problem

  • 若 $(a,b)\neq1$，设 $g=\gcd(a,b)$，那么构造 $\frac{\frac{a}{g}+1}{\frac{b}{g}}-\frac{1}{\frac{b}{g}}=\frac{a}{b}$ 即可；
  • 若 $(a,b)=1$ 且 $b$ 只有不多于一种质因子，那么不可能。因为：设 $b=p^k$，那么通分后分母 $df=b=p^k$，但是题设 $d,f<b$，所以不可能；
  • 若 $(a.b)=1$ 且 $b$ 可分解为两个互质的数的乘积，那我们就设 $d$ 和 $f$ 是这两个互质的因子，即 $df=b$。于是通分后分子有：$cf-de=a$，已知 $d,f,a$，解 $c,e$，扩欧即可。
F.cpp >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
#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 = 2000005;

bool notP[N];
int pList[N], pID;
void Euler(int n){
	notP[0] = notP[1] = 1;
	for(int i = 1; i <= n; i++){
		if(!notP[i])	pList[++pID] = i;
		for(int j = 1; j <= pID; j++){
			if(1ll * i * pList[j] > n)	break;
			notP[i * pList[j]] = 1;
			if(i % pList[j] == 0)	break;
		}
	}
}

int gcd(int a, int b){ return b == 0 ? a : gcd(b, a % b); }
int exgcd(int a, int b, LL &x, LL &y){ // solve ax+by=gcd(a,b)
	if(b == 0){
		x = 1, y = 0;
		return a;
	}
	int d = exgcd(b, a % b, x, y);
	LL t = x;
	x = y, y = t - a / b * y;
	return d;
}

int T;
LL a, b;

int main(){
	Euler(2000000);
	for(read(T); T; T--){
		read(a, b);
		LL g = gcd(a, b);
		if(g != 1){
			printf("%lld %lld %lld %lld\n", a / g + 1, b / g, 1ll, b / g);
			continue;
		}
		int d = 1, f = 1; LL c = 0, e = 0;
		int cnt = 0;

		for(int i = 1; pList[i] * pList[i] <= b; i++){
			if(b % pList[i] == 0)	cnt++;
			int &w = d == 1 ? d : f;
			while(b % pList[i] == 0){
				b /= pList[i];
				w *= pList[i];
			}
		}
		if(b > 1)	cnt++, f *= b;
		if(cnt <= 1){ puts("-1 -1 -1 -1"); continue; }
		exgcd(f, d, c, e);
		e = -e;
		if(c < 0 || e < 0){
			LL k = max(-c / d, -e / f) + 1;
			while(c + k * d < 0 || e + k * f < 0)	k++;
			c += k * d, e += k * f;
		}
		c *= a, e *= a;
		printf("%lld %d %lld %d\n", c, d, e, f);
	}
	return 0;
}

G Operating on a Graph

对每个点维护一个 vector<int> bd，存储与以该点为代表元素的 group 相邻而不属于这个 group 的点。每次操作就模拟一下，把与 $o$ 点相邻的 group 的所有 vector 合并起来，注意按秩合并避免超时。

G.cpp >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
#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 = 800005;

int T, n, m;

int fa[N];
int findfa(int x){ return x == fa[x] ? x : fa[x] = findfa(fa[x]); }
inline void unionn(int x, int y){ fa[findfa(y)] = findfa(x); }

int main(){
	for(read(T); T; T--){
		read(n, m);
		vector<vi> bd(n+1, vector<int>());
		for(int i = 1; i <= n; i++)	fa[i] = i;
		for(int i = 1; i <= m; i++){
			int u, v; read(u, v); u++, v++;
			bd[u].pb(v), bd[v].pb(u);
		}
		int q; for(read(q); q; q--){
			int o; read(o); o++;
			if(o != findfa(o))	continue;
			vi tmp = bd[o];
			bd[o].clear();
			for(auto p : tmp){
				p = findfa(p);
				if(p == o)	continue;
				unionn(o, p);
				if(bd[p].size() > bd[o].size())	swap(bd[o], bd[p]);
				for(auto &k : bd[p])	bd[o].pb(k);
				bd[p].clear();
			}
		}
		for(int i = 1; i <= n; i++)
			printf("%d ", findfa(i) - 1);
		puts("");
	}
	return 0;
}

L Problem L is the Only Lovely Problem

签到题

L.cpp >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
#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)

char s[20];

int main(){
	scanf("%s", s+1);
	int n = strlen(s+1);
	for(int i = 1; i <= n; i++)
		if(s[i] >= 'A' && s[i] <= 'Z')	s[i] += 'a' - 'A';
	if(s[1] == 'l' && s[2] == 'o' && s[3] == 'v' && s[4] == 'e' && s[5] == 'l' && s[6] == 'y')
		puts("lovely");
	else	puts("ugly");
	return 0;
}

2020牛客暑期多校训练营（第三场）

http://xyfjason.github.io/blog-xcpc/2020/07/18/2020牛客暑期多校训练营（第三场）/

作者

xyfJASON

发布于

2020-07-18

更新于

2021-08-28

许可协议

#

评论

关注我

分类

最新文章

标签

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