NOIP提高组模拟赛23
本场比赛是暴力的胜利！！！！
A. d
怎么说呢，考场想到正解方式，但是错误使用双指针，而且完全没想平衡树。。。。
做法就是分别按照\(a,b\)排序，然后枚举按照升序删掉多少\(a\)小的，剩下的按照\(b\)删，使用平衡树很好的解决，可惜考场完全忘了有这个东西。。
好在这样的暴力有\(81pts\)
code
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn=100005;
const int inf=2147483647;
int n,m;
struct node{ll a,b;}a[maxn];
struct FHQ_Treap{
struct node{
int l,r,val,size,key;
}t[maxn];
int root,tot;
int New(int val){t[++tot].val=val;t[tot].size=1;t[tot].key=rand();return tot;}
void push_up(int x){t[x].size=t[t[x].l].size+t[t[x].r].size+1;}
void split(int x,int &l,int &r,int val){
if(x==0){l=r=0;return;}
if(t[x].val>val){split(t[x].l,l,t[x].l,val);r=x;push_up(r);return;}
else{split(t[x].r,t[x].r,r,val);l=x;push_up(l);return;}
}
int merge(int l,int r){
if(!l||!r)return l|r;
if(t[l].key B. e
这是暴力的高光时刻！！！！
每次询问按照\(dfs\)序排一下，然后对相邻的两个点不停的暴力跳父亲取\(min\)
没错，暴力跳！
这样有\(89pts\)!!!
\(pyt\)学长在博客里说暴力的上界是\(89\)
然而，只需要加上快读+快输+特判（\(val-r==0\)），你就能轻松愉快的\(A\)掉，什么主席树？树套树？暴力\(yyds\)!!!!
暴力没有上界！！
其实应该可以卡掉，但是数据有点水，可以证明这种暴力的复杂度在最坏情况下是询问次数*节点数
假设树退化成一条链，每次都询问两个端点.......那这个暴力就萎了
code
#include
#include
#include
using namespace std;
const int maxn=100005;
int n,a[maxn],head[maxn],tot,lastans,ls[maxn];
bool flag;
int read(){
int x=0;char c;c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x;
}
void print(int x){
if(x==0)putchar('0');
char c[105];int w=0;
while(x)c[++w]=x%10+'0',x/=10;
for(int i=w;i>=1;--i)putchar(c[i]);
putchar('\n');
}
struct edge{
int to,net;
}e[maxn<<1|1];
void add(int u,int v){
e[++tot].net=head[u];
head[u]=tot;
e[tot].to=v;
}
struct node{
int dep,fa,son,top,size,id;
}d[maxn];
int dfn[maxn],dn;
void dfs1(int x){
dfn[x]=++dn;
for(int i=head[x];i;i=e[i].net){
int v=e[i].to;
if(v==d[x].fa)continue;
d[v].dep=d[x].dep+1;
d[v].fa=x;
dfs1(v);
}
}
bool cmp(int x,int y){
return dfn[x]d[v].dep){
ans=min(ans,abs(a[u]-r));
if(ans==0)return ans;
u=d[u].fa;
}
while(u!=v){
ans=min(ans,abs(a[u]-r));
ans=min(ans,abs(a[v]-r));
if(ans==0)return ans;
u=d[u].fa;v=d[v].fa;
}
ans=min(ans,abs(a[u]-r));
return ans;
}
void DO(int k,int r){
if(k<=1||flag){
lastans=abs(a[ls[1]]-r);
return;
}
sort(ls+1,ls+k+1,cmp);
lastans=2147483647;
for(int i=1;i 不过这题还是再次证明了那个真理：暴力出奇迹！
C. f
两个数是否对逆序对有贡献，取决于两个数二进制不同的最高位
用\(Tire\)树预处理出来从某位开始与该数不同的数的个数，然后二分答案，二分逆序对个数，查询有多少小于的
直接搞会\(TLE\)，需要\(meet in middle\)，因为每一位的贡献是固定且互不影响的，所以将二进制拆成两半考虑，每次组合一下即可
查询时用到了一点双指针思想，利用前一半数量单增，对应后一半单减进行优化。
code
#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn=500005;
int a[maxn],a2[maxn],p2;
ll gt[33][2];
int n,k,p,k1,k2,s2,s1,root;
struct tire{
struct node{
int son[2],cnt;
}t[maxn<<6|1];
int cnt=1;
void ins(int v){
int x=1;
for(int i=30;i>=-1;--i){
++t[x].cnt;
if(i==-1)break;
int now=v>>i&1;
if(!t[x].son[now])t[x].son[now]=++cnt;
gt[i][now]+=t[t[x].son[now^1]].cnt;
x=t[x].son[now];
}
}
}T;
struct node{
ll num;int i;
}fr[maxn],se[maxn];
bool cmp(node x,node y){return x.numx&&j>0)--j;
ans+=j;
}
return ans;
}
int main(){
scanf("%d%d%d",&n,&k,&p);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
if(k==0){printf("0 0\n");return 0;}
for(int i=1;i<=n;++i)T.ins(a[i]);
k1=k>>1;k2=k-k1;
s1=1<>j&1];
fr[i+1].i=i;
}
sort(fr+1,fr+s1+1,cmp);
for(int i=0;i>j&1];
se[i+1].i=i;
}
sort(se+1,se+s2+1,cmp);
ll l=0,r=1ll*n*(n-1)/2;
while(l>1;
if(check(mid)ans1)--j;
int ls=j;
while(se[j].num+fr[i].num==ans1&&j>0)a2[++p2]=fr[i].i+(se[j].i<