2024-02-26 17:18 山东大学 C++ 发布于山东

关注

个人题解 | 转载

原文链接：https://zhuanlan.zhihu.com/p/683944929

2024牛客寒假算法基础集训营6-个人题解

前言：

我是罚时高手

正文：

A：宇宙的终结

签到题， $O(n^3)$ 枚举，看乘积是否在范围内即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int prime[2000];
bool vis[2000];
vector<int>v;
void sieve(int n){//埃氏筛
    int i,j,k;
    k=0;
    vis[0]=vis[1]=1;
    for(i=2;i<=n;i++)
    {
        if(vis[i]==0){
            prime[k++]=i;
        }
        for(j=i+i;j<=n;j+=i){
           vis[j]=1; 
        }
    }
}
int main(){
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(0);
    int l,r;cin>>l>>r;
    sieve(r);
    for(int i=2;i<=r;i++){
        if(!vis[i]){
            v.push_back(i);
        }
    }
    for(int i=0;i<v.size();i++){
        for(int j=0;j<v.size();j++){
            for(int k=0;k<v.size();k++){
                if(v[i]*v[j]*v[k]<=r&&v[i]*v[j]*v[k]>=l&&v[i]!=v[j]&&v[j]!=v[k]&&v[i]!=v[k]){
                    cout<<v[i]*v[j]*v[k]<<'\n';
                    return 0;
                }
            }
        }
    }
    cout<<-1<<'\n';
    return 0;
}

B：爱恨的纠葛

签到题，对数组a，先sort一下，然后对于每一个数组b中的元素，用lower_bound在a中进行二分查找，并记录差的绝对值即可。

需要注意的是，每次进行查找时，除了lower_bound返回的下标x，记录abs(a[x]-b[i])外，还需要计算abs(a[x-1]-b[i])：比如对于数组a[]={3,4,9,9,11}，对b[i]=5进行lower_bound得到的是a[x]=9，而a[x-1]=4才是我们需要的目标。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100005],b[100005];
int main(){
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(0);
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    sort(a+1,a+1+n);
    ll minn=1e9+10;
    int minx=0,mini=0;
    for(int i=1;i<=n;i++){
        int x=lower_bound(a+1,a+1+n,b[i])-a;
        if(x==n+1)x--;
        int y=x-1;
        if(y<=1)y=1;
        if(minn>abs(a[x]-b[i])){
            minn=abs(a[x]-b[i]);
            minx=x;mini=i;
            //cout<<minx<<" "<<mini<<'\n';
        }
        if(minn>abs(a[y]-b[i])){
            minn=abs(a[y]-b[i]);
            minx=y;mini=i;
            //cout<<minx<<" "<<mini<<'\n';
        }
    }
    //cout<<minn<<'\n';
    swap(a[mini],a[minx]);
    for(int i=1;i<=n;i++){
        cout<<a[i]<<' ';
    }
    return 0;
}

C：心绪的解剖

贪心（猜结论）

每次都查找找尽可能大的值，这个值要小于n并且属于斐波那契数列，找到之后将其减去，如此查找三次，找到了就输出，找不到就输出-1。

（当时做的时候感觉挺显然的，后来发现不会证...）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
map<ll,bool>mp;
map<ll,int>mi;
ll f[1005];
int main(){
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(0);
    f[0]=0;f[1]=1;
    mp[0]=1;mp[1]=1;mi[0]=0;mi[1]=1;
    for(int i=2;i<=50;i++){
        f[i]=(f[i-1]+f[i-2]);
        mp[f[i]]=1;
        mi[f[i]]=i;
    }
    //cout<<f[50]<<'\n';
    int q;cin>>q;
    while(q--){
        cin>>n;
        int x=upper_bound(f+1,f+1+50,n)-f-1;
        int y=upper_bound(f+1,f+1+50,n-f[x])-f-1;
        int z=upper_bound(f+1,f+1+50,n-f[x]-f[y])-f-1;
        if(f[x]+f[y]+f[z]==n){
            cout<<f[x]<<" "<<f[y]<<" "<<f[z]<<'\n';
        }
        else{
            cout<<-1<<'\n';
        }
    }

    return 0;
}

D：友谊的套路

签到题，高中概率论知识

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
long double p,pp;

int main(){
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>p;
    pp=(1-p)*(1-p)*p*p*p+p*p*(1-p)*(1-p)*(1-p);
    printf("%.9Lf",pp);
    return 0;
}

E：未来的预言

签到题，简单模拟

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;


