Mobile wallpaper 1
Profile Image of the Author
0x0AB8
标签
1543 字
8 分钟
GXCPC-2024-游记
2024-09-03
游记
游记

写在前面#

  • 补题时间比较晚，摆烂了一段时间。。。

  • 大一废物的我，第一场 XCPC 之旅，前往广西师范大学（哈哈 我的梦中情校）

1

由于是弱校，只有个铜牌，当做经验吧。

比赛过程#

  1. 本人因经验较少，充当读题的角色（也算躺了），提供几个题目的思路。

  2. L题 Loong 一开始因为没有读题完整，导致L题 WA一次 ,给队友增加罚时 , 原因是要查找 输入NN年之后的龙年，读成NN年最近的龙年(包括前后的最近)

2

  1. 接下来做的是 B 题 Black Friday，相较于 L题 较为简单，一样是签到题，所以是一次过了。这里就不多说了。

  2. 再下来是E题Epsilon Estuary，我和另外一个队友读题，发现一样是模拟+贪心，只需要逮着 血量最大的史莱姆 模拟操作即可，但是在编写代码中，while的判断条件写成了 while(health) ，这样会导致 health < 0 导致无限循环，然后不出意外的 TLE 了，为下图中的 while(big) 处

3

  1. 接下来做F题 Farewell GXCPC 时，我和队友读题发现有点类似背包问题，可能是没有注意到 数据量，在每次处理数据的时候，都进行一次dp操作，导致了TLE，后来提出在操作用例前进行dp操作，读取区间即可。但是还是 WA了5次

  2. J 题Judge System with Random 可能是本场比赛的转折点了，到这就断层了（），罚时如果少，且A了这一题，可以拿到银牌了（），也许是我第一次参加这个比赛，不知道这个罚时的规则，看了多次的题目都没有看懂这个题。但是只有队长看懂了。他是选择了二分，当时我没有反应过来（哭了）。用二分查找那个边界，拿到二分的有边界 rr ，则可以得到答案，但是因为卡了一小时也没再看题目，也许是少了 pow(2,n+m)pow(2,n+m) % mod，导致一直WA，这就是队长当时了思路（估计）。下次还是得多看题目，不能因为搞懂大概题意就一直做题，要适当的回归题目本身。

  3. 然后就一直在试J题，直到比赛结束（）,然后大败而归

结果#

  • 这里是比赛得到的气球呜呜呜（没把牌子拿回去）

4

  • 奖牌

5

补题时间#

L Loong#

大概思路就是，先打表通过 2024 年 −12-12 or +12+12标记龙年，在用循环访问数组直到数组数值为龙年，输出ii的位置即可，代码就直接用java写吧，后面基本都是用cpp写的代码。

import java.util.Scanner;


public class Main {


    public static void main(String[] args) {
        // 2024 loong
        int[] arr = new int[10006];
        int y = 2024;
        while (y <= 10004) {
            arr[y] = 1;
            y += 12;
        }
        y = 2024;
        while (y > 0) {
            arr[y] = 1;
            y -= 12;
        }


        Scanner sr = new Scanner(System.in);


        int idx = sr.nextInt() + 1;
        while (arr[idx] != 1) idx++;
        System.out.println(idx);
    }


}

B Black Friday#

大概题意就是，输入 a b两个数值 计算，Eva所能接受的打折的游戏，直接循环

计算每个游戏的 rate=pi−qipirate=\frac{p_i-q_i}{p_i} 。

如果 rate≥abrate \ge \frac{a}{b} 累加结果并输出即可

import java.io.IOException;
import java.io.StreamTokenizer;


public class Main {


    static StreamTokenizer st = new StreamTokenizer(System.in);


    static int nextInt() throws IOException{
        st.nextToken();
        return (int)st.nval;
    }


    public static void main(String[] args) throws IOException{
        // n games
        int n = nextInt();


        int a = nextInt();
        int b = nextInt();


        double accept = (double)a / b;


        long sum = 0;
        for (int i = 0; i < n; i++){
            int p = nextInt();
            int q = nextInt();
            double rate = (double)(p - q) / p;
            if (rate >= accept) {
                sum += q;
            }
        }
        System.out.println(sum);
    }
}

