FCOI 13 官方题解

zhangjinxuan · 发表于 2024-8-27 22:00:00

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由 zhangjinxuan 于 2024-8-30 12:07 编辑

更好的阅读体验：https://www.luogu.com.cn/paste/vmp3ru1q

FCOI 13 题解

问题 A - 平均

平均数即总和与个数的比，总和显然为 $\frac{N(N+1)}{2}$，比上 $N$ 即 $\frac{N+1}{2}$，乘十后输出答案就是 $5N+5$。

print(int(input())*5+5)

问题 B - 区间公因数

相邻数字的 $\gcd$ 一定为 $1$，因此当 $l\neq r$ 时，一定包含至少一个相邻数字，就是 $1$。当 $l=r$ 时，就直接时为 $l$，记得取模。

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
        int l, r;
        cin >> l >> r;
        if (l != r) cout << 1;
        else cout << r% 998244353;
        return 0;
}

问题 C - 二号线

可以结合 `if-else` 和逻辑或实现。

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
        string s;
        cin >> s;
        if (s == "1" || s == "4" || s == "5" || s == "6" || s == "9" || s == "10" || s == "18" || s == "LP" || s == "JT") puts("DT");
        else if (s == "2" || s == "3") puts("DG");
        else if (s == "YB") puts("QG");
        else puts("ER");
        return 0;
}

彩蛋解析：因为标题为二号线，所以彩蛋和二号线相关，因此考虑故意将二号线认作为其他类别的类型，尝试 $\text {DT, ER,QG}$ 后发现是 $\text{QG}$。

问题 D - 无限水

注意到自动灌水的格子可以无限取水的，所以若能实现无限灌水就代表答案为 $2$，否则就是空格子数量总和，也就是一个一个格子倒水。

而可以实现无限灌水的唯一条件就是存在至少两个空地相邻，即题目中给定的条件。

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n;
char s[2003];

signed main() {
        scanf("%d%s", &n, s + 1);
        int cnt = 0;
        for (int i = 1; i <= n; ++i) {
                if (s[i] == '.') {
                        if (s[i - 1] == '.' && s[i + 1] == '.') return puts("2"), 0;
                        ++cnt;
                }
        }
        cout << cnt;
        return 0;
}

问题 E - AC 时间

找到前驱很简单的方法就是排序，然而这样会影响到整个序列的顺序。为了使得答案以正常的顺序输出，我们可以对于每一个数字再记录一个信息表示他在序列中原来的位置，排序完后直接根据位置信息复原答案即可。

对于 C/C++ 可以使用结构体实现，对于 C++ 可以直接使用 `std::pair`。

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, ans[200005];
pair<int, int> a[200005];

signed main() {
        cin >> n;
        for (int i = 1; i <= n; ++i) {
                cin >> a[i].first;
                a[i].second = i;
        }
        if (n <= 2000) {
                for (int i = 1; i <= n; ++i) {
                        int ans = a[i].first;
                        for (int j = 1; j <= n; ++j) {
                                if (a[i].first > a[j].first) ans = min(ans, a[i].first - a[j].first);
                        }
                        cout << ans << " \n"[i == n];
                }
        } else {
                sort(a + 1, a + n + 1);
                for (int i = 1; i <= n; ++i) {
                        ans[a[i].second] = a[i].first - a[i - 1].first;
                }
                for (int i = 1; i <= n; ++i) cout << ans[i] << " \n"[i == n];
        }
        return 0;
}

问题 F - 真算

Sub1
同时是 $4,6$ 的倍数一定要满足是 $12$ 的倍数，题目的代码却判断的是 $24$ 的倍数，数据 `12` 即可 Hack。

Sub2

注意到 $ab$ 的最大值比 $9.5\times10^{8}$ 大，因此 $ab \times cd$ 可以超过 `long long` 的存储范围，考虑令 $a=b=\lfloor \sqrt{998244353} \rfloor$，这样 $a,b$ 就能在值域较小的时候取到较大的模意义下的乘积。数据 `31595 31595 100000 100000` 即可。
Sub3
如果是随机生成每一次是 $O(\log n)$ 的，考虑这样构造，每一次使用一个大盒子取拼接小盒子，这样每一次遍历一次大盒子，单次会达到 $O(n)$，构造仅需要在第 $i$ 次操作用 $i$ 盒子去拼接 $i+1$ 即可。

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, ans[200005];
pair<int, int> a[200005];

