Contestant. Rank 2. Solved 4/8.

A. ACM? 你也想打ACM?

题意

对于 道题，给定 个提交记录，规定罚时为 分钟，按照 赛制计算通过题数和总用时。

思路

首先，没过的题不算罚时，过了的题重复提交无效。

因为题给数据是按照时间排序的，那么，我们不妨从前往后遍历，用数组记录当前的状态。

对于下面的 代码，其中 表示当前是否过了 题； 表示第 道题最早是在 时刻通过的； 表示第 道题在通过前 了几次。

最后，我们遍历所有题，如果过题了，记录过题数，并将总用时加上 。

时间复杂度：

本题测试点数据量过大，java需要使用快读，cpp若使用cin需要关闭输入输出流同步

对应AC代码 (cpp)

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 1.5e6 + 10, inf = 0x3f3f3f3f3f3f3f3f;

int a[N], p[N];
bool ok[N];

void solve(){
    int n, k;
    cin >> n >> k;
    for(int i=0;i<k;i++){
        string s;
        cin >> s;
        int id, h, m, now = 0, st = 0;
        bool msg = true;
        for(int i=0;i<s.size();i++){
            char e = s[i];
            if(e == ':'){
                if(st == 0){
                    id = now;
                    now = 0;
                    st = 1;
                }else if(st == 1){
                    m = now;
                    now = 0;
                    st = 2;
                }
            }else if(e == '-'){
                h = now;
                now = 0;
            }else if(e >= '0' && e <= '9'){
                now = now * 10 + (e - '0');
            }else if(e == 'u'){ //读到u就差不多了
                msg = false;
                break;
            }else break;
        }
        int cal = h * 60 + m;
        if(!ok[id]) a[id] = cal;
        if(msg) ok[id] = true;
        else if(!ok[id]) p[id] ++;
    }
    int cnt = 0, tot = 0;
    for(int i=1;i<=n;i++){
        cnt += ok[i] ? 1 : 0;
        if(ok[i]) tot += a[i] + p[i] * 20;
    }
    cout << cnt << ' ' << tot << '\n';
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t --) solve();
}

对应AC代码 (java)

import java.io.*;
import java.math.*;
import java.util.*;
import java.util.concurrent.atomic.*;

public class Main{
    public static void main(String[] args) throws Exception {
        Console console = new Console();
        int n = console.nextInt(), k = console.nextInt();
        boolean[] ok = new boolean[n + 1];
        int[] a = new int[n + 1], p = new int[n + 1];
        for (int i = 0; i < k; i++) {
            String[] s = console.next().split(":");
            int id = Integer.parseInt(s[0]),
                    cal = Integer.parseInt(s[1].split("-")[0]) * 60 + Integer.parseInt(s[1].split("-")[1]);
            if (!ok[id]) a[id] = cal;
            if (s[2].equals("accepted")) ok[id] = true;
            else if (!ok[id]) p[id]++;
        }
        int cnt = 0, tot = 0;
        for (int i = 1; i <= n; i++) {
            cnt += ok[i] ? 1 : 0;
            if (ok[i]) tot += a[i] + p[i] * 20;
        }
        console.print(cnt + " " + tot + "\n");
        console.close();
    }

    //快读模板 此处略去
    //public static class Console implements Closeable {}
}

java挂掉后果断切cpp，淦

B. 任何邪恶? 终将绳之以法!

题意

给定一个满二叉树，满足根节点为 ，节点 的子节点为 。

定义操作为下面三者任选一：

1. ，输出 节点到其他被标记节点的最短距离总和；

2. ，标记 节点；

3. ，取消标记 节点。

给定 个询问，执行对应操作。

思路

一些废话

首先，节点 的最短距离为两者 离 它们的 最近公共祖先 的距离 之和。

也就是说，这个路径一定是先向上找，再从一个节点折返，最后从下找的。

这个节点就像一个跳板，不过当然，跳板可以是起点自己。

当然，讨论到这里，我们也许可以对每个查询，都去跑一遍最近公共祖先（），但我觉得没这个必要。

不过，有没有一种可能，对于一个跳板，我们可以预处理出它的左右子树各有多少点被标记了，以及这些点距离跳板的距离呢。

这个预处理过程可以放在标记的时候。而且，我们不难发现这个过程是可逆的。因而，在取消标记的时候，我们进行相反的操作就好了。

