NOIP2017模拟赛（五）总结

时间：2022-12-17 08:46:49

NOIP2017模拟赛（五）解题报告

T1：

最远

题目描述

奶牛们想建立一个新的城市.它们想建立一条长度为N (1 <= N <= 1,000,000)的 主线大街，然后建立K条 (2 <= K <= 50,000)小街, 每条小街的尽头有一间房子(小街的其它位置没有房子).每条小街在主线大街的P_i 处分支，(0 <= P_i <= N) , 小街的长度是 L_i (1 <= L_i <= 1,000,000).FJ想知道最远的两个房子之间的距离是多少。

输入格式 1866.in

*第1行: 两个整数: N 和K.
* 第2..K+1行: 每行两个整数P_i、L_i. 对应着一条小街。

输出格式 1866.out

*一行:最远的两个房子之间的距离.

输入样例 1866.in

5 4
5 6
2 2
0 3
2 7

输出样例 1866.out

16
输入解释:
主线大街长度是5，有4条小街，分别位于距离主线大街 0、2、 2、 5 处。这4条小街的长度分别是3、 2、 7、 6. 注意：主线大街的同一个地点可以有多条小街.
输出解释:
房子1 和房子 4 的距离最远，是16。

题目分析：水题一道。我们将房子按P值排序，第i,j(i<j)所房子间的距离为H[j]+P[j]-P[i]+H[i]，于是我们扫一遍，维护H[i]-P[i]的最大值即可，时间复杂度O(Klog(K))（如果用桶排时间为O(N+K)）。后来我听说AbEver写了O(n)的求树的直径，呵呵……

CODE：

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
using namespace std;

const int maxk=50100;

struct data
{
int P,L;
} house[maxk];

int N,K;
int Max,ans=0;

bool Comp(data x,data y)
{
return x.P<y.P;
}

int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);

scanf("%d%d",&N,&K);
for (int i=1; i<=K; i++) scanf("%d%d",&house[i].P,&house[i].L);
sort(house+1,house+K+1,Comp);
Max=house[1].L-house[1].P;
for (int i=2; i<=K; i++)
{
ans=max(ans,house[i].P+house[i].L+Max);
Max=max(Max,house[i].L-house[i].P);
}
printf("%d\n",ans);

return 0;
}

T2：

01游戏

题目描述

有一种游戏,刚开始有A 个0和B个 1. 你的目标是最后变成A+B个1. 
每一次,你选中任意K个数字, 把他们的值取反(原来是0的变1, 原来是1的变0).
请问至少需要多少次才能达到目标？假如不可能达到目标，就输出-1.

输入格式 1867.in

多组测试数据.
第一行是一个整数: nG, 表示有nG组测试数据. 1 <= nG <= 5.
每组测试数据的格式如下:
第一行: 三个整数: A 、B 、K 。 1 <= A、B、K <= 100,000.

输出格式 1867.out

共nG行，每行一个整数。

NOIP2017模拟赛（五）总结

题目分析：这题我虽然在考场上AC了，但写的是很不优美的O(nlog(n))的Splay+宽搜。我们首先发现一种状态A个0，B个1和0,1摆放的位置无关，于是我们记f[a]表示到达a个0所需要的最小步数，这就是个宽搜。经计算，f[a]能够更新到的状态是|a-K|,|a-K|+2……min(a+K,2A+2B-a-K)-2, min(a+K,2A+2B-a-K)，即一个区间内的所有奇数或偶数。而且由于每个状态只会被加进一次队列，所以我们开两棵Splay，分别存奇数和偶数即可。当que[head]=a的时候，找|a-K|的前驱旋到根，找min(a+K,2A+2B-a-K)的后继旋到根的右儿子，DFS一遍根的右儿子的左子树，将里面的数加进队列，然后砍掉它。当然我们也可以用线段树来优化，树上的节点只需要记录对应的区间是否已经全部被加进队列即可。这样每一次log(A+B)地向下走，一定会将至少一个状态加进队列。以上的两种方法时间都是O((A+B)log(A+B))的，但我觉得Splay更好写。

其实我第一眼看到这题的时候，是往数论这方面去想的，我感觉像是log(n)的Exgcd之类的，或者是有O(1)的方法，但想了一会儿没什么头绪，而且感觉如果要用数学方法的话分类讨论，特殊判断太多了，很容易错。为了拿分还是写宽搜稳一点，至少不会错。加上我比较擅长数据结构，30min调对Splay无压力，于是果断……

