Streaming#6模拟赛题解

Posted on | In |
Words count in article: 1.8k | Reading time ≈ 9

Streaming#6模拟赛题解

A. 九九归一

题意：给出整数 $n$ 和 $q$ 个小于 $n$ 的正整数。一个正整数 $a$ 在模 $n$ 意义下自乘的最小循环节恰好等于 $\varphi(n)$ 时我们称 $a$ 是”神奇的“，问这 $q​$ 个正整数中哪些数是神奇的。

思路：（这个题是真的难！）

首先我们可以暴力检查对于每一个 $d | \varphi(n)$ 是否有 $a ^ d \bmod n = 1$ ，然后就会获得$80$ 分的好成绩（

然后我们考虑对上述解法进行优化：

考虑到只要一个 $d | \varphi(n)$ 满足 $a ^ d \bmod n = 1$ ，则 $d$ 的所有倍数一样满足这个条件，这样就可以减少判断的次数了

所以考虑枚举 $\varphi(n)$ 的质因数，若有

则显然不成立，这样可以大幅度降低复杂度。

注意：最后还是要判断 $a ^ {\varphi(n)} \bmod n$ 是否为 $1$ 。

代码：

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
#include <bits/stdc++.h>
#define ri register int
#define il inline
#define ll long long
using namespace std;

const int N = 1e7 + 110;
const int MAXN = 110;
const int inf = 0x7fffffff;
const double eps = 1e-8;

il int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while (!isdigit(ch))
	{
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (isdigit(ch))
	{
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}
	return x * f;
}

int n, q;
int phi[N], prime[N], foo[N];
bool vis[N];

il void Get_phi()
{
	phi[1] = 1;
	vis[1] = 1;
	for (ri i = 2; i <= n; i++)
	{
		if (!vis[i])
		{
			prime[++prime[0]] = i;
			phi[i] = i - 1;
		}
		for (ri j = 1; j <= prime[0] && (long long)prime[j] * i <= n; j++)
		{
			vis[i * prime[j]] = 1;
			phi[i * prime[j]] = phi[i] * (prime[j] - 1);
			if (i % prime[j] == 0)
			{
				phi[i * prime[j]] = phi[i] * prime[j];
				break;
			}
		}
	}
}

il ll Kasumi(ll x, ll y)
{
	ll ret = 1;
	while (y)
	{
		if (y & 1)
			ret = (ret * x) % n;
		x = (x * x) % n;
		y >>= 1;
	}
	return ret;
}

int main()
{
#ifndef Wepdekr
	freopen("mulone.in", "r", stdin);
	freopen("mulone.out", "w", stdout);
#endif
	n = read(), q = read();
	Get_phi();
	for (ri i = 1; i <= prime[0] && prime[i] < phi[n]; i++)
		if (phi[n] % prime[i] == 0)
			foo[++foo[0]] = prime[i];
	for (ri i = 1; i <= q; i++)
	{
		int x = read();
		if (x == 0 || x == 1)
		{
			putchar('0');
			continue;
		}
		bool f = 0;
		for (ri j = 1; j <= foo[0]; j++)
			if (Kasumi(x, phi[n] / foo[j]) == 1 || Kasumi(x, phi[n]) != 1)
			{
				putchar('0');
				f = 1;
				break;
			}
		if (!f)
			putchar('1');
	}
	return 0;
}
/*
7 3
5 2 0

*/

B. LCA的统计

题意：给出一棵 $n$ 个结点的有根树，每个结点 $i$ 的权值为 $w _ i$，求

思路：这很显然是一道树形 $\text{DP}$ ，我们设 $f _ i$ 表示以 $i$ 为根节点的子树的答案

设 $sum _ i$ 为以 $i$ 为根节点的子树已遍历过的结点的权值之和，然后有以下转移

统计完答案后要更新 $sum _ u$ 。

最后对于每个 $u$ 要记得统计 $i = j = u$ 的情况。

注意：本题大多数运算在模意义下进行，请注意取模。

代码：

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
#include <bits/stdc++.h>
#define ri register int
#define il inline
#define ll long long
using namespace std;

const int N = 1e6 + 110;
const int MAXN = 110;
const int inf = 0x7fffffff;
const double eps = 1e-8;
const ll mod = 1e9 + 7;

il int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while (!isdigit(ch))
	{
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (isdigit(ch))
	{
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}
	return x * f;
}

int n, cnt;
int head[N];
ll w[N], f[N], foo[N]; 

struct edge
{
	int to, nxt;
};
edge e[N];

il ll pls(ll a, ll b)
{
	return (a + b) >= mod ? a + b - mod : a + b;
}
il ll mul(ll a, ll b)
{
	ll ret = 0;
	while (b)
	{
		if (b & 1)
			ret = pls(ret, a);
		a = pls(a, a);
		b >>= 1;
	}
	return ret;
}

il void add_edge(int u, int v)
{
	e[++cnt] = (edge) {v, head[u]};
	head[u] = cnt;
}
il void Insert(int u, int v)
{
	add_edge(u, v);
	add_edge(v, u);
}

