当前位置:首页 >> 学科竞赛 >>

NOIP2014 提高组参赛总结 by yv


yv,让世界更邪恶

NOIP2014 提高组参赛总结
yvbbrjdr
11 月 7 日中午,我们从苏州出发前往南京航空航天大学。有点紧张又蛮轻 松,后座的人在玩狼人,车上充满了快活的空气。 到了学校以后, 按照熟悉的惯例报了到发了秩序册和参赛证, 然后前往宿舍。 这次我们还是悲催地住在了老宿舍里面,条件十分艰苦。 这次准考证号太奇怪,和

秩序册上的不一样,本来高高兴兴地拿到一个 JS286(80286) ,被改成了 JS-280。没错我就是苏州工业园区星海实验中学的周 远。 晚上和室友们玩玩,看看书写写程序就这么度过去了。 Day1 南京下起了小雨,我早上六点多就起了,把自己整理好然后叫醒了室友。一 起吃完了早饭就赶往高耸入云的一号教学楼。 进去之后测试环境,我的机器无法调试(好像没有机器可以调试) ,然后就 换到了一个装了 Dev-C++ 5.3.0.2 的机器上,等待开始考试。试题在开考前五 分钟发下来了。 1. rps 【问题描述】 石头剪刀布是常见的猜拳游戏:石头胜剪刀,剪刀胜布,布胜石头。如果两 个人出拳一样,则不分胜负。在《生活大爆炸》第二季第 8 集中出现了一种石头 剪刀布的升级版游戏。 升级版游戏在传统的石头剪刀布游戏的基础上,增加了两 个新手势: 斯波克: 《星际迷航》主角之一。 蜥蜴人: 《星际迷航》中的反面角色。 这五种手势的胜负关系如表一所示,表中列出的是甲对乙的游戏结果。 表一 石头剪刀布升级版胜负关系
乙 甲对乙的 甲 结果 剪刀 石头 布 蜥蜴人 斯波克
1

剪刀

石头



蜥蜴人

斯波克



输 平

赢 输 平

赢 赢 输 平

输 输 赢 赢 平

yv,让世界更邪恶

现在, 小 A 和小 B 尝试玩这种升级版的猜拳游戏。 已知他们的出拳都是有周 期性规律的,但周期长度不一定相等。例如:如果小 A 以“石头-布-石头-剪刀蜥蜴人-斯波克”长度为 6 的周期出拳,那么他的出拳序列就是“石头-布-石头剪刀-蜥蜴人-斯波克-石头-布-石头-剪刀-蜥蜴人-斯波克-……”,而如果小 B 以 “剪刀-石头-布-斯波克-蜥蜴人”长度为 5 的周期出拳,那么他出拳的序列就是 “剪刀-石头-布-斯波克-蜥蜴人-剪刀-石头-布-斯波克-蜥蜴人-……” 已知小 A 和小 B 一共进行 N 次猜拳。每一次赢的人得 1 分,输的得 0 分; 平局两人都得 0 分。现请你统计 N 次猜拳结束之后两人的得分。 【输入】 输入文件名为 rps.in。 第一行包含三个整数:N,NA,NB,分 别 表 示 共 进 行 N 次猜拳、小 A 出拳的周期长度,小 B 出拳的周期长度。数与数之间以一个空格分隔。 第二行包含 NA 个整数,表示小 A 出拳的规律,第三行包含 NB 个整数,表 示小 B 出拳的规律。其中,0 表示“剪刀”,1 表示“石头”,2 表示“布”,3 表示 “蜥蜴人”, 4 表示“斯波克”。数与数之间以一个空格分隔。 【输出】 输出文件名为 rps.out。 输出一行, 包含两个整数, 以一个空格分隔, 分别表示小 A、 小 B 的得分。 【输入输出样例 1】 rps.in 10 5 6 0 1 2 3 4 0 3 4 2 1 0 【输入输出样例 2】 rps.in 9 5 5 0 1 2 3 4 1 0 3 2 4

rps.out 6 2

rps.out 4 4

【数据说明】 对于 100%的数据,0 < N ≤ 200,0 < NA



200, 0 < NB



200。

