水木清研OJ：http://59.110.82.144/

Acwing：https://www.acwing.com/problem/

20250511

[系统测试] A+B Problem

https://www.smqyoj.com/p/AAA-P1000/solution

这个题确实和其他 OJ 常规签到的 A+B 不一样，需要考虑的点非常多。很快我们就看到了使用高精度以及 __int128_t 数据类型通过本题的同学们了。接下来给大家简单讲解一下各种做法都是怎么做的。

1.常规做法

利用数组模拟高精度运算这个我们就不在这里做赘述了。这里只说使用 g++ 和 msvc 编译器都有的 long long 以及 unsigned long long 就能解决的做法。

输入的整数 $a$ 和 $b$ 虽然在 long long 范围内，但是 $a+b$ 就不一定了。

Case 1

  • 对于一正一负（或者至少一个是 0)，必然不会爆 long long 的范围，所以我们照常输出 $a+b$ 即可。

Case 2

  • $a, b$ 均为正数，$a+b$ 就有可能超过 long long 表示范围上限的 $2^{63}-1$ 导致溢出，此时使用 long long 运算就会输出一个负数。

    在这种情况下我们可以考虑用 unsigned long long。因为两个最大为 $2^{63}-1$ 的正数相加最大为 $2^{64}-2$，不会超出 unsigned long long 的上限 $2^{64}-1$，因此直接强制类型转换计算即可。

Case 3

  • $a, b$ 均为负数，将两者取相反数，还用 unsigned long long 计算，计算结果多输出一个负数即可，这样可以应对一般的情况。

Case 4

  • 最后一组数据为 $a = b = -2^{63}$，两者相加的结果为 $-2^{64}$，这正好是 unsigned long long 无法存储的情况，因此直接**特判**并输出对应值 $-18446744073709551616$ 即可。
#include <stdio.h>
int main()
{
    long long a, b;
    scanf("%lld %lld", &a, &b);
    // a + b 可能超过 long long 最大值 故用必正的 unsigned long long
    if (a >= 0 && b >= 0)
    {
        unsigned long long sum = a + b; 
        printf("%llu\n", sum);
    }
    // 因为一正一非正 故相加不会超过long long范围正常输出即可
    else if (((a > 0 && b <= 0)) || ((a <= 0) && (b > 0)))
    {
        long long sum = a + b; 
        printf("%lld\n", sum);
    }
    // 特判 理由见上
    else if (a == -9223372036854775808ll && b == -9223372036854775808ll)
    {
        printf("-18446744073709551616\n"); 
    }
    // 因为特殊情况已经在上面被讨论 故剩下的可以放开手脚取相反数相加
    else if (a <= 0 && b <= 0)
    { 
        a = -a, b = -b;
        unsigned long long sum = a + b;
        printf("-%llu\n", sum);
    }
    return 0;
}

2.Python 做法

Python 的话和一般的 a+b 无异，原样输出即可。这是因为 Python 的 int 可以表示的范围非常大。

Python 的整数类型与众不同，因为它不设限于固定的字节数。无论是非常大还是非常小的整数，Python 都能够处理，这是因为 Python 内部使用了任意精度的算术。

但是除此之外，Python 在程序设计习题当中几乎没有其他优势。

a, b = map(int, input().split())
print(a + b)

关于input.split()：https://blog.csdn.net/qq_27003337/article/details/104928476

3.我的做法

迷迷糊糊的用了数组大整数加和大整数减，太复杂了

**分析：**对数据类型的范围不熟悉

知识总结

  1. int -2147483648～2147483647

  2. long int -2147483648～2147483647

  3. long long int -9223372036854775808～9223372036854775807

相应的无符号类型的各自表示范围为：

  1. unsigned int 0～4294967295

  2. unsigned long int 0～4294967295

  3. unsigned long long int 0～18446744073709551615

同理，

  1. __int64 -9223372036854775808～9223372036854775807

  2. unsigned __int64 0～18446744073709551615

  1. int -2147483648～2147483647

  2. long int -2147483648～2147483647

  3. long long int $-2^{63}$～$2^{63}-1$

相应的无符号类型的各自表示范围为：

  1. unsigned int 0～$2^{32}-1$

  2. unsigned long int 0～$2^{32}-1$

  3. unsigned long long int 0～$2^{64}-1$

同理，

  1. __int64 $-2^{63}$～$2^{63}-1$

  2. unsigned __int64 0～$2^{64}-1$

[系统测试] A/B Problem

关于c++如何控制输出小数的位数：

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
    double num = 3.14159265358979323846;
    cout << fixed << setprecision(2) << num << endl;  // 输出结果为 3.14
		printf("%.6lf \n", num);  // 也可以用printf，输出结果为 3.141592
    return 0;
}

在上面的例子中，使用了 fixed 和 setprecision() 函数来控制输出小数的位数。fixed 指定小数点后的位数固定，setprecision(2) 指定输出两位小数。
注意：使用 setprecision() 函数时，必须包含头文件#<iomanip>。

