题意#

模拟滚榜的流程

题解#

注意每次过完一道题都应该更新榜单

代码#

struct team
{
    int id;
    string problems;
};

void idol_produce(int testCase) {
    /*Code Here*/
    int n, m, p;
    cin >> n >> m >> p;
    vector<team> teams(n + 1);
    int sum = 0;
    for(int i = 1;i <= n; i++){
        cin >> teams[i].problems;
        teams[i].id = i;
        sum += count(teams[i].problems.begin(), teams[i].problems.end(), 'P');
    }
    int id = n;
    for(int i = 1;i <= sum; i++){
        string s;
        cin >> s >> s;
        while(teams[id].problems.find('P') == string::npos) id--;
        if (s == "Aaawww..."){
            for(auto &c : teams[id].problems){
                if(c == 'P'){
                    c = 'R';
                    break;
                }
            }
        }
        else{
            s.pop_back();
            s.pop_back();
            s.pop_back();
            s = s.substr(6);
            int up = s.size();
            for (auto &c : teams[id].problems) {
                if (c == 'P') {
                    c = 'A';
                    break;
                }
            }
            for(int i = id - 1; i >= id - up; i --){
                swap(teams[i], teams[i + 1]);
            }
        }
    }
    for(int i = 1;i <= n; i++){
        if(teams[i].id == p){
            cout << i << '\n';
            return;
        }
    }
}

题意#

判断给定的对是否形成不降序

题解#

按题意模拟即可

代码#

void idol_produce(int testCase) {
    /*Code Here*/
    int n;
    cin >> n;
    vector<pair<int, int> > a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i].first >> a[i].second;
    }
    for (int i = 2; i <= n; i++) {
        if (a[i].second < a[i - 1].second || a[i].first < a[i - 1].first) {
            cout << "no\n";
            return;
        }
    }
    cout << "yes\n";
}

题意#

给定 $n$ 个价格的物品，可以选择现金或刷卡支付，若选择现金支付价格将四舍五入最接近的 $0.05$，你可以将多个物品分为一组进行支付，使总价格最小

题解#

将所有价格单位转化成美分，并对 $5$ 美分取模，这样就得到模数为 $0 - 4$ 美分的各个物品的价格

• 对于所有的 $1$ 和 $2$ 美分的价格直接向下取整
• 对于每一对 $3$ 和 $4$ 美分的价格分为一组得到 $2$ 美分后向下取整
• 若剩余 $3$，则将每一对 $3$ 分为一组得到 $1$ 后向下取整
• 若剩余 $4$，则将每三个 $4$ 分为一组得到 $2$ 后向下取整
• 剩余的价格直接加入答案

为什么要先把 $3$ 和 $4$ 组成一对，再处理剩余的？

令 $f$ 表示将一些价格分为一组可以省下来的美分

显然对于省下同样的美分，将 $3$ 和 $4$ 组合起来一定比单独分组更优

代码#

void idol_produce(int testCase) {
    /*Code Here*/
    int n;
    cin >> n;
    vector<int> a(5);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        double x;
        cin >> x;
        // use round() not (int)()
        int p = round(x * 100);
        a[p % 5]++;
        ans += p;
    }
    ans -= a[1];
    ans -= a[2] * 2;
    ans -= min(a[3], a[4]) * 2;
    int tmp = min(a[3], a[4]);
    a[3] -= tmp;
    a[4] -= tmp;
    ans -= a[3] / 2;
    ans -= a[4] / 3 * 2;
    cout << fixed << setprecision(2) << ans / 100.00 << '\n';
}

题意#

给定一个长度为 $n$ 的不递减的未知数列 $o$，每一次询问 $i$ 可以得到 $o_i$ 的值，在 $50$ 次询问内，得到一个三元组 $(x, y, z)(1 \leq x,y,z \leq n, x \neq y, x \neq z, y \neq z)$ 使得 $\sqrt{|{o_x - o_y}|} + \sqrt{|{o_x - o_z}|} + \sqrt{|{o_y - o_z}|}$ 最大

题解#

设 $x < y < z$，显然 $x = 1, z = n$ 必然最优，即：

我们只需要确定 $y$ 的值即可，该函数求导后为一个凸函数，在 $o_y = \frac{1}{2} (o_1 + o_n)$ 最大，二分找到原数列最接近的值即可

int ask(int x) {
    cout << "? " << x << endl;
    int res;
    cin >> res;
    return res;
}

