Personal solution.
入门算法套思维场
A. 打牌
题意
对于一张牌，有对应的权值和点数。
对于牌上的字符，按照 A,K,Q,J,10,9,8,7,6,5,4,3,2 的顺序，权值依次减小。
对于牌上的字符，若字符为 2 ~ 9，则点数为字符对应的数字；否则，有下面的对应关系：
A: 1, T: 10, J: 11, Q: 12, K: 13
现在给定 A, B 之间的博弈：
每个人有两张牌，牌上会有两个字符，我们无视第二个字符；
双方都可以看到对方的牌，从而采取最优策略；
第一局
A先手。当 先手 所出的牌的权值 \(\geq\) 后手 所出的牌的权值，先手 获得权值最大的牌对应的点数，否则 后手 获得权值最大的牌对应的点数。上一局获得点数的玩家在第二局为先手，规则和上一局一致。
现在，若两个人都使用最优策略，输出 A 获得的点数 \(-\) B 获得的点数 的最大值。
思路
为方便计算，我们记 B 获得的都是负点数。
首先，因为只有两轮，我们可以发现，第一局的选择总共有四种。
即，如果我们将其标一个号，A 的牌为 1, 2，B 的牌为 3, 4，那么第一局可以是 1:3, 1:4, 2:3, 2:4。
我们可以枚举 A 出的牌，然后找出 B 可以出的牌中，最后答案最小的（即对于 B 来说获得点数最大的），最后对 A 出的所有牌对应的答案取最大的即可。
至于打牌得到的点数，直接模拟即可，注意对 A 的处理。
时间复杂度：\(O(1)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
string s = "0A23456789TJQK";
map<char, int> ind;
for(int i=1;i<=13;i++) ind[s[i]] = i;
auto duel = [&](int a, int b) -> int{
if(a == b) return a;
if(a == 1) return 1;
if(b == 1) return -1;
if(a >= b) return a;
return -b;
};
auto check = [&](int a, int b, int c, int d) -> int{
int ans = duel(a, b);
if(ans >= 0) ans += duel(c, d);
else ans -= duel(d, c);
return ans;
};
int q;
cin >> q;
while(q --) {
string s1, s2, s3, s4;
cin >> s1 >> s2 >> s3 >> s4;
int a1 = check(ind[s1[0]], ind[s3[0]], ind[s2[0]], ind[s4[0]]),
a2 = check(ind[s1[0]], ind[s4[0]], ind[s2[0]], ind[s3[0]]),
a3 = check(ind[s2[0]], ind[s3[0]], ind[s1[0]], ind[s4[0]]),
a4 = check(ind[s2[0]], ind[s4[0]], ind[s1[0]], ind[s3[0]]);
cout << max(min(a1, a2), min(a3, a4)) << '\n';
}
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}《博弈》
B. 括号大师
题意
给定 \(n\) 个由小括号组成的字符串，定义方案为选出若干个字符串，并将其按照任意顺序拼接，满足最后得到的字符串合法。
输出 长度最长的方案 的长度。
思路
首先，可以证明的是，最优策略是先让左括号尽可能递增，然后再递减到 \(0\)。
其次，在左括号递增的时候，我们需要判断它是否合法。因而我们尽可能把不合法的放后面。
同样的，在左括号递减的时候，也是一样的。
从而，我们可以按照上面的方式，对字符串进行排序，然后我们可以用背包计算出我们需要的答案。
时间复杂度：\(O(n \log n + nv ^ 2)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
vector<array<int, 3>> a(n);
for(int i=0;i<n;i++) {
string s;
cin >> s;
auto &[min_v, sum_v, siz] = a[i];
siz = s.size();
for(int j=0;j<siz;j++){
if(s[j] == '(') sum_v ++;
else sum_v --;
min_v = min(min_v, sum_v);
}
}
sort(all(a), [&](auto o1, auto o2) -> bool{
auto [min1, sum1, l1] = o1;
auto [min2, sum2, l2] = o2;
if(sum1 >= 0 && sum2 < 0) return true;
if(sum1 < 0 && sum2 >= 0) return false;
if(sum1 >= 0 && sum2 >= 0) return min1 > min2;
return sum1 - min1 > sum2 - min2;
});
vector<int> pre(90010, -1);
pre[0] = 0;
for(int i=0;i<n;i++){
auto [min, sum, len] = a[i];
vector<int> dp(90010, -1);
for(int j=0;j<=90000;j++){
dp[j] = max(dp[j], pre[j]);
if(j + min >= 0 && j + sum >= 0 && j + sum <= 90000 && pre[j] != -1){
dp[j + sum] = max(dp[j + sum], pre[j] + len);
}
}
pre = dp;
}
cout << pre[0] << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}背包一下（
C. Vigenère 密码
题意
给定加密方式，反推解密方式，并解密。
思路
首先，我们可以发现，加密的方式如下：
将密钥重复若干次，直到和需要加密的文本一样长；
从
0开始对字母表编号，并用其替换密钥字符串为一个数字序列 \(p\)；对于第 \(i\) 个需要加密的字符，对应的加密后的字符为将原字符按照字母表的顺序循环右移 \(p_i\) 位
那么，解密就是循环左移咯。
时间复杂度：\(O(n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
string k, enc;
cin >> k >> enc;
transform(all(k), k.begin(), ::tolower);
int ind = 0;
for(auto &e : enc){
int d = k[ind] - 'a';
if(e >= 'A' && e <= 'Z'){
e = ((e - 'A' - d + 26) % 26) + 'A';
}else{
e = ((e - 'a' - d + 26) % 26) + 'a';
}
ind = (ind + 1) % k.size();
}
cout << enc << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}看着吓人罢了
D. 菜数
题意
对于 \(n = a \cdot 10 ^ 0 + a \cdot 10 ^ 1 + a \cdot 10 ^ 2 + \ldots + a \cdot 10 ^ k\)，给定 \(n\)，任取 \(k\)，找出最小的 \(a\)，使式子成立。
思路
式子可以改为：\(n = a \cdot \underbrace{11 \ldots 1}_{k - 1个1}\)。
那么，我们直接枚举 \(k\) 的长度，然后计算答案即可。
时间复杂度：\(O(1)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e6 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
int base = 111111111111;
while(n % base != 0) base /= 10;
cout << n / base << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}验题的时候蠢了一下，写了个模拟版的，改一下可以过更大的数据。
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 1e6 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
for (int len = 1; len <= 12; len++) {
for (int cnt = 1; cnt <= 13 - len; cnt++) {
int now = n, suf = 0, beg = 0;
vector<int> sum = {0};
bool f = false;
for (int j = 1, p10 = 1; j <= len; j++, p10 *= 10) {
now -= sum[j - 1] - sum[beg];
if (now < 0) f = true;
suf += p10 * (now % 10);
if(j >= cnt) beg ++;
sum.pb(sum[j - 1] + now % 10);
now /= 10;
}
if (f) continue;
int cur = 0;
for (int j = 1; j <= cnt; j++) {
cur = cur * 10 + suf;
if (cur == n) {
cout << suf << '\n';
return;
}
}
}
}
cout << n << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}有点愚蠢在的
E. 拯救Ocean
题意
给定两个 \(4\) 位质数 \(x, y\)，不包含前导 \(0\)。
定义一次操作为选定一个位置，并将该位置上的数字修改为任意数字，满足修改完后的整个数字为不包含前导 \(0\) 的 \(4\) 位质数。
输出将 \(x\) 修改为 \(y\) 的最小操作数。
思路
我们直接 \(\mathtt{bfs}\)。
对于判素数，我们可以用线性筛先筛出来，也可以直接在 \(O(\sqrt n)\) 复杂度下暴力判。
时间复杂度：\(O(懒得分析，反正不大)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
bool vis[N], is_pri[N];
int pri[N], cnt;
//线性筛
void linear_prime(int n) {
for (int i = 2; i <= n; ++i) {
if (!vis[i]) pri[cnt++] = i, is_pri[i] = true;
for (int j = 0; j < cnt; ++j) {
if (1ll * i * pri[j] > n) break;
vis[i * pri[j]] = true;
if (i % pri[j] == 0)break;
}
}
}
void solve() {
linear_prime(2e5);
int x, y;
cin >> x >> y;
queue<pii> q;
q.ep(x, 0);
map<int, int> st;
while(!q.empty()){
auto [now, tot] = q.front();
q.pop();
if(st[now]) continue;
st[now] = true;
if(now == y){
cout << tot << '\n';
return;
}
int tmp = now;
for(int i=1,msk=1;i<=4;i++,msk*=10){
for(int j=0;j<=9;j++){
if(i == 4 && j == 0) continue;
int cur = now - (tmp % 10) * msk + j * msk;
if(cur == now || !is_pri[cur]) continue;
q.ep(cur, tot + 1);
}
tmp /= 10;
}
}
cout << -1 << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}当然也可以跑最短路
F. 小菜玩积木
题意
定义在 \(n\) 块积木上的博弈：
先手和后手每次可以拿走 \(2 ^ k, k \geq 0\) 个积木；
将最后一个积木拿走的玩家获胜
输出获胜的玩家。
如果先手胜，输出先手第一次至少要拿多少积木。
思路
首先，如果后手拿了 \(x\) 个，先手可以拿 \(\frac{x}{2}\) 个，这样可以保证拿的合法。
那么如果要让先手最后拿完，在后手第一次拿的时候，积木数量就必须是 \(3\) 的倍数。
那么，只要先手第一次拿掉 \(n \bmod 3\) 就可以了，而且可以发现 \(1, 2\) 都是合法的。
如果 \(n \bmod 3 = 0\)，那么后手就赢了。
时间复杂度：\(O(1)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int _t = 3;
while(_t --) {
string s;
cin >> s;
int sum = 0;
for (auto e : s) sum += e - '0';
if(sum % 3 == 0) cout << "You win!" << '\n';
else cout << "Caicai wins!" << '\n' << sum % 3 << '\n';
}
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}从结论开始证是很好证的（x
G. 新俄罗斯方块
题意
给定 \(m\) 个柱子，第 \(i\) 个柱子的高度为 \(h[i]\)，输出柱子围成一圈排列的方案数，使相邻两个柱子的高度差不超过 \(k\)。
思路
因为 \(m\) 太小了，所以我们直接暴力 \(\mathtt{dfs}\)，进行一个回溯搜索。
注意围成一圈，最后判断答案的时候不要漏判第一个和最后一个。
当然，最后的答案要除 \(m\)，因为可能有一些方案是通过某个方案 "旋转后" 得到的。
时间复杂度：\(O(10!)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int m, k;
cin >> m >> k;
vector<int> h(m + 1);
for(int i=1;i<=m;i++) cin >> h[i];
vector<bool> st(m + 1);
int ans = 0;
auto dfs = [&](auto dfs, int start, int pre, int cnt) -> void{
if(cnt == m){
if(abs(start - pre) <= k) ans ++;
return;
}
for(int i=1;i<=m;i++){
if(st[i] || abs(h[i] - pre) > k) continue;
st[i] = true;
dfs(dfs, start, h[i], cnt + 1);
st[i] = false; //回溯
}
};
for(int i=1;i<=m;i++) {
st[i] = true;
dfs(dfs, h[i], h[i], 1);
st[i] = false;
}
cout << ans / m << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}签
H. 小菜学数学
题意
给定一个长为 \(n\) 的数组 \(a\)，输出任意去掉一个元素后，所有元素的最大公约数的最大值。
思路
首先，你可以发现最大公约数具有前缀和的性质。
那么，我们记 \(pre[i]\) 为前 \(i\) 个数的 \(\gcd\)，\(suf[i]\) 为后 \(i\) 个数的 \(\gcd\)。
若第 \(i\) 个数是需要去掉的，那么剩下所有数的 \(\gcd\) 就是 \(\gcd(pre[i - 1], suf[i + 1])\)。
枚举即可。
时间复杂度：\(O(n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
vector<int> a(n + 1), pre(n + 1), suf(n + 2);
for(int i=1;i<=n;i++) {
cin >> a[i];
if(i == 1) pre[i] = a[i];
else pre[i] = __gcd(pre[i - 1], a[i]);
}
for(int i=n;i>=1;i--){
if(i == n) suf[i] = a[i];
else suf[i] = __gcd(suf[i + 1], a[i]);
}
int ans = max(pre[n - 1], suf[2]);
for(int i=2;i<n;i++){
ans = max(ans, __gcd(pre[i - 1], suf[i + 1]));
}
cout << ans << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}前缀和套了个壳
I. Ocean做噩梦
题意
给定 \(n\) 组人，每组人会有一个排列方式，这里用三个数 \(s_i, e_i, d_i\) 表示：
从 \(s_i\) 开始，每隔 \(d_i\) 放一个人，直到 \(e_i\)。
找出唯一的一个位置，该位置的人数为奇数，或输出找不到。
思路
我们记 \(sum[i]\) 为前 \(i\) 个位置的人数前缀和。
如果某一个位置的人数是奇数，那么可以发现，从这一位开始，后面的所有 \(sum[i]\) 都是奇数，而前面的都是偶数。
那么，这里出现了一个分隔点，分割点左边的值为偶数，右边为奇数。
那么，我们考虑二分答案，找出这个分隔点。
至于后面的计算，只要留意边界即可。
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
vector<array<int, 3>> a(n); //s, e, d
for(int i=0;i<n;i++) cin >> a[i][0] >> a[i][1] >> a[i][2];
auto check = [&](int x){
int cnt = 0;
for(auto [s, e, d] : a){
if(x < s) continue;
cnt += (min(e, x) - s) / d + 1;
}
return cnt % 2 == 1;
};
int l = 0, r = 4000000000, mid;
bool ok = false;
while(l < r){
mid = (l + r) >> 1;
if(check(mid)) {
r = mid;
ok = true;
}
else l = mid + 1;
}
if(!ok) {
cout << "Poor QIN Teng:(" << '\n';
return;
}
int ans = 0;
for(auto [s, e, d] : a) {
if (e >= l && l >= s && (l - s) % d == 0) ans++;
}
cout << l << ' ' << ans << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}还有位运算的做法
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Blog - Floating Ocean！
评论