比赛链接: https://www.luogu.com.cn/contest/122370#description
A - 排列排序
解题思路
根据题意是要去找区间, 并且n的世界范围较大, 所以考虑用双指针去维护; 根据题意我们可以知道排序的最优解就是找到所有最长的区间两端都不相等的区间, 然后把他们直接排序即可; 因为我们下标从小到大遍历, 所以我们最开始遇到的情况要么f[i]=i, 要么f[i]>i; 如果f[i]=i则i++, 如果f[i]>i, 那目前最长的异常区间就是i~f[i], 然后我们设变量j为i, 让j从i开始遍历去找i~f[i]种可能存在的更大的异常边界, 如果f[j]>f[i], 那么就更新最大值, 继续遍历j, 直到到达最大值后答案就可以加上j-i+1, 更新i=j+1 然后继续找下一个最长的异常区间;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10;
int n, m, p;
int f[N];
void solve() {
cin >> n;
int res = 0;
for (int i = 1; i <= n; i++) cin >> f[i];
int l = 1e9, r = 0;
int ans = 0;
for (int i = 1; i <= n; ) {
if (i == f[i]) i++;
else {
int j = i;
int ans = f[i];
while (j < ans) {
j++;
ans = max(ans, f[j]);
}
res += j - i + 1;
i = j + 1;
}
}
cout << res << endl;
}
signed main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
B - 计算分数
解题思路
一道比较繁琐的模拟, 因为要进行通分和约分, 还要考虑最后不同情况的输出形式; 当时为了保险就用的字符串进行读入, 后来看题解也可以用scanf("%d/%d",&a,&b)的形式来直接获取值, 代码会短很多, 不过本质都是一个不算难的模拟于是就懒得改了;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10;
int n, m, p;
int a, b, u;
string s;
PII res = { 0,0 };
bool f = false;
int fu = 1;
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
void check() {
b = u;
u = 0;
if (res.second == 0) {
int d = gcd(abs(a), b);
res.first = a / d;
res.second = b / d;
}
else {
int c = res.second * b / gcd(res.second, b);
int c1 = c / res.second;;
int c2 = c / b;
res.first *= c1;
a *= c2;
res.first += a;
res.second = c;
int d = gcd(abs(res.first), res.second);
res.first /= d, res.second /= d;
}
}
signed main() {
cin >> s;
for (int i = 0; i <= s.size(); i++) {
if (s[i] >= '0' && s[i] <= '9') {
u = u * 10 + s[i] - '0';
}
else if (s[i] == '+' || s[i] == '-') {
if (s[i] == '+') fu = 1;
else fu = -1;
check();
}
else if (s[i] == '/') {
a = fu * u;
u = 0;
f = true;
}
}
check();
if (res.second == 1) cout << res.first;
else if (res.first == 0) cout << 0;
else cout << res.first << '/' << res.second;
return 0;
}
C - 不成熟的梦想家
解题思路
本次训练赛感觉受益最大的一道题, 因为我对差分的使用方法还停留在修改一段区间的数值, 本题对差分的使用更加灵活; 根据题意, 暴力做法肯定是每次都更新一段区间里的值然后计算边界点的情况; 当时就卡在了怎么优化上, 因为我的思路还是在想怎么去更快地修改一段区间的值, 我想下一次询问的边界点需要用到最新的值去计算, 于是我们的思维就被限制住; 后来看题解发现原来差分还能怎么用:
既然每次都更新区间里的值一定会超时, 并且计算时我们只考虑边界点的情况, 那我们可以把每个点和前一个点的差值存起来, 也就是存差分; 因为我们每次修改一个区间时, 区间内部直接的差分就不变的, 所有就省去了遍历区间的过程, 我们只需要修改边界点的差分即可; 注意有一个坑点, 如果区间的右边界是序列的右边界设为n, 那么修改f[n+1]是没有意义的, 此处可以画图理解; 具体代码如下;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5 + 10;
int n, q, s, t, res;
int f[N];
void add(int u) {
if (f[u] > 0) res -= s * abs(f[u]);
else if (f[u] < 0) res += t * abs(f[u]);
}
void sub(int u) {
if (f[u] > 0) res += s * abs(f[u]);
else if (f[u] < 0) res -= t * abs(f[u]);
}
signed main() {
cin >> n >> q >> s >> t;
int a, last = 0;
for (int i = 0; i <= n; i++) {
cin >> a;
f[i] = a - last;
last = a;
add(i);
}
for (int i = 1; i <= q; i++) {
int a, b, c;
cin >> a >> b >> c;
sub(a);
if (b + 1 <= n) sub(b + 1);
f[a] += c;
f[b + 1] -= c;
add(a);
if (b + 1 <= n) add(b + 1);
cout << res << endl;
}
return 0;
}
E - 奶牛排队
解题思路
本题需要找一个区间, 区间里的值都要大于左端点小于右端点, 区间内部不要求单调性, 但是左端点要小于右端点; 题解有一个很巧的做法是用的单调栈; 我们可以遍历1~n来找右端点B, 对于第i个点B, 我们只需要找到B左边第一个大于等于它的的点C, 对于我们要找的左端点A一定在C的右边, 并且A是点C后面的第一个后缀最小值; 根据描述点C和点A都可以用单调栈来求: 找点C是, 每次新枚举到一个点B时，先不将新位置入栈，此时的单调栈顶就是点C位置; 找点C时需要一个下降的单调栈, 而找点A则需要一个上升的单调栈; 点A是上升单调栈中第一个下标大于点C的点; 所有我们单调栈中存的是下标, 找的过程可以用二分实现;
强烈建议用画图理解一下本题;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
int n, m, ans, res;
int f[N];
int up[N], down[N];
int su, sd;
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> f[i];
for (int i = 1; i <= n; i++) {
while (su && f[i] <= f[up[su]]) su--;//区间里的点不能和左端点相等, 所有是<=
while (sd && f[i] > f[down[sd]]) sd--;
int u = upper_bound(up + 1, up + su + 1, down[sd]) - up;
if (u != su + 1) {
ans = i - up[u] + 1;
res = max(res, ans);
}
up[++su] = i;
down[++sd] = i;
}
cout << res;
return 0;
}
F - Mieszanie kolorów
解题思路
本题不用思考很多, 直接开三个差分数组分别表示该区间是否被涂上某种颜色, 绿色只要满足有黄有蓝无红即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10;
int n, m, res;
int f[N], y[N], bl[N], r[N];
void ins(int a, int b, int c) {
if (c == 1) {
y[a]++;
y[b + 1]--;
}
else if (c == 2) {
bl[a]++;
bl[b + 1]--;
}
else if (c == 3) {
r[a]++;
r[b + 1]--;
}
}
signed main(){
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b, c;
cin >> a >> b >> c;
ins(a, b, c);
}
for (int i = 1; i <= n; i++) {
r[i] += r[i - 1];
y[i] += y[i - 1];
bl[i] += bl[i - 1];
if (y[i] && bl[i] && !r[i]) res++;
}
cout << res;
return 0;
}
H - Roy&October之取石子II
解题思路
一道博弈论的题目; 对于这种题目我们先考虑必赢的情况, 如果到October回合时石子数为1/2/3, 那么October就一定会赢, 对应的也就是说如果到Roy回合时石子数为4, 那么Roy必输; 根据这个我们得到一个规律, 对于一个数n, 两人都可以将其变成n-1~n-3之间的任意一个数; 如果October想让回合结束后石子数变成4, 那么October可以处在5/6/7的位置上, 如果October在8的位置上, 反而会会使得自己的回合时石子数为4, 也就是说October要是想赢就不能在4的倍数上, 而只要初识的石子数不是4的倍数, October就可以凭借n-1~n-3让Roy处于4的倍数上;
神秘代码
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 5e7 + 10;
int n, m, idx;
map<int, int> mp;
bool st[N];
signed main(){
scanf("%d", &n);
while (n--) {
scanf("%d", &m);
if (m % 4) cout << "October wins!" << endl;
else cout << "Roy wins!" << endl;
}
return 0;
}
I - Cow Dance Show S
解题思路
找最小值我们可以用二分的思路二分舞台大小, 在check函数中用小根堆进行模拟判断是否合法即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e4 + 10;
int n, m;
int f[N];
bool check(int u) {
priority_queue<int, vector<int>, greater<int>> q;
for (int i = 1; i <= u; i++) {
q.push(f[i]);
}
for (int i = u + 1; i <= n; i++) {
int t = q.top();
if (t + f[i] > m) return false;
else {
q.pop();
q.push(t + f[i]);
}
}
return true;
}
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> f[i];
int l = 1, r = n;
while (l < r) {
int mid = l + r>> 1;
if (check(mid)) {
r = mid;
}
else l = mid + 1;
}
cout << l;
return 0;
}