每日洛谷 10 月水题记录，有哪些你还没解决的难题？
摘要：每日水题记录（洛谷 10 月） 只记录红橙题，因为 (ge) 橙不算很水的题。 (2023.11.9) P1012 [NOIP1998 提高组] 拼数 (75) 分代码 直接把每个数字用字符串输入，然后按字典序排序。 原因：不
每日水题记录（洛谷 10 月）
只记录红橙题，因为 \(\ge\) 橙不算很水的题。
\(2023.11.9\)
P1012 [NOIP1998 提高组] 拼数
\(75\) 分代码
直接把每个数字用字符串输入，然后按字典序排序。
原因：不能直接按字典序排序，寄。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
using ll = long long;
const int kMaxN = 22, kInf = (((1 << 30) - 1) << 1) + 1;
int n;
string s[kMaxN];
int main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++ i) {
cin >> s[i];
}
sort(s + 1, s + n + 1);
for (int i = n; i >= 1; -- i) {
cout << s[i];
}
return 0;
}
\(100\) 分代码
我们直接用自己秘制的全比排序（注：这是以前写的，语言会有点那啥），每次比较 \(2\) 个数 \(a, b\)，如果 \(a + b > b + a\)，则交换 \(a, b\)。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
using ll = long long;
const int kMaxN = 22, kInf = (((1 << 30) - 1) << 1) + 1;
int n;
string s[kMaxN];
bool cmp(string a, string b) {
return a + b > b + a;
}
int main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++ i) {
cin >> s[i];
}
for (int i = 1; i <= n; ++ i) {
for (int j = i + 1; j <= n; ++ j) {
if (cmp(s[i], s[j])) {
swap(s[i], s[j]);
}
}
}
for (int i = n; i >= 1; -- i) {
cout << s[i];
}
return 0;
}
当然，还有 \(O(n \log n)\) 的快速排序。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
using ll = long long;
const int kMaxN = 22, kInf = (((1 << 30) - 1) << 1) + 1;
int n;
string s[kMaxN];
bool cmp(string a, string b) {
return a + b > b + a;
}
int main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++ i) {
cin >> s[i];
}
sort(s + 1, s + n + 1, cmp);
for (int i = 1; i <= n; ++ i) {
cout << s[i];
}
return 0;
}
P1017 [NOIP2000 提高组] 进制转换
前置知识：被除数 \(=\) 商 \(\times\) 除数 \(+\) 余数。
在 C++ 中，会出现这样的问题：
我：\(-10 \bmod -3 = 1\)，C++ 系统：\(-10 \bmod -3 = -1\)。
所以，用短除法。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
using ll = long long;
const int kMaxN = -1, kInf = (((1 << 30) - 1) << 1) + 1;
int n, m;
void S1(int n) {
if (n < 10) {
cout << n;
} else {
cout << char('A' + n - 10);
}
}
void S2(int n, int m) {
if (n == 0) {
return;
}
if (!(n % m) || n > 0) {
S2(n / m, m);
S1(n % m);
} else {
S2(n / m + 1, m);
S1(-m + n % m);
}
}
int main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
// ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
cout << n << "=";
S2(n, m);
cout << "(base" << m << ")\n";
return 0;
}
\(2023.11.10\)
B3647【模板】Floyd
经典模板题。
状态转移方程：\(f_{i, j} = min(f_{i, j}, f_{i, k} + f_{k, j})\)，时间复杂度 \(O(n^3)\)。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
using ll = long long;
const int kMaxN = 110, kInf = (((1 << 30) - 1) << 1) + 1;
int n, m, f[kMaxN][kMaxN];
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
memset(f, 0x3f, sizeof f);
for (int i = 1, u, v, w; i <= m; ++ i) {
cin >> u >> v >> w;
f[u][v] = w;
f[v][u] = w;
}
for (int i = 1; i <= n; ++ i) {
f[i][i] = 0;
}
for (int k = 1; k <= n; ++ k) {
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= n; ++ j) {
(f[i][j] > f[i][k] + f[k][j]) && (f[i][j] = f[i][k] + f[k][j]);
}
}
}
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= n; ++ j) {
cout << f[i][j] << ' ';
}
cout << '\n';
}
return 0;
}
当然，你还可以用 \(O(n \log m)\) 的 dijkstra，\(O(nk)\) 的 SPFA（关于 SPFA，它死了）……
B3648 [语言月赛202208] 你几岁了
输入输出题。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
using ll = long long;
const int kMaxN = -1, kInf = (((1 << 30) - 1) << 1) + 1;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int x;
cin >> x;
cout << "I am " << x << " years old.\n";
return 0;
}
B3649 [语言月赛202208] 大小比较
条件分支题。
这里可以用三目运算符，格式为 条件? 分支 1 : 分支 2。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
using ll = long long;
const int kMaxN = -1, kInf = (((1 << 30) - 1) << 1) + 1;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int a, b;
cin >> a >> b;
cout << (a <= b? "YE5" : "N0") << '\n';
return 0;
}
B3650 [语言月赛202208] 求和
循环题。
定义一个 \(ans\)，每次把 \(ans\) 加 \(i\ (1 \le i \le n)\)，然后输出。
注意，本题轻微卡常。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
using ll = long long;
const int kMaxN = -1, kInf = (((1 << 30) - 1) << 1) + 1;
ll n, ans = 0;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++ i) {
ans += i;
cout << ans << '\n';
}
return 0;
}
\(2023.11.11\)
B3821 [语言月赛 202308] 小粉兔 Failed System Test
摘自我的题解：
problem 1
我们注意到，\(1 \le n \le 10^9\)，而 \(k\) 可能等于 \(n\)，所以 \(k\) 也可能是 \(10^9\)，代码中有 \(k \times 3\) 的运算，而 \(10^9 \times 3 = 3 \times 10^9\)，又 \(3 \times 10^9 > 2^{31} - 1\)，所以只要让 \(k = 10^9\) 即可。
problem 2
我们注意到，这个代码运行完 \(18\) 和 \(19\) 行后，只判断了 c，没有判断 b 存在，所以我们输出只满足 \(2\) 和 \(3\) 条件的字符串即可。（例：aacc）
#include <iostream>
using namespace std;
int main() {
int taskId;
cin >> taskId;
if (taskId == 1) {
cout << "1000000000 999999999" <<endl;
} else if (taskId == 2) {
cout << "aaaccc" << endl;
} else { // 这个 else 不会被执行
cout << "I AK IOI! You AK NOI!" << endl;
}
}
\(2023.10.12\)
无，但是送给大家一个东西。
任何题目，从暴力开始。
\(2023.10.13\)
无。
\(2023.10.14\)
B3632 集合运算 1
只要懂得集合的基本运算即可。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
using ll = long long;
const int kMaxN = 77, kInf = (((1 << 30) - 1) << 1) + 1, kL = 63;
int n, m, a[kMaxN], b[kMaxN];
int main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1, x; i <= n; ++ i) {
cin >> x;
a[x] = 1;
}
cin >> m;
for (int i = 1, x; i <= m; ++ i) {
cin >> x;
b[x] = 1;
}
cout << n << '\n';
for (int i = 0; i <= kL; ++ i) {
if (a[i] && b[i]) {
cout << i << " ";
}
}
cout << '\n';
for (int i = 0; i <= kL; ++ i) {
if (a[i] || b[i]) {
cout << i << " ";
}
}
cout << '\n';
return 0;
}
B3637 最长上升子序列
模板题。
初始 \(f_i = 1\)，当 \(a_j > a_i\) 时 \(f_j = max(f_j, f_i + 1)\)，答案为 \(\max_{i = 1}^{n} f_i\)。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int kMaxN = 5050, kInf = (((1 << 30) - 1) << 1) + 1;
int n, a[kMaxN], f[kMaxN];
int main() {
cin >> n;
for (int i = 1; i <= n; ++ i) {
cin >> a[i];
f[i] = 1;
}
for (int i = 1; i <= n; ++ i) {
for (int j = i + 1; j <= n; ++ j) {
if (a[j] > a[i]) {
f[j] = max(f[j], f[i] + 1);
}
}
}
int ans = 0;
for (int i = 1; i <= n; ++ i) {
ans = max(ans, f[i]);
}
cout << ans << '\n';
return 0;
}
B3636 文字工作
很简单，\(f_0 = f_1 = 0\)，转移方程 \(f_i = min(f_{i - 1} + 1,\ f_{i \div 2} + 1)\)，\(f_{i + 1} = f_i + 1\)。
时间复杂度 \(O(n \div 2)\)。
dp 写法（以前写的）：
#include<bits/stdc++.h>
using namespace std;
#define qwq ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
int n, dp[1000010];
int main()
{
qwq;
cin >> n;
dp[0] = dp[1] = 0;
for (int i = 2; i <= n; i += 2)
{
dp[i] = min(dp[i-1] + 1, dp[i/2] + 1);
dp[i+1] = dp[i] + 1;
}
cout << dp[n];
return 0;
}
循环写法：
时间复杂度 \(O(\log n)\)。
如 \(n \bmod 2 = 0\)，则 \(n\) 除以 \(2\)，否则 \(n\) 减 \(1\)。每次答案 \(+1\)。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
using ll = long long;
const int kMaxN = -1, kInf = (((1 << 30) - 1) << 1) + 1;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
ll n, ans = 0;
for (cin >> n; n != 1; (n % 2 == 0? n >>= 1 : n -= 1), ++ ans);
cout << ans << '\n';
return 0;
}
\(2023.10.15\)
CF1789A Serval and Mocha's Array
我们只需要找到存在一组 \((i, j)\) 使得 \(1 \le i < j \le n\) 且 \(\gcd(a_i, a_j) = 2\) 就为 Yes，因为前面两个需要最大公约数 \(< 2\)，因为如果前两个最大公约数 \(< 2\)，那么长度 \(> 2\) 的前缀的最大公约数永远不会 \(> 2\)。这里就不太细讲了，请自行思考。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
using ll = long long;
const int kMaxN = 110, kInf = (((1 << 30) - 1) << 1) + 1;
int n, a[kMaxN];
bool f = 0;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
for (cin >> t; t; -- t) {
f = 0;
cin >> n;
for (int i = 1; i <= n; ++ i) {
cin >> a[i];
}
for (int i = 1; i <= n; ++ i) {
for (int j = i + 1; j <= n; ++ j) {
if (__gcd(a[i], a[j]) <= 2) {
f = 1;
}
}
}
cout << (f == 1? "Yes" : "No") << '\n';
}
return 0;
}
CF1789B Serval and Inversion Magic
考试时写的，写的什么玩意\oh。自己尝试理解一下吧。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
using ll = long long;
const int kMaxN = 130, kInf = (((1 << 30) - 1) << 1) + 1;
int n, a[kMaxN], sum = 0;
string s;
bool f = 1, ff = 1, fff = 1;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
for (cin >> t; t; -- t) {
f = 1, ff = 1, fff = 1;
cin >> n >> s;
int i = 0, j = n - 1;
for (; i <= j; ++ i, -- j) {
if (s[i] != s[j] && !ff) {
cout << "NO\n";
fff = 0;
break;
}
if (s[i] != s[j]) {
f = 0;
}
if (s[i] == s[j] && !f) {
ff = 0;
}
}
(fff) && (cout << "YES\n");
}
return 0;
}
CF1883B Chemistry
设字符出现个数为奇数的个数为 \(sum\)，当 \(n - k = 1\) 时（只留一个字母）或 \(sum - 1 \le k\) 即为 YES，否则 NO。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
using ll = long long;
const int kMaxN = 130, kInf = (((1 << 30) - 1) << 1) + 1;
int n, a[kMaxN], k, sum = 0;
string s;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
for (cin >> t; t; -- t) {
cin >> n >> k >> s;
memset(a, 0, sizeof a);
for (int i = 0; i < n; ++ i) {
++ a[s[i]];
}
sum = 0;
for (int i = 'a'; i <= 'z'; ++ i) {
sum += a[i] % 2;
}
-- sum;
if (n - k == 1) {
cout << "Yes\n";
} else if (sum <= k) {
cout << "Yes\n";
} else {
cout << "No\n";
}
}
return 0;
}
to be update.