小白月赛 131 题解

A. 小红的7

知识点：数学、模拟、字符串

预估难度：800

，，以此类推，我们发现每个 对应的循环节的首位数字是完全不同的。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int _;cin>>_;
    while(_--){
        string s;cin>>s;
        if(s[0]=='1')cout<<1<<"\n";
        else if(s[0]=='2')cout<<2<<"\n";
        else if(s[0]=='4')cout<<3<<"\n";
        else if(s[0]=='5')cout<<4<<"\n";
        else if(s[0]=='7')cout<<5<<"\n";
        else if(s[0]=='8')cout<<6<<"\n";
    }
}

B. 小红的回文串

知识点：贪心、字符串、回文串

预估难度：1100

原串已经是回文串，如果想要删除字符后依然是回文串，我们必须且只能删除位于回文串正中心的那些连续相同的字符。

为什么呢？因为一旦删去偏离中心的字符，左右两边对应的对称点必然会发生错位，导致新串不再回文。所以我们只需找到原串最中间的字符块，统计其中有多少个字符与正中心字符相同即可，有多少个就有多少种删除方案。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int _;cin>>_;
    while(_--){
        int n,i,ans=0;
        string s;
        cin>>n>>s;
        if(n%2==1){
            ans=1;
            for(i=n/2-1;i>=0;i--){
                if(s[i]==s[n/2])ans+=2;
                else break;
            }
        }else{
            if(s[n/2-1]==s[n/2]){
                ans=2;
                for(i=n/2-2;i>=0;i--){
                    if(s[i]==s[n/2])ans+=2;
                    else break;
                }
            }
        }
        cout<<ans<<"\n";
    }
}

C. 小红的gcd位运算构造

知识点：位运算、构造、数论

预估难度：1000

要求 ，最容易想到的互质数对自然是包含 或者某个不被 整除的质数的次幂。

如果 是偶数，那么它的二进制第 位必然是 ，我们直接令 即可，显然 且 。

如果 是奇数，那么 不能被 整除，即 不包含因子 。我们只需要找到 二进制中最低位的 （设在第 位），令 即可。由于 是 的次幂，而 是奇数，二者必然互质；同时 的第 位为 ，自然有 。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int _;cin>>_;
    while(_--){
        int x,y=1;
        cin>>x;
        while((x&y)!=0)y<<=1;
        cout<<y<<"\n";
    }
}

D. i在西元前

知识点：数学、复数、模拟

预估难度：1400

判定等比数列的核心是存在一个公比 使得 。利用等比数列的性质将其转化为交叉相乘：。题目保证了元素不为 （），因此这完全等价于判断相邻两项的商是否与前两项的商一致。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[202020][2];
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int _;cin>>_;
    while(_--){
        int n,i,ok=1;
        cin>>n;
        for(i=0;i<n;i++)cin>>a[i][0]>>a[i][1];
        for(i=1;i<n-1;i++){
            int r1=a[i+1][0]*a[0][0]-a[i+1][1]*a[0][1];
            int i1=a[i+1][0]*a[0][1]+a[i+1][1]*a[0][0];
            int r2=a[i][0]*a[1][0]-a[i][1]*a[1][1];
            int i2=a[i][0]*a[1][1]+a[i][1]*a[1][0];
            if(r1!=r2||i1!=i2){ok=0;break;}
        }
        if(ok)cout<<"Yes\n";
        else cout<<"No\n";
    }
}

E. 小红打游戏

知识点：动态规划、背包问题、混合背包

预估难度：1500

把这两类关卡分开处理。既然普通关卡（后 个）的选取没有次数限制，我们可以先用一个标准的二维完全背包（正向遍历容量），求出仅使用普通关卡时获取资源的最小花费。

处理完普通关卡后，我们再去处理限定关卡。由于限定关卡每关至多使用一次，所以用标准的二维 01 背包（逆向遍历容量）去在这个已经包含普通关卡的基础 DP 数组上继续转移。注意这里的容量可以对 和 取 ，因为溢出的部分也可以等效认为是满足了目标。全部算完后查 即可。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[10101],b[10101],c[10101];
int dp[1010][1010];
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int _;cin>>_;
    while(_--){
        int n,k,x,y,i,cx,cy,ans=1e18;
        cin>>n>>k>>x>>y;
        for(i=1;i<=n;i++)cin>>a[i]>>b[i]>>c[i];
        for(cx=0;cx<=x;cx++)for(cy=0;cy<=y;cy++)dp[cx][cy]=1e18;
        dp[0][0]=0;
        // 普通关卡（完全背包，正向遍历）
        for(i=k+1;i<=n;i++){
            for(cx=0;cx<=x;cx++){
                for(cy=0;cy<=y;cy++){
                    if(dp[cx][cy]==1e18)continue;
                    int nx=min(x,cx+a[i]);
                    int ny=min(y,cy+b[i]);
                    dp[nx][ny]=min(dp[nx][ny],dp[cx][cy]+c[i]);
                }
            }
        }
        // 限定关卡（01背包，逆向遍历）
        for(i=1;i<=k;i++){
            for(cx=x;cx>=0;cx--){
                for(cy=y;cy>=0;cy--){
                    if(dp[cx][cy]==1e18)continue;
                    int nx=min(x,cx+a[i]);
                    int ny=min(y,cy+b[i]);
                    dp[nx][ny]=min(dp[nx][ny],dp[cx][cy]+c[i]);
                }
            }
        }
        ans=dp[x][y];
        if(ans==1e18)cout<<-1<<"\n";
        else cout<<ans<<"\n";
    }
}