【解题报告】 看到数据范围的第一反应, 水题……甚至都不用去算 LCM, 直接纯模拟就行了。 我是这么做的,开一个打表的数组 win[5][5],win[i][j]代表甲出 i,乙出 j 时 甲 的 胜 负 情 况 。 win[i][j]=1 代 表 甲 胜 , win[i][j]=0 代 表 平 手 , win[i][j]=-1 代表甲输。这个表要打 25 行…然后就简单了,用 mod 来处理回 合 到 序 列 的 转 换 , 然 后 如 果 win[a[i%ta]][b[i%tb]=1 就 ++ 甲 ,
2

yv,让世界更邪恶

win[a[i%ta]][b[i%tb]=-1 就++乙,最后输出就行了。水题不能手抖啊,表不 要打错啊… 【我的代码】 #include <iostream> #include <cstdio> using namespace std; int n,na,nb,a[210],b[210],win[10][10],xa=0,xb=0; int main() { freopen("rps.in","r",stdin); freopen("rps.out","w",stdout); win[0][0]=0; win[0][1]=-1; win[0][2]=1; win[0][3]=1; win[0][4]=-1; win[1][0]=1; win[1][1]=0; win[1][2]=-1; win[1][3]=1; win[1][4]=-1; win[2][0]=-1; win[2][1]=1; win[2][2]=0; win[2][3]=-1; win[2][4]=1; win[3][0]=-1; win[3][1]=-1; win[3][2]=1; win[3][3]=0; win[3][4]=1; win[4][0]=1; win[4][1]=1; win[4][2]=-1; win[4][3]=-1; win[4][4]=0; scanf("%d%d%d",&n,&na,&nb); for (int i=0;i<na;++i) scanf("%d",a+i); for (int i=0;i<nb;++i) scanf("%d",b+i); for (int i=0;i<n;++i)
3

yv,让世界更邪恶

if (win[a[i%na]][b[i%nb]]==1) ++xa; else if (win[a[i%na]][b[i%nb]]==-1) ++xb; printf("%d %d\n",xa,xb); return 0; } 2. link 【问题描述】 无向连通图 G 有 n 个点,n-1 条边。点从 1 到 n 依次编号,编号为 i 的点 的权值为 Wi ,每条边的长度均为 1。图上两点(u, v)的距离定义为 u 点到 v 点的最短距离。对于图 G 上的点对(u, v),若它们的距离为 2,则它们之间会产 生 Wu×Wv 的联合权值。 请问图 G 上所有可产生联合权值的有序点对中,联合权值最大的是多少? 所有联合权值之和是多少? 【输入】 输入文件名为 link.in。 第一行包含 1 个整数 n。 接下来 n-1 行,每行包含 2 个用空格隔开的正整数 u、v,表示编号为 u 和 编号为 v 的点之间有边相连。 最后 1 行,包含 n 个正整数,每两个正整数之间用一个空格隔开,其中第 i 个整数表示图 G 上编号为 i 的点的权值为 Wi。 【输出】 输出文件名为 link.out。 输出共 1 行,包含 2 个整数,之间用一个空格隔开,依次为图 G 上联合权值 的最大值和所有联合权值之和。 由于所有联合权值之和可能很大,输出它时要对 10007 取余。 【输入输出样例】 link.in 5 1 2 2 3 3 4 4 5 1 5 2 3 10 【样例说明】

link.out 20 74

4

yv,让世界更邪恶

本例输入的图如上所示,距离为 2 的有序点对有(1,3)、(2,4)、(3,1)、 (3,5)、(4,2)、(5,3)。其联合权值分别为 2、15、2、20、15、20。其中最大 的是 20,总和为 74。 【数据说明】 对于 30%的数据,1<≤100; 对于 60%的数据,1<≤2000; 对于 100%的数据,1<≤200,000,0<Wi ≤10,000。 【解题报告】 这道题目朴素的算法是对每个点 DFS 两层,O(n^2),然后就悲剧。初步分 析问题后可以知道, 联合权值产生的那两个点距离为二,也就是说它们中间有第 三个点隔着,那么就简单了。建好树(要用无向邻接表) ,对整棵树进行 BFS, 搜到的点作为中间的那个点,然后穷举当前节点的所有儿子,计算两两的联合权 值,加到 sum 里面去(注意 mod) ,然后更新 max(注意不要 mod) 。但这样子还 是 O(n^2) , 问 题 出 在 穷 举 儿 子 上 。 我 们 要 算 的 权 值 实 际 上 是 a1*a2+a1*a3+…+a1*an+a2*a1+a2*a3+…+a2*an 以此类推。因式分解之后发现 就是 sum(a)^2-a1^2-a2^2-…-an^2。这样不需要两两相乘了,直接在找儿子的 时候在 sum 上做减法(sum=(sum-(ai*ai)%m+m)%m) (注意 mod) ,并把当前儿 子节点权值加到临时 sum 里面去。最后算 sum=(sum+(sum(a)*sum(a))%m)%m 就行了。 在穷举儿子的时候还要找到儿子的最大值和次大值, 因为 max 只可能是 儿子的最大值乘上次大值。更新一下 max(注意不要 mod) 。我在做的时候更新 次大值有一个 bug,但是没有影响分数,呵呵。关于时间复杂度,由于只有一个 BFS,所以就是 O(m+n),通过极限数据绰绰有余。最后发现连 BFS 都不需要, 直接一个 for 穷举中间的点就行了。 【我的代码】 #include <iostream> #include <cstdio> #include <vector> #include <queue> #include <algorithm> using namespace std;
5

yv,让世界更邪恶

int n,w[200010],fa[200010]={},res=0,m=0; vector<int>ljb[200010]; void bfs(int start) { queue<int>que; que.push(start); fa[start]=0; while (!que.empty()) { int tt=que.front(); que.pop(); int allkids=0,biggest=0,second=0; for (int i=0;i<ljb[tt].size();++i) if (ljb[tt][i]!=fa[tt]) { que.push(ljb[tt][i]); fa[ljb[tt][i]]=tt; res=(res+((w[ljb[tt][i]]*w[fa[tt]])<<1))%10007; m=max(m,w[ljb[tt][i]]*w[fa[tt]]); allkids=(allkids+w[ljb[tt][i]])%10007; res=((resw[ljb[tt][i]]*w[ljb[tt][i]])%10007+10007)%10007; if (w[ljb[tt][i]]>biggest) { second=biggest; biggest=w[ljb[tt][i]]; } else if (w[ljb[tt][i]]>second) second=w[ljb[tt][i]]; } m=max(m,biggest*second); res=(res+allkids*allkids)%10007; } } int main() { freopen("link.in","r",stdin); freopen("link.out","w",stdout); scanf("%d",&n); for (int i=0;i<n-1;++i) { int a,b; scanf("%d%d",&a,&b); ljb[a].push_back(b); ljb[b].push_back(a); } for (int i=1;i<=n;++i)
6

yv,让世界更邪恶

scanf("%d",w+i); bfs(1); printf("%d %d\n",m,res); return 0; } 3. bird 【问题描述】 Flappy Bird 是一款风靡一时的休闲手机游 戏。玩家需要不断控制点击手机屏幕的频率来调节小 鸟的飞行高度,让小鸟顺利通过画面右方的管道缝 隙。如果小鸟一不小心撞到了水管或者掉在地上的 话,便宣告失败。 为了简化问题,我们对游戏规则进行了简化和改 编: 1. 游戏界面是一个长为 n, 高 为 m 的二维平面, 其中有 k 个管道(忽略管道的宽度) 。 2. 小鸟始终在游戏界面内移动。小鸟从游戏界 面最左边任意整数高度位置出发,到达游戏界面最右边时,游戏完成。 3. 小鸟每个单位时间沿横坐标方向右移的距离为 1,竖直移动的距离由玩 家控制。 如果点击屏幕, 小鸟就会上升一定高度 X, 每个单位时间可以点 击多次,效果叠加;如果不点击屏幕,小鸟就会下降一定高度 Y。小鸟位 于横坐标方向不同位置时, 上升的高度 X 和下降的高度 Y 可能互不相同。 4. 小鸟高度等于 0 或者小鸟碰到管道时,游 戏 失 败 。小 鸟 高 度 为 m 时,无法再上升。 现在, 请你判断是否可以完成游戏。 如果可以, 输出最少点击屏幕数; 否则, 输出小鸟 最多可以通过多少个管道缝隙。 【输入】 输入文件名为 bird.in。 第 1 行有 3 个整数 n,m,k,分别表示游戏界面的长度,高度和水管的数 量,每两个整数之间用一个空格隔开; 接下来的 n 行,每行 2 个用一个空格隔开的整数 X 和 Y,依次表示在横坐标 位置 0~n-1 上玩家点击屏幕后, 小鸟在下一位置上升的高度 X, 以及在这个位置 上玩家不点击屏幕时,小鸟在下一位置下降的高度 Y。 接下来 k 行,每行 3 个整数 P,L,H,每两个整数之间用一个空格隔开。每 行表示一个管道,其中 P 表示管道的横坐标,L 表示此管道缝隙的下边沿高度为 L,H 表示管道缝隙上边沿的高度(输入数据保证 P 各不相同,但不保证按照大 小顺序给出) 。 【输出】
7

yv,让世界更邪恶

输出文件名为 bird.out。 共两行。 第一行,包含一个整数,如果可以成功完成游戏,则输出 1,否则输出 0。 第二行,包含一个整数,如果第一行为 1,则输出成功完成游戏需要最少点 击屏幕数,否则,输出小鸟最多可以通过多少个管道缝隙。 【输入输出样例 1】 bird.in 10 10 6 3 9 9 9 1 2 1 3 1 2 1 1 2 1 2 1 1 6 2 2 1 2 7 5 1 5 6 3 5 7 5 8 8 7 9 9 1 3 【输入输出样例 2】 bird.in 10 10 4 1 2 3 1 2 2 1 8 1 8 3 2 2 1 2 1 2 2 1 2 1 0 2 6 7 9 9 1 4 3 8 10
8

bird.out 1 6

bird.out 0 3

yv,让世界更邪恶

【输入输出样例说明】 如下图所示,蓝色直线表示小鸟的飞行轨迹,红色直线表示管道。

【数据范围】 对于 30%的数据:5≤n≤10,5≤m≤10,k=0,保证存在一组最优解使得同一单 位时间最多点击屏幕 3 次; 对于 50%的数据:5≤n≤20,5≤m≤10,保证存在一组最优解使得同一单位时 间最多点击屏幕 3 次; 对于 70%的数据:5≤n≤1000,5≤m≤100; 对于 100%的数据: 5≤n≤10000, 5≤m≤1000, 0≤k<n, 0<X<m, 0<Y<m, 0<P<n, 0≤L<H ≤m,L+1<H。 【解题报告】 本次竞赛最奇葩的一道题目来了,是风靡全球的 Flappy Bird。而且还把 这个游戏改得面目全非…这道题目我只拿了 70 分,因为只写出来了 O(n*m^2)的 动归算法,也只能过 70%的点啊…幸运的是这个算法是对的所以没有出小错误。 我不知道怎么去优化这个东西,就把我的思路说一下吧。 首先做一个优化,处理管道的时候假设每排都有管道,而如果没有管道,那 么下管道高度就是 0,上管道高度就是 m+1,用两个数组来保存:topbound[i] 表示第 i 列上管道高度,botbound[i]表示第 i 列下管道高度,注意一下初始 化就行了。 规 定 dp[i][j] 为 小 鸟 飞 到 (i,j) 要 点 击 的 最 少 次 数 , 则 显 然 dp[0][j]=0(1<=j<=m) 。 对 于 每 一 个 i , 只 要 更 新 dp[i][j](botbound[i]+1<=j<=topbound[i]-1)就行了,想一想为什么。这 个状态可以从 dp[i-1][k](botbound[i-1]+1<=k<=topbound[i-1]-1) 转移 到,要注意点击次数和是否是整数。特别地,如果 j=m 也就是说顶端,那么从各 个 dp[i-1][k]都可以转移到,注意一下点击次数就行了。最后看,如果可以到 达最后一列,那么就把最后一列最小值输出来,如果不能到达,就统计一下能到 达的那一列之前(不包括这一列)有多少管道就行了。总之这个动归不是很难, 但是复杂度很高啊…… 【我的代码】 #include <iostream>
9

yv,让世界更邪恶

#include <cstdio> #include <algorithm> #define oo 0x3fffffff using namespace std; int n,m,k,dp[10010][1010],u[10010],d[10010],topbound[10010],botbou nd[10010],res=+oo; bool havepipe[10010]={}; bool notallinf(int c) { for (int i=1;i<=m;++i) if (dp[c][i]!=+oo) return 1; return 0; } int main() { freopen("bird.in","r",stdin); freopen("bird.out","w",stdout); scanf("%d%d%d",&n,&m,&k); for (int i=0;i<=n;++i) { if (i) for (int j=0;j<1002;++j) dp[i][j]=+oo; else for (int j=m+1;j<1002;++j) dp[i][j]=+oo; topbound[i]=m+1; botbound[i]=0; } for (int i=1;i<=n;++i) scanf("%d%d",u+i,d+i); for (int i=0;i<k;++i) { int p,l,h; scanf("%d%d%d",&p,&l,&h); havepipe[p]=1; botbound[p]=l; topbound[p]=h; } for (int i=1;i<=n;++i) for (int j=botbound[i]+1;j<=topbound[i]-1;++j) { dp[i][j]=dp[i-1][j+d[i]]; for (int k=botbound[i-1]+1;k<=topbound[i-1]-1;++k)
10

yv,让世界更邪恶

if (k<j&&(j-k)%u[i]==0) dp[i][j]=min(dp[i][j],dp[i-1][k]+(j-k)/u[i]); else if (k<=j&&((j-k)%u[i]||j-k==0)&&j==m) dp[i][j]=min(dp[i][j],dp[i-1][k]+(j-k)/u[i]+1); else if (k>j) break; } for (int i=1;i<=m;++i) res=min(res,dp[n][i]); if (res!=+oo) printf("1\n%d\n",res); else { int nai=n-1; for (;nai>0;--nai) if (notallinf(nai)) break; res=0; for (int i=0;i<nai;++i) if (havepipe[i]) ++res; printf("0\n%d\n",res); } return 0; } 第一天就这样结束了,没有一题有多难。估计自己能拿到 270 分,结果拿到 成绩真的是 270 分…玩了一下午啊哈哈哈哈哈,晚上老师请我们去了“南航人家” 吃饭。觉得第一天的题目不难,感觉第二天有可能会难,就又看了一会儿书。 Day2 今天早晨起得稍晚,不过也准时到机房楼下了。有点紧张。 进考场之后,老师好心地发了一个 Dev-C++ 5.3.0.2 给所有人,终于不用 换机器了。 1. wireless 【问题描述】 随着智能手机的日益普及, 人们对无线网的需求日益增大。某城市决定对城 市内的公共场所覆盖无线网。 假设该城市的布局为由严格平行的 129 条东西向街道和 129 条南北向街道 所形成的网格状,并且相邻的平行街道之间的距离都是恒定值 1。东西向街道从 北到南依次编号为 0,1,2…128,南北向街道从西到东依次编号为 0,1,2…128。 东西向街道和南北向街道相交形成路口,规定编号为 x 的南北向街道和编
11

