CONTENTS
第一场
…做了一道就溜了…雨巨讲完之后其实还是晕乎乎的…
F 对答案一时爽
- 题意：给出两组长度为 n n n含有 A , B , C , D A,B,C,D A,B,C,D的序列，求两者得分的最大值
- 分析：一样的话，最多可以得两分，否则最多一分。由于有四个选项，最小则是 0 0 0分。
for(int i=0;i<n;++i) {
if(a[i]==b[i]) {
++ans;
}
}
cout << ans + n << " " << 0;
B 括号
- 题意：构造一个非空的括号字符串，包含正好 k k k 个不同合法括号对
- 样例：
k = 3 输出: ()()
说明:假设字符串数组下标从 1 开始，则 (1,2), (1,4), (3,4) 共计 3 个合法括号对
当然，"()))" 也是一种合法的构造
k = 4 输出: (())
说明:假设字符串数组下标从 1 开始，则 (1,3), (1,4), (2,3), (2,4) 共计 4 个合法括号对
另外，合法的构造还有"())()"、"()(()(" 等等。。
k = 9 输出: ()))))))))
说明:合法的还可以是：
())())()
((()))
)()()())(
等等等。。有非常多种合法构造，输出任意即可。
- 约定：构造出的长度不超过 1 0 5 10^5 105
- 分析：看第三个样例，我们可以先输出很长很长的 ( 序列，在特定的位置补足 ) 即可，而很自然的就想到先输出一半长度就可以了
int a = k / 50000;
for(int i=1;i<=a;++i) {
cout << "(";
}
int b = k % 50000;
for(int i=50000;i>=1;i--) {
if(i==b) {
cout << "(";
}
cout << ")";
}
A 串
- 题意：长度不超过 n n n，且包含子序列 u s us us 的、只由小写字母构成的字符串有多少个？
- 约定：答案对 1 0 9 + 7 10^9+7 109+7 取模。
- 分析1：排列组合问题
设 f [ i ] f\big[ i \big] f[i] 为长度为 i i i，含 u s us us的串的数量
-
f
[
i
−
1
]
f\big[ i -1\big]
f[i−1] 已经含有us
f [ i ] = 26 f [ i − 1 ] f\big[ i \big] = 26f\big[ i -1\big] f[i]=26f[i−1] - 有
u
u
u但是没有
u
s
us
us
f [ i ] = 2 6 i − 1 − 2 5 i − 1 − f [ i − 1 ] f\big[i\big] = 26^{i-1} - 25^{i-1} - f\big[i-1\big] f[i]=26i−1−25i−1−f[i−1]
于是， f [ i ] = 2 6 i − 1 − 2 5 i − 1 + 25 f [ i − 1 ] f\big[i\big] = 26^{i-1} - 25^{i-1} + 25f\big[i-1\big] f[i]=26i−1−25i−1+25f[i−1]
- 分析2：dp
设 f [ i ] [ t ] f\big[ i \big]\big[t\big] f[i][t] 为长度为 i i i串的数量
其中，t可取0,1,2，分别表示：无u，有u无s，有us的状态
f[1][0] = 25;
f[1][1] = 1;
f[1][2] = 0;
for (int i = 2; i <= n; ++i ) {
f[i][0] = (f[i-1][0] * 25) % p;;
f[i][1] = (f[i-1][1] * 25 + f[i-1][0]) % p ;
f[i][2] = (f[i-1][1] + f[i-1][2] * 26) % p ;
ans = (ans + f[i][2])%p;
}
cout << ans;
(
a
+
b
)
%
p
=
(
a
%
p
+
b
%
p
)
%
p
(a+b)\%p = (a\%p+b\%p)\%p
(a+b)%p=(a%p+b%p)%p
(
a
∗
b
)
%
p
=
(
a
%
p
∗
b
%
p
)
%
p
(a\ *b)\%p = (a\%p\ *b\%p)\%p
(a ∗b)%p=(a%p ∗b%p)%p
I 限制不互素对的排列
题意：请构造一个长度为
n
n
n的排列，使得其中正好有
k
k
k对相邻的数
g
c
d
gcd
gcd大于
1
1
1 。
约定：
0
<
k
≤
n
/
2
0<k≤n/2
0<k≤n/2
分析：
- 大于2的相邻数字互素
- 相邻两个奇数也互素
-
k
≤
n
/
2
−
1
k≤n/2-1
k≤n/2−1 可以将
k
k
k组偶数放一起(从小到大)，接着放相邻的奇数、偶数…以没有用到的数字收尾
例如： n = 25 , k = 5 n = 25,k = 5 n=25,k=5
2 4 6 8 10 12 ⏟ 13 14 15 16 17 … 25 ⏟ 1 3 5 7 9 11 ⏟ k + 1 个 偶 数 到 n 的 数 字 剩 下 的 \underbrace{2\ 4\ 6\ 8\ 10\ 12}\ \underbrace{13\ 14\ 15\ 16\ 17\ \dots\ 25}\ \underbrace{1\ 3\ 5\ 7\ 9\ 11}\\ \ \ k+1个偶数 \ \ \ \ \ \ \ \ 到n的数字\ \ \ \ \ \ \ \ \ \ \ \ 剩下的 2 4 6 8 10 12 13 14 15 16 17 … 25 1 3 5 7 9 11 k+1个偶数 到n的数字 剩下的
2. k = n / 2 k = n/2 k=n/2 此时偶数不够用，需要使得第一分界线处的两者不互素，选择 3 , 6 3,6 3,6即可
注意 n < 6 n<6 n<6且 k = n / 2 k=n/2 k=n/2无解，因为找不到 6 6 6
#define space ' '
if (n < 6 and k == n / 2) {
cout << -1;
return 0;
}
if (k < n/2) {
int i = 2;
for (int j = 1; j <= k+1 and i <= n; ++j,i+=2)
cout << i << space;
i -= 2;
for (int j = i + 1; j <= n; ++j)
cout << j << space;
for (int j = 1; j <= i; j+=2)
cout << j << space;
} else {
int i = 8;
for (int j = 1; j <= k-2 and i <= n; j++, i+= 2)
cout << i <<space;
cout << 2 <<space<< 4 << space << 6 << space;
cout << 3 <<space<< 1 << space ;
for (int i = 5; i <= n; i+= 2)
cout << i <<space;
}
H 幂塔个位数的计算
题意：称
a
↑
↑
n
a\uparrow\uparrow n
a↑↑n为以
a
a
a为底的
n
n
n层幂塔，计算方式如下：
a
↑
↑
i
=
{
a
a
↑
↑
(
i
−
1
)
i
>
1
a
i
=
1
a\uparrow\uparrow i= \begin{cases} a^{a\uparrow\uparrow (i-1)} &i>1\\ a &i=1 \end{cases}
a↑↑i={aa↑↑(i−1)ai>1i=1 ，求
a
↑
↑
n
的
个
位
数
a\uparrow\uparrow n的个位数
a↑↑n的个位数