A 中国象棋 [图片缺失] 原图：https://img-blog.csdnimg.cn/20200506201533473.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkxMDMyMA==,size_16,color_FFFFFF,t_70#pic_center 一道挺标准的DFS模板，只不过走法换成了走日字。 ```cpp #include using namespace std; char g[10][9]; bool book[10][9]; int dx[] = { -2,-1,1,2,2,1,-1,-2 }; int dy[] = { 1,2,2,1,-1,-2,-2,-1 }; bool dfs(int x, int y) { book[x][y] = true; if (g[x][y] == 'T')return true; for (int i = 0; i < 8; …
传送门→ A猴子摘桃 小学奥数，掰手指都能数出来是22. B平方和 也没啥好说的，填空题暴力就完事了。 ```cpp #include #include using namespace std; bool check(int x) { while(x > 0) { int t = x % 10; if(t == 2 || t == 0) return true; x /= 10; } return false; } int main() …
A有趣的数字 我们称一个数是质数，而且数位中出现了 5 的数字是有趣的。例如 5,59,457 都是有趣的，而 15,7 不是。求 1 到 100000 中有趣的数的个数。 没啥好说的，就硬来。先用筛法打出素数表，再用check函数确认数位里是否含5。时间复杂度肯定是不优的，但填空题嘛能解出来就是AC。最后答案是3282. ```cpp #include #include #include #include #define get(x) scanf("%d", &x;) #define lget(x) scanf("%lld", &x;) #define set(a,b) memset(a, b, sizeof(a)) #define rep(a, b, c) for (int a = b; a <= c; a++) using namespace std; typedef long long ll; const int …
传送门 题面 我的某室友学过素描，墙上有n张他的作品。这些作品都是宽度为1，高度不定的矩形，从左到右排成一排，且底边在同一水平线上。宿舍评比就要来了，为了及格，我们决定买不多于m块的矩形木板，把这些作品和谐掉。要求木板也从左到右排成一排，且底边与作品的底边在同一水平线上。在能够把所有作品和谐掉的前提下，我们希望这些木板的面积和最小，问最小面积和。 [图片缺失] 原图：http://lx.lanqiao.cn/RequireFile.do?fid=FaHtNHE3 输入 第一行两个数n和m，表示作品数和木板数；第二行n个数Hi，表示从左到右第i个作品的高度。 输出 一行一个数ans表示答案。 样例数据 样例输入 5 2 4 2 3 5 4 样例输出 22 数据规模 对于30%的数据：1<=n，m<=10；对于100%的数据：1<=n，m<=100，1<=Hi<=10000。 思路 题面意思转述一下就是：将若干幅矩形的画作通过不同的相邻组合方式，在用尽m块木板的情况下，使得覆盖它们的面积最小。显然这个面积由被覆盖区间中最高的画作来决定，所以需要设hmax[i][j]为hi~hj中画的最大高度。 设 dp[i][j]为用j块板子覆盖前i幅画的最小面积，记k为在dp[i][j]状态下还剩的板子数量。可以得到状态转移方程： [图片缺失] 原图：https://www.edisoncgh.com/wp-content/uploads/2020/03/2020031713184378-1024x61.png 关于初始状态的确定，这里在求最小值，所以dp初始化为INF。如果用一块板子来覆盖前i幅画，显然面积只能为i·hmax[1][i]，所以dp[i][1]初始化为 i·hmax[1][i] 。 ```cpp #include #include …