NOIP2019 pj备战计划-1

由于去年翻车了,今年要加倍努力,可能比完就AFO了

新开了个小号刷洛谷

妖孽皇

Task:pj试炼场2-1

T1 P1003

没什么好说的,水题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
int n,x,y,ans=-1;
struct node
{
int a,b,c,d;
}p[100000];
int main()
{
cin>>n;
for(int i=0;i<n;i++)
cin>>p[i].a>>p[i].b>>p[i].c>>p[i].d;
cin>>x>>y;
for(int i=0;i<n;i++)
if(x>=p[i].a&&x<=p[i].a+p[i].c&&y>=p[i].b&&y<=p[i].b+p[i].d)
ans=i+1;
cout<<ans<<endl;
}

T2 P1067

有点复杂的模拟

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>
using namespace std;
int n,a;
int main()
{
cin>>n;
cin>>a;
if(a!=1&&a!=-1)
cout<<a<<"x^"<<n;
else
{
if(a==1)
cout<<"x^"<<n;
else
{
if(a==-1)
cout<<"-x^"<<n;
}

}
for(int i=n-1;i>1;i--)
{
cin>>a;
if(a==0)
continue;
else
{
if(a==1)
cout<<"+x^"<<i;
else
{
if(a==-1)
cout<<"-x^"<<i;
else
{
if(a>0)
cout<<"+"<<a<<"x^"<<i;
else
{
cout<<a<<"x^"<<i;
}
}
}
}
}
cin>>a;
if(a!=0)
{
if(a==1)
cout<<"+x";
else
{
if(a==-1)
cout<<"-x";
else
{
if(a>0)
cout<<"+"<<a<<"x";
else
{
if(a<0)
cout<<a<<"x";
}
}
}
}
cin>>a;
if(a==0)
cout<<endl;
else
{
if(a>0)
cout<<"+"<<a<<endl;
else
{
cout<<a<<endl;
}
}
}

细节上wa了一次,需注意

T3 P1540

心血来潮写了个更好码的,用stl.vector实现

本来还想写题解结果发现很久以前就被memset0大大给写掉了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
vector<int> q;
int n,m,a,ans;
int main()
{
cin>>n>>m;
for(int i=0;i<m;i++)
{
cin>>a;
if(find(q.begin(),q.end(),a)==q.end())//找不到此单词
{
ans++;//查词典
q.push_back(a);//加入库
}
if(q.size()>n)//满了
q.erase(q.begin());//删词
}
cout<<ans<<endl;
}

T4 P1056

一道贪心,比较好想

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
#include<bits/stdc++.h>
using namespace std;
int m,n,k,l,d,aa,bb,cc,dd;
struct node
{
int gekai,weizi;
};
node x[1100],y[1100];
bool cmp(node a,node b)
{
return a.gekai>b.gekai;
}
bool CMP(node a,node b)
{
return a.weizi<b.weizi;
}
int main()
{
cin>>m>>n>>k>>l>>d;
while(d--)
{
cin>>aa>>bb>>cc>>dd;
if(bb==dd)
{
int o=min(aa,cc);
x[o].weizi=o;
x[o].gekai++;
}
else
{
int o=min(bb,dd);
y[o].weizi=o;
y[o].gekai++;
}
}
sort(x+1,x+m+1,cmp);
sort(y+1,y+n+1,cmp);
sort(x+1,x+k+1,CMP);
sort(y+1,y+l+1,CMP);
for(int i=1;i<=k;i++)
cout<<x[i].weizi<<" ";
cout<<endl;
for(int i=1;i<=l;i++)
cout<<y[i].weizi<<" ";
cout<<endl;
}

其中x表示一条竖着的通道,位子就是比较小的横坐标,隔开来存储能够有多少效益,贪心用

y同理

看样例解释很重要!不是普通的平面直角坐标系呀!x和y反过来的!de了很久的bug

T5 P1328

模拟水题,以前可能暴力代码就上了,但现在觉得肯定是预处理一下好写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
int n,n1,n2;
int ans1,ans2;
int a[205],b[205];
int point[10][10]={{0,0,1,1,0},{1,0,0,1,0},{0,1,0,0,1},{0,0,1,0,1},{1,1,0,0,0}};
int main()
{
cin>>n>>n1>>n2;
for(int i=0;i<n1;i++)
cin>>a[i];
for(int i=0;i<n2;i++)
cin>>b[i];
for(int i=0;i<n;i++)
{
int A=a[i%n1];
int B=b[i%n2];
ans1+=point[A][B];
ans2+=point[B][A];
}
cout<<ans1<<" "<<ans2<<endl;
}

