跳至主要內容

一些经验和技巧

BraumAce2024年7月26日笔记经验约 2192 字大约 7 分钟

一些经验和技巧

1. vector 维护一个动态数组

定义时初始化(一般 +1 防止数组越界)
vector<int> a(n + 1, 0);

定义一个二维动态数组
vector<vector<int>> g(n + 1, vector<int>(n + 1));

2. 字符串

  1. size() 和 length()：这两个函数会返回 string 类型对象中的字符个数，且它们的执行效果相同

strlen() ：是C语言标准库中的函数

// 返回 string 长度，单位字节
size_t length() const noexcept;

// 返回 string 长度，单位字节。作用等同于 length()
size_t size() const noexcept;

// C 标准库函数，返回C风格字符串长度，单位字节
size_t strlen ( const char * str );

（1）当 string 中含有空字符’\0’，使用 strlen() 获取 string 的长度时会被截断，使用成员函数 length() 和 size() 可以返回 string 的真实长度。

（2）cout 对 string 输出时，会过滤掉空字符，输出不会被截断。

（3）在构造或者拼接 string 时，建议同时指定 string 的长度，比如：

如果字符串长度很大（例如超过 1e9）的时候，要使用 s.length() 获取字符串长度，使用 s.size() 会爆掉

  1. max_size()：返回 string 类型对象最多包含的字符数。一旦程序使用长度超过 max_size() 的 string 操作，编译器会拋出 length_error 异常。

  2. resize() ： 修改字符串的长度

str.resize(5);   // 长度修改为5

  1. capacity() ：该函数返回在重新分配内存之前，string 类型对象所能包含的最大字符数。

  2. 使用 printf() 输出 string 类型

    ① printf 函数输出字符串是针对 char * 的，即 printf 只能输出c语言的内置数据类型，而 string 不是c语言的内置数据类型。

    ② string 类型的对象不止包含字符串，还包含了许多用于操作的函数，所以 &str 并非字符串的首地址。

    ③ 如需输出string对象中的字符串，可以使用 string 的成员函数c_str()，该函数返回字符串的首字符的地址。

    string s = "hello";
printf("%s", s.c_str());

//输出：hello

3. 在一个数组中查找最长的相同连续子序列

// 在由 0、1 组成的字符串中查找最长的‘1’     
for (int i = 0; i < n; i++)
{
    if (s[i] == '1') len++;
        
    if (s[i] == '0'){
        res = max(res, len);
        len = 0;
    }
}

4. 秦九韶算法

int res = 0;
for (int i = 1; i <= n; i++)
    res = res * b + a[i];   //b代表进制位数

将一个 ii 进制的数转化为十进制

int get(string s, int i)
{
    int res = 0;
    for (auto c : s)
        res = res * i + c - '0';
    return res;
}

5. 开栈空间代码

备份，以防爆栈风险

int main()
{
    int size(512<<20);  // 512M
    __asm__ ( "movq %0, %%rsp\n"::"r"((char*)malloc(size)+size));
    // YOUR CODE
   ...
    exit(0);
    return 0;
}

6. 求 a 除以 b 的正余数

int get_mod(int a, int mod)
{
    return (a % mod + mod) % mod;
}

7. 裴蜀定理

若 a, b 是整数,且 gcd(a,b) = d ，那么对于任意的整数 x, y, ax+by 都一定是 d 的倍数。特别地，一定存在整数 x, y，使 ax + by = d 成立。

它的一个重要推论是：

a, b 互质的充分必要条件是存在整数 x, y 使 ax + by = 1 .

8. 交互题

若要提问，请打印 “ ？+ 问题 ” ，然后从标准输入中输入响应

如果你的程序问了一个无效的问题，或者问题用完了，交互器将立即终止，你的程序将得到一个判断错误的答案。

要给出最终答案，请打印 “ ! + 答案 ”

问完一个问题后，要输出行的末尾并刷新输出，否则将会得到超过限制限制的结果。

C中的 fflush(stdout) 或者C++中的 cout.flush()；
Java中的 System.out.flush()；
Pascal中的 flush(output)；
Python中的 stdout.flush().

9. mex函数

auto mex = [](vector<int> w)
{
    sort(w.begin(), w.end());
    int mx = 0;
    for (int x : w)
        if (x == mx) ++mx;
    return mx;
};

int z = mex(v);

10. string 与 int 之间的转化

（1）int 转 string

  • 通过 to_string() 函数转换

    int num = 123;
string s = to_string(num);
cout << s << endl;

// s = "123"

  • 通过 sprintf 转换

    int num = 123;
char str[256];
sprintf(str, "%d", num);
printf("%s", str);

    这是一种C语言中的转换方式，sprintf 也可以换成更安全的 snprintf 函数

（2）string 转 int

  • 通过 sscnaf 转换

    string str = "123";
int num = 0;

sscanf(str.c_str(), "%d", &num);
cout << num << endl;