void answer(int x, int y, int z) {
    cout << "! " << x << " " << y << " " << z << endl;
    return;
}
void idol_produce(int testCase) {
    /*Code Here*/
    int n;
    cin >> n;
    int target = ask(1) + ask(n);
    int ans = -1;
    int res = INF;
    int l = 2, r = n - 1;
    while(l <= r){
        int mid = (l + r) >> 1;
        int tmp = ask(mid);
        if(abs(tmp * 2 - target) < res){
            ans = mid;
            res = abs(tmp * 2 - target);
        }
        if(tmp * 2 == target){
            break;
        }
        if(tmp * 2 < target){
            l = mid + 1;
        }else{
            r = mid - 1;
        }
    }
    answer(1, ans, n);
}

题意#

计划完成 $n$ 天的旅行，票价分为单程票和通行证

$n$ 张单程票，第 $i$ 张单程票表示第 $t_i$ 天旅行票价为 $f_i$

$k$张通行证，第 $i$ 张通行证表示购买价格为 $c_i$ 的通行证后，接下来的 $p$ 天内（包含当天），前 $d$ 次旅行免费

求完成 $n$ 天旅行的最少花费的价格

题解#

令 $pre(t)$ 表示第 $t$ 天之前的最新的旅行日的索引，即 $max(i|t_i \leq t)$，这个可以预处理

令 $dp_i$ 表示前 $i$ 次旅行最少花费的价格

那么得到转移方程:

代码#

void idol_produce(int testCase) {
    /*Code Here*/
    int n, k;
    cin >> n >> k;
    vector<int> t(n + 1), f(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> t[i] >> f[i];
    }
    vector<int> pre((int)1e6 + 5);
    int id = 0;
    for (int i = 0; i <= 1e6; i++) {
        while (id < n && t[id + 1] <= i) {
            id++;
        }
        pre[i] = id;
    }
    vector<int> p(k + 1), d(k + 1), c(k + 1);
    for (int i = 1; i <= k; i++) {
        cin >> p[i] >> d[i] >> c[i];
    }
    auto get_pre = [&](int x) {
        if (x < 0) return 0;
        return pre[x];
    };
    vector<int> dp(n + 1);
    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i - 1] + f[i];
        for (int j = 1; j <= k; j++) {
            dp[i] = min(c[j] + dp[max(i - d[j], get_pre(t[i] - p[j]))], dp[i]);
        }
    }
    cout << dp[n] << '\n';
}

题意#

给定 $n$ 个步骤，这些步骤有依赖关系（可能存在循环依赖），步骤 $i$ 有 $p_i$ 概率失败，一个步骤不失败要求它及其前置步骤均不失败，问失败概率最小的步骤的不失败概率为多少

题解#

对于非循环依赖的步骤，显然所有不存在依赖的步骤失败概率最小，对于循坏依赖的步骤，其组成的一个强连通分量中的每一个步骤的不失败概率均为 $\prod(1 - p_i)$ 先求强连通分量，再对所有入度为 $0$ 的步骤的失败概率取最小即可。

NOTE

输出小数点后200位

代码#

const int N = 1e5 + 5;
int dfn[N], low[N], dfncnt, s[N], in_stack[N], tp;
int scc[N], sc;  // 结点 i 所在 SCC 的编号
int sz[N];       // 强连通 i 的大小
vector<vector<int>> e(N);
void tarjan(int u) {
    low[u] = dfn[u] = ++dfncnt, s[++tp] = u, in_stack[u] = 1;
    for (auto v : e[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in_stack[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u]) {
        ++sc;
        do {
            scc[s[tp]] = sc;
            sz[sc]++;
            in_stack[s[tp]] = 0;
        } while (s[tp--] != u);
    }
}

void idol_produce(int testCase) {
    /*Code Here*/
    int n, m;
    cin >> n >> m;
    vector<double> p(n + 1);
    for(int i = 1;i <= n; i++){
        double x;
        cin >> x;
        p[i] = 1.0 - x;
    }
    vector<pair<int,int> > ed;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        e[v].push_back(u);
        ed.push_back({u, v});
    }
    for(int i = 1;i <= n; i++){
        if(!dfn[i]) tarjan(i);
    }
    vector<double> ans(sc + 1, 1);
    vector<int> in(sc + 1);
    for(int i = 1;i <= n; i++){
        ans[scc[i]] *= p[i];
    }
    for(auto &[u, v] : ed){
        if(scc[u] != scc[v]){
            in[scc[u]]++;
        }
    }
    double res = 0;
    for(int i = 1;i <= sc; i++){
        if(in[i] == 0){
            res = max(res, ans[i]);
        }
    }
    cout << fixed << setprecision(200) << res << '\n';
}

