XUPT_ACM2021寒假训练第二周练习记录

柔情只为你懂 2022-10-29 01:46 121阅读 0赞

> 试题链接：[第二周训练题 - Virtual Judge][- Virtual Judge]  
> 这周事情比较多，没有把20道题全部写完，只写了14道题。

### 目录 ###

*   *  B - 补提交卡
     *  C - 热血格斗场
     *  D - 背包包
     *  E - 数列极差
     *  G - 过河
     *  H - 超市
     *  I - 放苹果
     *  J - 滑雪
     *  L - 贫穷的ACM
     *  M - I NEED A OFFER!
     *  N - 今年暑假不AC
     *  O - 拯救X先生
     *  Q - 奇怪的电梯
     *  R - 小火车

## B - 补提交卡 ##

语言：C++

#include <iostream>
    #define MAXSIZE 105
    using namespace std;
    
    int a[MAXSIZE];
    
    int main() { 
        int T;
        cin >> T;
        while (T--) { 
            int N, M;
            cin >> N >> M;
            int ans = N <= M ? 100 : 0;
            for (int i = 0; i < N; i++) { 
                cin >> a[i];
            }
            for (int i = 0; i <= N - M; i++) { 
                int start = i > 0 ? a[i - 1] + 1 : 1;
                int end = i + M < N ? a[i + M] - 1 : 100;
                ans = max(ans, end - start + 1);
            }
            cout << ans << endl;
        }
        return 0;
    }

## C - 热血格斗场 ##

语言：C++

#include <bits/stdc++.h>
    using namespace std;
    
    int main() { 
        map<int, int> m;
        map<int, int>::iterator it;
        m[1000000000] = 1;
        int n;
        cin >> n;
        while (n--) { 
            int id, strength;
            cin >> id >> strength;
            it = m.upper_bound(strength);
            if (it == m.end()) { 
                it--;
                cout << id << " " << it->second << endl;
            } else if (it == m.begin()) { 
                cout << id << " " << it->second << endl;
            } else { 
                int t1 = abs(it->first - strength);
                it--;
                int t2 = abs(it->first-strength);
                if (t2 > t1) { 
                    it++;
                }
                cout << id << " " << it->second << endl;
            }
            m.insert(pair<int, int>(strength, id));
        }
        return 0;
    }

## D - 背包包 ##

语言：C++

#include <iostream>
    #define MAXSIZE 1005
    using namespace std;
    
    int w[MAXSIZE];
    int v[MAXSIZE];
    
    int main() { 
        int T;
        cin >> T;
        while (T--) { 
            int n, V;
            int maxN = 0;
            int maxV = 0;
            int dp[MAXSIZE] = { 0};
            cin >> n >> V;
            for (int i = 1; i <= n; i++) { 
                cin >> w[i];
            }
            for (int i = 1; i <= n; i++) { 
                cin >> v[i];
            }
            dp[v[1]] = w[1];
            for (int i = 2; i <= n; i++) { 
                for (int j = V; j >= v[i]; j--) { 
                    if (j == v[i] || dp[j - v[i]] != 0) { 
                        dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
                    }
                }
            }
            for (int i = V; i > 0; i--) { 
                if (dp[i] > maxN) { 
                    maxN = dp[i];
                    maxV = i;
                }
            }
            cout << maxN << " " << maxV << endl;
        }
        return 0;
    }

## E - 数列极差 ##

语言：C++

