ACM刷题之路（十六）Acm程序设计竞赛自制模板（一）

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);

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. }

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. }

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. }

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. }