Kyooma's Blog

2023杭电多校08

  • ~5.18K 字

题目来自: 2023“钉耙编程”中国大学生算法设计超级联赛（8）

Solved Rank A B C D E F G H I J
4 / 10 156 / 1200 - - - - O - O O - O
  • Ø 赛后通过
  • O 在比赛中通过
  • ! 尝试了但是失败了
  • - 没有尝试

E - 0 vs 1

DESCRIPTION

有一个 $01$ 字符串，零和一在博弈，每个人只能拿当前字符串的第一个或者最后一个，零只能拿 $0$，一只能拿 $1$，如果有人不能拿数则落败，如果字符串为空则平局。

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
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N=1e5+5;

int a[N];

void work(){
	int n;
	string s;
	cin >> n >> s;
	for(int i = 1; i <= n; i++){
		a[i] = s[i - 1] - '0';
	}
	int lt = 1, rt = n, f = 0;
	int ans = -1;
	while(lt <= rt){
		if(a[lt] != f && a[rt] != f){
			ans = f ^ 1;
			break;
		}
		if(a[lt] != a[rt]){
			if(a[lt] == f){
				lt++;
				f ^= 1;
			}else{
				rt--;
				f ^= 1;
			}
			continue;
		}
		if(lt == rt){
			break;
		}
		// f ... f
		if(a[lt + 1] == f){
			lt++;
			f ^= 1;
			continue;
		}else if(a[rt - 1] == f){
			rt--;
			f ^= 1;
			continue;
		}
		// fg...gf
		if(a[lt + 2] != f){
			rt--;
			f ^= 1;
		}else{
			lt++;
			f ^= 1;
		}
	}
	cout << ans << '\n';
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int _;
	cin >> _;
	while (_--) {
		work();
	}
}

G - Solubility

DESCRIPTION

签到题

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
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N=1e5+5;
int a[N],n,m,k,x;
int find(int k) {
	if (k==a[k]) return k;
	return a[k]=find(a[k]);
}
void work(){
	int n,m,k;
	cin >> n >> m;
	for (int i=1;i<=n;++i) a[i]=i;
	for (int i=1,u,v;i<=m;++i) {
		cin >> u >> v;
		a[find(v)]=find(u);
	}
	bool f=true;
	cin >> k;
	cin >> x;
	k--;
	for (int i=1,y;i<=k;++i) {
		cin >> y;
		if (find(x)!=find(y)) f=false;
	}
	if (f) cout << "YES" << endl;
	else   cout << "NO"  << endl;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int _;
	cin >> _;
	while (_--) {
		work();
	}
}

H - Expectation of Rank

DESCRIPTION

有一个 $n\times n$ 的矩阵，每个元素的值是区间 $[0, p - 1]$ 中等概率的随机的一个值，问这个矩阵所有元素在模 $p$ 意义下的秩的期望值。

SOLUTION

打表或者dp。

令 $T(i)$ 表示秩为 $i$ 的矩阵的个数，$T(i) = \prod \limits_{j = 0}^{i - 1} \frac{(p^n - p^j)^2}{p^i-p^j}$ 。

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
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int p=1e9+7;
const int N=5e3+10;
typedef long long ll;
ll po(ll x,ll y){
	ll b=1;
	while(y){
		if(y&1) b=b*x%p;
		y>>=1;
		x=x*x%p;
	}
	return b;
}
ll c[N];
void work(){
	ll x,y,n,m,k,i,j,ans=0;
	cin>>n>>k;
	c[0]=1;
	for(i=1;i<=n;i++) c[i]=c[i-1]*k%p;
	for(i=1;i<=n;i++){
		x=1;
		y=1;
		for(j=0;j<i;j++){
	 		x=x*(c[n]-c[j]+p)%p*(c[n]-c[j]+p)%p;
	 		y=y*(c[i]-c[j]+p)%p;
		}
//		printf("%lld\n",x);
		ans=(ans+x*i%p*po(y,p-2))%p;
	}
//	printf("%lld\n",ans);
	printf("%lld\n",ans*po(po(k,n*n)%p,p-2)%p);
} 

signed main(){
	ios::sync_with_stdio(false);
//	cin.tie(0);
//	init();
	int _ = 1;
	cin >> _;
	while (_--) {
		work();
	}
}

J - Rikka with Square Numbers

DESCRIPTION

给你两个数 $a, b$，一次操作可以对 $a$ 加上或者减去一个完全平方数，问 $a$ 变换到 $b$ 的最少操作次数。

SOLUTION

打表或者仔细分析可以发现，答案一定小于 $3$。

如果 $|a-b|$ 是个完全平方数，那么答案是 $1$。

如果 $|a-b| = x^2 + y^2$ 或者 $|a-b| = x^2 - y^2$，那么答案是 $2$。这种情况可以 $\sqrt{n}$ 的去枚举答案，对于第一种式子枚举 $x$，对于第二种式子枚举 $|a-b|$ 的因子。

其余答案为 $3$。

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
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N=1e5+5;

void work(){
	int n,m,k,i;
	cin>>n>>m;
	int x = abs(n - m);
	int y = sqrtl(x);
	if(y * y == x){
		cout << "1\n";
		return;
	}
	for(int i = 1; i * i <= x; i++){
		if(x % i == 0){
			int pi = x / i;
			if((i + pi) % 2 == 0){
				cout << "2\n";
				return;
			}
		}
		int py = x - i * i;
		int tmp = sqrtl(py);
		if(tmp * tmp == py){
			cout << "2\n";
			return;
		}
	}
	cout << "3\n";
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
//init();
	int _;
	cin >> _;
	while (_--) {
		work();
	}
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可