#include <iostream>
    #include <algorithm>
    #define MAXSIZE 50005
    using namespace std;
    
    int arr1[MAXSIZE];
    int arr2[MAXSIZE];
    
    bool cmp1(int a, int b);
    bool cmp2(int a, int b);
    int Max(int n);
    int Min(int n);
    
    int main() { 
        int n;
        while (cin >> n && n != 0) { 
            for (int i = 0; i < n; i++) { 
                cin >> arr1[i];
                arr2[i] = arr1[i];
            }
            cout << Max(n) - Min(n) << endl;
        }
        return 0;
    }
    
    bool cmp1(int a, int b) { 
        return a > b;
    }
    
    bool cmp2(int a, int b) { 
        return a < b;
    }
    
    int Max(int n) { 
        while (n > 2) { 
            sort(arr1, arr1 + n, cmp1);
            arr1[n - 2] = arr1[n - 2] * arr1[n - 1] + 1;
            n--;
        }
        return arr1[0] * arr1[1] + 1;
    }
    
    int Min(int n) { 
        while (n > 2) { 
            sort(arr2, arr2 + n, cmp2);
            arr2[n - 2] = arr2[n - 2] * arr2[n - 1] + 1;
            n--;
        }
        return arr2[0] * arr2[1] + 1;
    }

## G - 过河 ##

语言：C++

#include <iostream>
    #include <algorithm>
    #define MAXSIZE 1005
    using namespace std;
    
    int main() { 
        int T;
        cin >> T;
        while (T--) { 
            int n;
            int a[MAXSIZE] = { 0};
            cin >> n;
            for (int i = 1; i <= n; i++) { 
                cin >> a[i];
            }
            sort(a + 1, a + n + 1);
            int ans = 0;
            while (n > 0) { 
                if (n > 3) { 
                    int s1 = 2 * a[1] + a[n - 1] + a[n];
                    int s2 = 2 * a[2] + a[1] + a[n];
                    ans += min(s1, s2);
                    n -= 2;
                } else if (n == 3) { 
                    ans += a[1] + a[2] + a[3];
                    break;
                } else { 
                    ans += a[n];
                    break;
                }
            }
            cout << ans << endl;
        }
        return 0;
    }

## H - 超市 ##

**解法1**  
语言：C++

#include <iostream>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    #define MAXSIZE 10005
    using namespace std;
    
    pair<int, int> goods[MAXSIZE];
    priority_queue<int, vector<int>, greater<int>> q;
    
    int main() { 
        int n;
        while (cin >> n) { 
            int ans = 0;
            memset(goods, 0, sizeof(goods));
            for (int i = 0; i < n; i++) { 
                cin >> goods[i].second >> goods[i].first;
            }
            sort(goods, goods + n);
            for (int i = 0; i < n; i++) { 
                if (goods[i].first > q.size()) { 
                    q.push(goods[i].second);
                } else if (goods[i].first == q.size() && goods[i].second > q.top()) { 
                    q.pop();
                    q.push(goods[i].second);
                }
            }
            while (!q.empty()) { 
                ans += q.top();
                q.pop();
            }
            cout << ans << endl;
        }
        return 0;
    }

**解法2**  
语言：C++

#include <algorithm>
    #include <cstdio>
    using namespace std;
    
    struct data { 
        int p;
        int d;
    } h[10010];
    
    bool cmp(data a, data b);
    
    int main() { 
        int n, p, d;
        while (~scanf("%d", &n)) { 
            for (int i = 1; i <= n; i++) { 
                scanf("%d %d", &h[i].p, &h[i].d);
            }
            sort(h + 1, h + n + 1, cmp);
            int count = 0;
            int c[10010] = { 0};
            for (int i = 1; i <= n; i++) { 
                if (c[h[i].d] == 0) { 
                    c[h[i].d] = 1;
                    count += h[i].p;
                } else { 
                    for (int j = h[i].d - 1; j > 0; j--) { 
                        if (c[j] == 0) { 
                            c[j] = 1;
                            count += h[i].p;
                            break;
                        }
                    }
                }
            }
            printf("%d\n", count);
        }
        return 0;
    }
    
    bool cmp(data a, data b) { 
        return a.p > b.p;
    }

## I - 放苹果 ##

语言：C++

#include <iostream>
    using namespace std;
    
    int fun(int m, int n);
    
    int main() { 
        int t;
        cin >> t;
        while (t--) { 
            int m, n;
            cin >> m >> n;
            cout << fun(m, n) << endl;
        }
        return 0;
    }
    
    int fun(int m, int n) { 
        if (m == 0 || m == 1) { 
            return 1;
        }
        if (n == 0 || n == 1) { 
            return 1;
        }
        if (m >= n) { 
            return fun(m, n - 1) + fun(m - n, n);
        } else { 
            return fun(m, m);
        }
    }