踩了一个坑,要从0开始存,不然会在%的时候炸掉

T6 P1563

现在才知道这张毒瘤图片是哪里来的了233

水模拟,注意读入按逆时针就行了

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
#include<bits/stdc++.h>
using namespace std;
struct node
{
int num,dir;
string name;
}p[100005];
int n,m,a,b,ans;
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>p[i].dir>>p[i].name;
p[i].num=i;
}
for(int i=0;i<m;i++)
{
ans=(ans+n)%n;
cin>>a>>b;
if(a==0)
{
if(p[ans].dir==0)
ans-=b;
else
ans+=b;
}
else
{
if(p[ans].dir==0)
ans+=b;
else
ans-=b;
}
ans=(ans+n)%n;
}
cout<<p[ans].name<<endl;
}

Task: pj试炼场2-2

T1 P1023

一道阅读理解题。。。看了半个小时才看懂

其实本质就是列不等式,求解集

不等式都要求使政府预算的那个价格的总利润大于其他价位的总利润

for example:

1
2
3
4
(31-28+x)*110>=(28-28+x)*130
(31-28+x)*110>=(29-28+x)*125
(31-28+x)*110>=(30-28+x)*120
(31-28+x)*110>=(32-28+x)*95

根据题目条件,求绝对值最小的x,解出解集后就好办了

1
2
3
4
min>max=> no solution
max<0 => max
min>0 => min
解集中有0 =>0
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 cb,qi,x,y,a,tmp;
double maxx=10000000,minn=-10000000;
int pr[110000];
double ans;
int main()
{
cin>>qi>>x>>y;
cb=x;
while(x!=-1&&y!=-1)
{
pr[x]=y;
for(int i=tmp+1;i<x;i++)
pr[i]=pr[i-1]+(y-pr[tmp])/(x-tmp);
tmp=x;
cin>>x>>y;
}
cin>>a;
while(pr[tmp]>a)
{
tmp++;
pr[tmp]=pr[tmp-1]-a;
}
for(int j=cb;j<=tmp;j++)
{
double ans=1.0*(pr[qi]*(qi-cb)-pr[j]*(j-cb))/(pr[j]-pr[qi]);
if(pr[j]>pr[qi])maxx=min(maxx,ans);
else minn=max(minn,ans);
}
if(minn>maxx)cout<<"NO SOLUTION\n";
else
{
if(minn>0)cout<<ceil(minn);
else
{
if(maxx<0)cout<<floor(maxx);
else
{
cout<<"0\n";
}
}
}
}

T2 P1031

不用想很多用贪心的思路做不会有问题

处理当前的一堆,如果和平均数一样就当它不存在

不然就从下一堆增减

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
int n,p[1000],ave,ans;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>p[i];
ave+=p[i];
}
ave/=n;
for(int i=1;i<=n;i++)
{
if(p[i]!=ave)
{
p[i+1]=p[i+1]+p[i]-ave;
ans++;
}
}
cout<<ans<<endl;
}

T3 P1042

直接模拟即可,水题

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
48
49
50
#include<bits/stdc++.h>
using namespace std;
int main()
{
int w1=0;
int l1=0;
int w2=0;
int l2=0;
int i=0;
int f[100000][2];
memset(f,0,sizeof(f));
char a;
while(cin>>a&&a!='E')
{
if(a=='W')
{
w1++;
w2++;
}
else
{
if(a=='L')
{
l1++;
l2++;
}
}
if((w1>=11||l1>=11)&&(abs(w1-l1)>=2))
{
cout<<w1<<":"<<l1<<endl;
w1=0;
l1=0;
}
if((w2>=21||l2>=21)&&(abs(w2-l2)>=2))
{
f[i][1]=w2;
f[i][2]=l2;
w2=0;
l2=0;
i++;
}
}
cout<<w1<<":"<<l1<<endl;
cout<<endl;
for(int j=0;j<i;j++)
{
cout<<f[j][1]<<":"<<f[j][2]<<endl;
}
cout<<w2<<":"<<l2<<endl;
}