23 暑假友谊赛 No.4(UKIEPC 2017)

Problem A

Alien Sunset

hh,开始一眼差分,但是写寄了qwq,后来换枚举过了(Orz,但是看学长差分是能做的,我就说嘛,差分肯定能做(

说下枚举思路吧,就是把每个区间都存起来,选出自转周期的最大值为\(ma\),然后去枚举\(0 \sim ma \times 1825\),每次看枚举的这个数是否都不在给定的区间内即可,复杂度\(\mathcal{O}(Max(H_i)\times1825 \times N)\)

#include<bits/stdc++.h>

using namespace std;

struct Node{
    int H,R,T;
};

int main() {
    int n,mn = 1,ma = 0;
    cin >> n;
    vector<Node> A(n);
    for(int i = 0;i < n;i ++){
        cin >> A[i].H >> A[i].R >> A[i].T;
        ma = max(ma, A[i].H);
    }

    for(int i = 0;i <= ma * 1825;i ++){

        bool f = true;
        while(f){
            for(int j = 0;j < n;j ++){
                int k = i % A[j].H;
                if(A[j].R < A[j].T){
                    if(k > A[j].R && k < A[j].T){
                        f = false;
                        break;
                    }
                }else{
                    if(k < A[j].T || k > A[j].R){
                        f = false;
                        break;
                    }
                }
            }
            if(f){
                cout << i << '\n';
                return 0;
            }
        }
    }

    cout << "impossible\n";

    return 0;
}

Problem C(贪心)

Cued In

推倒一下样例大概就能发现:

第一个样例:黑红黑红黑红黑粉

第三个样例:棕红棕红棕红棕红棕红棕绿黄

其实就是先把分最大打进洞,然后场上存在红球就又把分最大的捞出来,再打进红球,最后一定会存在除红球以外的所有球,这时候一一打进去即可.

#include<bits/stdc++.h>

#define endl '\n'

using namespace std;

int main() {

    int n;
    cin >> n;
    unordered_map<string,int> col;
    col["red"] = 1,col["yellow"] = 2,col["green"] = 3;
    col["brown"] = 4,col["blue"] = 5,col["pink"] = 6, col["black"] = 7;
    int num[8] = {0};

    int ma = 0,sum = 0,rednum = 0;
    for(int i = 0;i < n;i ++){
        string s;
        cin >> s;
        rednum += (s == "red");
        num[col[s]]++;
        sum += col[s];
        ma = max(ma, col[s]);
    }

    if(rednum == n){
        cout << "1\n";
    }else{
        cout << (ma + 1) * rednum + (sum - rednum) << '\n';
    }

    return 0;
}

Problem D

Deranging Hat

思路就是将给的字符串排序后再还原到原字符串,然后哪项更大就放前边输出

#include<bits/stdc++.h>

#define endl '\n'

using namespace std;

int32_t main() {

    string s;
    cin >> s;

    string str = s;

    sort(str.begin(), str.end());

    for (int i = 0; i < str.size(); i++) {

        if (s[i] != str[i]) {
            for (int j = i + 1; j < str.size(); j++) {
                if (str[j] == s[i]) {
                    if (str[j] > str[i])cout << j + 1 << ' ' << i + 1 << endl;
                    else cout << i + 1 << ' ' << j + 1 << endl;
                    swap(str[j],str[i]);
                    break;
                }
            }
        }
    }

    return 0;
}

Problem E(贪心)

Education

本题就是一个排序贪心的问题,将房子按租金从小到大排序,然后学生也是人数从多到少排序,最后将学生放进房子就行(

#include<bits/stdc++.h>

#define endl '\n'

using namespace std;

typedef pair<int,int> PII;
typedef pair<PII,int> PPI;

int main() {

    int n,m;
    cin >> n >> m;
    vector<PII> s(n + 1);
    vector<pair<PII,int>> p(m + 1);
    for(int i = 1;i <= n;i ++) {
        cin >> s[i].first;
        s[i].second = i;
    }
    for(int i = 1;i <= m;i ++) cin >> p[i].first.first;
    for(int i = 1;i <= m;i ++){
        cin >> p[i].first.second;
        p[i].second = i;
    }

    std::sort(s.begin() + 1, s.end(),[](PII a,PII b){
        return a.first > b.first;
    });
    std::sort(p.begin() + 1, p.end(),[](PPI a, PPI b){
        if(a.first.second == b.first.second) return a.first.first < b.first.first;
        return a.first.second < b.first.second;
    });

    vector<int> ans(n + 1);
    vector<bool> vis(m + 1,false);
    int cnt = 0;
    for(int i =1;i <= n;i ++){

        for(int j = 1;j <= m;j ++){
            if(p[j].first.first >= s[i].first && !vis[j]){
                vis[j] = true;
                cnt ++;
                ans[s[i].second] = p[j].second;
                break;
            }
        }
    }

    if(cnt != n){
        cout << "impossible\n";
    }else{
        for(int i = 1;i <= n;i ++){
            cout << ans[i] << " \n"[i == n];
        }
    }


    return 0;
}

Problem F(概率dp)

Flipping Coins

设\(dp[i][j]\)表示抛i次j个向上的概率，根据全概率公式：\(dp[i][j] = dp[i - 1][j] * 0.5 + dp[i - 1][j - 1] * 0.5\)，

特别的，当\(j = (n - 1)\) 时，有\(dp[i][j] = dp[i - 1][j] * 0.5 + dp[i - 1][j + 1] * 0.5 + dp[i - 1][j - 1] * 0.5\)。

因为在\(j = (n-1)\)时,还可以是由全部面朝上的硬币得到,比如抛了一枚面朝上的硬币但最后那枚硬币面朝下,这个时候也能得到\((n-1)\)枚向上,另外概率不能直接除以2,会丢失小数.

#include<bits/stdc++.h>
using namespace std;

double dp[610][610];

int main(){
    ios::sync_with_stdio(0),cin.tie(0);//,cout.tie();
    int n, k;
    cin >> n >> k;
    dp[0][0] = 1;
    for(int i=1;i<=k;i++) {
        for (int j = 0; j <= k; j++) {
            dp[i][j] += dp[i - 1][j] * 0.5 + dp[i - 1][j - 1] * 0.5;
            if(j == n-1) dp[i][j] += dp[i - 1][n] * 0.5;
        }
    }
    double ans = 0;
    for(int i=0;i<=n;i++) ans += i*dp[k][i];
    printf("%.8lf",ans);
    return 0;
}

Problem I

I Work All Day

就是选择一个长度使得木头被这个长度均分后剩余的边角料(?)最少,所以直接取模看哪个余数最小就选哪个长度

#include<bits/stdc++.h>
//#define int long long
#define endl '\n'

using namespace std;

int32_t main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &i: a)cin >> i;
    int m;
    cin >> m;
    int ans = INT_MAX;
    int x = INT_MAX;
    for (auto i: a) {
        if (m % i < x) {
            x = m % i;
            ans = i;
        }
    }
    cout << ans << endl;
    return 0;
}