yv,让世界更邪恶

号为 y 的东西向街道形成的路口的坐标是(x, y) 。 在 某 些 路 口 存 在 一 定 数 量 的 公 共 场 所 。 由于政府财政问题, 只能安装一个大型无线网络发射器。该无线网络发射器 的传播范围是一个以该点为中心, 边长为 2*d 的正方形。 传播范围包括正方形边 界。 例如下图是一个 d = 1 的无线网络发射器的覆盖范围示意图。

现在政府有关部门准备安装一个传播参数为 d 的无线网络发射器,希望你 帮助他们在城市内找出合适的安装地点,使得覆盖的公共场所最多。 【输入】 输入文件名为 wireless.in。 第一行包含一个整数 d,表示无线网络发射器的传播距离。 第二行包含一个整数 n,表示有公共场所的路口数目。 接下来 n 行,每行给出三个整数 x, y, k, 中间用一个空格隔开,分别代 表路口的坐标(x, y)以及该路口公共场所的数量。同一坐标只会给出一次。 【输出】 输出文件名为 wireless.out。 输出一行,包含两个整数,用一个空格隔开,分别表示能覆盖最多公共场所 的安装地点方案数,以及能覆盖的最多公共场所的数量。 【输入输出样例】 wireless.in 1 2 4 4 10 6 6 20

