蒟蒻以为自己AK了 但实际上他爆零了 而且他死不要脸的边听金牌巨佬讲题边写博客

T1

求$n$的排列中逆序对数为$k$的数量 T组数据

要取模

蒟蒻随便YY了一下状移方程 $$f_{i,j}=f_{i-1,j}+f_{i,j-1}-[j\ge i]f_{i-1,j-1}$$

没取模就炸掉了

蒟蒻推柿子的时候完全没有想过这道题用DP可以更快地得到答案 蒟蒻考场上直接数学归纳，口胡证明

#include<bits/stdc++.h> using namespace std; #define in Read() int in{ int i=0,f=1;char ch=0; while(!isdigit(ch)&&ch!='-') ch=getchar(); if(ch=='-') ch=getchar(),f=-1; while(isdigit(ch)) i=(i<<1)+(i<<3)+ch-48,ch=getchar(); return i*f; } const int N=1e3+5,mod=10000; int a[N][N],n,k; int main(){ int T=in; while(T--){ memset(a,0,sizeof a); n=in,k=in; for(int i=0;i<=n;++i) a[i][0]=1; for(int i=1;i<=k;++i) a[0][i]=1; for(int i=1;i<=n;++i) for(int j=1;j<=k;++j){ a[i][j]=a[i][j-1]+a[i-1][j]; if(j-i>=0) a[i][j]=a[i][j]+mod-a[i-1][j-i]; a[i][j]%=mod; } printf("%d\n",(a[n][k]+mod-a[n][k-1])%mod); } return 0; }

T2

一个数列，区间$[l,r]$的中位数的优美值为区间长度 给出区间$[l,r]$，求其中优美值最大的一个

蒟蒻考场上YY出了做法 但是码炸了😭😢 蒟蒻不等式之类的边界弄错了

显然这题分两步，第一求优美度，第二求RMQ RMQ随便打一个数据结构就出来了，蒟蒻考场上用的SGT 然鹅最后发现暴力打擂台都能过

来谈一谈求优美度 真的不好想 但是观察一下中位数： 发现一段区间的中位数一定满足左边比它小的数的数量一定等于右边比他大的数的数量 这个数量可能为负，考虑$+n$去除符号 搞两个数组记录一下向左和向右的每个上述数量的最长长度就行 最后相符的数量的最大长度一拼，AC

说一下边界的问题

smaller和greater数组中，自己赋值$0$，其余赋值$-1$ 因为自己这个位点上向左向右就是$0$，但是其他位上该值为$0$就不能取考虑最后要将向左数量为正与向右数量为负的最大值相加 即smaller[n-num]+greater[n+num]+1，其中n是去除符号用的，+1是加他自己 向左，比中位数小的要++cnt，向右，比中位数大的要--cnt，这样这两个数的贡献才能一起加到|cnt|的区间长度里去 取等要同时取等最后统计答案时， 显然$cnt\in [1-i,i-1]$ 来一个循环枚它就是 #include<bits/stdc++.h> using namespace std; #define in Read() int in{ int i=0,f=1;char ch=0; while(!isdigit(ch)&&ch!='-') ch=getchar(); if(ch=='-') ch=getchar(),f=-1; while(isdigit(ch)) i=(i<<1)+(i<<3)+ch-48,ch=getchar(); return i*f; } const int N=1e4+5,INF=2147483647; int n,a[N]; int Smaller[N],Greater[N],val[N]; int main(){ // freopen("beautiful.in","r",stdin); // freopen(".zxd.out","w",stdout); n=in; for(int i=1;i<=n;++i) a[i]=in; for(int i=1;i<=n;++i){ memset(Smaller,-1,sizeof Smaller); memset(Greater,-1,sizeof Greater); Smaller[n]=Greater[n]=0; for(int j=i-1,cnt=n;j>=1;--j){ if(a[j]<=a[i]) --cnt; else ++cnt; Smaller[cnt]=i-j; } for(int j=i+1,cnt=n;j<=n;++j){ if(a[j]>=a[i]) ++cnt; else --cnt; Greater[cnt]=j-i; } for(int j=1-i;j<=i-1;++j){ if(Smaller[n+j]<0||Greater[n-j]<0) continue; val[i]=max(val[i],Smaller[n+j]+Greater[n-j]+1); } // printf("---%d %d\n",i,val[i]); // for(int j=1;j<=n*2;++j) printf("%d: %d %d\n",j,Smaller[j],Greater[j]);puts("---"); } // for(int i=1;i<=n;++i) cout<<val[i]<<" "; int q=in; for(int i=1;i<=q;++i){ int l=in,r=in; int res=0; for(int j=l;j<=r;++j) res=max(res,val[j]); cout<<res<<endl; } return 0; }

