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

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提高组解题报告
NOIP2015 提高组解题报告 T1 神奇的幻方【题目大意】 告诉你幻方的构造方法,给...NOIP2015提高组初赛C++试... 9页 2下载券 NOIP2015普及组解题报告 9页 1下载...
noip2015普及组解题报告
noip2015普及组解题报告_学科竞赛_初中教育_教育专区。noip2015普及组解题报告 ...NOIP2004普及组复赛解题... 8页 免费 NOIp2010复赛普及组解题... 10页 2下载...
noip2015普及组题解最终
noip2015 普及组题解 by 郁庭 from 宁波市镇海蛟川书院 2015 年 11 月 11 日 如果要拿到剩下的 40 分,主要有三种方法: 方法一:利用数据结构优化 O(NlogN)...
NOIP2015提高组day1第二题解题报告
NOIP2015 提高组复赛 Day1 第二题解题报告 By 某蒟蒻 zrw 1. 题目大概描述(因为写的时候题目还没放出来)几个小盆友们在传递自己的信息(生日) ,并且每个小盆...
更多相关标签: