题目目录
- A 小红的合数寻找
- 解题思路
- 参考代码
- B 小红的小球染色
- 解题思路
- 参考代码
- C 小红的二叉树
- 解题思路
- 参考代码
- D 小红的“质数”寻找
- 解题思路
- 参考代码
- E 小红的好排列
- 解题思路
- 参考代码
- F 小红的小球染色期望
- 解题思路
- 参考代码
A 小红的合数寻找
\hspace{15pt} 小红拿到了一个正整数 x x x，她希望你在 [ x , 2 × x ] [x, 2 \times x] [x,2×x] 区间内找到一个合数，你能帮帮她吗？
\hspace{15pt} 一个数为合数，当且仅当这个数是大于 1 1 1 的整数，并且不是质数。
解题思路
因为范围比较小，所以可以暴力枚举答案。
但其实会发现除了2以外的任何偶数都是合数，所以只要
2
×
x
2 \times x
2×x 不是偶数
2
2
2 也就是
x
x
x 不为
1
1
1 的情况下任何的
x
x
x 都有答案
2
×
x
2 \times x
2×x。
参考代码
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 2e5 + 10;
void solve(){
int x;
cin >> x;
if(x != 1){
cout << 2 * x << "\n";
return;
}
cout << "-1\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while(t --){
solve();
}
}
B 小红的小球染色
\hspace{15pt} 有 n n n 个白色小球排成一排。小红每次将随机选择两个相邻的白色小球，将它们染成红色。小红将持续这个操作直到无法操作，请你计算小红操作次数可能的最小值和最大值。
解题思路
首先最大值很显然是 n / 2 n / 2 n/2 个，最小值贪心的去取的话会发现肯定是隔一个染色两个这种，也就耗费三个小球操作一次，但是需要注意如果最后还剩下两个白色小球的话也可以染色，所以最小值其实就是 ( n + 1 ) / 3 (n + 1) / 3 (n+1)/3个。
如下图：7、8小球要被染色成红色。
参考代码
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 2e5 + 10;
void solve(){
int n;
cin >> n;
cout << (n + 1) / 3 << " " << n / 2 << "\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while(t --){
solve();
}
}
C 小红的二叉树
\hspace{15pt}
小红想知道，深度为
n
n
n 的满二叉树
[1]
^{\texttt{[1]}}
[1]有多少条长度为
2
2
2 的简单路径
[2]
^{\texttt{[2]}}
[2]？由于答案可能很大，请将答案对
(
1
0
9
+
7
)
(10^9+7)
(109+7) 取模后输出。
\hspace{15pt}
在本题中，两条简单路径所包含的点集不同时，被视为不同的。例如，路径
u
−
v
u-v
u−v 与路径
v
−
u
v-u
v−u 被视为相同的，因为它们均包含点
u
u
u 与点
v
v
v。
\hspace{15pt}
一棵深度为
h
h
h 的满二叉树
[1]
^{\texttt{[1]}}
[1]由恰好
2
h
−
1
2^h-1
2h−1 个节点组成，每一个节点要么是叶子节点，要么有
2
2
2 个儿子，并且全部叶子节点的深度均为
h
h
h。
\hspace{15pt}
简单路径
[2]
^{\texttt{[2]}}
[2]是指这样一条路径，其经过的顶点和边互不相同。
解题思路
首先稍微观察一下这棵树能发现每个鸡爪（蓝色部分）都是都是一条简单路径，而且每层的鸡爪数量从上往下每层是上一层的
2
2
2 倍。这里
n
n
n 大于等于
2
2
2 才会计算这部分的简单路径。
其次，红、蓝、紫、绿圈的每个部分也都是一条简单路径，并且从上往下也是每层是上一层的
2
2
2倍。这里
n
n
n 大于
2
2
2 才会计算这部分的简单路径。
参考代码
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
i64 qm(i64 x,i64 y){
i64 res = 1;
while(y){
if(y & 1){
res = res * x % mod;
}
x = x * x % mod;
y >>= 1;
}
return res;
}
void solve(){
int n;
cin >> n;
int ans = 0;
for(int i = 2;i <= n;i ++){
ans = ans + qm(2,i - 2);
ans %= mod;
}
for(int i = 3;i <= n;i ++){
ans = ans + qm(2,i - 1);
ans %= mod;
}
cout << ans << "\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while(t --){
solve();
}
}
D 小红的“质数”寻找
\hspace{15pt} 小红拿到了一个正整数 x x x，她希望你在 [ x , 2 × x ] [x, 2 \times x] [x,2×x] 区间内找到一个正整数，满足该正整数所有数位之和为一个质数，你能帮帮她吗？
解题思路
首先这题的数据范围 x ( 1 ≦ x ≦ 1 0 100 000 ) x \left(1\leqq x\leqq 10^{100\,000}\right) x(1≦x≦10100000)超大，直接输入不可行，用字符串来输入，这么大的数据就算 O ( N ) O(N) O(N) 都无法得到答案，那么我们思考观察是不是一个特性或者结论类的题。那么好，确实通过观察，我们其实只需要判断第一个字符就可以得出答案，且无论如何都有满足条件的质数。
看代码应该就能理解了。
参考代码
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using ld = long double;
const int N = 2e5 + 10;
void solve(){
string s;
cin >> s;
int x = s[0] - '0';
int ans = -1;
if(x == 1){
ans = 2;
}
if(x == 2){
ans = 3;
}
if(x == 3){
ans = 5;
}
if(x == 4 || x == 5 || x == 6){
ans = 7;
}
if(x == 7 || x == 8 || x == 9){
ans = 11;
}
cout << ans;
for(int i = 1;i < s.size();i ++){
cout << "0";
}
cout << "\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
cin >> t;
while(t --){
solve();
}
}
E 小红的好排列
\hspace{15pt}
小红认为一个偶数长度为
n
n
n 的排列
{
a
1
,
a
2
,
…
,
a
n
}
\{a_1,a_2,\dots,a_n\}
{a1,a2,…,an} 是好排列，当且仅当恰好有一半的
i
i
i 使得
a
i
×
i
a_i \times i
ai×i 是
3
3
3 的倍数。
\hspace{15pt}
小红想知道，全部长度为
n
n
n 的排列中，共有多少个好排列？由于答案可能很大，请将答案对
(
1
0
9
+
7
)
(10^9+7)
(109+7) 取模后输出。
\hspace{15pt} 长度为 n n n 的排列是由 1 ∼ n 1 \sim n 1∼n 这 n n n 个整数、按任意顺序组成的数组，其中每个整数恰好出现一次。例如， { 2 , 3 , 1 , 5 , 4 } \{2,3,1,5,4\} {2,3,1,5,4} 是一个长度为 5 5 5 的排列，而 { 1 , 2 , 2 } \{1,2,2\} {1,2,2} 和 { 1 , 3 , 4 } \{1,3,4\} {1,3,4} 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。
解题思路
排列组合。题目要求恰好有一半的
i
i
i 使得
a
i
×
i
a_i \times i
ai×i 是
3
3
3 的倍数。
首先一个长度为
n
n
n 的排列中有
n
/
3
n / 3
n/3个数是
3
3
3 的倍数，我们暂且记为
a
a
a，其次我们把一半的数也就是
n
/
2
n / 2
n/2 记为
b
b
b 。且
a
a
a 还是排列中下标
i
i
i 为
3
3
3 的倍数的个数。也就是说无论如何都一定最少有
a
a
a 个满足
a
i
∗
i
a_i * i
ai∗i 的数。那么我们只需要考虑
a
a
a 个数选
b
−
a
b - a
b−a 个在下标不是
3
3
3 的倍数的下标中如何排列即可。我们先把
b
−
a
b - a
b−a 记为
c
c
c 。
我们来举个例子：假设
n
n
n 为 6。
然后我们把下标为
3
3
3 的倍数的放一堆，不是倍数的放一堆，然后再考虑
1
1
1 到
n
n
n 的数如何去放。
其中，排列 A n k A_n^k Ank 的公式为：
A n k = n ! ( n − k ) ! A_n^k = \frac{n!}{(n - k)!} Ank=(n−k)!n!
组合 C n k C_n^k Cnk 的公式为：
C n k = ( n k ) = n ! k ! ( n − k ) ! C_n^k = \binom{n}{k} = \frac{n!}{k!(n - k)!} Cnk=(kn)=k!(n−k)!n!
除法转化为乘法逆元。
参考代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
using i64 = long long;
using ld = long double;
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
int fac[N];
void init(int n){
fac[0] = 1;
for(int i = 1;i <= n;i ++){
fac[i] = fac[i - 1] * i % mod;
}
}
int qm(int x,int y){
int res = 1;
while(y){
if(y & 1){
res = res * x % mod;
}
x = x * x % mod;
y >>= 1;
}
return res;
}
int C1(int x,int y){
return fac[x] * qm(fac[x - y],mod - 2) % mod;
}
int C2(int x,int y){
return fac[x] * qm(fac[x - y],mod - 2) % mod * qm(fac[y],mod - 2) % mod;
}
void solve(){
int n;
cin >> n;
init(n);
int a = n / 3;
int b = n / 2;
int c = b - a;
int ans = 1;
ans = C1(n - a,c) * C1(a,a - c) % mod * C1(n - a,n - a) % mod * C2(a,c) % mod;
cout << ans << "\n";
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while(t --){
solve();
}
}
F 小红的小球染色期望
\hspace{15pt} 有 n n n 个白色小球排成一排。小红每次将随机选择两个相邻的白色小球，将它们染成红色。小红将持续这个操作直到无法操作，请你计算小红操作次数的期望。
解题思路
概率期望题。
当
n
n
n 等于
2
2
2 时，期望为：
E
X
=
1
×
(
1
+
0
+
0
)
EX = 1\times(1 + 0 + 0)
EX=1×(1+0+0)
当
n
n
n 等于
3
3
3 时，期望为：
E
X
=
1
2
×
(
1
+
0
+
0
)
+
1
2
×
(
1
+
0
+
0
)
=
1
EX = \frac{1}{2}\times(1 + 0 + 0) + \frac{1}{2}\times(1 + 0 + 0) = 1
EX=21×(1+0+0)+21×(1+0+0)=1
当
n
n
n 等于
4
4
4 时，期望为：
E
X
=
1
3
×
(
1
+
0
+
1
)
+
1
3
×
(
1
+
0
+
0
)
+
1
3
×
(
1
+
1
+
0
)
=
5
/
3
。
EX =\frac{1}{3}\times(1 + 0 + 1) + \frac{1}{3}\times(1 + 0 + 0) + \frac{1}{3}\times(1 + 1 + 0) = 5 / 3。
EX=31×(1+0+1)+31×(1+0+0)+31×(1+1+0)=5/3。
然后我们来看个 n = 6 n = 6 n=6 的推导情况再看上面式子会更清晰。
下面我们来计算每对小球的期望：
红色的一对小球也就是第
1
、
2
1、2
1、2 个小球被选择的概率为
1
5
\frac{1}{5}
51，所以期望为：
f
(
红色
)
=
(
1
+
f
(
0
)
+
f
(
4
)
)
f(红色) = (1 + f(0) + f(4))
f(红色)=(1+f(0)+f(4))
其中
f
(
0
)
f(0)
f(0) 为这对小球左边
0
0
0 个小球的期望，
f
(
4
)
f(4)
f(4) 为这对小球右边
4
4
4 个小球的期望
其他的也是同样的道理。
所以我们可以大概推导到这么期望计算式子：
f
(
n
)
=
1
n
−
1
×
(
1
+
f
(
x
)
+
f
(
y
)
)
f(n) = \frac{1}{n - 1}\times(1 + f(x) + f(y) )
f(n)=n−11×(1+f(x)+f(y))，其中取值区间为
[
1
,
n
)
[1,n)
[1,n) （左闭右开）。
这里的
x
x
x 为 当前这对小球的左边小球有的小球个数，
y
y
y 为 当前这对小球的右边边小球有的小球个数
稍微推导一下就是：
f
(
n
)
=
1
n
−
1
×
(
1
+
f
(
x
)
+
f
(
y
)
)
f(n) = \frac{1}{n - 1}\times(1 + f(x) + f(y) )
f(n)=n−11×(1+f(x)+f(y))
=
∑
i
=
1
n
−
1
1
n
−
1
×
(
1
+
f
(
i
)
+
f
(
n
−
(
i
+
1
)
)
)
\sum_{i=1}^{n - 1} \frac{1}{n - 1}\times(1 + f(i) + f(n - (i + 1)) )
∑i=1n−1n−11×(1+f(i)+f(n−(i+1)))
=
1
n
−
1
×
∑
i
=
1
n
−
1
(
1
+
f
(
i
)
+
f
(
n
−
(
i
+
1
)
)
)
\frac{1}{n - 1}\times\sum_{i=1}^{n - 1}(1 + f(i) + f(n - (i + 1)) )
n−11×∑i=1n−1(1+f(i)+f(n−(i+1)))
=
1
n
−
1
×
∑
i
=
1
n
−
1
1
+
1
n
−
1
×
∑
i
=
1
n
−
1
f
(
i
−
1
)
+
1
n
−
1
×
∑
i
=
1
n
−
1
f
(
n
−
(
i
+
1
)
)
\frac{1}{n - 1}\times\sum_{i=1}^{n - 1}1 +\frac{1}{n - 1}\times\sum_{i=1}^{n - 1}f(i - 1) + \frac{1}{n - 1}\times\sum_{i=1}^{n - 1}f(n -(i + 1))
n−11×∑i=1n−11+n−11×∑i=1n−1f(i−1)+n−11×∑i=1n−1f(n−(i+1))
=
1
n
−
1
×
(
n
−
1
)
+
1
n
−
1
×
∑
i
=
1
n
−
1
f
(
i
−
1
)
+
1
n
−
1
×
∑
i
=
1
n
−
1
f
(
n
−
(
i
+
1
)
)
\frac{1}{n - 1}\times (n -1) +\frac{1}{n - 1}\times\sum_{i=1}^{n - 1}f(i - 1) + \frac{1}{n - 1}\times\sum_{i=1}^{n - 1}f(n -(i + 1))
n−11×(n−1)+n−11×∑i=1n−1f(i−1)+n−11×∑i=1n−1f(n−(i+1))
=
1
+
1
n
−
1
×
∑
i
=
1
n
−
1
f
(
i
−
1
)
+
1
n
−
1
×
∑
i
=
1
n
−
1
f
(
n
−
(
i
+
1
)
)
1+\frac{1}{n - 1}\times\sum_{i=1}^{n - 1}f(i - 1) + \frac{1}{n - 1}\times\sum_{i=1}^{n - 1}f(n -(i + 1))
1+n−11×∑i=1n−1f(i−1)+n−11×∑i=1n−1f(n−(i+1))
此时，令 j = i − 1 j = i - 1 j=i−1，带入得到：
= 1 + 1 n − 1 × ∑ j = 0 n − 2 f ( j ) + 1 n − 1 × ∑ i = 1 n − 1 f ( n − ( i + 1 ) ) 1+\frac{1}{n - 1}\times\sum_{j=0}^{n - 2}f(j) + \frac{1}{n - 1}\times\sum_{i=1}^{n - 1}f(n -(i + 1)) 1+n−11×∑j=0n−2f(j)+n−11×∑i=1n−1f(n−(i+1))
再令 j = n − ( i + 1 ) j = n - (i + 1) j=n−(i+1)，代入得到：
=
1
+
1
n
−
1
×
∑
j
=
0
n
−
2
f
(
j
)
+
1
n
−
1
×
∑
j
=
n
−
2
0
f
(
j
)
1+\frac{1}{n - 1}\times\sum_{j=0}^{n - 2}f(j) + \frac{1}{n - 1}\times\sum_{j=n-2}^{0}f(j)
1+n−11×∑j=0n−2f(j)+n−11×∑j=n−20f(j)
=
1
+
1
n
−
1
×
∑
j
=
0
n
−
2
f
(
j
)
+
1
n
−
1
×
∑
j
=
0
n
−
2
f
(
j
)
1+\frac{1}{n - 1}\times\sum_{j=0}^{n - 2}f(j) + \frac{1}{n - 1}\times\sum_{j=0}^{n-2}f(j)
1+n−11×∑j=0n−2f(j)+n−11×∑j=0n−2f(j)
=
1
+
2
n
−
1
×
∑
j
=
0
n
−
2
f
(
j
)
1+\frac{2}{n - 1}\times\sum_{j=0}^{n - 2}f(j)
1+n−12×∑j=0n−2f(j)
然后我们把
∑
j
=
0
n
−
2
f
(
j
)
\sum_{j=0}^{n - 2}f(j)
∑j=0n−2f(j) 用前缀和计算，即
s
u
m
[
i
]
=
s
u
m
[
i
−
1
]
+
f
[
i
]
sum[i] = sum[i - 1] + f[i]
sum[i]=sum[i−1]+f[i]，所以
n
n
n 个小球的期望就是：
f
(
n
)
=
1
+
2
n
−
1
×
s
u
m
[
i
−
2
]
f(n) = 1+\frac{2}{n - 1}\times sum[i - 2]
f(n)=1+n−12×sum[i−2]
需要稍微注意初始化
f
[
0
]
=
f
[
1
]
=
0
,
f
[
2
]
=
1
，
s
u
m
[
2
]
=
1
f[0] = f[1] = 0,f[2] = 1，sum[2] = 1
f[0]=f[1]=0,f[2]=1，sum[2]=1
最后套公式除法变为乘法逆元就可以了。
参考代码
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using ld = long double;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
i64 qm(i64 x,i64 y){
i64 res = 1;
while(y){
if(y & 1){
res = res * x % mod;
}
x = x * x % mod;
y >>= 1;
}
return res;
}
void solve(){
int n;
cin >> n;
vector<i64> f(n + 1),sum(n + 1);
f[2] = 1,sum[2] = 1;
for(int i = 3;i <= n;i ++){
f[i] = 1 + 2 * qm(i - 1,mod - 2) * sum[i - 2] % mod;
sum[i] = sum[i - 1] + f[i] % mod;
}
cout << f[n] << "\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while(t --){
solve();
}
}
