华师一附中OI组

标题: 2015 HSYIT代码暂存楼[0] [打印本页]
作者: smileandyxu    时间: 2015-11-14 22:36
标题: 2015 HSYIT代码暂存楼[0]
仿照hr567的格式开楼~

大家可以把没有做完的题目代码暂存在这里留一个备份，免得再重写或是遇到一些麻烦的事情......
作者: hr567    时间: 2015-11-15 10:39
听起来这栋楼好高端的样子。存代码不应该上Tyvj吗？
作者: smileandyxu    时间: 2015-11-15 11:51
hr567 发表于 2015-11-15 10:39
听起来这栋楼好高端的样子。存代码不应该上Tyvj吗？

AC率直线暴降
作者: diggersun    时间: 2015-11-16 13:27
支持！我也来存
作者: diggersun    时间: 2015-11-16 13:27
支持！我也来存
作者: hr567    时间: 2015-11-17 18:45
smileandyxu 发表于 2015-11-15 11:51
AC率直线暴降

陈严俊不就是这样的……AC率只有20%左右吧……
作者: hr567    时间: 2015-11-17 20:05
NOIP2015 第二天第一题代码保存 [0]
  1. //#include <iostream>
  2. #include <fstream>
  3. using namespace std;
  4. ifstream cin("stone3.in");
  5. ofstream cout("stone3.out");
  6. int a[50002];
  7. int l, n, k;
  8. int i, j, t, p, b;
  9. int main()
  10. {
  11.     cin >> l >> n >> k;
  12.     t = a[0] = 0;
  13.     for (i = 1; i <= n; ++i)
  14.     {
  15.         cin >> j;
  16.         a[i] = j - t;
  17.         t = j;
  18.     }
  19.     a[n+1] = l - t;
  20.     for (i = 1; i <= k; ++i)
  21.     {
  22.         t = a[0];
  23.         for (j = 1; j <= n; ++j)
  24.             if (t == 0 || (a[j] != 0 && a[j] < t))
  25.             {
  26.                 t = a[j];
  27.                 p = j;
  28.             }
  29.         if (a[n+1] < t)
  30.         {
  31.             b = n;
  32.             while (a[b] == 0)
  33.                 --b;
  34.             a[n+1] += a[b];
  35.             a[b] = 0;
  36.         }
  37.         else
  38.         {
  39.             b = p + 1;
  40.             while (a[b] == 0)
  41.                 ++b;
  42.             a[b] += a[p];
  43.             a[p] = 0;
  44.         }
  45.     }
  46.     t = a[0];
  47.     for (j = 1; j <= n+1; ++j)
  48.         if (t == 0 || (a[j] != 0 && a[j] < t))
  49.             t = a[j];
  50.     cout << t;
  51.     return 0;
  52. }
复制代码
作者: smileandyxu    时间: 2015-11-17 20:06
  1. #include <iostream>
  2. using namespace std;
  3. long long x[10000];
  4. int n;
  5. int tot[100];
  6. int main()
  7. {
  8.     cin >> n;
  9.     for (int i = 0; i != n; ++i)
  10.         cin >> x[i];
  11.     for (int i = 0; i != n; ++i) {
  12.         for (int j = i + 1; j != n; ++j) {
  13.             for (int p = 0; p != 100; ++p) {
  14.                
  15.             }
  16.             
  17.             tot += ((x[j] - x[i]) * 2);
  18.         }
  19.     }
  20.     return 0;
  21. }
复制代码
作者: hr567    时间: 2015-11-17 20:08
stone [2]
  1. //#include <iostream>
  2. #include <fstream>
  3. using namespace std;
  4. ifstream cin("stone3.in");
  5. ofstream cout("stone3.out");
  6. int a[50002];
  7. int l, n, k;
  8. int i, j, t, p, b;
  9. int main()
  10. {
  11.     cin >> l >> n >> k;
  12.     t = a[0] = 0;
  13.     for (i = 1; i <= n; ++i)
  14.     {
  15.         cin >> j;
  16.         a[i] = j - t;
  17.         t = j;
  18.     }
  19.     a[n+1] = l - t;
  20.     for (i = 1; i <= k; ++i)
  21.     {
  22.         t = 0;
  23.         for (j = 1; j <= n; ++j)
  24.             if (t == 0 || (a[j] != 0 && a[j] < t))
  25.             {
  26.                 t = a[j];
  27.                 p = j;
  28.             }
  29.         if (a[n+1] < t)
  30.         {
  31.             b = n;
  32.             while (a[b] == 0)
  33.                 --b;
  34.             a[n+1] += a[b];
  35.             a[b] = 0;
  36.         }
  37.         else
  38.         {
  39.             b = p + 1;
  40.             while (a[b] == 0)
  41.                 ++b;
  42.             a[b] += a[p];
  43.             a[p] = 0;
  44.         }
  45.     }
  46.     t = a[0];
  47.     for (j = 1; j <= n+1; ++j)
  48.         if (t == 0 || (a[j] != 0 && a[j] < t))
  49.             t = a[j];
  50.     cout << t;
  51.     return 0;
  52. }
复制代码
作者: smileandyxu    时间: 2015-11-18 13:27
  1. #include <iostream>
  2. using namespace std;
  3. bool A[1001][1001];
  4. int n, m;
  5. int tot;
  6. int main()
  7. {
  8.     cin >> n >> m;
  9.     for (int i = 0; i != m; ++i)
  10.         A[i][i] = true;
  11.     for (int i = 0; i != n; ++i) {
  12.         int a, b;
  13.         cin >> a >> b;
  14.         if (!A[a][b]) {
  15.             A[a][b] = true;
  16.             A[b][a] = true;
  17.             for (int j = 0; j != m; ++j) {
  18.                 int flag = 0;
  19.                 if (A[a][j])
  20.                     flag = 1;
  21.                 if (A[b][j])
  22.                     flag = 2;
  23.                 if (flag == 1) {
  24.                     if (!A[b][j]) {
  25.                         A[b][j] = true;
  26.                         A[j][b] = true;
  27.                     }
  28.                     else
  29.                         ++tot;
  30.                 }
  31.                 if (flag == 2) {
  32.                     if (!A[a][j]) {
  33.                         A[a][j] = true;
  34.                         A[j][a] = true;
  35.                     }
  36.                     else
  37.                         ++tot;
  38.                 }
  39.             }
  40.         }
  41.         else
  42.             ++tot;
  43.     }
  44.     cout << tot;
  45.     return 0;
  46. }
复制代码
作者: smileandyxu    时间: 2015-11-18 13:51
  1. #include <iostream>
  2. #include <string>
  3. #include <algorithm>
  4. #define MAXN 100
  5. using namespace std;
  6. typedef struct num {
  7.     int data[MAXN];
  8. };
  9. void input_num(num &a)
  10. {
  11.     string s;
  12.     cin >> s;
  13.     for (int i = 0; i != s.size(); ++i) {
  14.         a.data[i] = int(s[i]) - 48;
  15.     }
  16. }
  17. void output_num(num a)
  18. {
  19.     int i = MAXN;
  20.     while (a.data[i] == 0)
  21.         --i;
  22.     while (i >= 0)
  23.         cout << a.data[i];
  24. }
  25. bool comp_num(num a, num b) {
  26.     int i = MAXN;
  27.     int j = MAXN;
  28.     while (a.data[i] == 0)
  29.         --i;
  30.     while (b.data[j] == 0)
  31.         --j;
  32.     if (i < j)
  33.         return true;
  34.     else if (i > j)
  35.         return false;
  36.     else {
  37.         while (i >= 0) {
  38.             if (a.data[i] < b.data[i])
  39.                 return true;
  40.             else if (a.data[i] > b.data[i])
  41.                 return false;
  42.             else
  43.                 --i;
  44.         }
  45.         return true;
  46.     }
  47. }
  48. void plus_num(num &a, num b)
  49. {
  50.     int x = 0;
  51.     for (int i = 0; i != MAXN; ++i) {
  52.         a.data[i] += b.data[i];
  53.         a.data[i] += x;
  54.         x = a.data[i] / 10;
  55.         a.data[i] %= 10;
  56.     }
  57. }
  58. void minus_num(num &a, num b)
  59. {
  60.    
  61. }
  62. num x[10000];
  63. num tot;
  64. int n;
  65. int main()
  66. {
  67.     cin >> n;
  68.     for (int i = 0; i != n; ++i)
  69.         input_num(x[i]);
  70.     sort(x, x + n, comp_num);
  71.     for (int i = 0; i != n; ++i) {
  72.         for (int j = i + 1; j != n; ++j) {
  73.             num y;
  74.             for (int k = 0; k != MAXN; ++k)
  75.                 y.data[k] = x[j].data[k];
  76.             minus_num(y, x[i]);
  77.             plus_num(tot, y);
  78.             tot += ((x[j] - x[i]) * 2);
  79.         }
  80.     }
  81.     output(tot);
  82.     return 0;
  83. }
复制代码
作者: hr567    时间: 2015-11-18 17:03
stone[3]
  1. //#include <iostream>
  2. #include <fstream>
  3. using namespace std;
  4. ifstream cin("stone3.in");
  5. ofstream cout("stone3.out");
  6. int a[50002];
  7. int l, n, k;
  8. int i, j, t, p, b, e;
  9. int main()
  10. {
  11.     cin >> l >> n >> k;
  12.     for (i = 1; i <= n; ++i)
  13.     {
  14.         cin >> j;
  15.         a[i] = j - t;
  16.         t = j;
  17.     }
  18.     a[n+1] = l - t;
  19.     for (i = 1; i <= k; ++i)
  20.     {
  21.         t = 0;
  22.         for (j = 0; j <= n+1; ++j)
  23.             if ((a[j] != 0 && a[j] < t) || t == 0)
  24.             {
  25.                 t = a[j];
  26.                 p = j;
  27.             }
  28.         b = 0;
  29.         while (a[b] == 0)
  30.             ++b;
  31.         if (p == b)
  32.         {
  33.             b = p + 1;
  34.             while (a[b] == 0)
  35.                 ++b;
  36.             a[b] += a[p];
  37.         }
  38.         else if (p == n+1)
  39.         {
  40.             e = p - 1;
  41.             while (a[e] == 0)
  42.                 --e;
  43.             a[p] += a[e];
  44.         }
  45.         else
  46.         {
  47.             b = p + 1;
  48.             while (a[b] == 0)
  49.                 ++b;
  50.             e = p - 1;
  51.             while (a[e] == 0)
  52.                 --e;
  53.             if (a[b] <= a[e])
  54.                 a[b] += a[p];
  55.             else
  56.                 a[e] += a[p];
  57.         }
  58.         a[p] = 0;
  59.     }
  60.     t = 0;
  61.     for (j = 0; j <= n; ++j)
  62.         if (t == 0 || (a[j] != 0 && a[j] < t))
  63.             t = a[j];
  64.     cout << t;
  65.     return 0;
  66. }
复制代码
作者: hr567    时间: 2015-11-18 17:11
stone[4]
  1. //#include <iostream>
  2. #include <fstream>
  3. using namespace std;
  4. ifstream cin("stone3.in");
  5. ofstream cout("stone3.out");
  6. int a[50002];
  7. int l, n, k;
  8. int i, j, t, p, b, e;
  9. int main()
  10. {
  11.     cin >> l >> n >> k;
  12.     for (i = 1; i <= n; ++i)
  13.     {
  14.         cin >> j;
  15.         a[i] = j - t;
  16.         t = j;
  17.     }
  18.     a[n+1] = l - t;
  19.     for (i = 1; i <= k; ++i)
  20.     {
  21.         t = 0;
  22.         for (j = 0; j <= n+1; ++j)
  23.             if ((a[j] != 0 && a[j] < t) || t == 0)
  24.             {
  25.                 t = a[j];
  26.                 p = j;
  27.             }
  28.         b = 1;
  29.         while (!a[b])
  30.             ++b;
  31.         if (p == b)
  32.         {
  33.             b = p + 1;
  34.             while (!a[b])
  35.                 ++b;
  36.             a[b] += a[p];
  37.             a[p] = 0;
  38.         }
  39.         else if (p == n+1)
  40.         {
  41.             e = p - 1;
  42.             while (!a[e])
  43.                 --e;
  44.             a[p] += a[e];
  45.             a[e] = 0;
  46.         }
  47.         else
  48.         {
  49.             b = p + 1;
  50.             while (!a[b])
  51.                 ++b;
  52.             e = p - 1;
  53.             while (!a[e])
  54.                 --e;
  55.             if (a[b] <= a[e])
  56.             {
  57.                 a[b] += a[p];
  58.                 a[p] = 0;
  59.             }
  60.             else
  61.             {
  62.                 a[p] += a[e];
  63.                 a[e] = 0;
  64.             }
  65.         }
  66.     }
  67.     t = 0;
  68.     for (j = 0; j <= n; ++j)
  69.         if (t == 0 || (a[j] != 0 && a[j] < t))
  70.             t = a[j];
  71.     cout << t;
  72.     return 0;
  73. }
复制代码
作者: smileandyxu    时间: 2015-11-18 17:12
  1. #include <iostream>
  2. using namespace std;
  3. int D[2001];
  4. int f[2001][501];
  5. int N, M;
  6. int main()
  7. {
  8.     cin >> N >> M;
  9.     for (int i = 1; i <= N; ++i)
  10.         cin >> D[i];
  11.     for (int i = 1; i <= N; ++i) {
  12.         for (int j = 1; j <= M; ++j) {
  13.             if (f[i - 1][j - 1] + D[i] > f[i][j])
  14.                 f[i][j] = f[i - 1][j - 1] + D[i];
  15.         }
  16.     }
  17.     cout << f[N][M];
  18.     return 0;
  19. }
复制代码
作者: hr567    时间: 2015-11-27 15:53
P1916
  1. #include <iostream>
  2. #include <cmath>
  3. using namespace std;
  4. int i, j, k, n, l, t;
  5. int a[1000];
  6. int main()
  7. {
  8.     ci >> k >> n;
  9.     t = j = 1;
  10.     for (i = 0; i <= log2(n); ++i)
  11.     {
  12.         a[j-1] = t;
  13.         j *= 2;
  14.     }
  15.     cout << a[n];
  16.     return 0;
  17. }