## J - 滑雪 ##

语言：C++

#include <iostream>
    #define MAXSIZE 105
    using namespace std;
    
    int R, C;
    int h[MAXSIZE][MAXSIZE];
    int visited[MAXSIZE][MAXSIZE];
    int di[2][4] = { 
            { 0, 0, -1, 1},
            { -1, 1, 0, 0}
    };
    
    bool check(int i, int j);
    int longestPath(int i, int j);
    
    int main() { 
        int ans = 0;
        cin >> R >> C;
        for (int i = 0; i < R; i++) { 
            for (int j = 0; j < C; j++) { 
                cin >> h[i][j];
            }
        }
        for (int i = 0; i < R; i++) { 
            for (int j = 0; j < C; j++) { 
                longestPath(i, j);
                ans = max(ans, visited[i][j]);
            }
        }
        cout << ans << endl;
        return 0;
    }
    
    bool check(int i, int j) { 
        if (i >= 0 && i < R && j >= 0 && j < C) { 
            return true;
        } else { 
            return false;
        }
    }
    
    int longestPath(int i, int j) { 
        if (visited[i][j] != 0) { 
            return visited[i][j];
        }
        visited[i][j] = 1;
        for (int k = 0; k < 4; k++) { 
            int i_next = di[0][k] + i;
            int j_next = di[1][k] + j;
            if (check(i_next, j_next) && h[i_next][j_next] < h[i][j]) { 
                longestPath(i_next, j_next);
                visited[i][j] = max(visited[i][j], visited[i_next][j_next] + 1);
            }
        }
        return visited[i][j];
    }

## L - 贫穷的ACM ##

语言：C++

#include <iostream>
    #define MAXSIZE 10005
    #define INF 2000000000
    using namespace std;
    
    int main() { 
        int T;
        cin >> T;
        while (T--) { 
            int E, F;
            cin >> E >> F;
            int w = F - E;
            int N;
            cin >> N;
            int P[MAXSIZE], W[MAXSIZE];
            int dp[MAXSIZE];
            for (int i = 0; i < N; i++) { 
                cin >> P[i] >> W[i];
            }
            for (int i = 0; i <= w; i++) { 
                dp[i] = INF;
            }
            dp[0] = 0;
            for (int i = 0; i < N; i++) { 
                for (int j = W[i]; j <= w; j++) { 
                    dp[j] = min(dp[j], dp[j - W[i]] + P[i]);
                }
            }
            if (dp[w] != INF) { 
                cout << "The minimum amount of money in the piggy-bank is " << dp[w] << "." << endl;
            } else { 
                cout << "This is impossible." << endl;
            }
        }
        return 0;
    }

## M - I NEED A OFFER! ##

语言：C++

#include <cstdio>
    #include <iostream>
    #define MAXSIZE 10005
    using namespace std;
    
    int main() { 
        int n, m;
        while (cin >> n >> m) { 
            if (n == 0 && m == 0) { 
                break;
            }
            double a[MAXSIZE];
            double b[MAXSIZE];
            for (int i = 1; i <= m; i++) { 
                cin >> a[i] >> b[i];
            }
            double dp[MAXSIZE];
            for (int i = 0; i <= n; i++) { 
                dp[i] = 1;
            }
            for (int i = 1; i <= m; i++) { 
                for (int j = n; j >= a[i]; j--) { 
                    dp[j] = min(dp[j], dp[j - int(a[i])] * (1 - b[i]));
                }
            }
            printf("%.1lf%%\n", (1 - dp[n]) * 100);
        }
        return 0;
    }

## N - 今年暑假不AC ##

语言：C++

