鱼C竞赛团队第11场比赛题解

zhangjinxuan

【FCOI #11】（FBC #1） 题解

官方题解：https://fishc.com.cn/forum.php?m ... d=237189&page=1

比赛链接：https://www.luogu.com.cn/contest/143425

这一篇云剪贴板是 FCOI #11(FBC #1) 所有题目的题解，供大家学习参考。

A 互关

提取关键信息，进行梳理，得出一个人想要与 sfqxx1 互关的条件如下：

1. e > a
2. [b ] = 1
3. f > c
4. [d] = 0 or [g]=1

根据以上梳理内容，可以轻松写出代码：

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. int t;
   
5. long long e, f, a, c;
   
6. string g, b, d;
   
7. 
   
8. int main() {
   
9.         scanf("%d", &t);
   
10.         cin >> e >> f >> g;
    
11.         while (t--) {
    
12.                 cin >> a >> b >> c >> d;
    
13.                 if (e >= a && f >= c && b == "YES" && (g == "YES" || d == "NO")) {
    
14.                         cout << "YES" << endl;
    
15.                 } else cout << "NO" << endl;
    
16.         }
    
17.         return 0;
    
18. }

复制代码

B1 高斯记号

可以使用小数进行模拟：

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. int main() {
   
5.         int p;
   
6.         double x;
   
7.         scanf("%d%lf", &p, &x);
   
8.         if (p - 1) cout << x - floor(x);
   
9.         else printf("%d\n", (int)floor(x));
   
10.         return 0;
    
11. }

复制代码

当然也可以使用字符串。

C 只因出现一次的数字

发现数列的顺序与答案无关，所以我们可以对数字分类。

如何快速地对所有的数字分类呢？即把重复的数字放在一起。

可以哈希，不过，我们可以排序，这样的话，相同的元素必定是相邻的，只要忽略掉与相邻元素相同的元素，剩下的输出，就能找到“只因出现一次的数字 ”。

注意考虑 i=1 和 i=n 的情况。

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. int n, x[1000002];
   
5. 
   
6. int main() {
   
7.         scanf("%d", &n);
   
8.         for (int i = 1; i <= n; ++i) scanf("%d", &x[i]);
   
9.         sort(x + 1, x + n + 1);
   
10.         x[0] = -114514;
    
11.         x[n + 1] = -1919810;
    
12.         for (int i = 1; i <= n; ++i) {
    
13.                 if (x[i] != x[i - 1] && x[i] != x[i + 1]) {
    
14.                         printf("%d ", x[i]);
    
15.                 }
    
16.         }
    
17.         return 0;
    
18. }

复制代码

D 枪战

难度稍微提上来了，稍加分析 K_a 就是 a 到 a 后面下一个更大的数字（没有可以记为 n+1）中间数字的个数，唯一关键的就是如何找到每个数下一个更大的数字。

可以使用单调栈来维护，简而言之，从 1 ~ n 依次加入单调栈中，但是如果待加入的元素大于栈顶元素，说明这个栈顶元素下一个更大的数字就是自己，更新栈顶元素的答案，然后踢出他，重复执行直到栈空或不满足条件即可。

由于每一个元素最多进栈一次，出栈一次，所以时间复杂度为 O(n)。

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. int n, a[800002];
   
5. int ans[800002], st[800002], top;
   
6. 
   
7. int main() {
   
8.         scanf("%d", &n);
   
9.         for (int i = 1; i <= n; ++i) {
   
10.                 scanf("%d", &a[i]);
    
11.                 while (a[i] >= a[st[top]] && top) {
    
12.                         ans[st[top--]] = i;
    
13.                 }
    
14.                 st[++top] = i;
    
15.         }
    
16.         while (st[top]) ans[st[top--]] = n + 1;
    
17.         long long sum = 0;
    
18.         for (int i = 1; i <= n; ++i) {
    
19.                 sum += ans[i] - i - 1;
    
20.         }
    
21.         printf("%lld\n", sum);
    
22.         return 0;
    
23. }

复制代码

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。

前面的处理都是模拟，直接贴代码：

1. def floor(x):
   
2.     return int(x) if x >= 0 else int(x) - 1
   
3. s = input().strip()
   
4. rs = str()
   
5. pos = 0
   
6. kuohao = -1
   
7. number = ''
   
8. for i in s:
   
9.     if i == '[' or i == '{':
   
10.         kuohao = 1
    
11.     elif i == '}':
    
12.         rs +=  str(float(number)- floor(float(number)))
    
13.         number = ''
    
14.         kuohao = -1
    
15.     elif i == ']':
    
16.         rs += str(floor(float(number)))
    
17.         number = ''
    
18.         kuohao = -1;
    
19.     elif kuohao == -1:
    
