NOIP2017普及组解题报告非官方 本文关键词：解题，普及，报告，NOIP2017
NOIP2017普及组解题报告非官方 本文简介：NOIP2017普及组解题报告-by郑佳睿1.成绩(score.cpp/c/pas)【问题描述】牛牛最近学习了C++入门课程，这门课程的总成绩计算方法是：总成绩=作业成绩×20%+小测成绩×30%+期末考试成绩×50%牛牛想知道，这门课程自己最终能得到多少分。【输入格式】输入文件只有1行，包含三个非
NOIP2017普及组解题报告非官方 本文内容：
NOIP2017普及组解题报告-by
郑佳睿
1.
成绩(score.cpp/c/pas)
【问题描述】
牛牛最近学习了
C++入门课程，这门课程的总成绩计算方法是：
总成绩
=
作业成绩
×
20%
+
小测成绩
×
30%
+
期末考试成绩
×
50%
牛牛想知道，这门课程自己最终能得到多少分。
【输入格式】
输入文件只有
1
行，包含三个非负整数A、B、C，分别表示牛牛的作业成绩、小测
成绩和期末考试成绩。相邻两个数之间用一个空格隔开，三项成绩满分都是
100
分。
【输入样例1】
100
100
80
【输出样例1】
90
【输入样例2】
60
90
80
【输出样例2】
79
【数据说明】
30%
的数据，A
=
B
=
0。
对于另外
30%
的数据，A
=
B
=
100。
对于
100%
的数据，
0
≤
A、B、C
≤
100
且
A、B、C
都是
10
的整数倍。
【题解】
超级水题，输入数据都是10的倍数，不用考虑浮点的问题，直接输出答案。
【代码】
#include
using
namespace
std;
int
a,b,c;
int
main(){
cin>>a>>b>>c;
cout
using
namespace
std;
int
n,q,a[1005];
int
main(){
cin>>n>>q;
for(int
i=0;i>a[i];
for(int
j=0;j>len>>code;
for(int
i=1;i
using
namespace
std;
struct
node{
int
x,y,c,can,v;
//格点状态：坐标、临时颜色、能否用魔法、花费
}cur;
int
n,m,ans;
int
a[105][105],f[105][105];//a为输入
f存储每格最小花费
queue
q;
void
expand(int
x,int
y){
//该函数作用是扩展一个格点
int
v;
if((xm)||(ym))
return;
//越界忽略
if(a[x][y]!=-1){
//固有颜色花0个或1个金币
v=(a[x][y]==cur.c)?cur.v:cur.v+1;
if(v>m>>n;
memset(a,255,sizeof(a));//-1空格
0红色
1黄色
memset(f,127,sizeof(f));//初值为0x7f7f7f7f
for(int
i=0;i>x>>y>>c;
a[x][y]=c;
}
f[1][1]=0;
q.push((node){1,1,a[1][1],1,0});
while(!q.empty()){
//广搜
cur=q.front();q.pop();
expand(cur.x-1,cur.y);
expand(cur.x+1,cur.y);
expand(cur.x,cur.y-1);
expand(cur.x,cur.y+1);
}
if(f[m][m]=K，整体的复杂度为O(nlog(Gmax))，时间上满足题目的约定。
【代码】
#include
using
namespace
std;
struct
node{
//单调队列的元素x为和起点的距离
int
x,v;
//
v为x距离格的最大得分
}
q[500005];
int
n,d,k;
int
x[500005],s[500005],f[500005];
//x
s数组为每格的距离和分值
int
check(int
g){
//f为状态数组，第i格的最大得分
int
qmin=d-g,qmax=d+g;
//qmin和qmax是最小和最大跳跃距离
int
head=0,tail=-1,cur=0;
//head,tail为单调队列的首尾指针
if(qminqmax))
head++;
//距离超过qmax的删除
f[i]=(head=k)
return
1;
//已达到要求的得分返回True
}
return
0;
//直到所有格子计算完毕也无法得到要求的得分，返回false
}
int
main(){
cin>>n>>d>>k;
for(int
i=1;i>x[i]>>s[i];
//输入数据已按x[i]从小到大排序，无需再排序
int
l=0,r=x[n],ans=-1;
//在0到x[n]范围内二分
int
m=(l+r)/2;
//二分的标准程序
for(l;l<=r;m=(l+r)/2)
if(check(m))
r=m-1,ans=m;
else
l=m+1;
cout<
//输出答案，
//所有都不满足时，ans没被赋值，原值为-1
}