|
|
马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
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$。
问题 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}$，但应该是已知的最优解，如果您发现了时间更低的做法，欢迎告诉我。
|
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2024-8-27 22:00:00
置顶卡
千斤顶
显身卡
发表于 2024-8-27 23:46:29
楼主