2022牛客寒假算法基础集训营3 签到题7题（附基础集训营1-3签到题总结）

1、A-智乃的Hello XXXX

• 签到

#include<bits/stdc++.h>
using namespace std;
int main(){
    cout<<"hello chino\n";
    return 0;
}

2、B-智乃买瓜

• 背包

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1010, mod = 1e9+7;
int w[maxn], f[maxn][maxn];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n, m;  cin>>n>>m;
    for(int i = 1; i <= n; i++)cin>>w[i];
    f[0][0] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= m; j++){
            f[i][j] = (f[i][j]+f[i-1][j])%mod;
            if(j+w[i]/2<=m)(f[i][j+w[i]/2]+=f[i-1][j])%=mod;
            if(j+w[i]<=m)(f[i][j+w[i]]+=f[i-1][j])%=mod;
        }
    }
    for(int i = 1; i <= m; i++)cout<<f[n][i]<<" ";
    return 0;
}

3、C-智乃买瓜(another version)

• 继续dp

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1010, mod = 1e9+7;
int f[maxn];
vector<int>v;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n;  cin>>n;
    for(int i = 1; i <= n; i++)cin>>f[i];
    f[0] = 1;
    for(int i = 1; i <= n; i++){
        while(f[i]){
            v.push_back(2*i);
            for(int j = 0; j <= n; j++){
                if(j>=i)f[j] = (f[j]-f[j-i]+mod)%mod;
                if(j>=2*i)f[j] = (f[j]-f[j-2*i]+mod)%mod;
            }
        }
    }
    cout<<v.size()<<"\n";
    for(int x : v)cout<<x<<" ";
    return 0;
}

4、D-智乃的01串打乱

• 随便找一个0和1交换一下位置即可

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;  string s;
    cin>>n>>s;
    swap(s[s.find('0')],s[s.find('1')]);
    cout<<s;
    return 0;
}

5、E-智乃的数字积木(easy version)

• 简单贪心策略，对于初始固定的积木顺序，考虑到只有相邻颜色的能够交换，所以对相邻颜色的积木进行一个排序，我们尽可能让相同颜色的积木，数字较大的放在前面即可
• 1≤N,M≤10^5, 0≤K≤10，发现本题K的数据范围较小，所以可以直接暴力模拟计算答案，然后每次染色后只需修改颜色值然后重新再跑暴力即可。

#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int maxn = 1e5+10, mod = 1e9+7;

LL n, m, k;
string s;
int c[maxn];
LL solve(){
    for(int l = 0, r = 0; l < n; r = l){
        while(c[r]==c[r+1])r++; //找到颜色相同的区间
        sort(s.begin()+l, s.begin()+r+1, greater<int>());//对颜色相同的区间进行排序
        l = r+1; //更新遍历范围
    }
    LL ans = 0;
    for(int i = 0; i < n; i++){
        ans = (ans*10+s[i]-'0'+mod)%mod;
    }
    return ans;
}

int main(){
    cin>>n>>m>>k;
    cin>>s;
    for(int i = 0; i < n; i++)cin>>c[i];
    cout<<solve()<<"\n";
    while(k--){
        int x, y;  cin>>x>>y;
        for(int i = 0; i < n; i++){
            if(c[i]==x)c[i] = y;
        }
        cout<<solve()<<"\n";
    }
    return 0;
}

6、I-智乃的密码

• 题解

#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int maxn = 1e5+10;
LL f[maxn][4]; //到第i个位置为止，每种字符上一次出现的位置
int main(){
    LL n, l, r;  cin>>n>>l>>r;
    string s;  cin>>s;  s="0"+s;
    for(int i = 1; i <= n; i++){
        if(isupper(s[i]))s[i]='0';
        else if(islower(s[i]))s[i]='1';
        else if(isdigit(s[i]))s[i]='2';
        else s[i]='3';
        for(int j = 0; j < 4; j++)f[i][j] = f[i-1][j];
        f[i][s[i]-'0']=i;
    }
    LL ans = 0;
    for(int i = l; i <= n; i++){//枚举右端点
        sort(f[i],f[i]+4);
        LL nl = max(i-r+1, 1ll), nr = i-l+1;//左端点的可选范围
        if(f[i][1]>=nl){ //满足3种不同的位置在可选范围内
            ans += min(f[i][1],nr)-nl+1;
        }
    }
    cout<<ans<<"\n";
    return 0;
}