复制代码
作者: hr567    时间: 2015-11-27 16:07
  1. #include <iostream>
  2. #include <cmath>
  3. using namespace std;
  4. int i, j, k, n, l, t;
  5. int a[1000];
  6. int main()
  7. {
  8.     ci >> k >> n;
  9.     t = j = 1;
  10.     for (i = 0; i <= log2(n); ++i)
  11.     {
  12.         a[j-1] = t;
  13.         j *= 2;
  14.         t *= k;
  15.     }
  16.     for (i = 0; i <= n; ++i)
  17.     {
  18.         if (a[i])
  19.         {
  20.             ++i;
  21.             while (a[i])
  22.         }
  23.     }
  24.     cout << a[n];
  25.     return 0;
  26. }
复制代码
作者: hr567    时间: 2015-12-13 16:43
  1. #include <iostream>
  2. using namespace std;
  3. int a[5][5];
  4. int x_now, x_next, y_now, y_next;
  5. void pmn(int i)
  6. {
  7.     int j, k;
  8.     if (i == 25)
  9.         for (j = 0; j < 5; ++j)
  10.         {
  11.             for (k = 0; k < 5; ++k)
  12.                 cout << a[j][k] << ' ';
  13.             cout << endl;
  14.         }
  15.     else
  16.     {
  17.         x_next = x_now + 1;
  18.         x_next = x_now + 1;
  19.         x_next = x_now + 2;
  20.         x_next = x_now + 2;
  21.         x_next = x_now - 1;
  22.         x_next = x_now - 1;
  23.         x_next = x_now - 2;
  24.         x_next = x_now - 2;
  25.     }
  26. }
  27. int main()
  28. {
  29.     pmn(0);
  30.     return 0;
  31. }
复制代码
作者: smileandyxu    时间: 2015-12-15 13:52
  1. #include <iostream>
  2. using namespace std;
  3. int A[100];
  4. int F[100][100];
  5. int n;
  6. int main()
  7. {
  8.     cin >> n;
  9.     for (int i = 0; i != n; ++i)
  10.         cin >> A[i];
  11.     for (int i = 0; i != n - 2; ++i) {
  12.         F[i][i + 2] = A[i] * A[i + 1] * A[i + 2];
  13.     }
  14.     for (int i = 0; i != n - 2; ++i) {
  15.         for (int j = i + 2; j != n; ++j) {
  16.             for (int k = i + 1; k != j; ++k) {
  17.                 if (F[i][k] * k * F[k][j] < F[i][j])
  18.                     F[i][j] = F[i][k] * k * F[k][j];
  19.             }
  20.         }
  21.     }
  22.     cout << F[0][n - 1];
  23.     return 0;
  24. }
复制代码

作者: smileandyxu    时间: 2015-12-15 15:04
  1. #include <iostream>
  2. using namespace std;
  3. int A[100];
  4. int F[100][100];
  5. int n;
  6. int mysearch(int p, int q)
  7. {
  8.     if (q - p == 2) {
  9.         F[p][q] = A[p] * A[p + 1] * A[q];
  10.         return F[p][q];
  11.     }
  12.     else if (q - p > 2) {
  13.         for (int k = p + 1; k != q; ++k) {
  14.             int a = (F[p][k] > 0) ? F[p][k] : mysearch(p, k);
  15.             int b = (F[k][q] > 0) ? F[k][q] : mysearch(k, q);
  16.             if (a + b + (A[p] * A[k] * A[q]) < F[p][q])
  17.                 F[p][q] = a + b + (A[p] * A[k] * A[q]);
  18.         }
  19.         return F[p][q];
  20.     }
  21. }
  22. int main()
  23. {
  24.     cin >> n;
  25.     for (int i = 0; i != n; ++i)
  26.         cin >> A[i];
  27.     cout << mysearch(0, n - 1);
  28.     return 0;
  29. }
复制代码
作者: hr567    时间: 2015-12-15 20:10
  1. #include <iostream>
  2. using namespace std;
  3. int n, m, a[2000];
  4. int i, j, b[2000], c[2000];
  5. int main()
  6. {
  7.     cin >> n >> m;
  8.     for (i = 0; i < n; ++i)
  9.         cin >> a[i];
  10.     for (i = 0; i < n; ++i)
  11.     {
  12.         b
  13.     }
  14.     return 0;
  15. }
复制代码
作者: smileandyxu    时间: 2015-12-18 13:53
  1. #include <iostream>
  2. using namespace std;
  3. int F[400001][401];
  4. int A[401];
  5. int C[401];
  6. int H[401];
  7. int N, V;
  8. int main()
  9. {
  10.     cin >> N;
  11.     for (int i = 1; i <= N; ++i) {
  12.         cin >> H[i] >> A[i] >> C[i];
  13.         if (A[i] > V)
  14.             V = A[i];
  15.     }
  16.     for (int i = 1; i <= N; ++i) {
  17.         bool flag = false;
  18.         for (int j = V; j >= H[i]; --j) {
  19.             if (F[j - H[i]][0] + H[i] > F[j][0] && F[j - H[i]][i] < C[i] && F[j - H[i]][0] + H[i] <= A[i]) {
  20.                 F[j][0] = F[j - H[i]][0] + H[i];
  21.                 F[j][i] = F[j - H[i]][i] + 1;
  22.                 flag = true;
  23.             }
  24.         }
  25.         if (flag)
  26.             --i;;
  27.     }
  28.     cout << F[V][0] << endl;
  29.     for (int i = 1; i <= N; ++i)
  30.         cout << F[V][i] << " ";

  32.     return 0;
  33. }
复制代码
作者: hr567    时间: 2016-1-6 13:54
P1088
  1. #include <iostream>
  2. using namespace std;
  3. int a[2001];
  4. int i, j, n;
  5. int f[2001][2001];
  6. int main()
  7. {
  8.     cin >> n;
  9.     for (i = 1; i <= n; ++i)
  10.         cin >> a[i];
  11.     for (i = 1; i <= n; ++i)
  12.         f[i][0] = a[i]*i + f[i-1][0];
  13.     for (j = 1; j <= n; ++j)
  14.         f[0][j] = a[n-j+1]*j + f[0][j-1];
  15.     for (i = 1; i <= n; ++i)
  16.         for (j = 0; j <= n-i; ++j)
  17.         {
  18.             max(f[i-1][j] + a[i]*(i+j), f[i][j-1] + a[n-j-1]*(i+j));
  19.             f[i][j] = (n+i-j);
  20.         }
  21.     return 0;
  22. }
  23. /*
  24. 5
  25. 1 3 1 5 2
  26. */
复制代码
作者: hr567    时间: 2016-1-6 13:59
P1088
  1. #include <iostream>
  2. using namespace std;
  3. int a[2001];
  4. int i, j, n;
  5. int f[2001][2001];
  6. int ans;
  7. int main()
  8. {
  9.     cin >> n;
  10.     for (i = 1; i <= n; ++i)
  11.         cin >> a[i];
  12.     for (i = 1; i <= n; ++i)
  13.         f[i][0] = a[i]*i + f[i-1][0];
  14.     for (j = 1; j <= n; ++j)
  15.         f[0][j] = a[n-j+1]*j + f[0][j-1];
  16.     for (i = 1; i <= n; ++i)
  17.         for (j = 1; j <= n-i; ++j)
  18.             max(f[i-1][j] + a[i]*(i+j), f[i][j-1] + a[n-j-1]*(i+j));
  19.     for (i = 0; i <= n; ++i)
  20.         for (j = 0; j <= n-i; ++j)
  21.             ans = max(ans, f[i][j]);
  22.     cout << ans;
  23.     return 0;
  24. }
  25. /*
  26. 5
  27. 1 3 1 5 2
  28. */
复制代码
作者: hr567    时间: 2016-1-6 17:05
  1. for (i = 0; i < n; ++i)
  2. {
  3.     if (!b[i])
  4.         a[cnt++] = i;
  5.     for (j = 0; j < cnt && a[j]*i < m; ++j)
  6.     {
  7.         b[a[j]*i] = true;
  8.         if (i%a[j] == 0) break;
  9.     }
  10. }
复制代码
作者: smileandyxu    时间: 2016-3-11 13:46
#include <iostream>
#define INF 200000000
using namespace std;
int F[400001];
int A[100001];
int M, N;
inline int father(int x)
{
    return (x >> 1);
}
inline int lchild(int x)
{
    return (x << 1);
}
inline int rchild(int x)
{
    return (x << 1) + 1;
}
int index(int x)
{
    int l = 1;
    int r = M;
    int m = (l + r) / 2;
    int i = 1;
    while (r - l > 1) {
        if (x <= m) {
            i = lchild(i);
            r = m;
        }
        else {
            i = rchild(i);
            l = m;
        }
        m = (l + r) / 2;
    }
    return i + x - m;
}
int minimum(int l, int r, int ql, int qr, int i)
{
    int ans = INF;
    if (ql <= l && r <= qr)
        return F[i];
    else {
        int m = (l + r) / 2;
        if (ql <= m) {
            ans = min(ans, minimum(l, m, ql, qr, lchild(i)));
        }
        if (qr >= m + 1) {
            ans = min(ans, minimum(m + 1, r, ql, qr, rchild(i)));
        }
    }
    return ans;
}
void initialize()
{
    for (int i = 1; i <= M * 2; ++i)
        F[i] = INF;
}
void build(int l, int r, int i)
{
    if (l == r)
        F[i] = A[l];
    else {
        int m = (l + r) / 2;
        build(l, m, lchild(i));
        build(m + 1, r, rchild(i));
        F[i] = min(F[lchild(i)], F[rchild(i)]);
    }
}
void update(int p, int x)
{
    int i = index(p);
    bool flag = true;
    F[i] = x;
    i = father(i);
    while (i >= 1 && flag) {
        if (F[i] > x)
            F[i] = x;
        else
            flag = false;
        i = father(i);
    }
}
int main()
{
    cin >> M >> N;
    for (int i = 1; i <= M; ++i) {
        cin >> A[i];
    }
    initialize();
    build(1, M, 1);
    for (int i = 1; i <= N; ++i) {
        int p, x, y;
        cin >> p >> x >> y;
        if (p == 1) {
            cout << minimum(1, M, x, y, 1) << " ";
        }
        if (p == 2) {
            update(x, y);
        }
    }

    return 0;
}
作者: smileandyxu    时间: 2016-3-11 13:56
#include <iostream>
#define INF 200000000
using namespace std;
int F[400001];
int A[100001];
int P[100001];
int M, N;
inline int father(int x)
{
    return (x >> 1);
}
inline int lchild(int x)
{
    return (x << 1);
}
inline int rchild(int x)
{
    return (x << 1) + 1;
}
int minimum(int l, int r, int ql, int qr, int i)
{
    int ans = INF;
    if (ql <= l && r <= qr)
        return F[i];
    else {
        int m = (l + r) / 2;
        if (ql <= m) {
            ans = min(ans, minimum(l, m, ql, qr, lchild(i)));
        }
        if (qr >= m + 1) {
            ans = min(ans, minimum(m + 1, r, ql, qr, rchild(i)));
        }
    }
    return ans;
}
void initialize()
{
    for (int i = 1; i <= M * 2; ++i)
        F[i] = INF;
}
void build(int l, int r, int i)
{
    if (l == r) {
        F[i] = A[l];
        P[l] = i;
    }
    else {
        int m = (l + r) / 2;
        build(l, m, lchild(i));
        build(m + 1, r, rchild(i));
        F[i] = min(F[lchild(i)], F[rchild(i)]);
    }
}
void update(int p, int x)
{
    int i = P[p];
    bool flag = true;
    F[i] = x;
    i = father(i);
    while (i >= 1 && flag) {
        if (F[i] > x)
            F[i] = x;
        else
            flag = false;
        i = father(i);
    }
}
int main()
{
    cin >> M >> N;
    for (int i = 1; i <= M; ++i) {
        cin >> A[i];
    }
    initialize();
    build(1, M, 1);
    for (int i = 1; i <= N; ++i) {
        int p, x, y;
        cin >> p >> x >> y;
        if (p == 1) {
            cout << minimum(1, M, x, y, 1) << " ";
        }
        if (p == 2) {
            update(x, y);
        }
    }
    for (int i = 1; i <= M; ++i)
        cout << P[i] << " ";
    return 0;
}
作者: smileandyxu    时间: 2016-3-22 13:52
  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;
  4. double V[150][150];
  5. double L[150][150];
  6. double D[150];
  7. double O[150];
  8. int F[150];
  9. int M, N, E;
  10. void initialize()
  11. {
  12.     for (int i = 1; i != 150; ++i)
  13.         D[i] = 200000000;
  14.     for (int i = 0; i != 150; ++i)
  15.         F[i] = i;
  16.     O[0] = 70;
  17. }
  18. void input()
  19. {
  20.     cin >> N >> M >> E;
  21.     for (int i = 0, a, b; i != M; ++i) {
  22.         cin >> a >> b;
  23.         cin >> V[a][b] >> L[a][b];
  24.     }
  25. }
  26. void spfa()
  27. {
  28.     queue<int> Q;
  29.     bool B[150];
  30.     B[0] = true;
  31.     Q.push(0);
  32.     while (!Q.empty()) {
  33.         int k = Q.front();
  34.         B[k] = false;
  35.         Q.pop();
  36.         for (int i = 0; i != N; ++i) {
  37.             if (V[k][i] == 0) {
  38.                 if (D[k] + (L[k][i] / O[k]) < D[i]) {
  39.                     D[i] = D[k] + (L[k][i] / O[k]);
  40.                     O[i] = O[k];
  41.                     F[i] = k;
  42.                     if (B[i]) {
  43.                         Q.push(i);
  44.                         B[i] = true;
  45.                     }
  46.                 }
  47.             }
  48.             else {
  49.                 if (D[k] + (L[k][i] / V[k][i]) < D[i]) {
  50.                     D[i] = D[k] + (L[k][i] / V[k][i]);
  51.                     O[i] = V[k][i];
  52.                     F[i] = k;
  53.                     if (B[i]) {
  54.                         Q.push(i);
  55.                         B[i] = true;
  56.                     }
  57.                 }
  58.             }
  59.         }
  60.     }
  61. }
  62. void output(int p = E)
  63. {
  64.     if (F[p] != p)
  65.         output(F[p]);
  66.     cout << p << " ";
  67. }
  68. int main()
  69. {
  70.     initialize();
  71.     input();
  72.     spfa();
  73.     output();
  74.     return 0;
  75. }
