2015 HSYIT代码暂存楼[0]

smileandyxu

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

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

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

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. {
    
54. 
    
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

#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

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

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

1. #include <iostream>
   
2. using namespace std;
   
3. int A[50];
   
4. int n, tot;
   
5. bool can(int i)
   
6. {
   
7. 
   
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. {
    
24. 
    
25.     cin >> n;
    
26.     dfs(1);
    
27.     tot *= 2;
    
28.     cout << tot;
    
29.     return 0;
    
30. }
    

复制代码

smileandyxu

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

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.         }
    
88. 
    
89. 
    
90. 
    
91. 
    
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. }
     

复制代码