主要给出了WA时可能会出现的错误, 节省调试时间, 并方便日后回顾; 建议提交一次后对照查询, 其他问题请本地调试解决.
Hello World
略.
A+B
略.
数据类型大小及范围
可使用switch-case进行条件判断.
使用CHAR_MAX等宏时, 注意包含头文件<limits.h>.
平均值
直接相加可能会越界.
1
|
int avg = ((a-b)>>1)+b;
|
进制转换
输出大写十六进制需使用"%X", “%x"会输出小写十六进制.
浮点数输出
略.
动态宽度输出
可使用"tmp/10"做十进制向右移位获取输入数字长度.
1
2
3
4
5
6
|
cnt = 0, tmp = n;
while(tmp){
tmp /= 10;
++cnt;
}
if (!n) cnt = 1;
|
计算地球上两点之间的距离
C中三角函数仅接收弧度参数, 需先将经纬度转换为弧度.
1
2
|
#define Pi 3.1415926
phi1 = phi1*PI/180;
|
风寒指数
输出要求四舍五入, 只做类型转换是截断.
1
|
int chillInt = (int)(chillDouble+0.5f);
|
颜色模型转换
取最大值和最小值, 可使用比较运算符.
1
2
|
int max = r >= g ? (r >= b ? r : b) : (r >= b ? r : b);
int min = r <= g ? (r <= b ? r : b) : (r <= b ? r : b);
|
如果使用浮点型比较, 浮点数不精确, 不能直接使用"a == b”, 应当使用"a-b < 1e-9".
如果使用整型比较, 计算时应当进行类型转换(强制或隐式), 否则"/“左右操作数均为整数时只能得到整数.
此外, 每个除数都应当判断不为0.
乘数模
直接相乘可能会越界, 先取模再相乘再取模.
方阵
可使用比较运算符得到矩阵元素. 无需使用数组.
1
|
a = (col-raw) ? (col-raw) : (raw-col); // a[col][raw]
|
分数的加、减、乘、除法
可使用"getchar();“取走输入中的”/”.
约分时, 可使用辗转相除法得到分子分母最大公因数, 再分别除掉.
1
2
3
4
|
int gcd(int a,int b){
if (b == 0) return a;
else return gcd(b,a%b);
}
|
结果中若出现负分数, 只需保证最大公因数为正即可.
1
2
|
int d = gcd(m,n);
d = d > 0 ? d : -d;
|
操作数
同“动态宽度输出”, “%10"可以得到个位数, “/10"可以十进制下向右移动一位.
组合数
动态规划题, 但由于 $n\leq 50$, 暴搜不会超时.
比率
“*10"实现十进制下向左移动一位, 直到变成整数, 判断不是整数可使用"x != floor(x)”.
得到最大公因数并约分, 同"分数的加、减、乘、除法”.
级数和
“/10"实现十进制下右移一位, 直到没有整数部分, 判断有整数部分可使用”(int)x”.
舍去末尾的0, 可使用"%g"格式化输出.
对称数
“fget(num,11,stdin)“获取数字为字符串, 并替换掉末尾换行符.
1
2
|
char *find = strchr(num,'\n');
if(find) *find = '\0';
|
使用"strlen()“获取长度.
翻转分为数字改变和位置改变. 数字(实则为字符)改变为: ‘6’->‘9’, ‘9’->‘6’, ‘0’->‘0’, ‘1’->‘1’, ‘8’->‘8’. 位置改变为第i位换到第(len-i-1)位.
可使用switch-case翻转后再逐位判断, 或直接判断; 包含其他数字时(default)则直接输出"No”.
偷分寄巧: 由于该题样例只有三位数, 可直接暴力判断
1
2
3
4
5
6
7
8
9
10
|
int a = (n/100)%10;
int b = (n/10)%10;
int c = n%10;
if ((b == 0 || b == 1 || b == 8) && ((a == 6 && c == 9) || (a == 9 && c == 6)
|| ((a == 0 || a == 1 || a == 8) && (c == 0 || c == 1 || c == 8)))){
printf("Yes\n");
} else {
printf("No\n");
}
|
幂数模
直接求幂再求模可能会越界超时, 须使用快速模幂.
$b=2k$ 时, 有 $a^b\equiv(a^k)^2 ({\rm mod}\ m)$;
$b=2k+1$ 时, 有 $a^b\equiv(a^k)^2\times a ({\rm mod}\ m)$.
1
2
3
4
5
6
7
8
9
10
11
12
13
|
typedef unsigned long long uint64;
uint64 fastPowerMod (uint64 t, uint64 e, uint64 m){
uint64 r = 1;
while (e){
if (e&1){
r = (r*t)%m;
}
t = (t*t)%m;
e >>= 1;
}
return r;
}
|
倍数和
输入采用动态数组或足够大的数组或直接循环均可.
1
2
3
4
5
6
7
8
|
unsigned int t;
scanf("%u",&t);
// 以下四种方法任选其一
unsigned int n[t]; // 1. MSVC会报错, 但GCC支持, 可以AC
unsigned int *n = (unsigned int *)malloc(t*sizeof(unsigned int)); // 2. MSVC和GCC均支持
unsigned int n[100000] // 3. 足够大的数组, 不会溢出, 不会超出内存限制
for (unsigned int i = 1; i <= t; ++i); // 4. 循环读取输入并输出
|
暴搜, 不会超时.
余数和
输入顺序.
最大数字
条件为小于或等于 $n$.
倒水
使用BFS(广度优先), 将水杯状态视为顶点, 状态间的转移即为边, 每次转移相对(初始状态)距离加1; $(0,0)$为初始状态, 检索到 $(0,d)$ 或 $(d,0)$ 时终止, 此时距离矩阵中对应元素值即为最小操作次数.
1
2
3
4
5
6
|
#include <string.h>
#define INF 0x3f3f3f3f // 无穷大, 表示未检索
int distTable[10000][10000]; // 距离矩阵
memset(distTable, 0x3f, sizeof(distTable)); // 初始化
distTable[0][0] = 0; // 设置初始状态
|
每次状态转移共有八种情况: (记左为0, 右为1)
- 装满0: $(a,b)\to (n,b)$;
- 装满1: $(a,b)\to (a,m)$;
- 倒空0: $(a,b)\to (0,b)$;
- 倒空1: $(a,b)\to (a,0)$;
- 0倒入1, 1未满: $(a,b)\to (0,a+b)$, $a+b<m$;
- 0倒入1, 1已满: $(a,b)\to (a+b-m,m)$, $a+b\geq m$;
- 1倒入0, 0未满: $(a,b)\to (a+b,0)$, $a+b<n$;
- 1倒入0, 0已满: $(a,b)\to (n,a+b-n)$, $a+b\geq n$.
使用数组表示循环队列, 当前状态为队首, 转移后插入至队尾.
1
2
3
4
5
6
7
8
9
|
#define MAXSIZE 10000
int queue[MAXSIZE][2] = {0}; // 循环队列并初始化
int head = 0; // 队首指向0
int tail = 1; // 队尾指向1
// 移动队首队尾时用取余实现循环效果
head = (head+1)%MAXSIZE
tail = (tail+1)%MAXSIZE
|
好数字
同幂数模.
$$\frac{n+1}{2} = \begin{cases}
k, \ n=2k \\
k+1, \ n=2k+1 \\
\end{cases}$$
毕达哥拉斯三元组
不妨设 $a$ 为短直角边, $b$ 为长直角边; 则 $a\in (0,\frac{n}{4})$, $b\in [a,\frac{n}{2})$.
$a\times b\times c$可能越界, 使用unsigned long long.
竖式乘法
“/10"获取位数"len(num)”.
获取右数第 $n$ 位数字.
1
2
3
4
|
#include <math.h>
x /= (uint)pow(10,n-1);
x %= 10;
|
总宽度为"lenTotal = len(ans)+1;”, 加算中第 $i$ 列空格数为 “j <= lenTotal-len(current)-(i-1);” 亦即 “j < lenTotal-len(current)-i”.
查找数列
写成下三角形式, 第 $n$ 列末尾项数为 $1+2+…+n$.
1
2
3
4
5
6
7
|
cnt = 1, sum = 0;
while(n-sum > 0){
sum += cnt;
++cnt;
}
sum -= cnt;
ans = n-sum == 0 ? cnt : (n-sum-1);
|
俄罗斯农夫乘法
在循环输出中判断并累加即可.
阶乘倍数
枚举阶乘模可能会超时, 可以改为对 $k$ 因子分解后二分查找.
可以使用两个数组记录因子分解情况再二分查找, 也可以在二分查找过程中不断分解 $k$.
正整数均有唯一分解形式: $k=\prod p_i^{\alpha_i}$, $p_i$ 为素数.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
typedef unsigned long long uint64;
uint64 pFactNum = 0; // 素因子个数
uint64 prime[20] = {0}, exponent[20] = {0}; // 前19个素数相乘已经非常大了
for (uint64 i = 2; i*i <=k; ++i){
if (k%i == 0){
prime[++pFactNum] = i;
while (k%i == 0){
++exponent[pFactNum];
k /= i;
}
}
}
// 无法分解, 说明k为素数
if (k>1) {
prime[++pFactNum] = k;
++exponent[pFactNum];
}
|
匹配时, $n!$ 中含有素因子个数($\lfloor\frac{n}{p}\rfloor+\lfloor\frac{n}{p^2}\rfloor+…$)应当超过 $k$ 中对应素因子的指数.
1
2
3
4
5
6
|
uint64 primeNum = 0, tmp = n;
// n!中含有k的第i个素因子的个数
while(tmp) {
primeNum += tmp/prime[i];
tmp /= prime[i];
}
|
二分查找时, 中间值满足条件说明在左区间, 不满足则在右区间; 可以使用开区间或闭区间, 但均须保证不重不漏, 并避免死循环.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
int64 left = 1, right = 1e19, mid, ans;
// 闭区间
while (left <= right){
mid = ((right-left)>>1)+left;
if (1){
right = mid-1;
ans = mid;
} else {
left = mid+1;
}
}
// 开区间
while (left+1 < right){
mid = ((right-left)>>1)+left;
if (1){
right = mid;
ans = mid;
} else {
left = mid;
}
}
|
方案数
枚举首项可能会超时, 可以改为枚举项数.
不妨设存在时, 首项为 $a$, 项数为 $m$, 有 $\frac{m(2a+m-1)}{2}=n$, 即 $a=\frac{n-m(m-1)/2}{m}\geq 1$. 故存在时有 $m|n-m(m-1)/2$ 和 $m<\sqrt{2n}$.
哈沙德数
易知 $n=10^k$ 或 $1\leq n\leq 9$ 时会导致死循环, 在HarshadNumber中添加"if (s == 1) return 1;”, 并修改while.
1
2
3
4
5
6
|
int cnt = 0;
if (n == 1) cnt = 1;
while ((n != 0) && (n != 1)) {
n = HarshadNumber(n);
if (n) ++cnt;
}
|
素数
根据题目提示可以得到埃氏筛法, 但埃氏筛法中形如 $p_1…p_k$ 的数会被素数 $p_1,…,p_k$ 反复筛取导致时间较长. 可使用数组存储每个数被筛情况, 即线性筛.
1
2
3
4
5
6
7
8
9
10
11
12
13
|
void prime(uint64 n){
bool isPrime[n+1];
memset(isPrime,1,n+1);
uint64 cnt = 0;
for (uint64 i = 2; i <= n; ++i){
if (isPrime[i]){
for (uint64 j = 2; j*i <= b; ++j){
isPrime[j*i] = false;
if (i%prime[j] == 0) break; // 线性筛
}
}
}
}
|
基思数
可使用循环数组存储数列, 存储时低位在左端, 高位在右端, 从右到左循环遍历.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
int arr[8] = {0}; // 最大位数为8
int len = 0, tmp = n;
while (tmp){
arr[len++] = tmp%10; // 低位在左端, 高位在右端
tmp /= 10;
}
int i = len - 1;
while (arr[i] < n){
int sum = 0;
for (int j = 0; j < len; ++j) {
sum += arr[(i-j+len)%len]; // 从右到左遍历
}
arr[i] = sum;
i = (i-1+len)%len; // 左移
}
|
二进制表示
递归函数实现, 从高位依次取二进制位, 超过范围时进入递归, 设置标识判断何时输出加号.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
bool flag = false;
for (int i = 15; i >= 0 ; --i) {
if ((a>>i)&1) {
if (flag) printf("+");
if (i >= 2){
printf("2(");
binary(i);
printf(")");
}
if (i == 1) printf("2");
if (i == 0) printf("2(0)");
flag = true;
}
}
|
光线追踪
反射经过的三边总长相等(否则无法回到入射点), 即可以通过平移得到等边三角形; 每轮反射时相当于累加更相减损的结果, 或说Euclid算法减去余数部分; 而最终余数为 ${\rm gcd}(n,x)$, 故总长度为 $3(n-{\rm gcd(n,x)})$.
使用"unsigned int".
冰雹数列
最后一位不能有空格.
佩尔数
略.
可变参数累加
1
2
3
4
5
6
7
8
9
10
11
|
#include <stdarg.h>
void func([typename] start, ...){
va_list vaList; // 初始化参数列表
va_start(vaList,start); // 开始参数列表
[typename] curr = start;
while(curr != num){ // 读到num时停止循环
curr = va_arg(vaList,[typename]); // 获取参数列表中下一个参数
}
va_end(vaList) // 结束参数列表
}
|
运动会
以队长为原点构建平面直角坐标系, 观察可得所求即互素对 $(x,y)$, $1\leq x,y\leq N-1$ 个数, 即 $2\sum_{i=1}^{n-1}\varphi(i)+1$. $\varphi(n)$ 为Euler函数, 含义为所有小于 $n$ 且与 $n$ 互素的数的个数.
Euler函数满足如下性质:
- 若素数 $p|n$, 则 $\varphi(pn)=p\varphi(n)$;
- 若素数 $p\nmid n$, 则 $\varphi(pn)=(p-1)\varphi(n)$;
- 若 ${\rm gcd}(m,n)=1$, 则 $\varphi(m,n)=\varphi(m)\varphi(n)$;
- 若 $n=\prod_{i=1}^k p_i^{\alpha_i}$, 则 $\varphi(n)=n\prod_{i=1}^k(1-\frac{1}{p_i})$.
在 $n$ 较小时, 可使用线性筛节省时间; 在 $n$ 较大时, 可使用因式分解节省空间.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
void phiEuler(int n){
int phi[n+1],prime[n+1];
bool isSieved[n+1];
int sum = 0, cnt = 1, comp;
prime[0] = 1;
phi[1] = 1;
for (int i = 2; i < n; ++i){
if (!isSieved[i]){
prime[cnt++] = i;
phi[i] = i-1; // Euler函数性质
}
for (int j = 1; i*prime[j] <= n; ++j){
comp = i*prime[j];
isSieved[comp] = true;
if (i%prime[j] == 0){
phi[comp] = prime[j]*phi[i]; // Euler函数性质
break; // 线性筛
} else{
phi[comp] = (prime[j]-1)*phi[i]; // Euler函数性质
}
}
}
}
|
可变参数平均
1
2
3
4
5
6
7
8
|
void func(int num, ...){
va_list vaList; // 初始化参数列表
va_start(vaList,start); // 开始参数列表
for (int i = 0; i < num; ++i){ // 读取num个后停止循环
[typename] curr = va_arg(vaList,[typename]); // 获取参数列表中下一个参数
}
va_end(vaList) // 结束参数列表
}
|
航空旅行
共三种情况, 三个"if"判断即可.
蒙特卡罗法求积分
随机选取"x = (double)rand()/RAND_MAX * w + a".
采样 $n-1$ 次但除以 $n$. 虽然我也不知道为什么.
飞机起飞速度
目前WA.
稀疏矩阵
满足任一定义, 而非同时满足.
回文数之和
10进制转换为任意进制 (数组每个元素存一位).
1
2
3
4
|
while (tmp) {
kSys[cnt++] = tmp % k;
tmp /= k;
}
|
判断回文数, 可使用双指针.
1
2
3
4
5
|
int head = 0, tail = cnt - 1;
while (head < tail) { // 终止条件
if (arr[head] != arr[tail]) break;
++head, --tail;
}
|
完美矩阵
子矩阵只能为方阵. 暴搜会超时, 使用前缀和.
为方便书写, 数组下标均从 $1$ 开始; 矩阵 $A_{m\times n}$, 将子矩阵记为 $[(x_1,y_1),(x_2,y_2)]$, 意即以元素 $a_{x_1y_1}$ 为左上角元素向右向下的子矩阵 $C_{(x_2-x_1+1)\times(y_2-y_1+1)}$; $s[(x_1,y_1),(x_2,y_2)]$ 表示该子矩阵的元素和.
将输入的 0-1 矩阵变为 1-(-1) 矩阵, 发现此时条件(3)即为 $s[(x_1,y_1),(x_2,y_2)]\in\{-1,0,1\}$, 条件(2)即为 $s[(x_1,y_1),(x_2,y_2)]-s[(x_1+1,y_1+1)(x_2-1,y_1-1)]=2(y_2-y_1+x_2-x_1)$ (行数及列数至少为3时).
1
2
3
4
5
6
7
8
9
10
|
bool isPerfect(int x1, int x2, int y1, int y2) {
int outer = getSum(x1, x2, y1, y2), inner;
int len = 2 * (x2 - x1 + y2 - y1);
if ((x2 - x1) == 1 || (y2 - y1) == 1) inner = 0;
else inner = getSum(x1 + 1, x2 - 1, y1 + 1, y2 - 1);
if (inner != 1 && inner != 0 && inner != -1) return false; // 条件(3)
if ((outer - inner) != len) return false; // 条件(2)
return true;
}
|
而任意一个 $s[(x_1,y_1),(x_2,y_2)]$ 可以由前缀和处理后以 $O(1)$ 的时间复杂度得到.
1
2
3
4
5
6
7
8
9
10
11
12
13
|
void prefix(int n, int m){
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1]
- preSum[i - 1][j - 1] + arr[i][j]; // 容斥原理
}
}
}
int getSum(int x1, int x2, int y1, int y2) {
return preSum[x2][y2] - preSum[x1 - 1][y2] - preSum[x2][y1 - 1]
+ preSum[x1 - 1][y1 - 1]; // 容斥原理
}
|
遍历子矩阵, 选取基点 $(i,j)$, 从基点向右向下扩展 $(k,l)$, 即可保证不重不漏. 发现扩展遍历时遇到元素为 $0$, 该方向的扩展均不可能为完美矩阵 (因为扩展的最外圈总会包含这个 $0$), 由此进行优化.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
int perfectNum(int n, int m) {
int cnt = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
for (int k = 1; k + i <= n && k + j <= m; ++k) {
if (arr[i][k + j] == -1 || arr[k + i][j] == -1) break;
if (isPerfect(i, i + k, j, j + k)) {
++cnt;
}
}
}
}
return cnt;
}
|
波士顿房价预测
直接代入OLS公式, $\hat{b}$ 表示为估计值, $\bar{x}$ 表示为平均值.
$$\hat{b}=\frac{\sum_{i=1}^{n}(x_i-\bar{x})(y_i-\bar{y})}{\sum_{i=1}^{n}(x_i-\bar{x})^2},\
\hat{a}=\bar{y}-\hat{b}\bar{x}.$$
行列式值
使用代数余子式递归或使用Guass消去法化为上三角形.
代数余子式法(按任一行/列展开): $|A_{n\times n}|=\sum_{j=1}^{n}a_{ij}(-1)^{i+j}M_{ij}=\sum_{i=1}^{n}a_{ij}(-1)^{i+j}M_{ij}$.
Guass消去法: 交换 $i,j$ 两行/列 $|A’|\overset{\text{(i,j)}}{=\!=\!=}-|A|$; $i$ 行/列的 $k$ 倍加到第 $j$ 行/列 $|A’|\overset{\text{ki+j}}{=\!=\!=}|A|$; 提取 $i$ 行/列的公因子 $l$, $|A’|\overset{\text{i/l}}{=\!=\!=}\frac{1}{l}|A|$; 特别, 某行/列均为 $0$ 时 $|A|=0$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
int swap(double matrix[MAXSIZE][MAXSIZE], int r1, int r2, int n) {
for (int i = 0; i < n; ++i) {
double temp = matrix[r1][i];
matrix[r1][i] = matrix[r2][i];
matrix[r2][i] = temp;
}
return -1;
}
int pivotAdd(double matrix[MAXSIZE][MAXSIZE], int r, int n) {
for (int i = r + 1; i < n; ++i) {
double pivot = matrix[i][r];
for (int j = 1; j < n; ++j) {
matrix[i][j] -= pivot * matrix[r][j];
}
}
return 1;
}
int pivotFact(matrix[MAXSIZE][MAXSIZE], int r) {
double commonFact = matrix[r][r];
if (commonFact == 0) return 0;
for (int i = r; i < n; ++i) {
arr[r][i] /= commomFact;
}
return commonFact;
}
|
通常来讲, Guass消去法性能更佳.
货运优化
贪心策略. $6,5,4$ 各需要一个包裹, 每4个 $3$ 需要一个包裹; $4$ 和 $3$ 的空余补 $2$; 全部空余补 $1$.
素数筛法
同素数.
字符串替换
目前WA.
删除前后缀
可采用双指针遍历.
大小写交换
直接判断并转换, 或引入头文件"ctype.h".
前后缀移除
遍历(反向遍历)第一行字符串时判断是否在第二行字符串中出现, 并将字符串左移(截断).
1
2
3
|
if (mov) memmove(str - mov, str, strlen(str) - 1); // 左移mov
*(str + strlen(str) - len) = '\0' // 截断len
|
字符串后缀
从"str + strlen(str) - strlen(suffix)“处开始逐字符判断.
Atol转换
跳过空格符.
判断范围可采用"INT_MAX"及"INT_MIN”.
字符串转换为数字.
1
|
num = (str[i] - '0') + num * 10;
|
元宇宙A+B
字符转换.
高精度加法.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#define SACLE 36
char a[100] = "", b[100] = "", c[100] = "";
int A[100] = {0}, B[100] = {0}, C[100] = {0};
void add(void) {
int lenA = strlen(a), lenB = strlen(b);
for (int i = 0; i < lenA; ++i) A[i] = strToDec(a[lenA - i - 1]);
for (int i = 0; i < lenB; ++i) B[i] = strToDec(b[lenB - i - 1]);
int carry = 0;
int lenC = lenA > lenB ? lenA : lenB;
for (int i = 0; i < lenC; ++i) {
C[i] = A[i] + B[i] + carry;
carry = C[i] / SCALE;
C[i] %= SCALE;
}
if (carry != 0) {
C[lenC] = carry;
++lenC;
}
for (int i = lenC - 1; i >= 0; --i) c[i] = decToStr[C[lenC - i - 1]];
c[lenC] = '\0';
}
|
字符串切片
“iter < 0"有"iter -= str(len)”, 余下正常遍历或反向遍历.
分离字符串
“strstr()“找到子串并返回首字符位置, “memcpy()“拷贝并输出, “memmove()“原字符串左移.
Kids A+B
无聊的打表题. 出题人闲着没事干系列
时钟A-B
使用"struct tm”, “mktime”, “difftime”; 差值为负时输出是错的, 但AC.
1
2
3
4
5
|
// 结构体初始化
struct tm timeBegin = {0};
// tm_year: 自1900年起年数
// tm_mon: 从0开始
time_t begin = mktime(&begin);
|
加密字串
减法时额外”(…+26)%26"防止产生负值.
Arduino显示
遍历数字(范围: 0-1111)而非单元数.
有效表达式
同"进出栈序列”, 不妨记左括号为”-1”, 右括号为”+1"; 则变为由 $n$ 个"-1"和 $n$ 个"+1"组合成的合法序列数, 合法含义为所有前缀和 $\geq 0$.
总情况共 $C(2n,n)$ 种, 非法情况共 $C(2n,n+1)$ 种; 即合法序列共 $C(2n,n)-C(2n,n+1)=\frac{C(2n,n)}{n+1}$ 种.
长安
可直接用组合数求解, 也可以使用DFS(深度优先搜索); 但起始点为 $(1,1)$.
1
2
3
4
5
6
7
8
9
10
|
int bx, by, px, py, cnt;
void dfs(int x, int y) {
if ((x == px && y == py) || x > bx || y > by) return;
if (x == bx && y == by) {
++cnt;
return;
}
dfs(x + 1, y);
dfs(x, y + 1);
}
|
GPS通信协议
目前WA.
三元搜索
略. 注意处理死循环.
DNS双螺旋结构
无聊打表题.
PID控制
略.
循环排序
略. 注意处理死循环.