signed main() {
        ios::sync_with_stdio(0);
        cin >> n;
        if (n == 1) cout << 12;
        else if (n == 2) cout << "31595 31595 100000 100000";
        else if (n == 3) {
                cout << 50000 << " " << 49999 << "\n";
                for (int i = 1; i <= 50000; ++i) {
                        cout << i << " \n"[i == 50000];
                }
                for (int i = 1; i <= 49999; ++i) {
                        cout << i << " " << i + 1 << "\n";
                }
        }
        return 0;
}

问题 G - 连除

尝试在 $A_l$ 后面添加小括号，那么答案就是 $\displaystyle \frac{ A_l }{ \prod_{i=l+1}^{r} A_i}$，就转换成了两数模意义下除法和区间连乘的问题。

对于一个序列，我们可以预处理他们的前缀乘积，即对于任意 $S_i$ 都等于 $\displaystyle \prod_{j=1} ^{i} A_i$，这里是需要取模的。

然后查询 $l+1\sim r$ 的连乘就是 $\frac{S_r}{S_{l}}$，这一步同样也是一次模意义下除法。所以一段区间的连除就是 $\frac{A_l}{\frac{S_r}{S_{l}}}$。

模意义下的除法题目已经给出定义，即标准的乘法逆元，求解这个可以使用快速幂实现，即费马小定理求解逆元。

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, q, a[200005], pres[200005];
const int p = 998244353;

long long qpow(long long a, long long b) {
        long long res = 1;
        while (b) {
                if (b & 1) res = res * a % p;
                a = a * a % p;
                b >>= 1;
        }
        return res;
}

signed main() {
        ios::sync_with_stdio(0);
        cin >> n >> q;
        pres[0] = 1;
        for (int i = 1; i <= n; ++i) {
                cin >> a[i];
                pres[i] = (pres[i - 1] * a[i]) % p;
        }
        while (q--) {
                int l, r;
                cin >> l >> r;
                cout << a[l] * qpow(pres[r] * qpow(pres[l], p - 2) % p, p - 2) % p << "\n";
        }
        return 0;
}

问题 H - 数字 LIS

考虑如何使用最少的量来维护一个最长不降子序列，显然需要三种东西给，一个是上一个元素，一个是以本身结尾的答案，一个是全局的答案，因此就能用 $O(N^3)$ 的复杂度表示出整个问题，而不是枚举数字的 $O(10^N)$，这样，只需要把这 $O(N^3)$ 的状态作为 DP 的维度进行 DP 即可。

但是这个算法只有在 $n\le100$ 的时候才能勉强跑一跑，对于 $n\le1000$，几乎不可能优化，所以考虑使用打表的技巧，由于空间过大，所以考虑使用滚动数组优化，即可在本地运行。

打表程序：

#include <bits/stdc++.h>
using namespace std;
#define lim 1000
long long n, f[2][11][lim+2][lim+2];
int main() {
        freopen("ans.cpp", "w", stdout);
        cin >> n;
        for (int i = 0; i < 11; ++i) for (int j = 0; j < lim; ++j) for (int k = 0; k < lim; ++k) f[0][i][j][k] = k;
        cout << "#include <bits/stdc++.h>\nusing namespace std;\n";
        cout << "const int ans[1004] = {-1, ";
        for (int i = 1; i <= n; ++i) {
                for (int lst = 0; lst <= 10; ++lst) 
                for (int now = 0; now <= n + 1; ++now) for (int ans = 0; ans <= n + 1; ++ans) {
                        int sum = 0;
                        for (int j = 0; j <= 9; ++j)
                                if (j >= lst) (sum += f[(i - 1) & 1][j][now + 1][max(ans, now + 1)]) %= 998244353;
                                else (sum += f[(i - 1) & 1][j][1][max(ans, 1)]) %= 998244353;                
                        f[i & 1][lst][now][ans] = sum;
                }
                cout << f[i & 1][10][1][1] << ", " << flush;
                cerr << i << endl;
        }
        cout << "};\n";
        cout << "\nint main() {\n\tint t;\n\tcin >> t;\n\twhile(t--) {int n; cin >> n; cout << ans[n] << "\\n"; }\n\treturn 0;\n}";
        return 0;
}

至少需要 $5\text{min}$，但应该是已知的最优解，如果您发现了时间更低的做法，欢迎告诉我。