il void DFS(int x, int pre)
{
	f[x] = pls(f[x], mul(w[x], mul(w[x], w[x])));
	foo[x] = pls(foo[x], w[x]);
	for (ri i = head[x]; i; i = e[i].nxt)
	{
		int v = e[i].to;
		if (v == pre)
			continue;
		DFS(v, x);
		f[x] = pls(f[x], f[v]);
		f[x] = pls(f[x], mul(pls(w[x], w[x]), mul(foo[v], foo[x])));
		foo[x] = pls(foo[x], foo[v]);
	}
}

int main()
{
#ifndef Wepdekr
	freopen("lcastat.in", "r", stdin);
	freopen("lcastat.out", "w", stdout);
#endif
	n = read();
	w[1] = read();
	for (ri i = 2; i <= n; i++)
	{
		int fa = read();
		w[i] = read();
		Insert(i, fa);
	}
	DFS(1, 0);
	printf("%lld", f[1]);
	return 0;
}
/*
2 2
1 1

*/

C. 四驱兄弟

题意：给出 $n$ 个人， $m$ 辆赛车，第 $i$ 辆车预计完成比赛的时间为 $a _ i$ ，每辆车对应两个点，可以选择连边或不连边。

若连边则完成比赛的时间为 $a _ i$ ，否则为 $\infty$ 。

问在不形成环的情况下第 $1, 2, …, n$ 名的成绩最小是多少。

思路：很显然是一个最小生成树，但它为什么是正确的……我也不知道。只要把完成比赛的时间看做两点之间所连边的边权，然后做最小生成树就行了。字符串的处理方面哈希和暴力弄都可以。

注意：哈希不能挂。

代码：

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
#include <bits/stdc++.h>
#define ri register int
#define il inline
#define ll long long
#define ull unsigned long long
#define mpair make_pair
using namespace std;

const int N = 1e6 + 110;
const int MAXN = 110;
const int inf = 0x7fffffff;
const double eps = 1e-8;
const ull base = 998244353;
const ull base2 = 19260817;

il int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while (!isdigit(ch))
	{
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (isdigit(ch))
	{
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}
	return x * f;
}

int n, m, tot;
int fa[N];
ull hash[N];
map <pair <ull, ull> , int> mp;

struct foo
{
	int fr, to, dis;
	friend bool operator < (foo a1, foo a2)
	{
		return a1.dis < a2.dis;
	}
};
foo a[N];

il pair <ull, ull> Get_Hash(string str)
{
	int len = str.size();
	ull ret1 = 0, ret2 = 0;
	for (ri i = 0; i < len; i++)
		ret1 = ret1 * base + str[i];
	for (ri i = 0; i < len; i++)
		ret2 = ret2 * base2 + str[i];
	return mpair(ret1, ret2);
}

il int Find(int x)
{
	return x == fa[x] ? x : fa[x] = Find(fa[x]);
}
il void Merge(int x, int y)
{
	int fx = Find(x);
	int fy = Find(y);
	fa[fx] = fy;
}

il void Kruskal()
{
	int cnt = 0;
	for (ri i = 1; i <= m; i++)
	{
		if (cnt == n)
			break;
		int u = a[i].fr, v = a[i].to;
		if (Find(u) != Find(v))
		{
			Merge(u, v);
			cnt++;
			printf("%d\n", a[i].dis);
		}
	}
	for (ri i = cnt + 1; i <= n; i++)
		puts("INF");
}

int main()
{
#ifndef Wepdekr
	freopen("letsandgo.in", "r", stdin);
	freopen("letsandgo.out", "w", stdout);
#endif
	n = read(), m = read();
	for (ri i = 1; i <= m; i++)
	{
		string s[2];
		int w = read();
		cin >> s[0] >> s[1];
		pair <ull, ull> ViXbob = Get_Hash(s[0]), Edgration = Get_Hash(s[1]);
		if (!mp[ViXbob])
			mp[ViXbob] = ++tot;
		if (!mp[Edgration])
			mp[Edgration] = ++tot;
		a[i] = (foo) {mp[ViXbob], mp[Edgration], w};
	}
	for (ri i = 1; i <= 2 * m; i++)
		fa[i] = i;
	sort(a + 1, a + 1 + m);
	Kruskal();
	return 0;
}
/*
3 3
95 GP_1 GP_2
100 GP_1 gp@3
100 gp@3 GP_2

*/

总结

其实很可惜， $\text{B}$ 题因为一个很小的问题错丢了 $10pts$ ，然后 $\text{C}$ 题哈希的时候 $base$ 用 $998244353$ 被卡了（这么大的 $base$ 其实也是我作死），然后丢了 $30pts$ ，于是 $200pts$ 变成了 $160pts$ 。

同机房的 $\text{ViXbob}$ 在很短的时间内就 $\text{AK}$ 了，说明其实也并不是那么难，没做好……果然还是我太菜了吧。然后下次再作死我就自行去世！

0%