E Epsilon Estuary#

每次攻击 nn个史莱姆，每个史莱姆会分裂出 ⌊x2⌋\left \lfloor \frac{x}{2} \right \rfloor和 ⌈x2⌉\left \lceil \frac{x}{2} \right \rceil，我们每次选择最大血量的史莱姆攻击即可，累加攻击次数，即可得到结果，时间复杂度为 O(nlogn)O(n logn)

#include <bits/stdc++.h>


using namespace std;


#define ll long long


void solve(){
    int n;
    ll y; // y is dameage


    cin >> n >> y;


    ll big = 0;
    for(int i =0;i<n;i++){
        ll v;
        cin >> v;
        if(v > big) big = v;
    }


    ll cnt = 0;
    while (big > 0){
        big = big - y;
        big = ceil(big / 2.0);
        cnt++;
    }


    cout << cnt << "\n";
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);


    int t;
    cin >> t;
    while(t--) solve();
    return 0;
}

F FareWell GXCPC#

很明显是一个背包的问题，建立dp表，把5000内的情况全部考虑，再预处理区间的最大值，最后输出结果就可以了

#include <bits/stdc++.h>


using namespace std;


const int MAXN = 5e3;


int n,q;


int main(){
    cin >> n >> q;


    vector<int> dp(MAXN+1,-0x3f3f3f);
    dp[0] = 0;
    // 建立dp表，把5000内的情况全部考虑
    for(int i = 0;i<n;i++){
        int d,f;
        cin >> d >> f;
        for(int j = MAXN;j>=d;j--) dp[j] = max(dp[j],dp[j-d]+f);
    }


    // 遍历全部区间，找到最大的
    vector<vector<int>> res(MAXN+1,vector<int>(MAXN+1,-1));
    // cache data
    for(int i = 1 ;i<=MAXN;i++)
        for(int j = i ;j<=MAXN;j++)
            res[i][j] = max(res[i][j-1],dp[j]);


    // 输出区间
    while(q--) {
        int l ,r;
        cin >> l >> r;


        cout << res[l][r] << endl;
    }


    return 0;
}

J Judge System with Random#

  • 大概题意是： Colin 和 Eva 对比罚时，谁小谁赢，输入的时候对数据进行处理

  • for(int i =0;i<n;i++) cin >> x[i]; x[i] += 20 * i;

  • i为0的时候就是第一次提交成功，往下就是提交失败的，加上罚时，不难发现 提交的时间是 单调上升的，那么说明结果也是同样的，会存在一个边界，找到那个边界的 右 r ，带入 pow(2, r)，使用快速幂即可计算得到结果

#include <bits/stdc++.h>


using namespace std;


#define ll long long


const int N = 1e5 + 1;


vector<int> x(N,0);
vector<int> y(N+1,0);


int n,m;


ll qpow(ll a, ll b, ll m) {
  a %= m;
  ll res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return res;
}


bool cmp(const int& x, const int& y){
  return x <= y;
}


const int mod= 998244353;


int main(){
    cin >> n >> m;


    for(int i =0;i<n;i++){
        cin >> x[i];
        x[i] += 20 * i;
    }


    for (int i = 0; i < m; i++){
        cin >> y[i];
        y[i] += 20 * i;
    }
    y[m] = 1e9;
    ll ans = 0;
    for(int i = n-1;i>=0;i--) {
        auto it = upper_bound(y.begin(),y.begin() + m,x[i],cmp);


        int j = distance(y.begin(),it);


        //cout << i << " " << j << endl;


        ans += qpow(2,(n - i) + (m - j - 1) ,mod);
        ans %= mod;
    }


    cout << ans;


    return 0;
}

D Dune#

  • 太菜了，还是不会喵（）
GXCPC-2024-游记
https://blog.cutebaka.cloud/posts/7thgxcpc/
作者
0x0AB8
发布于
2024-09-03
许可协议
CC BY-NC-SA 4.0

部分信息可能已经过时

校园网不断网方案
SecurityManager魔法
你好笨啊喵
© 2025 0x0AB8. All Rights Reserved. / RSS / Atom / Sitemap
Powered by Astro & Mizuki  Version 7.6.5