NOIP2019 pj备战计划-3

欢迎收看秒切系列!

Task:pj试炼场2-3

T1 P1177

也许你一看这道题,就会说:sort一波搞定!水炸了!大不了优先队列喽

1
2
3
4
5
6
7
8
9
10
11
#include<bits/stdc++.h>
using namespace std;
int a[100010];
int n;
int main()
{
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
sort(a,a+n);
for(int i=0;i<n;i++)cout<<a[i]<<" ";
}

过了!

不过,好心的出题人还说了这么一句话

C++选手请不要试图使用STL,虽然你可以使用sort一遍过,但是你并没有掌握快速排序算法的精髓。

好吧,手写快排。。。试一下吧

由于算法简单不常用,本人也熟悉,放几张丁爸的PPT完事

1.JPG

2.JPG

3.JPG

4.JPG

5.JPG

6.JPG

虽然在能用STL的比赛里没人会手写这玩意

噗,加了快读快输还是3个TLE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
using namespace std;
int a[100010];
int n;
int i,j,s;
int read()
{
int w=1,q=0;char ch=' ';
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
return w*q;
}
int write(int x)
{
int s[20],top=0;
while(x){s[++top]=x%10;x/=10;}
if(!top)s[++top]=0;
while(top)putchar(s[top--]+'0');
putchar(' ');
}
void Sort(int left,int right)
{
if(left>=right)return;
s=a[left];
i=left,j=right;
while(i!=j)
{
while(a[j]>=s&&i<j)j--;
while(a[i]<=s&&i<j)i++;
if(i<j)swap(a[i],a[j]);
}
a[left]=a[i];
a[i]=s;
Sort(left,i-1);
Sort(i+1,right);

}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)a[i]=read();
Sort(1,n);
for(int i=1;i<=n;i++)write(a[i]);
}

看来传统快排是不行了

那就来几个小优化?

多次试验后,我是这么做的:

1.把swap换成手写赋值(STL慢啊)

2.随机化(玄学)

3.加入一些插入排序(这个是看题解的)

额。。。还是T了一个点

辣么。。。

二分?

其实就是把基准数定在中间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
using namespace std;
int a[100010];
int n;
int i,j,s,tmp,ra;
int read()
{
int w=1,q=0;char ch=' ';
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
return w*q;
}
int write(int x)
{
int s[20],top=0;
while(x){s[++top]=x%10;x/=10;}
if(!top)s[++top]=0;
while(top)putchar(s[top--]+'0');
putchar(' ');
}
void Sort(int left,int right)
{
i=left,j=right;
s=a[(left+right)/2];
while(i<=j)
{
while(a[j]>s)j--;
while(a[i]<s)i++;
if(i<=j)tmp=a[i],a[i]=a[j],a[j]=tmp,i++,j--;
}
if(left<j)Sort(left,j);
if(i<right)Sort(i,right);

}
int main()
{
n=read();
for(int i=0;i<n;i++)a[i]=read();
Sort(0,n-1);
for(int i=0;i<n;i++)write(a[i]);
}

T2 P1059

红题,水,set自带去重和排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
set<int> s;
int n,a;
int main()
{
cin>>n;
while(n--)
{
cin>>a;
s.insert(a);
}
cout<<s.size()<<endl;
while(s.size())
{
cout<<*s.begin()<<" ";
s.erase(s.begin());
}
}

T3 P1068

还是水题,结构体排序即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
using namespace std;
struct node
{
int number,score;
}p[5005];
bool cmp(node x,node y)
{
if(x.score!=y.score)return x.score>y.score;
else return x.number<y.number;
}
int main()
{
int a,b;
cin>>a>>b;
for(int i=0;i<a;i++)cin>>p[i].number>>p[i].score;
int m=floor(b*1.5);
sort(p,p+a,cmp);
int S=p[m-1].score;
int sum=0;
for(int i=0;i<a;i++)
if(p[i].score>=S)sum++;
else break;
cout<<S<<" "<<sum<<endl;
for(int i=0;i<a;i++)
if(p[i].score>=S)cout<<p[i].number<<" "<<p[i].score<<endl;
else break;
}

T4 P1781

还是水题,坑点只有票数很大,用字符串就ok了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
string point,maxx=" ";
int n,ans;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>point;
if(point.size()>maxx.size()||(point.size()==maxx.size()&&point>maxx))
{
maxx=point;
ans=i;
}
}
cout<<ans<<endl;
cout<<maxx<<endl;
}

Task:pj试炼场2-4

T1 P1583

不想说

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
int e[10];
struct node
{
int w,num,val;
}p[20000];
bool cmp1(node x,node y)
{
if(x.w!=y.w)return x.w>y.w;
else return x.num<y.num;
}
bool cmp2(node x,node y)
{
if(x.val!=y.val)return x.val>y.val;
else return x.num<y.num;
}
int main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=10;i++)cin>>e[i];
for(int i=1;i<=n;i++)
{
cin>>p[i].w;
p[i].num=i;
}
sort(p+1,p+n+1,cmp1);
for(int i=1;i<=n;i++)p[i].val=p[i].w+e[(i-1)%10+1];
sort(p+1,p+n+1,cmp2);
for(int i=1;i<=k;i++)cout<<p[i].num<<" ";
}

T2 P1051

水题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;
struct node
{
string name;
int qimo,banji,lunwen,num;
char ganbu,xibu;
int score;
}p[105];
bool cmp(node a,node b)
{
if(a.score!=b.score)
return a.score>b.score;
else
return a.num<b.num;
}
int n,sum;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>p[i].name>>p[i].qimo>>p[i].banji>>p[i].ganbu>>p[i].xibu>>p[i].lunwen;
p[i].num=i;
if(p[i].qimo>80&&p[i].lunwen>=1)p[i].score+=8000;
if(p[i].qimo>85&&p[i].banji>80)p[i].score+=4000;
if(p[i].qimo>90)p[i].score+=2000;
if(p[i].qimo>85&&p[i].xibu=='Y')p[i].score+=1000;
if(p[i].banji>80&&p[i].ganbu=='Y')p[i].score+=850;
}
sort(p+1,p+n+1,cmp);
cout<<p[1].name<<endl<<p[1].score<<endl;
for(int i=1;i<=n;i++)sum+=p[i].score;
cout<<sum<<endl;
}

T3 P1093

还是用来练练手的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace std;
struct node
{
int a,b,c,d,e;
}stu[305];
bool cmp(node a,node b)
{
if(a.e!=b.e)return a.e>b.e;
if(a.a!=b.a)return a.a>b.a;
return a.d<b.d;
}
int main()
{
int t;
cin>>t;
for(int i=0;i<t;i++)
{
cin>>stu[i].a>>stu[i].b>>stu[i].c;
stu[i].e=stu[i].a+stu[i].b+stu[i].c;
stu[i].d=i+1;
}
sort(stu,stu+t,cmp);
for(int i=0;i<5;i++)cout<<stu[i].d<<" "<<stu[i].e<<endl;
}