【LGR-161-Div.3】洛谷基础赛 #4 题解

Acoipp · 2023-09-27 18:40:11 · 题解

A-Judg. 题解

这是一道签到题，有 2 种方法通过。

其实题目就是要求输入长度为 n 的字符串序列，输出所有字符串不是 \texttt{AC} 的下标。

我们可以输入 char 数组，也可以通过 STL 里的 string 来处理，代码分别如下所示：

//char version
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,i;
char s[105];
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>(s+1);
        if(s[1]!='A'||s[2]!='C') cout<<i<<" ";
    }
    return 0;
}
//备注：Atcoder 的 C++20 不支持用 cin 像上面输入 char 字符串，必须用 scanf。 

//string version
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,i;
string s;
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>s;
        if(s!="AC") cout<<i<<" ";
    }
    return 0;
}

B-Maps. 题解

我们可以发现，字典序最小，要求这个字符串第一个为 1 的元素一定尽量靠后，那么我们可以从 1 枚举到 n，判断这个 1 放在哪里。

判断的时候呢，如果当前枚举到了 i，那么相当于只用 i+1 \sim n 的元素能不能满足题目的要求。

想一下我们就会发现最优的安排方式一定是形如 \texttt{1010101...101} 的形式，串长是偶数的情况，同理。

所以设串长为 n，那么满足题目所给的条件的格子的数量最多为 \lfloor \dfrac{n-1}{2}\rfloor。

那么这道题就判断出是否有解，有解的话枚举第一个 1 的位置，找到能够满足的最后的一个位置，然后剩下直接填 \texttt{101010...010101} 的形式即可。（事实上由于这道题的贪心性，其实最后一个数字总是为 1）

代码如下所示：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll T,n,p,i,j;
inline ll calc(ll x){
    return (x-1)/2;
}
int main(){
    cin>>T;
    while(T--){
        cin>>n>>p;
        if(calc(n)<p){
            cout<<"-1\n";
            continue;
        }
        for(i=1;i<=n;i++){
            if(calc(i)==p) break;
        }
        for(j=1;j<=n-i;j++) cout<<'0';
        for(j=1;j<=i;j++){
            if(j&1) cout<<'1';
            else cout<<'0';
        }
        cout<<endl;
    }
    return 0;
}

C-Colo. 题解

方便起见，以下讨论的颜色均为网格上出现过的颜色。

首先，如果我们保留了大于等于 2 种颜色，那么设这两个颜色出现过的最左边的下标和最右边的下标分别为 x_1,y_1 和 x_2,y_2，一定满足 y_1<x_2 或 y_2<x_1。

这样子的话，我们就可以愉快地背包 dp 了。

直接从左往右枚举每个网格，如果网格是当前颜色的最后出现的地方，设其下标为 i，再找到这个颜色最前出现的下标，设为 j，那么枚举所有 k<j 且 k 是某个颜色最后出现的地方，那个颜色的编号小于当前颜色的编号，那么就可以背包 dp 了。

具体来说，就是插入一个大小为当前颜色出现的次数，权重为当前颜色的权值的物品，最后对于所有不同的 k 的 dp 结果取一个 \max 即可。

下面是代码：

#include<bits/stdc++.h>
#define ll long long
#define N 505
using namespace std;
ll n,m,a[N],b[N],i,j,k,dp[N][N],la[N],en[N],vis[N],ans=-1;
int main(){
    memset(dp,-0x3f,sizeof(dp));
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(i=1;i<=n;i++){
        //记录第一个出现和最后一个出现的地方。 
        cin>>a[i],en[a[i]]=i,vis[a[i]]=1;
        if(!la[a[i]]) la[a[i]]=i;
    }
    for(i=1;i<=n;i++) cin>>b[i];
    //这里是先枚举颜色的编号，然后枚举下标，与上述描述功能相同。 
    for(i=1;i<=n;i++){
        if(vis[i]){ 
            for(j=1;j<la[i];j++){
                for(k=2;k<=m;k++){
                    //背包转移。 
                    dp[en[i]][k] = max(dp[en[i]][k],dp[j][k-1]+b[i]);
                }
            }
            //特判只选自己。 
            dp[en[i]][1] = b[i];
        }
    }
    for(i=1;i<=n;i++) ans=max(ans,dp[i][m]);
    cout<<ans<<endl;
    return 0;
}

