2022.08.31 模拟赛小结
目录题面
原题题包(计蒜客) 去掉了 T4,其余有部分改动
(这个链接只是为了自己方便找,页面设置权限了,不要尝试访问)
更好的阅读体验戳此进入
(建议您从上方链接进入我的个人网站查看此 Blog,在 Luogu 中图片会被墙掉,部分 Markdown 也会失效)
赛时思路
T1
一个很简单的...思维题?
一个区间有四种操作对应着区间升序、降序、翻转、对应位置交换,求最后序列的最小值位置。
关于对应位置交换的含义:4 l r k:依次对每个 i=l,l+1 , ⋯,r ,执行 swap(a[i], a[i+k])。保证 r + k ≤ n ,≥ 1。
很显然地想到维护最小值的位置,如果当前最小值位置在修改区间内,前两个操作分别代表变为首位和末位,第三个操作意味着将其从位置 $ p $ 变为 $ l + r - p $ 第四个操作需要一些简单的思考,显然考虑位置 $ p $ 在交换的两个区间内时,可以考虑如果 $ k \gt r - l $ 则直接将 $ p $ 一次转移到对应位置,反之则可以考虑判断如果 $ p $ 在 $ l + k $ 以内,一定会被多次等距向右交换直到超出范围,否则则一定会被向回交换有且仅有一次,如此即可线性完成整个题。
需要注意此题数据量极大,建议用读入优化而非 scanf
,当然一般比赛不会卡 scanf
(虽然我们这次模拟赛卡了,幸亏我习惯用读入优化)。
因为题目较为简单所以赛时顺便打了个对拍,以防思路假掉。
Code:
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
using namespace std;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
template<typename T = int>
inline T read(void);
int arr[210000];
int N, Q;
int minpos(0), minn(INT_MAX);
int main(){
// freopen("/home/jdoi/cpp/OI/in.txt", "r", stdin);
// freopen("/home/jdoi/cpp/OI/out-std.txt", "w", stdout);
freopen("resort.in", "r", stdin);
freopen("resort.out", "w", stdout);
int T = read();
while(T--){
minpos = 0; minn = INT_MAX;
N = read(), Q = read();
for(int i = 1; i <= N; ++i){
arr[i] = read();
if(arr[i] < minn){
minn = arr[i];
minpos = i;
}
}
for(int q = 1; q <= Q; ++q){
int opt = read();
switch(opt){
case 1:{
int l = read(), r = read();
if(l <= minpos && minpos <= r){
minpos = l;
}
break;
}
case 2:{
int l = read(), r = read();
if(l <= minpos && minpos <= r){
minpos = r;
}
break;
}
case 3:{
int l = read(), r = read();
if(l <= minpos && minpos <= r){
minpos = l + r - minpos;
}
break;
}
case 4:{
int l = read(), r = read(), k = read();
if(minpos < l || (minpos > r && minpos < l + k) || r + k < minpos)break;
for(int i = l; i <= r; ++i){
if(i == minpos)minpos = i + k;
else if(i + k == minpos){
minpos = i;
break;
}
}
}
}
}
printf("%d\n", minpos);
}
// fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template<typename T>
inline T read(void){
T ret(0);
short flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
暴力:
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
using namespace std;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
template<typename T = int>
inline T read(void);
int arr[210000];
int N, Q;
int minpos(0), minn(INT_MAX);
int main(){
int T = read();
while(T--){
minpos = 0; minn = INT_MAX;
N = read(), Q = read();
for(int i = 1; i <= N; ++i){
arr[i] = read();
// if(arr[i] < minn){
// minn = arr[i];
// minpos = i;
// }
}
for(int q = 1; q <= Q; ++q){
int opt = read();
switch(opt){
case 1:{
int l = read(), r = read();
sort(arr + l, arr + r + 1, less<int>());
break;
}
case 2:{
int l = read(), r = read();
sort(arr + l, arr + r + 1, greater<int>());
break;
}
case 3:{
int l = read(), r = read();
reverse(arr + l, arr + r + 1);
break;
}
case 4:{
int l = read(), r = read(), k = read();
for(int i = l; i <= r; ++i)swap(arr[i], arr[i + k]);
}
}
}
for(int i = 1; i <= N; ++i){
if(arr[i] < minn){
minn = arr[i];
minpos = i;
}
}
printf("%d\n", minpos);
}
// fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template<typename T>
inline T read(void){
T ret(0);
short flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
对拍:
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
using namespace std;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
template<typename T = int>
inline T read(void);
int N, Q;
void BuildVal(void){
freopen("/home/jdoi/cpp/OI/in.txt", "w", stdout);
int T = rndd(1, 10);
printf("%d\n", T);
while(T--){
N = rndd(3, 10000), Q = rndd(1, 10000);
printf("%d %d\n", N, Q);
for(int i = 1; i <= N; ++i)printf("%d%c", rndd(1, 100000000), i == N ? '\n' : ' ');
for(int q = 1; q <= Q; ++q){
int opt = rndd(1, 4);
int l = rndd(1, N - 2);
int r = rndd(l + 1, N - 1);
printf("%d %d %d", opt, l, r);
if(opt == 4){
int k = rndd(1, N - r);
printf(" %d\n", k);
}else{
printf("\n");
}
fflush(stdout);
}
}
fflush(stdout);
}
int main(){
// BuildVal();
while(true){
BuildVal();
freopen("/home/jdoi/cpp/OI/log.txt", "a", stdout);
// fprintf(stderr, "Caling std...\n");
system("/home/jdoi/cpp/OI/std < /home/jdoi/cpp/OI/in.txt > /home/jdoi/cpp/OI/out-std.txt");
// fprintf(stderr, "Caling bl...\n");
system("/home/jdoi/cpp/OI/bl < /home/jdoi/cpp/OI/in.txt > /home/jdoi/cpp/OI/out-bl.txt");
fflush(stdout);
if(!system("diff /home/jdoi/cpp/OI/out-bl.txt /home/jdoi/cpp/OI/out-std.txt")){
fflush(stdout);
fprintf(stderr, "Compare Successful! Which N = %d, Q = %d\n", N, Q);
}else{
fprintf(stderr, "Wrong! Which N = %d, Q = %d\n", N, Q);
break;
}
}
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template<typename T>
inline T read(void){
T ret(0);
short flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
T2
咕咕咕
T3
咕咕咕
正解
咕咕咕
UPD
update-2022_8_31 初稿
标签:int,31,ret,read,long,2022.08,define,小结,getchar From: https://www.cnblogs.com/tsawke/p/16710271.html