Namomo Summer Camp 23 Day 1(GCPC2021)

Problem B: Brexiting and Brentering

签到

#include<bits/stdc++.h>

using i64 = long long;

using namespace std;

typedef pair<i64, i64> PII;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    string s,ans = "";
    cin >> s;
    int pos = s.size();
    for(int i = s.size() - 1;i >= 0;i --){
        if(s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u'){
            pos = i + 1;
            break;
        }
    }

    cout << s.substr(0,pos) + "ntry" << '\n';

    return 0;
}

Problem C: Card Trading

买的人对于比意愿价格(他心中的最大接受价格)更低的成交价肯定也乐意买,而卖的人同理,对于比意愿出售价(心中最低接受价格)更高的成交价也乐意卖.所以我们将价格排序后,对卖商品的人做一个前缀和,买商品的人做一个后缀和,对于每一个价格,最大成交量就是处于这个价格的买家和卖家的最小意愿数

啊,这题还卡\(double\),一定要开\(longdouble\)

#include<bits/stdc++.h>

using i64 = long long;

using namespace std;

typedef pair<i64, i64> PII;

struct people {
    long double value;
    i64 buy, sale;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n ;
    vector<people> a(n);
    for (int i = 0; i < n; i ++) {
        cin >> a[i].value >> a[i].buy >> a[i].sale;
    }

    sort(a.begin(), a.end(), [](people x, people y) {
        return x.value < y.value;
    });

    vector<i64> s1(n), s2(n);
    s2[n - 1] = a[n - 1].buy;
    s1[0] = a[0].sale;
    for (int i = 1; i < n; i ++)
        s1[i] = s1[i - 1] + a[i].sale;
    for (int i = n - 2; i >= 0; i --)
        s2[i] = s2[i + 1] + a[i].buy;


    long double ans = 0, pos = -1;
    for (int i = 0; i < n; i ++) {
        if (min(s1[i], s2[i]) * a[i].value > ans) {
            ans = min(s1[i], s2[i]) * a[i].value;
            pos = i;
        }
    }

    if (pos == -1) {
        puts("impossible");
    } else
        printf("%.2Lf %.2Lf\n", a[pos].value, ans);

    return 0;
}

Problem A: Amusement Arcade

要使得在\(n\)个位置中选一个位置(标位\(x\))后,其两边位置要刚好隔一个插一个人,且两边最边界不能是空格,其实无非是离\(x\)有\(2,4,8...\),为啥不能是\(6\)呢,因为它是每次取一半的位置,\(6\)取一半中间就会空出两个位置不符合要求,发现这个规律之后其实就是去看去掉\(x\)这个位置后剩余的位置能否凑成一个\(2^i\)或者两个数\(2^i\)和\(2^j\)的和

#include<bits/stdc++.h>

using i64 = long long;

using namespace std;

typedef pair<i64, i64> PII;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    i64 n;
    cin >> n;
    if (n == 1) {
        cout << 1 << '\n';
        return 0;
    }
    for (int i = 1; i < 63; i ++) {
        for (int j = 1; j < 63; j ++) {
            if ((1ll << i) + 1 == n || (1ll << i) + (1ll << j) + 1 == n) {
                cout << (1ll << i) + 1 << '\n';
                return 0;
            }
        }
    }

    cout << "impossible\n";

    return 0;
}

Problem M: Monty’s Hall

感觉自己好没用啊,都说是道小学奥数题(尊嘟假嘟o.O),可惜我是个大学生了

第一次选择的时候,我们开出宝箱的概率为\(\frac{S}{D}\),没开出宝箱的概率为\(\frac{D-S}{D}\),中间排除了\(E\)扇门,假如我们在第二次更换了\(L(0 \leq L \leq min(S,D-S-E))\)扇门,在原来中宝箱的概率上保证不会把宝箱换掉的概率就是只换掉了\(S\)扇门中的\(L\)扇非宝箱门,让宝箱在剩下的\(S-L\)扇门中,即再次中宝箱的概率为\(\frac{S-L}{S}\),而如果第一次没中,我们在第二次中宝箱的概率就是在剩下的\(D-S-E\)扇门中选择的\(L\)扇里含有宝箱,即\(\frac{L}{D-S-E}\),因此两次一共中宝箱的概率为\(\frac{S}{D} \times \frac{S-L}{S} + \frac{D-S}{D} \times \frac{L}{D-S-E}\),通分之后就是\(\frac{SD - S^2 - SE+LE}{D(D-S-E)}\),这里面只有\(L\)是未知的,我们只需要去枚举\(L\)就可以了,不过貌似\(L\)一定是在最大值或最小值处,这里我就懒得证了(orz)

#include<bits/stdc++.h>

using i64 = long long;

using namespace std;

typedef pair<i64, i64> PII;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long double d,s,e,ans = 0;
    cin >> d >> s >> e;

    for(int l = 0 ;l <= min(s,d - s - e);l ++)
        ans = max((s * d - s * s - s * e + l * e )/(d * (d - s - e)),ans);

    cout << ans << '\n';
    return 0;
}

Problem G: Grid Delivery

考虑贪心的做法,第一层先让司机拿完所有的货物,然后向下延伸,后面有货物就继续往后走,如果前面有货物,就再派一辆司机,后面几层同理,二分就是去找上一层小于等于当前货物位置的司机或者当前位置前面的司机

#include<bits/stdc++.h>

using i64 = long long;

using namespace std;

typedef pair<i64, i64> PII;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<string> g(n);
    for (auto &i : g) cin >> i;

    multiset<int> ans;
    ans.insert(-666);//防止越界
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < m; j ++) {
            if (g[i][j] == 'C') {                           
                auto t = prev(ans.upper_bound(j));
                if(*t == -666) ans.insert(j);
                else ans.erase(t), ans.insert(j);
            }
        }
    }

    cout << ans.size() - 1 << '\n';
    return 0;
}

Problem H: Hectic Harbour II

可以把这两个栈想象成一个顶部对接的链表,比如例\(2\)就可以看成是\(2,4,0,1,5,3,6\),第一次把\(1\)拿走,它的左边有\(0\),答案\(+1\),第二拿走\(2\),左右没\(0\),跳过,拿走\(3\),左右无\(0\),跳过,拿走\(4\),右边有\(0\),答案\(+1\),拿走\(5\),左边有\(0\),答案\(+1\),拿走\(6\),左边有\(0\),答案\(+1\),更直观点就是(黑体表示要拿走的数字):\(2,4,0,\textbf{1},5,3,6 \rightarrow \textbf{2},4,0,5,3,6 \rightarrow 4,0,5,\textbf{3},6 \rightarrow \textbf{4},0,5,6 \rightarrow 0,\textbf{5},6 \rightarrow 0,\textbf{6}\)

然后你就会发现,其实这就是从\(0\)向两边求上升序列的长度

#include<bits/stdc++.h>

using i64 = long long;

using namespace std;

typedef pair<i64, i64> PII;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, s1, s2;
    cin >> n >> s1 >> s2;
    vector<int> s(n + 1);
    for (int i = 0; i < s1; i ++)
        cin >> s[i];
    for (int i = n; i >= s1; i --)
        cin >> s[i];

    i64 ans = 0;
    auto t = find(s.begin(), s.end(), 0) - s.begin();
    int ma = 0;
    for (int i = t; i <= n; i ++){
        if (s[i] > ma){
            ans ++;
            ma = s[i];
        }
    }
    ma = 0;
    for (int j = t; j >= 0; j --){
        if (s[j] > ma){
            ans ++;
            ma = s[j];
        }
    }

    cout << ans << '\n';

    return 0;
}