题意#

给定 $1-n$ 每个整数的代价 $c_i$, 选择一个整数集合使得对于共计 $m$ 个区间的每一个区间 $[l_i,r_i]$，都有至少一个整数落在区间内，求最小的代价之和

题解#

显然动态规划：

设 $dp_i$ 表示在选择整数 $i$ 的前提下，所有 $r_i \leq i$ 的区间均被满足的最小代价

其中 $k_i$ 表示所有 $\max(l_i|r_i < i)$，即所有满足 $r_i < i$ 的区间中，最大的 $l_i$

可以使用线段树维护 $dp$ 值

代码#

void idol_produce(int testCase) {
    /*Code Here*/
    int n, m;
    cin >> n >> m;
    vector<ll> dp(n + 2, 0);
    vector<ll> c(n + 2, 0);
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
    }
    vector<pair<int,int>> p(m + 1);
    for (int i = 1; i <= m; i++) {
        cin >> p[i].first >> p[i].second;
    }
    sort(p.begin() + 1, p.end(), [](const pair<int,int> &a, const pair<int,int> &b) {
        return a.second > b.second;
    });
    SegmentMinTree st(vector<ll>(n + 2));
    int l = 0;
    for(int i = 1;i <= n + 1; i++){
        while(!p.empty() && p.back().second < i){
            l = max(l, p.back().first);
            p.pop_back();
        }
        if(l == 0) dp[i] = c[i];
        else dp[i] = c[i] + st.query(l, i - 1);
        st.change(i, i, dp[i]);
    }
    cout << dp[n + 1] << '\n';
}

题意#

给定一个字符串 $s$，选择一个非空字符串 $t$，将字符串 $s$ 中的所有不相交的子串 $t$ 均替换为单个字符，获得新的字符串 $s'$，求 $|{t}| + |{s'}|$ 的最小值

题解#

采用哈希计算每个不相交子字符串出现的数量，注意必须选择一个非空子串，所以初始 $ans = |{s}| + 1$

NOTE

不要用 map or unordered_map 将哈希值直接作为下标存储对应的 $index$ 集合，否则你的时间常数和空间常数会巨大

代码#

int get_id(int i, int j){
    return 5000 * i + j;
}
void idol_produce(int testCase) {
    /*Code Here*/
    string s;
    cin >> s;
    int n = s.size();
    vector<ull> hash_value(5005 * 5005);
    for(int i = 0; i < n; i++){
        ull h = 0;
        for(int j = i; j < s.size(); j++){
            h = h * 131 + s[j];
            hash_value[get_id(i, j + 1)] = h;
        }
    }
    int ans = s.size() + 1;
    unordered_map<ull, int> count, next_pos;
    for(int len = 2; len < n; len++){
        count.clear();
        next_pos.clear();
        for(int i = 0; i <= n - len; i++){
            ull h = hash_value[get_id(i, i + len)];
            if(next_pos[h] > i) continue;
            count[h]++;
            next_pos[h] = i + len;
        }
        for(auto [_,c]:count){
            ans = min(ans, n - (len - 1) * (c - 1) + 1);
        }
    }
    cout << ans << "\n";
}

题意#

在未加权图中找到最短路径，但不能进行超过 $k$ 个不间断的转弯。求最短路径

题解#

以 路口位置，路口方向，信号灯状态，开启次数，步数 为节点状态进行广度优先搜索。

NOTE

朝路口某段方向行驶时，不一定走直线。如样例，从路口 $2$ 向南行驶，到达路口 $3$ 时不处在其北侧。

代码#

vector<vector<int> > a(5005, vector<int>(4, 0));

enum Light { left = -1, right = 1, up = 0 };
struct node {
    int loc;
    int direction;
    int light;
    int time;
    int step;

    node go_up() {
        node res = *this;
        if (res.light != Light::up) {
            res.light = Light::up;
        }
        res.loc = a[res.loc][(res.direction + 2) % 4];
        res.step += 1;
        if (res.loc == 0) return res;
        for (int i = 0; i < 4; i++) {
            if (a[res.loc][i] == this->loc) res.direction = i;
        }
        return res;
    }

    node go_right() {
        auto res = *this;
        if (res.light != Light::right) {
            res.light = Light::right;
            res.time += 1;
        }
        res.loc = a[res.loc][(res.direction + 3) % 4];
        res.step += 1;
        if (res.loc == 0) return res;
        for (int i = 0; i < 4; i++) {
            if (a[res.loc][i] == this->loc) res.direction = i;
        }
        return res;
    }