F. 小红的等比数列

知识点：数学、构造、分类讨论

预估难度：2300

由于原数组全为整数，且插入的元素也必须为整数，等比数列的公比 必然是一个有理数 。

等比数列的一个重要性质是：由于公比的绝对值必然 或 ，所以如果我们直接对整个数组按绝对值排序，那么排序后的序列必然已经排好了等比的先后顺序。

因此我们首先将数组按照绝对值进行排序。排序后，合法的等比数列必然满足处处都有 。

特判 的情况：要么在两端延长（ 或 ），要么在中间插入（前提是 且存在整数平方根）。

特判所有元素绝对值相同的情况：此时公比必然是 或 。只需统计正数和负数的个数，看是否能通过插入一个数满足全同（公比 ）或正负交替（公比 ）。

对于一般情况，我们扫一遍排序后的数组，找到第一个不满足 的位置 。如果找不到这样的 ，说明原序列已经是一个完整的等比数列，我们只需尝试在首部或尾部追加一个合法整数即可。

如果找到了 ，说明“缺失的那个元素”必然在 附近。我们只需要利用 附近（如 等）依然保持着等比关系的元素，推算出缺失的元素 （例如 等），然后将 插入到序列中，再用 的时间全局 check 一遍 是否全部成立即可。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,a[202020],b[202020];
bool cmp(int x,int y){return abs(x)<abs(y);}
bool go(int k,int x){
    int i;
    for(i=0;i<k;i++)b[i]=a[i];
    b[k]=x;
    for(i=k;i<n;i++)b[i+1]=a[i];
    for(i=1;i<n;i++)if(b[i]*b[i]!=b[i-1]*b[i+1])return 0;
    cout<<"Yes\n";
    for(i=0;i<=n;i++)cout<<b[i]<<" ";
    cout<<"\n";
    return 1;
}
void solve(){
    int i,j,k,x,y;
    cin>>n;
    for(i=0;i<n;i++)cin>>a[i];
    sort(a,a+n,cmp);
    if(n==1){
        cout<<"Yes\n"<<a[0]<<" "<<a[0]<<"\n";
        return;
    }
    if(n==2){
        if(a[1]*a[1]%a[0]==0){
            cout<<"Yes\n"<<a[0]<<" "<<a[1]<<" "<<a[1]*a[1]/a[0]<<"\n";
            return;
        }
        if(a[0]*a[0]%a[1]==0){
            cout<<"Yes\n"<<a[0]*a[0]/a[1]<<" "<<a[0]<<" "<<a[1]<<"\n";
            return;
        }
        if(a[0]*a[1]>0){
            x=round(sqrt(a[0]*a[1]));
            for(k=max(0LL,x-2);k<=x+2;k++){
                if(k*k==a[0]*a[1]){
                    cout<<"Yes\n"<<a[0]<<" "<<k<<" "<<a[1]<<"\n";
                    return;
                }
            }
        }
        cout<<"No\n";
        return;
    }
    if(abs(a[0])==abs(a[n-1])){
        int v=abs(a[0]),m=n+1,p=0,q=0;
        for(i=0;i<n;i++)if(a[i]>0)p++;else q++;
        if(!q){
            cout<<"Yes\n";
            for(i=0;i<m;i++)cout<<v<<" ";
            cout<<"\n";
            return;
        }
        if(!p){
            cout<<"Yes\n";
            for(i=0;i<m;i++)cout<<-v<<" ";
            cout<<"\n";
            return;
        }
        for(int d:{v,-v}){
            int p2=p+(d>0),q2=q+(d<0);
            if(p2==(m+1)/2&&q2==m/2){
                cout<<"Yes\n";
                for(i=0;i<m;i++)cout<<(i%2?-v:v)<<" ";
                cout<<"\n";
                return;
            }
            if(q2==(m+1)/2&&p2==m/2){
                cout<<"Yes\n";
                for(i=0;i<m;i++)cout<<(i%2?v:-v)<<" ";
                cout<<"\n";
                return;
            }
        }
        cout<<"No\n";return;
    }
    int t=-1;
    for(i=1;i<n-1;i++){
        if(a[i]*a[i]!=a[i-1]*a[i+1]){
            t=i;
            break;
        }
    }
    if(t==-1){
        if(a[1]&&a[0]*a[0]%a[1]==0&&go(0,a[0]*a[0]/a[1]))return;
        if(a[n-2]&&a[n-1]*a[n-1]%a[n-2]==0&&go(n,a[n-1]*a[n-1]/a[n-2]))return;
    }else{
        if(t>=2&&a[t-2]&&a[t-1]*a[t-1]%a[t-2]==0){
            if(go(t,a[t-1]*a[t-1]/a[t-2]))return;
        }
        if(t+1<n&&a[t+1]&&a[t]*a[t]%a[t+1]==0){
            if(go(t,a[t]*a[t]/a[t+1]))return;
        }
        if(t>=1&&a[t-1]&&a[t]*a[t]%a[t-1]==0){
            if(go(t+1,a[t]*a[t]/a[t-1]))return;
        }
        if(t+2<n&&a[t+2]&&a[t+1]*a[t+1]%a[t+2]==0){
            if(go(t+1,a[t+1]*a[t+1]/a[t+2]))return;
        }
    }
    cout<<"No\n";
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int _;cin>>_;
    while(_--)solve();
}