2015 HSYIT代码暂存楼[0]

smileandyxu

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] << " ";
    
31. 
    
32.     return 0;
    
33. }

复制代码

hr567

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

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

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

#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

#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

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

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

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();
    
72. 
    
73.     return 0;
    
74. }
    

复制代码

smileandyxu

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

复制代码