Tricks

154KB

cheat_sheet.pdf

PDF

打开

py二维数组初始化

dp = [[0] * (n+1) for i in range(m+1)] # dp[m][n]

字符串gcd

def sgcd(str1: str, str2: str):
    if str1+str2 == str2+str1:
        len1 = len(str(str1))
        len2 = len(str(str2))
        return str1[0:gcd(len1, len2)]
    return ''

字符串lcm

def slcm(str1,str2):
    _gcd = sgcd(str1, str2)
    if not _gcd:
        return -1
    leng = len(_gcd)
    a = len(s)//leng
    b = len(t)//leng
    c = lcm(a, b)
    return c*_gcd

排列与组合数

def arrang(n,m):
    return math.factorial(n)//math.factorial(n-m)

def com(n, m):
    return math.factorial(n)//(math.factorial(m)*math.factorial(n-m))

围成圆圈处理套路

int go(int p, int d, int t) {
 while(t--) {
 do { p = (p+d+n-1) % n + 1; } while(a[p] == 0); //走到下一个非0数字
 }
 return p;
}

//例题4-3 救济金发放（The Dole Queue, UVa 133）
//n (n <20)个人站成一圈，逆时针编号为1～n 。有两个官员，A从1开始逆时针数，B
//从n 开始顺时针数。在每一轮中，官员A数k 个就停下来，官员B数m 个就停下来（注
//意有可能两个官员停在同一个人上）。接下来被官员选中的人（1个或者2个）离开队
//伍。
//输入n，k，m 输出每轮里被选中的人的编号（如果有两个人，先输出被A选中的）。
//例如，n =10，k =4，m =3，输出为4 8, 9 5, 3 1, 2 6, 10, 7。注意：输出的每个
//数应当恰好占3列。
//【分析】
//仍然采用自顶向下的方法编写程序。用一个大小为0的数组表示人站成的圈。为了避
//免人走之后移动数组元素，用0表示离开队伍的人，数数时跳过即可。主程序如下：
#include<stdio.h>

#define maxn 25
int n, k, m, a[maxn];

//逆时针走t步，步长是d（-1表示顺时针走），返回新位置
int go(int p, int d, int t) { … }

int main() {
    while (scanf("%d%d%d", &n, &k, &m) == 3 && n) {
        for (int i = 1; i <= n; i++) a[i] = i;
        int left = n; //还剩下的人数
        int p1 = n, p2 = 1;
        while (left) {
            p1 = go(p1, 1, k);
            p2 = go(p2, -1, m);
            printf("%3d", p1);
            left--;
            if (p2 != p1) {
                printf("%3d", p2);
                left--;
            }
            a[p1] = a[p2] = 0;
            if (left) printf(",");
        }
        printf("\n");
    }
    return 0;
}

//约瑟夫问题
//n 个人标号0，1，，n-1 。逆时针站一圈，从0号开始，每一次从当前的人逆时针数k个，
//然后让这个人出局。问最后剩下的人是谁。
int josephus(int n, int k) {
  int res = 0;
  for (int i = 1; i <= n; ++i) res = (res + k) % i;
  return res;
}

进制转换

string PtoR(string &src, int srcBase, int destBase) {
    int sum = 0;
    int residue;
    string saveResidue;

    // PtoD 转10进制
    for (int i = 0; src[i] != '\0'; i++) {
        sum *= srcBase;
        if (src[i] >= '0' && src[i] <= '9') {
            sum += src[i] - '0' + 0;        // 字符转数字，可以先减掉基底字符，然后加上基底数字
        } else { sum += src[i] - 'A' + 10; }
    }

    // DtoR 10进制转R
    while (sum != 0) {
        residue = sum % destBase;
//        if (residue == 0) {
//            residue = destBase;
//            sum = sum - destBase;
//        }
        if (residue >= 0 && residue <= 9) {
            saveResidue += residue - 0 + '0';    // 数字转字符，可以先减掉基底数字，然后加上基底字符
        } else
            saveResidue += residue - 10 + 'A';
        sum = sum / destBase;
    }

    reverse(saveResidue.begin(), saveResidue.end());
    return saveResidue;
}

浮点数gcd

double fgcd(double a, double b) {
    //求浮点数的gcd
    if (b < EPS) return a;
    return fgcd(b, fmod(a, b));
}