    node go_left() {
        auto res = *this;
        if (res.light != Light::left) {
            res.light = Light::left;
            res.time += 1;
        }
        res.loc = a[res.loc][(res.direction + 1) % 4];
        res.step += 1;
        if (res.loc == 0) return res;
        for (int i = 0; i < 4; i++) {
            if (a[res.loc][i] == this->loc) res.direction = i;
        }
        return res;
    }

    bool operator==(const node &x) const {
        return x.loc == loc && x.direction == direction && x.light == light &&
               x.time == time;
    }
};

struct NodeHasher {
    size_t operator()(const node &x) const {
        return (hash<int>()(x.loc) * 4) ^ (hash<int>()(x.direction) * 3) ^
               (hash<int>()(x.light) * 2) ^ hash<int>()(x.time);
    }
};
void idol_produce(int testCase) {
    /*Code Here*/
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 4; j++) {
            cin >> a[i][j];
        }
    }
    if (n == 1) {
        cout << 0 << '\n';
        return;
    }
    queue<node> q;
    for (int i = 0; i <= 3; i++) {
        if (a[1][i] == 0) continue;
        int dir = 0;
        for (int j = 0; j < 4; j++) {
            if (a[a[1][i]][j] == 1) {
                dir = j;
                break;
            }
        }
        q.push({a[1][i], dir, up, 0, 1});
    }
    unordered_set<node, NodeHasher> vis;
    while (!q.empty()) {
        auto t = q.front();
        q.pop();
        if (t.time > k) continue;
        if (vis.count(t)) continue;
        vis.insert(t);
        if (t.loc == n) {
            cout << t.step << '\n';
            return;
        }
        auto res = t.go_up();
        if (res.loc != 0) q.push(res);
        res = t.go_left();
        if (res.loc != 0) q.push(res);
        res = t.go_right();
        if (res.loc != 0) q.push(res);
    }
    cout << "impossible\n";
}

题意#

将 $n$ 个数 $[a_1,a_2,a_3...,a_n]$ 分为 $m$ 组，每组的价值为 $p_j$ 使得所有数均满足以下条件：

1. 对于组别 $j$ 的总和 $sum_j = \sum\limits_{i \in j} a_i$
2. 属于组别 $j$ 的数字 $a_i$ ，满足 $\frac{a_i \times p_j}{sum_j} \geq \frac{a_i \times p_k}{sum_k + a_i},k \neq j$

题解#

对数字从大到小排序，以此将每个数字放在其占比最大的一个分组中。

证明：

1. 对于当前选择的数字 $a_i$，显然选择价值最大的组为最优解，设其选择的组别为 $k$。

2. 对于已经分好组的数字 $a_j$，满足 $a_j \geq a_i$

3. 对于与 $a_i$ 同组的 $a_j$，在 $a_i$ 不加入 $k$ 前满足：

   $$\frac{a_i \times p_k}{sum_k + a_i} \geq \frac{a_i \times p_{other}}{sum_{other} + a_i}$$

   因此，必然满足：

   $$\frac{a_j \times p_k}{sum_k + a_i} \geq \frac{a_j \times p_{other}}{sum_{other} + a_j}, a_j \geq a_i$$

   因此 $a_j$ 移到其他组一定不优

4. 对于与 $a_i$ 不同组的 $a_j$，在 $a_i$ 不加入前就已经选择好了最优组，$a_i$ 加入 $k$ 只是让一个对于 $a_j$ 不优的组变得更加不优而已

代码#

void idol_produce(int testCase) {
    /*Code Here*/
    int n, m;
    cin >> n >> m;
    vector<pair<ll, int>> a(n + 1);
    vector<ll> p(m + 1);
    for (int i = 1; i <= n; i++) cin >> a[i].first, a[i].second = i;
    for (int i = 1; i <= m; i++) cin >> p[i];
    sort(a.begin() + 1, a.end(), greater<>());
    vector<vector<int> > ans(m + 1);
    vector<ll> sum(m + 1);
    for(int i = 1;i <= n;i ++){
        int id = 1;
        for(int j = 2;j <= m;j ++){
            if(p[j] * (sum[id] + a[i].first) > p[id] * (sum[j] + a[i].first)){
                id = j;
            }
        }
        ans[id].emplace_back(a[i].second);
        sum[id] += a[i].first;
    }
    for(int i = 1;i <= m;i ++){
        cout << ans[i].size() << ' ';
        for(int j = 0;j < ans[i].size();j ++){
            cout << ans[i][j] << ' ';
        }
        cout << '\n';
    }
}