后来听AbEver说网上有一个O(n)的方法，还有个O(1)的方法，好像是各种数学证明+恶心的分类讨论。我也还没有仔细去看……之后再填坑吧。

CODE：

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
using namespace std;

const int maxn=200100;

struct Tnode
{
int valA;
Tnode *fa,*son[2];
int Get_d() { return fa->son[1]==this; }
void Connect(Tnode *P,int d) { (son[d]=P)->fa=this; }
} tree[maxn];
Tnode *Root[2];
int cur;

int que[maxn];
int num[maxn];
int head,tail;

int nG,A,B,K;

Tnode *Build(int L,int R,Tnode *F)
{
if (L>R) return NULL;
Tnode *P=&tree[++cur];
int mid=(L+R)>>1;
if ( (L&1)^(mid&1) ) mid++;
P->valA=mid;
P->fa=F;
P->son[0]=Build(L,mid-2,P);
P->son[1]=Build(mid+2,R,P);
return P;
}

void Zig(Tnode *P,Tnode *&tag)
{
int d=P->Get_d();
Tnode *F=P->fa;
if (P->son[!d]) F->Connect(P->son[!d],d);
else F->son[d]=NULL;
if (F!=tag) F->fa->Connect(P,F->Get_d());
else P->fa=F->fa,tag=P;
P->Connect(F,!d);
}

void Splay(Tnode *P,Tnode *&tag)
{
Tnode *F;
while (P!=tag)
{
F=P->fa;
if (F!=tag) ( F->Get_d() ^ P->Get_d() )? Zig(P,tag):Zig(F,tag);
Zig(P,tag);
}
}

void Work(Tnode *P,int val,Tnode *&tag)
{
if (!P) return;
if ( val < P->valA ) Work(P->son[0],val,tag);
if ( val == P->valA ) Splay(P,tag);
if ( P->valA < val ) Work(P->son[1],val,tag);
}

Tnode *Find_prev(Tnode *P,int v,Tnode *op)
{
if (!P) return op;
if ( v <= P->valA ) return Find_prev(P->son[0],v,op);
return Find_prev(P->son[1],v,P);
}

Tnode *Find_succ(Tnode *P,int v,Tnode *op)
{
if (!P) return op;
if ( v < P->valA ) return Find_succ(P->son[0],v,P);
return Find_succ(P->son[1],v,op);
}

void Copy(Tnode *P,int Num)
{
if (!P) return;
que[++tail]=P->valA;
num[tail]=Num;
Copy(P->son[0],Num);
Copy(P->son[1],Num);
}

int main()
{
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);

scanf("%d",&nG);
while (nG--)
{
scanf("%d%d%d",&A,&B,&K);
if (!A)
{
printf("0\n");
continue;
}
cur=-1;

int L=-2,R=A+B+2;
R-=(R&1);
Root[0]=Build(L,R,NULL);

L=-1,R=A+B+2;
if (R%2==0) R--;
Root[1]=Build(L,R,NULL);

int x=A&1;
Work(Root[x],A-2,Root[x]);
Work(Root[x],A+2,Root[x]->son[1]);
Root[x]->son[1]->son[0]=NULL;

head=0,tail=1;
que[1]=A;
num[1]=0;
bool sol=false;

while (head<tail)
{
int val=que[++head];
if (val==K)
{
sol=true;
printf("%d\n",num[head]+1);
break;
}

int x=A+B-val;
int low=max(val-K,K-val);
int high=min(val+K,val+x+x-K);
if (low>high) continue;

x=low&1;
Tnode *P=Find_prev(Root[x],low,NULL);
low=P->valA;
P=Find_succ(Root[x],high,NULL);
high=P->valA;

Work(Root[x],low,Root[x]);
Work(Root[x],high,Root[x]->son[1]);
Copy(Root[x]->son[1]->son[0],num[head]+1);
Root[x]->son[1]->son[0]=NULL;
}

if (!sol) printf("-1\n");
}

return 0;
}

T3：

bst计数

题目描述

相信大家对二叉查找树都很熟悉了，现在给你N个整数的序列，每个整数都在区间[1,N]内，且不重复。现在要你按照给定序列的顺序，建立一个二叉查找树，把第一整数作为根，然后依次插入后面的整数。
每个结点X的插入过程其实就是模拟下面的 insert(X,root)过程：
NOIP2017模拟赛（五）总结
你要求的是：每次把序列的一个整数插入到二叉查找数后，当目前为止计数类加器C的值是多少？请把它输出。注意：第一次插入根，计数器C的值是0，你可以理解为插入根是不执行insert()操作的，其后每插入一个结点，C都类加，也就是每次进入过程insert( number X, node N )，都会执行increase the counter C by 1，使得C不断增大。

