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

NOIP2015普及组复赛解题报告


NOIP2015 普及组解题报告
南京师范大学附属中学树人学校 CT 1. 金币(coin.cpp/c/pas) 【问题描述】 国王将金币作为工资,发放给忠诚的骑士。第一天,骑士收到一枚金 币;之后两天(第二天和第三天) ,每天收到两枚金币;之后三天(第 四、五、六天) ,每天收到三枚金币;之后四天(第七、八、九、十 天) ,每天收到四枚金币……;这种工资发放模式会一直这样延续下 去:当连续 N 天每天收到 N 枚金币后,骑士会在之后的连续 N+1 天 里,每天收到 N+1 枚金币。 请计算在前 K 天里,骑士一共获得了多少金币。 【输入格式】 输入文件名为 coin.in。 输入文件只有 1 行,包含一个正整数 K,表示发放金币的天数。 【输出格式】 输出文件名为 coin.out。 输出文件只有 1 行,包含一个正整数,即骑士收到的金币数。 【数据说明】 对于 100%的数据,1 ≤K ≤10,000。 【思路】 模拟 【时空复杂度】 O(k),O(1)

2、扫雷游戏(mine.cpp/c/pas) 【问题描述】 扫雷游戏是一款十分经典的单机小游戏。 在n行m列的雷区中有一些格 子含有地雷 (称之为地雷格) , 其他格子不含地雷 (称之为非地雷格) 。 玩家翻开一个非地雷格时, 该格将会出现一个数字——提示周围格子 中有多少个是地雷格。游戏的目标是在不翻出任何地雷格的条件下, 找出所有的非地雷格。 现在给出n行m列的雷区中的地雷分布, 要求计算出每个非地雷格周围 的地雷格数。 注:一个格子的周围格子包括其上、下、左、右、左上、右上、左下、 右下八个方向上与之直接相邻的格子。 【输入格式】 输入文件名为mine.in。 输入文件第一行是用一个空格隔开的两个整数n和m, 分别表示雷区的 行数和列数。 接下来n行, 每行m个字符, 描述了雷区中的地雷分布情况。 字符’*’ 表示相应格子是地雷格,字符’?’表示相应格子是非地雷格。相邻 字符之间无分隔符。 【输出格式】 输出文件名为mine.out。 输出文件包含n行,每行m个字符,描述整个雷区。用’*’表示地雷 格,用周围的地雷个数表示非地雷格。相邻字符之间无分隔符。 【数据说明】

对于 100%的数据,1≤n≤100,1≤m≤100。 【思路】 模拟 【技巧】 可将数组多开一圈,省去边界条件的判断。 【时空复杂度】 O(mn),O(mn)

3. 求和(sum.cpp/c/pas) 【问题描述】 一条狭长的纸带被均匀划分出了 n 个格子,格子编号从 1 到 n。每个 格子上都染了一种颜色 colori(用[1,m]当中的一个整数表示) ,并且 写了一个数字 numberi。 定义一种特殊的三元组:(x, y, z),其中 x,y,z 都代表纸带上格子的 编号,这里的三元组要求满足以下两个条件: 1. x, y, z 都是整数,x < y < z, y ? x = z ? y 2. colorx=colorz 满足上述条件的三元组的分数规定为(x+z)*(numberx+numberz)。整个 纸带的分数规定为所有满足条件的三元组的分数的和。 这个分数可能 会很大,你只要输出整个纸带的分数除以 10,007 所得的余数即可。 【输入格式】 输入文件名为 sum.in。 第一行是用一个空格隔开的两个正整数 n 和 m,n 代表纸带上格子的 个数,m 代表纸带上颜色的种类数。 第二行有 n 个用空格隔开的正整数,第 i 个数字 numberi 代表纸带上 编号为 i 的格子上面写的数字。 第三行有 m 个用空格隔开的正整数,第 i 个数字 colori 代表纸带上编 号为 i 的格子染的颜色。 【输出格式】 输出文件名为 sum.out。 共一行,一个整数,表示所求的纸带分数除以 10,007 所得的余数。

