NOIP2015普及组解题报告

1、NOIP2015 普及组解题报告From 贴吧 id u007zzt金币 国王将金币作为工资，发放给忠诚的骑士。 第一天骑士收到一枚金币；之后两天（第二天和第三天） ，每天收到两枚金 币；之后三天（第四、五、六天） ，每天收到三枚金币；之后四天，每天收到四 枚金币， 以此类推； 这种工资发放模式会一直延续下去， 当连续 N 天收到 N 枚金 币后，骑士会在之后的N+1天，每天收到N+1枚金币。请计算前K天里，骑士一共获得了多少金币。输入格式输入包含一个正整数K，表示发放金币的天数。输出格式 输出一个正整数，即骑士收到的金币数。样例 1样例输入 16样例输出 114样例 2样例输入 21000样

2、例输出 229820对于全部数据，K K=i)ans+=i*i;k-=i;elseans+=k*i;k=0;i+;printf(%dn,ans);return 0;扫雷游戏 扫雷游戏是一款十分经典的单机小游戏。在 n 行 m 列的雷区中有一些格子含有地雷(称之为地雷格) ，其他格子不含 地雷(称之为非地雷格) 。玩家翻开一个非地雷格时， 该格将会出现一个数字提示周围格子中有多 少个是地雷格。游戏的目标是在不翻出任何地雷格的条件下，找出所有的非地雷格。现在给出n行m列的雷区中的地雷分布，要求计算出每个非地雷格周围的地 雷格数。注：一个格子的周围格子包括其上、下、左、右、左上、左下、右上、右下 八

3、个方向上与之直接相邻的格子。输入格式第一行用一个空格隔开的两个整数 n和m分别表示雷区的行数和列数。接下来n行，每行m个字符，描述了雷区中的地雷分布情况。字符?表示相 应的格子是地雷格，字符(?)表示相应的格子是非地雷格子。相邻字符之间无分 隔符。输出格式输出文件包括n行，每行m个字符，描述了整个雷区。用？表示地雷格，用 周围地雷格数表示非地雷格。相邻字符之间无分隔符。样例 1样例输入 13 3*?*?样例输出 1*102211*1样例 2样例输入 22 3?*?*?样例输出 22*1*21又是水题一道，请允许我吐槽一下pj组的难度别的没什么，注意字符的读入。附C+弋码。#include st

4、dio.husing namespace std;int matrix105105;char str105;int dir3=0,1,-1;int n,m;int main()freopen(mine.in,r,stdin);freopen(mine.out,w,stdout);scanf(%d%d,&n,&m);int i,j,k,t;for(i=1;i=n;i+)scanf(%s,str+1);for(j=1;j=m;j+)if(strj=*) matrixij=-1;for(i=1;i=n;i+)for(j=1;j=m;j+)if(matrixij=0)for(k=0;k3;k+)for

5、(t=!k;t3;t+)matrixij+=matrixi+dirkj+dirt=-1 ?1:0;for(i=1;i=n;i+)for(j=1;j=m;j+)if(matrixij=-1)putchar(*);elseputchar(matrixij+O); putchar(n);return 0;求和一条狭长的纸带被均匀划分出了 n个格子，格子编号从1到n。每个格子上 都染了一种颜色 color i (用1，m当中的一个整数表示)，并且写了一个数字 nu mber。编号3456定义一种特殊的三元组：(x, y, z)，其中x，y, z都代表纸带上格子的编 号，这里的三元组要求满足以下两个条件

6、：x, y, z都是整数,xvyvz ,y - x=z- ycolor x = color z满足上述条件的三元组的分数规定为(x+z) ?(numberx+number)。整个纸带的 分数规定为所有满足条件的三元组的分数的和。这个分数可能会很大，你只要输 出整个纸带的分数除以10,007所得的余数即可。输入格式第一行是用一个空格隔开的两个正整数n和m,n代表纸带上格子的个数，m代表纸带上 颜色的种类数。第二行有n个用空格隔开的正整数，第i个数字numberi代表纸带上编号 为i的格子上面写的数字。第三行有n个用空格隔开的正整数，第i个数字colori代表纸带上编号 为i的格子染的颜色。输出格

