Hints of sd0061(快排思想)

Hints of sd0061

Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 492 Accepted Submission(s): 106

Problem Description

sd0061, the legend of Beihang University ACM-ICPC Team, retired last year leaving a group of noobs. Noobs have no idea how to deal with

Input

There are multiple test cases (about

unsigned x = A, y = B, z = C;
unsigned rng61() {
  unsigned t;
  x ^= x << 16;
  x ^= x >> 5;
  x ^= x << 1;
  t = x;
  x = y;
  y = z;
  z = t ^ x ^ y;
  return z;
}

Output

For each test case, output "Case #" in one line (without quotes), where

Sample Input

3 3 1 1 1

0 1 2

2 2 2 2 2

1 1

Sample Output

Case #1: 1 1 202755

Case #2: 405510 405510

Source

2017 Multi-University Training Contest - Team 1

//题意: n,m,a,b,c abc为3个参数，用这些参数生成n个数，然后，求排好序后的 n 个数中，m 次查询，第 i 的数的值

//题解：这种数据下 10e7 ，不能直接用快排，就算快排，还是会超时，但是要利用快排的思想。因为 m 比较小，可以这样，每次快排结束后，前部分一定比分界值小或等，后半部分一定大或等，要查询第 k 大的数时，如果 k 在分界位置左边，就只排左边，在右就只排右，这样，每阶段快排省去一半区间，就行了，还wa了一发，很蛋疼，因为生成数据那部分不能直接用LL，只能用题目给的unsigned ，卡数据，很难玩那！

但是还是差点超时 2300ms ，评测机卡还有可能TLE，我擦，让我再想想怎么优化

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 using namespace std;
 5 #define LL long long
 6 #define MXN 10000005
 7 #define MXM 105
 8 
 9 int num[MXM];
10 LL prt[MXM];
11 LL data[MXN];
12 bool vis[MXN];
13 
14 int n,m;
15 unsigned x,y,z;
16 unsigned rng61(){
17   LL t;
18   x ^= x << 16;
19   x ^= x >> 5;
20   x ^= x << 1;
21   t = x;
22   x = y;
23   y = z;
24   z = t ^ x ^ y;
25   return z;
26 }
27 
28 void qk_sort(int l,int r,int k)
29 {
30     if (l>=r) return;
31     int a=l, b=r;
32     while (a<b)
33     {
34         while (a<b&&data[b]>=data[l]) b--;
35         while (a<b&&data[a]<=data[l]) a++;
36         swap(data[a],data[b]);
37     }
38     swap(data[l],data[a]);
39     vis[a]=1;
40     if (k==a) return;
41     if (k<a) qk_sort(l,a-1,k);
42     if (k>a) qk_sort(a+1,r,k);
43 }
44 
45 int main()
46 {
47     int cnt=1;
48     while (scanf("%d%d%u%u%u",&n,&m,&x,&y,&z)!=EOF)
49     {
50         for (int i=0;i<m;i++)
51             scanf("%d",&num[i]);
52         for (int i=0;i<n;i++)
53             data[i]=(LL)rng61();
54 
55         memset(vis,0,sizeof(vis));
56 
57         for (int i=0;i<m;i++)
58         {
59             int l =num[i],r=num[i];
60             while (l>=0&&vis[l]==0) l--;
61             l++;
62             while (r<n&&vis[r]==0) r++;
63             r--;
64             qk_sort(l,r,num[i]);
65             prt[i] = data[num[i]];
66         }
67         printf("Case #%d:",cnt++);
68         for (int i=0;i<m;i++)
69             printf(" %lld",prt[i]);
70         printf("
");
71     }
72     return 0;
73 }

View Code

STL 里面的 nth_element(arr,arr+x,arr+n);

可以将x在[0,n]范围内，将第x小的数字移动到arr[x]上，其余比arr[x]大的，在x后面，比arr[x]小的，在x前面。

1684 ms

STL 用得好省事多啊

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <algorithm>
 5 using namespace std;
 6 #define LL long long
 7 #define MXN 10000005
 8 #define MXM 105
 9 struct Node
10 {
11     int w;
12     int p;
13     bool operator <(const Node b) const
14     {
15         return w<b.w;
16     }
17 }num[MXM];
18 LL prt[MXM];
19 LL data[MXN];
20 bool vis[MXN];
21 
22 int n,m;
23 unsigned x,y,z;
24 unsigned rng61(){
25   LL t;
26   x ^= x << 16;
27   x ^= x >> 5;
28   x ^= x << 1;
29   t = x;
30   x = y;
31   y = z;
32   z = t ^ x ^ y;
33   return z;
34 }
35 
36 int main()
37 {
38     int cnt=1;
39     while (scanf("%d%d%u%u%u",&n,&m,&x,&y,&z)!=EOF)
40     {
41         for (int i=0;i<m;i++)
42         {
43             scanf("%d",&num[i].w);
44             num[i].p=i;
45         }
46         sort(num,num+m);
47 
48         for (int i=0;i<n;i++)
49             data[i]=(LL)rng61();
50 
51         memset(vis,0,sizeof(vis));
52 
53         for (int i=m-1;i>=0;i--)
54         {
55             if (i==m-1)
56                 nth_element(data,data+num[i].w,data+n);
57             else
58                 nth_element(data,data+num[i].w,data+num[i+1].w);
59             prt[num[i].p] = data[num[i].w];
60         }
61         printf("Case #%d:",cnt++);
62         for (int i=0;i<m;i++)
63             printf(" %lld",prt[i]);
64         printf("
");
65     }
66     return 0;
67 }

View Code