具体思路

计算

首先，我们先来考虑怎么计算：

我们不妨从查询点 开始向上遍历，并记录当前走了 步。遍历时，我们传递一下当前遍历到的父节点 是由哪个子树来的，这个参数和 的奇偶性有关。这样的话，我们就可以拿出另一个子树中所有被标记点到 的距离和 ，以及被标记的节点数 。画个图易得， 到 这段路被反复经过了 次，经过这个跳板后，剩余距离的总和就是 ，因此，以 为跳板，我们可以得到贡献 。

上述过程对于 的情况是成立的，而 时，两个子树的值我们都需要考虑（传参时，我们不妨传递一个特殊值，如 ），具体的贡献计算方式和上面一致。

特别地，若我们遍历到的 是被标记过的，那么贡献会多出 。

预处理

对于加上一个标记 的操作，我们可以从该节点开始向上遍历，直到根节点为止。

同样，在遍历的时候，我们记录步数 ，并传递 是由哪个子树来的，然后将 对应子树的 加上 ， 加上 。

取消标记的做法恰好相反，减去即可。

时间复杂度：反正挺复杂

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;

pii dp[N][2];
int ans;
bool is[N];

void up_dfs_add(int x, int from, int st){
    if(x == 0) return;
    if(from == -1){
        dp[x][0].first += st;
        dp[x][1].first += st;
    }else dp[x][from].first += st, dp[x][from].second ++;
    up_dfs_add(x / 2, x % 2, st + 1);
}

void up_dfs_del(int x, int from, int st){
    if(x == 0) return;
    if(from == -1){
        dp[x][0].first -= st;
        dp[x][1].first -= st;
    }else dp[x][from].first -= st, dp[x][from].second --;
    up_dfs_del(x / 2, x % 2, st + 1);
}

void up_dfs_cal(int x, int from, int st){
    if(x == 0) return;
    int cur;
    if(from == -1) cur = dp[x][0].first + dp[x][1].first > 0 ? (dp[x][0].first + dp[x][0].second * st + dp[x][1].first + dp[x][1].second * st) : 0;
    else cur = dp[x][1 - from].first > 0 ? (dp[x][1 - from].first + dp[x][1 - from].second * st) : 0;
    ans += cur;
    if(is[x]) ans += st;
    up_dfs_cal(x / 2, x % 2, st + 1);
}

void solve(){
    int n, q;
    cin >> n >> q;
    while(q --){
        int tp, x;
        cin >> tp >> x;
        if(tp == 1){
            ans = 0;
            up_dfs_cal(x, -1, 0);
            cout << ans << '\n';
        }else if(tp == 2) is[x] = true, up_dfs_add(x, -1, 0);
        else is[x] = false, up_dfs_del(x, -1, 0);
    }
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t --) solve();
}

复杂之，但类似的题其实做过好几次吧，有点像树型dp

C. 蘑菇! 提莫来采蘑菇啦!

没做，待补充

D. 锁屏图案? 当然是第k长的最好看!

题意

对于一个九宫格锁屏图案，规定需要一笔将所有点连起来，且不能重复使用同一个点。

规定连接了两个点的时候，若这个路径经过了一个未被使用的点，那么这个点一定要一起被连上，否则视为不合法，如斜角上的 ，在没使用过 前， 是不合法的。

定义满足条件的全排列中，排序的主关键字为路径长，次要关键字为字典序，按照降序排列。

给定 个询问，对于给定的 ，输出第 个排列。

思路

首先，数据量很小， 的复杂度完全可以暴力。

那么，我们不妨枚举所有全排列，然后算出可行解的路径长，以及排列的结果，按照这个排个序然后取出来就好了。

唯一麻烦的是码量。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-7;

struct node{
    string ans;
    double dist;
};

vector<node> ans;
vector<int> a = {1, 2, 3, 4, 5, 6, 7, 8, 9};
vector<pii> pos(10);

double cal(int x, int y){
    return sqrt(pow(abs(pos[x].fs - pos[y].fs), 2) + pow(abs(pos[x].sc - pos[y].sc), 2));
}

bool check(int l, int r, int mid){
    int l_pos = -1, r_pos = -1, m_pos = -1;
    for(int i=0;i<9;i++){
        if(a[i] == l) l_pos = i;
        else if(a[i] == r) r_pos = i;
        else if(a[i] == mid) m_pos = i;
    }
    if(l_pos > r_pos) swap(l_pos, r_pos);
    return l_pos + 1 != r_pos || m_pos < r_pos;
}