输入格式 1868.in

第一行：一个整数：N,表示序列有多少个整数。 1 <= N <=300000
接下来有N行，每行一个整数X, X在区间[1,N]内，且不重复，这N个整数就组成了一个有序的序列。

输出格式 1868.out

N行，每行一个整数，第一行表示你把序列的第一个数插入到二叉查找树后，当前计数器C的值是多少。 50%的数据：N <= 1000。

NOIP2017模拟赛（五）总结

题目分析：看到这题的时候我已经无力吐槽了：这不就是HNOI2017Day1T1的弱弱弱化版么？

有一个很显然的结论：每一次插入一个数val时，它一定会作为前驱和后继中深度较大的点的儿子。这是因为在这棵BST中，val的前驱和后继一定具有祖先关系。反证一下：如果prev和succ没有祖先关系，它们的LCA就必定会比prev或succ更靠近val，这样val的前驱或后继就变成了LCA（还要注意，这里的前提是没有两个数相同）。那么假设后继在前驱的右子树中，前驱就肯定不可能再接val为右儿子，并且由于后继是前驱的右子树中的值最小的点，它的左儿子一定为空。

于是我果断写了个treap，每个节点除了维护它的值val以外，还额外维护它在原BST上的深度dep。由于treap可以旋转，可以在log(n)的时间内找插入前驱后继，所以总时间复杂度是O(nlog(n))的。

然而后来我又听到其实不用数据结构，可以用离线+链表在O(n)的时间内做这题，感觉自己好菜……之后再填坑吧。

CODE：

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
#include<time.h>
using namespace std;

const int maxn=300100;

struct Tnode
{
int val,dep,fix;
Tnode *lson,*rson;
} tree[maxn];
Tnode *Root;
int cur=-1;

int N,X;
long long C=0;

Tnode *New_node(int v,int d)
{
cur++;
tree[cur].val=v;
tree[cur].dep=d;
tree[cur].fix=rand();
tree[cur].lson=tree[cur].rson=NULL;
return tree+cur;
}

Tnode *Find_prev(Tnode *P,int v,Tnode *op)
{
if (!P) return op;
if ( v < P->val ) return Find_prev(P->lson,v,op);
return Find_prev(P->rson,v,P);
}

Tnode *Find_succ(Tnode *P,int v,Tnode *op)
{
if (!P) return op;
if ( v < P->val ) return Find_succ(P->lson,v,P);
return Find_succ(P->rson,v,op);
}

void Right_turn(Tnode *&P)
{
Tnode *W=P->lson;
P->lson=W->rson;
W->rson=P;
P=W;
}

void Left_turn(Tnode *&P)
{
Tnode *W=P->rson;
P->rson=W->lson;
W->lson=P;
P=W;
}

void Insert(Tnode *&P,int v,int d)
{
if (!P) P=New_node(v,d);
else
if ( v < P->val )
{
Insert(P->lson,v,d);
if ( P->lson->fix < P->fix ) Right_turn(P);
}
else
{
Insert(P->rson,v,d);
if ( P->rson->fix < P->fix ) Left_turn(P);
}
}

int main()
{
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);

srand( time(0) );
rand();
rand();

scanf("%d",&N);
scanf("%d",&X);
Root=New_node(X,1);
printf("0\n");

for (int i=1; i<N; i++)
{
scanf("%d",&X);
int dep_fa=0;
Tnode *prev=Find_prev(Root,X,NULL);
Tnode *succ=Find_succ(Root,X,NULL);
if (prev) dep_fa=max(dep_fa,prev->dep);
if (succ) dep_fa=max(dep_fa,succ->dep);
C=C+(long long)dep_fa;
Insert(Root,X,dep_fa+1);
printf("%I64d\n",C);
}

return 0;
}

比赛心得：这次虽然AK了，但第二题敲了Splay+宽搜，说明我还是只会敲数据结构的蒟蒻，思维依旧一般。第三题一见到做过类似的题就马上敲了个treap，没有往更优的时间复杂度去想，虽然好像300000也能过的说。考场上当然是敲自己熟悉的算法更好，但考后还要继续研究一下一题多解，将自己不熟的算法也写多几遍。我……我也不知道啦。

 

标签：

相关文章