D-Bina. 题解

我们可以发现，经过这样子构造成的二叉树，如果把它补成一个完全二叉树的话，那么每一层的编号从左到右都是连续的，而且相邻两层的编号也是连续的，类似于下面这个样子：

我们由可以发现 build(1,n,1) 这个函数构建出来的二叉树的形态只与前两个参数的差有关，并且含有比这个值多 1 个的叶子节点。

上图就是 build(1,4,1) 构造出来的二叉树，恰好含有 4-1+1=4 个叶子节点。

现在假设我们没有补全这棵二叉树，那么假设是 build(1,6,1)，构建出来的二叉树如下图所示：

多模拟几遍，我们就可以发现两个性质：

• 在执行 build(1,n,1) 函数的递归过程当中，所有 build(s,t,p) 中的不同的 t-s+1 的数量是 \log n 级别的。
• 所有构造出的二叉树一定只有最后一层缺少节点，其他层全部都是满的，设层数为 k（根节点层数为 0），则从左到右编号为 2^k \sim 2^{k+1}-1。

接下来就可以考虑解决这道题目了，显然，我们需要枚举我们选择的深度，深度只有 \log n。

然后我们需要快速知道这个比这个深度还深的节点的编号总和，我们可以考虑计数 dp。

因为当 t-s+1 相同时，构造的二叉树形态也相同，所以我们设 cnt_{i,j} 表示这样构造出来的二叉树（根节点编号为 1，即调用 build(1,t-s+1,1) 函数）的深度为 j（根节点深度为 0，与题目略有不同）的数的个数，dp_{i,j} 则表示编号之和，那么我们可以列出来这么两个方程：

设 l = \lfloor \frac{i+1}{2} \rfloor,r = \lfloor \frac{i}{2} \rfloor，这里 l 和 r 的意义是 i 的左子树的 t-s+1 的值，和 i 的右子树的 t-s+1 的值。（这里可以手算一下）

那么：

左子树的根节点编号从 1 变成 2 后，深度为 j 的所有节点的编号都要加一个 2^{j-1} 次方；右子树的根节点编号从 1 变成 3 后，右子树的所有节点都要加一个 2^j 次方，我们可以简单地推导出来，然后顺便记录左右子树某深度的节点个数就可以了。

最后就是 dp 的第一维值太大，但是个数很少怎么办？可以先把所有可能的值找出来，排序之后映射到下标即可。

（但是也可以只记录最后一层的元素，为了不让题目难度增加，我们这里就放过去了 O(T \log^2 n) 的做法）

下面是代码（代码中的深度都是题解中的深度加 1 之后得到的，所以会有些许不同）：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll T,n,m,p[105],tot,i,j,cnt1[105][105],cnt2[105][105],ans,ls,rs,sum,qmi[105],p1,p2,p3,p4;

