第六届浙江ACM省赛——解题报告

最近有点伤感啊,区域赛打的不好,随便找了个省赛的题练练手,省赛整体还是比区域赛简单的。后面有几个比较难的题过后单独补上

Problem A Second-price Auction

Link

点击打开题目链接——zoj3202

Mean

水题,排序后找出最大和次大的即可。

Code

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

typedef pair<int, int> P;
P v[110];

int main() {
    int T; cin >> T;
    while(T--) {
        int n; cin >> n;
        for(int i = 1; i <= n; ++i) {
            cin >> v[i].first;
            v[i].second = i;
        }
        sort(v + 1, v + n + 1);
        cout << v[n].second << " " << v[n-1].first << endl;
    }
    return 0;
}

Problem B Light Bulb

Link

点击打开题目啊链接——zoj3202

Mean

有一个屋子,有灯泡和一个人,屋子的长和灯泡的高度和人的身高是固定的,问你影子最长是多少,影子可以打在墙上。

推公式然后打表看一下,最后的结果是凸函数,所以三分答案即可。三分的时候用《挑战编程竞赛》上的一个技巧就是循环100次即可,防止出现来回WA和TLE的情况。

Code

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

const double eps = 1e-7;
double H, h, D;
double lim;


double solve(double i) {
    if(i >= lim) {
        double d = D - i;
        return d * h / H;
    }
    double m = (D*h - i*H) / (H - h);
    return i + H * m / (D + m);
}



int main()
{
    int T; scanf("%d", &T);
    while(T--) {
        scanf("%lf%lf%lf", &H, &h, &D);
        lim = D * h / H;
        double L = 0, R = D;
        for(int i = 0; i < 100; ++i) {
            double mid1 = L + (R - L) / 3.0;
            double mid2 = R - (R - L) / 3.0;
            if(solve(mid1) > solve(mid2)) {
                R = mid2;
            } else {
                L = mid1;
            }
        }
        printf("%.3f\n", solve(L));
    }
    return 0;
}

Problem C Connect them

Link

点击打开题目链接——zoj3204

Mean

有N个点,每两个点要想连通都有一个花费,有些点之间不能连通,让你建造一些路,使得所有点能够连通。总的路程必须最短,如果有多个最短,选出使得输出字典序最小的路。

最小生成树的变式,还是用kruskal,排序的时候按照字典序排一下,输出的时候也按照字典序排一下就好了。注意双向的路都要加进去,比如2-3和3-2两条路都要有,这样才能保证字典序。

Code

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;

struct Edge {
    int from, to, cost;
    Edge(int from, int to, int cost):
        from(from), to(to), cost(cost) {}
    bool operator < (const Edge & rhs) const {
        if(cost != rhs.cost) return cost < rhs.cost;
        if(from != rhs.from) return from < rhs.from;
        return to < rhs.to;
    }
};
const int maxn = 110;
vector<Edge> e;
vector<P> res;
int n, pa[maxn];

void Init(int n) { for(int i = 0; i <= n; ++i) pa[i] = i; }
int Find(int x) { return pa[x] == x ? x : pa[x] = Find(pa[x]); }

void Kruskal() {
    sort(e.begin(), e.end());
    res.clear();
    int cnt = 0;
    Init(n);
    for(int i = 0; i < e.size(); ++i) {
        int rx = Find(e[i].from);
        int ry = Find(e[i].to);
        if(rx != ry) {
            pa[rx] = ry;
            res.push_back(P(e[i].from, e[i].to));
            ++cnt;
            if(cnt >= n - 1)
                break;
        }
    }
}

int main() {
    int T; scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        e.clear();
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= n; ++j) {
                int len; scanf("%d", &len);
                if(len) e.push_back(Edge(i, j, len));
            }
        }
        Kruskal();
        if(res.size() < n-1) {
            puts("-1");
        } else {
            sort(res.begin(), res.end());
            for(int i = 0; i < res.size(); ++i) {
                printf("%d %d%c", res[i].first, res[i].second, i==res.size()-1 ? '\n' : ' ');
            }
        }
    }
    return 0;
}