7、式共一行，一个整数，表示所求的纸带分数除以10,007所得的余数。样例1样例输入16 25 5 3 2 2 22 2 1 1 2 1样例输出182样例2样例输入215 45 10 8 2 2 2 9 9 7 7 5 6 4 2 42 2 3 3 4 3 3 2 4 4 4 4 1 1 1 样例输出 2 1388 限制对于第1组至第2组数据，1 nW 100, 1 m 5 ;对于第3组 至第 4 组数据，1 nW 3000, 1 w m 100 ；对于第 5 组至第 6 组数据， 1 W n W 100000, 1 W m W 100000 ，且不 存在出现次数超过 20 的颜色；对于全部 10

8、 组数据， 1 W n W 100000, 1 W m W 100000, 1 W color i W m, 1 W numberi W 100000。提示 【输入输出样例 1 说明】 纸带如题目描述中的图所示。 所有满足条件的三元组为： (1, 3, 5), (4, 5, 6)。所以纸带的分数为 (1 + 5) ? (5 + 2) + (4 + 6)? (2 + 2) = 42 + 40 = 82 。观察题意可以得知， 如果第 i 位和第 j 位同色，那么就一定能够组成一个三 元组，并且三元组的价值完全与中间那个数无关。 那么，我们就用一个数组存储 同奇偶性的同色方块，用 n 表示数值， i

9、 和 j 表示坐标。那么价值就是 (n i+n j)*(i+j) 。现在如果把每组的数的下标用 a1an表示，数值用n1nk表示，用sum表 示数值之和。答案就是(n 1+ n2)*(a1+a2)+。如果这样做就是 O(nA2)的 算法。但是我们现在可以针对每一个数， 只求只与这个数的下标和其他数值有关的 值，也就是 a1(n1+n2)+a1(n1+ n3)+a1(n1+ n4)+ +a1(n1+ nk)。一个同奇偶性 同颜色的一组总和就是a取1到k的得数之和。又因为a1(n1+n2) + a1(n1+ n3) +a1(n1+n4)+a1(n1+nk)=a1(n1*(n-1)+n2+nk)=a

10、1*n1*(n-2)+a1*sum。这样转化过来就很好求了，O(n)的时间复杂度就能得到解。附C+代码：#include stdio.husing namespace std;const int SIZE=100005,mod=10007; int n,m;int colorSIZE;int numSIZE;int sum2SIZE;int d2SIZE;int ans=0;int main() freopen(sum.in,r,stdin); freopen(sum.out,w,stdout); scanf(%d%d,&n,&m);int i;for(i=1;i=n;i+)scanf(%d,

11、num+i);for(i=1;i=n;i+)scanf(%d,color+i); sumi%2colori= (sumi%2colori+numi)%mod;di%2colori+;for(i=1;i=n;i+)ans=(ans+sumi%2colori*i%mod+ (di%2colori-2)%mod*numi%mod*i%mod)%mod;printf(%dn,ans);return 0;推销员阿明是一名推销员， 他奉命到螺丝街推销他们公司的产品。 螺丝街是一条死 胡同，出口与入口是同一个，街道的一侧是围墙，另一侧是住户。螺丝街一共有 N 家住户，第 i 家住户到入口的距离为 Si 米。

12、由于同一栋房子里可以有多家 住户，所以可能有多家住户与入口的距离相等。 阿明会从入口进入， 依次向螺丝 街的 X 家住户推销产品， 然后再原路走出去。 阿明每走 1 米就会积累 1 点疲 劳值，向第 i 家住户推销产品会积累 Ai 点疲劳值。 阿明是工作狂， 他想知道， 对于不同的 X ，在不走多余的路的前提下，他最多可以积累多少点疲劳值。输入格式第一行有一个正整数N，表示螺丝街住户的数量。接下来的一行有 N 个正整数，其中第 i 个整数 Si 表示第 i 家住户到入 口的距离。数据保证 S1 Sn10&接下来的一行有 N 个正整数，其中第 i 个整数 Ai 表示向第 i 户住户推 销产品会积

