[模拟赛]提高2019-05-19

并不知道今天有比赛

比赛13:15开始，然而13:35才到机房...

只有我和jjc...

于是想起数学作业单元AB还没改...又改+订正了好久...

14:15左右被通知去机房3打比赛...

然后忙着把剩下的题写完之后有人来QQ找我...

回复了一下...本来想着晚上再说的...结果貌似那个人下线了...

总之大概14:30左右开始的比赛...

%%%MinamotoAK虐全场%%%初二神仙lch%%%

又掉rating了....

第一题：

好像很水的样子...

水了个树形DP...

然鹅样例RE了...

忘记return了...

既然好像大家都做出来了...就不具体写了...

貌似才不到30min，理所当然的去上了个厕所...

第二题：

题目描述

nodgd 的粉丝太多了，每天都会有很多人排队要签名。今天有𝑛个人排队，每个人的身高都是一个整数，且互不相同。很不巧，nodgd 今天去忙别的事情去了，就只好让这些粉丝们明天再来。同时 nodgd 提出了一个要求，每个人都要记住自己前面与多少个比自己高的人，以便于明天恢复到今天的顺序。但是，粉丝们或多或少都是有些失望的，失望使她们晕头转向、神魂颠倒，已经分不清楚哪一边是“前面”了，于是她们可能是记住了前面比自己高的人的个数，也可能是记住了后面比自己高的人的个数，而且他们不知道自己记住的是哪一个方向。 nodgd 觉得，即使这样明天也能恢复出一个排队顺序，使得任意一个人的两个方向中至少有一个方向上的比他高的人数和他记住的数字相同。可惜𝑛比较大，显然需要写个程序来解决，nodgd 很忙，写程序这种事情就交给你了。

Input

第一行输入一个整数𝑛，表示指令的条数。接下来𝑛行，每行两个整数𝑎𝑖,𝑏𝑖，表示一个人的身高和她记住的数字，保证身高互不相同。

Output

输出一行，这个队列里从前到后的每个人的身高。如果有多个答案满足题意，输出字典序最小。如果不存在满足题意的排列，输出“impossible”（不含引号）。

看到数据范围1e5反而松了一口气...不是DP...

如果是DP的话现在的状态应该写不出来...

那应该是是某个神奇的数据结构维护了吧...

然而想不出来...

于是先打了一个$O(n!*n^2)$的暴力...

貌似题面没有数据范围...不知道有几分...最多30分吧...

然后看了T3期望？

看数据范围像是DP...瞪了好久...然后写了n特别小的数据（没错...n=1和n=2的手玩数据）...

然后回去看T2...

貌似有点思路，好像可以离散了之后搞到权值线段树上去...

然而既没有进展了...

后来在比赛结束还有1h的时候打了一个$O(n^3)$的暴力...

大概就是先把最小的元素确定位置，再是次小的...以此类推（因为之后放的每个数都会比这个大诶，所以只要是空位就是比它大的）

这里是代码:(告诉你们个秘密:$n^3$过了1000的数据)

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<iostream>
 5 #include<ctime>
 6 using namespace std;
 7 inline int read(){
 8     int ans=0,f=1;char chr=getchar();
 9     while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();}
10     while(isdigit(chr)) {ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
11     return ans*f;
12 }const int M=1e5+5;
13 struct P{int a,b;}a[M];
14 int n,rk[M],p[M];
15 int v[M];
16 bool operator <(const P &x,const P &y){return x.a<y.a;}
17 int main(){
18     n=read();
19     for(int i=1;i<=n;++i) a[i].a=read(),a[i].b=read();
20     sort(a+1,a+n+1);
21     for(int i=1;i<=n;i++) rk[i]=a[i].a,a[i].a=i;
22     int pos1=min(a[1].b+1,n-a[1].b);
23     p[pos1]=a[1].a;
24     v[pos1]=1;
25     for(int i=2;i<=n;i++){
26         int ff=0;
27         int x=a[i].a,y=a[i].b;
28         for(int j=1;j<=n;j++){
29             if(v[j]) continue;
30             int cnt1=0;
31             for(int k=1;k<j;k++) if(!v[k]) ++cnt1;
32             int cnt2=n-i-cnt1;
33             if(cnt1==y||cnt2==y){
34                 v[j]=1;
35                 p[j]=i;
36                 ff=1;
37                 break;
38             }
39         }
40         if(!ff){
41             puts("impossible");
42             return 0;
43         }
44     }
45     for(int i=1;i<=n;i++){
46         cout<<rk[p[i]]<<" ";
47     }
48     return 0;
49 }

View Code

本来打算优化成$n^2logn$的，然而死活调不出来...

然而出来大家都说T2打了$n^2$的暴力...还有初二、初三的神仙用线段树、平衡树切掉了...

正解：

　　bztMinamoto和Sinner的做法是平衡树...然鹅平衡树暂时只是入了个门...先不考虑这个算法了

　　确实可以用线段树做...思路也和我想的一样...然而这个做法把我$n^3$中的$n^2$优化成了$logn$%%%

　　思路是一样的，就是每次把第i个小的数字***去的时候直接在更新线段树的时候搞...

 1 #pragma GCC optimize(3)
 2 #pragma GCC optimize("Ofast")
 3 #include<cstdio>
 4 #include<iostream>
 5 #include<cstring>
 6 #include<algorithm>
 7 #define writeln(x)  write(x),puts("")
 8 #define writep(x)   write(x),putchar(' ')
 9 using namespace std;
10 inline int read(){
11     int ans=0,f=1;char chr=getchar();
12     while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();}
13     while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
14     return ans*f;
15 }void write(int x){
16     if(x<0) putchar('-'),x=-x;
17     if(x>9) write(x/10);
18     putchar(x%10+'0');
19 }const int M=1e5+5;
20 int n,rk[M],s[M<<2],L[M<<2],R[M<<2]; 
21 struct P{int a,b;}a[M];
22 bool operator <(const P &x,const P &y){return x.a<y.a;}
23 #define ls (i<<1)
24 #define rs (i<<1|1)
25 #define mid (l+r>>1)
26 void Build(int i,int l,int r){
27     s[i]=r-l+1;L[i]=l,R[i]=r;
28     if(l==r) return;
29     Build(ls,l,mid),Build(rs,mid+1,r);
30 }
31 void Insert(int i,int k,int h){
32     --s[i];
33     if(L[i]==R[i])    return (void)(rk[L[i]]=h);
34     if(s[ls]>=k) Insert(ls,k,h);
35     else Insert(rs,k-s[ls],h);
36 }
37 int main(){
38     n=read();
39     for(int i=1;i<=n;++i)    a[i].a=read(),a[i].b=read();
40     sort(a+1,a+n+1),Build(1,1,n);
41     for(int i=1;i<=n;++i){
42         if(a[i].b>n-i){puts("impossible");return 0;}
43         int pos=a[i].b+1;
44         pos=min(pos,n-a[i].b-i+1);
45         Insert(1,pos,a[i].a);
46     }
47     for(int i=1;i<=n;++i) writep(rk[i]);
48     return 0;
49 }