Problem F 80ers’ Memory

Link

点击打开题目链接——zoj3207

Mean

水题,给出N个单词“记忆”和K个查询,每次查询输出本次查询在“记忆”中的个数。

直接用set搞即可。

Code

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

set<string> s;

int main() {
    int n; cin >> n;
    for(int i = 0; i < n; ++i) {
        string cur; cin >> cur;
        s.insert(cur);
    }
    cin >> n;
    while(n--) {
        int m, cnt = 0; cin >> m;
        while(m--) {
            string cur; cin >> cur;
            if(s.count(cur)) ++cnt;
        }
        cout << cnt << endl;
    }
    return 0;
}

Problem I A Stack or A Queue?

Link

点击打开题目链接——zoj3210

Mean

给你一个序列,给出入栈/队列的序列,和出栈/队列的序列,入和出不交叉。问你到底是栈还是队列。

直接加在vector里用==判断,然后stl的reverse一遍再==一遍。就可以判断出来了

Code

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

vector<int> a, b;

int main() {
    int T; cin >> T;
    while(T--) {
        int n; cin >> n;
        a.clear(); b.clear();
        for(int i = 0; i < n; ++i) {
            int x; cin >> x;
            a.push_back(x);
        }
        for(int i = 0; i < n; ++i) {
            int x; cin >> x;
            b.push_back(x);
        }
        bool ok1 = false;
        bool ok2 = false;
        if(a == b) ok1 = true;
        reverse(a.begin(), a.end());
        if(a == b) ok2 = true;
        if(ok1 && ok2) {
            cout << "both" << endl;
        } else if(ok1 && !ok2) {
            cout << "queue" << endl;
        } else if(!ok1 && ok2) {
            cout << "stack" << endl;
        } else {
            cout << "neither" << endl;
        }
    }
    return 0;
}

Problem J Dream City

Link

点击打开题目链接——zoj3211

Mean

有N颗树,每棵树都有初始水果个数Ai,每棵树每天都会固定多长Bi个水果。你每天只能砍一棵树,收获果实,一共M天,问你最多能收获多少个水果。

收获的顺序一定是按照B递增的顺序,脑补+草稿一下为什么……这样就排序后转化成01背包来搞,N*logN + N*M的复杂度。

Code

#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;

const int maxn = 300;
int n, m, dp[maxn][maxn];
P v[maxn];

int main() {
    int T; scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; ++i)
            scanf("%d", &v[i].first);
        for(int i = 1; i <= n; ++i)
            scanf("%d", &v[i].second);
        sort(v+1, v+n+1, [](const P &a, const P& b) { return a.second < b.second; });
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= m; ++i) {
            for(int j = 1; j <= n; ++j) {
                dp[i][j] = max(dp[i][j-1], dp[i-1][j-1] + v[j].first + (i-1)*v[j].second);
            }
        }
        printf("%d\n", dp[m][n]);
    }
    return 0;
}

Problem K K-Nice

Link

点击打开题目链接——zoj3212

Mean

构造一个N×M的棋盘,使得不在边缘的数中有K个满足以下条件:这个数==sum(这个数周围的4个数)。

观察样例二即可发现一种构造方法,就是棋盘初始化为0,这样就有(N-1)*(M-1)个满足条件的数字,从第一行第二个往后填充1,2,3…,这样这个数下面的数便不满足条件。这样填充构造即棋盘可。

Code

#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;

const int maxn = 300;
int n, m, dp[maxn][maxn];
P v[maxn];

int main() {
    int T; scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; ++i)
            scanf("%d", &v[i].first);
        for(int i = 1; i <= n; ++i)
            scanf("%d", &v[i].second);
        sort(v+1, v+n+1, [](const P &a, const P& b) { return a.second < b.second; });
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= m; ++i) {
            for(int j = 1; j <= n; ++j) {
                dp[i][j] = max(dp[i][j-1], dp[i-1][j-1] + v[j].first + (i-1)*v[j].second);
            }
        }
        printf("%d\n", dp[m][n]);
    }
    return 0;
}

 

欢迎留言