wireless.out 1 30

【数据说明】 对于 100%的数据,1 ≤ d ≤ 20,1 ≤ n ≤ ≤ 128, 0 < k ≤ 1,000,000。

20, 0 ≤ x ≤ 128, 0 ≤ y

【解题报告】 刚看到这个题目,没看数据范围,感觉蛮难的,要考虑边界啊什么的,所以
12

yv,让世界更邪恶

先做第二题了。 做完回过头来瞥到范围,什么破玩意儿嘛直接开大数组穷举时间 都够的。由于这道题是测试你会不会编程的,就像 Day1 第一题一样,这个我就 不讲了。 【我的代码】 #include <cstdio> int d,n,m[150][150]={},res1,res2=-1; int main() { freopen("wireless.in","r",stdin); freopen("wireless.out","w",stdout); scanf("%d%d",&d,&n); for (int i=0;i<n;++i) { int x,y,k; scanf("%d%d%d",&x,&y,&k); m[x][y]=k; } for (int i=0;i<=128;++i) for (int j=0;j<=128;++j) { int t=0; for (int k=i-d;k<=i+d;++k) for (int l=j-d;l<=j+d;++l) if (k>=0&&k<=128&&l>=0&&l<=128) t+=m[k][l]; if (res2<t) { res1=1; res2=t; } else if (res2==t) ++res1; } printf("%d %d\n",res1,res2); return 0; } 2. road 【问题描述】 在有向图 G 中,每条边的长度均为 1,现给定起点和终点,请你在图中找一 条从起点到终点的路径,该路径满足以下条件: 1.路径上的所有点的出边所指向的点都直接或间接与终点连通。 2.在满足条件 1 的情况下使路径最短。 注意:图 G 中可能存在重边和自环,题目保证终点没有出边。 请你输出符合条件的路径的长度。
13

