6.28 测试

6.28 测试

混氏新子 蒟蒻
  2023-07-02 17:10:25 2023-07-02 17:10:25 创建   2023-09-24 19:11:58 2023-09-24 19:11:58 更新    1.3k 字  7 分钟  

前情提要

题目链接

成绩表

成绩表

tnnd，第二题题目都解释不清楚。

题解

T1

这道题思路很好想，判断逆序对是奇数还是偶数。没想到正解，用树状数组求逆序对，没满。但是听说如果用 bool 数组可能会满……

正解：显然奇数步走到的情况和偶数步走到的情况的集合是不相交的，因此只要判断一种走的情况是奇还是偶就行，可以找置换环，完成。

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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct Generator{
	std::vector<int> num;
//	bool vis[2500005];
	int cnt[2500005];
	typedef unsigned int ui;
	ui a,b,x;ui getnum()
	{ 
		return x=a*x+b;
	}
	std::vector<int> get_permutation(int n,ui a_,ui b_)
	{
		a=a_;
		b=b_;
		x=0;
		std::vector<int> per;
		for(int i=1;i<=n;i++)
		{
			per.emplace_back(getnum()%n+1);
			cnt[per.back()]++;
		}
		for(int i=1;i<=n;i++)
		{
			cnt[i]+=cnt[i-1];
		}
		for(int i=0;i<n;i++) per[i]=cnt[per[i]]--;
		for(int i=1;i<=n;i++) cnt[i]=0;
		return per;
	}
}gen;
int t;
int n, op, x;
vector<int> a;
unsigned int sta, stb;
ll tot;
bool vis[2500005];
void dfs(int u) {
	vis[u + 1] = 1;
	if (vis[a[u]]) {
		return;
	} else {
		++tot;
		dfs(a[u] - 1);
	}
}
int main() {
	freopen("binary.in", "r", stdin);
	freopen("binary.out", "w", stdout);
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d", &n, &op);
		a.clear();
		if (op) {
			scanf("%u%u", &sta, &stb);
			a = gen.get_permutation(n, sta, stb);
		} else {
			for (int i = 0; i < n; ++i) {
				scanf("%d", &x);
				a.emplace_back(x);
			}
		}
		tot = 0;
		memset(vis, 0, sizeof(vis));
		for (int i = 0; i < n; ++i) {
			if (!vis[i + 1]) dfs(i);
		}
		printf("%s\n", (tot & 1ll) ^ ((3 * n) & 1) ? "Um_nik" : "Petr");
	}
	return 0;
}

T2

#dp #树形dp

题目没说最大匹配， 直接没写。最大匹配就是让两个联通的点匹配成一对的最大对数（一个点只能一次），直接简单树形 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
#define mod 998244353ll
#define N 300010
#define eb emplace_back
using namespace std;
using ll = long long;
vector <int> g[N];
ll f[N][3]; //0 : single  1: parent  2: son
int n, u, v;
ll qp(ll x, ll y) {
	ll ans = 1;
	while (y) {
		if (y & 1) ans = ans * x % mod;
		y >>= 1;
		x = x * x % mod;
	}
	return ans;
}
void dfs(int u, int v) {
	f[u][0] = 1;
	f[u][1] = 1;
	for (auto &i: g[u]) {
		if (i == v) continue;
		dfs(i, u);
		f[u][0] *= (f[i][0] + f[i][2]) % mod;
		f[u][0] %= mod;
		f[u][1] *= (f[i][0] + f[i][2] * 2 % mod) % mod;
		f[u][1] %= mod;
	}
	for (auto &i : g[u]) {
		if (i == v) continue;
		f[u][2] += f[u][1] * qp((f[i][0] + f[i][2] * 2 % mod) % mod, mod - 2) % mod * f[i][1] % mod;
		f[u][2] %= mod;
	}
}
int main() {
	freopen("match.in", "r", stdin);
	freopen("match.out", "w", stdout);
	scanf("%d", &n);
	for (int i = 1; i < n ; ++i) {
		scanf("%d%d", &u, &v);
		g[u].eb(v);
		g[v].eb(u);
	}
	dfs(1, 0);
	printf("%lld", (f[1][0] + f[1][2]) % mod);
	return 0;
}

T3

#质数 #线性筛

