洛谷刷题日记1

P1000P1001不解释

#include<cstdio> int main(){printf(" ********\n ************\n ####....#.\n #..###.....##....\n ###.......###### ### ###\n ........... #...# #...#\n ##*####### #.#.# #.#.#\n ####*******###### #.#.# #.#.#\n ...#***.****.*###.... #...# #...#\n ....**********##..... ### ###\n ....**** *****....\n #### ####\n ###### ######\n##############################################################\n#...#......#.##...#......#.##...#......#.##------------------#\n###########################################------------------#\n#..#....#....##..#....#....##..#....#....#####################\n########################################## #----------#\n#.....#......##.....#......##.....#......# #----------#\n########################################## #----------#\n#.#..#....#..##.#..#....#..##.#..#....#..# #----------#\n########################################## ############");} #include<cstdio> int main() { long a, b; scanf("%ld%ld", &a, &b); printf("%ld", a+b); }

P1002过河卒 简单的动态规划，详细解释一下思路： 首先看着不舒服先把那只马去掉，把问题转化成从A点到B点的走最短距离的走法，已知是让我们求最短路线，所以方向其实是确定的，一定不是向右就是向下，这样一定能满足是最短路线，这种情况下我们的做法是算出从A到每一个点的走法，因为走的方向是固定的，所以从A走到每个不在边上的点P(i, j)，只能从P1(i-1, j)和P2(i, j-1)走来，所以从A到P的走法就是从A到P1与从A到P2的走法和，若我们把从A走到(x, y)的距离走法表示成f(x, y)，那么f(x, y)可以表示成这样： $$f(x,y)\{\begin{array}{l}1,当x=0或y=0\\ f(x-1,y)+f(x,y-1)\end{array}$$ 这很容易想到递归，我们再加上个那只马，可以写成这样： $$f(x,y)\{\begin{array}{l}0,当(x,y)可以被马打到\\ 1,当x=0或y=0\\ f(x-1,y)+f(x,y-1)\end{array}$$ 但是没有必要，直接模拟一下就好，代码奉上：

//数学的标点法 #include<cstdio> #include<iostream> using namespace std; const int NR=30; struct point { bool f;//是否可以走 long p;//从原点到这里的路线数量 }a[NR][NR]; int main() { int bx, by; scanf("%d%d", &bx, &by); for(int i=0;i<=bx;i++) for(int j=0;j<=by;j++) a[i][j].f=true, a[i][j].p=0; int hx, hy; scanf("%d%d", &hx, &hy); //初始化，把马的位置还有它可以走到的位置标记 a[hx][hy].f=false; if(hx>=2) { if(hy>=1) a[hx-2][hy-1].f=false; a[hx-2][hy+1].f=false; } if(hy>=1)a[hx+2][hy-1].f=false; if(hy>=2) { if(hx>=1) a[hx-1][hy-2].f=false; a[hx+1][hy-2].f=false; } if(hx>=1)a[hx-1][hy+2].f=false; a[hx+1][hy+2].f=false; a[hx+2][hy+1].f=false; //初始化递推基本数据 a[0][0].p=1; for(int i=1;i<=bx;i++) { if(!a[i][0].f)break; a[i][0].p=1; } for(int i=1;i<=by;i++) { if(!a[0][i].f)break; a[0][i].p=1; } //递推 for(int i=1;i<=bx;i++) for(int j=1;j<=by;j++) { if(!a[i][j].f)continue; a[i][j].p=a[i-1][j].p+a[i][j-1].p; } printf("%ld", a[bx][by].p); return 0; }

P1003铺地毯 直接模拟不多说：

#include<stdio.h> const int NR=1e5; struct carpet { int x1, y1, x2, y2; void scan() { scanf("%d%d%d%d", &x1, &y1, &x2, &y2); x2+=x1, y2+=y1; } bool hasPoint(int a, int b) { return a>=x1 && a<=x2 && b>=y1 && b<=y2; } }a[NR+10]; int n, x, y, ans=-1; int main() { scanf("%d", &n); for(int i=1;i<=n;i++) a[i].scan(); scanf("%d%d", &x, &y); for(int i=1;i<=n;i++) if(a[i].hasPoint(x, y)) ans=i; printf("%d", ans); return 0; }

先写这么多其他明天再说