xw的妙妙屋

[TOC] 树状数组求逆序对[https://vjudge.net/contest/515986#problem/C]: 123456789101112131415161718192021222324252627282930313233343536373839404142#include <bits/stdc++.h>using namespace std;int n;const int N = 2e5 + 10;int a[N];int t[N];typedef long long ll;int lowbit(int x){ return x & -x;}void add(int x){ while (x <= n) { t[x]++; x += lowbit(x); }}int ask(int x){ int sum = 0; while (x >= 1) { sum += t[x...

数字游戏[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，再枚举下一位 12345678910111213141...

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 namespace...

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++) { ...

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 {...