【数据说明】 对于第 1 组至第 2 组数据,1≤n≤100,1≤m≤5; 对于第 3 组至第 4 组数据,1≤n≤3000,1≤m≤100; 对于第 5 组至第 6 组数据,1≤n≤100000,1≤m≤100000,且不存在出现 次数超过 20 的颜色; 对于全部 10 组数据,1≤ n ≤ 100000, 1≤ m ≤ 100000, 1 ≤ colori ≤ m, 1 ≤ numberi ≤100000。 【思路】 先分析一下,我们的任务是什么。题目的要求是求分数和,我们就得 把所有符合条件的三元组“找”出来。 至少需要枚举三元组(x,y,z)中的一个元素,这里枚举的是 z(当然 x 也可以,不过不要选 y,因为 y 对分数没什么用) 。 1、因为 x<y<z,所以只需向前枚举 x,y 2、因为 y-x=z-y,所以 x+z=2y,x、z 同奇偶,且分数与 y 无关,只 需枚举 z 和 x。 3、因为 colourx=colourz,所以只需枚举 z 之前同奇偶且同色的 x。 这样的话时间复杂度是 O(n2),能得 40 分。如何快速枚举 x 呢? 其实不是快速枚举 x,是快速枚举分数和。 观察三元组分数: (x+z)·(numberx+numberz) 显然我们不方便处理多项式乘法,那就把它拆开 (事实上很多人到这步都放弃了,其实试一试立刻就明白了) =x·numberx+x·numberz+z·numberx+z·numberz

那么对于 z 的所有合法决策 x1,x2,??,xk 根据乘法分配率,分数=Σ (xi*numberxi)+Σ (xi)*numberz +Σ (numberxi) *z+Σ (z*numberz) (1<=i<=k) 由于 z 是枚举的,所以只需快速得到Σ (x·numberx),Σ x,Σ numberx 和 k(注意最后一项被算了 k 次,要乘 k) 这样我们就可以开 4 个累加器,分别记录这四个量。而对于不同奇偶 性、 不同颜色的 z 有不同的决策 x, 所以要开一个 s[2][m][4]的累加器。 【时空复杂度】 O(n),O(n+m) 【注意】题目数据较大,每次计算一定要模 10007, 否则很容易出错。 【样例程序】
#include <cstdio> const int maxn=100000; const int maxm=100000; const int p=10007; int n,m,ans; int number[maxn+1],colour[maxn+1]; int s[2][maxm+1][4]; void init() { freopen("sum.in","r",stdin); freopen("sum.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&number[i]); for(int i=1;i<=n;i++) scanf("%d",&colour[i]); } void solve() { for(int i=1;i<=n;i++)

{ int z=i%p,numz=number[i]%p,c=colour[i],t=i%2; int count=s[t][c][0]%=p,x=s[t][c][1]%=p, numx=s[t][c][2]%=p,x_numx=s[t][c][3]%=p; ans=(ans+((count*z)%p*numz)%p)%p; ans=(ans+x_numx)%p; ans=(ans+x*numz)%p; ans=(ans+z*numx)%p; s[t][c][0]++; s[t][c][1]+=z; s[t][c][2]+=numz; s[t][c][3]+=z*numz; } } void output() { printf("%d\n",ans); fclose(stdin); fclose(stdout); } int main() { init(); solve(); output(); return 0; }