7、L-智乃的数据库

• 直接模拟就行，对于按照字段分类可以把需要使用的m个字段拿出来重新组成新的vector。
• 对于聚合统计个数，可以直接map判个重记录一下相同vector的个数即可。

#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int maxn = 1010;

string s[maxn];
map<string,int>field;
int a[maxn][maxn];

int main(){
    //输入数据表
    int n, m;  cin>>n>>m;
    for(int i = 1; i <= m; i++)cin>>s[i], field[s[i]] = i;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++)cin>>a[i][j];
    }
    //处理字段
    cin.get();  string ss;  getline(cin,ss);
    vector<int>id;
    int cur = 36;
    for(int i = 37; i<ss.size(); i++){
        if(ss[i]==','||ss[i]==';'){
            string k = ss.substr(cur, i-cur);
            id.push_back(field[k]);
            cur = i+1;
        }
    }
    //输出结果
    map<vector<int>,int> res;
    for(int i = 1; i <= n; i++){
        vector<int>vc;
        for(int x : id){
            vc.push_back(a[i][x]);
        }
        res[vc]++;
    }
    cout<<res.size()<<"\n";
    for(auto x : res)cout<<x.second<<" ";
    return 0;
}

附签到题总结

• 2022牛客寒假算法基础集训营1
  题号 标题 已通过代码 通过率 我的状态
  A 九小时九个人九扇门 点击查看 1956/3965 未通过
  B 炸鸡块君与FIFA22 点击查看 772/2772 未通过
  C Baby’s first attempt on CPU 点击查看 1402/4353 未通过
  D 牛牛做数论 点击查看 1160/3461 通过（数学结论）
  E 炸鸡块君的高中回忆 点击查看 3459/17851 通过（贪心，结论）
  F 中位数切分 点击查看 2035/3008 通过（数学结论）
  G ACM is all you need 点击查看 265/809 未通过
  H 牛牛看云 点击查看 2499/10363 通过（化简后暴力枚举）
  I B站与各唱各的 点击查看 1133/3199 通过（数学结论）
  J 小朋友做游戏 点击查看 2915/11305 通过（贪心后排序枚举）
  K 冒险公社 点击查看 444/1144 未通过
  L 牛牛学走路 点击查看 3695/5901 通过（输出）
• 2022牛客寒假算法基础集训营2
  题号 标题 已通过代码 通过率 我的状态
  A 小沙的炉石 点击查看 1096/4595 通过（推导结论）
  B 小沙的魔法 点击查看 294/969 未通过
  C 小沙的杀球 点击查看 3144/10359 通过（贪心）
  D 小沙的涂色 点击查看 100/324 未通过
  E 小沙的长路 点击查看 1534/5205 通过（贪心后结论）
  F 小沙的算数 点击查看 1493/8685 通过（简单模拟）
  G 小沙的身法 点击查看 423/1673 未通过
  H 小沙的数数 点击查看 2005/8364 通过（贪心后结论）
  I 小沙的构造 点击查看 1073/4952 通过（模拟）
  J 小沙的Dota 点击查看 48/235 未通过
  K 小沙的步伐 点击查看 3379/7150 通过（签到）
  L 小沙的remake（普通版） 点击查看 314/1038 未通过
  M 小沙的remake（竞速版） 点击查看 334/975 未通过
• 2022牛客寒假算法基础集训营3
  题号 标题 已通过代码 通过率 我的状态
  A 智乃的Hello XXXX 点击查看 3307/3598 通过（输出）
  B 智乃买瓜 点击查看 2282/4845 通过（分组背包）
  C 智乃买瓜(another version) 点击查看 816/1705 通过（反向dp）
  D 智乃的01串打乱 点击查看 3106/5342 通过（签到）
  E 智乃的数字积木(easy version) 点击查看 1229/2689 通过（贪心后暴力）
  F 智乃的数字积木(hard version) 点击查看 118/753 未通过
  G 智乃的树旋转(easy version) 点击查看 668/1915 未通过
  H 智乃的树旋转(hard version) 点击查看 210/394 未通过
  I 智乃的密码 点击查看 1316/6137 通过（线性dp）
  J 智乃的C语言模除方程 点击查看 282/1401 未通过
  K 智乃的C语言模除方程(another version) 点击查看 88/326 未通过
  L 智乃的数据库 点击查看 1476/3532 通过（简单stl模拟）