复制代码
作者: smileandyxu    时间: 2016-3-22 15:08
  1. #include <iostream>
  2. using namespace std;
  3. const int LEN = 200;
  4. int A[202][3];
  5. int n;
  6. void print(int x)
  7. {
  8.     int i = LEN - 1;
  9.     while (A[i][x % 3] == 0)
  10.         --i;
  11.     while (i >= 0) {
  12.         cout << A[i][x % 3];
  13.         --i;
  14.     }
  15. }
  16. int main()
  17. {
  18.     cin >> n;
  19.     A[0][1] = 1;
  20.     A[0][2] = 5;
  21.     for (int i = 3; i <= n; ++i) {
  22.         cout << i << ":";
  23.         print(i);
  24.         cout << endl;
  25.         int p = i % 3;
  26.         int x = 0;
  27.         for (int j = 0; j != LEN; ++j) {
  28.             A[j][p] = A[j][(p + 2) % 3] * 3;
  29.             A[j][p] += x;
  30.             x = A[j][p] / 10;
  31.             A[j][p] %= 10;
  32.         }
  33.         x = 0;
  34.         for (int j = 0; j != LEN; ++j) {
  35.             A[j][p] -= A[j][(p + 1) % 3];
  36.             while (A[j][p] < 0) {
  37.                 --A[j + 1][p];
  38.                 A[j][p] += 10;
  39.             }
  40.         }
  41.         A[0][p] += 2;
  42.         int j = 0;
  43.         while (A[j][p] > 10) {
  44.             A[j][p] -= 10;
  45.             ++A[j + 1][p];
  46.             ++j;
  47.         }
  48.     }
  49.     int i = LEN - 1;
  50.     while (A[i][n % 3] == 0)
  51.         --i;
  52.     while (i >= 0) {
  53.         cout << A[i][n % 3];
  54.         --i;
  55.     }
  56.     return 0;
  57. }
复制代码
作者: smileandyxu    时间: 2016-3-22 20:10
  1. #include <iostream>
  2. #define MAXN 100001
  3. #define INF 0x3f3f3f3f
  4. #define father(x) (x >> 1)
  5. #define lchild(x) (x << 1)
  6. #define rchild(x) ((x << 1) + 1)
  7. using namespace std;
  8. struct node {
  9.     int left;
  10.     int right;
  11.     int sum;
  12.     int add;
  13. };
  14. node F[MAXN * 4];
  15. int P[MAXN];
  16. int A[MAXN];
  17. int n;
  18. void initialize()
  19. {
  20.     for (int i = 1; i <= MAXN * 4; ++i) {
  21.         F[i].sum = 0;
  22.         F[i].add = 0;
  23.     }
  24. }
  25. void input()
  26. {
  27.     cin >> n;
  28.     for (int i = 1; i <= n; ++i)
  29.         cin >> A[i];
  30. }
  31. void build(int l = 1, int r = n, int i = 1)
  32. {
  33.     F[i].left = l;
  34.     F[i].right = r;
  35.     if (l == r) {
  36.         F[i].sum = A[l];
  37.         P[l] = i;
  38.     }
  39.     else {
  40.         int d = (l + r) / 2;
  41.         build(l, d, lchild(i));
  42.         build(d + 1, r, rchild(i));
  43.         F[i].sum = F[lchild(i)].sum + F[rchild(i)].sum;
  44.     }
  45. }
  46. void update(int l, int r, int x, int i = 1)
  47. {
  48.     if (F[i].left == l && r == F[i].right) {
  49.         F[i].add = x;
  50.     }
  51.     else {
  52.         int d = (F[i].left + F[i].right) / 2;
  53.         if (l <= d)
  54.             update(l, d, x, lchild(i));
  55.         if (r > d)
  56.             update(d, r, x, rchild(i));
  57.     }
  58. }
  59. int query(int l, int r, int i = 1)
  60. {
  61.     if (F[i].left == l && F[i].right == r)
  62.         return F[i].sum + (r - l + 1) * F[i].add;
  63.     else {
  64.         0
  65.     }
  66. }
  67. int main()
  68. {
  69.     initialize();
  70.     input();
  71.     build();

  73.     return 0;
  74. }
复制代码
作者: smileandyxu    时间: 2016-3-29 15:49
  1. #include <iostream>
  2. using namespace std;
  3. int F[501][501];
  4. int A[501];
  5. int B[501];
  6. int C[501];
  7. int m, n;
  8. void dfs(int p, int k)
  9. {
  10.     if (F[p][k] != -1)
  11.         return;
  12.     else if (k == 0) {
  13.         F[p][k] = 0;
  14.         return;
  15.     }
  16.     else if (p == -1)
  17.         return;
  18.     else {
  19.         dfs(B[p], k);
  20.         F[p][k] = F[B[p]][k];
  21.         for (int j = 0; j != k; ++j) {
  22.             dfs(C[p], j);
  23.             dfs(B[p], k - j - 1);
  24.             if (F[C[p]][j] + F[B[p]][k - j - 1] + A[p] > F[p][k])
  25.                 F[p][k] = F[C[p]][j] + F[B[p]][k - j - 1] + A[p];
  26.         }
  27.     }
  28. }
  29. int main()
  30. {
  31.     cin >> n >> m;
  32.     for (int i = 0; i <= n; ++i) {
  33.         B[i] = -1;
  34.         C[i] = -1;
  35.         for (int j = 0; j <= m; ++j)
  36.             F[i][j] = -1;
  37.     }
  38.     for (int i = 1, a; i <= n; ++i) {
  39.         cin >> a >> A[i];
  40.         B[i] = C[a];
  41.         C[a] = i;
  42.     }
  43.     dfs(C[0], m);
  44.     cout << F[C[0]][m];
  45.     return 0;
  46. }
复制代码
作者: smileandyxu    时间: 2016-3-29 20:12
  1. #include <iostream>
  2. #include <stack>
  3. using namespace std;
  4. int A[10001];
  5. int n, k, sum, l, r;
  6. int main()
  7. {
  8.     cin >> n >> k;
  9.     for (int i = 1; i <= n; ++i) {
  10.         cin >> A[i];
  11.         r += A[i];
  12.         if (A[i] > l)
  13.             l = A[i];
  14.     }
  15.     bool flag = true;
  16.     while (r - l > 1 && flag) {
  17.         int d = (l + r) / 2;
  18.         int a = 0;
  19.         int cnt = 0;
  20.         int tmp = 0;
  21.         int len = 0;
  22.         cout << d << ":" << endl;
  23.         for (int i = 1; i <= n; ++i) {
  24.             tmp += A[i];
  25.             if (tmp >= d) {
  26.                 if (tmp > d) {
  27.                     tmp -= A[i];
  28.                     --i;
  29.                 }
  30.                 if (tmp > len)
  31.                     len = tmp;
  32.                 tmp = 0;
  33.                 ++cnt;
  34.             }
  35.         }
  36.         ++cnt;
  37.         if (cnt == k) {
  38.             stack<int> S;
  39.             for (int i = n; i >= 1; --i) {
  40.                 tmp += A[i];
  41.                
  42.             }
  43.             cout << "#" << d << endl;
  44.             flag = false;
  45.         }
  46.         if (cnt > k)
  47.             l = d + 1;
  48.         if (cnt < k)
  49.             r = d;
  50.     }
  51.     return 0;
  52. }
复制代码
作者: smileandyxu    时间: 2016-4-2 12:56
  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4. #define INF 200000000
  5. using namespace std;
  6. vector<int> V[10001];
  7. int B[10001];
  8. int D[10001];
  9. int m, n, s, t;
  10. void dfs(int i)
  11. {
  12.     if (B[i] != 0)
  13.         return;
  14.     else if (V[i].size() == 0) {
  15.         B[i] = -1;
  16.     }
  17.     else {
  18.         int flag = 1;
  19.         for (int j = 0; j != V[i].size() && flag == 1; ++j) {
  20.             dfs(V[i][j]);
  21.             flag = B[V[i][j]];
  22.         }
  23.         B[i] = flag;
  24.     }
  25. }
  26. void spfa()
  27. {
  28.     queue<int> Q;
  29.     bool U[10001];
  30.     Q.push(s);
  31.     U[s] = true;
  32.     while (!Q.empty()) {
  33.         int k = Q.front();
  34.         Q.pop();
  35.         U[k] = false;
  36.         for (int i = 0; i != V[k].size(); ++i) {
  37.             if (B[V[k][i]] && D[k] + 1 < D[V[k][i]]) {
  38.                 D[V[k][i]] = D[k] + 1;
  39.                 if (!U[V[k][i]]) {
  40.                     Q.push(V[k][i]);
  41.                     U[V[k][i]] = true;
  42.                 }
  43.             }
  44.         }
  45.     }
  46. }
  47. int main()
  48. {
  49.     cin >> n >> m;
  50.     for (int i = 0, u, v; i != m; ++i) {
  51.         cin >> u >> v;
  52.         V[u].push_back(v);
  53.     }
  54.     cin >> s >> t;
  55.     B[t] = 1;
  56.     dfs(s);

  58.     for (int i = 1; i <= n; ++i)
  59.         D[i] = INF;
  60.     D[s] = 0;
  61.     spfa();
  62.     if (D[t] == INF)
  63.         cout << "-1";
  64.     else
  65.         cout << D[t];
  66.     return 0;
  67. }
复制代码
作者: smileandyxu    时间: 2016-4-5 12:37
  1. #include <iostream>
  2. #include <cctype>
  3. #include <queue>
  4. #define INF 0x6fffffff
  5. using namespace std;
  6. deque<int> P[1001]; ///max
  7. deque<int> Q[1001]; ///min
  8. deque<int> M; ///max
  9. deque<int> N; ///min
  10. int A[1001][1001];
  11. int a, b, n, x, y;
  12. int main()
  13. {
  14.     cin >> a >> b >> n;
  15.     for (int i = 0; i != a; ++i)
  16.         for (int j = 0; j != b; ++j)
  17.             cin >> A[i][j];
  18.     x = INF;
  19.     y = -INF;
  20.     for (int j = 0; j != n - 1; ++j) {
  21.         for (int i = 0; i != a; ++i) {
  22.             while (!P[i].empty() && A[i][j] >= A[i][P[i].back()])
  23.                 P[i].pop_back();
  24.             P[i].push_back(j);
  25.             while (!Q[i].empty() && A[i][j] <= A[i][Q[i].back()])
  26.                 Q[i].pop_back();
  27.             Q[i].push_back(j);
  28.         }
  29.     }
  30.     for (int j = n - 1; j + n - 1 != b; ++j) {
  31.         M.clear();
  32.         N.clear();
  33.         for (int i = 0; i != a; ++i) {
  34.             while (!P[i].empty() && A[i][j] >= A[i][P[i].back()])
  35.                 P[i].pop_back();
  36.             P[i].push_back(j);
  37.             while (!Q[i].empty() && A[i][j] <= A[i][Q[i].back()])
  38.                 Q[i].pop_back();
  39.             Q[i].push_back(j);
  40.         }
  41.         for (int i = 0; i != a; ++i) {
  42.             while (P[i].front() < j)
  43.                 P[i].pop_front();
  44.             while (Q[i].front() < j)
  45.                 Q[i].pop_front();
  46.         }
  47.         for (int i = 0; i != n - 1; ++i) {
  48.             while (!M.empty() && A[i][P[i].front()] >= M.back())
  49.                 M.pop_back();
  50.             M.push_back(P[i].front());
  51.             while (!N.empty() && A[i][Q[i].front()] <= N.back())
  52.                 N.pop_back();
  53.             N.push_back(Q[i].front());
  54.         }
  55.         for (int i = n - 1; i + n - 1 != a; ++i) {
  56.             while (!M.empty() && A[i][P[i].front()] >= M.back())
  57.                 M.pop_back();
  58.             M.push_back(i);
  59.             while (!N.empty() && A[i][Q[i].front()] <= N.back())
  60.                 N.pop_back();
  61.             N.push_back(i);
  62.             while (M.front() < i)
  63.                 M.pop_front();
  64.             x = min(x, A[M.front()][P[M.front()].front()]);
  65.             while (N.front() < i)
  66.                 N.pop_front();
  67.             y = max(y, A[N.front()][Q[N.front()].front()]);
  68.         }
  69.     }
  70.     cout << x << " " << y;
  71.     return 0;
  72. }
复制代码
作者: smileandyxu    时间: 2016-4-7 13:50
  1. #include <iostream>
  2. using namespace std;
  3. int A[50];
  4. int n, tot;
  5. bool same(int i, int j, int x, int y)
  6. {
  7.     bool flag = true;
  8.     for (int p = 0; i + p <= j && flag; ++p)
  9.         if (A[i + p] != A[x + p])
  10.             flag = false;
  11.     return flag;
  12. }
  13. bool can(int i, int x)
  14. {
  15.     bool flag = true;
  16.     if (i >= 2) {
  17.         flag = !(A[i - 2] == x && A[i - 1] == x);
  18.         for (int l = 2; l <= (i + 1) / 3 && flag; ++l) {
  19.             for (int j = 0; j != l && flag; ++j) {
  20.                 int cnt = 1;
  21.                 for (int k = i - l + 1; k - l >= 0 && flag; k -= l) {
  22.                     if (same(k, k + l - 1, k - l, k - 1)) {
  23.                         ++cnt;
  24.                         if (cnt == 3)
  25.                             flag = false;
  26.                     }
  27.                     else {
  28.                         cnt = 1;
  29.                     }
  30.                 }
  31.             }
  32.         }
  33.     }
  34.     return flag;
  35. }
  36. void dfs(int i)
  37. {
  38.     if (i == n) {
  39.         ++tot;
  40.         //cout << tot << endl;
  41.     }
  42.     else {
  43.         A[i] = 0;
  44.         if (can(i, 0))
  45.             dfs(i + 1);
  46.         A[i] = 1;
  47.         if (can(i, 1)) {
  48.             dfs(i + 1);
  49.         }
  50.     }
  51. }
  52. int main()
  53. {

  55.     cin >> n;
  56.     if (n == 1)
  57.         tot = 2;
  58.     else if (n == 2)
  59.         tot = 4;
  60.     else {
  61.         dfs(1);
  62.         tot *= 2;
  63.     }
  64.     cout << tot;
  65.     return 0;
  66. }
