写在前面

补题时间比较晚，摆烂了一段时间。。。
我的第一场 XCPC 之旅，前往广西师范大学（哈哈我的梦中情校）
第一次坐京✌列车，好高级呜呜呜

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

比赛过程

本人因经验较少，充当读题的角色（也算躺了），提供几个题目的思路。
L题 Loong 一开始因为没有读题完整，导致L题 WA一次 ,给队友增加罚时 , 原因是要查找输入$N$年之后的龙年，读成$N$年最近的龙年(包括前后的最近)

接下来做的是 B 题 Black Friday，相较于 L题较为简单，一样是签到题，所以是一次过了。这里就不多说了。
再下来是E题Epsilon Estuary，我和另外一个队友读题，发现一样是模拟+贪心，只需要逮着血量最大的史莱姆模拟操作即可，但是在编写代码中，while的判断条件写成了 while(health) ，这样会导致 health < 0 导致无限循环，然后不出意外的 TLE 了，为下图中的 while(big) 处

接下来做F题 Farewell GXCPC 时，我和队友读题发现有点类似背包问题，可能是没有注意到数据量，在每次处理数据的时候，都进行一次dp操作，导致了TLE，后来提出在操作用例前进行dp操作，读取区间即可。但是还是 WA了5次
J 题Judge System with Random 可能是本场比赛的转折点了，到这就断层了（），罚时如果少，且A了这一题，可以拿到银牌了（），也许是我第一次参加这个比赛，不知道这个罚时的规则，看了多次的题目都没有看懂这个题。但是只有队长看懂了。他是选择了二分，当时我没有反应过来（哭了）。用二分查找那个边界，拿到二分的有边界 $r$ ，则可以得到答案，但是因为卡了一小时也没再看题目，也许是少了 $pow(2,n+m) % mod$，导致一直WA，这就是队长当时了思路（估计）。下次还是得多看题目，不能因为搞懂大概题意就一直做题，要适当的回归题目本身。
然后就一直在试J题，直到比赛结束（）,然后大败而归

结果

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

奖牌

补题时间

L Loong

大概思路就是，先打表通过 2024 年 $-12$ or $+12$标记龙年，在用循环访问数组直到数组数值为龙年，输出$i$的位置即可，代码就直接用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=\frac{p_i-q_i}{p_i}$ 。

如果 $rate \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

每次攻击 $n$个史莱姆，每个史莱姆会分裂出 $\left \lfloor \frac{x}{2} \right \rfloor$和 $\left \lceil \frac{x}{2} \right \rceil$，我们每次选择最大血量的史莱姆攻击即可，累加攻击次数，即可得到结果，时间复杂度为 $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

还没学到，以后再补充吧（）