yv,让世界更邪恶

【输入】 输入文件名为 road.in。 第一行有两个用一个空格隔开的整数 n 和 m,表示图有 n 个点和 m 条边。 接下来的 m 行每行 2 个整数 x、y,之间用一个空格隔开,表示有一条边从 点 x 指向点 y。 最后一行有两个用一个空格隔开的整数 s、t,表示起点为 s,终点为 t。 【输出】 输出文件名为 road.out。 输出只有一行,包含一个整数,表示满足题目描述的最短路径的长度。如果 这样的路径不存在,输出-1。 【输入输出样例 1】 road.in 3 2 1 2 2 1 1 3

road.out -1

【输入输出样例说明】

如上图所示,箭头表示有向道路,圆点表示城市。起点 1 与终点 3 不连通, 所以满足题目描述的路径不存在,故输出-1。 【输入输出样例 2】 road.in

road.out

14

yv,让世界更邪恶

6 1 1 2 2 4 3 1

6 2 3 6 5 5 4 5

3

【输入输出样例说明】

如上图所示, 满足条件的路径为 1->3->4->5。 注意点 2 不能在答案路径中, 因为点 2 连了一条边到点 6,而点 6 不与终点 5 连通。 【数据说明】 对于 30%的数据,0< n ≤10,0< m ≤20; 对于 60%的数据,0< n ≤100,0< m ≤2000; 对于 100%的数据,0< n ≤10,000,0< m ≤200,000,0< x,y,s,t≤n, x≠t。 【解题报告】 刚说到我第一个做的题目就是这个, 而且一眼就看出做法了…又是一个水题。 先把所有边反向, 从目标点开始做一次 floodfill, 没有访问到的点就是不能直 接或者间接达到目标点的点,所以它们连着的点(注意! )都不能作为路径上的 点。去掉这些点建一个新图再从原点 bfs 一下就能求出最短路了。连边权都没 有,数据这么少,也真够水的…
15