复制代码
作者: hr567    时间: 2016-4-8 13:51
#include <iostream>
using namespace std;
int f[100+1][100+1][100+1];
int a[100+1];
int pmn(int l, int r, int k)
{
    int &p = f[l][r][k];
    if (p == 0)
    {
        for (int m = l; m < r; ++m)
        {
            for (int t = 0; t <= k && t <= m - l; ++t)
            {
                p = max(p, max(pmn(l, m, t) + pmn(m+1, r, k-t), pmn(l, m, t) * pmn(m+1, r, k-t-1)));
            }
        }
    }
    return p;
}
/*
5 2
1 2 3 4 5
*/
int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        a[i] += a[i-1];
        for (int j = 1; j <= i; ++j)
            f[j][i][0] = a[i] - a[j-1];
    }
    cout << pmn(1, n, k) << endl;
    return 0;
}
作者: smileandyxu    时间: 2016-4-11 13:53
tyvj3075
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #define INF 0x6fffffff
  5. using namespace std;
  6. vector<int> V[101];
  7. bool B[101];
  8. int A[101];
  9. int n, s, ans;
  10. void add(int u, int v)
  11. {
  12.     if (u == 0 || v == 0)
  13.         return;
  14.     else {
  15.         V[u].push_back(v);
  16.         V[v].push_back(u);
  17.     }
  18. }
  19. void dfs(int p, int d)
  20. {
  21.     if (V[p].size() == 1 && B[V[p][0]])
  22.         return;
  23.     else {
  24.         B[p] = true;
  25.         s += A[p] * d;
  26.         for (int i = 0; i != V[p].size(); ++i) {
  27.             if (!B[V[p][i]])
  28.                 dfs(V[p][i], d + 1);
  29.         }
  30.     }
  31. }
  32. int main()
  33. {
  34.     cin >> n;
  35.     for (int i = 1, w, l, r; i <= n; ++i) {
  36.         cin >> A[i] >> l >> r;
  37.         add(i, l);
  38.         add(i, r);
  39.     }
  40.     ans = INF;
  41.     for (int i = 1; i <= n; ++i) {
  42.         B[i] = true;
  43.         dfs(i, 0);
  44.         if (s < ans)
  45.             ans = s;
  46.         s = 0;
  47.         B[i] = false;
  48.     }
  49.     cout << ans;
  50.     return 0;
  51. }
复制代码
作者: smileandyxu    时间: 2016-4-13 13:34
  1. #include <iostream>
  2. #include <stack>
  3. using namespace std;
  4. const int A[46] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903};
  5. stack<int> S;
  6. int B[46];
  7. int n;
  8. int main()
  9. {
  10.     while (cin >> n) {
  11.         int t = n;
  12.         int i = 45;
  13.         if (n == 1) {
  14.             S.push(1);
  15.             t = 0;
  16.         }
  17.         while (t > 0 && i >= 0) {
  18.             if (A[i] < t || (A[i] == t && t != n)) {
  19.                 if (t / A[i] > 2 || t / A[i] == 2) {
  20.                     S.push(A[i]);
  21.                     S.push(A[i]);
  22.                     t -= 2 * A[i];
  23.                 }
  24.                 else {
  25.                     S.push(A[i]);
  26.                     t -= A[i];
  27.                 }
  28.             }
  29.             --i;
  30.         }
  31.         if (t != 0)
  32.             cout << "Illegal";
  33.         while (!S.empty()) {
  34.             cout << S.top() << " ";
  35.             S.pop();
  36.         }
  37.         cout << endl;
  38.     }
  39.     return 0;
  40. }
复制代码
作者: smileandyxu    时间: 2016-4-13 13:53
  1. #include <iostream>
  2. using namespace std;
  3. int A[50];
  4. int n, tot;
  5. bool can(int i)
  6. {

  8. }
  9. void dfs(int i)
  10. {
  11.     if (i == n)
  12.         ++tot;
  13.     else {
  14.         A[i] = 0;
  15.         if (can(i))
  16.             dfs(i + 1);
  17.         A[i] = 1;
  18.         if (can(i))
  19.             dfs(i + 1);
  20.     }
  21. }
  22. int main()
  23. {

  25.     cin >> n;
  26.     dfs(1);
  27.     tot *= 2;
  28.     cout << tot;
  29.     return 0;
  30. }
复制代码
作者: smileandyxu    时间: 2016-4-18 13:50
  1. #include <cstdio>
  2. #include <cctype>
  3. #define INF 0x7fffffff
  4. using namespace std;
  5. inline int getint()
  6. {
  7.     char c = getchar();
  8.     while (!isdigit(c))
  9.         c = getchar();
  10.     int x = 0;
  11.     while (isdigit(c)) {
  12.         x = x * 10 + c - '0';
  13.         c = getchar();
  14.     }
  15.     return x;
  16. }
  17. int F[50001][2];
  18. int P[50001][2];
  19. int A[50001];
  20. int S[50001];
  21. int m, n, l, d, r, len;
  22. int main()
  23. {
  24.     n = getint();
  25.     m = getint();
  26.     for (int i = 1; i <= n; ++i) {
  27.         A[i] = getint();
  28.         S[i] = S[i - 1] + A[i];
  29.         if (A[i] > l)
  30.             l = A[i];
  31.     }
  32.     r = S[n];
  33.     len = INF;
  34.     d = (l + r) / 2;
  35.     while (l < d) {
  36.         d = (l + r) / 2;
  37.         //cout << l << " " << d << " " << r << "=";
  38.         int cnt = 0;
  39.         int tmp = 0;
  40.         int maxlen = 0;
  41.         for (int i = 1; i <= n; ++i) {
  42.             if (tmp + A[i] > d) {
  43.                 if (tmp > maxlen)
  44.                     maxlen = tmp;
  45.                 tmp = A[i];
  46.                 ++cnt;
  47.             }
  48.             else
  49.                 tmp += A[i];
  50.         }
  51.         if (tmp > maxlen)
  52.             maxlen = tmp;
  53.         //cout << cnt << endl;
  54.         if (cnt <= m) {
  55.             if (maxlen < len)
  56.                 len = maxlen;
  57.             r = d;
  58.         }
  59.         else {
  60.             l = d + 1;
  61.             d = (l + r) / 2;
  62.         }
  63.     }
  64.     if (l == d) {
  65.         int cnt = 0;
  66.         int tmp = 0;
  67.         int maxlen = 0;
  68.         for (int i = 1; i <= n; ++i) {
  69.             if (tmp + A[i] > d) {
  70.                 if (tmp > maxlen)
  71.                     maxlen = tmp;
  72.                 tmp = A[i];
  73.                 ++cnt;
  74.             }
  75.             else
  76.                 tmp += A[i];
  77.         }
  78.         if (tmp > maxlen)
  79.             maxlen = tmp;
  80.         if (cnt <= m) {
  81.             if (maxlen < len)
  82.                 len = maxlen;
  83.         }
  84.     }
  85.     printf("%d\40", len);
  86.     for (int i = 1; i <= n; ++i) {
  87.         F[i][0] = 1;
  88.         P[i][0] = P[i - 1][0] + F[i][0];
  89.     }
  90.     for (int j = 1; j <= m; ++j) {
  91.         int pos = 1;
  92.         for (int i = 1; i <= n; ++i) {
  93.             bool flag = true;
  94.             for (int k = pos; k < i && flag; ++k) {
  95.                 if (S[i] - S[k - 1] <= len) {
  96.                     F[i][j % 2] = (P[i - 1][(j + 1) % 2] - P[pos - 1][(j + 1) % 2]) % 10007;
  97.                     P[i][j % 2] = (P[i - 1][j % 2] + F[i][j % 2]) % 10007;
  98.                     flag = false;
  99.                 }
  100.                 else
  101.                     pos = k + 1;
  102.             }
  103.         }
  104.     }
  105.     for (int i = 1; i <= n; ++i) {
  106.         printf("%d\40", F[i][m % 2]);
  107.     }
  108.     printf("%d", F[n][m % 2]);
  109.     return 0;
  110. }
复制代码
作者: smileandyxu    时间: 2016-4-19 13:52
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <cctype>
  4. #define INF 0x7fffffff
  5. using namespace std;
  6. inline int getint()
  7. {
  8.     char c = getchar();
  9.     while (!isdigit(c))
  10.         c = getchar();
  11.     int x = 0;
  12.     while (isdigit(c)) {
  13.         x = x * 10 + c - '0';
  14.         c = getchar();
  15.     }
  16.     return x;
  17. }
  18. int F[50001][2];
  19. int C[50001][2];
  20. int A[50001];
  21. int S[50001];
  22. int m, n, l, d, r, len, sum;
  23. int main()
  24. {
  25.     n = getint();
  26.     m = getint();
  27.     for (int i = 1; i <= n; ++i) {
  28.         A[i] = getint();
  29.         S[i] = S[i - 1] + A[i];
  30.         if (A[i] > l)
  31.             l = A[i];
  32.     }
  33.     r = S[n];
  34.     len = INF;
  35.     d = (l + r) / 2;
  36.     while (l <= r) {
  37.         d = (l + r) / 2;
  38.         int cnt = 0;
  39.         int tmp = 0;
  40.         int maxlen = 0;
  41.         for (int i = 1; i <= n; ++i) {
  42.             if (tmp + A[i] > d) {
  43.                 if (tmp > maxlen)
  44.                     maxlen = tmp;
  45.                 tmp = A[i];
  46.                 ++cnt;
  47.             }
  48.             else
  49.                 tmp += A[i];
  50.         }
  51.         if (tmp > maxlen)
  52.             maxlen = tmp;
  53.         //cout << cnt << endl;
  54.         if (cnt <= m) {
  55.             if (maxlen < len)
  56.                 len = maxlen;
  57.             r = d - 1;
  58.         }
  59.         else
  60.             l = d + 1;
  61.     }
  62.     printf("%d\40", len);
  63.     /*for (int i = 1; i <= n; ++i) {
  64.         F[i][0] = 1;
  65.         C[i][0] = C[i - 1][0] + F[i][0];
  66.     }*/
  67.     F[1][0] = 1;
  68.     sum = n;
  69.     for (int j = 1; j <= m; ++j) {
  70.         int p = j % 2;
  71.         int tmp = sum;
  72.         int pos = 1;
  73.         sum = 0;
  74.         for (int i = j + 1; i <= n; ++i) {
  75.             bool flag = true;
  76.             for (int k = pos; k < i && flag; ++k) {
  77.                 if (S[i] - S[k] <= len) {
  78.                     flag = false;
  79.                     pos = k;
  80.                 }
  81.                 else
  82.                     tmp -= F[k][p ^ 1];
  83.             }
  84.             F[i][p] = tmp;
  85.             tmp += F[i][p ^ 1];
  86.             sum += F[i][p];
  87.         }




  92.         cout << j << ":" << endl;
  93.         for (int i = 1; i <= n; ++i)
  94.             cout << F[i][p] << " ";
  95.         cout << endl;
  96.         for (int i = 1; i <= n; ++i)
  97.             cout << C[i][p] << " ";
  98.         cout << endl;
  99.     }
  100.     /*for (int i = 1; i <= n; ++i)
  101.         printf("%d\40", F[i][m % 2]);*/
  102.     printf("\n");
  103.     printf("%d", F[n][m % 2]);
  104.     return 0;
  105. }
复制代码
作者: smileandyxu    时间: 2016-4-19 20:20
  1. P1882 [NOIP2000P4]单词接龙[code]#include <iostream>
  2. #include <string>
  3. using namespace std;
  4. bool C[21][21]; ///i包含j C[i][j] || C[j][i] ...
  5. int B[21][21];
  6. string S[21];
  7. int A[51];
  8. int P[51];
  9. char c;
  10. int n, tmp, ans;
  11. bool can(int i)
  12. {
  13.     bool flag = false;
  14.     for (int j = 1; j <= n && (!flag); ++j)
  15.         if (P[j] <= 1 && B[A[i - 1]][j] > 0 && (!C[A[i - 1]][j]) && (!C[j][A[i - 1]]))
  16.             flag = true;
  17.     return flag;
  18. }
  19. void dfs(int i)
  20. {
  21.     for (int k = 0; k < i; ++k) {
  22.         cout << S[A[k]] << " ";
  23.         cout << endl;
  24.     }
  25.     if (!can(i))
  26.         if (tmp > ans)
  27.             ans = tmp;
  28.     else {
  29.         for (int j = 1; j <= n; ++j) {
  30.             if (P[j] <= 1 && B[A[i - 1]][j] > 0 && (!C[A[i - 1]][j]) && (!C[j][A[i - 1]])) {
  31.                 ++P[j];
  32.                 A[i] = j;
  33.                 tmp += (S[j].size() - B[i][j]);
  34.                 dfs(i + 1);
  35.                 tmp -= (S[j].size() - B[i][j]);
  36.                 --P[j];
  37.             }
  38.         }
  39.     }
  40. }
  41. int main()
  42. {
  43.     cin >> n;
  44.     for (int i = 1; i <= n; ++i)
  45.         cin >> S[i];
  46.     cin >> c;
  47.     for (int i = 1; i <= n - 1; ++i) {
  48.         for (int j = i + 1; j <= n; ++j) {
  49.             for (int k = 1; k <= S[i].size() - 1 && k <= S[j].size() - 1; ++k) {
  50.                 if (S[i].substr(S[i].size() - k, k) == S[j].substr(0, k))
  51.                     B[i][j] = k;
  52.                 if (S[j].substr(S[j].size() - k, k) == S[i].substr(0, k))
  53.                     B[j][i] = k;
  54.             }
  55.             if (S[i].size() >= S[j].size())
  56.                 for (int k = 0; k + S[j].size() <= S[i].size(); ++k)
  57.                     if (S[i].substr(k, S[j].size()) == S[j])
  58.                         C[i][j] = true;
  59.             else
  60.                 for (int k = 0; k + S[i].size() <= S[j].size(); ++k)
  61.                     if (S[j].substr(k, S[i].size()) == S[i])
  62.                         C[j][i] = true;
  63.         }
  64.     }
  65.     for (int i = 1; i <= n; ++i) {
  66.         for (int j = 1; j <= n; ++j) {
  67.             cout << B[i][j] << " ";
  68.         }
  69.         cout << endl;
  70.     }
  71.     for (int i = 1; i <= n; ++i) {
  72.         if (S[i][0] == c) {
  73.             A[0] = i;
  74.             tmp = S[i].size();
  75.             ++P[i];
  76.             dfs(1);
  77.             --P[i];
  78.         }
  79.     }
  80.     cout << ans;
  81.     return 0;
  82. }
