【学习经验】从学长学姐继承下来的板子们

二分查找/二分法

  1. 查找a中是否存在key

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    int find(int a[], int n, int key){
        int l = 0, r = n - 1, mid;
        while (l <= r){
            mid = l + (r - l) / 2;      //左右边界中间点的值
            if (a[mid] < key) l = mid + 1;   
            //如果当前的mid比目标小，则左边界右移到mid右边
            else if (a[mid] > key) r = mid - 1;     
            //如果当前的mid比目标大，则右边界左移到mid左边
            else return mid;                        
            //如果当前的mid等于目标，返回mid
        }
        return -1;              //没找到key
    }

  2. 查a中第一个大于等于 key 的

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    int find_first(int a[], int n, int key){
        int l = 0, r = n - 1, mid;
        while (l <= r){
        	mid = l + (r - l) / 2;
        	if (a[mid] < key) l = mid + 1; 
            //如果当前的mid<目标，则左边界右移到mid右边
        	else r = mid - 1;                       
            //如果当前的mid>=目标，则右边界左移到mid左边
        }
        if (l < 0 || l >= n) return -1;     //key<a[0] || key>a[n-1]
        return a[l] == key ? l : -1;        //如果key不存在，返回-1
     }

  3. 查a中第一个大于key的

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    int find_last(int a[], int n, int key){
        int l = 0, r = n - 1, mid;
        while (l <= r){
            mid = l + (r - l) / 2;
            if (a[mid] <= key) l = mid + 1;         
            //如果当前的mid<=目标，则左边界右移到mid右边
            else r = mid - 1;                       
            //如果当前的mid>目标，则右边界左移到mid左边
        }
        if (l < 0 || l >= n) return -1;       //key<a[0] || key>a[n-1]
        return a[l] == key ? l : -1;          //如果key不存在，返回-1
    }

  4. 二分法求单调（递增）函数func(x)的解

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    double solve(double left, double right, double y){
        double mid;
        while (right - left > eps){
            mid = (right + left) / 2;
            if (func(mid) > y)        // 递减则 func(mid) < y
                right = mid;
            else left = mid;
        }
        return mid;
    }