T3

三种操作

add：集合中插入一个数del：集合中减少一个数cnt：求集合中满足$x\&a=a,x\in Set$的数量

简单的trie

#include<bits/stdc++.h> using namespace std; #define in Read() #pragma GCC optimize(2) #pragma GCC optimize(3) int in{ int i=0,f=1;char ch=0; while(!isdigit(ch)&&ch!='-') ch=getchar(); if(ch=='-') ch=getchar(),f=-1; while(isdigit(ch)) i=(i<<1)+(i<<3)+ch-48,ch=getchar(); return i*f; } const int N=2e5+5; int n,x,sz,val[N]; char opt[10]; struct Trie{ int s[2]; }trie[N]; void insert(int x,int v){ int p=0; for(int i=16;i>=0;--i){ int c=(x>>i)&1; if(!trie[p].s[c]) trie[p].s[c]=++sz; p=trie[p].s[c]; } val[p]+=v; } int query(int x,int deg,int p){ if(deg<0) return val[p]; int c=(x>>deg)&1; if(c){ int res=0; if(trie[p].s[0]) res+=query(x,deg-1,trie[p].s[0]); if(trie[p].s[1]) res+=query(x,deg-1,trie[p].s[1]); return res; }else{ if(trie[p].s[0]) return query(x,deg-1,trie[p].s[0]); else return 0; } } int main(){ // freopen("subset.in","r",stdin); // freopen("subset.out","w",stdout); n=in; for(int i=1;i<=n;++i){ scanf("%s",opt); x=in; if(opt[0]=='a'){ insert(x,1); }else if(opt[0]=='d'){ insert(x,-1); }else{ printf("%d\n",query(x,16,0)); } } return 0; }

题面

放一下题面 方便搜索的朋友使用

T1 1 permut 1.1 题目᧿述 求由 1 到 n 一共 n 个数字组成的所有排列中，逆序对个数为 k 的有多少个 1.2 输入Ṭᔿ 第一行为一个整数 T，为数据组数。 以下 T 行，每行两个整数 n，k，意义如题目所述。 1.3 输出Ṭᔿ 对每组数据输出答案对 10000 取模后的结果

T2 2 beautiful 2.1 题目᧿述 一个长度为 n 的序列，对于每个位置 i 的数 ai 都有一个优美值，其定义是：找到序列中最 长的一段 [l, r]，满足 l ≤ i ≤ r，且 [l, r] 中位数为 ai（我们比较序列中两个位置的数的大小时， 以数值为第一关键字，下标为第二关键字比较。这样的话 [l, r] 的长度只有可能是奇数），r - l

1 就是 i 的优美值。 接下来有 Q 个询问，每个询问 [l, r] 表示查询区间 [l, r] 内优美值的最大值。 2.2 输入Ṭᔿ 第一行输入 n 接下来 n 个整数，代表 ai 接下来 Q，代表有 Q 个区间接下来 Q 行，每行 两个整数 l, r(l ≤ r)，表示区间的左右端点 2.3 输出Ṭᔿ 对于每个区间的询问，输出答案

T3 3 subset 3.1 题目᧿述 一开始你有一个空集，集合可以出现重复元素，然后有 Q 个操作

add s 在集合中加入数字 s。del s 在集合中删除数字 s。保证 s 存在cnt s 查询满足 a&s = a 条件的 a 的个数 3.2 输入Ṭᔿ 第一行一个整数 Q 接下来 Q 行，每一行都是 3 个操作中的一个 3.3 输出Ṭᔿ 对于每个 cnt 操作输出答案