2022.10.14 模拟赛小结
大概是相对来讲补的比较全的一场了。。。
题面PDF链接
(这个链接只是为了自己方便找，页面设置权限了，不要尝试访问)
更好的阅读体验戳此进入
（建议您从上方链接进入我的个人网站查看此 Blog，在 Luogu 中图片会被墙掉，部分 Markdown 也会失效）
赛时思路
T1
排列 $ A_n $ 种进行若干次操作，每次删去相邻两个数较大的那个，求最终可能得到的序列数量
原题 LG-P7972 [KSN2021] Self Permutation
大概就是想到了一些性质（不过没用），想到了一些 DP 状态（然后没转移出来），总之最后的最后推了一个来小时，啥也没推出来，只能想到十分 nt 的 $ O(n!) $ 做法，直接爆零，我是 fw。
T2
对于正整数序列 $ A_n $，每次求区间 $ \left[ l, r \right] $ 内值域在 $ \left[ a, b \right] $ 的数和数值个数。
能依稀感觉有点像莫队但是依然不会，然后也没想到值域分块，最后糊了个暴力上去，$ O(nm) $ 感觉好像也能过？不过最后好像是数据锅了还是怎么，总之最后 LemonLime 上爆零了。
Code
#define USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
typedef long long ll;
typedef unsigned long long unll;
typedef unsigned int uint;
typedef long double ld;
template < typename T = int >
T read(void);
int N, M;
int a[110000];
// bool vis[110000];
bitset < 101000 > vis;
// int buc100[1100][110000];
// vector < int > arr;
int main(){
freopen("interval.in", "r", stdin);
freopen("interval.out", "w", stdout);
N = read(), M = read();
for(int i = 1; i <= N; ++i)a[i] = read();
// sort(arr.begin(), arr.end());
// for(int i = 1; i <= N; ++i)a[i] = distance(arr.begin(), lower_bound(arr.begin(), arr.end(), a[i])) + 1;
// for()
if(M <= 1000){
while(M--){
int l = read(), r = read(), x = read(), y = read();
int ans1(0), ans2(0);
vis.reset();
for(int i = l; i <= r; ++i){
if(x <= a[i] && a[i] <= y){
++ans1;
if(!vis[a[i]])vis.set(a[i]), ++ans2;
}
}
printf("%d %d\n", ans1, ans2);
}
return 0;
}
if(N <= 1000){
while(M--){
int l = read(), r = read(), x = read(), y = read();
int ans1(0);
vector < int > tmp;
for(int i = l; i <= r; ++i)
if(x <= a[i] && a[i] <= y)++ans1, tmp.push_back(a[i]);
auto endpos = unique(tmp.begin(), tmp.end());
printf("%d %d\n", ans1, (int)distance(tmp.begin(), endpos));
}
return 0;
}
return 0;
}
template < typename T >
T read(void){
T ret(0);
short flag(1);
char c = getchar();
while(!isdigit(c) && c != '-')c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}ret *= flag;
return ret;
}
T3
构造一棵有 $ 2n $ 节点的树，对于节点 $ i $ 和 $ i + n $ 记值为 $ i $，要求满足任意 $ i $ 和 $ i + n $ 之间的路径的值异或起来为 $ i $。
原题 AT5140 [AGC035C] Skolem XOR Tree
阴间构造，只推出来了 $ 2^t $ 的数是无解的，不过没啥用，puts("No") 也能过。
总之最后手动构造的 $ 1-10 $ 过了，然后有两个 No 过了，成为了本场所有题里唯一的 $ 40\texttt{pts} $。
Code
#define USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
typedef long long ll;
typedef unsigned long long unll;
typedef unsigned int uint;
typedef long double ld;
template < typename T = int >
T read(void);
bool is2k[110000];
int main(){
freopen("xortree.in", "r", stdin);
freopen("xortree.out", "w", stdout);
int N = read();
int cur(1);
while(cur <= 101000)is2k[cur] = true, cur <<= 1;
if(is2k[N])printf("No\n"), exit(0);
switch(N){
// case 1:{
// printf("No\n");
// break;
// }
// case 2:{
// printf("No\n");
// break;
// }
case 3:{
printf("Yes\n1 2\n2 3\n3 4\n4 5\n5 6\n");
break;
}
// case 4:{
// printf("");
// break;
// }
case 5:{
printf("Yes\n4 5\n5 1\n1 9\n9 10\n4 6\n6 8\n8 7\n6 2\n2 3\n");
break;
}
case 6:{
printf("Yes\n4 5\n5 1\n1 10\n4 7\n7 9\n9 8\n7 2\n2 3\n7 11\n10 6\n9 12\n");
break;
}
case 7:{
printf("Yes\n4 5\n5 1\n1 11\n4 8\n8 10\n10 9\n8 2\n2 3\n8 12\n11 6\n10 13\n12 14\n10 7\n");
break;
}
// case 8:{
// printf("");
// break;
// }
case 9:{
printf("10 8\n8 9\n10 18\n18 17\n10 5\n10 13\n13 15\n5 4\n4 1\n1 14\n1 2\n1 12\n14 7\n2 3\n12 11\n12 6\n12 16\n");
break;
}
case 10:{
printf("10 8\n8 9\n8 11\n11 19\n19 18\n11 5\n11 14\n5 4\n14 16\n4 1\n1 13\n1 2\n1 15\n15 7\n2 3\n3 12\n3 6\n3 17\n12 20\n");
break;
}
default:{
puts("No");
break;
}
}
return 0;
}
template < typename T >
T read(void){
T ret(0);
short flag(1);
char c = getchar();
while(!isdigit(c) && c != '-')c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}ret *= flag;
return ret;
}
T4
期望题，不会，不过实际上不是很难，不是不可做的题。
正解
T1
把每个点建立一个区间，左右分别是第一个比它小的数的位置向中心移动一位，用单调栈从左到右从右到左各自维护一遍，令 $ dp(i) $ 表示以 $ a_i $ 结尾有多少种可能的最终排列，转移就是从 $ j \lt i $ 种找到所有 $ i $ 和 $ j $ 的区间有交的来求和，这个东西可以用树状数组维护一下，最终复杂度 $ O(n \log n) $，可以通过。
Code
#define _USE_MATH_DEFINES
#include <bits/extc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
/******************************
abbr
******************************/
using namespace std;
using namespace __gnu_pbds;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
#define MOD (ll)(1e9 + 7)
#define MAXN 310000
template<typename T = int>
inline T read(void);
int N;
int a[MAXN];
int lft[MAXN], rht[MAXN];
ll dp[MAXN];
ll ans(0);
stack < int > cur;
class TreeArray{
private:
int lim;
ll tr[MAXN];
public:
void set(int lim){this->lim = lim;}
int lowbit(int x){return x & -x;}
void add(int x, ll v){while(x <= lim)tr[x] = (tr[x] + v) % MOD, x += lowbit(x);}
ll query(int x){ll ret(0); while(x)ret = (ret + tr[x]) % MOD, x -= lowbit(x); return ret;}
}tr;
int main(){
N = read();tr.set(N);
for(int i = 1; i <= N; ++i)a[i] = read();
for(int i = 1; i <= N; ++i){
while(!cur.empty() && a[cur.top()] > a[i])rht[cur.top()] = i - 1, cur.pop();
cur.push(i);
}while(!cur.empty())rht[cur.top()] = N, cur.pop();
for(int i = N; i >= 1; --i){
while(!cur.empty() && a[cur.top()] > a[i])lft[cur.top()] = i + 1, cur.pop();
cur.push(i);
}while(!cur.empty())lft[cur.top()] = 1, cur.pop();
tr.add(1, 1);
for(int i = 1; i <= N; ++i){
dp[i] = (tr.query(N) - tr.query(lft[i] - 1) + MOD) % MOD;
tr.add(rht[i], dp[i]);
}
int cmn(INT_MAX);
for(int i = N; i >= 1; --i){cmn = min(cmn, a[i]); if(cmn == a[i])ans = (ans + dp[i]) % MOD;}
printf("%lld\n", ans);
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
说实话这题确实不难，不过以前好像几乎没写过莫队，也没怎么写过值域分块，考场上是在是没想出来。
通过莫队维护区间 $ \left[ l, r \right] $ 的答案，具体的答案维护套一个值域分块，实现起来确实不难，细节也不是很多，挺板子的。
确实是没啥可说的。
Code
#define _USE_MATH_DEFINES
#include <bits/extc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
/******************************
abbr
******************************/
using namespace std;
using namespace __gnu_pbds;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
#define BLOCK(x) (x / B + 1)
#define MAXN 110000
template<typename T = int>
inline T read(void);
int N, M;
int B;
int maxV(-1);
int blk[MAXN], blkv[MAXN];
int a[MAXN];
int sum_pos[MAXN];
int sum_blk[MAXN], sum_blk_exist[MAXN];
pair < int, int > ans[MAXN];
struct Query{
int l, r;
int a, b;
int idx;
friend const bool operator < (const Query x, const Query y){
if(blk[x.l] != blk[y.l])return x.l < y.l;
return blk[x.l] & 1 ? x.r < y.r : x.r > y.r;
}
};
vector < Query > Q;
pair < int, int > QueryBlk(int l, int r){
if(l > maxV)return {0, 0};
r = min(r, maxV);
int bl = blkv[l], br = blkv[r];
int ret1(0), ret2(0);
if(bl == br){
for(int i = l; i <= r; ++i)ret1 += sum_pos[i], ret2 += (bool)sum_pos[i];
return {ret1, ret2};
}
if(blkv[l - 1] == bl){
for(int i = l; blkv[i] == bl && i <= maxV; ++i)
ret1 += sum_pos[i], ret2 += (bool)sum_pos[i];
++bl;
}
if(blkv[r + 1] == br){
for(int i = r; blkv[i] == br && i >= 1; --i)
ret1 += sum_pos[i], ret2 += (bool)sum_pos[i];
--br;
}
for(int i = bl; i <= br; ++i)
ret1 += sum_blk[i], ret2 += sum_blk_exist[i];
return {ret1, ret2};
}
void add(int x){
++sum_blk[blkv[x]];
if(++sum_pos[x] == 1)++sum_blk_exist[blkv[x]];
}
void del(int x){
--sum_blk[blkv[x]];
if(--sum_pos[x] == 0)--sum_blk_exist[blkv[x]];
}
int main(){
N = read(), M = read();
B = (double)N / sqrt(M) + 1;
for(int i = 1; i <= N; ++i)
a[i] = read(), blk[i] = i / B + 1, maxV = max(maxV, a[i]);
B = sqrt(maxV) + 1;
for(int i = 1; i <= maxV; ++i)
blkv[i] = i / B + 1;
for(int i = 1; i <= M; ++i){
int l = read(), r = read(), a = read(), b = read();
Q.emplace_back(Query{l, r, a, b, i});
}sort(Q.begin(), Q.end());
int gl(0), gr(0);
for(auto ask : Q){
while(gl > ask.l)add(a[--gl]);
while(gr < ask.r)add(a[++gr]);
while(gl < ask.l)del(a[gl++]);
while(gr > ask.r)del(a[gr--]);
ans[ask.idx] = QueryBlk(ask.a, ask.b);
}
for(int i = 1; i <= M; ++i)printf("%d %d\n", ans[i].first, ans[i].second);
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;
}
T3
确实算是一道很神奇的构造。
首先显然若 $ n = 2^t $，或者说 $ n = \operatorname{lowbit}(n) $，那么显然无解。
考虑到对于 $ \forall i \in \left[ 2, n – 1 \right] $ 且 $ 2 \mid i $，有 $ i \oplus 1 \oplus (i + 1) \oplus i = i $，对于 $ i + 1 $ 同理，所以可以以 $ 1 $ 为根，在 $ 1 $ 上挂两个链，$ i \rightarrow i + 1 \(，\) i + 1 + n \rightarrow i + n $。然后考虑把 $ 1 + n $ 挂在 $ 3 $ 或者 $ 2 + n $ 上即可，这个很显然。
然后若 $ 2 \mid n $，对于最后剩下的 $ n $，挂一条 $ n \rightarrow \operatorname{lowbit}(n) + 1 + n \rightarrow 1 \rightarrow n – \operatorname{lowbit}(n) \rightarrow n + n $ 的链即可。
#define _USE_MATH_DEFINES
#include <bits/extc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
/******************************
abbr
******************************/
using namespace std;
using namespace __gnu_pbds;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
template<typename T = int>
inline T read(void);
int lowbit(int x){return x & -x;}
int main(){
int N = read();
if(lowbit(N) == N)puts("No"), exit(0);
puts("Yes");
for(int i = 2; i <= N - 1; i += 2){
printf("%d %d\n", 1, i);
printf("%d %d\n", i, i + 1);
printf("%d %d\n", 1, i + 1 + N);
printf("%d %d\n", i + 1 + N, i + N);
}
printf("%d %d\n", 3, 1 + N);
if(!(N & 1)){
printf("%d %d\n", N, lowbit(N) + 1 + N);
printf("%d %d\n", N - lowbit(N), N + N);
}
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;
}
T4
咕咕咕，不过这题还不错，加到题单里了，laterrrrrrrrrrrr 可以做一做。
UPD
update-2022_10_14 初稿
原文地址：http://www.cnblogs.com/tsawke/p/16820310.html
1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，请务用于商业用途!
3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！
8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载
声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性