#include <iostream>
    #include <algorithm>
    #define MAXSIZE 105
    using namespace std;
    
    typedef struct { 
        int Ts;
        int Te;
    } Time;
    
    bool cmp(Time a, Time b);
    
    int main() { 
        int n;
        while (cin >> n && n != 0) { 
            Time T[MAXSIZE];
            for (int i = 0; i < n; i++) { 
                cin >> T[i].Ts >> T[i].Te;
            }
            sort(T, T + n, cmp);
            int tmp = T[0].Te;
            int ans = 1;
            for (int i = 1; i < n; i++) { 
                if (tmp <= T[i].Ts) { 
                    ans++;
                    tmp = T[i].Te;
                }
            }
            cout << ans << endl;
        }
        return 0;
    }
    
    bool cmp(Time a, Time b) { 
        return a.Te < b.Te;
    }

## O - 拯救X先生 ##

语言：C++

#include <iostream>
    #include <algorithm>
    #define MAXSIZE 105
    using namespace std;
    
    struct treasure { 
        int p;
        int m;
    } a[MAXSIZE];
    
    bool cmp(treasure x, treasure y);
    
    int main() { 
        int v, n;
        while (cin >> v && v != 0) { 
            cin >> n;
            for (int i = 0; i < n; i++) { 
                cin >> a[i].p >> a[i].m;
            }
            sort(a, a + n, cmp);
            int ans = 0;
            for (int i = 0; i < n; i++) { 
                if (v - a[i].m >= 0) { 
                    ans += a[i].m * a[i].p;
                    v -= a[i].m;
                } else { 
                    ans += a[i].p * v;
                    break;
                }
            }
            cout << ans << endl;
        }
        return 0;
    }
    
    bool cmp(treasure x, treasure y) { 
        return x.p > y.p;
    }

## Q - 奇怪的电梯 ##

语言：C++

#include <iostream>
    #include <queue>
    #define MAXSIZE 205
    using namespace std;
    
    typedef struct { 
        int step;
        int floor;
    } qElem;
    
    int main() { 
        int n;
        while (cin >> n && n != 0) { 
            int A, B;
            int k[MAXSIZE];
            cin >> A >> B;
            for (int i = 1; i <= n; i++) { 
                cin >> k[i];
            }
            queue<qElem> q;
            bool flag[MAXSIZE] = { 0};
            bool tag = false;
            qElem start, end;
            start.step = 0;
            start.floor = A;
            q.push(start);
            while (!q.empty()) { 
                start = q.front();
                q.pop();
                if (start.floor == B) { 
                    cout << start.step << endl;
                    tag = true;
                    break;
                }
                if (start.floor + k[start.floor] <= n && !flag[start.floor + k[start.floor]]) { 
                    end.floor = start.floor + k[start.floor];
                    end.step = start.step + 1;
                    flag[end.floor] = true;
                    q.push(end);
                }
                if (start.floor - k[start.floor] > 0 && !flag[start.floor - k[start.floor]]) { 
                    end.floor = start.floor - k[start.floor];
                    end.step = start.step + 1;
                    flag[end.floor] = true;
                    q.push(end);
                }
            }
            if (!tag) { 
                cout << -1 << endl;
            }
        }
        return 0;
    }

## R - 小火车 ##

语言：C++

#include <iostream>
    #include <string>
    #include <stack>
    using namespace std;
    
    int main() { 
        int n;
        while (cin >> n) { 
            stack<int> st;
            string s1, s2;
            cin >> s1 >> s2;
            string ans;
            int cur = 0;
            bool flag = true;
            for (int i = 0; i < n; i++) { 
                while (st.empty() || st.top() != s2[i]) { 
                    if (cur >= n) { 
                        break;
                    }
                    st.push(s1[cur++]);
                    ans += '1';
                }
                if (st.top() == s2[i]) { 
                    st.pop();
                    ans += '0';
                } else { 
                    flag = false;
                }
            }
            if (flag) { 
                cout << "Yes." << endl;
                for (char an : ans){ 
                    cout << (an == '1' ? "in" : "out") << endl;
                }
            } else { 
                cout << "No." << endl;
            }
            cout << "FINISH" << endl;
        }
        return 0;
    }

[- Virtual Judge]: https://vjudge.net/contest/421093