复制代码
[/code]
作者: smileandyxu    时间: 2016-4-23 18:36
木棍分割
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <cctype>
  4. #define INF 0x7fffffff
  5. using namespace std;
  6. inline int getint()
  7. {
  8.     char c = getchar();
  9.     while (!isdigit(c))
  10.         c = getchar();
  11.     int x = 0;
  12.     while (isdigit(c)) {
  13.         x = x * 10 + c - '0';
  14.         c = getchar();
  15.     }
  16.     return x;
  17. }
  18. int F[50001][2];
  19. int C[50001][2];
  20. int A[50001];
  21. int S[50001];
  22. int m, n, l, d, r, len, ans;
  23. int main()
  24. {
  25.     n = getint();
  26.     m = getint();
  27.     for (int i = 1; i <= n; ++i) {
  28.         A[i] = getint();
  29.         S[i] = S[i - 1] + A[i];
  30.         if (A[i] > l)
  31.             l = A[i];
  32.     }
  33.     r = S[n];
  34.     len = INF;
  35.     d = (l + r) / 2;
  36.     while (l <= r) {
  37.         d = (l + r) / 2;
  38.         int cnt = 0;
  39.         int tmp = 0;
  40.         int maxlen = 0;
  41.         for (int i = 1; i <= n; ++i) {
  42.             if (tmp + A[i] > d) {
  43.                 if (tmp > maxlen)
  44.                     maxlen = tmp;
  45.                 tmp = A[i];
  46.                 ++cnt;
  47.             }
  48.             else
  49.                 tmp += A[i];
  50.         }
  51.         if (tmp > maxlen)
  52.             maxlen = tmp;
  53.         //cout << cnt << endl;
  54.         if (cnt <= m) {
  55.             if (maxlen < len)
  56.                 len = maxlen;
  57.             r = d - 1;
  58.         }
  59.         else
  60.             l = d + 1;
  61.     }
  62.     printf("%d\40", len);
  63.     for (int i = 1; i <= n; ++i) {
  64.         if (S[i] <= len)
  65.             F[i][0] = 1;
  66.     }

  68.         cout << 0 << ":" << endl;
  69.         for (int i = 1; i <= n; ++i)
  70.             cout << F[i][0] << " ";
  71.         cout << endl;
  72.     for (int j = 1; j <= m; ++j) {
  73.         int p = j % 2;
  74.         int tmp = 0;
  75.         int pos = 1;
  76.         for (int i = 1; i <= j; ++i)
  77.             F[i][p ^ 1] = 0;
  78.         for (int i = j + 1; i <= n; ++i) {
  79.             for (int k = pos; k < i; ++k) {
  80.                 if (S[i] - S[k] <= len) {
  81.                     tmp += F[k][p ^ 1];
  82.                     pos = k;
  83.                 }
  84.                 else
  85.                     tmp -= F[k][p ^ 1];
  86.             }
  87.             F[i][p] = tmp;
  88.             tmp += F[i][p ^ 1];
  89.         }
  90.         cout << j << ":" << endl;
  91.         for (int i = 1; i <= n; ++i)
  92.             cout << F[i][p] << " ";
  93.         cout << endl;
  94.     }
  95.     /*for (int i = 1; i <= n; ++i)
  96.         printf("%d\40", F[i][m % 2]);*/
  97.     printf("\n");
  98.     printf("%d", ans);
  99.     return 0;
  100. }
复制代码
作者: smileandyxu    时间: 2016-4-23 20:02
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <string>
  5. #include <queue>
  6. using namespace std;
  7. struct edge {
  8.     int end;
  9.     int len;
  10. };
  11. struct data {
  12.     string way;
  13.     int len;
  14.     bool operator<(const data &x) const {
  15.         return len > x.len;
  16.     }
  17. };
  18. priority_queue<data> Q;
  19. vector<edge> V[51];
  20. data w;
  21. bool B[51];
  22. int A[51];
  23. int m, n, k, a, b, cnt;
  24. string change(int x)
  25. {
  26.     string s;
  27.     do {
  28.         s += char((x % 10) + '0');
  29.         x /= 10;
  30.     } while (x > 0);
  31.     reverse(s.begin(), s.end());
  32.     return s;
  33. }
  34. void put(int x)
  35. {
  36.     w.way += change(x);
  37.     w.way += '-';
  38. }
  39. void del()
  40. {
  41.     string s = w.way;
  42.     int i = s.size() - 2;
  43.     while (s[i] != '-' && i >= 0);
  44.         --i;
  45.     w.way = s.substr(0, i + 1);
  46. }
  47. void add(int u, int v, int l)
  48. {
  49.     edge tmp;
  50.     tmp.end = v;
  51.     tmp.len = l;
  52.     V[u].push_back(tmp);
  53. }
  54. void dfs(int p)
  55. {
  56.     if (p == b) {
  57.         cout << w.way << endl;
  58.         Q.push(w);
  59.         ++cnt;
  60.     }
  61.     else {
  62.         for (int i = 0; i != V[p].size(); ++i) {
  63.             if (!B[V[p][i].end]) {
  64.                 B[V[p][i].end] = true;
  65.                 put(V[p][i].end);
  66.                 w.len += V[p][i].len;
  67.                 dfs(V[p][i].end);
  68.                 B[V[p][i].end] = false;
  69.                 w.len -= V[p][i].len;
  70.                 del();
  71.             }
  72.         }
  73.     }
  74. }
  75. int main()
  76. {
  77.     cin >> n >> m >> k >> a >> b;
  78.     for (int i = 0, u, v, l; i != m; ++i) {
  79.         cin >> u >> v >> l;
  80.         add(u, v, l);
  81.     }
  82.     put(a);
  83.     B[a] = true;
  84.     dfs(a);
  85.     if (cnt < k)
  86.         cout << "No";
  87.     else {
  88.         for (int i = 1; i <= k - 1; ++i)
  89.             Q.pop();
  90.         cout << Q.top().way;
  91.     }
  92.     return 0;
  93. }
复制代码
作者: smileandyxu    时间: 2016-4-30 20:46
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #define INF 0x7fffffff
  5. using namespace std;
  6. inline int abs(int x)
  7. {
  8.     return (x > 0 ? x : -x);
  9. }
  10. vector<int> V;
  11. bool B[251];
  12. int A[251];
  13. int P[251];
  14. int n, k, a, b, tmp, ans;
  15. void cmn(int i)
  16. {
  17.     if (i == k)
  18.         V.push_back(tmp);
  19.     else {
  20.         for (int j = (i == 0 ? 0 : P[i - 1]); j != n; ++j) {
  21.             if (!B[j]) {
  22.                 B[j] = true;
  23.                 P[i] = j;
  24.                 tmp += A[j];
  25.                 cmn(i + 1);
  26.                 tmp -= A[j];
  27.                 B[j] = false;
  28.             }
  29.         }
  30.     }
  31. }
  32. int main()
  33. {
  34.     cin >> n >> k >> a >> b;
  35.     for (int i = 0; i != n; ++i)
  36.         cin >> A[i];
  37.     cmn(0);
  38.     sort(V.begin(), V.end());
  39.     for (int i = a; i <= b; ++i) {
  40.         vector<int>::iterator iter = lower_bound(V.begin(), V.end(), i);
  41.         tmp = INF;
  42.         if (iter != V.end()) {
  43.             tmp = min(tmp, abs(*iter - i));
  44.         }
  45.         --iter;
  46.         if (iter != V.end()) {
  47.             tmp = min(tmp, abs(*iter - i));
  48.         }
  49.         ans = max(ans, tmp);
  50.     }
  51.     cout << ans;
  52.     return 0;
  53. }
复制代码
作者: smileandyxu    时间: 2016-4-30 21:49
  1. #include <iostream>
  2. #include <string>
  3. #define INF 0x7fffffff
  4. using namespace std;
  5. struct stack {
  6.     char C[500001];
  7.     int top = 0;
  8.     int size() const {
  9.         return top;
  10.     }
  11.     bool empty() const {
  12.         return top == 0;
  13.     }
  14.     void pop() {
  15.         --top;
  16.     }
  17.     void push(char c) {
  18.         C[top] = c;
  19.         ++top;
  20.     }
  21. };
  22. stack S;
  23. string s;
  24. int tot, tmp;
  25. void dfs(int i)
  26. {
  27.     if (i == s.size()) {
  28.         if (S.empty()) {
  29.             ++tot;
  30.             if (tot == 1000000009)
  31.                 tot = 0;
  32.         }
  33.     }
  34.     else if (s[i] == '?') {
  35.         if (!(!S.empty() && s[i - 1] == 'W')) {
  36.             S.push('B');
  37.             ++tmp;
  38.             s[i] = 'B';
  39.             dfs(i + 1);
  40.             s[i] = '?';
  41.             --tmp;
  42.             S.pop();
  43.         }
  44.         if (!S.empty()) {
  45.             S.pop();
  46.             s[i] = 'W';
  47.             dfs(i + 1);
  48.             s[i] = '?';
  49.             S.push('B');
  50.         }
  51.     }
  52.     else {
  53.         if (s[i] == 'B') {
  54.             if ((!S.empty() && s[i - 1] == 'W') || tmp >= s.size() / 2)
  55.                 return;
  56.             S.push('B');
  57.             ++tmp;
  58.             dfs(i + 1);
  59.             S.pop();
  60.             --tmp;
  61.         }
  62.         else {
  63.             if (S.empty())
  64.                 return;
  65.             S.pop();
  66.             dfs(i + 1);
  67.             S.push('B');
  68.         }
  69.     }
  70. }
  71. int main()
  72. {
  73.     cin >> s;
  74.     if (s[0] == 'W')
  75.         cout << 0;
  76.     else {
  77.         S.push('B');
  78.         s[0] = 'B';
  79.         tmp = 1;
  80.         dfs(1);
  81.         cout << tot;
  82.     }
  83.     return 0;
  84. }
复制代码
作者: smileandyxu    时间: 2016-5-3 13:51
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cctype>
  4. #define father(x) (x >> 1)
  5. #define lchild(x) (x << 1)
  6. #define rchild(x) (x << 1 | 1)
  7. #define isleft(x) (x == ((x >> 1) << 1))
  8. #define isright(x) (x == ((x >> 1) << 1) | 1)
  9. #define INF 0x7fffffff
  10. using namespace std;
  11. inline int getint()
  12. {
  13.     char c = getchar();
  14.     while (!isdigit(c))
  15.         c = getchar();
  16.     int x = 0;
  17.     while (isdigit(c)) {
  18.         x = x * 10 + c - '0';
  19.         c = getchar();
  20.     }
  21.     return x;
  22. }
  23. inline int max(int x, int y)
  24. {
  25.     return (x > y ? x : y);
  26. }
  27. int T[4000001]; ///maximum
  28. int A[4000001]; ///add
  29. int L, R;
  30. int m, n;
  31. bool found;
  32. int value(int x)
  33. {
  34.     int a = T[x];
  35.     x = father(x);
  36.     while (x >= 1) {
  37.         a += A[x];
  38.         x = father(x);
  39.     }
  40.     return a;
  41. }
  42. void input()
  43. {
  44.     n = getint();
  45.     m = getint();
  46.     L = 1;
  47.     while (L < n)
  48.         L <<= 1;
  49.     R = L + n - 1;
  50.     found = false;
  51.     for (int i = 0; i != L; ++i)
  52.         T[L + i] = -INF;
  53.     for (int i = 0; i != n; ++i) {
  54.         T[L + i] = getint();
  55.         T[L + i] = -T[L + i];
  56.     }
  57. }
  58. void build()
  59. {
  60.     for (int i = L - 1; i >= 1; --i)
  61.         T[i] = max(T[lchild(i)], T[rchild(i)]);
  62. }
  63. bool add(int left, int right, int d)
  64. {
  65.     int l = left;
  66.     int r = right;
  67.     bool flag = true;
  68.     while (l < r && flag) {
  69.         cout << l << " " << r << " " << value(l) + d << " " << value(r) + d << endl;
  70.         if (isleft(l) && isright(r)) {
  71.             l = father(l);
  72.             r = father(r);
  73.         }
  74.         else {
  75.             if (isright(l)) {
  76.                 if (value(l) + d > 0)
  77.                     flag = false;
  78.                 l = father(l) + 1;
  79.             }
  80.             else {
  81.                 l = father(l);
  82.             }

  84.             if (isleft(r)) {
  85.                 if (value(r) + d > 0)
  86.                     flag = false;
  87.                 r = father(r) - 1;
  88.             }
  89.             else {
  90.                 r = father(r);
  91.             }
  92.         }
  93.     }
  94.     if (l == r && value(l) + d > 0)
  95.         flag = false;
  96.     l = left;
  97.     r = right;

  99.     while (l < r && flag) {
  100.         if (isleft(l) && isright(r)) {
  101.             l = father(l);
  102.             r = father(r);
  103.         }
  104.         else if (isright(l)) {
  105.             A[l] += d;
  106.             l = father(l) + 1;
  107.         }
  108.         else if (isleft(r)) {
  109.             A[r] += d;
  110.             r = father(r) - 1;
  111.         }
  112.     }
  113.     if (l == r)
  114.         A[l] += d;
  115.     return flag;
  116. }
  117. int main()
  118. {
  119.     input();
  120.     build();
  121.     for (int i = 0, d, s, t; i != m; ++i) {
  122.         d = getint();
  123.         s = getint();
  124.         t = getint();
  125.         if (!found) {
  126.             if (!add(L + s - 1, L + t - 1, d)) {
  127.                 if (!found)
  128.                     printf("-1\n");
  129.                 found = true;
  130.                 printf("%d\n", i + 1);
  131.             }
  132.         }
  133.     }
  134.     if (!found)
  135.         printf("0");
  136.     return 0;
  137. }
