题解 | #小红的点构造#

A.小红的点构造

满足要求的最近B点一定在A点1步范围内,A点四周取任意一点即可

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
void solve(){
    int x,y;cin>>x>>y;
    auto isok=[&](int X,int Y) ->bool {
        if(x<0&&X>=0) return false;
        if(x>0&&X<=0) return false;
        if(y>0&&Y<=0) return false;
        if(y<0&&Y>=0) return false;
        return true;
    };
    for(int i=0;i<4;i++){
        int fx=x,fy=y;
        if(i==0) fx++;
        else if(i==1) fx--;
        else if(i==2) fy++;
        else if(i==3) fy--;
        if(isok(fx,fy)) {
            cout<<fx<<" "<<fy<<endl;
            return;
        }
    }
    cout<<1<<' '<<1<<endl;
}
int main(){
    cin.tie(0)->ios::sync_with_stdio(false);
    int T=1;cin>>T;
    while(T--) solve();
    return 0;
}

B.小红的数组重排

假设 $a_{i} - i =a_ {j} - j$ 条件成立,则必定有 $a_i < a_j$ ,打破这种规则只需使得结果保证非升序即可

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
void solve(){
    int n;cin>>n;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a.begin()+1,a.end(),greater<int>());
    for(int i=1;i<=n;i++) cout<<a[i]<<' ';
    cout<<endl;
}
int main(){
    cin.tie(0)->ios::sync_with_stdio(false);
    int T=1;cin>>T;
    while(T--) solve();
    return 0;
}

C.小红下象棋

先判断当前国王可行进的下一个位置有没有都被马卡死，如果没有，输出'C'.

再判断当前国王存在的位置有没有倍任意一个马卡死，如果有输出'B'. 否则输出'A'.

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
int x_[8]={0,1,0,-1,1,-1,1,-1};
int y_[8]={1,0,-1,0,1,1,-1,-1};
int _x[8]={1,2,1,2,-1,-2,-1,-2};
int _y[8]={2,1,-2,-1,2,1,-2,-1};
void solve(){
    int x,y,n;cin>>x>>y>>n;
    set<pair<int,int>>st;
    for(int i=1;i<=n;i++){
        int x,y;cin>>x>>y;
        st.emplace(x,y);
        for(int i=0;i<8;i++){
            int fx=x+_x[i],fy=y+_y[i];//马一步能走到的位置
            st.emplace(fx,fy);
        }
    }
    bool f=true;
    for(int i=0;i<8;i++){
        int fx=x+x_[i],fy=y+y_[i];
        f&=(bool)st.count({fx,fy});
    }
    if(f){
        if(st.count({x,y})) cout<<"B"<<endl;
        else cout<<"A"<<endl;
    }
    else{
        cout<<"C"<<endl;
    }
}
int main(){
    cin.tie(0)->ios::sync_with_stdio(false);
    int T=1;cin>>T;
    while(T--) solve();
    return 0;
}

D.小红的区间查询

首先[l,r]区间中的合法答案通过差分操作转化为[0,r]-[0,l-1]中两端的答案差, 然后考虑[0,x]中答案如何计算,对于 $0\leq i \leq x$ 中满足 $(i-b)|(i-a)$ 等价于满足 $(i-b)|(a-b)$ . 因为有 $\dfrac{i-a}{i-b}=\dfrac{i-b+b-a}{i-b}=1+\dfrac{b-a}{i-b}$ 这样就转化为了统计(b-a)的因数中所有在[0,x-b]范围内的数字个数,可以用简单的筛,也可以不使用筛暴力出因子数. 时间复杂度 $O(n\lg n)$ 瓶颈在预处理因数.

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
vector<vector<int>>fac;
void Init(int n){
    fac.resize(n+1);
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j+=i){
            fac[j].push_back(i);
        }
    }
}//预处理出所有数的因数
void solve(){
    ll a,b;cin>>a>>b;
    ll l,r;cin>>l>>r;
    auto calc=[&](ll x) ->ll {
        int cnt=0;
        for(int p:fac[b-a]){
            cnt+=(p+b<=x);
        }
        return cnt;
    };
    cout<<calc(r)-calc(l-1)<<endl;
}
int main(){
    cin.tie(0)->ios::sync_with_stdio(false);
    int T=1;cin>>T;
    Init(2e5+5);
    while(T--) solve();
    return 0;
}

E.小红的gcd

数据很小,考虑计数dp,分成三段更新,注意三段必须保证都要出现并且

当当前字母是每一段内部数字可以仅与之前相同字母衔接，

当当前字母是每一段结束字母时，尽可以与之前不同字母衔接，

当 $((i+j-2) mod (2 \times {n}-1)\neq 0)$ 时

$dp_{i,j}+=dp_{i-1,j} (a_{i,j}=a_{i-1,j})$

$dp_{i,j}+=dp_{i-1,j} (a_{i,j}=a_{i,j-1})$

当 $((i+j-2) mod (2 \times {n}-1) = 0)$ 时

$dp_{i,j}+=dp_{i-1,j} (a_{i,j} \neq a_{i-1,j})$

$dp_{i,j}+=dp_{i-1,j} (a_{i,j} \neq a_{i,j-1})$ 还有一个约束：三种不同的字符都要出现，

相邻不同满足还不够，可能有gggcccggg的情况没排除

因此考虑增加一维需要二进制掩码保存已选择的字符

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const ll mod=998244353;
void solve(){
    int n;cin>>n;
    vector<vector<char>>a(n+1,vector<char>(n+1));

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++) cin>>a[i][j];
    }

    auto calc=[&](char c) ->int {
        if(c=='c') return 1;
        if(c=='g') return 2;
        if(c=='d') return 4;
        return 0;
    };//二进制标记已选择数字
    vector dp(n+1,vector (n+1,vector<ll>(8)));

    dp[1][1][calc(a[1][1])]=1;
    int T=2*n-1;
    T/=3;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int t=i+j-1;
            int c=(calc(a[i][j]));
            for(int S=0;S<8;S++){//枚举前一位选数状态集合
                if(i-1>=1){
                    int nxt=(S|c);
                    if((t-1)%T==0){
                        if(a[i][j]!=a[i-1][j]&&(S&c)==0) {
                            dp[i][j][nxt]+=dp[i-1][j][S];
                            dp[i][j][nxt]%=mod;
                        } 
                    }
                    else{
                        if(a[i][j]==a[i-1][j]&&(S&c)!=0) {
                            dp[i][j][nxt]+=dp[i-1][j][S];
                            dp[i][j][nxt]%=mod;
                        } 
                    }
                }
                if(j-1>=1){
                    int nxt=(S|c);
                    if((t-1)%T==0){
                        if(a[i][j]!=a[i][j-1]&&(S&c)==0) {
                            dp[i][j][nxt]+=dp[i][j-1][S];
                            dp[i][j][nxt]%=mod;
                        } 
                    }
                    else{
                        if(a[i][j]==a[i][j-1]&&(S&c)!=0) {
                            dp[i][j][nxt]+=dp[i][j-1][S];
                            dp[i][j][nxt]%=mod;
                        } 
                    }
                }
            }
        }
    }
    cout<<dp[n][n][7]<<endl;
}
int main(){
    cin.tie(0)->ios::sync_with_stdio(false);
    int T=1;cin>>T;
    while(T--) solve();
    return 0;
}

Upd: 原本的E被hack了... 新的代码已启用对拍与佬的代码Aging1986拍了半小时没问题

牛魔，又是被D卡死的一天.