1.计算a到b之间有多少符合条件的数，可打表后二分找a和b的位置后相减
例:
1. scanf("%lld%lld", &n, &m); 2. i = lower_bound(s1.begin(), s1.end(), n) - s1.begin(); 3. j = upper_bound(s1.begin(), s1.end(), m) - s1.begin(); 4. printf("%lld\n", j - i);
2.前缀和思想，不要直接暴力模拟。
3.(x1,y1)(x1,y1)(x2,y2)(x2,y2)两点连线之间的整点数是gcd(|x1−x2|,|y1−y2|)+1
4. 满足在[2,n]范围内有多少个数是非次方数（也就是不是x^k(k>1)这样的）
答案：
f(n)=4*f(n-2)-f(n-4)
f（n）=f（n-1）+6×（i-1）
f(n)=f(n-4)+f(n-2)+f(n-1)（n>4）
f[i]=f[i-1]+f[i-2]*4;
f(n)=f(n-2)+f(n-1)，n>3。
F[i] = F[i-1] + 2 * F[i-2];
a[n][m] = a[n-1][m] +a[n][m-1]
1. //————————algorithm———————— 2. int a[] = { 1, 3, 5, 7, 9, 11, 13 }; 3. lower_bound(a, a + 7, 7);//返回第一个大于等于7的地址 4. upper_bound(a, a + 7, 7);//返回第一个小于等于7的地址 5. binary_search(a, a + 7, 8);//若a到a+7有8，返回true 否则返回false 6. reverse(a, a + 7);//反转a到a+7的元素 7. fill(a, a + 7, 4);//填充函数，把a到a+7全部填充为4 8. int b[11] = { 1, 2, 3, 4 }; 9. copy_backward(a, a + 7, b + 7);//把a数组复制到b，首地址，尾地址，复制后数组的尾地址 10. next_permutation(b, b + 4);//b数组的下一个排列 11. prev_permutation(b, b + 4);//b数组的上一个排列 12. replace(b, b + 4, 3, 5);//把b到b+4中所有3替换成5 13. stable_sort(a, a + 7, cmp);//按照cmp规则稳定排序a到a+7 14. unique(a, a + 7);//去重，返回去重后数组的尾地址 15. printf("%d\n", *max_element(a, a + 6));//返回序列a到a+6的最大元素地址 16. //————————algorithm————————
1. //————————cstring———————— 2. char a[200] = "hello world"; 3. char b[] = "hello acm"; 4. cout << a << endl << b << endl; 5. memset(a, 0, sizeof(a));//初始化 只能0 -1 6. int len = strlen(a);//返回a的长度 到'\0'就算结束 7. strcpy(a, b);//把b赋值给a 覆盖掉 8. memcpy(a, b, 8);//把b赋值给a 覆盖掉8个长度 9. strcat(a, b);//把b连接到a后面 10. strncat(a, b, 3);//把b的最多3个字符连接到a后面 11. strcmp(a, b);//a>b 返回正数,a<b返回负数，一样返回0 12. strncmp(a, b, 7);//比较a和b的前7位字符 返回规则同上 13. int xiabiao = strchr(a, 'l') - a;//返回a中找字符l出现的首地址 没有返回NULL 14. int xiabiao2 = (char*)memchr(a, 'l', 7) - a;//返回a的前7个字符中找字符l出现的首地址 没有返回NULL 15. strspn(a, b);//比较a和b 从第一位开始比较返回从头数相等的长度 16. strstr(a, b)-a;//返回b在a首次出现的地址 17. //————————cstring————————
1. int a = 1, b = -2, c = 3, d = 4; 2. double e = 1.1, f = 8.36, g = 2.2, h =3.4; 3. /*————————<cmath> 部分————————*/ 4. e = sqrt(f);//平方根函数 返回根号f 5. e = cbrt(f);//立方根函数 返回三次根号f 6. e = pow(f, g); //幂函数 返回f的g次方 7. e = floor(f);//向下取整 返回f的向下取整的整数 8. e = ceil(f);//向上取整 返回f的向上取整的整数 9. a = abs(b);//int类型 返回b的绝对值 10. e = fabs(f);//double类型 返回f的绝对值 11. e = fmod(f, g);//double类型 返回f除以g的余数 12. e = modf(2.36, &f);//把2.36的整数部分赋值给f(有&) 把小数返回给e 13. e = frexp(1024.0, &a);//把1024.8转化为0.5*2^11;0.5返回 11赋值给a，返回的小数范围[0.5,1) 14. e = ldexp(1.0, 3);//返回1.0 *(2^3) 15. e = exp(3);//返回e的3次方 exp(1)就是e的值 acos(-1)就是pai的值 16. f = log(666.0);//返回log e (666.0) 以e为底数 17. f = log10(666.0);//返回log 10 (666.0) 以10为底数 18. f = log10(8) / log10(2);// 计算log 2 (8) 运用换底公式 19. f = acos(-1);//返回以弧度表示的 -1 的反余弦 20. f = asin(-1);//返回以弧度表示的 -1 的反正弦 21. f = atan(-1);//返回以弧度表示的 -1 的反正切 22. f = atan2(1, 2); //返回以弧度表示的 1/2 的反正切。1和2的值的符号决定了正确的象限。 23. f = cos(1.1);//返回弧度为1.1的余弦 24. f = sin(1.1);//返回弧度为1.1的正弦 25. f = tan(1.1);//返回弧度为1.1的正切 26. f = cosh(1.1);//返回弧度为1.1的双曲余弦 27. f = sinh(1.1);//返回弧度为1.1的双曲正弦 28. f = tanh(1.1);//返回弧度为1.1的双曲正切 29. f = hypot(3, 4);//返回以3和4为直角边的三角形斜边长 30. /*————————<cmath> 部分————————*/
1. int poww(int n, int m) 2. { 3. int ans = 1; 4. while (m > 0) 5. { 6. if (m & 1) ans *= n; 7. n *= n; 8. m /= 2; 9. } 10. return ans; 11. }
1. bool huiwen(int n) 2. {//判断一个数字是否回文 3. int temp = n, t = 0; 4. while (temp) 5. { 6. t = t * 10 + temp % 10; 7. temp /= 10; 8. } 9. return t == n; 10. }
1. int s=0,e=0,sum=a[0]; 2. int chang=0,min=1000010; 3. while(e<n) 4. {//s到e的一把尺子 5. if(sum<m)//如果sum小于预想结果 6. { 7. e++;//尺子后面边长 8. sum+=a[e]; 9. } 10. else if(sum>=m)//若达到结果 11. { 12. if(e-s+1<min) 13. { 14. min=e-s+1;//记录最小值 15. } 16. sum-=a[s]; 17. s++; //尺子前面缩短 18. } 19. 20. } 21. if(min!=1000010) //若有满足答案 22. printf("%d\n",min); 23. else 24. printf("0\n"); 25.
1. double s=开始,e=结尾,mid; 2. while(1) 3. { 4. mid=(s+e)/2.0; 5. if(满足条件) 6. {//或者while里面写(左<=右) 7. break; 8. } 9. else if(结果小于预想答案) 10. { 11. s=mid（按照情况+1或者不加）; 12. } 13. else 14. { 15. e=mid（按照情况-1或者不加）; 16. } 17. } 18. printf("%.4lf\n",mid);
1. int gcd(int x, int y) //547ms 2. { 3. int z; 4. while (y > 0) 5. { 6. z = x%y; 7. x = y; 8. y = z; 9. } 10. return x; 11. } 12. int gcd2(int a, int b) //544ms 13. { 14. return b == 0 ? a : gcd(b, a%b); 15. }
1. 三位的水仙花数共有4个：153，370，371，407； 2. 四位的四叶玫瑰数共有3个：1634，8208，9474； 3. 五位的五角星数共有3个：54748，92727，93084； 4. 六位的六合数只有1个：548834； 5. 七位的北斗七星数共有4个：1741725，4210818，9800817，9926315； 6. 八位的八仙数共有3个：24678050，24678051，88593477
1. int a[10005]; 2. int find(int x)//查找自己的老大 3. { 4. if (a[x] == x) return x; 5. else return a[x] = find(a[x]); 6. } 7. void mix(int x, int y)//合并 8. { 9. if (find(x) != find(y)) 10. { 11. a[find(x)] = find(y); 12. } 13. } 14. 主函数： 15. 1. for (i = 1; i <= 10000; i++)//初始化自己是自己的老大 16. a[i] = i; 17. 2. for (i = 1; i <= max; i++)//合并后需路径压缩 18. { 19. find(i); 20. } 21. 3. if (find(e) == find(r)) puts("Y"); 22. else puts("N");//如果老大一样，就是一个集合
1. int day_diff(int year1, int month1, int day1, int year2, int month2, int day2) 2. {//年月日 年月日 日期差公式 求相差几天 3. int y2, m2, d2, y1, m1, d1; 4. m1 = (month1 + 9) % 12; 5. y1 = year1 - m1 / 10; 6. d1 = 365 * y1 + y1 / 4 - y1 / 100 + y1 / 400 + (m1 * 306 + 5) / 10 + (day1 - 1); 7. 8. m2 = (month2 + 9) % 12; 9. y2 = year2 - m2 / 10; 10. d2 = 365 * y2 + y2 / 4 - y2 / 100 + y2 / 400 + (m2 * 306 + 5) / 10 + (day2 - 1); 11. return (d2 - d1); 12. }
1. #include<iostream> 2. #include<time.h> 3. using namespace std; 4. double zuhe(int n, int m) 5. { 6. double sum = 1; 7. int i; 8. for (i = 0; i < n; i++) 9. { 10. if (n - i>m) sum *= n - i; 11. if (n - m - i > 1) sum /= n - m - i;//顺带抵消，防止爆double 12. } 13. return sum; 14. } 15. 16. double zuhe2(int n,int r) 17. { 18. double s = 1; 19. int i; 20. for (i = 1; i <= r; i++) 21. s = s*(n - i + 1) / i; 22. return s; 23. } 24. 25. int main() 26. { 27. int n, m; 28. while (cin >> n >> m) 29. { 30. cout << zuhe(n, m) << endl;//506 ms 31. cout << zuhe2(n, m) << endl;//866 ms 32. } 33. return 0; 34. }
1. 直线分割平面: 任意两条直线都要相交，且任意三条直线不能有同一个交点 2. 即f(n) = f(n - 1) + n 或 f(n) = 1/2 * (n*n + n) + 1 3. 平面分空间: F(n) = (n * n * n + 5 * n + 6) / 6; 4. 另: 平方项的通项公式 1^2+2^2+3^2+……+n^2=n(n+1)(2n+1)/6 5. 立方差公式: n^3-(n-1)^3 = =2*n^2+(n-1)^2-n
1. int a[100003]; 2. int longziliehe(int n) 3. { 4. int maxsum = 0; 5. int thissum = 0; 6. for (int i = 0; i < n; i++) 7. { 8. scanf("%d", &a[i]); 9. thissum += a[i]; 10. if (thissum >= maxsum) maxsum = thissum; 11. if (thissum < 0) thissum = 0; 12. } 13. return maxsum; 14. }
LIS(最长上升子序列)
1. 1.o(n*logn) 2. #include<iostream> 3. #include<algorithm> 4. #include<cstring> 5. using namespace std; 6. int a[500020];//初始数组 7. int dp[500020];//最后的LIS数组 8. int lis(int n) 9. { 10. memset(dp, 0, sizeof(dp)); 11. dp[1] = a[1]; 12. int len = 1; 13. for (int i = 2; i <= n; i++) 14. { 15. int wei = lower_bound(dp + 1, dp + 1 + len, a[i]) - dp; 16. if (wei > len) 17. { 18. len++; 19. dp[wei] = a[i]; 20. } 21. else 22. { 23. dp[wei] = a[i]; 24. } 25. } 26. return len; 27. } 28. int main() 29. { 30. int n, i, j; 31. cout << "请输入需要求LIS的数组长度" << endl; 32. cin >> n; 33. cout << "数组长度输入完毕，请依次输入数组元素" << endl; 34. for (i = 1; i <= n; i++) 35. { 36. scanf("%d", &a[i]); 37. } 38. int max = lis(n); 39. cout << "该数组的LIS数组长度为" << max << endl; 40. cout << "该数组的最优LIS数组为" << endl; 41. for (i = 1; i <= max; i++) 42. { 43. cout << dp[i] << " "; 44. } 45. cout << endl; 46. return 0; 47. } 48. 49. 2. o(n^2) 50. #include<iostream> 51. #include<algorithm> 52. #include<cstring> 53. using namespace std; 54. int a[500020]; 55. int dp[500020]; 56. int lis(int n) 57. { 58. memset(dp, 0, sizeof(dp)); 59. dp[1] = 1; 60. int max = 1; 61. for (int i = 2; i <= n; i++) 62. { 63. for (int j = 1; j < i; j++) 64. { 65. if (a[j]<a[i] && dp[j] + 1> dp[i]) 66. { 67. dp[i] = dp[j] + 1; 68. if (dp[i] > max) max = dp[i]; 69. } 70. } 71. } 72. return max; 73. } 74. int main() 75. { 76. int n, i, j, k; 77. while (cin >> n) 78. { 79. for (i = 1; i <= n; i++) 80. { 81. scanf("%d", &a[i]); 82. } 83. int max = lis(n); 84. cout << max << endl; 85. } 86. return 0; 87. }
LCS(最长公共子序列)
1. 1. 滚动数组 2. #include<iostream> 3. #include<algorithm> 4. using namespace std; 5. int map[2][10005]; 6. string str1, str2; 7. int len1, len2; 8. void LCS(int x, int y) 9. { 10. for (int i = 0; i <= x; i++) 11. { 12. for (int j = 0; j <= y + 1; j++) 13. { 14. if (i == 0 || j == 0) 15. { map[i % 2][j] = 0; continue; } 16. if (str1[i - 1] == str2[j - 1]) 17. { 18. map[i % 2][j] = map[(i - 1) % 2][j - 1] + 1; 19. } 20. else 21. { 22. map[i % 2][j] = max(map[(i - 1) % 2][j], map[i % 2][j - 1]); 23. } 24. } 25. } 26. } 27. int main() 28. { 29. while (cin >> str1 >> str2) 30. { 31. len1 = str1.length(); 32. len2 = str2.length(); 33. LCS(len1, len2); 34. printf("%d\n", map[len1 % 2][len2]); 35. } 36. return 0; 37. } 38. 2.o(n+m) 39. #include<cstdio> 40. #include<string> 41. #include<iostream> 42. #include<algorithm> 43. using namespace std; 44. int map[10005][10005]; 45. string str1, str2; 46. int len1, len2; 47. int max(int x, int y) 48. { 49. if (x > y) return x; 50. return y; 51. } 52. 53. 54. int main() 55. { 56. while (cin >> str1 >> str2) 57. { 58. len1 = str1.length() - 1; 59. len2 = str2.length() - 1; 60. for (int i = 0; i <= len1 + 1; i++) 61. { 62. for (int j = 0; j <= len2 + 1; j++) 63. { 64. if (i == 0 || j == 0) 65. { 66. map[i][j] = 0; 67. continue; 68. } 69. if (str1[i - 1] == str2[j - 1]) 70. { 71. map[i][j] = map[i - 1][j - 1] + 1; 72. } 73. else 74. { 75. map[i][j] = max(map[i - 1][j], map[i][j - 1]); 76. } 77. } 78. } 79. printf("%d\n", map[len1 + 1][len2 + 1]); 80. } 81. return 0; 82. }
1. #include<iostream> 2. #include<string.h> 3. using namespace std; 4. int i, a[1000], b[1000]; 5. char s1[1000], s2[1000]; 6. int sum(char *s1, char *s2) 7. { 8. int len, len1 = strlen(s1), len2 = strlen(s2), t; 9. memset(a, 0, sizeof(a)), memset(b, 0, sizeof(b)); 10. for (i = 0; i<len1; i++) 11. //字符转换成数字，倒序存放，方便求和 12. a[i] = s1[len1 - 1 - i] - '0'; 13. for (i = 0; i<len2; i++) 14. b[i] = s2[len2 - 1 - i] - '0'; 15. len = len1>len2 ? len1 : len2; 16. for (t = i = 0; i <= len; i++) 17. { 18. a[i] += (b[i] + t); 19. //把数组b里的数字加到a数组里 20. t = a[i] / 10; //t为进位数 21. a[i] %= 10; 22. } 23. return a[len] == 0 ? len - 1 : len;//判断求和之后的长度的len还是len-1 24. } 25. int main() 26. { 27. int i; 28. while (~scanf("%s%s",s1,s2)) 29. { 30. int len = sum(s1, s2); 31. for (i = len; i >= 0; i--) 32. { 33. printf("%d", a[i]); 34. } 35. puts(""); 36. } 37. return 0; 38. }
1. import java.math.BigInteger; 2. import java.util.Scanner; 3. public class Main 4. { 5. public static void main(String args[]) 6. { 7. Scanner in = new Scanner(System.in); 8. while(in.hasNext()) 9. { 10. BigInteger a= in.nextBigInteger(); 11. BigInteger b= in.nextBigInteger(); 12. System.out.println(a + " + " + b + " = " + a.add(b)); 13. } 14. } 15. }
求第k个排列(阶乘法)
1. #include<iostream> 2. #include<algorithm> 3. #include<cstring> 4. #include<queue> 5. #include<vector> 6. using namespace std; 7. vector<int>a; 8. 9. 10. 11. long long jc(int x)//阶乘的递归算法 12. { 13. if (x < 2) return 1; 14. return x*jc(x - 1); 15. } 16. 17. 18. 19. 20. void shengcheng(int n)//生成1到n的排列，在a数组中 21. { 22. a.clear(); 23. for (int i = 0; i < n; i++) 24. a.push_back(i + 1); 25. } 26. 27. 28. 29. int maxjc(int n,int k) 30. //求小于等于k的最大的阶乘数 n为排列最大阶乘 31. { 32. for (int i = n; i>0; i--) 33. { 34. if (jc(i) <= k) return i; 35. } 36. return -1; 37. } 38. 39. void makepailie(int n,int k)//求第k个排列 40. { 41. int kk = k;//用于后面输出 42. k--;//这里需要减去一 43. int t = maxjc(n, k); 44. //求出小于等于k的最大的阶乘数 45. queue<int>q; 46. for (int i = 1; i < n - t; i++) 47. { 48. q.push(i); 49. a.erase(a.begin()); 50. } 51. while (t>=0) 52. { 53. int zheng = k / jc(t); 54. int yu = k % jc(t); 55. q.push(a[zheng]); 56. a.erase(a.begin() + zheng); 57. k %= jc(t); 58. t--; 59. } 60. cout << " 1 到"; 61. printf("%2d ", n);//控制格式 62. cout << "的第"; 63. printf(" %2d ", kk);//控制格式 64. cout<< "个排列为 : "; 65. while (!q.empty()) 66. { 67. cout << " " << q.front(); 68. q.pop(); 69. } 70. cout << endl; 71. } 72. 73. int main() 74. { 75. int n, i, k; 76. //------------------------------------------------ 77. //功能1： 输入n ，输出 1到n 的全排列 78. while (cin >> n) 79. { 80. for (i = 1; i <= jc(n); i++) 81. { 82. shengcheng(n); 83. makepailie(n, i); 84. } 85. } 86. //------------------------------------------------ 87. //功能2： 实现1到n 的第K个排列 88. while (cin >> n >> k) 89. { 90. shengcheng(n); 91. makepailie(n, k); 92. } 93. //------------------------------------------------ 94. return 0; 95. }
