写在前边
链接：Codeforces Round #704 (Div. 2)
D就不补了，大fst场。
A. Three swimmers
链接：A题链接
题目大意:
给定三个游泳者的到达岸边的周期，(a,b,c)，而你到达岸边的时间为(p)，现在问你到达岸边后最少需要多少时间能遇到一名游泳者。
思路：
老套路题了，公式:
注意，写代码的时候((p + a - 1) / a * a) 与(a * (p + a - 1) / a)获得的结果也不一样，前一种正确。
代码:
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <unordered_map>
using namespace std;
#define Inf 0x3f3f3f3f
#define PII pair<int, int>
#define P2LL pair<long long, long long>
#define endl '
'
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<long long> VLL;
typedef vector<int> VI;
void solve() {
LL p, a, b, c;
cin >> p >> a >> b >> c;
LL a1, b1, c1;
a = (p + a - 1) / a * a;
b = (p + b - 1) / b * b;
c = (p + c - 1) / c * c;
cout << min(a, min(b, c)) - p << endl;
}
int main()
{
//ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
B. Card Deck
链接：B题链接
题目大意:
一副扑克盘，从上往下拿，截止点作为新牌的起点，会形成一种新的顺序，使得这种顺序权值最大，计算权值公式:
思路：
把公式展开后就得出让新的牌须变成字典序最大即可，那么我们就每一次以剩余的最大数作为截止点拿牌，形成新的顺序，一开始就想到这种方法了，但是复杂度想成了(O(n^2))没敢做，于是看题解后，做的也是这种方法，于是想了一下复杂度并不是(O(n^2))，最坏是是(O(n + n))
代码:
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <map>
#include <cstring>
#include <set>
//#pragma GCC optimize(2)
//#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
#define Inf 0x3f3f3f3f
#define PII pair<int, int>
#define P2LL pair<long long, long long>
#define endl '
'
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<long long> VLL;
typedef vector<int> VI;
const int Mod = 10000007;
LL gcd(LL a, LL b) {
return b ? gcd(b, a % b) : a;
}
const int N = 1e5 + 10;
int a[N];
void solve() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
set<int> st;
vector<int> rem;
for (int i = 1; i <= n; i++) st.insert(i);
int maxn = n;
for (int i = n; i >= 1; i--) {
rem.push_back(a[i]);
st.erase(a[i]);
if (a[i] == maxn) {
reverse(rem.begin(), rem.end());
for (auto &it : rem) cout << it << " ";
rem.clear();
if (st.size()) maxn = *(--st.end());
}
}
cout << endl;
}
int main()
{
//ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t;
scanf("%d", &t);
while (t--) {
solve();
}
return 0;
}
C. Maximum width
链接：C题链接
题目大意:
给定一个长度分别为(n，m)的字符串(s，t)，同时可以得到一个序列(p)，(1 leq p_1 leq p_2 leq p_3 leq ... leq n)，使得(s_{p_i} = t_i)对于所有的(s[1, m])，让我们构造以(p)得到一个(maxlimits_{1 leq i leq m} (p_{i + 1} - p_i))。
思路：
每次做这种题都会让坐标烦，这道题仔细抠一下题意就是在(s)中找到一个(t)，并使得(t)在(s)中相邻两个字母的坐标差最大，那么可以分别从前边可后边维护两个数组(f,g)，(f_i)表示(t_i)在s中最左侧位置下标，(g_i)就表示(t_i)在(s)中最右侧位置的下边,那么答案就是(maxlimits_{1 leq i leq {m - 1}} (g_{i + 1} - f_i))
代码:
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <unordered_map>
using namespace std;
#define Inf 0x3f3f3f3f
#define PII pair<int, int>
#define P2LL pair<long long, long long>
#define endl '
'
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<long long> VLL;
typedef vector<int> VI;
const int N = 2e5 + 10;
char s[N], t[N];
int f[N], g[N];
void solve() {
int n, m;
scanf("%d%d", &n, &m);
scanf("%s", s + 1);
scanf("%s", t + 1);
int cnt = 1;
for (int i = 1; i <= m; i++) {
while (s[cnt] != t[i]) cnt++;
f[i] = cnt;
cnt++;
}
cnt = n;
for (int i = m; i >= 1; i--) {
while (s[cnt] != t[i]) cnt--;
g[i] = cnt;
cnt--;
}
int res = 0;
for (int i = 1; i <= m - 1; i++) res = max(res, g[i + 1] - f[i]);
printf("%d
", res);
}
int main()
{
solve();
return 0;
}