// num = 123

    sscanf 函数的第一个参数类型是 const char *，string类型的参数需要转换一下

  • 使用 atoi 转换

    string str = "123";
cout << atoi(str.c_str());

// 123

    atoi 函数的头文件是 stdlib.h

11. string::npos

string::npos是一个静态成员常量，表示size_t的最大值（Maximum value for size_t）。该值表示“直到字符串结尾”**，**作为返回值它通常被用作表明没有匹配。

string::npos是这样定义的：

static const size_type npos = -1;

常用于配合 find() 函数使用，该函数有唯一的返回类型，即 string::size_type , 即一个无符号整型类型，可能是整数，也可能是长整数。

如果查找成功，返回按照查找规则找到的第一个字符或者子串的位置；

如果查找失败，返回 string::npos , 即 -1

12. x >> i & 1

x >> i & 1 用来判断 x 的二进制表示下的每一位是不是 1 .

13. assign()

C++ 函数 std::vector::assign() 通过替换旧值为向量元素分配新值。 如有必要，它会修改矢量的大小。

assign(n, val) 有两个参数，n — 容器大小，val — 重新赋给每个元素的值；

assign(first, last) 区间，左闭右开

功能：

①将区间 [first,last) 的元素赋值到当前的 vector 容器中；

②赋 nn 个值为 x 的元素到 vector 容器中，会覆盖掉 vector 容器中以前的内容。

1.第一种用法
vector<int> v1, v2;
v2.assign(v1,begin(), v1.end());

2.第二种用法
vector<int> a(n + 1);
vector<vector<int>> g(n + 1);
一维：a.assign(n + 1, 0);
二维：g.assign(n + 1, vector<int>());

14. lambda表达式

lambda 表达式定义了一个匿名函数，并且可以捕获一定范围内的变量。lambda 表达式的语法形式可简单归纳如下：

[ capture ] ( params ) opt -> ret {
    body;
};

其中

capture 是捕获列表，空表示不捕获任何变量；

& 表示捕获外部作用域中所有变量，并作为引用在函数体中使用（按引用捕获）；

= 表示捕获外部作用域中所有变量，并作为副本在函数体中使用（按值捕获）；

=，&foo 表示按值捕获外部作用域中所有变量，并按引用捕获 foo 变量。

bar 按值捕获 bar 变量，同时不捕获其他变量；

this 表示捕获当前类中的 this 指针，让 lambda 表达式拥有和当前类成员函数同样的访问权限。如果已经使用了 & 或者 =，就默认添加此选项。捕获 this 的目的是可以在 lamda 中使用当前类的成员函数和成员变量。

params 是参数表，
opt 是函数选项，
ret 是返回值类型，
body是函数体

写法示例：

// 计算两个数的和
auto plus = [] (int v1, int v2) -> int {
    return v1 + v2;
}

int sum = plus(1, 2);

递归 Lambda 表达式：

//d
vector<int> cnt(n);
auto dfs = [&](auto self, int u, int p) -> void {
    for (auto v : adj[u]) {
        if (v != p) {
            self(self, v, u);
            cnt[u] += cnt[v];
        }
    }
    if (cnt[u] == 0) {
        cnt[u] = 1;
    }
};

dfs(dfs, 0, -1);  //树的根节点从0开始，初始化为-1

15. max_element() 与 min_element()

  1. max_element() 与min_element() 分别用来求最大元素和最小元素的位置。

    接收参数：容器的首尾地址（迭代器）（可以是一个区间）

    返回：最值元素的地址（迭代器），需要减去序列头以转换为下标

vector<int> v;
int maxPos = max_element(v.begin(), v.end()) - v.begin(); //最大值下标
int minPos = min_element(v.begin(), v.end()) - v.begin();//最小值下标

2）普通数组
int a[] = {1,2,3,4};
int maxPos = max_element(a, a + 2) - a; //最大值下标
int minPos = min_element(a, a + 2) - a;//最小值下标

  1. max_element() 与 min_element() 分别用来求最大元素和最小元素的值。

    接收参数：容器的首尾地址（迭代器）（可以是一个区间）

    返回：最值元素的值

int maxValue = *max_element(v.begin(), v.end()); //最大值
int minValue = *min_element(v.begin(), v.end()); //最小值

int maxValue = *max_element(a, a + 2); //最大值
int minValue = *min_element(a, a + 2); //最小值

16. tuple

tuple 是泛化的 std::pair，我们通常是把它当作一个结构体使用，比如我们可以将多个参数整合为一个结构体传递到函数内部，实现一些简洁的操作。

  1. 创建

    tuple<int,float,int,float> tu = make_tuple(1,2.f,3,4.f);//创建方式一
tuple<int,float,int,float> tu(1,2.f,3,4.f);//创建方式二

//相当于结构体：
struct tu
{
   int a;
   float b;
   int c;
   float d;
}

  2. 同 pair<first, second> 一样

主题美化