4. 推销员(salesman.cpp/c/pas) 【问题描述】 阿明是一名推销员,他奉命到螺丝街推销他们公司的产品。螺丝街是 一条死胡同,出口与入口是同一个,街道的一侧是围墙,另一侧是住 户。螺丝街一共有 N 家住户,第 i 家住户到入口的距离为 Si 米。由于 同一栋房子里可以有多家住户,所以可能有多家住户与入口的距离相 等。阿明会从入口进入,依次向螺丝街的 X 家住户推销产品,然后再 原路走出去。 阿明每走 1 米就会积累 1 点疲劳值,向第 i 家住户推销产品会积累 Ai 点疲劳值。阿明是工作狂,他想知道,对于不同的 X,在不走多余的 路的前提下,他最多可以积累多少点疲劳值。 【输入格式】 输入文件名为 salesman.in。 第一行有一个正整数 N,表示螺丝街住户的数量。 接下来的一行有 N 个正整数,其中第 i 个整数 Si 表示第 i 家住户到入 口的距离。数据保证 S1≤S2≤…≤Sn<108。 接下来的一行有 N 个正整数,其中第 i 个整数 Ai 表示向第 i 户住户推 销产品会积累的疲劳值。数据保证 Ai<103。 【输出格式】 输出文件名为 salesman.out。 输出 N 行,每行一个正整数,第 i 行整数表示当 X=i 时,阿明最多积 累的疲劳值。 【数据说明】

对于 20%的数据,1≤N≤20; 对于 40%的数据,1≤N≤100; 对于 60%的数据,1≤N≤1000; 对于 100%的数据,1≤N≤100000。 【思路】 题目要求每一个 X 的情况,显然不能每个 X 专门推一遍,要充分利用 已知的 X 的情况,那么很可能会是 DP。 定义 f[i]为 X=i 时的最大疲劳值。 关键是怎么建立状态转移方程呢?考试时观察了两组样例数据,直觉 告诉我 f[i+1]的决策应该会包含 f[i]的决策(此处的决策指住户下标) 。 事实上也确实如此。 证明: 设 f[i]的决策为 k1,k2,??,ki(k1< k2<??< ki),f[i+1]的决策将 f[i]决策 中的 ks 换成 j 并增加了一个决策 ki+1, f[i+1]的决策 k 中最大的为 maxk。 f[i]=2*s[ki]+Σ a[kt](1<=t<=i) f[i+1]=2*s[maxk]+ Σ a[kt](1<=t<=s-1)+ Σ a[kt](s+1<=t<=i)+a[j]+a[ki+1] ∵2*s[maxk]+ Σ a[kt](1<=t<=s-1)+ Σ a[kt](s+1<=t<=i)+a[j]是 X=i 时的 一种决策的疲劳值(即决策为 k1,k2,??ks-1,ks+1,??ki,kj 时) ∴2*s[maxk]+ Σ a[kt](1<=t<=s-1)+ Σ a[kt](s+1<=t<=i)+a[j]<=f[i] ∴2*s[maxk]+ Σ a[kt](1<=t<=s-1)+ Σ a[kt](s+1<=t<=i)+a[j]+ a[ki+1] <=f[i]+ a[ki+1](即决策为 k1,k2,??,ks,??,ki,ki+1 时的疲劳值) 若小于,说明保留 ks 更优; 若等于, 对于两个目前疲劳值相等的决策序列 k, max{k}越小越好 (就

是说目前走的路程越短越好) ,因为在 max{k}左边的决策 l 只能增加 a[l] 的 疲 劳 值 , 而 对 于 max{k} 右 边 的 决 策 r 则 可 以 增 加 2*(s[r]-s[max{k}])+a[r],对于左边,max{k} 没有影响,而对于右边, max{k}越小,后面的 f[]增加疲劳值的空间越大。 根 据 以 上 原 则 , 虽 然 决 策 k1,k2, ? ? ,ks, ? ? ,ki 与 决 策 k1,k2, ? ? ks-1,ks+1,??ki,kj 疲劳值相等,但 f[i]选择了前者,说明前者更优。 综上,无论小于或等于,决策 k1,k2,??,ks,??,ki 都比决策 k1,k2,?? ks-1,ks+1,??ki,kj 更优。 ∴f[i+1]的最优决策一定包含了 f[i]的最优决策,证毕. 也就是说,对于 f[i],只需在 f[i-1]的基础上加一个最优决策就可以了。 易得出状态转移方程: f[i]=f[i-1]+max{max{a[k]|1<=k<maxi},max{2*(s[k]-s[maxi])+a[k]|maxi<k<=n}} 其中 k 表示待选决策(已经选过的不能再选) ,maxi 表示 f[i-1]的决策序列 中最大的一个决策。 解释一下:因为 maxi 左边的决策 k 不会增加距离,只增加推销的疲劳值 a[k];而 maxi 右边的决策 k 不仅会增加疲劳值,还会使距离从 s[maxi]增加 到 s[k],来回还要×2,也就是增加了 2*(s[k]-s[maxi])+a[k] 枚举 k 的话时间复杂度是 O(n2)的,只能得 60 分。 做到这里,优化已经很明显了。对于 maxi 的左边,我们需要动态求区间 a[k] 最值,无论是堆、线段树、优先级队列、集合,时间复杂度都是 log2n 级别 的;而对于 maxi 右边,由于所有决策疲劳值都要减去 s[maxi],所以我们只 要求区间 2*s[k]+a[k]的最值,而且可用决策必然是不断减少的,可以预处理 排个递减序, 每次找第一个合法决策。 当然, 左边的方法对于右边同样适用。