复制代码
作者: smileandyxu    时间: 2016-5-3 15:54
  1. #include <iostream>
  2. #include <string>
  3. using namespace std;
  4. struct num {
  5.     int A[200] = {0};
  6.     int LEN = 200;
  7.     num operator+(num y)
  8.     {
  9.         int x = 0;
  10.         for (int i = 0; i != LEN; ++i) {
  11.             A[i] += y.A[i];
  12.             A[i] += x;
  13.             x = A[i] / 10;
  14.             A[i] %= 10;
  15.         }
  16.         return *this;
  17.     }
  18.     num operator*(int y)
  19.     {
  20.         int x = 0;
  21.         for (int i = 0; i != LEN; ++i) {
  22.             A[i] *= y;
  23.             A[i] += x;
  24.             x = A[i] / 10;
  25.             A[i] %= 10;
  26.         }
  27.         return *this;
  28.     }
  29.     void operator=(int y)
  30.     {
  31.         for (int i = 0; i != LEN && y > 0; ++i) {
  32.             A[i] = y % 10;
  33.             y /= 10;
  34.         }
  35.     }
  36.     void operator=(num y)
  37.     {
  38.         for (int i = 0; i != LEN; ++i)
  39.             A[i] = y.A[i];
  40.     }
  41. };
  42. num max(num x, num y)
  43. {
  44.     int flag = 0;
  45.     for (int i = x.LEN - 1; i >= 0 && flag == 0; --i) {
  46.         if (x.A[i] > y.A[i])
  47.             flag = 1;
  48.         else
  49.             flag = -1;
  50.     }
  51.     return (flag == 1 ? x : y);
  52. }
  53. void input(num &x)
  54. {
  55.     string tmp;
  56.     cin >> tmp;
  57.     for (int i = 0; i != tmp.size(); ++i)
  58.         x.A[i] = tmp[tmp.size() - i - 1] - '0';
  59. }
  60. void output(num x)
  61. {
  62.     int i = x.LEN - 1;
  63.     while (i > 0 && x.A[i] == 0)
  64.         --i;
  65.     while (i >= 0) {
  66.         cout << x.A[i];
  67.         --i;
  68.     }
  69. }
  70. num F[101][101];
  71. num A[101];
  72. num ans;
  73. int m, n;
  74. int main()
  75. {
  76.     cin >> n >> m;
  77.     for (int i = 1; i <= n; ++i) {
  78.         for (int j = 1; j <= m; ++j)
  79.             input(A[j]);
  80.         for (int j = 1; j <= m; ++j)
  81.             for (int k = 1; k <= m; ++k)
  82.                 F[j][k] = 0;
  83.         for (int l = 1; l <= m; ++l) {
  84.             for (int j = 1; j + l - 1 <= m; ++j) {
  85.                 F[j][j + l - 1] = max(F[j][j + l - 2] * 2 + A[j + l - 1], F[j + 1][j + l - 1] * 2 + A[j]);
  86.             }
  87.         }
  88.         ans = ans + F[1][m];
  89.     }
  90.     output(ans * 2);
  91.     return 0;
  92. }
复制代码
作者: smileandyxu    时间: 2016-5-10 20:16
  1. #include <iostream>
  2. #include <stack>
  3. #define father(x) (x >> 1)
  4. #define lchild(x) (x << 1)
  5. #define rchild(x) ((x << 1) | 1)
  6. #define isleft(x) (x == (x >> 1) << 1)
  7. #define isright(x) (x == ((x >> 1) << 1) | 1)
  8. using namespace std;
  9. int T[800001];
  10. int A[800001];
  11. int L, R;
  12. int n, q;
  13. int value(int x)
  14. {
  15.     int v = 0;
  16.     while (x >= 1) {
  17.         v += A[x];
  18.         x = father(x);
  19.     }
  20.     return v;
  21. }
  22. int query(int l, int r)
  23. {
  24.     int v = 0;
  25.     while (l <= r) {
  26.         if (isleft(l) && isright(r)) {
  27.             l = father(l);
  28.             r = father(r);
  29.         }
  30.         else {
  31.             if (isright(l)) {
  32.                 v += value(l) + T[l];
  33.                 l = father(l) + 1;
  34.             }
  35.             else
  36.                 l = father(l);
  37.             if (isleft(r)) {
  38.                 v += value(r) + T[r];
  39.                 r = father(r) - 1;
  40.             }
  41.             else
  42.                 r = father(r);
  43.         }
  44.     }
  45. }
  46. void update(int x)
  47. {
  48.     do {
  49.         x = father(x);
  50.         T[x] = T[lchild(x)] + T[rchild(x)];
  51.     } while (x >= 1);
  52. }
  53. void maintain(int x)
  54. {
  55.     stack<int> S;
  56.     while (x > 1) {
  57.         S.push(isright(x));
  58.         x = father(x);
  59.     }
  60.     while (!S.empty()) {
  61.         A[lchild(x)] += A[x];
  62.         A[rchild(x)] += A[x];
  63.         A[x] = 0;
  64.         x = lchild(x) | (S.top());
  65.         S.pop();
  66.     }
  67. }
  68. void add(int l, int r, int x)
  69. {
  70.     l = L + l - 1;
  71.     r = L + r - 1;
  72.     while (l <= r) {
  73.         if (isleft(l) && isright(r)) {
  74.             l = father(l);
  75.             r = father(r);
  76.         }
  77.         else {
  78.             if (isright(l)) {
  79.                 A[l] += x;
  80.                 maintain(l);
  81.                 l = father(l) + 1;
  82.             }
  83.             else
  84.                 l = father(l);
  85.             if (isleft(r)) {
  86.                 A[r] += x;
  87.                 maintain(r);
  88.                 r = father(r) - 1;
  89.             }
  90.             else
  91.                 r = father(r);
  92.         }
  93.     }
  94. }
  95. int main()
  96. {
  97.     cin >> n;
  98.     L = 1;
  99.     while (L < n)
  100.         L <<= 1;
  101.     R = L * 2 - 1;
  102.     for (int i = 0; i != n; ++i) {
  103.         cin >> T[L + i];
  104.         update(L + i);
  105.     }
  106.     for (int i = 0, p, a, b, x; i != q; ++i) {
  107.         cin >> p >> a >> b;
  108.         if (p == 1) {
  109.             cin >> x;
  110.             add(a, b, x);
  111.         }
  112.         if (p == 2) {
  113.             cout << query(a, b) << endl;
  114.         }
  115.     }
  116.     return 0;
  117. }
复制代码
作者: smileandyxu    时间: 2016-5-15 16:48
  1. #include <iostream>
  2. #include <stack>
  3. #define father(x) (x >> 1)
  4. #define lchild(x) (x << 1)
  5. #define rchild(x) ((x << 1) | 1)
  6. #define isleft(x) (x == ((x >> 1) << 1))
  7. #define isright(x) (x == (((x >> 1) << 1) | 1))
  8. using namespace std;
  9. int T[800001];
  10. int A[800001];
  11. int L, R;
  12. int n, q;
  13. int height(int x)
  14. {
  15.     int len = 0;
  16.     while (x >= 1) {
  17.         x = father(x);
  18.         ++len;
  19.     }
  20.     return len - 1;
  21. }
  22. int width(int x)
  23. {
  24.     int len = 1;
  25.     while (height(L) > height(x)) {
  26.         len <<= 1;
  27.         x = lchild(x);
  28.     }
  29.     return len;
  30. }
  31. void update(int x)
  32. {
  33.     do {
  34.         x = father(x);
  35.         T[x] = T[lchild(x)] + T[rchild(x)];
  36.     } while (x >= 1);
  37. }
  38. void maintain(int x)
  39. {
  40.     stack<int> S;
  41.     while (x > 1) {
  42.         S.push(isright(x));
  43.         x = father(x);
  44.     }
  45.     while (!S.empty()) {
  46.         A[lchild(x)] += A[x];
  47.         A[rchild(x)] += A[x];
  48.         T[lchild(x)] += A[x] * width(lchild(x));
  49.         T[rchild(x)] += A[x] * width(rchild(x));
  50.         A[x] = 0;
  51.         x = lchild(x) | (S.top());
  52.         S.pop();
  53.     }
  54. }
  55. void add(int l, int r, int x)
  56. {
  57.     l = L + l - 1;
  58.     r = L + r - 1;
  59.     while (l <= r) {
  60.         if (isleft(l) && isright(r)) {
  61.             l = father(l);
  62.             r = father(r);
  63.         }
  64.         else {
  65.             if (isright(l)) {
  66.                 A[l] += x;
  67.                 T[l] += x * width(l);
  68.                 update(l);
  69.                 l = father(l) + 1;
  70.             }
  71.             else
  72.                 l = father(l);
  73.             if (isleft(r)) {
  74.                 A[r] += x;
  75.                 T[r] += x * width(r);
  76.                 for (int j = 1; j <= R; ++j)
  77.                 update(r);
  78.                 r = father(r) - 1;
  79.             }
  80.             else
  81.                 r = father(r);
  82.         }
  83.     }
  84. }
  85. int query(int l, int r)
  86. {
  87.     l = L + l - 1;
  88.     r = L + r - 1;
  89.     int v = 0;
  90.     while (l <= r) {
  91.         if (isleft(l) && isright(r)) {
  92.             l = father(l);
  93.             r = father(r);
  94.         }
  95.         else {
  96.             if (isright(l)) {
  97.                 maintain(l);
  98.                 v += T[l];
  99.                 l = father(l) + 1;
  100.             }
  101.             else
  102.                 l = father(l);
  103.             if (isleft(r)) {
  104.                 maintain(r);
  105.                 v += T[r];
  106.                 r = father(r) - 1;
  107.             }
  108.             else
  109.                 r = father(r);
  110.         }
  111.     }
  112. }
  113. int main()
  114. {
  115.     cin >> n;
  116.     L = 1;
  117.     while (L < n)
  118.         L <<= 1;
  119.     R = L * 2 - 1;
  120.     for (int i = 0; i != n; ++i) {
  121.         cin >> T[L + i];
  122.         update(L + i);
  123.     }
  124.     cin >> q;
  125.     for (int i = 0, p, a, b, x; i != q; ++i) {
  126.         cin >> p >> a >> b;
  127.         if (p == 1) {
  128.             cin >> x;
  129.             add(a, b, x);
  130.         }
  131.         if (p == 2) {
  132.             cout << query(a, b) << endl;
  133.         }
  134.     }
  135.     return 0;
  136. }
复制代码
作者: smileandyxu    时间: 2016-5-16 13:54
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cctype>
  4. #include <stack>
  5. #define father(x) (x >> 1)
  6. #define lchild(x) (x << 1)
  7. #define rchild(x) ((x << 1) | 1)
  8. #define isleft(x) (x == ((x >> 1) << 1))
  9. #define isright(x) (x == (((x >> 1) << 1) | 1))
  10. using namespace std;
  11. inline int getint()
  12. {
  13.     char c = getchar();
  14.     while (!isdigit(c))
  15.         c = getchar();
  16.     int x = 0;
  17.     while (isdigit(c)) {
  18.         x = x * 10 + c - '0';
  19.         c = getchar();
  20.     }
  21.     return x;
  22. }
  23. inline void putint(int x)
  24. {
  25.     int tmp[20];
  26.     int i = 0;
  27.     do {
  28.         tmp[i] = x % 10;
  29.         x /= 10;
  30.         ++i;
  31.     } while (x > 0);
  32.     --i;
  33.     while (i >= 0) {
  34.         putchar(tmp[i] + '0');
  35.         --i;
  36.     }
  37.     putchar('\n');
  38. }
  39. int T[800001];
  40. int A[800001];
  41. int L, R;
  42. int n, q;
  43. int height(int x)
  44. {
  45.     int len = 0;
  46.     while (x >= 1) {
  47.         x = father(x);
  48.         ++len;
  49.     }
  50.     return len - 1;
  51. }
  52. int width(int x)
  53. {
  54.     int len = 1;
  55.     while (height(L) > height(x)) {
  56.         len <<= 1;
  57.         x = lchild(x);
  58.     }
  59.     return len;
  60. }
  61. void update(int x)
  62. {
  63.     do {
  64.         x = father(x);
  65.         T[x] = T[lchild(x)] + T[rchild(x)];
  66.     } while (x > 1);
  67. }
  68. void maintain(int x)
  69. {
  70.     stack<bool> S;
  71.     while (x > 1) {
  72.         S.push(isright(x));
  73.         x = father(x);
  74.     }
  75.     while (!S.empty()) {
  76.         A[lchild(x)] += A[x];
  77.         A[rchild(x)] += A[x];
  78.         T[lchild(x)] += A[x] * width(lchild(x));
  79.         T[rchild(x)] += A[x] * width(rchild(x));
  80.         A[x] = 0;
  81.         x = lchild(x) + int(S.top());
  82.         S.pop();
  83.     }
  84. }
  85. void add(int l, int r, int x)
  86. {
  87.     l = L + l - 1;
  88.     r = L + r - 1;
  89.     while (l <= r) {
  90.         if (isleft(l) && isright(r)) {
  91.             l = father(l);
  92.             r = father(r);
  93.         }
  94.         else {
  95.             if (isright(l)) {
  96.                 A[l] += x;
  97.                 T[l] += x * width(l);
  98.                 update(l);
  99.                 l = father(l + 1);
  100.             }
  101.             else
  102.                 l = father(l);
  103.             if (isleft(r)) {
  104.                 A[r] += x;
  105.                 T[r] += x * width(r);
  106.                 update(r);
  107.                 r = father(r - 1);
  108.             }
  109.             else
  110.                 r = father(r);
  111.         }
  112.     }
  113. }
  114. int query(int l, int r)
  115. {
  116.     l = L + l - 1;
  117.     r = L + r - 1;
  118.     int v = 0;
  119.     while (l <= r) {
  120.         if (isleft(l) && isright(r)) {
  121.             l = father(l);
  122.             r = father(r);
  123.         }
  124.         else {
  125.             if (isright(l)) {
  126.                 maintain(l);
  127.                 v += T[l];
  128.                 l = father(l + 1);
  129.             }
  130.             else
  131.                 l = father(l);
  132.             if (isleft(r)) {
  133.                 maintain(r);
  134.                 v += T[r];
  135.                 r = father(r - 1);
  136.             }
  137.             else
  138.                 r = father(r);
  139.         }
  140.     }
  141.     return v;
  142. }
  143. int main()
  144. {
  145.     n = getint();
  146.     L = 1;
  147.     while (L < n)
  148.         L <<= 1;
  149.     R = L * 2 - 1;
  150.     for (int i = 0; i != n; ++i) {
  151.         T[L + i] = getint();
  152.         update(L + i);
  153.     }
  154.     q = getint();
  155.     for (int i = 0, p, a, b, x; i != q; ++i) {
  156.         p = getint();
  157.         a = getint();
  158.         b = getint();
  159.         if (p == 1) {
  160.             x = getint();
  161.             if (a != b)
  162.                 add(a, b, x);
  163.             else {
  164.                 T[L + a - 1] += x;
  165.                 update(L + a - 1);
  166.             }
  167.         }
  168.         if (p == 2) {
  169.             putint(query(a, b));
  170.         }
  171.     }
  172.     return 0;
  173. }
  174. /*
  175. 12
  176. 9 899 6 5 7 2 4 4 3 59 78 116
  177. 6
  178. 1 1 9 11
  179. 2 6 9
  180. 1 7 7 4
  181. 1 5 8 10
  182. 2 5 7
  183. 2 1 12
  184. */
  185. /*
  186. 12
  187. 9 899 6 5 7 2 4 4 3 59 78 116
  188. 5
  189. 1 1 9 11
  190. 2 6 9
  191. 1 5 8 10
  192. 2 5 7
  193. 2 1 12
  194. */
