Dytechlab Cup 2022 (A - C)

A - Ela Sorting Books

分析：贪心，将字符串每一位都存在map里，从前往后尽量让每一个\(n / k\)的段\(mex\)值尽量大，模拟mex即可。

void solve(){
    int n,k;
    cin >> n >> k;
    string s;
    cin >> s;
    map<char,int> mp;
    int d =  n / k;
    set<char> st;
    for (int i =0;i < n;i++) {
        mp[s[i]]++;
    }
    while(k--){
        bool  f = false;
        for (int j = 0; j < d;j ++) {
            if(mp['a' + j] > 0) {
                mp['a' + j]--;
            }
            else {
                f =  true;
                cout << char ('a' + j);
                break;
            }
        }
        if(!f) cout << char('a' + d);
    }
    cout << endl;
}

B - Ela's Fitness and the Luxury Number

分析:我自己也不太会证qwq，大概思路就是，因为这题数据量很大，可以肯定是\(O(1)\)计算无疑了，打表猜公式即可。

int rcl(int x) {
    int d = sqrt(x);
    int res = (int)(sqrt(x) - 1);
    res *= 3;
    int now = d * d;
    while(now <= x){
        now += d;
        res++;
    }
    return res;
}
void solve(){
    int l,r;
    cin >> l >> r;
    int ans1 = rcl(r);
    int ans2 = rcl(l);
    int q = 0;
    if(l % (int)(sqrt(l)) == 0)q++;
    cout << ans1 - ans2 + q<< endl;

}

C - Ela and Crickets

分析：画图模拟，很容易可以看出，以开始的点画十字，是可以跳到的位子，如何判断是否在十字内呢，只要目标点和出发的中心 \(x\)或\(y\)满足有一个绝对差是偶数倍即可。

还需要考虑边界情况，如果出发的中心在棋盘的四个角，那只能是一条横着的直线和竖着的直线了。

void solve(){
    int n;
    cin >> n;
    PII cp[5];
    for (int i = 1;i <= 3;i++) {
        cin >> cp[i].first >> cp[i].second;
    }
    int ax,ay;
    cin >> ax >> ay;
    sort(cp+1,cp+3);
    map<int,int> mp1;
    map<int,int> mp2;
    int tagx;
    int tagy;
    for (int i = 1;i <= 3;i ++) {
        mp1[cp[i].first]++;
        mp2[cp[i].second]++;
        if(mp1[cp[i].first] == 2) tagx = cp[i].first;
        if(mp2[cp[i].second] == 2) tagy = cp[i].second;
    }
    if((tagx == 1 && tagy == 1) || (tagx == n && tagy == 1) || (tagx == 1 && tagy == n) || (tagx == n && tagy == n)) {
        if(tagx == ax || tagy == ay) {
            cout << "YES" << endl;
            return ;
        }
        else {
            cout << "NO" << endl;
            return ;
        }
    }
    else {
        if(abs(ax - tagx) % 2 == 0 || abs(tagy - ay) % 2 == 0 ) {
            cout <<"YES" << endl;
            return ;
        }
        else {
            cout <<"NO" << endl;
            return ;
        }
    }

}