noip2017普及组复赛解题报告.pdf

《noip2017普及组复赛解题报告.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、noip2017普及组解题报告*仅代表个人看法算法丌一定最优更多解题方法请移步洛谷等网站*byNANA_FinalT1成绩模拟水题不解释#includeusingnamespacestd;inta,b,c;intmain(){cin>>a>>b>>c;cout<<(a/10)*2+(b/10)*3+(c/10)*5;return0;}T2图书管理员模拟数据太弱所以直接暴力就能过比较部分也可以用截取字符串的方式#include#includeusingnamespacestd;inti,

2、j,k,n,q,m,ans,a[1001];intmain(){cin>>n>>q;for(i=1;i<=n;i++)cin>>a[i];for(i=1;i<=q;i++){cin>>m>>k;ans=10000001;for(j=1;j<=n;j++)if(a[j]%int(pow(10,m)+0.5)==k&&a[j]

3、000001)ans=-1;cout<usingnamespacestd;intm,n,xx,yy,i,j,chess[101][101],f[101][101];voiddfs(intx,inty,intlen,booluseMagic,intcolor){//(x,y)表示当前准备去的位置，len到上一步为止消耗的金币数（丌含上一个点到（x,y)这一

4、步所需的金币数）//useMagic表示上一个点是否使用了魔法，color表示上一个点的颜色（包括被魔法染色后的颜色）if(x<0

5、

6、x>m

7、

8、y<0

9、

10、y>m)return;//如果（x，y）是无色的，而且魔法上一个点用了魔法，就走丌到（x，y）这个点if(chess[x][y]==-1&&useMagic==true)return;//如果（x，y）是无色的，而且上一个点没用魔法，就用魔法到（x，y）if(chess[x][y]==-1&&useMagic==false){len+=2;//增加魔法开销useMagic=true;//c

11、olor默认染色成上一个点的颜色}//如果（x，y）有色，就可以到（x，y）if(chess[x][y]!=-1){len+=(color==chess[x][y])?0:1;//增加魔法开销useMagic=false;color=chess[x][y];}//剪枝if(f[x][y]==-1

12、

13、len

14、ic,color);dfs(x,y+1,len,useMagic,color);}intmain(){cin>>m>>n;//chess存储棋盘颜色用-1代表无色for(i=1;i<=m;i++)for(j=1;j<=m;j++)chess[i][j]=-1;//f[i][j]表示从点（1,1）到点（i,j)所需要的最少金币数for(i=1;i<=m;i++)for(j=1;j<=m;j++)f[i][j]=-1;for(i=1;i<=n;i++){cin>>xx>>yy;cin>>chess[xx][yy];}dfs(1,1,0,fals

15、e,chess[1][1]);cout<

16、）然后对这张新图做最短路，求出点（1,1）到其他所有有颜色点的最短路最后如果（m,m）有颜色，（1,1）到（m,m）之间的距离就是最短路否则需要借助跳板（m,m-1)或(m-1,