yv,让世界更邪恶

【我的代码】 #include <cstdio> #include <vector> #include <queue> #include <cstring> using namespace std; int n,m,s,t; bool vis[10010]={},oktoadd[10010]={}; vector<int>ljb1[10010],ljb2[10010],ljb3[10010]; void floodfill(int cur) { oktoadd[cur]=vis[cur]=1; for (int i=0;i<ljb2[cur].size();++i) if (!vis[ljb2[cur][i]]) floodfill(ljb2[cur][i]); } int bfs(int start) { int dist[10010]; dist[start]=0; memset(vis,0,sizeof(vis)); queue<int>que; vis[start]=1; que.push(start); while (!que.empty()) { int tt=que.front(); que.pop(); if (tt==t) return dist[t]; for (int i=0;i<ljb3[tt].size();++i) if (!vis[ljb3[tt][i]]) { vis[ljb3[tt][i]]=1; dist[ljb3[tt][i]]=dist[tt]+1; que.push(ljb3[tt][i]); } } return -1; } int main() { freopen("road.in","r",stdin); freopen("road.out","w",stdout); scanf("%d%d",&n,&m);
16

yv,让世界更邪恶

for (int i=0;i<m;++i) { int x,y; scanf("%d%d",&x,&y); ljb1[x].push_back(y); ljb2[y].push_back(x); } scanf("%d%d",&s,&t); floodfill(t); for (int i=1;i<=n;++i) if (!vis[i]) for (int j=0;j<ljb2[i].size();++j) oktoadd[ljb2[i][j]]=0; for (int i=1;i<=n;++i) if (oktoadd[i]) for (int j=0;j<ljb1[i].size();++j) if (oktoadd[ljb1[i][j]]) ljb3[i].push_back(ljb1[i][j]); printf("%d\n",bfs(s)); return 0; } 3. equation 【问题描述】 已知多项式方程:

求这个方程在[1, m]内的整数解(n 和 m 均为正整数) 。 【输入】 输入文件名为 equation.in。 输入共 n+2 行。 第一行包含 2 个整数 n、m,每两个整数之间用一个空格隔开。 接下来的 n+1 行每行包含一个整数,依次为 a0,a1,a2,……,an。 【输出】 输出文件名为 equation.out。 第一行输出方程在[1, m]内的整数解的个数。 接下来每行一个整数,按照从小到大的顺序依次输出方程在[1, m]内的一 个整数解。 【输入输出样例 1】 equation.in
17

equation.out

yv,让世界更邪恶

2 10 1 -2 1

1 1

【输入输出样例 2】 equation.in 2 10 2 -3 1

equation.out 2 1 2

【输入输出样例 3】 equation.in 2 10 1 3 2

equation.out 0

【数据说明】 对于 30%的数据,0<n≤2,|ai|≤100,an≠0,m≤100; 对于 50%的数据,0<n≤100,|ai|≤10100,an≠0,m≤100; 对于 70%的数据,0<n≤100,|ai|≤1010000,an≠0,m≤10000; 对于 100%的数据,0<n≤100,|ai|≤1010000,an≠0,m≤1000000。 【解题报告】 什么破玩意儿, 为什么写了高精度还作了秦九韶、 快速乘优化, 只拿了 30 分, 估计还是 T 掉了。我用的是朴素算法写的。就算不写高精度这个 30 分也是很好 拿啊…听说这道题目要模大素数?我们学校的一个大神用的是求 n 次导。 【我的代码】 #include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <algorithm> using namespace std; struct bign { int num[10010],len; bool positive;
18

yv,让世界更邪恶

bign() { memset(num,0,sizeof(num)); len=0; positive=1; } bign operator=(const char* s) { if (*s=='-') { positive=0; ++s; } len=strlen(s); for (int i=0,j=len-1;i<len;++i,--j) num[i]=s[j]-'0'; return *this; } friend bign operator+(bign a,bign b) { bign t; if (a.positive==0&&b.positive==0) { a.positive=b.positive=1; t=a+b; t.positive=0; return t; } if (a.positive==0&&b.positive==1) swap(a,b); if (a.positive==1&&b.positive==0) { b.positive=1; return a-b; } t.len=max(a.len,b.len); for (int i=0;i<t.len;++i) { t.num[i]+=a.num[i]+b.num[i]; t.num[i+1]+=t.num[i]/10; t.num[i]%=10; } if (t.num[t.len]) ++t.len; return t; } friend bign operator-(bign a,bign b) { bign t; if (a<b) { t.positive=0; swap(a,b);
19

yv,让世界更邪恶

} t.len=a.len; for (int i=0;i<t.len;++i) t.num[i]=a.num[i]-b.num[i]; for (int i=0;i<t.len;++i) while (t.num[i]<0) { t.num[i]+=10; --t.num[i+1]; } while (t.len>=0&&(!t.num[t.len])) --t.len; ++t.len; return t; } friend bign operator*(bign a,int b) { bign res; for (;b;b>>=1) { if (b&1) res=res+a; a=a+a; } return res; } friend bool operator<(bign a,bign b) { if (a.len!=b.len) return a.len<b.len; for (int i=a.len-1;i>=0;--i) if (a.num[i]!=b.num[i]) return a.num[i]<b.num[i]; } bool operator==(int n) {return len==0;} }; typedef bign real; int n,m; real a[110]; vector<int>res; real check(int x) { real z=a[n]; for (int i=n-1;i>=0;--i) { z=z*x; z=z+a[i];
20

yv,让世界更邪恶

} return z; } int main() { freopen("equation.in","r",stdin); freopen("equation.out","w",stdout); scanf("%d%d",&n,&m); for (int i=0;i<=n;++i) { char s[10010]; scanf("%s",s); a[i]=s; } for (int i=1;i<=m;++i) if (check(i)==0) res.push_back(i); printf("%d\n",res.size()); for (int i=0;i<res.size();++i) printf("%d\n",res[i]); return 0; } 感觉写了蛮多东西了,就在这里总结一下吧。 这次题目偏简单,是我们都没有想到的,所以这次考试不是考的谁会得多, 而是考谁出错少。我拿了 500 分,这个成绩我还是比较满意的,就是最后一题只 拿了 30 分感到有点不可思议。我也只拿到了江苏省 40 名左右,听说我在浙江 省只有 100 名,但是拿到国家一等奖还是蛮高兴的。在 NOIP 吧里面看到很多人 说“题目太简单了,我原来可以可以 AK 的,但是粗心掉 200 分”这种嘴巴 AK。 简单题目都会粗心, 那么难题目怎么可能做得好?去年的国一线是 300 多, 而今 年要 400 多。我们学校很多人拿了 300 多,就差一点点有些可惜。 而我要说的不是这些, 我想把我们训练的情况说说。 这次我们一共训练了三 个星期左右,每天晚上都要在学校训练到 9 点,周末也是一样。到最后我还停了 四个下午的课。我们每天要刷掉一套试题(周末三套) 。很累,没得休息,但是 真的是累并快乐着。所有人说说笑笑,无聊了就 MC 一会儿,还一起出去吃饭。 那段日子过得真幸福。 以后不会有这种共同训练的日子了,它将永远地留存在我 们的记忆里。 以后我们都会记得我们曾经一起奋斗 OI 的时光, 都会记得那些 “脑 残”的小伙伴们。 大家都辛苦了,也祝大家好运。

