语法和库函数
基础语法
变量
数组初始化
int array[114514] = {0} // 全部初始化为 0
int a[4][5] = {0};
要初始化为其他值，还是需要循环赋值。
static 关键字
修饰全局变量：作用域在文件内
修饰局部变量：只初始化一次
static char[36] flag = "flag{you_cannot_read_me_from_outside}";
int timer1(){
static int t = 0;
return ++t;
}
int timer2(){
static int t;
t = 0;
return ++t;
}
int main(){
for(int i = 0; i < 10; i++){
printf("%d ", timer1()); // 1 2 3 4 5 6 7 8 9 10
}
putchar('\n');
for(int i = 0; i < 10; i++){
printf("%d ", timer2()); // 1 1 1 1 1 1 1 1 1 1
}
return 0;
}
extern 关键字
来自其他文件的东西，多文件编程。
IO
其他库函数
string.h
数据结构（EASY）
链表
其实挺容易犯错的，尤其是在没有想清楚细节的情况下.
最好先想好要修改哪几个节点的数据，修改该节点的前驱还是后继.
合并 K 个有序链表
这个问题考察了链表的基础使用：
- 对
NULL的判断 - 正确更新
node->next - （也许重要）内存管理
可以用到分治法.
node* mergeK(node **lists, int size){
if(size == 0){
return NULL;
}
else if(size == 1){
return lists[0];
}
int len = size/2;
return merge2(mergeK(lists, len), mergeK(lists+len, size-len));
}
基于 merge2：
node* merge2(node* l1, node* l2) {
if (l1 == NULL) {
return l2;
}
if (l2 == NULL) {
return l1;
}
node *ans = (node*)malloc(sizeof(node)), *ansp = ans;
node *p1 = l1, *p2 = l2;
while (p1 != NULL && p2 != NULL) {
if (p1->val <= p2->val) {
ansp->next = p1;
p1 = p1->next;
} else {
ansp->next = p2;
p2 = p2->next;
}
ansp = ansp->next;
}
if (p1 != NULL) {
ansp->next = p1;
} else if (p2 != NULL) {
ansp->next = p2;
}
ansp = ans->next;
free(ans);
return ansp;
}
判环：Floyd's Cycle Finding Algorithm (快慢指针)
用数组模拟链表
next[pos] 比 pos->next 快.
#include <stdio.h>
#include <stdlib.h>
int n, m;
int opt;
int *pre, *next;
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
int main()
{
scanf("%d%d", &n, &m);
pre = (int *)malloc(sizeof(int) * (n + 1));
next = (int *)malloc(sizeof(int) * (n + 1));
for (int i = 1; i <= n; i++)
{
pre[i] = i - 1;
next[i] = i + 1;
}
pre[0] = -2;
next[0] = 1;
next[n] = -1;
while (m--)
{
int x, y;
scanf("%d%d%d", &opt, &x, &y);
switch (opt)
{
case 1:
if (next[x] == y)
{
break;
}
next[pre[x]] = next[x];
pre[next[x]] = pre[x];
next[pre[y]] = x;
pre[x] = pre[y];
pre[y] = x;
next[x] = y;
break;
case 2:
if (next[y] == x)
{
break;
}
next[pre[x]] = next[x];
pre[next[x]] = pre[x];
pre[next[y]] = x;
next[x] = next[y];
pre[x] = y;
next[y] = x;
break;
case 3:
int px = pre[x], nx = next[x];
int py = pre[y], ny = next[y];
if (next[x] == y)
{ // x 紧邻 y
pre[y] = px;
next[x] = ny;
next[px] = y;
pre[ny] = x;
next[y] = x;
pre[x] = y;
}
else if (next[y] == x)
{ // y 紧邻 x
pre[x] = py;
next[y] = nx;
next[py] = x;
pre[nx] = y;
next[x] = y;
pre[y] = x;
}
else
{ // x 和 y 不相邻
next[px] = y;
pre[nx] = y;
next[py] = x;
pre[ny] = x;
swap(pre+x,pre+y);
swap(next+x, next+y);
}
break;
default:
break;
}
}
int val = 0, cnt = 0;
unsigned long long sum = 0;
while (1)
{
cnt++;
val = next[val];
if (val == -1)
break;
if (cnt % 2 == 1)
{
sum += val;
}
}
printf("%llu", sum);
return 0;
}
简易哈希表
基础算法
数学
快速幂
原理是二进制表示： $$ 3^{11} = 3^{(1011)_2} = 3^{(1000)_2} \times 3^{(10)_2} \times 3^{(1)_2} = 3^8 \times 3^2 \times 3^1 $$
long long pow(long long base, int exp){
long long result = 1;
while(exp){
if(exp % 2){ // 这一位是否是 1
result *= base;
}
base *= base; // 即使不是，也要累乘
exp /= 2; // 幂舍去一位
}
return result;
}
行列式计算
Laplace 变换
$$ M = \sum (-1)^{i+j}a_{(i,j)}M_{i,j} $$
2阶方阵可以直接求，三阶以上就应该使用 Laplace 降阶。
int laplace(vector<vector<int>> &matrix, int size){
if(size == 1){
return matrix[0][0];
}
else if(size == 2){
return matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix[1][0];
}
int sum = 0;
for(int i = 0; i < size; i++){
vector<vector<int>> submatrix(size-1, vector<int>(size-1));
for(int j = 1; j < size; j++){
for(int k = 0; k < size; k++){
if(k < i){
submatrix[j-1][k] = matrix[j][k];
}
else if(k > i){
submatrix[j-1][k-1] = matrix[j][k];
}
}
}
sum += matrix[0][i] * pow(-1, i+2) * laplace(submatrix, size-1);
}
return sum;
}
LU 分解（应该不至于）
BigNum
结合了之前看到的快读快取的代码
加法
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
#define MAX_SIZE 100
char aa[MAX_SIZE], bb[MAX_SIZE], ans[MAX_SIZE + 1];
int head_a, head_b;
int qread(char c[])
{
int ptr = MAX_SIZE - 1;
char ch;
while ((ch = getchar()) && isdigit(ch))
{
c[ptr--] = ch;
}
return ptr;
}
int qprint(char c[])
{
int ptr = MAX_SIZE - 1;
while (c[ptr] != 0)
{
putchar(c[ptr--]);
}
return ptr;
}
void plus(char a[], char b[])
{
int offset = head_a - head_b;
for (int i = head_b + 1; i < MAX_SIZE; i++)
{
b[i + offset] = b[i];
}
for (int i = MAX_SIZE + offset; i < MAX_SIZE; i++)
{
b[i] = '0';
}
int dig_l = 0;
for (int i = MAX_SIZE - 1; i > head_a; i--)
{
int dig_a = a[i] - '0';
int dig_b = b[i] - '0';
div_t dt = div(dig_a + dig_b + dig_l, 10); // 一个汇编指令，同时得到商和余数
dig_l = dt.quot;
ans[i] = dt.rem + '0';
}
if (dig_l != 0)
{
ans[head_a] = dig_l;
}
}
int main()
{
head_a = qread(aa);
head_b = qread(bb);
if(head_b >= head_a){
plus(aa,bb);
}
else{
int temp = head_a;
head_a = head_b;
head_b = temp;
plus(bb,aa);
}
qprint(ans);
return 0;
}
乘除法：
最大公约数
引理：$gcd(a, b) = gcd(b ,a \mod b)$
$O(n)$ 复杂度，Greatest Common Divisor 的欧几里德求法：
// ver1
int gcd(int a, int b){
return b == 0 ? a : gcd(b, a%b);
}
// ver 2
int gcd(int a, int b){
while(b != 0){
int temp = a;
a = b;
b = temp % b;
}
return a;
}
退出机制是：$gcd(a,0)=|a|$.
最小公倍数
引理：$gcd(a,b) \cdot lcm(a,b) = |a \cdot b|$
lcm = a*b/gcd(a,b);