int main(){
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(0);
    string a,b;
    cin>>a>>b;
    int n;
    auto x=a.substr(2,a.size()-2);
    //cout<<x<<'\n';
    n=stoi(x);
    int rn=0,pn=0,num=0;
    bool flg=1;
    for(int i=0;i<b.size();i++){
        if(b[i]=='P')pn++;
        if(b[i]=='R')rn++;
        if(rn>=n/2+1){
            flg=0;
            cout<<"kou!"<<'\n';
             cout<<i+1<<'\n';
            break;
        }
        if(pn>=n/2+1){
            flg=0;
            cout<<"yukari!"<<'\n';
            cout<<i+1<<'\n';
            break;
        }
    }
    if(flg){
        cout<<"to be continued."<<"\n";
        cout<<b.size()<<'\n';
    }
    return 0;
}

F：命运的抉择

思路来源：2024牛客寒假算法基础集训营6(C,F,G,I,J) - 知乎 (zhihu.com)，很巧妙的方法。

这道题的关键是记录质因子。

由于质数与质数之间的公因数只有1，那么如果两个数字的质因数都不相同，就意味着它们的公因数只能是1。

那么我们枚举1e6内的所有质数 $i$ ，使得其1e6范围内的所有倍数 $j$ 能够与之关联，这样我们就可以通过查询两个数字之间有没有公共质因数来判断这两个数字能不能放在同一个集合；

至于如何处理集合，可以使用并查集操作。

详细部分可以看代码，标注的很清楚：

（吐槽一下本题数据不太强，多测清空时只清了一部分都过了...）

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n;
ll a[100005];
bool vis[1000010];
int prime[1000010];
int fa[100005];
int check[1000004];
vector<int>p[1000010];

void init(){
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
}
int find(int x){
    return x == fa[x] ? x : (fa[x] = find(fa[x]));
}

void uni(int a,int b){
	fa[find(a)]=find(b);
}
void sieve(int m){//埃氏筛
    int i,j,k;
    k=0;
    vis[0]=vis[1]=1;
    for(i=2;i<=m;i++)
    {
        if(vis[i]==0)
            prime[k++]=i;
        for(j=i+i;j<=m;j+=i)
            vis[j]=1;
    }
}
int main(){
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(0);
    int q;cin>>q;
    sieve(1e6);
    for(int i=2;i<=1e6;i++){
        if(!vis[i]){
            for(int j=i;j<=1e6;j+=i){
                p[j].push_back(i);//j的质因数就是p[j]的所有元素
            }
        }
    }
    while(q--){
        cin>>n;
        init();
        vector<int>cle;//清空check用
        for(int i=1;i<=n;i++){
            cin>>a[i];
            for(auto it=p[a[i]].begin();it!=p[a[i]].end();it++){
                int x=*it;
                if(check[x]==0){//如果这个质因数还没人用过
                    check[x]=i;//标记上i，意为x是a[i]的质因数
                    cle.push_back(x);
                }
                else{//如果上面已经标记check[x]=j，说明a[j]和a[i]有相同的质因数
                    uni(check[x],i);
                }
            }
        }
        set<int>ss;
        for(int i=1;i<=n;i++){
            //cout<<find(i)<<'\n';
            ss.insert(find(i));
        }
        if(ss.size()>1){
            int x=find(1);
            vector<int>b,c;
            for(int i=1;i<=n;i++){
                if(find(i)==x){
                    b.push_back(a[i]);
                }
                else{
                    c.push_back(a[i]);
                }
            }
            cout<<b.size()<<' '<<c.size()<<'\n';
            for(int i=0;i<b.size();i++){
                cout<<b[i]<<" ";
            }
            cout<<'\n';
            for(int i=0;i<c.size();i++){
                cout<<c[i]<<" ";
            }
            cout<<'\n';
        }
        else{
            cout<<-1<<" "<<-1<<"\n";
        }
        for(int i=0;i<=n;i++){
            fa[i]=0;a[i]=0;
        }
        //for(int i=0;i<=1000;i++)check[i]=0;//这都过了
        for(auto it=cle.begin();it!=cle.end();it++){
            int x=*it;
            check[x]=0;
        }
    }
}

G：人生的起落

//后补，听说坑大大的多

H：纷乱的红线

//后补（不喜欢几何...）

I：时空的交织

考虑到1e5的数据范围，普通的二维DP肯定会超时，因此考虑有没有什么简化的方法。

于是乎发现确实有一个很重要的数学结论，能看出来这道题就能秒杀了：

对于数组a，设 $l_1$ 到 $r_1$ 的子段和为 $sum_1$ ，对于数组b，设 $l_2$ 到 $r_2$ 的子段和为 $sum_2$ ，此时矩阵 $l_1$ 到 $l_2$ 行， $r_1$ 到 $r_2$ 列的子矩阵中所有元素的和 $sum_3=sum_1*sum_2$ ；