复制代码
作者: smileandyxu    时间: 2016-5-17 13:52
  1. #include <iostream>
  2. using namespace std;
  3. struct node {
  4.     node* ch[2];
  5.     double v;
  6.     int s;
  7.     node(int val): v(val), s(1) { }
  8.     int cmp(double x) const
  9.     {
  10.         if (x == v)
  11.             return -1;
  12.         return x < v ? 0 : 1;
  13.     }
  14. };
  15. const node* null;
  16. void rotate(node* &o, int d)
  17. {
  18.     node* k = o->ch[d ^ 1];
  19.     o->ch[d ^ 1] = k->ch[d];
  20.     k->ch[d] = o;
  21.     k->s = o->s;
  22.     o->s = o->ch[0]->s + o->ch[1]->s;
  23.     o = k;
  24. }
  25. void
  26. int main()
  27. {

  29.     return 0;
  30. }
复制代码
作者: smileandyxu    时间: 2016-5-17 16:04
  1. #include <iostream>
  2. using namespace std;
  3. struct node {
  4.     node* ch[2];
  5.     int v;
  6.     int s;
  7.     int cmp(int x) const
  8.     {
  9.         if (x == v)
  10.             return -1;
  11.         return x < v ? 0 : 1;
  12.     }
  13. };
  14. node* null = new node();
  15. node* newnode(int x)
  16. {
  17.     node* tmp = new node();
  18.     tmp->ch[0] = null;
  19.     tmp->ch[1] = null;
  20.     tmp->v = x;
  21.     tmp->s = 1;
  22.     return tmp;
  23. }
  24. int rank(node* o, int x)
  25. {
  26.     if (o == null)
  27.         return -1;
  28.     if (o->cmp(x) == -1)
  29.         return 1;
  30.     else if (o->cmp(x) == 0)
  31.         return rank(o->ch[0], x);
  32.     else
  33.         return o->ch[0]->s + rank(o->ch[1], x);
  34. }
  35. node* find_kth(node* o, int k)
  36. {
  37.     if (k == 1) {
  38.         while (o->ch[0] != null)
  39.             o = o->ch[0];
  40.         return o;
  41.     }
  42.     else {
  43.         if (o->ch[0]->s >= k)
  44.             return find_kth(o->ch[0], k);
  45.         else
  46.             return find_kth(o->ch[1], k - o->ch[0]->s);
  47.     }
  48. }
  49. node* precursor(node* o, int x)
  50. {
  51.     return find_kth(o, rank(o, x) - 1);
  52. }
  53. node* successor(node* o, int x)
  54. {

  56.     return find_kth(o, rank(o, x) + 1);
  57. }
  58. void rotate(node* &o, int d)
  59. {
  60.     node* k = o->ch[d ^ 1];
  61.     o->ch[d ^ 1] = k->ch[d];
  62.     k->ch[d] = o;
  63.     k->s = o->s;
  64.     o->s = o->ch[0]->s + o->ch[1]->s;
  65.     o = k;
  66. }
  67. void maintain(node* o, bool d)
  68. {
  69.     if (!d) {
  70.         if (o->ch[0]->ch[0]->s > o->ch[1]->s)
  71.             rotate(o, 1);
  72.         else if (o->ch[0]->ch[1]->s > o->ch[1]->s) {
  73.             rotate(o->ch[0], 0);
  74.             rotate(o, 1);
  75.         }
  76.         else
  77.             return;
  78.     }
  79.     else {
  80.         if (o->ch[1]->ch[1]->s > o->ch[0]->s)
  81.             rotate(o, 0);
  82.         else if (o->ch[1]->ch[0]->s > o->ch[0]->s) {
  83.             rotate(o->ch[1], 1);
  84.             rotate(o, 0);
  85.         }
  86.         else
  87.             return;
  88.     }
  89.     cout << "#";
  90.     maintain(o->ch[0], false);
  91.     maintain(o->ch[1], true);
  92.     maintain(o, false);
  93.     maintain(o, true);
  94. }
  95. void insert(node* &o, int x)
  96. {
  97.     if (o == null)
  98.         o = newnode(x);
  99.     else {
  100.         if (o->cmp(x) == 0)
  101.             insert(o->ch[0], x);
  102.         else
  103.             insert(o->ch[1], x);
  104.         ++o->s;
  105.         maintain(o, false);
  106.         maintain(o, true);
  107.     }
  108. }
  109. void erase(node* &o, int x)
  110. {
  111.     if (o->cmp(x) == -1) {
  112.         if (o->ch[0] == null && o->ch[1] == null)
  113.             o = null;
  114.         else if (o->ch[0] == null)
  115.             o = o->ch[1];
  116.         else if (o->ch[1] == null)
  117.             o = o->ch[0];
  118.         else {
  119.             node* tmp = find_kth(o->ch[1], 1);
  120.             o->v = tmp->v;
  121.             erase(o->ch[1], tmp->v);
  122.             --o->s;
  123.         }
  124.     }
  125.     else {
  126.         if (o->cmp(x) == 0)
  127.             erase(o->ch[0], x);
  128.         else {
  129.             erase(o->ch[1], x);
  130.         }
  131.         --o->s;
  132.     }
  133. }
  134. node* T = null;
  135. int n;
  136. int main()
  137. {
  138.     cin >> n;
  139.     null->ch[0] = null;
  140.     null->ch[1] = null;
  141.     for (int i = 0, p; i != n; ++i) {
  142.         int x;
  143.         cin >> p >> x;
  144.         if (p == 1)
  145.             insert(T, x);
  146.         if (p == 2)
  147.             erase(T, x);
  148.         if (p == 3)
  149.             cout << rank(T, x) << endl;
  150.         if (p == 4)
  151.             cout << find_kth(T, x)->v << endl;
  152.         if (p == 5)
  153.             cout << precursor(T, x)->v << endl;
  154.         if (p == 6)
  155.             cout << successor(T, x)->v << endl;
  156.     }
  157.     return 0;
  158. }
复制代码
作者: smileandyxu    时间: 2016-5-18 13:53
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <set>
  4. using namespace std;
  5. set<int> G[501][501];
  6. int F[501][501];
  7. int B[501];
  8. int C[501];
  9. int W[501];
  10. int P[501];
  11. int L[501];
  12. int n;
  13. void mysearch(int i, int p)
  14. {
  15.     if (F[i][p] != 0 || i == 0)
  16.         return;
  17.     else if (W[i] > p) {
  18.         mysearch(B[i], p);
  19.         F[i][p] = F[B[i]][p];
  20.         G[i][p] = G[B[i]][p];
  21.     }
  22.     else if (W[i] == p) {
  23.         F[i][p] = L[i];
  24.         G[i][p].insert(i);
  25.     }
  26.     else {
  27.         mysearch(B[i], p);
  28.         mysearch(B[i], p - W[i]);
  29.         mysearch(C[i], p - W[i]);
  30.         F[i][p] = F[B[i]][p];
  31.         G[i][p] = G[B[i]][p];
  32.         for (int k = 0; k <= p - W[i]; ++k) {
  33.             if (k <= P[i] && p - W[i] - k <= P[i] && p - W[i] - k >= 0) {
  34.                 mysearch(B[i], k);
  35.                 mysearch(C[i], p - W[i] - k);
  36.                 if (F[B[i]][k] + F[C[i]][p - W[i] - k] > F[i][p]) {
  37.                     F[i][p] = F[B[i]][k] + F[C[i]][p - W[i] - k];
  38.                     for (set<int>::iterator iter = G[B[i]][k].begin(); iter != G[B[i]][k].end(); ++iter)
  39.                         G[i][p].insert(*iter);
  40.                     for (set<int>::iterator iter = G[C[i]][p - W[i] - k].begin(); iter != G[C[i]][p - W[i] - k].end(); ++iter)
  41.                         G[i][p].insert(*iter);
  42.                 }
  43.             }
  44.         }
  45.     }
  46. }
  47. int main()
  48. {
  49.     cin >> n;
  50.     for (int i = 1, t; i <= n; ++i) {
  51.         cin >> t >> W[i] >> P[i] >> L[i];
  52.         int k = C[t];
  53.         C[t] = i;
  54.         B[i] = k;
  55.     }
  56.     for (int i = W[1]; i <= P[1] + W[1]; ++i)
  57.         mysearch(1, P[1] + W[1]);
  58.     cout << F[1][P[1] + W[1]];
  59.     cout << endl;
  60.     for (set<int>::iterator iter = G[1][P[1] + W[1]].begin(); iter != G[1][P[1] + W[1]].end(); ++iter)
  61.         cout << *iter << " ";
  62.     return 0;
  63. }
复制代码
作者: smileandyxu    时间: 2016-5-31 13:50
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #define esp 1e-7
  5. using namespace std;
  6. struct edge {
  7.     int beg;
  8.     int end;
  9.     int len;
  10.     int vel;
  11. };
  12. vector<edge> V;
  13. double D[201][501];
  14. int P[201];
  15. int m, n, d;
  16. void add(int a, int b, int v, int l)
  17. {
  18.     edge tmp;
  19.     tmp.beg = a;
  20.     tmp.end = b;
  21.     tmp.vel = v;
  22.     tmp.len = l;
  23.     V.push_back(tmp);
  24. }
  25. void spfa()
  26. {
  27.    
  28. }
  29. int main()
  30. {
  31.     cin >> n >> m >> d;
  32.     for (int i = 0, a, b, v, l; i != n; ++i) {
  33.         cin >> a >> b >> v >> l;
  34.         add(a, b, v, l);
  35.     }
  36.     spfa();
  37.    
  38.     return 0;
  39. }
复制代码
作者: smileandyxu    时间: 2016-5-31 15:47
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #define INF 0x3fffffff
  5. #define eps 1e-8
  6. using namespace std;
  7. struct edge {
  8.     int end;
  9.     int len;
  10.     int vel;
  11. };
  12. vector<edge> V[201];
  13. double D[201][501];
  14. int F[201][501];
  15. int G[201][501];
  16. int m, n, d;
  17. void add(int a, int b, int v, int l)
  18. {
  19.     edge tmp;
  20.     tmp.end = b;
  21.     tmp.vel = v;
  22.     tmp.len = l;
  23.     V[a].push_back(tmp);
  24. }
  25. void spfa()
  26. {
  27.     queue<int> Q;
  28.     queue<int> P;
  29.     bool B[201][501];
  30.     Q.push(0);
  31.     P.push(70);
  32.     B[0][70] = true;
  33.     D[0][70] = 0;
  34.     while (!Q.empty()) {
  35.         int k = Q.front();
  36.         int t = P.front();
  37.         B[k][t] = false;
  38.         Q.pop();
  39.         P.pop();
  40.         for (int i = 0; i != V[k].size(); ++i) {
  41.             if (V[k][i].vel == 0) {
  42.                 if (D[V[k][i].end][t] - D[k][t] + double(V[k][i].len) / double(t) > eps) {
  43.                     D[V[k][i].end][t] = D[k][t] + double(V[k][i].len) / double(t);
  44.                     F[V[k][i].end][t] = k;
  45.                     G[V[k][i].end][t] = t;
  46.                     cout << "change: " << V[k][i].end << "#" << t << " ====> " << k << "#" << t << endl;
  47.                     if (!B[V[k][i].end][t]) {
  48.                         Q.push(V[k][i].end);
  49.                         P.push(t);
  50.                         B[V[k][i].end][t] = true;
  51.                     }
  52.                 }
  53.             }
  54.             else {
  55.                 if (D[V[k][i].end][V[k][i].vel] - D[k][t] + double(V[k][i].len) / double(V[k][i].vel) > eps) {
  56.                     D[V[k][i].end][V[k][i].vel] = D[k][t] + double(V[k][i].len) / double(V[k][i].vel);
  57.                     F[V[k][i].end][V[k][i].vel] = k;
  58.                     G[V[k][i].end][V[k][i].vel] = t;
  59.                     cout << "change: " << V[k][i].end << "#" << V[k][i].vel << " ====> " << k << "#" << t << endl;
  60.                     if (!B[V[k][i].end][V[k][i].vel]) {
  61.                         Q.push(V[k][i].end);
  62.                         P.push(V[k][i].vel);
  63.                         B[V[k][i].end][V[k][i].vel] = true;
  64.                     }
  65.                 }
  66.             }
  67.         }
  68.     }
  69. }
  70. int cnt;
  71. void output(int x, int y)
  72. {
  73.     if (cnt <= 30)
  74.     cout << x << "#" << y << endl;
  75.     ++cnt;
  76.     if (F[x][y] != x && x != 0)
  77.         output(F[x][y], G[x][y]);
  78.     cout << x << " ";
  79. }
  80. int main()
  81. {
  82.     cin >> n >> m >> d;
  83.     for (int i = 0, a, b, v, l; i != m; ++i) {
  84.         cin >> a >> b >> v >> l;
  85.         add(a, b, v, l);
  86.     }
  87.     for (int i = 0; i != n; ++i) {
  88.         for (int j = 0; j <= 500; ++j) {
  89.             D[i][j] = INF;
  90.             F[i][j] = i;
  91.         }
  92.     }
  93.     spfa();
  94.     double tmp = INF;
  95.     int k = 0;
  96.     for (int i = 0; i <= 500; ++i) {
  97.         if (tmp - D[d][i] > eps) {
  98.             tmp = D[d][i];
  99.             k = i;
  100.         }
  101.     }
  102.     cout << "==================================" << endl;
  103.     output(d, k);
  104.     return 0;
  105. }