同时,如果选择了右边的决策 k,还需要将 maxi 到 k 之间的决策加入到左边 的待选决策中。 (因为它们的身份已经从右边的点变成了左边的点) 。 由于每个决策最多从右边出一次,从左边进一次、出一次,均摊时间复杂度 是 O(nlog2n),能得 100 分。 (可惜考试时多写了一个“]” ,编译错误,400 变成了 300) 【时空复杂度】 O(nlog2n),O(n)(取决于使用的数据结构) 【样例程序】 heap:
#include <cstdio> #include <algorithm> using namespace std; const int maxn=100000; int n; int s[maxn+1],a[maxn+1],f[maxn+1]; int left[maxn+1],right[maxn+1],l,r=1,maxi; bool cmpl(const int i,const int j) { if(a[i]!=a[j]) return a[i]<a[j]; else return i>j; } bool cmpr(const int i,const int j) { if(2*s[i]+a[i]!=2*s[j]+a[j]) return 2*s[i]+a[i]>2*s[j]+a[j]; else return i<j; } void init() {

freopen("salesman.in","r",stdin); freopen("salesman.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&s[i]); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); right[i]=i; } sort(right+1,right+n+1,cmpr); } void choose_left(const int i) { f[i]=f[i-1]+a[left[1]]; pop_heap(left+1,left+l--+1,cmpl); } void choose_right(const int i) { f[i]=f[i-1]+2*(s[right[r]]-s[maxi])+a[right[r]]; for(int i=maxi+1;i<right[r];i++) { left[++l]=i; push_heap(left+1,left+l+1,cmpl); } maxi=right[r++]; while(r<=n&&right[r]<=maxi) r++; } void solve() { for(int i=1;i<=n;i++) if(l==0) choose_right(i); else if(r>n) choose_left(i); else if(a[left[l]]>=2*(s[right[r]]-s[maxi])+a[right[r]]) choose_left(i); else choose_right(i); } void output()

{ for(int i=1;i<=n;i++) printf("%d\n",f[i]); fclose(stdin); fclose(stdout); } int main() { init(); solve(); output(); return 0; }

set:
#include <cstdio> #include <algorithm> using namespace std; const int maxn=100000; int n; int s[maxn+1],a[maxn+1],f[maxn+1]; int left[maxn+1],right[maxn+1],l,r=1,maxi; bool cmpl(const int i,const int j) { if(a[i]!=a[j]) return a[i]<a[j]; else return i>j; } bool cmpr(const int i,const int j) { if(2*s[i]+a[i]!=2*s[j]+a[j]) return 2*s[i]+a[i]>2*s[j]+a[j]; else return i<j; } void init() {

freopen("salesman.in","r",stdin); freopen("salesman.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&s[i]); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); right[i]=i; } sort(right+1,right+n+1,cmpr); } void choose_left(const int i) { f[i]=f[i-1]+a[left[1]]; pop_heap(left+1,left+l--+1,cmpl); } void choose_right(const int i) { f[i]=f[i-1]+2*(s[right[r]]-s[maxi])+a[right[r]]; for(int i=maxi+1;i<right[r];i++) { left[++l]=i; push_heap(left+1,left+l+1,cmpl); } maxi=right[r++]; while(r<=n&&right[r]<=maxi) r++; } void solve() { for(int i=1;i<=n;i++) if(l==0) choose_right(i); else if(r>n) choose_left(i); else if(a[left[l]]>=2*(s[right[r]]-s[maxi])+a[right[r]]) choose_left(i); else choose_right(i); } void output()

{ for(int i=1;i<=n;i++) printf("%d\n",f[i]); fclose(stdin); fclose(stdout); } int main() { init(); solve(); output(); return 0; }

priority_queue:
#include <cstdio> #include <queue> const int maxn=100000; using namespace std; int n; int s[maxn+1],a[maxn+1],f[maxn+1],maxi; class cmpl { public: bool operator()(const int i,const int j) { return a[i]<a[j]; } }; class cmpr { public: bool operator()(const int i,const int j) { if(2*s[i]+a[i]!=2*s[j]+a[j]) return 2*s[i]+a[i]<2*s[j]+a[j]; else return i>j; }

}; priority_queue<int,vector<int>,cmpl> left; priority_queue<int,vector<int>,cmpr> right; void init() { freopen("salesman.in","r",stdin); freopen("salesman.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&s[i]); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); right.push(i); } } void choose_left(const int i) { f[i]=f[i-1]+a[left.top()]; left.pop(); } void choose_right(const int i) { int r=right.top(); f[i]=f[i-1]+2*(s[r]-s[maxi])+a[r]; for(int i=maxi+1;i<r;i++) left.push(i); maxi=r; while(!right.empty()&&right.top()<=maxi) right.pop(); } void solve() { for(int i=1;i<=n;i++) if(left.empty()) choose_right(i); else if(right.empty()) choose_left(i); else { int l=left.top(),r=right.top();

if(l>=2*(s[r]-s[maxi])+a[r]) choose_left(i); else choose_right(i); } } void output() { for(int i=1;i<=n;i++) printf("%d\n",f[i]); fclose(stdin); fclose(stdout); } int main() { init(); solve(); output(); return 0; }

鉴于 set 和 priority_queue 属于 c++ STL,实现起来可能较宏观、容易,但效 率会略比 heap 低一些。自测时 heap 约 0.43s,set 约 0.7s,priority_queue 约 0.94s。


相关文章:
NOIP2015普及组解题报告.doc
NOIP2015 普及组解题报告 From 贴吧 id u007zzt 金币 国王将金币作为工资,发放...NOIP2015普及组复赛试题... 6页 1下载券 noip2015普及组解题报告 6页 2下载...
NOIP2015普及组复赛解题报告.doc
NOIP2015普及组复赛解题报告_学科竞赛_初中教育_教育专区。NOIP2015普及组复赛解题报告 NOIP2015 普及组解题报告南京师范大学附属中学树人学校 CT 1. 金币(coin.cpp/...
noip2015普及组题解最终.doc
noip2015 普及组题解 by 郁庭 from 宁波市镇海蛟川书院 2015
noip2017普及组复赛解题报告.pdf
noip2017普及组复赛解题报告_学科竞赛_初中教育_教育专区。noip2017 普及组解题...NOIP2015普及组复赛试题 暂无评价 8页 5下载券 NOIP2016普及组复赛试题... ...
noip2015普及组解题报告.doc
noip2015普及组解题报告_学科竞赛_初中教育_教育专区。noip2015普及组解题报告 ...NOIP2004普及组复赛解题... 8页 免费 NOIp2010复赛普及组解题... 10页 2下载...
NOIP2017普及组复赛-解题报告.pdf
衢州市兴华中学 NOIP2017 普及组复赛 By 冯明浩 NOIP2017 普及组复赛-解题报告...noip2015普及组解题报告 14页 1下载券 NOIP08普及组解题报告 6页 免费 喜欢...
NOIP2015普及组复赛试题.pdf
CCF 全国信息学奥林匹克联赛(NOIP2015)复赛 CCF 全国信息学奥林匹克联赛(NOIP2015)复赛 普及组 (请选手务必仔细阅读本页内容)一、 题目概况 中文题目名称 金币 ...
noip2015普及组题解.doc
noip2015 普及组题解 by 郁庭 from 宁波市镇海蛟川书院 2015
NOIP2015提高组解题报告.doc
NOIP2015 提高组解题报告 T1 神奇的幻方【题目大意】 告诉你幻方的构造方法,给...NOIP2015提高组初赛C++试... 9页 2下载券 NOIP2015普及组解题报告 9页 1下载...
NOIP2015普及组复赛试题.doc
CCF 全国信息学奥林匹克联赛(NOIP2015)复赛 CCF 全国信息学奥林匹克联赛(NOIP2015)复赛 普及组 (请选手务必仔细阅读本页内容)一、 题目概况 中文题目名称 金币 ...
NOIP2015普及组复赛试题讲解(c++版本)_图文.ppt
NOIP2015普及组复赛试题讲解(c++版本) - 试题分析 NOIP2015 普及组复赛题解 NOIP2015普及组C++ 2017. 07. 28 第1题 “金币”简述 ? 国王将...
全国信息学奥林匹克联赛(NOIP2015)复赛普及组第一题pas....txt
全国信息学奥林匹克联赛(NOIP2015)复赛普及组第一题pascal版coin
NOIP2015普及组初赛试题及答案(Pascal).doc
NOIP2015普及组初赛试题及答案(Pascal)_学科竞赛_初中教育_教育专
NOIP2015普及组复赛试卷.pdf
全国信息学奥林匹克联赛(NOIP2015)复赛 普及组 CCF 全国信息学奥林匹克联赛(NOIP2015)复赛 普及组(请选手务必仔细阅读本页内容)一.题目概况中文题目名称 英文题目...
NOIP2015复赛普及组试题.doc
全国信息学奥林匹克联赛(NOIP2015)复赛 普及组 CCF 全国信息学奥林匹克联赛(NOIP2015)复赛 普及组(请选手务必仔细阅读本页内容)一.题目概况中文题目名称 英文题目...
noip2016普及组解题报告.pdf
noip2015普及组解题报告 14页 1下载券 NOIP 2007 普及组解题报... 14页 1...NOIP2010普及组解题报告 9页 免费 2009NOIP普及组复赛解题... 6页 免费 NOI...
NOIP2014普及组解题报告.doc
NOIP2014 普及组复赛解题报告本人是潍坊一中的 wyw,69 级,今年高一, 现在马上就要 NOIP 了, 打算把历年的 NOIP 普及、提高组题目都做一下, 然后写写解题 报告...
noip2015普及组答案.pdf
noip2015普及组答案_学科竞赛_初中教育_教育专区。2015年全国信息学奥林匹克竞赛初赛普及组答案 第二十一届全国青少年信息学奥林匹克联赛初赛 普及组参考答案一、单项...
NOIP2015_普及组复赛word版.pdf
全国信息学奥林匹克联赛(NOIP2015)复赛 普及组 CCF 全国信息学奥林匹克联赛(NOIP2015)复赛 普及组(请选手务必仔细阅读本页内容)一.题目概况中文题目名称 英文题目...
NOIP2015初赛普及组参考答案.doc
NOIP2015初赛普及组参考答案_IT认证_资格考试/认证_教育专区 暂无评价|0人阅读|0次下载|举报文档NOIP2015初赛普及组参考答案_IT认证_资格考试/认证_教育专区。NOIP...
更多相关标签: