个人题解,有疏漏望指出(

有些题废话比较多(

丢一个个人博客.link


Contestant. Rank 2. Solved 4/8.

A. ACM? 你也想打ACM?

题意

对于 nn 道题,给定 kk 个提交记录,规定罚时为 2020 分钟,按照 ACM/ICPCACM/ICPC 赛制计算通过题数和总用时。

思路

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

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

对于下面的 ACAC 代码,其中 okiok_i 表示当前是否过了 ii 题;aia_i 表示第 ii 道题最早是在 aia_i 时刻通过的;pip_i 表示第 ii 道题在通过前 WAWA 了几次。

最后,我们遍历所有题,如果过题了,记录过题数,并将总用时加上 ai+20pia_i + 20p_i

时间复杂度:O(nk)O(nk)

本题测试点数据量过大,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 {
        private BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        private StringTokenizer tokenizer = new StringTokenizer("");
        private BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        private String innerNextLine() {
            try {
                return reader.readLine();
            } catch (IOException ex) {
                return null;
            }
        }

        public boolean hasNext() {
            while (!tokenizer.hasMoreTokens()) {
                String nextLine = innerNextLine();
                if (nextLine == null) {
                    return false;
                }
                tokenizer = new StringTokenizer(nextLine);
            }
            return true;
        }

        public String nextLine() {
            tokenizer = new StringTokenizer("");
            return innerNextLine();
        }

        public String next() {
            hasNext();
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public BigInteger nextBigInt() {
            return new BigInteger(next());
        }

        public void print(Object object) throws IOException {
            writer.write(object.toString());
        }

        public void println() throws IOException {
            writer.write(System.lineSeparator());
        }

        public void println(Object object) throws IOException {
            writer.write(object.toString());
            writer.write(System.lineSeparator());
        }

        @Override
        public void close() throws IOException {
            writer.close();
        }
    }
}

java挂掉后果断切cpp,淦

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

题意

给定一个满二叉树,满足根节点为 11,节点 xx 的子节点为 2x,2x+12x, 2x + 1

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

  1. 1 x1\ x,输出 xx 节点到其他被标记节点的最短距离总和;
  2. 2 x2\ x,标记 xx 节点;
  3. 3 x3\ x,取消标记 xx 节点。

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

思路

一些废话

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

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

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

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

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

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

具体思路

计算

首先,我们先来考虑怎么计算:

我们不妨从查询点 xx 开始向上遍历,并记录当前走了 stst 步。遍历时,我们传递一下当前遍历到的父节点 pp 是由哪个子树来的,这个参数和 xx 的奇偶性有关。这样的话,我们就可以得到另一个子树中所有被标记点到 pp 的距离和 sumsum,以及被标记的节点数 cntcnt。至于这个 sumsum 如何计算,画个图易得,xxpp 这段路被反复经过了 cntcnt 次,经过这个跳板后,剩余距离的总和就是 tottot,因此,以 pp 为跳板,我们可以得到贡献 sum=tot+cnt×stsum = tot + cnt \times st

上述过程对于 pxp \neq x 的情况是成立的,而 p=xp = x 时,两个子树的值我们都需要考虑(传参时,我们不妨传递一个特殊值,如 1-1),具体的贡献计算方式和上面一致。

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

预处理

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

同样,在遍历的时候,我们记录步数 stst,并传递 pp 是由哪个子树来的,然后将 pp 对应子树的 sumsum 加上 ststcntcnt 加上 11

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

时间复杂度:反正挺复杂

对应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长的最好看!

题意

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

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

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

给定 qq 个询问,对于给定的 kk,输出第 kk 个排列。

思路

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

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

唯一麻烦的是码量。

时间复杂度:O(899!q)O(8 \cdot 9 \cdot 9! \cdot q)

对应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. 微积分?低程竟然有微积分?

题意

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

输出它的积分。

思路

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

化简很简单,除以 gcdgcd 即可。

系数 11 不做过多解释,自行体会(

时间复杂度:O(n)O(n)乘上点常数

对应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!

题意

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

思路

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

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

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

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

我们来考虑任意两个字符串 si,sjs_i, s_j,如果 si+sj<sj+sis_i + s_j < s_j + s_i,那么很显然,前者的字典序更小。

那么,如果有三个呢?如果 sj+sk<sk+sjs_j + s_k < s_k + s_j,那么依然是前者的字典序更小。此时,我们联立起两个式子,会发现有趣的事情:si+sk<sk+sis_i + s_k < s_k + s_i

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

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

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

4 3
bbaba
bba
b
b

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

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

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

时间复杂度:O(n2)O(n ^ 2)

对应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?

题意

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

定义三个相同的牌可以合成一个等级更高的牌,输出拿到 WFWF 的金牌的最早时刻,不能拿到则输出可以拿到的价值最高的牌,什么牌都拿不到(打铁)输出 1-1

思路

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

对于最后价值最高的牌的记录,不妨用 "类型" ×10+\times 10 + "奖牌" 的方式存,方便一点((

时间复杂度:O(n)O(n)

#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

1 comments

  • @ 2023-3-23 0:17:53

    O神带带~

    • 1