A.小红的点构造

显然 $(2 x, 2y)$ 满足题意。

void solve(){
    ll x = read(), y =  read();
    print(PLL{2*x,2*y});
}

B.小红的数组重排

显然把数组按降序排序后， $b_i = a _i - i$ 这个数组一定单调递减。

因为此时 $a_i$ 单调不增， $i$ 单调递增。

void solve(){
    ll n = read();
    vector<ll> a(n);
    for(ll i=0;i<n;i++) a[i] = read();
    sort(all(a), greater<ll>());
    print(a);
}

C.小红下象棋

开一个 $map$ 记录一下被马控制的点，按题意判断即可。

vector<PLL> d = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};
vector<PLL> d2 = {{1, 0},{1, 1}, {1, -1}, {0, 1},{0, -1},{-1, -1},{-1, 0},{-1, 1}};

void solve(){
    ll x = read(), y = read(), n = read();
    map<PLL, ll> memo;
    for(ll i=1;i<=n;i++){
        ll xx = read(), yy = read();
        for(auto [dx, dy]:d){
            memo[{xx+dx, yy+dy}]=1;
        }
    }
    ll f = 0;
    if(memo[{x, y}]){
        f |= 1;
    }
    ll cnt = 0;
    for(auto [dx, dy]:d2){
        cnt += memo[{x+dx,y+dy}];
    }
    if(cnt == 8){
        f |= 2;
    }
    if(f == 3){
        putchar('B');
    }
    else if(f == 2){
        putchar('A');
    }
    else{
        putchar('C');
    }
    putchar('\n');
}

D.小红的区间查询

由题意 $(x - b) | (x- a)$ ，则有 $(x-a) = k (x- b) (k \ge 1)$ ，整理得 $x = (kb - a)/(k-1) = b + (b-a)/(k-1)$ 。

因此我们可以遍历 $b-a$ 的所有因子，判断对应的 $x$ 是否在 $[l, r]$ 内即可。

void solve(){
    ll a = read(), b = read(), l = read(), r = read(), ans = 0;
    for(ll i=1;i*i<=b-a;i++){
        if((b-a)%i==0){
            ll t = b +(b-a)/i;
            if(l <= t && t <= r){
                ans++;
            }
            if(i*i!=(b-a)){
                ll t2 = b+ i;
                if(l <= t2 && t2 <= r){
                    ans++;
                }
            }
        }
    }
    print(ans);
}

E.小红的gcd

注意到开头和结尾已经固定。

因此只需要限制前 $\frac{1}{3}$ 步都走 $g_{1, 1}$ 相同字符，后 $\frac{1}{3}$ 步都走 $g_{n, n}$ 相同字符，中间走剩下那种即可。

ll g[1001][1001];
ll dp[1001][1001];
void solve(){
    ll n;cin>>n;
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=n;j++){
            char c;cin>>c;
            g[i][j] = (c=='c'?0:(c=='g'?1:2));
            dp[i][j] = 0;
        }
    }
    dp[1][1] = 1;
    ll mid = 3 - g[1][1] - g[n][n];
    ll t1 = (2*n-1)/3;
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=n;j++){
            if(i == 1 && j == 1) continue;
            ll d = (i-1)+(j-1);
            if(d < t1){
                if(g[i][j] != g[1][1]) continue;
                dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MOD;
            }
            else if(d < t1 * 2){
                if(g[i][j] != mid) continue;
                dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MOD;
            }
            else{
                if(g[i][j] != g[n][n]) continue;
                dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MOD;
            }
        }
    }
    cout<<dp[n][n]<<'\n';
    
}

F.小红的树构造

观察样例可以想到一种构造方案：示例图片

即中间一条链，除了链头外的节点的度都为 $k$ , 如果还有剩下的点，全部接到其中一个上面去。

遍历中间链的长度，找到一个可行的长度构造即可。

注意 $k=1$ 时，若 $n < 5$ 无解，否则构造一张图中有两个节点的度互质即可。

void solve(){
    ll n = read(), k = read();
    if(k == 1){
        if(n < 5){
            puts("No");
        }
        else{
            puts("Yes");
            puts("1 2");
            puts("1 3");
            puts("2 4");
            puts("2 5");
            for(ll i=6;i<=n;i++){
                print(PLL{i-1, i});
            }
        }
    }
    else if(k == n - 1){
        puts("Yes");
        for(ll i=2;i<=n;i++){
            print(PLL{1, i});
        }
    }
    else{
        for(ll num=3;num<=n;num++){
            ll left = (n-num);
            ll d = n-num-(num-2)*(k-2);
            if(!(d >= 0 && d%k == 0)){
                //判断能不能让链中所有点都补到度为 k，且剩余的点数量为 k 的倍数
                continue;
            }
            if(num == 3 && d > 0){
                // 长度为 3 时如果补点的话 gcd 会变化
                continue;
            }
            puts("Yes");
            for(ll i=1;i<num;i++){
                print(PLL{i, i+1});
            }
            ll idx = num + 1;
            for(ll i=2;i<num;i++){
                ll c = 0;
                while(c < k - 2){
                    print(PLL{i,idx});
                    idx++;c++;
                }
            }
            while(idx<=n){
                print(PLL{2,idx});
                idx++;
            }
            return;
        }
        puts("No");
    }
    
}

c++火车头