xw的妙妙屋

数字游戏 [https://vjudge.net/problem/LibreOJ-10164]: 题目大意： 科协里最近很流行数字游戏。 某人命名了一种不降数，这种数字必须满足从左到右各位数字呈非下降关系，如 123，446。 现在大家决定玩一个游戏，指定一个整数闭区间 [a,b]，问这个区间内有多少个不降数。 输入格式 输入包含多组测试数据。 每组数据占一行，包含两个整数 a 和 b。 输出格式 每行给出一组测试数据的答案，即 [a,b] 之间有多少不降数。 数据范围 1≤ a ≤ b ≤2^31−1 解题思路： f[i][j] 数组代表着最高位是j并且一共有i位不降数的集合 f[i][j] = f[i-1][j] + f[i-1][j+1] + f[i-1][j+2] +…+ f[i-1][9]; 按照数位DP分析步骤： 假设我们当前枚举到第i位，且第i位上的数字是x，那么现在对于答案的第i位数字j来说，可以填两类数字： 1.j 取0~x-1 那么res += f[i+1][j]; 2.j 取 x last记录x，再枚举下一位 123456789101112131415161...

A. 小竹与妈妈 题意 ay+b=x, 已知a,b,x,求y 题解 显然小竹的年龄为 直接输出即可。 代码 123456789#include <bits/stdc++.h>using namespace std;int main(){ long long a, b, x; scanf("%lld%lld%lld", &a, &b, &x); printf("%lld\n", (x - b) / a); return 0;} B.走丢的小竹 题意 有 n 个出口，每个出口都连着 m 个房间其中一个，有 q 次询问，每次都问如果不能去 x 号房间的话，有多少出口能走。 1≤n,m,q≤105 题解 记录每个房间有多少个出口连接记为,每次询问输出即可。 代码 123456789101112131415161718192021222324#include <bits/stdc++.h>using namespa...

A.我会开摆 题意 给定n=4的方阵，问是否存在n=2的方阵中四个格子全是一个字符的情况 题解 直接枚举所有点当n=2方阵的左上角，看是否符合题目要求 注意：检查n=2的方阵时，要先排除某点为左上角没有n=2方阵情况 代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include <bits/stdc++.h>using namespace std;char a[5][5];int main(){ int t; scanf("%d", &t); while (t--) { for (int i = 1; i <= 4; i++) { for (int j = 1; j <= 4; j++) { cin >>...

1.杨辉三角递推法求组合数 设 $C[i][j]$ 为已在 $i$个元素中抽取了 $j$ 个元素，对于上一步描述，有可能是： 这一步没有抽取元素，之前已经抽了 $j$ 个元素：$C[i-1][j]$ 这一步抽取了一个元素，之前已经抽了 $j-1$ 个元素：$C[i-1][j-1]$ 将这两种情况加起来便是 $C[i][j]$ 的结果，由此得出式子： $C[i][j] = C[i-1][j] + C[i-1][j-1]$ 时间复杂度：$O(n^2)$ 核心代码 1234567891011121314151617void getC(int N){ for (int i = 0; i <= N; i++) { for (int j = 0; j <= i; j++) { if (j == 0) { C[i][j] = 1; } else {...

把某周做过的题稍微整理了一下，主要是DP，方便随时复习，也方便后人踩坑。 1 完全背包 · 洛谷 P1616 疯狂的采药 思路 把「时间」看成背包容量，「价值」就是药草收益。每种药草可以无限次采集 ⇒ 完全背包。 状态转移 1dp[j] = max(dp[j], dp[j - h[i]] + w[i]) 代码 12345678910111213141516171819202122232425#include <bits/stdc++.h>using namespace std;const int N = 1e4 + 10;typedef long long ll;int h[N], w[N];const int M = 1e7 + 10;ll dp[M];int main(){ int t, m; scanf("%d%d", &t, &m); for (int i = 1; i <= m; i++) { scanf("%d%d", &...