一部分用线性筛打表，一部分直接枚举质数个数，然后在等分的位置前后枚举就行。

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
#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;
using ll = long long;
mt19937_64 mt(random_device{}());
int N  = 240000000;
bool vis[240000000 + 1];
ll prime[28638900];
int cnt;
//num : 125494, max : 1662377
ll n;
void init() {
	vis[1] = 1;
	for (int i = 2; i <= N; ++i) {
		if (!vis[i]) {
			prime[++cnt] = i;
		}
		for (int j = 1; j <= cnt && prime[j] * i <= N; ++j) {
			vis[prime[j] * i] = 1;
			if (i % prime[j] == 0) break;
		}
	}
	for (int i = 1; i <= cnt; ++i) prime[i] += prime[i - 1];
}
inline ll qp(__int128 x, ll y, ll p) {
	if (y == 0) return 1;
	x %= p;
	__int128 ans = 1;
	while (y) {
		if (y & 1) ans = ans * x % p;
		y >>= 1;
		x = x * x % p;
	}
	return ans;
}
inline bool pzs(const ll& nn)
{
	if(nn==2)return 1;
	if(nn<2||!(nn&1))return 0;
	if (nn <= N) return !vis[nn];
//	for(int i=1;i <= cnt&&(prime[i] - prime[i - 1])*(prime[i] - prime[i - 1])<=nn;++i)if(!(nn%(prime[i] - prime[i - 1])))
//		return 0;
//	return 1;
	ll zs = nn - 1, v;
	int t = 0;
	while (zs % 2 == 0) zs >>= 1, ++t;
	for (int i = 0; i < 1; ++i) {
		ll bs = mt() % (nn - 2) + 2;
		v = qp(bs, zs, nn);
		if (v == 1) continue;;
		int j;
		for (j = 0; j < t; ++j) {
			if (v == nn - 1) break;
			v = (__int128) v * v % nn;
		}
		if (j == t) return 0;
	}
	return 1;
}
ll js(ll l, ll r) {
	ll sum=0;
	for(ll i=l;i<=r;++i)
	{
		if(pzs(i))sum+=i;
		if(sum>1e11) return (ll)(1e11) + 1;
	}
	return sum;
}
deque <ll> a;
int main() {
	freopen("prime.in", "r", stdin);
	freopen("prime.out", "w", stdout);
	scanf("%lld", &n);
	N = max(min((ll)N, n), 100ll);
//	cerr << N << endl;
	init();
	int l, r = lower_bound(prime, prime + cnt + 1, n) - prime;
	for (int i = r; i <= cnt; ++i) {
		l = lower_bound(prime, prime + cnt + 1, prime[i] - n) - prime;
		if (prime[i] - prime[l] == n) {
			printf("%lld %lld", prime[l + 1] - prime[l], prime[i] - prime[i - 1]);
			return 0;
		}
	}
	if (prime[cnt] - prime[cnt - 1] > n) {
		puts("NIE");
		return 0;
	}
	if (pzs(n)) {
		printf("%lld %lld", n, n);
		return 0;
	}
	for (ll i = 2; i <= n / (prime[cnt] - prime[cnt - 1]); ++i) {
		a.clear();
		for (ll j = n / i, jj = 0; j < n && jj < i; ++j) {
			if (pzs(j)) ++jj, a.eb(j);
		}
		for (ll j = n/i - 1, jj = 0; j && jj < i; --j) {
			if (pzs(j)) ++jj, a.emplace_front(j);
		}
//		cerr << i << endl;
//		for (auto &i : a) cerr << i <<' ';
//		cerr << endl;
		a.emplace_front(0);
		for (int ii = 1; ii < a.size(); ++ii) a[ii] += a[ii - 1];
		int l = 1, r = 1;
		for (r = 1; r < a.size(); ++r) {
			while (l <= r && a[r] - a[l - 1] > n) ++l;
			if (a[r] - a[l - 1] == n) {
				printf("%lld %lld", a[l] - a[l - 1], a[r] - a[r - 1]);
				return 0;
			}
		}
	}
	puts("NIE");
	return 0;
}

后记

需要努力，任重道远。

  • 标题: 6.28 测试
  • 作者: 混氏新子
  • 创建于 : 2023-07-02 17:10:25
  • 更新于 : 2023-09-24 19:11:58
  • 链接: https://blog.huasushis.cn/2023/6.28 测试/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
推荐阅读
6.29 测试 6.29 测试 7.3 测试 7.3 测试 6.27 测试 6.27 测试
推荐阅读
6.29 测试 6.29 测试 7.3 测试 7.3 测试
评论
此页目录
6.28 测试
  1. 前情提要
  2. 题解
    1. T1
    2. T2
    3. T3
  3. 后记