排序

  1. 冒泡排序-升序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    void bubble_sort(int a[], int n){
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++){
                if (a[j] > a[j + 1]) {
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
            }
        }
    }

  2. 选择排序-升序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    void select_sort(int a[], int n) {
        for (int i = 0; i < n - 1; i++) {
            int min_idx = i;
            for (int j = i + 1; j < n; j++) {
                if (a[j] < a[min_idx]) {
                    min_idx = j;
                }
            }
            if (min_idx != i) {
                int temp = a[i];
                a[i] = a[min_idx];
                a[min_idx] = temp;
            }
        }
    }

  3. qsort快排

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    qsort(a, n, sizeof(double), cmp);   
    //a 需要排序的数组名称    n 需要排序的个数    sizeof(double) 一个元素的大小
    //升序排序，最基础的写法
    int cmp(const void*p1, const void*p2){
        double *d1=(double *)p1;    //转换为目标类型
        double *d2=(double *)p2;    //转换为目标类型
        if((*d1 - *d2) < -eps) return -1;       //返回负数=p1在p2前面
        else if((*d1 - *d2) > eps) return 1;    //返回正数=p1在p2后面
        else return 0;
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    // 结构体的指针数组的cmp
     int cmp(const void *p1, const void *p2){
         struct tnode **d1 = (struct tnode **)p1;
         struct tnode **d2 = (struct tnode **)p2;
         if((*d1)->weight < (*d2)->weight){
             return -1;
         }else if((*d1)->weight > (*d2)->weight){
             return 1;
         }else{
             if((*d1)->c < (*d2)->c){
                 return -1;
             }else{
                 return 1;
             }
         }
     }

  4. 归并排序

    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
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    void msort(int left, int right){    //归并排序
        if(left == right){      // 只剩一个元素，已经有序，无需排序
            return;
        }
        int mid = (left+right)/2;
       
        // 排序左侧
        msort(left, mid);
        // 排序右侧
        msort(mid+1, right);
       
        // 合并
        int left_i = left, right_i = mid+1, i=left;
        while(left_i<=mid && right_i<=right){
            if(a[right_i] < a[left_i]){
                temp[i++] = a[right_i];
                right_i++;
            }else if(a[right_i] > a[left_i]){
                temp[i++] = a[left_i];
                left_i++;
            }else{
                temp[i++] = a[right_i];
                temp[i++] = a[left_i];
                left_i++;
                right_i++;
            }
        }
        while(left_i<=mid){
            temp[i++] = a[left_i++];
        }
        while(right_i<=right){
            temp[i++] = a[right_i++];
        }
        for(int j=left; j<=right; j++){
            // printf("%d ", temp[j]);
            a[j] = temp[j];
        }
        // puts("");
    }

高精度

  1. 高精度加法

    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
    28
    29
    #include <stdio.h>
    #include <string.h>

    #define MAX 1000005
    char s1[MAX], s2[MAX];
    int a1[MAX], a2[MAX];

    int main() {
        int len, len1, len2, i, j;
        scanf("%s", s1);        //s1读入第一个数字
        scanf("%s", s2);        //s2读入第二个数字
        len1 = strlen(s1);
        len2 = strlen(s2);
        for (i = 0; i < len1; i++)
            //字符串倒序导入数组，方便从低位开始运算
            a1[i] = s1[len1 - 1 - i] - '0';
        for (i = 0; i < len2; i++)
            //字符串中的是字符，要转换成数字
            a2[i] = s2[len2 - 1 - i] - '0';
        len = (len1 > len2) ? len1 : len2;
        for (i = 0; i < len; i++) {
            a1[i + 1] += (j = (a1[i] + a2[i]) / 10);//进位
            a1[i] = (a1[i] + a2[i]) % 10;//保留
        }
        if (j) len++;//最后一位是否进位
        for (i = 0; i < len; i++)
            printf("%d", a1[len - 1 - i]);
        return 0;
    }

  2. 高精度减法

    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
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>

    #define MAX 1000005
    char s1[MAX], s2[MAX];
    int a[MAX], b[MAX];

    int main() {
        int len, i;
        scanf("%s %s", s1, s2);
        int l1 = strlen(s1);
        int l2 = strlen(s2);
        int flag = 0;

        if (l1 < l2 || (strcmp(s1, s2) < 0 && l1 == l2)) {  //s2代表的数更大
            len = l2;
            flag = 1;
            for (i = l2 - 1; i >= 0; i--)
                a[l2 - i - 1] = s2[i] - '0';
            for (i = l1 - 1; i >= 0; i--)
                b[l1 - i - 1] = s1[i] - '0';
        } else {
            len = l1;
            for (i = l1 - 1; i >= 0; i--)
                a[l1 - i - 1] = s1[i] - '0';
            for (i = l2 - 1; i >= 0; i--)
                b[l2 - i - 1] = s2[i] - '0';
        }

        for (i = 0; i < len; i++) {
            a[i] -= b[i];
            if (a[i] < 0) {
                a[i + 1] -= 1;
                a[i] += 10;
            }
        }
        while (a[len - 1] == 0 && len > 1) len--;
        if (flag == 1) printf("-");
        for (i = len - 1; i >= 0; i--) printf("%d", a[i]);
        printf("\n");
        return 0;
    }

  3. 高精度乘法

    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
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    #include <stdio.h>
    #include <string.h>

    #define MAX 1000005
    char s1[MAX], s2[MAX];
    int a1[MAX], a2[MAX], ans[MAX];
    int main() {
        int i, j, len1, len2;
        scanf("%s%s", s1, s2);
        len1 = strlen(s1);
        len2 = strlen(s2);
        for (i = 0; i < len1; i++) {
            a1[i] = s1[len1 - 1 - i] - '0';
        }
        for (i = 0; i < len2; i++) {
            a2[i] = s2[len2 - 1 - i] - '0';
        }
        for (i = 0; i < len1; i++) {
            for (j = 0; j < len2; j++) {
                ans[i + j] += a1[i] * a2[j];
            }
        }
        for (i = 0, j = 0; i < len1 + len2; i++) {
            ans[i] += j;
            j = ans[i] / 10;
            ans[i] %= 10;
        }
        for (; ans[i] == 0; i--){
            if(i<0){
                printf("0");
                break;
            }
        }       //跳过前面的0
        for (; i >= 0; i--) {
            printf("%d", ans[i]);
        }
        return 0;
    }

最大公约数

1
2
3
4
5
6
7
8
int gcd(int a, int b) {
    while (b != 0) {
        int tmp = a;
        a = b;
        b = tmp % b;
    }
    return a;
}

输出全排列

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
28
29
30
31
32
33
#include <stdio.h>
int n;
int stack[10];
void print_stack();
void dfs(int len);
int find_in_stack(int key, int len);
int main() {
    scanf("%d", &n);
    dfs(0);
    return 0;
}
void dfs(int len) {
    if (len == n) {
        print_stack();
        return;
    }
    for (int i = 1; i <= n; i++)
        if (!find_in_stack(i, len)) {
            stack[len] = i;
            dfs(len + 1);
        }
}
void print_stack() {
    for (int i = 0; i < n; i++)
        printf("%d ", stack[i]);
    puts("");
}
int find_in_stack(int key, int len) {
    for(int i = 0; i < len; i++)
        if (key == stack[i])
            return 1;
    return 0;
}

计算组合数

1
2
3
4
long long comb(long long n, long long m) {    //n >= m
    if (m == n || m == 0) return 1;
    else return comb(n - 1, m) + comb(n - 1, m - 1);
}

快速幂取模-a的b次方%p

1
2
3
4
5
6
7
8
9
10
11
long long fast_pow(long long a, long long b, long long p) {
    long long ans = 1;
    a = a % p;
    while (b) {
        if (b & 1)          //b二进制的最后一位是1时
            ans = (ans * a) % p;
        b >>= 1;    // b按位右移
        a = a * a % p;
    }
    return ans;
}

  • 假设我们拿到了a，并且b=11。想求 a11，但是又不想乘11次，有点慢。以电脑视角稍稍观察一下 b=(11)10，二进制下是 b=(1011)2。制作一个base。现在base = a，表示的是，a1 = a。待会base会变的。制作一个ans，初值 11，准备用来做答案。

    1
    2
    while(b > 0)
    {

  • 循环一。看，b（二进制）的最后一位是11吗？是的。这代表a11=a8×a2×a1中的“ ×a1 ”存在。所以 ans*=base。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    if(b & 1)
        ans *= base;

    /*关于 b & 1：
    “&”美名曰“按位与”。
    x & y 是二进制 x 和 y 的每一位分别进行“与运算”的结果。
    与运算，即两者都为 1 时才会返回 1，否则返回 0。
    那么 b & 1

              二进制
    b     =    1011
    1     =    0001
    b&1   =    0001

    因为 1（二进制）的前面几位全部都是 0，
    所以只有 b 二进制最后一位是 1 时，b & 1 才会返回 1。
    挺巧妙的，并且很快。)*/

    然后base努力上升，他通过自乘一次，使自己变成a2。

    1
    base *= base;

    同时

    1
    b >>= 1;

    它把（二进制的）自己每一位都往右移动了。原来的最后第二位，变成了最后第一位。b=(101)2。

    1
    }

  • 循环二，再看看b，最后一位还是11。这说明有“ ×a2 ”，ans∗=base。base继续努力，通过base∗=base让自己变成了a4。然后b也右移一位。b=(10)2。

  • 循环三，可是b的最后一位不再是1了，说明不存在“×a4”。base自我升华，达到了a8。且 b>>=1。这一步中，答案没有增加，可是毕竟 b>0，还有希望。

  • 循环四，b的最后一位是1，这说明“×a8”的存在。ans∗=base。由于b再右移一位就是0了，循环结束。

    总的来说，如果b在二进制上的某一位是1，我们就把答案乘上对应的a2^n。

一些相关笔记补充

  1. 直接求幂可以用循环解决，但是会出现溢出的问题

    1
    2
    3
    4
    5
    6
    7
    long long normal(long long base,long long power){
        long long result=1;
        for(int i=1;i<=power;i++){
            result*=base;
        }
        return result;
    }

  2. 取模运算的法则：

    (a+b)%p=(a%p+b%p)%p (ab)%p=(a%pb%p)%p，利用这一法则可以在循环乘积每一步前先取模来防止溢出

  3. 快速幂算法：每一步将指数分成两半，相应底数做平方运算，最后求出的结果实际是指数为奇数时的底数相乘

    1
    2
    3
    4
    5
    6
    7
    while(power>0){
        if(power&1==1){
            result=result *base;
        }
        power>>=1;
        base=base*base;
    }

汉诺塔

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>

void move(int n, char from, char to) {
    printf("Move %d from %c to %c!\n", n, from, to);
}

void hanoi(int n, char from, char via, char to) {
    if (n == 1){        //只剩一个盘子，递归结束
        move(n, from, to);
    }else{
        hanoi(n - 1, from, to, via);        //先把n-1个盘子拿走
        move(n, from, to);                  //再移动最底下的
        hanoi(n - 1, via, from, to);        //再把n-1个搬到目标棍子上
    }
}

int main(){
    int n;
    scanf("%d", &n);
    char a = 'A', b = 'B', c = 'C';
    hanoi(n, a, b, c);
    return 0;
}

判断质数

  1. 法一：直接判断

    1
    2
    3
    4
    5
    6
    7
    int is_prime(int x){
        if (x < 2) return 0;
        for (int i = 2; i * i <= x; i++){
            if (x % i == 0) return 0;
        }
        return 1;
    }

  2. 生成质数表再查找

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    //利用已有的质数表primes，判断n是否为质数
    int isPrime(int primes[], int n){
        int i;
        for(i=0; primes[i]*primes[i] <= n; i++){
            if(n % primes[i]== 0)
            return 0;
        }
        return 1;
    }
    //构造≤Q的质数表（Q>=5）
    void init_primes(int primes[], int Q){
        int count=3, num, step;
        primes[0] = 2; primes[1] = 3; primes[2] = 5;//头3个质数
        num = 7; step = 2;//初始为2
        while(count < Q){
            step = 6-step;// 构造4-2-4-2-...序列，减少遍历
            if(isPrime(primes, num))
                primes[count++] = num;
            num += step;// 下一个可能的质数
        }
    }

判断闰年

1
2
3
4
5
if((y%4==0 && y%100!=0) || y%400==0){
    printf("闰喵29\n");
}else{
    printf("不闰喵28\n");
}

计算逆序数

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// 利用归并排序计算一串数字a中的逆序数 
int a[500010], temp[500010];
long long nixu;
void msort(int left, int right);
int main() {
    int n;
    scanf("%d", &n);
    for(int i=0; i<n; i++){
        scanf("%d", &a[i]);
    }
    msort(0, n-1);
    printf("%lld", nixu);
    return 0;
}

void msort(int left, int right){
    if(left == right){      // 只剩一个元素，已经有序，无需排序
        return;
    }
    int mid = (left+right)/2;

    // 排序左侧
    msort(left, mid);
    // 排序右侧
    msort(mid+1, right);

    // 合并
    int left_i = left, right_i = mid+1, i=left;
    while(left_i<=mid && right_i<=right){
        if(a[right_i] < a[left_i]){
            nixu += (mid-left_i+1);
            temp[i++] = a[right_i++];
        }else{
            temp[i++] = a[left_i++];
        }
    }
    while(left_i<=mid){
        temp[i++] = a[left_i++];
    }
    while(right_i<=right){
        temp[i++] = a[right_i++];
    }
    for(int j=left; j<=right; j++){
        a[j] = temp[j];
    }
}

斐波那契数列

  1. 斐波那契数列

    1
    2
    3
    4
    int fb(int n){
        if(n<=3) return 1;
        return fb(n-3)+fb(n-1);
    }

  2. 广义斐波那契数列

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    #include <stdio.h>
    long long gfb(long long n,long long p,long long q,long long a,long long b,long long c );
    int main(){
        long long n,t,p,q,a,b,c;
        scanf("%lld%lld%lld%lld%lld%lld",&n,&p,&q,&a,&b,&c);
        t=gfb(n,p,q,a,b,c);
        printf("%lld",t);
        return 0;
    }
    long long gfb(long long n,long long p,long long q,long long a,long long b,long long c ){
        if(1==n) return p;
        if(2==n) return q;
        if(n>=3) return (a*gfb(n-1,p,q,a,b,c)+b*gfb(n-2,p,q,a,b,c)+c);
    }

大数乘法取模-(a*b)%mod

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
long long quickMulMod(long long a, long long b, long long mod){
    long long ans = 0;
    while (b){
        if (b & 1ll){
            ans = (ans + a) % mod;
        }
        a = (a + a) % mod;
        b >>= 1;
    }
    return ans;
}

计算三角形周长面积

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
28
29
30
#include <stdio.h>
#include <math.h>
double S(double a,double b,double c);
double C(double a,double b,double c);

int main(){
    int t;
    double x1,y1,x2,y2,x3,y3;
    double a,b,c;
    scanf("%d",&t);
    for(int i=0;i<t;i++){
        scanf("%lf%lf%lf%lf%lf%lf",&x1,&y1,&x2,&y2,&x3,&y3);
        a=sqrt((x2-x3)*(x2-x3)+(y2-y3)*(y2-y3));
        b=sqrt((x1-x3)*(x1-x3)+(y1-y3)*(y1-y3));
        c=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
        printf("%.3f %.3f\n",C(a,b,c),S(a,b,c));
    }
    return 0;
}

double C(double a,double b,double c){
    return a+b+c;
}
//海伦公式
double S(double a,double b,double c){
    double co,si;
    co=(a*a+b*b-c*c)/(2*a*b);
    si=sqrt(1-co*co);
    return a*b*si/2;
}

进制转化

  1. 十进制转二进制小数

    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
    28
    29
    30
    31
    32
    33
    #include <stdio.h>
    #include <string.h>
    int main()
    {
        double xiao,x;
        int zheng,a[50],b[11],i=0,cnt=0,len=0,tmp;
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        scanf("%lf",&x);
        tmp=zheng=(int)x;   //整数部分
        if(!zheng){          //整数是0
            printf("0");
        }else{              //整数不是0
            while(zheng){
                a[len++]=zheng%2;
                zheng /= 2;
            }
        }
        for(i=len-1;i>=0;i--){  //输出整数部分
            printf("%d",a[i]);
        }
        printf(".");       //输出小数点
        xiao=x-tmp;       //小数部分
        while(xiao){
            tmp=(int)(xiao*2);
            b[cnt++]=tmp;
            xiao=2*xiao-tmp;
        }
        for(i=0;i<10;i++){     //输出小数部分
            printf("%d",b[i]);
        }
        return 0;
    }

  2. 二进制转十进制

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    int bin2Dec(int arr[]){
        /*
        * 将2进制转为10进制
        * 设1个int的32位bit由低到高存在arr[0]...arr[31]
        * 函数命名是binary to decimal的缩写
        */
        int ret = 0;
        for (int i = 0; i < 32; i++){
            ret += arr[i] * (1 << i); 
            //相当于ret += arr[i] * (int)pow(2, i);
        }
        return ret;    //ret是得到的十进制数
    }

  3. 任意进制转换为2-36进制的long long

    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
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    #include <stdio.h>
    #include <ctype.h>

    typedef long long ll;

    /**
     * Convert string to long long int
     *
     * @param s source string
     * @param base 2 <= base <= 36
     * @return long long int value
     */
    ll str2ll(char s[], int base) {
        ll sum = 0;
        int x, i;
        for (i = 0; s[i]; i++) {
            if (isdigit(s[i])) x = s[i] - '0';
            else if (islower(s[i])) x = s[i] - 'a' + 10;
            else if (isupper(s[i])) x = s[i] - 'A' + 10;
            else {
                printf("Unexpected Character!");
                return -1;
            }

            if (x >= base) {
                printf("Unexpected Character!");
                return -1;
            }
            sum *= base;
            sum += x;
        }
        return sum;
    }

    int main() {
        char s[32];
        int x;
        scanf("%s%d", s, &x);      //s需要转换的字符串    //x进制
        printf("%lld", str2ll(s, x));
        return 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
#include <stdio.h>
#include <string.h>
int w1[27]={0};
int w2[27]={0};
int main()
{
    int i=0;
    char str[105]={};
    scanf("%s",str);
    int len=strlen(str);
    int flag=0;
    for(i=0;i<len;i++){
        if(w1[str[i]-'a']==0){
            w1[str[i]-'a']=i+1;
        }else{        //出现过一次
            if(w2[str[i]-'a']==0) w2[str[i]-'a']=i+1;
            else{
                printf("%c %d %d %d",str[i],w1[str[i]-'a'],w2[str[i]-'a'],i+1); //哪个字符 第一出现 第二次出现 第三次出现
                flag=1;
            }
        }
        if(flag) break;
    }
    return 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <stdlib.h>
#define ll long long
#define ull unsigned long long
char s[205];
char t[205];
void swap(char a,char b);
int main(){
    scanf("%s %s",s,t);
    int ls=strlen(s),lt=strlen(t);
    int i=0,j=0;
    int head,tail;
    char tmp;
    int flag=1;
    for(i=0;i<=(ls-lt);i++){
        j=0;
        flag=1;
        if(s[i]==t[j]){
            for(j=1;j<lt;j++){
                if(s[i+j]!=t[j]){
                    flag=0;
                    break;
                }
            }
        }
        if(flag&&j==lt){
            for(head=i,tail=i+lt-1;head<tail;head++,tail--){
                tmp=s[head];
                s[head]=s[tail];
                s[tail]=tmp;
            }
            i+=lt-1;
        }
    }
    for(i=0;i<ls;i++){
        printf("%c",s[i]);
    }
    return 0;
}

字符串归零（by onlyar）

1
2
3
4
5
6
7
typedef unsigned long long ull
void fill_zero_to_string(char *address){
    ull zero =0;
    for (int i=0;i*sizeof(zero)< MAX_KEEPWORD_LEN; i++){
        *((ull *) address + i) = zero;
    }
}

字符串查找（或许你想写个strstr吗）

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
28
29
30
31
32
#include <stdio.h>
#include <string.h>
#define MN 50005
char hastack[MN];
char needle[MN];
int strStr(char a[],char b[]);

int main(){
    gets(hastack);
    gets(needle);
    printf("%d",strStr(hastack,needle));
    return 0;
}
int strStr(char a[],char b[]){
    if(b==NULL){
        return 0;
    }else{
        int flag=1;
        int la=strlen(a),lb=strlen(b),i=0,j=0;
        for(i=0;i<=(la-lb);i++){
            flag=1;
            for(j=0;j<lb;j++){
                if(a[i+j]!=b[j]){
                    flag=0;
                    break;
                }
            }
            if(flag) return i+1;
        }
        if(!flag) return -1;
    }
}

多关键字排序-所以说这位不知名的学长你为什么要三目运算符套三目运算符啊（害怕）

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
28
29
30
31
32
33
34
35
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <stdlib.h>
#define ll long long
#define ull unsigned long long
int n, k;
struct node{
    int id;
    int w[11];
};
struct node arr[1010];
int cmp(const void *a, const void *b){
    struct node c = *(struct node *)a;
    struct node d = *(struct node *)b;
    int i;
    for(i = 0; i < k; ++i)
        if(c.w[i] == d.w[i]) continue;
        else return i % 2 ? (d.w[i] > c.w[i] ? 1 : -1) : (c.w[i] > d.w[i] ? 1 : -1);
    return c.id - d.id;
}
int main(){
    scanf("%d%d", &n, &k);
    int i, j;
    for(i = 0; i < n; ++i){
        arr[i].id = i + 1;
        for(j = 0; j < k; ++j)
            scanf("%d", &arr[i].w[j]);
    }
    qsort(arr, n, sizeof(arr[0]), cmp);
    for(i = 0; i < n; ++i)
        printf("%d ", arr[i].id);
    return 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
28
29
30
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <stdlib.h>
#define ll long long
#define ull unsigned long long
void re(int n);
int main(){
    ll n;
    scanf("%lld",&n);
    re(n);
    return 0;
}
void re(int n){
    int flag=0;
    if(n==0){
        printf("0");
    }else if(n==1){
        printf("2(0)");
    }else{
        for(int i=31;i>=0;i--){
            if(n&(1<<i)){
                printf(flag++?"+2(":"2(");
                re(i);
                printf(")");
            }
        }
    }
}

我觉得不会再考一遍吧-双阶乘-但还是存一下吧

  1. 版本1
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <stdio.h>
int a[2500000];//定义数组同时将数组全部初始化
int main(){
   long long n,t,k=0;
   scanf("%lld", &t);
   int i,m,s,c,temp;//i用来乘阶乘；m为数组位数; s为位数; c是进位
   while(k<t){
       scanf("%lld", &n);
       if(n == 0){
           printf("1\n");
       }else{
           if(n%2 == 0&&n!=0){       //偶数情况
               a[0]=1;
               s=1;
               //利用数组来存储结果
               for(i=2;i<=n;i+=2){
                   for(m=0,c=0;m<s;m++){
                       temp=a[m]*i+c;
                       a[m]=temp%10;
                       c=temp/10;     //进位
                   }
                   while(c!= 0){
                       ++s;
                       a[s-1]=c%10;
                       c=c/10;
                   }
               }
               //倒序输出结果
               for(i=s-1;i>=0;i--){
                   printf("%d",a[i]);
               }
               printf("\n");
           }else{     //奇数情况
               a[0]=1;
               s=1;
               //利用数组来存储结果
               for(i=1;i<=n;i+=2){
                   for(m=0,c=0;m<s;m++){
                       temp=a[m]*i+c;
                       a[m]=temp%10;
                       c=temp/10;
                   }
                   while(c!=0){
                       ++s;
                       a[s-1]=c%10;
                       c=c/10;
                   }
               }
               //倒序输出结果
               for(i=s-1;i>=0;i--){
                   printf("%d",a[i]);
               }
               printf("\n");
           }
       }
       k++;
   }
   return 0;
}
  1. 版本2
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
28
29
30
31
32
33
34
35
36
37
38
39
#include<stdio.h>
int main(){
   int a[10001];
   int b,sum;
   int x=0;
   int y,z=0;
   int i=0,k=1;
   scanf("%d",&y);
   for(k=1;k<=y;k++){
       z=0;
       i=0;
       while(i<=10000){
           a[i]=0;
           i++;
       }
       a[10000]=1;
       scanf("%d",&b);
       for(;b>=2;b-=2){
           for(i=10000;i>=0;i--){
               a[i]*=b;
           }
           for(i=10000;i>=0;i--){
               if(a[i]>=10000){
                   a[i-1]+=(a[i]/10000);
                   a[i]%=10000;
               }
           }
       }
       while(a[z]==0){
           z++;
       }
       printf("%d",a[z]);
       for(i=z+1;i<=10000;i++){
           printf("%04d",a[i]);
       }
       printf("\n");
   }
   return 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
28
29
30
31
32
33
34
/*
* 定义结构体 struct Vector，其指针重命名为 VecPtr
* length   : 数组已使用的长度
* capacity : 数组的容量
* array    ：用于存放数据的区域
*/
typedef struct Vector {
    int length;
    int capacity;
    int *array;
} *VecPtr;

/*
* 创建一个空的变长数组，初始容量为 5，返回变长数组的指针
*/
VecPtr create_vector() {
    VecPtr vec = (VecPtr) malloc(sizeof(struct Vector));
    vec->array = (int *) malloc(5 * sizeof(int));
    vec->capacity = 5;
    vec->length = 0;
    return vec;
}

/*
* 这个函数可以在数组的尾部插入元素，当数组满了自动扩大一倍
* vec  : 变长数组的指针
* item : 要插入的元素
*/
void push_back(VecPtr vec, int item) {
    vec->array[vec->length] = item;
    vec->length++;
    if (vec->length == vec->capacity)   // 满了
        vec->array = (int *) realloc(vec->array, 2 * vec->capacity * sizeof(int));      // 翻倍
}
学习经验
#学习经验
【学习经验】从学长学姐继承下来的板子们
http://example.com/2024/01/14/LE-banzi/
Author
John Doe
Posted on
January 14, 2024
Licensed under