Practice.
A. Two Elevators
题意
给定两个电梯，电梯从一层移动到相邻层需要一秒。当前人位于第一层；第一个电梯位于 \(a\) 层；第二个电梯位于 \(b\) 层，但是该电梯会先前往 \(c\) 层。
输出最先到达第一层的电梯的耗时。
思路
第一个电梯耗时 \(a - 1\)，第二个梯子耗时 \(abs(b - c) + c - 1\)。
取最小值即可。
时间复杂度：\(O(1)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pdd pair<double, double>
#define fs first
#define sc second
void solve() {
int a, b , c;
cin >> a >> b >> c;
int p = abs(a - 1), q = abs(c - b) + abs(c - 1);
if(p == q) cout << 3 << '\n';
else if(p > q) cout << 2 << '\n';
else cout << 1 << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}b不一定小于c，要取绝对值
B. Decode String
题意
对于一个字符串，给定如下的加密方式：
遍历所有字符；
对于一个字符，设 \(x_i\) 为从 \(a\) 开始编号的数值；
如果 \(x_i \geq 10\)，将 \(x_i\) 乘上 \(10\)；
将所有 \(x\) 按顺序拼接起来
现在，给定加密后的结果，输出原字符串。
思路
首先，小于 \(10\) 的数不会出现末尾为 \(0\) 的情况，而出现了末尾是 \(0\)，前面两个数就是原字符对应的编号。
所以，我们直接倒序遍历，若找到 \(0\)，跳过 \(0\) 并读取前两个数并转换，若不是 \(0\)，那么将这个数转换。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define pdd pair<double, double>
#define fs first
#define sc second
void solve() {
int n;
cin >> n;
string s;
cin >> s;
string ans;
for(int i = n - 1; i >= 0; i --){
char now = s[i];
if(now == '0'){
ans = (char) ((s[i - 2] - '0') * 10 + (s[i - 1] - '0') - 1 + 'a') + ans, i -= 2;
}else{
ans = (char) (s[i] - '0' - 1 + 'a') + ans;
}
}
cout << ans << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}通俗
C. Jumping on Tiles
题意
给定一个字符串，规定操作为从该位置跳到另一个位置，代价为两个位置对应字符在字母表中位置的差的绝对值。
输出从字符串左端跳到右端的代价和的最小值，以及该代价下能跳过的最多位置（不可以重复跳到同一个位置）。
思路
显然，我们只需按照字典序跳着走即可，那么我们不妨记录每个字母出现的次数以及对应的下标，然后从起点的字母按顺序遍历到终点的字母，边遍历边将所有下标都加入答案中，最后根据答案序列计算代价即可。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;
void solve(){
string s;
cin >> s;
int n = s.size();
vector<vector<int>> a(26);
for(int i=0;i<n;i++) a[s[i] - 'a'].emplace_back(i);
vector<int> ans;
int step = s[0] < s[n - 1] ? 1 : -1;
for(int i=s[0]-'a';i*step<=((int)(s[n-1]-'a'))*step;i += step){
for(auto e : a[i]) ans.emplace_back(e);
}
int sum = 0;
for(int i=1;i<ans.size();i++) sum += abs((int) (s[ans[i]] - s[ans[i - 1]]));
cout << sum << ' ' << ans.size() << '\n';
for(auto e : ans) cout << e + 1 << ' ';
cout << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}跳一跳
D. Friends and the Restaurant
题意
给定 \(n\) 个朋友，每个朋友需要花 \(a_i\) 的时间，个人时间预期为 \(b_i\)，由此给定长度为 \(n\) 的两个序列 \(a, b\)。
定义每次可取出至少两个朋友，只要所有人花费的时长小于等于预期时间的总和，那么这些朋友就可以一起去餐馆吃饭。
输出最多可取出多少对满足条件的朋友，且一个人最多只能在一对朋友里。
思路
首先，我们不难会想到构建一个新的数组 \(c\)，满足 \(c_i = b_i - a_i\)，然后将其排个序。
我们不妨直接两两配对，因为既然三个人能配对，那么将其拆开去和其他的人组合一定贡献更大。
其次，如果我们从大到小遍历，并从最小值开始从小到大寻找能进行配对的数，那么我们可以发现我们跳过的数对后续的遍历都没有任何贡献。
具体来说，当我们从小到大遍历的时候，既然这个数不满足要求，那么因为另一个数是递减的，我们一定找不出答案。
因此，我们直接贪心地降序排序，然后枚举左端点，移动右指针即可。
时间复杂度：\(O(n \log n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;
void solve(){
int n;
cin >> n;
vector<int> a(n);
for(int i=0;i<n;i++) cin >> a[i];
for(int i=0;i<n;i++){
int cur;
cin >> cur;
a[i] = cur - a[i];
}
sort(a.rbegin(), a.rend());
int l = 0, r = n - 1;
int cnt = 0;
while(l < r){
while(l < r && a[l] + a[r] < 0) r --;
if(l < r && a[l] + a[r] >= 0) cnt ++;
else break;
l ++, r --;
}
cout << cnt << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}但是升序排序是不可行的哦
E. Guess the Cycle Size
题意
互动游戏。
对于一个由 \(n\) 个节点连接而成的一个无向环，节点的顺序未知。
定义询问为指定两个点，返回值为联结两个点的两条边随机选一，随机是等概率的。如果给定的两个点中至少有一个点超出范围，那么输出 \(-1\)。
对于 \(1e18\) 级别的 \(n\)，在 \(50\) 次询问内，输出 \(n\) 的值。
思路
这是一道很有趣的题。
首先，这道题没有 \(100\%\) 能通过的算法，但 \(99.999851\%\) 的通过概率可以视为正确。
具体来说，因为随机是等概率的，所以我们可以进行 \(25\) 次询问，每次询问 \(1\ i, i\ 1\)，如果两者的返回值不相等，那么我们就找到了答案。
若我们从 \(2\) 开始逐一递增枚举 \(i\)，那么只要我们得到了 \(-1\)，前一个 \(i\) 就是答案。
这样，我们可以以一个很高的概率 "通过" 此题。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;
int ask(int l, int r){
cout << "? " << l << ' ' << r << endl;
cout.flush();
int x;
cin >> x;
return x;
}
void solve(){
int ans = 0;
for (int i = 2; i <= 26; i++) {
long long x = ask(1, i);
long long y = ask(i, 1);
if (x == -1) {
ans = i - 1;
break;
}
if (x != y) {
ans = x + y;
break;
}
}
cout << '!' << ' ' << ans << '\n';
cout.flush();
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
//cin >> t;
while(t --) solve();
}真的过了吗？真的没过吗？如过
F. Kirei and the Linear Function
题意
给定一个十进制数字构成的字符串 \(s\) 以及一个整数 \(w\)，定义 \(v(l, r)\) 为 \(s_{[l ,r]}\) 转为数字后的值，可以有前导零。
现在给定 \(q\) 个询问，每次询问给定 \(l, r, k\)，找到最小的 \(L_1, L_2\)，满足 \(L_1 \neq L_2, v(L_1, L_1 + w - 1) \times v(l, r) + v(L_2, L_2 + w - 1) \equiv k \pmod 9\)。
思路
首先，有一个结论是：一个数模 \(9\) 的值等于其十进制下所有位数字相加之和模 \(9\) 的值。
并且，因为我们求的是模 \(9\) 意义下的值，那么我们可以将所有 \(v(l, r)\) 都模上 \(9\)。
那么这题就好办了，我们直接求前缀和 \(sum\)，那么 \(v(l, r) = (sum[r] - sum[l - 1]) \bmod 9\)。
我们在询问之前，可以预处理所有 \(v(L, L + w - 1) \bmod 9\) 值对应的 \(L\)，那么对应询问，我们直接暴力枚举 \(v(L_1, L_1 + w - 1) \bmod 9\)，可以发现 \(v(L_2, L_2 + w - 1) \bmod 9\) 是唯一确定的。
那么，我们只要判断 \(v(L_1, L_1 + w - 1) \bmod 9\) 和 \(v(L_2, L_2 + w - 1) \bmod 9\) 是否相等即可，相等取前两个，不相等各自取第一个。
时间复杂度：\(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 = 1e6 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
string s;
cin >> s;
int n = s.size();
s = " " + s;
int w, m;
cin >> w >> m;
vector<int> sum(n + 1);
for(int i=1;i<=n;i++) sum[i] = sum[i - 1] + (s[i] - '0');
vector<vector<int>> ind(9);
for(int i=1;i+w-1<=n;i++){
ind[(sum[i + w - 1] - sum[i - 1]) % 9].pb(i);
}
while(m --){
int l, r, k;
cin >> l >> r >> k;
int v = (sum[r] - sum[l - 1]) % 9;
pii ans = {inf, inf};
for(int i=0;i<9;i++){
int j = ((k - v * i % 9) % 9 + 9) % 9;
if(i == j){
if(ind[i].size() < 2) continue;
if(ans.fs > ind[i][0]) ans = {ind[i][0], ind[i][1]};
}else{
if(ind[i].empty() || ind[j].empty()) continue;
if(ans.fs > ind[i][0]) ans = {ind[i][0], ind[j][0]};
}
}
if(ans.fs == inf) cout << -1 << ' ' << -1 << '\n';
else cout << ans.fs << ' ' << ans.sc << '\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();
}主要是第一个结论
G. Cut Substrings
题意
给定一个字符串 \(s\) 和一个模式串 \(t\)，定义一次操作为选定 \(s\) 中一个与模式串 \(t\) 匹配的子串，并将这个子串所有字符修改为 "."。
输出最小的操作数，使得 \(s\) 中没有可以和模式串 \(t\) 匹配的子串，并输出方案数。
思路
因为数据量较小，我们考虑将所有匹配的点都暴力枚举出来。
那么，我们可以得到若干个 \(s\) 上的区间。
可以发现，如果两个区间相交，那么删除任意一个区间都可以让这两个区间无法匹配。
那么反着来说，两个不相交的区间的操作是独立的。
那么我们考虑动态规划，其中 \(dp[i]\) 为必须要选定 \(i\) 的条件下，让前 \(i\) 个区间的无法匹配的最小操作数，\(val[i]\) 为对应的方案数。
我们考虑枚举 \(i\)，并找出第一个和 \(i\) 不相交的区间 \(j\)，然后枚举和 \(j\) 相交的所有区间 \(k\)（包含 \(j\) 本身）。
可以发现，\(i\) 和 \(j, k\) 不相交，\(j, k\) 相交。那么很显然 \(dp[k] = \min(dp[k], dp[i] + 1)\)。
与此对应地，如果 \(dp[k] > dp[i] + 1\)，那么 \(val[k] = val[i]\)，否则如果 \(dp[k] = dp[i] + 1\)，那么 \(val[k] += val[i]\)。
但是这里存在一个问题，我们不知道最后的状态在哪一个位置。
因而，我们考虑多放入一个区间，区间左端点为 \(n + m\)，即保证不和前面区间相交。那么最后该区间的 \(dp\) 值 \(-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 = 1e6 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
string s, t;
cin >> s >> t;
int n = s.size(), m = t.size();
s = " " + s, t = " " + t;
vector<int> p(1, -inf);
for (int i = 1; i + m - 1 <= n; i ++) {
bool f = true;
for (int j = 1; j <= m; j ++) {
if (s[i + j - 1] != t[j]) {
f = false;
break;
}
}
if (f) p.pb(i);
}
p.pb(n + m);
n = p.size() - 1;
vector<int> dp(n + 1, inf), val(n + 1);
dp[0] = 0;
val[0] = 1;
for (int i = 0; i < n; i ++) {
int j = i + 1;
while (j <= n && p[j] <= p[i] + m - 1) j ++;
for (int k = j; k <= n && p[k] <= p[j] + m - 1; k ++) {
if (dp[i] + 1 < dp[k]) {
dp[k] = (dp[i] + 1) % mod;
val[k] = val[i];
} else if (dp[i] + 1 == dp[k]) {
val[k] = (val[k] + val[i]) % mod;
}
}
}
cout << dp[n] - 1 << ' ' << val[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();
}神奇的 \(dp\)