《哈理工2016级新生赛解题报告(答案)》由会员分享，可在线阅读，更多相关《哈理工2016级新生赛解题报告(答案)（25页珍藏版）》请在金锄头文库上搜索。
1、A采用递推的方法，由于要到达棋盘上的一个点，只能从左边或者上边过来，根据加法原则，到达某一点的路径数目，就等于到达其相邻的上点和左点的路径数目的总和。所有海盗能达到的点将其路径数置为0即可。#include #include #include int main() int i,j,x,y,n,m,f100100; long long ans100100; int t; scanf(%d, &t); while (t-) scanf(%d%d%d%d,&n,&m,&x,&y); memset(f,1,sizeof(f); memset(ans,0,sizeof(ans); ans00=1; fx
2、y=0,fx+1y+2=0,fx-1y+2=0; fx+1y-2=0,fx-1y-2=0,fx+2y+1=0; fx-2y+1=0,fx+2y-1=0,fx-2y-1=0; for (i=1; i=n; i+) if (fi0) ansi0=1; else break; for (i=1; i=m; i+) if (f0i) ans0i=1; else break; for (i=1; i=n; i+) for (j=1; j=m; j+) if (fij) ansij=ansi-1j+ansij-1; printf(%lldn,ansnm); return 0;B对于任意点K，其与点1之间的
3、最短路有两种情况：（1） 直接从点1走到K；（2） 从1走到点A，通过A直接跳到点B，再从B走到K。或者说，这条最短路等于min（直接从1走到K的距离，从1走到点A通过A跳到B在从B走到K的距离）。设点I和J之间的直线距离为DISI,J，则：在第（1）种情况下，最短路长度为DIS1,K；在第（2）种情况下，最短路长度为DIS1,A + DISB,K;由于DIS1,A是一个常数（因为A固定），而与K有关的只有B，应直接选择A=1使DIS1,1 = 0.（也就是说传送门的第一个点一定要建在1点上）。对当前枚举的第二个传送点位置B,必有唯一一个点C具有如下性质：DIS1,C = DISC,K 且 D
4、IS1,C+1 DISC,K此时距离1最长的点为C，C+1或N中的一个。留意到随着B的递增，C是不递减的，所以在O（n）枚举B的同时只需要O（1）就可以找到。#include #include #include #include using namespace std;const int maxn = 1100000;int i, j, r, n, m, ansi, ansj, ansr;long long ans;long long pmaxn;inline void make() long long temp; ans = pn; i = j = 1; while (i = n) whil
5、e (j i & pj = pi - pj) j+; temp = max(pi - pj, pj-1); temp = max(pn - pi, temp); if (temp ans) ans = temp; ansi = i; ansj = j; i+; int main() int T; scanf(%d, &T); while (T-) memset(p, 0, sizeof(p); scanf(%d, &n); for (i = 2; i = n; i+) scanf(%lld, &pi); pi += pi-1; make(); printf(%lldn, ans); retur
6、n 0;S=n13+n23+nk3C首先需要判断行和列的总和是否相等，因为它们都应该是整个矩阵的所有元素之和。如果他们不相等则这个矩阵肯定不存在。这道题的贪心策略是，把列和从大到小枚举，对每个列和，按行和从大到小的顺序进行选择填上1，然后该行的行和减去1.这种贪心策略之所以有效，是因为这种策略会使各行的行和趋向于平均，尽可能地使行和减为零的情况推迟发生，而行和减为零意味着，当前可选的行数减少1，因此后面的计算可选择方法肯定比这种贪心的策略要少。#include #include using namespace std;const int size=100000;/最大行列数int asize,
7、bsize;/分别保存行和与列和int main()int r,c,i,j;long long s,t;/枚举时比较的行和与列和总数while(scanf(%d%d,&r,&c)=2)/输入整数r,c直到文件结束for(i=0,s=0; ir; i+)scanf(%d,&ai);/输入行和s+=ai;/累加行和for(i=0,t=0; ic; i+)scanf(%d,&bi);/输入列和t+=bi;/累加列和if(s!=t)/如果行和与列和总数不相等printf(NOn);/则不可能有解continue;sort(a,a+r);/行和排序sort(b,b+c);/列和排序for(i=j=0,t
8、=s=0; ic; i+)/从大到小枚举列和t+=bc-i-1;/当前已枚举的列和总数s+=r-j;/当前可用的行和总数while(jr&aji+1)/如果某行和小于枚举列数s-=i+1-aj;/把行和总数多算出来的部分减去j+;if(st) break;/如果可用行和小于当前列和则不可能有解printf(i=c?YESn:NOn);/输出答案return 0;D因为要求出N的因子个数，我们从素数开始讨论。N=1时只有一个因子1，对于任意一个质数p，只有1和p两个因子，所以 Sp= 13+ 23=9,而对于一个质数的幂pk，它的因子分别是p0,p1,p2,pk一共k个，因子的因子数分别是1,2
9、,3,.,k+1个，因此：Spk= 13+23+(k+1)3=i-1k+1i3.如果N有两个不同的素因子p1和p2，这时不妨设N=p1k1*p2k2,这时可以把N的因子按照和p2k2的最大公约数来分成k2+1类，显然每一类的数目都是一样的。注意到一个事实np2jp1i=j+1n(p1i),我们很容易得到：SN=S(p1k1p2k2) = i=0k1n3p1i+i=0k1n3p2p1i+i=0k1n3p2k2p1i= i=0k1n3p1i+i=0k123n3p1i+i=0k1(k2+1)3n3(p1i) =j=1k2+1(j3i=0k1n3(p1i) = i=1k1+1(i3j=1k2+1j3)
10、采用类似的方法，对N的因子使用数学归纳法，可以证明对任意N=p1k1p2k2pmkmSN=Sp1k1p2k2pmkm= i1=1k1+1(i3i2=1k2+1(i23(im=1km+1im3)#include #include using namespace std;const int size=100000;/最大行列数int asize,bsize;/分别保存行和与列和int main()int r,c,i,j;long long s,t;/枚举时比较的行和与列和总数while(scanf(%d%d,&r,&c)=2)/输入整数r,c直到文件结束for(i=0,s=0; ir; i+)sc
11、anf(%d,&ai);/输入行和s+=ai;/累加行和for(i=0,t=0; ic; i+)scanf(%d,&bi);/输入列和t+=bi;/累加列和if(s!=t)/如果行和与列和总数不相等printf(NOn);/则不可能有解continue;sort(a,a+r);/行和排序sort(b,b+c);/列和排序for(i=j=0,t=s=0; ic; i+)/从大到小枚举列和t+=bc-i-1;/当前已枚举的列和总数s+=r-j;/当前可用的行和总数while(jr&aji+1)/如果某行和小于枚举列数s-=i+1-aj;/把行和总数多算出来的部分减去j+;if(st) break;/如果可用行和小于当前列和则不可能有解printf(i=c?YESn:NOn);/输出答案return 0;E将每个排列利用康托展开压缩为一个整数，采用广度优先搜索的方式不停的搜索直到得到目标状态即可。#include #include st
