哈理工2016级新生赛解题()程序.docx

A采用递推的方法，由于要到达棋盘上的一个点，只能从左边或者上边过来，根据加法原则，到达某一点的路径数目，就等于到达其相邻的上点和左点的路径数目的总和。所有海盗能达到的点将其路径数置为0即可。#include stdio.h#include string.h#include stdlib.hint main(){ int i,j,x,y,n,m,f[100][100]; long long ans[100][100]; 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)); ans[0][0]=1; f[x][y]=0,f[x+1][y+2]=0,f[x-1][y+2]=0; f[x+1][y-2]=0,f[x-1][y-2]=0,f[x+2][y+1]=0; f[x-2][y+1]=0,f[x+2][y-1]=0,f[x-2][y-1]=0; for (i=1; i=n; i++) if (f[i][0]) ans[i][0]=1; else break; for (i=1; i=m; i++) if (f[0][i]) ans[0][i]=1; else break; for (i=1; i=n; i++) for (j=1; j=m; j++) if (f[i][j]) ans[i][j]=ans[i-1][j]+ans[i][j-1]; printf(%lld\n,ans[n][m]); } return 0;}B对于任意点K，其与点1之间的最短路有两种情况：直接从点1走到K；从1走到点A，通过A直接跳到点B，再从B走到K。或者说，这条最短路等于min（直接从1走到K的距离，从1走到点A通过A跳到B在从B走到K的距离）。设点I和J之间的直线距离为DIS[I,J]，则：在第（1）种情况下，最短路长度为DIS[1,K]；在第（2）种情况下，最短路长度为DIS[1,A] + DIS[B,K];由于DIS[1,A]是一个常数（因为A固定），而与K有关的只有B，应直接选择A=1使DIS[1,1] = 0.（也就是说传送门的第一个点一定要建在1点上）。对当前枚举的第二个传送点位置B,必有唯一一个点C具有如下性质：DIS[1,C] = DIS[C,K] 且 DIS[1,C+1]　＞ DIS[C,K]此时距离1最长的点为C，C+1或N中的一个。留意到随着B的递增，C是不递减的，所以在O（n）枚举B的同时只需要O（1）就可以找到Ｃ。#include cstdio#include cstring#include cstdlib#include algorithmusing namespace std;const int maxn = 1100000;int i, j, r, n, m, ansi, ansj, ansr;long long ans;long long p[maxn];inline void make() { long long temp; ans = p[n]; i = j = 1; while (i = n) { while (j i p[j] = p[i] - p[j]) j++; temp = max(p[i] - p[j], p[j-1]); temp = max(p[n] - p[i], 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, p[i]); p[i] += p[i-1]; }