鱼C竞赛团队第11场比赛题解
本帖最后由 zhangjinxuan 于 2023-12-20 10:53 编辑【FCOI #11】（FBC #1） 题解
官方题解：https://fishc.com.cn/forum.php?mod=viewthread&tid=237189&page=1
比赛链接：https://www.luogu.com.cn/contest/143425
这一篇云剪贴板是 FCOI #11(FBC #1) 所有题目的题解，供大家学习参考。
A 互关
提取关键信息，进行梳理，得出一个人想要与 sfqxx1 互关的条件如下：
1. e > a
2. = 1
3. f > c
4. = 0 or =1
根据以上梳理内容，可以轻松写出代码：
#include <bits/stdc++.h>
using namespace std;
int t;
long long e, f, a, c;
string g, b, d;
int main() {
scanf("%d", &t);
cin >> e >> f >> g;
while (t--) {
cin >> a >> b >> c >> d;
if (e >= a && f >= c && b == "YES" && (g == "YES" || d == "NO")) {
cout << "YES" << endl;
} else cout << "NO" << endl;
}
return 0;
}
B1 高斯记号
可以使用小数进行模拟：
#include <bits/stdc++.h>
using namespace std;
int main() {
int p;
double x;
scanf("%d%lf", &p, &x);
if (p - 1) cout << x - floor(x);
else printf("%d\n", (int)floor(x));
return 0;
}
当然也可以使用字符串。
C 只因出现一次的数字
发现数列的顺序与答案无关，所以我们可以对数字分类。
如何快速地对所有的数字分类呢？即把重复的数字放在一起。
可以哈希，不过，我们可以排序，这样的话，相同的元素必定是相邻的，只要忽略掉与相邻元素相同的元素，剩下的输出，就能找到“只因出现一次的数字 ”。
注意考虑 i=1 和 i=n 的情况。
#include <bits/stdc++.h>
using namespace std;
int n, x;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &x);
sort(x + 1, x + n + 1);
x = -114514;
x = -1919810;
for (int i = 1; i <= n; ++i) {
if (x != x && x != x) {
printf("%d ", x);
}
}
return 0;
}
D 枪战
难度稍微提上来了，稍加分析 K_a 就是 a 到 a 后面下一个更大的数字（没有可以记为 n+1）中间数字的个数，唯一关键的就是如何找到每个数下一个更大的数字。
可以使用单调栈来维护，简而言之，从 1 ~ n 依次加入单调栈中，但是如果待加入的元素大于栈顶元素，说明这个栈顶元素下一个更大的数字就是自己，更新栈顶元素的答案，然后踢出他，重复执行直到栈空或不满足条件即可。
由于每一个元素最多进栈一次，出栈一次，所以时间复杂度为 O(n)。
#include <bits/stdc++.h>
using namespace std;
int n, a;
int ans, st, top;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a);
while (a >= a] && top) {
ans] = i;
}
st[++top] = i;
}
while (st) ans] = n + 1;
long long sum = 0;
for (int i = 1; i <= n; ++i) {
sum += ans - i - 1;
}
printf("%lld\n", sum);
return 0;
}
E 可恶的 zhangjinxuan
这并没有我们想象的那样复杂。
因为直接求有相邻的非常不好求，而且还要套容斥，不如先考虑不会产生矛盾的。
如果一组方案不会产生矛盾，那么这个方案一定是这样的：
1 . 第一个团队任意，一共 N 种选择
2 . 第二个团队不能和第一个团队相同，只有 N-1 种选择。
...
i . 第 $i$ 个团队不能和第 i-1 个团队相同，只有 N-1 种选择。
...
M. 第 $M$ 个团队不能和第 M-1 个团队相同，只有 N-1 种选择。
所以不会产生矛盾的方案数就是 (M-1)^(N-1) * N
而所有可能的做题方案就是 M^N 种，所以最终的答案就是 M^N-(M-1)^(N-1) * N。
不想贴代码，C++ 只要注意一下负数取模就可以了。
B2 高斯记号
比较复杂，而且还有小数运算，更没有 spj，考虑 Python。
前面的处理都是模拟，直接贴代码：
def floor(x):
return int(x) if x >= 0 else int(x) - 1
s = input().strip()
rs = str()
pos = 0
kuohao = -1
number = ''
for i in s:
if i == '[' or i == '{':
kuohao = 1
elif i == '}':
rs +=str(float(number)- floor(float(number)))
number = ''
kuohao = -1
elif i == ']':
rs += str(floor(float(number)))
number = ''
kuohao = -1;
elif kuohao == -1:
rs += i
else:
number += i
ans = eval(rs)
if ans == int(ans):
print(int(ans))
else:
print(ans)
你说得对，但是 WA 46pts。
这很正常，因为这个是提取小数产生的误差，我们不应该用 $N - \lfloor N \rfloor$ 来获取小数部分，更好的替代方案是使用字符串：
def floor(x):
return int(x) if x >= 0 else int(x) - 1
s = input().strip()
rs = str()
pos = 0
kuohao = -1
number = ''
for i in s:
if i == '[' or i == '{':
kuohao = 1
elif i == '}':
rs += '0.'+number.split('.')
number = ''
kuohao = -1
elif i == ']':
rs += number.split('.')
number = ''
kuohao = -1;
elif kuohao == -1:
rs += i
else:
number += i
ans = eval(rs)
if ans == int(ans):
print(int(ans))
else:
print(ans)
F 公因数
感觉也没有这么难，也就是推式子：
很简单有没有？
#include <bits/stdc++.h>
using namespace std;
long long phi(long long a) {
long long res = a;
for (long long i = 2; i * i <= a; ++i) {
if (a % i == 0) {
res = res * (i - 1) / i;
while (a % i == 0) {
a /= i;
}
}
}
if (a > 1) res = res * (a - 1) / a;
return res;
}
int main() {
long long a;
scanf("%lld", &a);
long long res = 0;
for (long long i = 1; i * i <= a; ++i) {
if (a % i == 0) {
res += phi(a / i) * i;
if (i * i != a) {
res += phi(i) * (a / i);
}
}
}
printf("%lld\n", res);
return 0;
}
时间复杂度证明：
枚举 N 的因数，\sqrt{N} 时间复杂度。
N 大约有 log N 个因数，对于每一个因数，都需要用 sqrt{N} 的复杂度求解，所以最终时间复杂度为 O(sqrt{N} log N。
在 N 为 2^32 量级可以通过。
题目总结（验题人主观评价）
也是很均匀的，题目质量很高。
题目编号 | 题目难度 | 算法标签 | 个人评价
A | 入门 | 模拟 | 简单阅读题
B1 | 入门 | 字符串 | 简单字符串题
C | 普及- | 排序，哈希 | 简单思维题
D | 普及 | 单调栈 | 简单模板题
E | 普及 | 数学 | 简单计数题
B2 | 普及+ | 字符串 | 中等字符串题
F | 提高- | 数学 | 中等数学题
好了，这就是 FCOI #11 的全部题目的题解，完工，散会！
666 相信我，最后一题真的是蓝{:10_266:} 我去写一下官方题解{:10_256:} sfqxx 发表于 2023-12-1 18:52
相信我，最后一题真的是蓝
从某种意义上来说，确实是蓝，但是甚至比模板还简单，所以综合一下是绿{:10_316:} zhangjinxuan 发表于 2023-12-1 19:40
从某种意义上来说，确实是蓝，但是甚至比模板还简单，所以综合一下是绿
{:5_104:} 推式子我觉得太直接了，能否给一下证明？ sfqxx 发表于 2023-12-1 21:18
推式子我觉得太直接了，能否给一下证明？
？？？这已经是最详细了的啊 厉害！！ zhangjinxuan 发表于 2023-12-1 21:38
？？？这已经是最详细了的啊
我的就是证明一下 荣誉 +20 鱼币 +21 贡献 +15
我朝 Consolas 字体好好看！ 本帖最后由 sfqxx 于 2024-1-5 19:25 编辑
给定三个 01 串 $A,B,C$，长度均为 $3^N$。字符串下标从 $1$ 开始。
其中：
- $A=\texttt{101010101 \ldots 101}$；
- $B=\texttt{010101010 \ldots 010}$；
- $C=\texttt{001001000 \ldots}$；具体来说，第 $I$ 个字符为 $V_3(I) \bmod 2$。**$V_3(I)$ 的定义请见提示。**
记 $\operatorname{mc}(X,Y)$ 为字符串 $X$ 和 $Y$ 中匹配的字符的个数。
试求：
$$\min\{\operatorname{mc}(A,C),\operatorname{mc}(B,C)\}$$
答案对 $10^9+7$ 取模。 论坛支持MarkDown了！ sfqxx 发表于 2024-1-5 19:19
给定三个 01 串 $A,B,C$，长度均为 $3^N$。字符串下标从 $1$ 开始。
其中：
$\LaTeX$ sfqxx 发表于 2024-1-5 19:26
论坛支持MarkDown了！
这 LaTeX 看起来好奇怪 zhangjinxuan 发表于 2024-1-5 19:34
这 LaTeX 看起来好奇怪
这个得加载很久
对了，你是怎么知道这个字体的？我选不出来 sfqxx 发表于 2024-1-5 19:37
这个得加载很久
对了，你是怎么知道这个字体的？我选不出来
zhangjinxuan 发表于 2024-1-5 19:40
你是怎么知道这个字体的？ sfqxx 发表于 2024-1-5 19:41
自从发现这个特性之后。
页:
[1]
2