如果不加 fixed，setprecision() 函数会控制有效数字的位数，而不是小数点后的位数。 例如，代码如下：

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
    double num = 123.456789;
    cout << setprecision(4) << num << endl;  // 输出结果为 123.5

    return 0;
}

如果不加 fixed，setprecision(4) 会控制输出的有效数字为 4 位，因此会四舍五入取到小数点后一位，输出结果为 123.5。如果加上 fixed，就会控制小数点后的位数，输出结果为 123.4568。

知识总结

scanf中的格式控制

数据类型 格式符 举例
int %d scanf(“%d”, &n);
long long %lld scanf(“%lld”, &n);
float %f scanf(“%f”, &f);
double %lf scanf(“%lf”, &db);
char %c scanf(“%c”, &c);
字符串 (char 数组) %s scanf(“%s”, str);

printf中的格式控制

数据类型 格式符 举例
int %d printf(“%d”, n);
long long %lld printf(“%lld”, n);
float %f printf(“%f”, f);
double %f printf(“%f”, db);
char %c printf(“%c”, c);
字符串 (char 数组) %s printf(“%s”, str);

在 printf 中，无论是 float 类型还是 double 类型，输出都需要用 %f，在有些系统中用 %lf 也不会出错，但是尽量还是按照标准来。

20250512

CSP#P2013002. [CSP201312] ISBN号码

总结

数组空间开大一点（定义的时候多定义几个）！

可以用STL容器。

#include<iostream>

using namespace std;

int main() {
    char a[14]; // 为了 '\0' 多给一个位置所以开了14，如果定义为char a[13]，在一些OJ会报错……
    int b[10];
    cin >> a;
    int j = 0;
    for (int i = 0; i < 13; i++) {
        if (a[i] == 'X') {
            b[j++] = 10;
        } else if (a[i] <= '9' && a[i] >= '0') {
            b[j++] = a[i] - '0';
        }
    }
    int sum = 0, i = 1;
    j = 0;
    while (j < 9) {
        sum = sum + b[j++] * (i++);
    }
    sum = sum % 11;
    int output;
    if (sum == b[9]) {
        cout << "Right" << endl;
    } else {
        for (int i = 0; i < 12; i++) {
            cout << a[i];
        }
        if (sum == 10) {
            cout << 'X' << endl;
        } else {
            cout << sum << endl;
        }
    }
    return 0;
}

20250513

动态规划-DP

  • 状态表示

  • 状态计算

graph TD
    A[动态规划] --> B["状态表示F[ i ]"]
    A --> C[状态计算]

时间复杂度：状态数量*计算每个状态所需的时间

3304.数字三角形

graph TD
    A[动态规划] --> B["状态表示F[ i , j ]"]
    A --> C[状态计算]
    B --> D["集合：所有从起点走到( i , j )的路径长度"]
    B --> E[Max]

1490.最长上升子串

graph TD
    A[动态规划] --> B["状态表示F[ i ]"]
    A --> C[状态计算]
    B --> D["集合：所有以第i个数结尾的上升子序列"]
    B --> E[Max]

时间复杂度： $O(n^2)$

首先考虑使用暴力遍历解答，逐个删除某个数字然后双指针统计上升子串的长度。
过程中我们会发现，如果删除该元素 对于上升子串没有提升的长度 则可以考虑剪枝。
对于上升子串没有提升的长度的定义呢 就是该数字的左边的数小于该数字右边的数。
那么进一步的优化，如果我们首先统计以该数字为结尾和以该数字为开始 的上升子串的长度，
可以减少不少的计算量。

类似如此
a b c d 如果我们实现统计了 以各个元素为结尾的最长上升子串长度 ai bi ci di
统计了 以各个元素为起始的最长上升子串长度 aj bj cj dj.

那么如果 a < c 我们可以尝试删除b，得到子串长度就是 ai+bj;
但如果b < d 我们可以尝试删除c，得到的子串长度就是bi+dj;

参考代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int a[N], f[N], g[N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

    // 预处理f[i]：以i结尾的单调上升子串的最大长度
    for (int i = 1; i <= n; i ++ )
        if (a[i] > a[i - 1]) f[i] = f[i - 1] + 1;
        else f[i] = 1;

    // 预处理g[i]：以i开头的单调上升子串的最大长度
    for (int i = n; i; i -- )
        if (a[i] < a[i + 1]) g[i] = g[i + 1] + 1;
        else g[i] = 1;

    int res = 0;
    // 枚举删除哪个数
    for (int i = 1; i <= n; i ++ )
        if (a[i - 1] >= a[i + 1]) res = max(res, max(f[i - 1], g[i + 1]));
        else res = max(res, f[i - 1] + g[i + 1]);

    printf("%d\n", res);

    return 0;
}