20.         rs += i
    
21.     else:
    
22.         number += i
    
23.         
    
24. ans = eval(rs)
    
25. if ans == int(ans):
    
26.     print(int(ans))
    
27. else:
    
28.     print(ans)

复制代码

你说得对，但是 WA 46pts。

这很正常，因为这个是提取小数产生的误差，我们不应该用 $N - \lfloor N \rfloor$ 来获取小数部分，更好的替代方案是使用字符串：

1. def floor(x):
   
2.     return int(x) if x >= 0 else int(x) - 1
   
3. s = input().strip()
   
4. rs = str()
   
5. pos = 0
   
6. kuohao = -1
   
7. number = ''
   
8. for i in s:
   
9.     if i == '[' or i == '{':
   
10.         kuohao = 1
    
11.     elif i == '}':
    
12.         rs += '0.'+number.split('.')[1]
    
13.         number = ''
    
14.         kuohao = -1
    
15.     elif i == ']':
    
16.         rs += number.split('.')[0]
    
17.         number = ''
    
18.         kuohao = -1;
    
19.     elif kuohao == -1:
    
20.         rs += i
    
21.     else:
    
22.         number += i
    
23.         
    
24. ans = eval(rs)
    
25. if ans == int(ans):
    
26.     print(int(ans))
    
27. else:
    
28.     print(ans)

复制代码

F 公因数

感觉也没有这么难，也就是推式子：


很简单有没有？

1. 
   
2. #include <bits/stdc++.h>
   
3. using namespace std;
   
4.        
   
5. long long phi(long long a) {
   
6.         long long res = a;
   
7.         for (long long i = 2; i * i <= a; ++i) {
   
8.                 if (a % i == 0) {
   
9.                         res = res * (i - 1) / i;
   
10.                         while (a % i == 0) {
    
11.                                 a /= i;
    
12.                         }
    
13.                 }
    
14.         }
    
15.         if (a > 1) res = res * (a - 1) / a;
    
16.         return res;
    
17. }
    
18. 
    
19. 
    
20. int main() {
    
21.         long long a;
    
22.         scanf("%lld", &a);
    
23.         long long res = 0;
    
24.         for (long long i = 1; i * i <= a; ++i) {
    
25.                 if (a % i == 0) {
    
26.                         res += phi(a / i) * i;
    
27.                         if (i * i != a) {
    
28.                                 res += phi(i) * (a / i);
    
29.                         }
    
30.                 }
    
31.         }
    
32.         printf("%lld\n", res);
    
33.         return 0;
    
34. }

复制代码

时间复杂度证明：

枚举 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

sfqxx

相信我，最后一题真的是蓝

sfqxx

我去写一下官方题解

zhangjinxuan

sfqxx 发表于 2023-12-1 18:52
相信我，最后一题真的是蓝

从某种意义上来说，确实是蓝，但是甚至比模板还简单，所以综合一下是绿

sfqxx

zhangjinxuan 发表于 2023-12-1 19:40
从某种意义上来说，确实是蓝，但是甚至比模板还简单，所以综合一下是绿

sfqxx

推式子我觉得太直接了，能否给一下证明？

zhangjinxuan

sfqxx 发表于 2023-12-1 21:18
推式子我觉得太直接了，能否给一下证明？

？？？这已经是最详细了的啊

小甲鱼

厉害！！

sfqxx

zhangjinxuan 发表于 2023-12-1 21:38
？？？这已经是最详细了的啊

我的就是证明一下

zhangjinxuan

1. 荣誉 +20        鱼币 +21        贡献 +15

复制代码

zhangjinxuan

我朝 Consolas 字体好好看！

sfqxx

给定三个 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$ 取模。

sfqxx

论坛支持MarkDown了！

zhangjinxuan

sfqxx 发表于 2024-1-5 19:19
给定三个 01 串 $A,B,C$，长度均为 $3^N$。字符串下标从 $1$ 开始。

其中：

$\LaTeX$

zhangjinxuan

sfqxx 发表于 2024-1-5 19:26
论坛支持MarkDown了！

这 LaTeX 看起来好奇怪

sfqxx

zhangjinxuan 发表于 2024-1-5 19:34
这 LaTeX 看起来好奇怪

这个得加载很久

对了，你是怎么知道这个字体的？我选不出来

zhangjinxuan

sfqxx 发表于 2024-1-5 19:37
这个得加载很久

对了，你是怎么知道这个字体的？我选不出来

1. [font=Consolas][/font]

复制代码

sfqxx

zhangjinxuan 发表于 2024-1-5 19:40

你是怎么知道这个字体的？

zhangjinxuan

sfqxx 发表于 2024-1-5 19:41

自从发现这个特性之后。