那么这道题就转化成了求最大子段和，贪心法 $O(m n)$ 即可。

因为要考虑正负性，假如数组a最大子段和 $sum_1=5$ ，数组b的最大子段和 $sum_2=-1$ ，此时我们反而应该使得 $sum_1$ 尽可能小——因此我们还需要再求一个最小子段和。方法和贪心求最大子段和是一样的，只需要把数组反转 $(a[i]=-a[i],b[i]=-b[i])$ ，求得反转后数组的最大子段和，再加个负号，即是最小子段和。

最终结果在 $a_{max}*b_{max},a_{max}*b_{min},a_{min}*b_{max},a_{min}*b_{min}$ 找最大值即可。

（赛时代码，很丑）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100005],b[100005];

int main(){
    cin.tie(0);cout.tie(0);
    ios::sync_with_stdio(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=m;i++){
        cin>>b[i];
    }
    
    ll sum = 0, max_sum = -2100000000;
    for (int i = 1; i <= n; i++) {
        sum += a[i];
        if (sum > max_sum) {
            max_sum = sum;
        }
        if (sum < 0) {
            sum = 0;
        }
    }
    ll asum=max_sum;
    
    for(int i=1;i<=n;i++){
        a[i]=-a[i];
    }
    
    sum = 0, max_sum = -2100000000;
    for (int i = 1; i <= n; i++) {
        sum += a[i];

        if (sum > max_sum) {
            max_sum = sum;
        }

        if (sum < 0) {
            sum = 0;
        }
    }
    ll amin=-max_sum;
    
    sum = 0, max_sum = -2100000000;
    for (int i = 1; i <= m; i++) {
        sum += b[i];
        if (sum > max_sum) {
            max_sum = sum;
        }
        if (sum < 0) {
            sum = 0;
        }
    }
    ll bsum=max_sum;
    //cout<<a1<<" "<<a2<<" "<<b1<<" "<<b2<<'\n';
    for(int i=1;i<=m;i++){
        b[i]=-b[i];
    }
    sum = 0, max_sum = -2100000000;
    for (int i = 1; i <= m; i++) {
        sum += b[i];
        if (sum > max_sum) {
            max_sum = sum;
        }

        if (sum < 0) {
            sum = 0;
        }
    }
    ll bmin=-max_sum;
    //cout<<asum<<" "<<amin<<" "<<bsum<<" "<<bmin<<'\n';
    ll max1=asum*bsum,max2=asum*bmin,max3=amin*bsum,max4=amin*bmin;
    ll ans=-2100000000;
    ans=max(ans,max1); ans=max(ans,max2); ans=max(ans,max3); ans=max(ans,max4); 
    cout<<ans<<'\n';
    return 0;
}

J：绝妙的平衡

不知道为什么调了好久...我是不是天生跟搜索犯冲？

对于每个红色节点，如果它没有白色子节点，则它的子树除它以外的和已经是3的倍数，它为1或2都不可能再使它的子树和为3的倍数。

如果它至少有1个白色子节点，则它和白色子节点可以配合使得它的子树和为3的倍数。

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
#define int long long
const int N=1e5+10;

//char s[N];
string s;
vector<int>e[N];
bool r;
int sum[N],ans[N];

void dfs(int v){
    if(r) return;
    for(auto x:e[v]){
        dfs(x);
        sum[v]=(sum[v]+sum[x])%3;
    }
    //cout<<s[1]<<s[2]<<s[3]<<endl;
    if(s[v]=='R'){
        //cout<<s[1]<<s[2]<<s[3]<<endl;
        int p=0;
        for(auto x:e[v]){
            if(s[x]=='W'){
                //cout<<s[v]<<" "<<x<<endl;
                p=x;
                break;
            }
        }
        if(!p) r=true;
        else{
            if(sum[v]==0) ans[p]=2,ans[v]=2;
            else ans[v]=3-sum[v];
        }
        sum[v]=0;
    }
    else{
        ans[v]=1;
        sum[v]=(sum[v]+1)%3;
    }
}

signed main(){
    int n;
    cin>>n;
    cin>>s;
    s=' '+s;
    for(int i=2;i<=n;i++){
        int x;
        cin>>x;
        e[x].push_back(i);
    }
    dfs(1);
    if(r){
        cout<<"-1"<<endl;
    }else{
        for(int i=1;i<=n;i++){
            cout<<ans[i];
        }
        cout<<endl;
    }
    return 0;
}