NOIP2019 pj备战计划-4

Task:pj试炼场2-4(续)

T4 P1309

对于这道题,首先明白一点:快排不行!

只有60分!

每次需要更新的值,都是相邻两个人变化后的分数;而相邻的分数,有些是不会改变位置的,而快速排序则是每次全部修改,必然会造成浪费。

那就试试归并吧,它挺适合这道题,因为每次比赛后胜者组与败者组构成的数组还是有序的,只要修改相邻区间即可

先尝试一下

黑科技

把sort改成stable_sort(stable_sort()可以对数组里的某个成员进行排序,而且可保证相等元素的原本相对次序在排序后保持不变)

80pts!

众所周知,STL慢,那么就来手写一波

归并的思想就是利用指针合并两个同序数组,每次比较两个指针所指的值,更小/大的放在temp数组中,然后在原数组中删掉它,指针往后移

代码实现也比较easy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void s(int left,int right)
{
if(lfet==right)return;//不符合
int i=left;//数组内的指针
int mid=(left+right)/2;//也有二分思想
int j=mid+1;//数组内的指针
int now=left;//指针
s(left,mid);//先内部排个序
s(mid+1,right);//两边同序才行
while(i<=mid&&j<=right)
{
if(a[i]>a[j])tmp[++now]=a[++i];//选大的放进去
else tmp[++now]=a[++j];
}
while(i<=mid)tmp[++now]=a[++i];
while(j<=right)tmp[++now]=a[++j];//没放进去的放进去
for(int k=left;k<=right;k++)a[k]=tmp[k];//tmp内排序完毕,传回去
}

那么放到这道题里

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
45
#include<bits/stdc++.h>
#define maxx 2000005
using namespace std;
int n,r,q;
int v[maxx],l[maxx],num[maxx];
int qaq,qwq,now;
struct node
{
int pow,pt;
}p[maxx];
bool cmp(int i,int j)
{
if(p[i].pt==p[j].pt)return i<j;
return p[i].pt>p[j].pt;
}
void s()
{
int i,j;
i=j=1,now=0;
while(i<=qaq&&j<=qwq)
if(cmp(v[i],l[j]))num[++now]=v[i++];
else num[++now]=l[j++];
while(i<=qaq)num[++now]=v[i++];
while(j<=qwq)num[++now]=l[j++];
}
int main()
{
cin>>n>>r>>q;
n*=2;
for(int i=1;i<=n;i++)num[i]=i;
for(int i=1;i<=n;i++)cin>>p[i].pt;
for(int i=1;i<=n;i++)cin>>p[i].pow;
sort(num+1,num+n+1,cmp);
while(r--)
{
qaq=qwq=0;
for(int i=1;i<=n;i+=2)
if(p[num[i]].pow>p[num[i+1]].pow)
v[++qaq]=num[i],l[++qwq]=num[i+1],p[num[i]].pt++;
else
v[++qaq]=num[i+1],l[++qwq]=num[i],p[num[i+1]].pt++;
s();
}
cout<<num[q]<<endl;
}

Task pj试炼场2-5

T1 P1603

世界上不是没有水题,而是缺少发现水题的眼睛。—-yyy 2015-06-25 17:15 于此题题解

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
#include<bits/stdc++.h>
using namespace std;
string dic[25]={" ","one","two","three","four","five","six","seven",
"eight","nine","ten","eleven","twelve","thirteen","fourteen","fifteen",
"sixteen","seventeen""eighteen","nineeen","twenty"};
string s;
priority_queue<int,vector<int>,greater<int> > q;
int main()
{
while(cin>>s&&s!=".")
{
bool flag=0;
for(int i=1;i<=20;i++)
{
if(s==dic[i])
{
q.push(i*i%100);
flag=1;
}
}
if(!flag)
{
if(s=="a"||s=="first"||s=="another")q.push(1);
else
if(s=="second"||s=="both")q.push(4);
else
if(s=="third")q.push(9);
}
}
bool is_first=0;
while(q.size())
{
int n=q.top();
if(!is_first&&n!=0)
{
cout<<n;
is_first=1;
}
else printf("%02d",n);
q.pop();
}
if(!is_first)puts("0");
}

翻了圈题解,我的已经挺短了,但优先队列已经有人写过了

T2 P1071

还比较简单,用STL的map写起来会快很多

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
#include<bits/stdc++.h>
using namespace std;
map<char,char>map1,map2;
char s1[105],s2[105],ans[105];
int len;
int sum;
int main() {
cin>>s1>>s2>>ans;
if(strlen(s1)!=strlen(s2)||strlen(s1)<26)
{
cout<<"Failed\n";
return 0;
}
len=strlen(s1);
for(int i=0; i<len; i++)
if(map1[s1[i]]==0&&map2[s2[i]]==0)
map1[s1[i]]=s2[i],map2[s2[i]]=s1[i],sum++;
else if(map1[s1[i]]!=s2[i]||map2[s2[i]]!=s1[i])
{
cout<<"Failed\n";
return 0;
}
if(sum<26)
{
cout<<"Failed\n";
return 0;
}
for(int i=0; i<strlen(ans); i++)
{
cout<<map1[ans[i]];
}
cout<<endl;
}

T3 P1012

大爱STL!

玄学一遍过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
bool cmp(string a,string b)
{
return b+a<a+b;
}
int main()
{
string a[25];
int t;
cin>>t;
for(int i=0;i<t;i++)cin>>a[i];
sort(a,a+t,cmp);
for(int i=0;i<t;i++)cout<<a[i];
}

T4 P1538

一道毒瘤题,很烦,但是只要想到分块处理就行了,就像电梯里的数字显示器一样,有没有都用0/1表示并打印即可

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
45
46
47
#include<bits/stdc++.h>
using namespace std;
string n;
char ans[1000][1000];
void pa(int place,int size,bool top,bool _top,bool top_,bool middle,bool _bottom,bool bottom_,bool bottom)
{
for(int i=place;i<=place+size+2;i++)
for(int j=0;j<=size*2+3;j++)
ans[j][i]=' ';
for(int i=place+1;i<=place+size;i++)
{
if(top)ans[0][i]='-';
if(middle)ans[size+1][i]='-';
if(bottom)ans[2*size+2][i]='-';
}
for(int i=1;i<=size;i++)
{
if(_top)ans[i][place]='|';
if(top_)ans[i][place+size+1]='|';
}
for(int i=size+2;i<=2*size+1;i++)
{
if(_bottom)ans[i][place]='|';
if(bottom_)ans[i][place+size+1]='|';
}
}
int main()
{
int k,p=0;
string s;
cin>>k>>s;
for(int i=0;i<s.length();i++)
{
if(s[i]=='0')pa(p,k,1,1,1,0,1,1,1);
if(s[i]=='1')pa(p,k,0,0,1,0,0,1,0);
if(s[i]=='2')pa(p,k,1,0,1,1,1,0,1);
if(s[i]=='3')pa(p,k,1,0,1,1,0,1,1);
if(s[i]=='4')pa(p,k,0,1,1,1,0,1,0);
if(s[i]=='5')pa(p,k,1,1,0,1,0,1,1);
if(s[i]=='6')pa(p,k,1,1,0,1,1,1,1);
if(s[i]=='7')pa(p,k,1,0,1,0,0,1,0);
if(s[i]=='8')pa(p,k,1,1,1,1,1,1,1);
if(s[i]=='9')pa(p,k,1,1,1,1,0,1,1);
p+=k+3;
}
for(int i=0;i<=2*k+2;i++)cout<<ans[i]<<endl;
}//这段代码不知怎么回事放上去的时候排版乱了