Tricks
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));
}
最后更新于