21


相关文章:
NOIP2014提高组第二试题解
NOIP2014提高组第二试题解_IT认证_资格考试/认证_教育专区。NOIP2014提高组第二试题解 1.无线网络发射器选址只需在读入数据时对每个场所将其能接触到 WIFI 信号...
NOIP2014信息学奥赛全国联赛提高组参考答案
NOIP2014信息学奥赛全国联赛提高组参考答案_学科竞赛_高中教育_教育专区。NOIP2014信息学奥赛全国联赛提高组参考答案第二十届全国青少年信息学奥林匹克联赛初赛 提高组参...
NOIP2014提高组复赛试题
CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day1 1.生活大爆炸版石头剪刀布 (rps.cpp/c/pas) 【问题描述】 石头剪刀布是常见的猜拳游戏:石头胜剪刀,...
NOIP2014提高组复赛试题
CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day1 (请选手务必仔细阅读本页内容)一.题目概况 中文题目名称 英文题目与子目录名 可执行文件名 输入文件名 ...
2012十八届noip提高组题目及答案
每一级 比赛的优胜 者晋级上一 级比赛 5.如里不在快速排序中引入随机化,有...Noip 2013 提高组 Day2 ... 14页 免费©2014 Baidu 使用百度前必读 | 文库...
Noip2014初赛提高组C试题及答案(完整版)
Noip2014初赛提高组C试题及答案(完整版)_IT认证_资格考试/认证_教育专区。Noip2014 初赛提高组试题及答案(完整版) 提高组 C 语言试题 一、单项选择题(每题 1.5...
NOIP(2014)第二十届全国青少年信息学奥林匹克联赛初赛试题及答案(提高组试题及答案PASCAL)
NOIP(2014)第二十届全国青少年信息学奥林匹克联赛初赛试题及答案(提高组试题及答案PASCAL)_学科竞赛_高中教育_教育专区。NOIP(2014)第二十届全国青少年信息学奥林...
NOIP2014提高组第一试题解
NOIP2014 提高组第一试题解【第一题】石头剪刀布 rps 【题目大意】 a 和 b 石头剪刀布游戏,每个人一共有五种方式,相互之间的胜负关系给出,a 和 b 出拳的...
NOIP(2014)第二十届全国青少年信息学奥林匹克联赛初赛试题及答案(提高组PASCAL)
NOIP(2014)第二十届全国青少年信息学奥林匹克联赛初赛试题及答案(提高组PASCAL)_学科竞赛_高中教育_教育专区。NOIP(2014)第二十届全国青少年信息学奥林匹克联赛初赛试...
NOIP2014 提高组模拟试题(一试)
NOIP2014 提高组模拟试题(一试)_学科竞赛_高中教育_教育专区。1. 宿舍 (a.cpp/c/pas) 【题目描述】 某日,某宿舍 n 名同学为了抢厕所里的 m 个蹲位争执起...
更多相关标签:
noip2016提高组复赛 | noip2015提高组复赛 | noip2015提高组初赛 | noip2016提高组初赛 | noip2014提高组复赛 | noip2016提高组 | noip2010提高组复赛 | noip2016提高组查分 |