新开传奇网站999,企业管理系统er图,沈丘做网站yooker,可信网站代码前言
万年D组系列…
正题 题目1#xff1a;数池塘#xff08;jzoj1898#xff09;
有一个地方有一些积水#xff0c;连着的积水是一个池塘#xff0c;求池塘数。
输入
第1行#xff1a;由空格隔开的两个整数#xff1a;N和M 第2..N1行#xff1a;每行M个字符代表…前言
万年D组系列…
正题 题目1数池塘jzoj1898
有一个地方有一些积水连着的积水是一个池塘求池塘数。
输入
第1行由空格隔开的两个整数N和M 第2..N1行每行M个字符代表约翰农场的一排方格的状态。每个字符或者是’W’或者是’.’字符之间没有空格。
输出
第1行约翰农场上的池塘数
样例输入
10 12 W……..WW. .WWW…..WWW ….WW…WW. ………WW. ………W.. ..W……W.. .W.W…..WW. W.W.W…..W. .W.W……W. ..W…….W.
样例输出
3
解题思路
深搜不解释。
代码
#includecstdio
#includeiostream
using namespace std;
int n,m,s;
char c;
bool a[101][101];
void dfs(int x,int y)
{if (x1 || y1 || xn || ym || a[x][y]) return;//退出a[x][y]true;//封dfs(x1,y);dfs(x-1,y);dfs(x,y1);dfs(x,y-1);dfs(x1,y1);dfs(x-1,y-1);dfs(x1,y-1);dfs(x-1,y1);//搜
}
int main()
{//freopen(lkcount.in,r,stdin);//freopen(lkcount.out,w,stdout);scanf(%d%d,n,m);for (int i1;in;i){for (int j1;jm;j){cinc;//用cin输入比较保险昨天就是没用cin错了if (c.) a[i][j]true;//封}}for (int i1;in;i){for (int j1;jm;j)if (!a[i][j])//搜{dfs(i,j);s;//累计数量}}printf(%d,s);
} 题目2接苹果jzoj1899
有两颗苹果树每分钟某一颗树会掉一颗苹果。开始在第一颗树下只能移动c次的情况下在t秒最多能接到多少颗苹果。
输入
第1行由空格隔开的两个整数T和W 第2..T1行1或2每分钟掉落苹果的树的编号
输出
第一行在贝茜移动次数不超过W的前提下她能接到的最多苹果数
样例输入
7 2 2 1 1 2 2 1 1
样例输出
6
解题思路
用dp有两种情况就是移动或不移动这里用三维数组 f[i][j][k]表示第i分钟移动了j次在第k颗树下其实可以不用
代码
#includecstdio
#includeiostream
using namespace std;
int f[1001][31][2],t,w,a[1001],maxs;
int check(int t,int x)//能否接到苹果
{if (a[t]x) return 1;return 0;
}
int main()
{//freopen(bcatch.in,r,stdin);//freopen(bcatch.out,w,stdout);scanf(%d%d,t,w);for (int i1;it;i) scanf(%d,a[i]);for (int i1;it;i){f[i][0][0]f[i-1][0][0]check(i,1);//不移动maxsmax(maxs,f[i][0][0]);for (int j1;jw;j){f[i][j][0]max(f[i-1][j-1][1]check(i,2),f[i-1][j][0]check(i,1));f[i][j][1]max(f[i-1][j-1][0]check(i,1),f[i-1][j][1]check(i,2));//动态转移maxsmax(maxs,max(f[i][j][0],f[i][j][1]));//求最大值。}}printf(%d,maxs);
} 题目3找数jzoj1416
输入一串序列输出第k大的数。
输入
输入文件find.in,输入两行,第一行两个数N、K表示序列的长度表示要找在这个序列中的第大的数。 第二行N≤3000000个数用空格隔开
输出
输出文件find.out,输出序列中的第大的数。
样例输入
6 3 5 2 4 3 1 6
样例输出
4
自解
用小根堆存K个最大的数然后输出堆顶
正解
c算法库直接sort快排
代码
#includecstdio
#includealgorithm
using namespace std;
int n,k,a[3000001],num,x;
void upA(int x)//维护堆的性质
{while (x1 a[x]a[x/2]){swap(a[x],a[x/2]);x/2;}
}
void downA(int x)//维护堆的性质
{int y0;while (x*2num a[x]a[x*2] || x*21num a[x]a[x*21]){yx*2;if (y1num a[y]a[y1]) y;swap(a[x],a[y]);xy;}
}
int main()
{//freopen(find.in,r,stdin);//freopen(find.out,w,stdout);scanf(%d%d,n,k);for (int i1;in;i) {scanf(%d,x);//输入if (numk) {a[num]x;upA(num);}//前k个else if (xa[1])//选大的{a[1]x;//替换downA(1);//维护}}printf(%d,a[1]);//输出
} 题目4最短路径jzoj1417
没错这道题就像题目一样没错就是递推才不是什么最短路。一个n*m的地方不能走斜线求最短数量。
输入
输入文件Sline.in,一行,两个数M,N,其中 2
输出
输出文件sline.out,输出最短路的走法总数.
样例输入
7 5
样例输出
210
解题思路
首先我们可以从左边或下面来所以f[i][j]f[i-1]f[j-1]。然后因为数据忒大有不需要取膜又容易超时。 所以这道题的方法是禁忌·压位高精滚动反复递推
代码
#includecstdio
using namespace std;
int n,m,f[2][801];
int a[1601][61];
void add(int n1,int n2,int n3)
{int g0;for (int i1;i60;i){a[n1][i]a[n1][i]a[n2][i]g;ga[n1][i]/100000000;a[n1][i]%100000000;a[n3][i]a[n1][i];}
}
void write(int n1)
{int w60;while (a[n1][w]0) w--;//找printf(%d,a[n1][w]);//输出for (int iw-1;i1;i--){if (a[n1][i]10000000) printf(0);//暴力判断前导0if (a[n1][i]1000000) printf(0);if (a[n1][i]100000) printf(0);if (a[n1][i]10000) printf(0);if (a[n1][i]1000) printf(0);if (a[n1][i]100) printf(0);if (a[n1][i]10) printf(0);printf(%d,a[n1][i]);}
}
int main()
{//freopen(sline.in,r,stdin);//freopen(sline.out,w,stdout);scanf(%d%d,n,m);if (mn) {int tm;mn;nt;}//避免错误for (int i1;im;i) {f[0][i]i;f[1][i]ni;}//对应高精度数组号a[f[1][1]][1]1;//初值for (int i1;in;i){for (int j1;jm;j){if (i!1 || j!1)add(f[(i-1)%2][j],f[i%2][j-1],f[i%2][j]);//加}}write(f[n%2][m]);
} 题目5棋盘覆盖jzoj1418
一个N*N的棋盘用“L”字方块覆盖3格覆盖除了特殊方块棋盘不能重叠。求覆盖方法。
输入
输入文件Chessboard.in,共两行,第一行一个数N为棋盘的大小,N满足条件N2^K,1K10. 第二行,两个数x,y,表示棋盘中那一个与其它方格不同的位置,x表示行,y表示列.
输出
输出文件Chessboard.out,输出N行N列,共N×N个数,表示用L 型占3 个小格纸片覆盖棋盘上除特殊方格的所有部分各纸片不得重叠的方法.其中的数表示L型纸片覆盖的顺序编号, 不同的L型纸片用不同的编号同一个L型纸片占据的三个位置相同编号从1开始,特殊方格用-1标志;每两个数之间用一个空格隔开,每行最末一个数后面没有空格.
样例输入
4 2 2
样例输出
2 2 3 3 2 -1 1 3 4 1 1 5 4 4 5 5
解题思路
用分治算法不断分然后计算子问题。
代码
#includecstdio
using namespace std;
int number,dx,dy,n,a[1025][1025];
void dfs(int x,int y,int ux,int uy,int s)//x,y表示位置,ux,uy表示特殊符号位置,s表示边长
{if (s1) return;//退出number;//号int zxxs/2;int zyys/2;//中间位置if (uxzx uyzy)//特殊格子在左上{a[zx-1][zy]number;a[zx][zy-1]number;a[zx][zy]number;//记录dfs(x,y,ux,uy,s/2);//分治dfs(zx,y,zx,zy-1,s/2);dfs(x,zy,zx-1,zy,s/2);dfs(zx,zy,zx,zy,s/2);}else if (uxzx uyzy){a[zx][zy-1]number;a[zx-1][zy-1]number;a[zx][zy]number;dfs(x,y,zx-1,zy-1,s/2);dfs(x,zy,ux,uy,s/2);dfs(zx,y,zx,zy-1,s/2);dfs(zx,zy,zx,zy,s/2);}else if (uxzx uyzy){a[zx-1][zy-1]number;a[zx-1][zy]number;a[zx][zy]number;dfs(x,y,zx-1,zy-1,s/2);dfs(zx,y,ux,uy,s/2);dfs(x,zy,zx-1,zy,s/2);dfs(zx,zy,zx,zy,s/2);}else if (uxzx uyzy){a[zx-1][zy]number;a[zx][zy-1]number;a[zx-1][zy-1]number;dfs(x,y,zx-1,zy-1,s/2);dfs(x,zy,zx-1,zy,s/2);dfs(zx,y,zx,zy-1,s/2);dfs(zx,zy,ux,uy,s/2);}
}
int main()
{//freopen(chessboard.in,r,stdin);//freopen(chessboard.out,w,stdout);scanf(%d%d%d,n,dx,dy);a[dx][dy]-1;//特殊方块dfs(1,1,dx,dy,n);//搜索for (int i1;in;i){for (int j1;jn;j)printf(%d ,a[i][j]);printf(\n);}//输出
}