复制代码
作者: smileandyxu    时间: 2016-5-31 15:54
  1. #include <iostream>
  2. #include <set>
  3. #define INF 0x6fffffff
  4. using namespace std;
  5. set<int> S;
  6. int n, ans;
  7. int main()
  8. {
  9.     cin >> n;
  10.     cin >> ans;
  11.     S.insert(ans);
  12.     for (int i = 0, x; i != n - 1; ++i) {
  13.         cin >> x;
  14.         set<int>::iterator iter = S.find(x);
  15.         int minx = INF;
  16.         ++iter;
  17.         if (iter != S.end())
  18.             minx = min(minx, *iter - x);

  20.     }
  21.     return 0;
  22. }
复制代码
作者: smileandyxu    时间: 2016-6-14 15:54
  1. #include <iostream>
  2. #define father(x) (x >> 1)
  3. #define lchild(x) (x << 1)
  4. #define rchild(x) (x << 1 | 1)
  5. using namespace std;
  6. struct node {
  7.     int sum;
  8.     int add;
  9.     int left;
  10.     int right;
  11. };
  12. node T[800001];
  13. int L, R;
  14. int n, m;
  15. void update(int i)
  16. {
  17.     while (i > 0) {
  18.         T[i].sum = T[lchild(i)].sum + T[rchild(i)].sum;
  19.         i = father(i);
  20.     }
  21. }
  22. void build(int i, int l, int r)
  23. {
  24.     T[i].left = l;
  25.     T[i].right = r;
  26.     if (l != r) {
  27.         int d = (l + r) >> 1;
  28.         build(lchild(i), l, d);
  29.         build(rchild(i), d + 1, r);
  30.         T[i].sum = T[lchild(i)].sum + T[rchild(i)].sum;
  31.     }
  32. }
  33. int add(int i, int l, int r, int x)
  34. {
  35.     if (l == T[i].left && r == T[i].right) {
  36.         T[i].sum += x * (r - l + 1);
  37.         T[i].add += x;
  38.         return x * (r - l + 1);
  39.     }
  40.     else {
  41.         int d = (T[i].left + T[i].right) >> 1;
  42.         int s = 0;
  43.         if (l <= d)
  44.             s += add(lchild(i), l, d, x);
  45.         if (r >= d + 1)
  46.             s += add(rchild(i), d + 1, r, x);
  47.         T[i].sum += s;
  48.         return s;
  49.     }
  50. }
  51. void pushdown(int i)
  52. {
  53.     int len = (T[i].right - T[i].left + 1) >> 1;
  54.     T[lchild(i)].sum += T[i].add * len;
  55.     T[rchild(i)].sum += T[i].add * len;
  56.     T[lchild(i)].add += T[i].add;
  57.     T[rchild(i)].add += T[i].add;
  58.     T[i].add = 0;
  59. }
  60. int query(int i, int l, int r)
  61. {
  62.     if (l == T[i].left && r == T[i].right)
  63.         return T[i].sum;
  64.     else {
  65.         int d = (T[i].left + T[i].right) >> 1;
  66.         T[i].sum = 0;
  67.         pushdown(i);
  68.         if (l <= d)
  69.             T[i].sum += query(lchild(i), l, d);
  70.         if (r >= d + 1)
  71.             T[i].sum += query(rchild(i), d + 1, r);
  72.         return T[i].sum;
  73.     }
  74. }
  75. void print()
  76. {
  77.     cout << " ==> ";
  78.     for (int i = 1; i <= R; ++i)
  79.         cout << T[i].sum << " ";
  80.     cout << endl;
  81. }
  82. int main()
  83. {
  84.     cin >> n;
  85.     L = 1;
  86.     while (L < n)
  87.         L <<= 1;
  88.     R = L * 2 - 1;
  89.     cout << L << endl;
  90.     for (int i = 0; i != n; ++i)
  91.         cin >> T[L + i].sum;
  92.     build(1, 1, L);
  93.     cin >> m;
  94.     for (int i = 0, p, l, r, x; i != m; ++i) {
  95.         cin >> p;
  96.         if (p == 1) {
  97.             cin >> l >> r >> x;
  98.             add(1, l, r, x);
  99.         }
  100.         if (p == 2) {
  101.             cin >> l >> r;
  102.             cout << query(1, l, r) << endl;
  103.         }
  104.         print();
  105.     }
  106.     return 0;
  107. }
  108. /*
  109. 6
  110. 1 1 4 5 2 3
  111. 4
  112. 1 1 3 4
  113. 1 2 4 3
  114. 2 2 3
  115. 2 1 4
  116. */
复制代码
作者: smileandyxu    时间: 2016-6-15 13:46
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <stack>
  4. using namespace std;
  5. int P[200001];
  6. int Q[200001];
  7. int head, tail;
  8. int m, d, t, n;
  9. int main()
  10. {
  11.     cin >> m >> d;
  12.     for (int i = 0; i != m; ++i) {
  13.         char c;
  14.         int x;
  15.         cin >> c >> x;
  16.         if (c == 'A') {
  17.             ++n;
  18.             x = (x + t) % d;
  19.             while (head < tail && Q[tail - 1] <= x)
  20.                 --tail;
  21.             Q[tail] = x;
  22.             P[tail] = tail;
  23.             ++tail;
  24.         }
  25.         if (c == 'Q') {
  26.             int p = lower_bound(P, P + tail, tail - x) - P;
  27.             t = Q[p];
  28.             cout << Q[p] << endl;
  29.         }
  30.     }
  31.     return 0;
  32. }
  33. /*
  34. 8 10000
  35. A 101
  36. A 200
  37. Q 1
  38. Q 2
  39. A 10
  40. Q 1
  41. Q 2
  42. Q 3
  43. */
复制代码
作者: smileandyxu    时间: 2016-6-15 17:08
  1. #include <iostream>
  2. #define INF 0x3fffffff
  3. using namespace std;
  4. inline int abs(int x)
  5. {
  6.     return (x > 0 ? x : -x);
  7. }
  8. struct node {
  9.     node* ch[2];
  10.     int v;
  11.     int s;
  12. };
  13. node* null = new node();
  14. node* newnode(int x)
  15. {
  16.     node* tmp = new node();
  17.     tmp->ch[0] = null;
  18.     tmp->ch[1] = null;
  19.     tmp->v = x;
  20.     tmp->s = 1;
  21.     return tmp;
  22. }
  23. node* prec(node* o, node* p, int v)
  24. {
  25.     if (o == null)
  26.         return p;
  27.     else if (v < o->v)
  28.         return prec(o->ch[0], p, v);
  29.     return prec(o->ch[1], o, v);
  30. }
  31. node* succ(node* o, node* p, int v)
  32. {
  33.     if (o == null)
  34.         return p;
  35.     else if (v > o->v)
  36.         return prec(o->ch[1], p, v);
  37.     return prec(o->ch[0], o, v);
  38. }
  39. void rotate(node* &o, int d)
  40. {
  41.     node* k = o->ch[d ^ 1];
  42.     o->ch[d ^ 1] = k->ch[d];
  43.     k->ch[d] = o;
  44.     k->s = o->s;
  45.     o->s = o->ch[0]->s + o->ch[1]->s + 1;
  46.     o = k;
  47. }
  48. void maintain(node* &o, bool d)
  49. {
  50.     if (!d) {
  51.         if (o->ch[0]->ch[0]->s > o->ch[1]->s)
  52.             rotate(o, 1);
  53.         else if (o->ch[0]->ch[1]->s > o->ch[1]->s) {
  54.             rotate(o->ch[0], 0);
  55.             rotate(o, 1);
  56.         }
  57.         else
  58.             return;
  59.     }
  60.     else {
  61.         if (o->ch[1]->ch[1]->s > o->ch[0]->s)
  62.             rotate(o, 0);
  63.         else if (o->ch[1]->ch[0]->s > o->ch[0]->s) {
  64.             rotate(o->ch[1], 1);
  65.             rotate(o, 0);
  66.         }
  67.         else
  68.             return;
  69.     }
  70.     maintain(o->ch[0], false);
  71.     maintain(o->ch[1], true);
  72.     maintain(o, false);
  73.     maintain(o, true);
  74. }
  75. void insert(node* &o, int v)
  76. {
  77.     if (o == null)
  78.         o = newnode(v);
  79.     else {
  80.         ++o->s;
  81.         insert(o->ch[v >= o->v], v);
  82.         maintain(o, false);
  83.         maintain(o, true);
  84.     }
  85. }
  86. void print(node* o)
  87. {
  88.     if (o != null) {
  89.         print(o->ch[0]);
  90.         cout << o->v << " ";
  91.         print(o->ch[1]);
  92.     }
  93. }
  94. node* T;
  95. int n, ans;
  96. int main()
  97. {
  98.     null->ch[0] = null;
  99.     null->ch[1] = null;
  100.     T = null;
  101.     cin >> n;
  102.     for (int i = 0, x; i != n; ++i) {
  103.         cin >> x;
  104.         node* p = prec(T, null, x);
  105.         node* q = succ(T, null, x);
  106.         int t = ans;
  107.         if (p == null)
  108.             ans += q->v - x;
  109.         else if (q == null)
  110.             ans += x - p->v;
  111.         else
  112.             ans += min(q->v - x, x - p->v);
  113.         cout <<"==>" <<  ans - t << endl;
  114.         insert(T, x);
  115.     }
  116.     cout << ans;
  117.     return 0;
  118. }
复制代码
作者: smileandyxu    时间: 2016-8-19 16:24
  1. #include <iostream>
  2. #include <cstring>
  3. #include <cstdio>
  4. #include <cctype>
  5. #define INF 0x7fffffff
  6. using namespace std;
  7. inline int getint()
  8. {
  9.     char c = getchar();
  10.     while (!isdigit(c))
  11.         c = getchar();
  12.     int x = 0;
  13.     while (isdigit(c)) {
  14.         x = x * 10 + c - '0';
  15.         c = getchar();
  16.     }
  17.     return x;
  18. }
  19. int END[4000001], FLOW[4000001], NEXT[4000001];
  20. int DIS[1000001], GAP[1000001], HEAD[1000001];
  21. int S, T;
  22. int n, m, eid;
  23. void addedge(int u, int v, int w)
  24. {
  25.     END[eid] = v, FLOW[eid] = w, NEXT[eid] = HEAD[u], HEAD[u] = eid++;
  26.     END[eid] = u, FLOW[eid] = 0, NEXT[eid] = HEAD[v], HEAD[v] = eid++;
  27. }
  28. void init()
  29. {
  30.     n = getint();
  31.     m = getint();
  32.     for (int i = 1; i <= m * n; ++i)
  33.         HEAD[i] = -1;
  34.     for (int i = 1; i <= n; ++i) {
  35.         for (int j = 1, w; j <= m - 1; ++j) {
  36.             w = getint();
  37.             addedge((i - 1) * m + j, (i - 1) * m + j + 1, w);
  38.         }
  39.     }
  40.     for (int i = 1; i <= n - 1; ++i) {
  41.         for (int j = 1, w; j <= m; ++j) {
  42.             w = getint();
  43.             addedge((i - 1) * m + j, i * m + j, w);
  44.         }
  45.     }
  46.     for (int i = 1; i <= n - 1; ++i) {
  47.         for (int j = 1, w; j <= m - 1; ++j) {
  48.             w = getint();
  49.             addedge((i - 1) * m + j, i * m + j + 1, w);
  50.         }
  51.     }
  52. }
  53. int augment(int pos, int flow)
  54. {
  55.     if (pos == m * n)
  56.         return flow;
  57.     else {
  58.         int cur, aug;
  59.         cur = 0;
  60.         for (int i = HEAD[pos]; i != -1; i = NEXT[i]) {
  61.             int j = END[i];
  62.             if (FLOW[i] && DIS[pos] == DIS[j] + 1) {
  63.                 aug = augment(j, min(flow - cur, FLOW[i]));
  64.                 FLOW[i] -= aug;
  65.                 FLOW[i ^ 1] += aug;
  66.                 cur += aug;
  67.                 if (cur == flow || DIS[S] >= m * n)
  68.                     return cur;
  69.             }
  70.         }
  71.         if (!cur) {
  72.             if (--GAP[DIS[pos]] == 0) {
  73.                 DIS[S] = m * n;
  74.                 return cur;
  75.             }
  76.             int mindis = m * n;
  77.             for (int i = HEAD[pos]; i != -1; i = NEXT[i])
  78.                 if (FLOW[i])
  79.                     mindis = min(mindis, DIS[END[i]] + 1);
  80.             DIS[pos] = mindis;
  81.             ++GAP[DIS[pos]];
  82.         }
  83.         return cur;
  84.     }
  85. }
  86. int isap()
  87. {
  88.     int max_flow = 0;
  89.     S = 1;
  90.     T = m * n;
  91.     GAP[0] = m * n; //***//
  92.     while (DIS[S] < m * n)
  93.         max_flow += augment(S, INF);
  94.     return max_flow;
  95. }
  96. int main()
  97. {
  98.     init();
  99.     if (m == 1 && n == 1)
  100.         printf("%d", 0);
  101.     else
  102.         printf("%d", isap());
  103.     return 0;
  104. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2