13、累的疲劳值。数据保证 Ai103 。输出格式输出 N 行，每行一个正整数，第 i 行整数表示当 X=i 时，阿明最多积累 的疲劳值。样例 1样例输入 151 2 3 4 51 2 3 4 5样例输出 11519222425样例 2样例输入 251 2 2 4 55 4 3 4 1样例输出 21217212427对于20%的数据，K NW 20;对于40%的数据，K N 100;对于60%的数据，K N 1000;对于100%的数据，K N 100000。【输入输出样例 1 说明】X=1: 向住户 5 推销，往返走路的疲劳值为 5+5，推销的疲劳值为 5 ，总疲 劳值为 15 。X=2: 向住户

14、 4、5 推销，往返走路的疲劳值为 5+5 ，推销的疲劳值为 4+5， 总疲劳 值为 5+5+4+5=19。X=3: 向住户 3 、4、5 推销，往返走路的疲劳值为 5+5 ，推销的疲劳值 3+4+5， 总疲 劳值为 5+5+3+4+5=22。X=4: 向住户 2 、3、4、5 推销，往返走路的疲劳值为 5+5，推销的疲劳值 2+3+4+5， 总疲劳值 5+5+2+3+4+5=24。X=5: 向住户 1 、2、3、4、5 推销，往返走路的疲劳值为 5+5 ，推销的疲劳 值 1+2+3+4+5， 总疲劳值 5+5+1+2+3+4+5=25。【输入输出样例 2 说明】X=1:向住户4推销，往返走路

15、的疲劳值为4+4，推销的疲劳值为4，总疲 劳值4+4+4=12。X=2 :向住户1、4推销，往返走路的疲劳值为 4+4，推销的 疲劳值为 5+4，总疲劳值 4+4+5+4=17。X=3:向住户1、2、4推销，往返走路的疲劳值为 4+4，推销的疲劳值为 5+4+4，总疲劳值 4+4+5+4+4=21。X=4:向住户1、2、3、4推销，往返走路的疲劳值为4+4，推销的疲劳值 为 5+4+3+4， 总疲劳值 4+4+5+4+3+4=24。或者向住户 1 、 2、 4、 5 推销，往返 走路的疲劳值为 5+5，推销的疲劳值为 5+4+4+1，总疲劳值 5+5+5+4+4+1=24。X=5:向住户1、2

16、、3、4、5推销，往返走路的疲劳值为5+5，推销的疲劳 值为 5+4+3+4+1 ， 总疲劳值 5+5+5+4+3+4+1=27。可以证明每一次的最优解必然包含了上一次的最优解， 也就是说只要知道这 一轮的最大疲劳值就行了。 而这一次的最大疲劳值也就是找最大能多消耗的疲劳 值。如果是正着做，可以分成两部分：一部分的距离小于已经到达的最远距离， 另一部分大于可以到达的最远距离。对于小于最远距离的部分， 它们的疲劳增加值是不会变的， 所以用优先队列 存储，令疲劳增加值尽量大的靠前。因此开一个数组a,存储距离从小到大排序的位置。另一个同样的数组， 按照两倍的距离加上拜访的疲劳值消耗排序。 如果 距离

17、比已经到达的最远距离小， 那么可以直接略过。 而位置比到达的最远距离远 的点的排序是不会变的，因为都相当于疲劳值少了二倍的当前距离。这样一想，就好做多了，每次比较到达最远点和最近点的疲劳消耗，哪边大 就选哪边。附C+弋码（不知道为何vijos总60，于是搬了 AC代码）#include #include #include #include using namespace std; const int N=100005;struct Node int id, v;bool operator (const Node &a) const return va.v; /最大值优先;priority_qu

18、eue la;priority_queue ra;int sN, aN;int main()freopen(salesman.in,r,stdin);freopen(salesman.out,w,stdout);scanf(%d, &n); for (int i=1; i=n; i+)scanf(%d, &si); / for (int i=1; i=n; i+)scanf(%d, &ai); / int ans=-1, p=-1; for (int i=1; i=ans)/ =int n;读入路径读入疲劳值求加路径疲劳值的最大值 保证第一次找到的位置 p 尽可能的ans=d; p=i;/第一轮找加路径疲劳度最大值ans及位置pprintf(%dn, ans);for (int i=1; ip; i+)la.push(ai); /p之间的疲劳值直接入左堆for (int i=p+1; i=n; i+)Node tp;tp.id=i; tp.v=(si-sp)*2+ai;ra.push(tp); /p之后的加路径(相对)疲劳值入右堆for (int q=2; qy)ans+=x; la.pop(); /