void init(){
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            pos[3 * (i - 1) + j] = {i, j};
    do{
        vector<vector<int>> checker = {{1, 3, 2}, {1, 7, 4}, {3, 9, 6}, {7, 9, 8}, {3, 7, 5}, {1, 9, 5}, {2, 8, 5}, {4, 6, 5}};
        bool f = true;
        for(auto e : checker) f &= check(e[0], e[1], e[2]);
        if(!f) continue;
        node now = {};
        for(int i=0;i<9;i++){
            now.ans += (a[i] + '0');
            now.ans += " ";
            if(i > 0) now.dist += cal(a[i], a[i - 1]);
        }
        ans.emplace_back(now);
    }while(next_permutation(a.begin(), a.end())); //这里学到了，好用的东西
    sort(ans.begin(), ans.end(), [](node o1, node o2){
        return abs(o1.dist - o2.dist) > eps ? o1.dist > o2.dist : o1.ans > o2.ans;
    });
}

void solve(){
    int k;
    cin >> k;
    cout << ans[k - 1].ans << '\n';
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    int t;
    cin >> t;
    while(t --) solve();
}

草，怎么赛时就没想着去做捏，这么暴力（（（

E. 微积分？低程竟然有微积分？

题意

给定一个多项式，满足式子中没有重复次幂，项按照次幂降序排序，次幂最小为 。项的系数可以为负，但不会为 。

输出它的积分。

思路

很清晰的模拟题，坑点在于化简和系数 。

化简很简单，除以 即可。

系数 不做过多解释，自行体会（

时间复杂度：乘上点常数

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;

int gcd(int a, int b){
    return b == 0 ? a : gcd(b, a % b);
}

void solve(){
    string exp;
    cin >> exp;
    exp += "#"; //end
    int now = 0, root = 0;
    cout << "y=";
    bool tp = false;
    for(int i=3;i<exp.size();i++){
        char cur = exp[i];
        if(cur == 'x'){
            root = (now == 0 ? 1 : now);
            now = 0;
            if(i >= exp.size() - 2 || exp[i + 1] != '^'){
                if(root % 2 == 0 && root / 2 != 1) cout << root / 2 << "x^2";
                else if(root % 2 == 0) cout << "x^2";
                else cout << root << "/" << 2 << "x^2";
                root = 0;
            }
        }
        else if(cur == '+' || cur == '-' || cur == '#') {
            if(tp){
                int p = now;
                if(root % (p + 1) == 0 && root / (p + 1) == 1) cout << "x^" << p + 1;
                else if(root % (p + 1) == 0) cout << root / (p + 1) << "x^" << p + 1;
                else{
                    int x = gcd(p + 1, root);
                    cout << root / x << "/" << (p + 1) / x << "x^" << (p + 1);
                }
            }else if(now == 1) cout << "x";
            else if(now != 0) cout << now << "x";
            tp = false; 
            now = 0;
            if(cur == '+' || cur == '-') cout << cur;
            else cout << "+C";
        }
        else if(cur == '^') tp = true;
        else now = now * 10 + (cur - '0');
    }
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t --) solve();
}

系数1太坑了捏

F. SCI! 我就是要发SCI!

题意

给定 个字符串，从中选 个字符串并进行任意组合，输出最小的字典序。

思路

首先，”从 个东西中选 个”，很容易让人想到背包问题，或者更具体地，这是一个 背包。

但是，再套上板子之前，我们思考一下怎么递推。

有一个错误的思路（这也是我在赛时想到的奇怪思路），就是用一维的 ， 表示选了 个后的最小字典序。那么我们直接枚举所有的字符串 ，遍历 。对于 ，遍历其中的字符串，将 依次插入缝中，最后找出一种插法，使得 的字典序变小即可。

显然，我们不可以随意遍历，但有没有一种无需考虑插入位置的方法呢？

我们来考虑任意两个字符串 ，如果 ，那么很显然，前者的字典序更小。

那么，如果有三个呢？如果 ，那么依然是前者的字典序更小。此时，我们联立起两个式子，会发现有趣的事情：。