int main(){
    ios::sync_with_stdio(false);
    qmi[0] = 1;
    for(i=1;i<=100;i++) qmi[i]=qmi[i-1]*2;
    cin>>T;
    while(T--){
        ans=-1;
        sum=0;
        tot=0;
        cin>>n>>m;
        //找到所有出现过的值 
        p1=n,p2=0;
        while(1){
            p[++tot] = p1;
            if(p2) p[++tot] = p2;
            if(p2==1) p2=0;
            if(p1==1) p1=0;
            if(!p1&&!p2) break;
            if(p1&&p2){
                p3 = LLONG_MIN,p4 = LLONG_MAX;
                if(p1%2!=0) p3=p1/2+1;
                else p3=p1/2;
                p4=p2/2;
                p1 = p3,p2 = p4;
            }
            else{
                if(p1%2!=0) p2=p1/2,p1=p1/2+1;
                else p1/=2;
            }
        }
        //排序之后映射到下标 
        sort(p+1,p+tot+1);
        tot = unique(p+1,p+tot+1)-p-1;
        //初始化：cnt1=题面中的cnt，cnt2=题面中的dp 
        for(i=1;i<=tot;i++){
            for(j=1;j<=tot;j++) cnt1[i][j]=cnt2[i][j]=0;
        }
        for(i=1;i<=tot;i++){
            if(p[i]==1){
                cnt1[i][1] = 1,cnt2[i][1] = 1;
                continue;
            }
            //找i的左子树和右子树的叶子数量 
            for(j=1;j<i;j++){
                if(p[j]==(p[i]+1)/2){
                    ls=j;
                    break;
                }
            }
            for(j=1;j<i;j++){
                if(p[j]==p[i]/2){
                    rs=j;
                    break;
                }
            }
            //进行dp转移，注意初始条件，深度为0的需要特判（下面的深度都从1开始，比题解中的多1） 
            cnt1[i][1] = 1,cnt2[i][1] = 1;
            for(j=2;j<=tot;j++){
                cnt1[i][j] = cnt1[ls][j-1]+cnt1[rs][j-1];
                cnt2[i][j] = cnt2[ls][j-1]+cnt2[rs][j-1]+cnt1[ls][j-1]*qmi[j-2]+cnt1[rs][j-1]*qmi[j-1];
            }
        }
        for(i=tot;i>=1;i--) cnt1[tot][i]+=cnt1[tot][i+1];
        //按照题面意思模拟即可 
        for(i=1;i<=tot;i++){
            if(!cnt1[tot][i]) break;
            sum += cnt2[tot][i];
            if(cnt1[tot][i+1]>=m) ans = max(ans,sum/i);
        }
        cout<<ans<<endl;
    }
    return 0;
}

下面是 dino 修改后的代码，会更简单明了一点（此处感谢 TA 指出题解中的不足）：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll T,n,m,p[105],tot,i,j,cnt1[105][105],cnt2[105][105],ans,ls,rs,sum,qmi[105],p1,p2,p3,p4;

int main(){
    ios::sync_with_stdio(false);
    qmi[0] = 1;
    for(i=1;i<=100;i++) qmi[i]=qmi[i-1]*2;
    cin>>T;
    while(T--){
        ans=-1;
        sum=0;
        tot=0;
        cin>>n>>m;
        int pp = n, p1, p2;
        int dep = 1;
        p[++tot] = n;
        while(pp){
            dep++;
            if(pp % 2 == 0){
                pp /= 2;
                p[++tot] = pp;
            }
            else{
                p1 = pp / 2;
                p2 = pp - p1; 
                p[++tot] = p1;
                p[++tot] = p2;
                if(p1 % 2 == 0) pp = p2;
                else pp = p1; 
            }
            if(pp == 1) break;
        }
        dep++;
        sort(p+1,p+tot+1);
        for(i=1;i<=tot;i++){
            for(j=1;j<=tot;j++) cnt1[i][j]=cnt2[i][j]=0;
        }
        for(i=1;i<=tot;i++){
            if(p[i]==1){
                cnt1[i][1] = 1,cnt2[i][1] = 1;
                continue;
            }
            for(j=1;j<i;j++){
                if(p[j]==(p[i]+1)/2){
                    ls=j;
                    break;
                }
            }
            for(j=1;j<i;j++){
                if(p[j]==p[i]/2){
                    rs=j;
                    break;
                }
            }
            cnt1[i][1] = 1,cnt2[i][1] = 1;
            for(j=2;j<=dep;j++){
                cnt1[i][j] = cnt1[ls][j-1]+cnt1[rs][j-1];
                cnt2[i][j] = cnt2[ls][j-1]+cnt2[rs][j-1]+cnt1[ls][j-1]*qmi[j-2]+cnt1[rs][j-1]*qmi[j-1];
            }
        }
        for(i=tot;i>=1;i--) cnt1[tot][i]+=cnt1[tot][i+1];
        for(i=1;i<=dep;i++){
            if(!cnt1[tot][i]) break;
            sum += cnt2[tot][i];
            if(cnt1[tot][i+1]>=m) ans = max(ans,sum/i);
        }
        cout<<ans<<endl;
    }
    return 0;
}