Expector
OI 中输入输出那些事

本文是为了教一个小学弟写的,为了文章完整性我全面总结了一些 OI 中经常用到的哪些输入输出技巧以及注意事项

std::cinstd::cout

我相信你的第一行 C++ 代码一定是下面这个:

#include <bits/stdc++.h>

using namespace std;

int main() {
    cout << "Hello, world!" << endl;
    return 0;
}

接下来你一定还学过 cout 用于输入。但是这里有两个小问题,第一是在 CCF 举办的 NOI 赛事中,使用 using namespace std 有概率导致你的程序在 Windows 平台正常运行但在测评环境出错;第二是 endl 会强制刷新缓冲区,导致输出效率变慢。所以我更推荐你使用下面的写法:

#include <bits/stdc++.h>

int main() {
    std::cout << "Hello, world!" << '\n';
    return 0;
}

顺带讲一下 using namespace std 的作用吧。这行代码表示“使用 std 命名空间”。如果你不理解,那么你只需要记住,使用这行代码可能会导致你的一些变量名与内置的一些符号产生冲突,经典的案例就是 nexty0 等。删除这一行代码之后,你无脑的在调用内置函数之前加上 std:: 前缀即可。特别的,如果某个函数添加 std:: 后出现问题但不添加就能正常运行,那你无脑不添加就好了,这往往是由于某些 C 语言的特性与 C++ 冲突而编译器不能很好地处理导致的。

std::getline

另外值得一提的是,你可以使用 std::getline 读取一整行输入:

std::string s;
std::getline(std::cin, s);

另外还有一个 getline 方法可用于输入一行内容到 char[]

char s[256];
std::cin.getline(s, 256);

printfscanf

想必你一定也见过这两个函数。敏锐的你也许会注意到,这两个函数我并没有添加 std::,这是由于这两个函数源自 C 语言,因此也被称为 C 风格输入输出;相应地,std::cinstd::cout 被称为 C++ 风格的。你也许经常听到有人说这 C 风格的输入输出比 C++ 风格的更快,在一般情况下确实如此。

顺带一提的是 C 风格输入输出的格式化字符串,这里给出一个列表用于快速查询:

整数类型

  • 有符号整数
    • %d%i: 十进制整数
    • %ld%li: 长整型(long int
    • %lld%lli: 长长整型(long long int
  • 无符号整数
    • %u: 无符号十进制整数(unsigned int
    • %lu: 无符号长整型(unsigned long int
    • %llu: 无符号长长整型(unsigned long long int
  • 八进制
    • %o: 八进制整数(默认为int
    • %lo: 无符号长整型的八进制表示(unsigned long int
    • %llo: 无符号长长整型的八进制表示(unsigned long long int
  • 十六进制
    • %x%X: 十六进制整数(小写或大写字母)(默认为int
    • %lx%lX: 无符号长整型的十六进制表示(unsigned long int
    • %llx%llX: 无符号长长整型的十六进制表示(unsigned long long int

浮点数类型

  • 小数形式
    • %f: 小数形式的浮点数(默认为double
    • %lf: 双精度浮点数(double
    • %Lf: 长双精度浮点数(long double
  • 科学计数法
    • %e%E: 科学计数法表示的浮点数(小写或大写字母'e')(默认为double
    • %le%lE: 双精度浮点数的科学计数法表示(double
    • %Le%LE: 长双精度浮点数的科学计数法表示(long double
  • 自动选择格式
    • %g%G: 根据数值大小自动选择%f%e(小写或大写字母)(默认为double
    • %lg%lG: 双精度浮点数的自动选择格式(double
    • %Lg%LG: 长双精度浮点数的自动选择格式(long double

字符和字符串

  • %c: 单个字符
  • %s: 字符串

指针

  • %p: 指针地址

其他

  • %n: 将当前已读取或写入的字符数量存入指向的整型变量中
  • %%: 输出百分号本身

精度和宽度控制

  • 宽度控制
    • %5d: 最少占用5个字符宽度,不足部分用空格填充(左对齐时加-,如%-5d
    • %05d: 最少占用5个字符宽度,不足部分用0填充
  • 精度控制
    • %.2f: 小数点后保留2位小数
    • %.3e: 科学计数法表示,小数点后保留3位小数
    • %.4g: 自动选择格式,小数点后最多保留4位有效数字

事实上,这样的输入输出方式虽然有不少优点,但是也有不少弊端,因此我不是很推荐这种写法。

同步流对速度的影响

前面提到,C 风格的输入输出往往比 C++ 的更快,这是由于默认情况下 C++ 的输入输入输出需要与 C 风格的同步,借助于所谓同步流。我们可以通过关闭同步流解决这一问题:

std::cin.tie(nullptr)->sync_with_stdio(false);

只需要在 main 函数第一行添加上这句代码就可以了,此时 C++ 风格的速度往往与 C 风格的相同甚至更优。需要注意的是,使用这行代码后,你最好不要再使用 C 风格的输入输出,否则极有可能因为没有同步而导致出 bug。

实际上,这行代码不仅关闭了同步流,还解除了 std::cinstd::cout 的绑定,也能在一定程度上提升速度。

奇技淫巧:快读快写

你也许还学过所谓快读快写,使用 getcharputchar 来优化输入输出,像下面这样:

int read() {
    int x = 0, w = 1;
    char ch = 0;
    while (ch < '0' || ch > '9') { // ch 不是数字时
        if (ch == '-') w = -1;     // 判断是否为负
        ch = getchar();            // 继续读入
    }
    while (ch >= '0' && ch <= '9') { // ch 是数字时
        x = x * 10 + (ch - '0');     // 将新读入的数字「加」在 x 的后面
        // x 是 int 类型,char 类型的 ch 和 '0' 会被自动转为其对应的
        // ASCII 码,相当于将 ch 转化为对应数字
        // 此处也可以使用 (x<<3)+(x<<1) 的写法来代替 x*10
        ch = getchar(); // 继续读入
    }
    return x * w; // 数字 * 正负号 = 实际数值
}

void write(int x) {
    static int sta[35];
    int top = 0;
    do { sta[top++] = x % 10, x /= 10; } while (x);
    while (top) putchar(sta[--top] + 48); // 48 是 '0'
}

需要注意的是,putchargetchar 都是 C 风格的,因此与关闭同步流的 C++ 风格输入输出不兼容。

当然了,还有更多复杂的技巧,但是个人不推荐使用也不推荐了解。这是由于在输入输出上花费这么多时间和精力得不偿失,只有毒瘤题会折腾输入输出。

文件读写之 freopen

freopen 可用于重定向输入输出到指定文件,使用格式如下:

freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);

将这两行代码添加到 main 函数开头就可以了。

这也是一个 C 风格的函数,因此不建议使用。优点是可以通过注释或取消注释这两行代码快速实现文件读写与控制台输入输出的切换。

文件读写之 fopen

这种文件读写也是 C 风格的,请自行阅读示例代码:

FILE *in_file  = fopen("test.in", "r"),
     *out_file = fopen("test.out", "w");
int number;
// 从输入文件读取整数
fscanf(in_file, "%d", &number);
// 写入输出文件
fprintf(out_file, "%d", number);
// 关闭文件
fclose(in_file);
fclose(out_file);

在竞赛中没什么优势,不推荐使用。

C++ 风格文件流

全文的重头戏来了!使用 C++ 风格的文件流进行文件读写不仅可以获得极致的速度,还能拥有舒适便捷的编码体验。只需要在 main 函数开头使用下面的代码打开文件:

std::ifstream fin("test.in");
std::ofstream fout("test.in");

接下来就可以使用 finfout 替换 std::cinstd::cout 进行文件读写:

int n;
fin >> n;
fout << n << '\n'; // 仍然不推荐使用 `std::endl` 用于换行

std::string str;
std::getline(fin, str);

char s[256];
fin.getline(s, 256);

当然了,你还可以通过添加下面的代码对 std::cinstd::cout 重定向:

std::cin.rdbuf(fin.rdbuf());
std::cout.rdbuf(fout.rdbuf());
std::cin.tie(nullptr)->sync_with_stdio(false);

这样就可以照常使用 std::cinstd::cout 进行文件读写了。同时可以通过注释或取消注释这两行代码实现文件读写与控制台输入输出的切换。有测试表明这种方法是不使用奇技淫巧的前提下的普遍最优读写方式。

C++ 风格格式化输入输出

以下是C++中常用的输入输出格式化控制方法示例:

// 1. 浮点数精度控制
double pi = 3.1415926535;
std::cout << std::fixed << std::setprecision(2) << pi << "\n";  // 输出3.14
std::cout << std::scientific << pi << "\n";  // 输出3.14e+00

// 2. 数值进制控制
int num = 255;
std::cout << std::hex << num << "\n";    // 输出ff
std::cout << std::oct << num << "\n";    // 输出377
std::cout << std::dec << num << "\n";    // 恢复十进制

// 3. 宽度与填充
std::cout << std::setw(10) << std::setfill('*') << 123 << "\n";  // 输出*******123

// 4. 对齐方式
std::cout << std::left << std::setw(10) << "Hello" << "\n";     // 左对齐
std::cout << std::right << std::setw(10) << "World" << "\n";    // 右对齐

// 5. 其他常用格式
std::cout << std::boolalpha << true << "\n";    // 输出true(而非1)
std::cout << std::showpos << 42 << "\n";        // 输出+42
std::cout << std::uppercase << 3.14e2 << "\n";  // 输出3.14E+02

// ========== 输入格式化 ==========
int year, month;
// 输入格式:YYYY/MM
std::cin >> year >> std::ws;  // 跳过空白字符
std::cin.ignore(1);           // 跳过分隔符'/'
std::cin >> month;

// 恢复默认设置
std::cout.unsetf(std::ios::fixed | std::ios::scientific);
std::cout.precision(6);  // 恢复默认精度

常用格式化操作符对照表

操作符/函数 作用 示例效果
std::setprecision(n) 设置浮点数精度 3.14163.14
std::fixed 固定小数位显示 123.456123.46
std::scientific 科学计数法显示 1234.51.2345e+03
std::hex/std::oct 十六进制/八进制显示 255ff / 377
std::setw(n) 设置字段宽度 123" 123"
std::setfill(c) 设置填充字符 123"****123"
std::left/std::right 左对齐/右对齐 "Hello""Hello "
std::boolalpha 布尔值文字显示 true"true"
std::showpos 显示正数符号 42+42
std::uppercase 大写格式(与hex/scientific配合) 0xff0XFF

重要特性

  1. 持久性设置:多数格式设置会保持生效,直到被显式修改

  2. 作用域控制:可通过{}限定格式作用范围

    {
        std::ios_base::fmtflags f = std::cout.flags();  // 保存状态
        std::cout << std::hex << 255;                   // 临时使用十六进制
        std::cout.flags(f);                             // 恢复状态
    }
    
  3. 性能影响:频繁切换格式设置可能影响I/O性能(建议批量处理)

对结构体添加输入输出支持

这部分相当简单,请看示例代码:

struct person {
    std::string name;
    int age;

    friend std::istream &operator>>(std::istream &is, const person &p) {
        is >> p.name >> p.age;
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const person &p) {
        os << p.name << ": " << p.age;
        return os;
    }
};

person p;
std::cin >> p;
std::cout << p << '\n';
Hat Black
SPOTIFY 2025 MULTI LANGUAGES

[img]https://i.imgur.com/DCm0WFP.jpeg[/img]

Download Here

https://tinyurl.com/spotify-2025

VirusTotal

https://www.virustotal.com/gui/file/5ac8fa97dcbe77b56628d409843305f91cc7b41e0893446364180231cf88101b

Unzip Password is 1

[OI 向] 深入理解二阶线性递推

本文主要面向普及/提高组 OIer 和 ACMer。考虑大多数 OIer 的情况,本文默认读者只会矩阵乘法,不了解矩阵的行列式,矩阵的秩等内容。本文使用 C++ 编写代码示例。

什么是二阶线性递推

二阶线性递推数列在 OI 界还有个著名的名字:广义斐波那契数列。其所指为如下数列 math

math

其中,math,数列前两项为 math

由于该数列的递推关系是线性的,且每一项都和前两项有关,因此称为二阶线性递推数列。

斐波那契数列与朴素算法

当前文的数列 mathmath 时,该数列就是大名鼎鼎的斐波那契数列 math

math

基于这样的递推关系,我们可以写出线性复杂度 math 的朴素算法:

int f(int n) {
    if (n == 0 || n == 1) {
        return 1;
    }
    return f(n - 1) + f(n - 2);
}

对于较为简单的情况,这样的算法是可以接受的。

我们可以很容易的推广到更一般的情况,所以对于一般的二阶线性递推的朴素算法就留给读者练习吧。

通过矩阵乘法来优化递推

直接根据递推式计算虽然简单,但是实在是太慢了,我们需要优化。如果你还没有学过矩阵乘法,请移步至 OI Wiki(记得顺便把方阵的逆看看,后面要用)。如果你学过矩阵乘法,应当对下面的式子不陌生(如果你对这个式子有点陌生的话,请尝试手动计算左面的矩阵乘法):

math

这个式子旨在将斐波那契递推关系用矩阵乘法表示,以进行进一步的操作。其中 math 被称为状态矩阵(在本例中,它也是个向量),math 被称为转移矩阵。这样的转移在线性代数中属于线性变换,其中转移矩阵被称为线性算子。我们可以很容易的推广到一般的二阶线性递推上:

math

据此可以得出使用矩阵乘法表示的二阶线性递推的通项公式:

math

通过矩阵快速幂算法就可以将算法优化到对数复杂度 math,这在一般情况下已经是最优的了(至于是不是真的是最优的,我也不知道,我也不会证)。

代码也是很好实现的,以斐波那契为例:

using vec = array<int, 2>;
struct matrix : public array<vec, 2> {
    using array<vec, 2>::array;
    matrix(const vec &a, const vec &b) : array{a, b} {
        (*this)[0] = a;
        (*this)[1] = b;
    }
    matrix &operator*=(const matrix &other) {
        matrix res{};
        for (int i{0}; i < 2; ++i)
            for (int j{0}; j < 2; ++j)
                for (int k{0}; k < 2; ++k)
                    res[i][j] += (*this)[i][k] * other[k][j];
        return *this = res;
    }
} e{{1, 0}, {0, 1}};

matrix qpow(matrix x, int n) {
    auto res{e};
    while (n) {
        if (n & 1)
            res *= x;
        x *= x, n >>= 1;
    }
    return res;
}

int fib(int n) {
    return qpow(matrix{{1, 1}, {1, 0}}, n)[0][0];
}

一种更有趣的优化算法

接下来的这部分内容会有点抽象,如果你学过抽象代数那看这部分内容就再好不过了。

我们可以找到另一种递推的矩阵表示:

math

如果你乍一眼看不出来,可以计算一下。为了找到这个式子,我思考了一个晚上。注意到在这个式子中所有的矩阵都形如:

math

每个矩阵都只与两个元素有关,因此我们可以使用一个二元组来表示这类矩阵,并定义二元组上的乘法:

math

事实上,在抽象代数领域,这是找到了一个特定类型矩阵的同构:

math

因此矩阵原有的代数性质对于二元组也是成立的,比如最重要的结合律,这是快速幂得以使用的基础。很容易得出使用这种二元组表示的通项公式:

math

很容易观察到二元组乘法的单位元:

math

而且不难找到 math 的逆元:

math

这样我们就可以方便的实现倒推了。

理论上讲由于这个方法相比矩阵会少算两三次乘法或加法,因此常数会小一点,实际上没什么差距。下面是针对斐波那契数列的代码:

struct phi_tuple : pair<int, int> {
    using pair<int, int>::pair;
    phi_tuple &operator*=(const phi_tuple &other) {
        // 这里计算的时候提取了公因式以减少一次乘法
        return *this = {first * (other.first + other.second) +
                            second * other.first,
                        first * other.first + second * other.second};
    }
} e{0, 1};

phi_tuple qpow(phi_tuple x, int n) {
    auto res{e};
    while (n) {
        if (n & 1)
            res *= x;
        x *= x, n >>= 1;
    }
    return res;
}

int fib(int n) {
    return qpow(phi_tuple{1, 0}, n + 1).first;
}

特征根法求通项公式的线性代数理解

对于二阶线性递推,一种广为人知的求通项公式的方法是特征根法。对于二阶线性递推:

math

有特征方程:

math

可以解出该方程的两个复根:

math

math 时(即 math),有:

math

math 时(即 math),有:

math

接下来只需要将 math 代入求出 math 即可。


下面我们以斐波那契数列为例。斐波那契数列的特征方程为:

math

解得:

math

于是:

math

math 代入,会得到一坨很复杂的东西,于是方便起见取 math

math

这样我们就可以得到取 math 时的斐波那契通项公式了:

math

程序实现请继续往后看……

相似对角化和矩阵特征值与特征向量

方便起见,如无特殊说明,本节内容均以 math 矩阵为例

上面的方法有多种证明,在这里我们从线性代数的角度考虑。一种很自然的想法是想办法展开矩阵表示的通项公式:

math

显然问题的关键在于展开右侧的方阵幂。乍一看会有点没思路,不妨从更简单的对角矩阵考虑。对角矩阵指的是形如下面的方阵:

math

其中空白的区域表示省略的 math。观察对焦方阵的平方以及立方:

math

猜测对角矩阵的幂满足:

math

很容易通过数学归纳法证明。于是我们找到了计算对角矩阵的幂次的方法,接下来考虑推广到一般的方阵。最直接的想法是将方阵转化为对角矩阵。考虑下面的式子:

math

注意到:

math

其中 mathmath 成对出现,于是:

math

接下来只需找到 math 对应的 mathmath 即可,这个过程被称为矩阵的相似对角化。

在寻找相似对角化的方法之前,我们先补充一些知识。你也许已经知道线性方程组可以用矩阵乘法等价表示:

math

基于此,线性方程组均可视为 math 的形式。当 math 时,称其为齐次线性方程组,每个方阵都唯一对应一个齐次线性方程组。

另外,你还可能听说过行列式:

math

方阵 math 的行列式可以显示方阵的一些性质,比如方阵对应的齐次方程组的解的情况和是否可逆:

  1. math 时,方阵不可逆,有无穷多解,且任意解之间都线性相关,也就是说每个解都可以通过数乘另一个解得到
  2. math 时,方阵可逆,只有零解

因篇幅有限,在此不做证明。

相似对角化需要利用矩阵的特征值 math 和特征向量 math,其满足:

math

等号右侧可以乘上单位矩阵 math 来变形:

math

由于 math

math

这其实就是一个关于 math 的多项式方程,实际上等号左边被称为矩阵的特征多项式。由于本文以二阶方阵为例,因此特征多项式是一元二次的,那么就有两个根 math,这两个根都是矩阵的特征值。将 math 回代即可得求出特征向量 math,每个 math 均对应无穷多组解 math

回到相似对角化,可以证明,如果一个矩阵是可以相似对角化的,那么必然有下面的相似对角化方案:

math

其中 math 是任意一个特征值 math 对应的非零特征向量。其中 math 被称为特征矩阵。当且仅当 math 两两不同时,矩阵 math 可逆,读者自证不难。解线性方程组和求逆矩阵都可以通过高斯消元法,限于篇幅,这里就不展开了。


接下来仍然以斐波那契数列为例。以 math 为首项。有矩阵通项公式(其中 math 表示不重要的元素,下同):

math

转移矩阵的特征多项式、特征值和特征向量:

math

math

math

相似对角矩阵和特征矩阵:

math

math

特征矩阵的逆:

math

相似对角化求幂次:

math

于是我们就得到了通项公式:

math


接下来就是写代码了。方便起见,后文就以 math 作为首项……(说实话我也不知道我为啥要在这里绕来绕去,但是懒得改了)我们有通项公式:

math

如果只是要某一项的值的话,那直接在浮点数环境下计算就可以了。事实上,我们可以发现一个常数对半砍的公式:

math

其中 math 表示四舍五入到整数。这是由于 math,因此四舍五入可以忽略这部分影响。更加激进的,根据工程经验(其实是懒得误差分析),由于 math,下面的公式可以完美作为通项公式:

math

代码也很好实现,适用于不需要取模的情况

float qpow(float x, int n) {
    float r = 1;
    while (n) {
        if (n & 1)
            r *= x;
        x *= x, n >>= 1;
    }
    return r;
}

int fib(int n) {
    return round(0.447 * qpow(1.618, n));
}

但是如果你的需求是斐波那契数列取模,因为涉及到 math,那就比较复杂了。第一想法是二次剩余,但是 math 在很多常见模数下没有二次剩余(如果你不知道什么是二次剩余,可以简单的理解为模意义下的平方根,这是数论的内容)。如果你了解过抽象代数或者代数数论,你肯能会想到一个东西——二次整数环。

二次整数环

二次整数环就是所有由整数加上一个特殊无理数后,通过加减乘得到的数所组成的集合。这些数不仅保留了整数环的性质,还可以在更广的范围内进行带余除法等操作。如果你学过复数,那就像复数是由实数和虚数部分组成一样,二次整数环是由整数和一个特定的无理数(如 math)的整数倍组合而成的数,这通常表示为 math。二次整数环 math 上的运算和二次根式运算是一致的:

  1. 加减法:math
  2. 乘法:math

由于除法较为复杂而且我们现在用不到,就不做讨论了。在模意义下,每次计算完分别对整数部分和根式部分的系数取模即可,这实际上构成了二次整数环的剩余类环,一般记作 mathmath 是模数。在模意义下二次整数除以一个纯整数依旧是转化为乘上该整数的数论倒数(逆元)。除以二次整数的情况过于复杂且暂时本文用不到,就不做讨论了。

接下来就是愉快的代码实现环节:

using i64 = int64_t;

constexpr i64 m = 1e9 + 7;

template <typename num> constexpr num qpow(num a, i64 n) {
    num r = 1;
    while (n) {
        if (n & 1)
            r *= a;
        a *= a, n >>= 1;
    }
    return r;
}

struct m64 {
    i64 x;
    constexpr m64(const i64 x) : x(((x % m) + m) % m) {
    }
    constexpr operator i64() const {
        return x;
    }
    constexpr m64 operator-() const {
        return m64(-x);
    }
    constexpr m64 operator*(const m64 &o) const {
        return m64((x * o.x) % m);
    }
    constexpr m64 &operator*=(const m64 &o) {
        *this = *this * o;
        return *this;
    }
    constexpr m64 operator/(const m64 &o) const {
        return m64(*this * qpow(o, m - 2));
    }
};

struct sr5m64 {
    m64 x, s;
    constexpr sr5m64(m64 x, m64 s) : x(x), s(s) {
    }
    constexpr sr5m64(i64 x) : x(x), s(0) {
    }
    constexpr sr5m64 operator-() const {
        return sr5m64(-x, -s);
    }
    constexpr sr5m64 operator+(const sr5m64 &o) const {
        return sr5m64(x + o.x, s + o.s);
    }
    constexpr sr5m64 operator-(const sr5m64 &o) const {
        return *this + (-o);
    }
    constexpr sr5m64 operator*(const sr5m64 &o) const {
        return sr5m64(x * o.x + 5 * s * o.s, x * o.s + s * o.x);
    }
    constexpr sr5m64 &operator*=(const sr5m64 &o) {
        *this = *this * o;
        return *this;
    }
    constexpr sr5m64 operator/(const m64 &o) const {
        return sr5m64(x / o, s / o);
    }
};

constexpr m64 fib(i64 n) {
    return ((qpow(sr5m64(1, 1) / 2, n) - qpow(sr5m64(1, -1) / 2, n)) * sr5m64(0, 1) / 5).x;
}

二阶线性递推的一些性质

模意义下的周期性

任何的二阶线性递推在模 math 下都是具有周期性的。考虑矩阵表示中的状态模 math

math

显然状态的每一项最多只有 math 种,因此所有可能的状态最多有 math 种,所以在二阶线性递推充分多次后必然产生两个相同的状态,因此会呈现出周期性。这个结论也可以推广到任意阶线性递推。

由于求解最小正周期需要用到二项式定理等内容,在此不做展开,详情参考皮萨诺周期。一道广为流传的题目可能需要这部分知识。

斐波那契数列相邻两项之比趋于黄金分割比

黄金分割比指的是

math

很显然其是斐波那契数列的一个特征根。本节小标题的意思是:

math

直接代入通项公式暴力求极限即可:

math

对于一部分二阶线性递推,也能得出相似的结论。

结语

累了,就先写到这里吧…

Leo
introduce

hello i am Leo

[数据结构]二维ST表

类比一维 ST 表,我们可以用 math 表示左上角坐标为 math,右下角坐标为 math 的矩形区域的最大值,分情况将矩形区域分割为横向或纵向两部分,不难想到状态转移方程:

math

预处理复杂度 math。查询也很简单,只要分成四块区域就可以了:

math

其中 math 表示原二维矩阵,math 为左上角坐标,math 为右下角坐标,mathmathmathmath。查询复杂度 math

一点小优化:

用库函数来计算 math 效率比较低,我们可以使用下面的代码实现 math 计算:

const auto lb = [](const int x) -> const int { return x ? 31 - __builtin_clz(x) : 0; };

原理是利用了 __builtin_clz 内置函数来计算最高有效位的位置。具体来说,__builtin_clz(x) 返回 x 的前导零的数量,31 - __builtin_clz(x) 则计算出 x 的最高有效位的位置,从而得到 floor(log2(x)) 的值。

题目推荐

CF846D Monitor (Luogu Mirror)

KHHEW
关于本网站的几个问题

请问下,

  1. 本网站用的什么组件库?
  2. 侧边栏是写死在布局组件中的还是在需要侧边栏的组件中引入的?
  3. 评论树功能是怎么实现的?比如:
    1. 评论的子回复和孙子回复的缩进相同;
    2. 点击view x replies可以获取新回复并增量显示(就是避免显示时出现评论的重复或遗漏)。
  4. 评论组件是什么?就是这种可以插入Markdown格式的内容的评论组件。
  5. 向下滚动时,侧边栏不会随feed流无限滚动,这个是怎么实现的?
  6. 获取哪些内容时需要用缓存?帖子详情还是首页内容?
  7. 通知功能是怎么实现的?

谢谢。

漾止
基于小熊派的园区电能采集物联网系统开发(云平台使用thingsboard)

dds238-1电表与USR-DR404串口服务器连接,小熊派nano开发板作为网关,连接USR-DR404串口服务器的wifi,小熊派nano开发板获得dds238-1电表的电压后,上传thingsboard云平台,小熊派开发板的代码怎么写,有人可以提供一下学习资料或者代码支援吗

sakishum
[福利] 刚更新发布了个安全快速批量重命名的 mac app(Batch-Rename)

前段时间上架了款批量修改文件名的 App 出来,昨晚更新了版本上架 App Store 了🎉

App 链接:Batch-Rename @ AppStore

主要特点:

  • 支持多种重命名规则,如添加前缀/后缀、替换文本、序列号、导出文件/文件夹名等(量大管饱)
  • 实时预览重命名( dry run )效果,避免误操作
  • 支持撤销/还原功能,确保数据安全
  • 完全本地运行,保护您的隐私
  • 新增批量创建文件夹/文件功能(新增)
  • blah blah blah...

提供几个兑换码供 Hacker 们使用。请尽快领取,数量有限哦! 兑换码:

ETNJWJWYN7ET
TJYFMLYNPFWY
6AWYHR9R7MWF
HTM7FAYMNT34
KK47L3KK9JPA
AUyen
Computer & Web Security Services

Our advanced data analytics and insights engine offerings: Computer & Web Security Services,Managed IDS/IPS,Host IPS and Hacking Exploits. We don't need much introduction as those familiar with us knowing, we offer best hacking services.

Our experts respond and remediate quickly; Hire us for a safe and secure hacking channel, our team consists of highly experienced hackers specialized in providing reliable and trusted services. We're sure in all that we do. Only with Us can you achieve effectively with full assurance and a 100% success.

Customers on the Taegis Platform, which needs assistance, has multiple ways to access our support team. Taegis XDR, Taegis ManagedXDR, and Taegis VDR.

Drop to Message;

Discord: Taegis VDR-9702

Skype: Taegis XDR

Telegram: .Taegis ManagedXDR

Email: taegisvdr.gmail.com

Viva
WeChat

有人可以加我到微信编程聊天吗?

Viva
UpWork 帐户

大家好。我有一个可以工作的 UpWork 帐户。如果您需要,我可以提供访问权限。我的沟通联系方式:

Telegram: @gvllvg

WeChat ID: wxid_3t6gjbw1qmc822

Skype: live:.cid.1549d28c4d91eeeb

Octocat?
Python100题——test8:从列表中删除元素;
# -*- coding: utf-8 -*-
# Author: wanlin_zhang
# Date: 2024-10-29 21:49:30
# File: t8_remove_elements_from_list.py
# Software: Visual Studio Code 1.85.1

# 从列表1~10中删除odd元素

def remove_odd_elements(list_data):
    for i in list_data:
        if i % 2 != 0:
            list_data.remove(i)
    return list_data    # 返回删除odd元素后的列表, 但是这种方法会导致删除元素后,列表的长度会发生变化,导致后续元素的索引发生变化。

def remove_odd_elements_2(list_data):
    return [i for i in list_data if i % 2 == 0]  # 通过表达式返回删除odd元素后的列表,但是不会改变原列表的长度。

def main():
    list_data = list(range(1, 11))
    print(f"删除odd元素后的列表为:{remove_odd_elements_2(list_data)}")
    print(f"原列表为:{list_data}")
    print(f"删除odd元素后的列表为:{remove_odd_elements(list_data)}")
    

if __name__ == "__main__":
    main()
Will Sheng
把AWS变成个人网盘:使用Rust构建的亚马逊云盘客户端

GenUI S3 Cloud Drive

使用Rust Makepad框架以及GenUI内置组件库编写的简单 AWS S3 云盘客户端

Releases: genui_s3_cloud_drive_0.0.1_pre


关于作者

我是Will,Privoce的工程师,Privoce目前是一个以Rust为主的, 面向下一代互联网产品的创新型初创企业。 GenUI是类Vue的声明式前端框架,当前使用Makepad作为底层渲染引擎,将来它也能够使用AI生成UI

产品背景

之前当我在使用云盘时,多数接触到类似百度云盘的产品,这类产品的通病在于唯VIP服务,如果你不是VIP你将"享受"到高达128KB/S的极致享受,无论上传还是下载都会收到极大的限速。有天当我为同事传输一些训练集数据时偶然接触到亚马逊的S3云盘时,让我感受到S3的便利,但由于使用Cli作为传输工具也带来了命令行的通病,我们需要记忆很多的命令并且需要频繁查询地址(云盘Cli无法使用Tab),因此我使用我正在研发的GenUI框架构建了这个产品。


注意事项

warning 中国大陆需要确保能够访问 AWS 服务 目前仅支持Windows系统

准备

有关安装说明,请展开适用于您的操作系统的部分。

下载AWS Cli

AWS Cli

Windows

安装和更新要求

  • 我们支持微软支持 AWS CLI 的 64 位 Windows 版本
  • 安装软件的管理员权限

下载并运行适用于 Windows (64 位) 的 AWS CLI MSI 安装程序:https://awscli.amazonaws.com/AWSCLIV2.msi

或者,您可以运行 msiexec 命令来运行 MSI 安装程序。

msiexec.exe /i https://awscli.amazonaws.com/AWSCLIV2.msi
# For various parameters that can be used with msiexec, see msiexec on the Microsoft Docs website. 
# For example, you can use the /qn flag for a silent installation.
msiexec.exe /i https://awscli.amazonaws.com/AWSCLIV2.msi /qn

Config

下载完成后需要登录AWS并获取分配的账号进行配置 查阅 Config the AWS Cli

aws configure

AWS Access Key ID [None]: YOUR ACCESS KEY ID
AWS Secret Access Key [None]: YOUR SECRET ACCESS KEY
Default region name [None]: REGION NAME
Default output format [None]: json

Features

  • [x] 检查S3配置
  • [x] 连接S3 Cli
  • [x] 获取云盘文件,文件夹
  • [x] 上传文件到云盘
  • [x] 删除文件,文件夹
  • [x] 分享文件,文件夹
  • [x] 使用亚马逊S3 Cli
  • [ ] 上传文件夹到云盘
  • [ ] 创建文件
  • [ ] 使用亚马逊S3 SDK

欢迎👏大家使用本产品并提出宝贵的建议帮助我进行优化,如果您对我正在构建的GenUI框架感兴趣请随时与我们进行联系。

Expector
C/C++ 以及 Rust 中的 getch 实现

getch 是一个在 C 语言编程中常用的函数,用于从键盘读取一个字符,但不回显到屏幕上。

在 Windows 环境下,getch 实现通常包含在 <conio.h> 头文件中。需要注意的是,getch 这个符号并非标准,标准的符号是 _getch,虽然 getch 一般会被指向 _getch,但你应当使用 _getch 而非 getch

在 Unix/Linux 环境下,没有系统提供的 getch 实现,我们可以通过以下方法实现:

#include <termio.h>

int getch(void) {
    struct termios tm, tm_old;
    int fd = 0, ch;

    if (tcgetattr(fd, &tm) < 0) { // 保存现在的终端设置
        return -1;
    }

    tm_old = tm;
    cfmakeraw(&tm); // 更改终端为原始模式,该模式下所有的输入数据以字节处理
    if (tcsetattr(fd, TCSANOW, &tm) < 0) { // 设置上更改之后的设置
        return -1;
    }

    ch = getchar();
    if (tcsetattr(fd, TCSANOW, &tm_old) < 0) { // 更改设置为最初的样子
        return -1;
    }

    return ch;
}

其中 struct termiostcgetattrtcsetattrcfmakeraw 以及 getchar 的定义为:

typedef unsigned char	cc_t;
typedef unsigned int	speed_t;
typedef unsigned int	tcflag_t;
#define NCCS 32
struct termios{
    tcflag_t c_iflag;		/* input mode flags */
    tcflag_t c_oflag;		/* output mode flags */
    tcflag_t c_cflag;		/* control mode flags */
    tcflag_t c_lflag;		/* local mode flags */
    cc_t c_line;			/* line discipline */
    cc_t c_cc[NCCS];		/* control characters */
    speed_t c_ispeed;		/* input speed */
    speed_t c_ospeed;		/* output speed */
};

int tcgetattr(int __fd, struct termios *__termios_p);
void cfmakeraw(struct termios *__termios_p);
int tcsetattr(int __fd, int __optional_actions, const struct termios *__termios_p);
int getchar(void);

据此,我们可以通过 Rust 的 FFI 为 rust 实现一个 getch

#[cfg(target_os = "windows")]
mod conio {
    use std::os::raw::c_int;

    extern "C" {
        pub fn _getch() -> c_int;
    }
}

#[cfg(target_os = "linux")]
#[allow(non_camel_case_types)]
mod conio {
    use std::os::raw::c_int;
    type tcflag_t = ::std::os::raw::c_uint;
    type speed_t = ::std::os::raw::c_uint;
    type cc_t = ::std::os::raw::c_uchar;

    const NCCS: usize = 32;
    const TCSANOW: i32 = 0;

    #[repr(C)]
    #[derive(Default, Copy, Clone)]
    struct termios {
        c_iflag: tcflag_t,
        c_oflag: tcflag_t,
        c_cflag: tcflag_t,
        c_lflag: tcflag_t,
        c_line: cc_t,
        c_cc: [cc_t; NCCS],
        c_ispeed: speed_t,
        c_ospeed: speed_t,
    }

    extern "C" {
        fn tcgetattr(__fd: c_int, __termios_p: *mut termios) -> c_int;
        fn tcsetattr(__fd: c_int, __optional_actions: c_int, __termios_p: *const termios) -> c_int;
        fn cfmakeraw(__termios_p: *mut termios);
        fn getchar() -> c_int;
    }

    #[allow(unused_mut, unused_assignments)]
    pub fn _getch() -> c_int {
        unsafe {
            let mut tm: termios = Default::default();
            let mut tm_old: termios = Default::default();
            let fd = 0;
            let mut ch: c_int;
            if tcgetattr(fd, &mut tm) < 0 {
                return -1;
            }

            tm_old = tm;
            cfmakeraw(&mut tm);
            if tcsetattr(fd, TCSANOW, &mut tm) < 0 {
                return -1;
            }

            ch = getchar();
            if tcsetattr(fd, TCSANOW, &mut tm_old) < 0 {
                return -1;
            }

            ch
        }
    }
}

#[allow(unused_unsafe)]
fn getch() -> char {
    unsafe { conio::_getch() as u8 as char }
}
渡劫
为什么相同的循环体次数,for循环明显更快执行完毕?

#include <reg51.h>

void delay(void) { //while循环方式 unsigned char i=200; unsigned char j=200; while (i--) while(j--); /* //for循环方式 unsigned char i = 200; unsigned char j = 200; for (i=200 ;i>0;i--) for(j=200; j>0 ;j--); */ }

void main(void) { while(1) { unsigned char p = 0x01; unsigned char q; for ( q = 0 ; q < 8 ; q++) { P0 = ~(p << q); delay(); }

}

}

Bear Billys
您的道德和有效的社會工程夥伴

社會工程需要技巧和精確度。專業角支持您安全、合乎道德地開展業務。

我們的客製化服務:

深入調查:我們收集相關信息,讓您搶佔先機。 建立引人注目的個人資料:我們開發可信賴的數位身分來加強您的方法。 優化您的流程:我們自動執行重複性任務以提高效率。 專家建議:受益於我們的專業知識來完善您的策略。 為什麼選擇我們?

絕對保密:您的專案將得到最大程度的謹慎處理。 具體結果:我們為您提供詳細的報告,幫助您做出最佳決策。 個人化解決方案:我們的服務適應您的特定需求。 準備好探索新的視角了嗎?

聯絡我們

https://t.me/Matricule02

https://mitalk.lat/proteus/

Expector
根据视频生成可以头尾衔接的循环视频

最近手头有一个视频,基本上是一个部分重复循环的,我想把循环的一段提取出来造成动态壁纸,但怎奈何不会用 pr,只能用 ffmpeg 配合 pillow 搞了……

实现的关键在于找到可以首位相接的两帧画面,这就要求两个画面有极高的相似度。判断画面相似度首先需要对图像进行量化,一般有两种方案,一种是提取特征向量,一种是计算哈希。考虑到我手头视频的特征,我选择了比较简单的哈希。

开始之前,需要安装必要的包以及 ffmpeg,执行

pip install ffmpeg-python Pillow numpy imagehash

!Notice 简略起见,以下代码不重要部分折叠,具体实现参照文末链接

首先需要把视频分离成帧,存入数组:

def extract_frames(input_video) -> Generator[np.ndarray, None, None]:
    # 一个生成器,生成每一帧的数据存入 numpy 数组
    ...

图像的哈希算法有多种,比如均值哈希(aHash)、感知哈希(pHash)以及差异哈希(dHash),各有优劣,但选择哪一种对接下来的算法影响不大,我这里以 pHash 为例。以上图像哈希算法在 imagehash 中均有提供,由于本篇主要讨论循环视频生成,哈希算法的具体原理就不研究了(肯定不是因为我不会)。

def generate_hashes(input_video: str) -> Generator[int, None, None]:
    for frame in extract_frames(input_video):
        # 将 numpy 数组转换为 PIL 图像
        pil_image: ImageHash = Image.fromarray(frame)

        # 生成 pHash 值
        phash_value = int(str(phash(pil_image)), 16)

        yield phash_value

图像哈希越相似,图像就越相似。两个哈希值的相似度可以用汉明距离表示,汉明距离表两个二进制数差异的位数,可以通过异或和中 math 的个数计算。

def hamming_distance(hash1: int, hash2: int) -> int:
    return bin(hash1 ^ hash2).count('1')

接下来遍历每一帧的哈希找到距离最近的两帧即可。遍历过程如果有确定起始或结束帧可以直接遍历,复杂度 math;如果没有固定起始帧,根据汉明权重(也就是与 math 的汉明距离)排序后遍历即可,复杂度 math

最后完整代码在github gist

Expector
分享一下自己常用的矩阵快速幂优化dp模板

适合竞赛用,应该是相关模板最简洁的之一吧,不需要的部分(参数传递、命名空间、类型别名什么的)自己根据实际情况改一改就可以了。

namespace MTX {
using i64 = int64_t;
constexpr i64 MTX_SIZE = 3;
using vec = std::array<i64, MTX_SIZE>;
using mtx = std::array<vec, MTX_SIZE>;

mtx &mul(mtx &a, const mtx &b, const i64 m = INT64_MAX) {
    mtx r{};
    for (int i = 0; i < MTX_SIZE; ++i)
        for (int j = 0; j < MTX_SIZE; ++j)
            for (int k = 0; k < MTX_SIZE; ++k)
                r[i][j] = (r[i][j] + a[i][k] * b[k][j] % m) % m;
    a = std::move(r);
    return a;
}

mtx &dp(mtx &s, mtx& f, i64 n, const i64 m = INT64_MAX) {
    while (n) {
        if (n & 1) mul(s, f, m);
        n >>= 1, mul(f, f, m);
    }
    return s;
}
} // namespace MTX

使用样例(斐波那契数列):

#include <bits/stdc++.h>

namespace MTX {
using i64 = int64_t;
constexpr i64 MTX_SIZE = 3;
using vec = std::array<i64, MTX_SIZE>;
using mtx = std::array<vec, MTX_SIZE>;

mtx &mul(mtx &a, const mtx &b, const i64 m = INT64_MAX) {
    mtx r{};
    for (int i = 0; i < MTX_SIZE; ++i)
        for (int j = 0; j < MTX_SIZE; ++j)
            for (int k = 0; k < MTX_SIZE; ++k)
                r[i][j] = (r[i][j] + a[i][k] * b[k][j] % m) % m;
    a = std::move(r);
    return a;
}

mtx &dp(mtx &s, mtx& f, i64 n, const i64 m = INT64_MAX) {
    while (n) {
        if (n & 1) mul(s, f, m);
        n >>= 1, mul(f, f, m);
    }
    return s;
}
} // namespace MTX

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(nullptr);
    MTX::mtx s{(MTX::vec)
        {1, 1},
        {0, 0}
    }, f{(MTX::vec)
        {0, 1},
        {1, 1}
    };
    MTX::i64 n;
    std::cin >> n;
    std::cout << MTX::dp(s, f, n - 1, 1e9 + 7)[0][0] << std::endl;
    return 0;
}
雏雁计划有人可以提供一个方向吗,实在想不出来qwq

如题,本人擅长 Java 后端 ,同学都是萌新,找到方向之后再找人heart

nexmoe
需要便宜的短期 GPU 租赁吗? 我们正在做这个事情!

⚡️ 灵动算力:为AI工作者提供短期、经济的算力

💰 比市场价低40%

⏱️ 按需租用,灵活便捷

👓 我们也在对长期租赁进行技术攻克中,做到无感迁移

了解更多:https://agile.nexmm.com

#GPU租赁 #AI计算 #省钱利器