也就是说，如果我们按照 的字典序升序排序，就可以直接将取出的任意的 个字符串拼接起来，而无需考虑这 个字符串的顺序，此时字典序一定是最小的。

那么，问题就剩下从 个东西中选 个，代价最小的问题了，也就是求最小代价的 背包。

事情到这里并未结束，我们来看下面的样例：

4 3
bbaba
bba
b
b

不难发现，这组数据的答案为 。但如果我们套上板子，直接跑，得到的答案是 。

问题在哪里呢？我们并没有考虑拼接上的答案的后缀，而如果出现了前缀一致的情况，我们无法控制让后缀尽可能短。

那么，很简单的解决方法，就是反着 ，反着拼，这样就可以保证所有后缀的情况都被我们遍历过了。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;

void init(){}

void solve(){
    int n, k;
    cin >> n >> k;
    vector<string> s(n);
    for(int i=0;i<n;i++) cin >> s[i];
    vector<string> dp(k + 1, "{"); //保证ans原来的字典序为inf
    dp[0] = "";
    sort(s.begin(), s.end(), [](string o1, string o2){
        return o1 + o2 > o2 + o1; //倒着做来让所有后缀都被遍历到
    });
    for(auto e : s) //一维01背包
        for(int j=k;j>=1;j--){
            dp[j] = min(dp[j], e + dp[j - 1]);
        }
    cout << dp[k] << '\n';
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    int t = 1;
    //cin >> t;
    while(t --) solve();
}

还好赛时没怎么看这题（打完01的板子就突然意识到思路不对了，草

G. 旅行! 我就是想去旅行!

不会，样例都没过.jpg，待补充

H. WF？刚打低程就想着WF？

题意

定义 种奖牌类型由低到高分别为 ，，，，，。奖牌由低到高分为铜 ()，银 ()，金 ()。当然还有铁牌，但不计入。

定义三个相同的牌可以合成一个等级更高的牌，输出拿到 的金牌的最早时刻，不能拿到则输出可以拿到的价值最高的牌，什么牌都拿不到（打铁）输出 。

思路

模拟即可。注意不要打错单词。

对于最后价值最高的牌的记录，不妨用 “类型” “奖牌” 的方式存，方便一点（（

时间复杂度：

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;

void solve(){
    int n;
    cin >> n;
    vector<vector<int> > cnt(6, vector<int>(3));
    map<string, int> mp;
    mp["LowerLevelProgrammingCompetition"] = 0;
    mp["SchoolCompetition"] = 1;
    mp["ProvincialCompetition"] = 2;
    mp["Regional"] = 3;
    mp["ECfinal"] = 4;
    mp["WF"] = 5;
    mp["Cu"] = 0;
    mp["Ag"] = 1;
    mp["Au"] = 2;
    mp["Fe"] = -1;
    int hi = -1;
    int time = -1;
    for(int i=0;i<n;i++){
        string s, a;
        cin >> s >> a;
        int id = mp[s], what = mp[a];
        if(what == -1) continue;
        cnt[id][what] ++;
        if(id == 5 && what == 2 && time == -1) time = i + 1; 
        hi = max(hi, id * 10 + what);
        if(cnt[id][what] == 3){
            cnt[id][what] = 0;
            if(what == 2) {
                if(id < 5){
                    cnt[id + 1][0] ++;
                    hi = max(hi, (id + 1) * 10);
                }else{
                    if(time == -1) time = i + 1;
                }
            }
            else if(what < 2) {
                cnt[id][what + 1] ++;
                hi = max(hi, id * 10 + what + 1);
                if(id == 5 && what + 1 == 2 && time == -1) time = i + 1;
            }
        }
    }
    if(time != -1) cout << time << '\n';
    else if(hi != -1){
        int id = hi / 10, what = hi % 10;
        string ans; //懒得再写一个map了，累
        if(id == 0) ans = "LowerLevelProgrammingCompetition";
        else if(id == 1) ans = "SchoolCompetition";
        else if(id == 2) ans = "ProvincialCompetition";
        else if(id == 3) ans = "Regional";
        else if(id == 4) ans = "ECfinal";
        else ans = "WF";
        cout << ans << ' ';
        if(what == 0) ans = "Cu";
        else if(what == 1) ans = "Ag";
        else ans = "Au";
        cout << ans << '\n';
     }else cout << -1 << '\n';
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t --) solve();
}

Ag == Au