sfqxx · 发表于 2024-8-27 23:46:29

求py代码

学习编程中的Ben · 发表于 2024-8-28 08:33:36

打表？？？！！！

学习编程中的Ben · 发表于 2024-8-28 08:50:40

这非常规过分了吧。。。

zhangchenyvn · 发表于 2024-8-28 09:22:01

我有一种最后一道题的想法。。。

zhangchenyvn · 发表于 2024-8-28 09:25:24

如果序列足够大，将输入序列分段，将每一段分配给一个线程，每个线程计算出该段所有可能的最长不降子序列，后将所有返回，由主线程再次将其分配，将每个不降序列进行排序，即可

zhangjinxuan · 发表于 2024-8-28 18:15:25

本帖最后由 zhangjinxuan 于 2024-8-28 18:31 编辑

zhangchenyvn 发表于 2024-8-28 09:25
如果序列足够大，将输入序列分段，将每一段分配给一个线程，每个线程计算出该段所有可能的最长不降子序列， ...

无意义，因为多线程相当于使用超级计算机。

而且总序列量级是 $10^{1000}$ 的。

sfqxx · 发表于 2024-8-28 18:41:24

懂了，非常规=逆天

zhangjinxuan · 发表于 2024-8-28 18:42:16

sfqxx 发表于 2024-8-27 23:46
求py代码

G：

n, q = map(int, input().split())
p = 998244353
a = [0] + list(map(int, input().split()))
pres = [1]
for i in range(1, n + 1):
    pres.append(pres[-1] * a[i] % p)
for i in range(q):
    l, r = map(int, input().split())
    print(a[l] * pow(pres[r] * pow(pres[l], p - 2, p) % p, p - 2, p) % p)

记得用 PyPy3。

H 我觉得转换也不复杂（

zhangjinxuan · 发表于 2024-8-28 18:44:57

sfqxx 发表于 2024-8-28 18:41
懂了，非常规=逆天

来我们重庆育才，虽然不保证一定金牌，但是绝对保证提升你的假算和打表能力（

zhangchenyvn · 发表于 2024-8-28 19:10:14

zhangjinxuan 发表于 2024-8-28 18:15
无意义，因为多线程相当于使用超级计算机。

而且总序列量级是 $10^{1000}$ 的。

有道理

zhangchenyvn · 发表于 2024-8-28 19:13:18

本帖最后由 zhangchenyvn 于 2024-8-28 19:15 编辑

zhangjinxuan 发表于 2024-8-28 18:42
G：

H题py文件我也转了一下

# 定义常量
lim = 1000
n = int(input())
f = [[[[0] * (lim + 2) for _ in range(lim + 2)] for _ in range(11)] for _ in range(2)]

for i in range(11):
    for j in range(lim):
        for k in range(lim):
            f[0][i][j][k] = k

with open("ans.py", "w") as output_file:
    output_file.write("# Converted Python Code\n")
    output_file.write("ans = [-1, ")

    for i in range(1, n + 1):
        for lst in range(11):
            for now in range(n + 2):
                for ans in range(n + 2):
                    sum_value = 0
                    for j in range(10):
                        if j >= lst:
                            sum_value += f[(i - 1) & 1][j][now + 1][max(ans, now + 1)]
                        else:
                            sum_value += f[(i - 1) & 1][j][1][max(ans, 1)]
                        sum_value %= 998244353
                    f[i & 1][lst][now][ans] = sum_value
        
  
        output_file.write(f"{f[i & 1][10][1][1]}, ")
        print(i)  

    output_file.write("]\n\n")
    output_file.write("def main():\n")
    output_file.write("\tt = int(input())\n")
    output_file.write("\twhile t > 0:\n")
    output_file.write("\t\tn = int(input())\n")
    output_file.write("\t\tprint(ans[n])\n")
    output_file.write("\t\tt -= 1\n")
    output_file.write("\nif __name__ == '__main__':\n\tmain()\n")

sfqxx · 发表于 2024-8-28 19:30:35

zhangjinxuan 发表于 2024-8-28 18:42
G：

sfqxx · 发表于 2024-9-6 13:55:07

zhangchenyvn 发表于 2024-8-28 19:13
H题py文件我也转了一下

账号		自动登录	找回密码
密码			立即注册

[技术交流] FCOI 13 官方题解

马上注册，结交更多好友，享用更多功能^_^