2021牛客寒假算法基础集训营2

B.牛牛抓牛妹

题解：
感情这个题目很妙。
分层图+瞎几把搜索。

我们可以发现题目中最多就只有7个锁， $2^7=128$ ，那我们可以建128层图，读题可知牛妹每回合都会寻找当前位置到终点的最短路线移动，如果最短路线不唯一，她总是会选择移动到节点编号较小的节点，我们不会每次都要跑一次最短路吧。。？？
想了想是不必要得，我们可以提前把每种状态他走的下一个点提前预处理出来，就可以O(1)知道牛妹得下一个点去哪了。
如何预处理？
对于每一种状态来说，我们可以从终点开始进行bfs，遍历每个点，每个点得next即为他的父节点。

我们最终得目的就是把牛妹骗到陷阱当中，那么我们从七点开始bfs搜索，走到走不出来得地方即可break输出。
注意每个点bfs时要遍历到不同状态得相同点继续传递即可。

对于输出答案我们用一个pre数组记录一下每次走的前一步逆序输出即可。

代码：

/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
//#define int long long
#define endl '\n'

using namespace std;
const int maxn=110;
const int maxm=510;
const int mod=1e9+7;

int n,m,k;
int node[maxn],dis[maxn][maxm];
int nxt[maxn][maxm];
vector<int> edge[maxn];
vector<pair<int,int> > ans;
bool judge(int x,int st){
    int pos=0;
    while(st){
        if((st&1)&&node[pos]==x) return true;
        pos++,st>>=1;
    }
    return false;
}


void bfs(int st){
    queue<int> q;
    q.push(n);
    while(!q.empty()){
        int t=q.front();q.pop();
        if(judge(t,st)) continue;
        for(auto i:edge[t]){
            if(i==n) continue;
            if(!dis[i][st]){
                dis[i][st]=dis[t][st]+1;
                q.push(i);
            }
            if(dis[i][st]==dis[t][st]+1){
                if(!nxt[i][st]||nxt[i][st]>t) nxt[i][st]=t;
            }
        }
    }
}

bool visited[maxn][maxm];
int ansx,ansst;
pair<int,int> pre[maxn][maxm];
void sol(){
    queue<pair<int,int> > q;
    q.push({1,0});
    while(!q.empty()){

        int x=q.front().first;
        int st=q.front().second;
        //cout<<x<<endl;
        q.pop();
        if(x==n) continue;
        if(!dis[x][st]){
            ansx=x;ansst=st;
            //cout<<"find!"<<endl;

        }
        else{
            if(!visited[nxt[x][st]][st]){
                visited[nxt[x][st]][st]=true;
                q.push({nxt[x][st],st});
                pre[nxt[x][st]][st]={x,st};
            }
            for(int i=0;i<(1<<k);i++){
                if(!visited[x][i]){
                    visited[x][i]=true;
                    q.push({x,i});
                    pre[x][i]={x,st};
                }
            }
        }
    }
    //cout<<"test "<<ansx<<" "<<ansst<<endl;
    while(ansx){
            //cout<<"sss "<<ansx<<" "<<ansst<<endl;
        ans.emplace_back(ansx,ansst);
        if(ansx==1&&ansst==0) break;
        int t1=pre[ansx][ansst].first;
        int t2=pre[ansx][ansst].second;
        ansx=t1,ansst=t2;

    }
    reverse(ans.begin(),ans.end());

}



signed main(){
//    ios::sync_with_stdio(false);
//    cin.tie(0);
//    cout.tie(0);
    cin>>n>>m>>k;
    for(int i=0;i<k;i++) cin>>node[i];
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    for(int i=0;i<(1<<k);i++){
        bfs(i);
    }
    //cout<<"debug"<<endl;
    memset(visited,false,sizeof visited);
    sol();
    //cout<<"debug"<<endl;

    for(int i=1;i<ans.size();i++){
        if(ans[i].first!=ans[i-1].first){
            cout<<"continue"<<endl;
            continue;
        }
        int x=ans[i].second,y=ans[i-1].second,id=0;
        while(x){
            if((x&1)!=(y&1)){
                if(x&1) cout<<"lock ";
                else cout<<"unlock ";
                cout<<node[id]<<endl;
            }
            x>>=1;y>>=1;id++;

        }
    }
    cout<<"checkmate!"<<endl;

}

C. 牛牛与跷跷板

题解：
这题主要是建图，不正确的建图方法可能会让本题TLE。
怎么建图呢，首先可以按照左端点进行排序，（我这个建图方法可能更省劲一些，时间正好也给卡过去了），排好序遍历第一行每一个，对于每个点遍历第二行，一旦发现第二行的跷跷板在当前跷跷板的右边了，我们就可以直接break，进行下一个点的遍历，当然你也可以用差不多的方法优化一下左边的端点。
将建好的图进行bfs即可。

代码：

/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
//#define int long long
#define endl '\n'

using namespace std;
const int maxn=1e5+10;
const int mod=1e9+7;


struct node{
    int id,l,r;
    bool operator <(const node & a)const
    {
        return l<a.l;
    }
};

vector <node> v[maxn];
vector<int> edge[maxn];



void add(int x,int y){
    for(auto i:v[x]){
        for(auto j:v[y]){
            if((i.l>=j.l)&&(i.l>=j.r)) continue;
            else if((i.r<=j.l)&&(i.r<=j.r)) break;
            else{
                edge[i.id].push_back(j.id);
                edge[j.id].push_back(i.id);
            }
        }
    }
}

int dis[maxn];
bool visited[maxn];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    //memset(visited,false,sizeof visited);
    memset(dis,0x7f,sizeof dis);
    for(int i=1;i<=n;i++){
        int x,l,r;

        cin>>x>>l>>r;
        v[x+1].push_back({i,l,r});
    }

    //cout<<"debug"<<endl;

    for(int i=1;i<maxn;i++){
        if(v[i].size()){
            sort(v[i].begin(),v[i].end());
        }
    }


    for(int i=1;i<=maxn;i++){
        //cout<<i<<endl;

        if(v[i].size()&&v[i+1].size()){
            add(i,i+1);
        }
        if(!v[i].size()) continue;
        for(int j=0;j<v[i].size()-1;j++){
            if(v[i][j].r==v[i][j+1].l){
                edge[v[i][j].id].push_back(v[i][j+1].id);
                edge[v[i][j+1].id].push_back(v[i][j].id);
               // cout<<v[i][j].id<<" "<<v[i][j+1].id<<endl;
            }
        }
        //cout<<i<<endl;
    }


    queue<int> q;
    q.push(1);
    dis[1]=0;

    while(!q.empty()){
        int temp=q.front();
        q.pop();
        for(auto i:edge[temp]){
            if(dis[i]>dis[temp]+1){
                dis[i]=dis[temp]+1;
                q.push(i);
            }
        }
    }
    cout<<dis[n]<<endl;


}

F.牛牛与交换排序

题解：
一旦某一次操作选择了数组的某个位置进行区间翻转操作，下一次做区间翻转的位置将会比上一次更靠右
通过这句话，我们贪心优先从对左边未归位好的元素进行归为。
首先，你需要把题目中的元素都给归好位，我们这边从左边开始归位，如何确定这个交换的长度呢，长度即为：从左边往右边进行遍历，第一个（下标与元素不同）的位置与（元素大小等于该下标）位置的长度。
确定好长度以后，我们对数组遍历，然后暴力反转即可。
900ms+ （危

/*Keep on going Never give up*/
//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;
const int maxn=1e5+10;
const int mod=1e9+7;

int a[maxn];

void sol(int l,int r){
    for(int i=l;i<=(l+r)/2;i++){
        swap(a[i],a[l+r-i]);
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int num=1;
    for(int i=1;i<=n;i++){
        if(a[i]!=i){
            num=i;
            break;
        }
    }
    if(num==n){
        cout<<"yes"<<endl;
        cout<<1<<endl;
        return 0;
    }
    int l=num,len=0;
    for(int i=l;i<=n;i++){
        if(num==a[i]){
            len=(i-l+1);
            break;
        }
    }
    bool flag=true;
    //cout<<len<<endl;
    for(int i=l;i<=n-len+1;i++){
        //cout<<i<<" "<<i+len-1<<endl;
        if(a[i]==i){
            continue;
        }
        else if(i==a[i+len-1])
            sol(i,i+len-1);
        else{
            flag=false;
            break;
        }
    }
    if(flag){
        cout<<"yes"<<endl;
        cout<<len<<endl;
    }
    else cout<<"no"<<endl;
}

H.牛牛与棋盘

题解：
循环输出

代码：

/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;
const int maxn=3e5+10;
const int mod=1e9+7;


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if((i+j)&1) cout<<1;
            else cout<<0;
        }
        cout<<endl;
    }

}

I.牛牛的“质因数”

题解：
这个题我们可以由递推来做，先把素数给筛出来，F(x*p)=在F(x)前面加一个p。把p乘到相应的位数的大小即可。

代码：

/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;
const int maxn=4e6+10;
const int mod=1e9+7;

int shai[maxn],tes[maxn],cnt=0;
bool pir[maxn];

int dp[maxn];

void init(){
    for(int i=2;i<maxn;i++) pir[i]=true;


    for(int i=2;i<maxn;i++){
        if(pir[i]){
            shai[++cnt]=i,tes[i]=i;
            for(int j=2*i;j<maxn;j+=i){
                pir[j]=false;
                tes[j]=i;
            }
        }
    }
}

inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
inline void write(int x){
    if (x < 0) x = ~x + 1, putchar('-');
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
void sol(int n){
    int res=2;
    for(int i=3;i<=n;i++){
        int pp=tes[i];
        int zzz=1;
        int temp=pp;
        while(temp){
            temp/=10;
            zzz*=10;
        }
        dp[i]=(dp[i/pp]*zzz%mod+pp)%mod;
        res=(res+dp[i])%mod;
    }
    write(res);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    n=read();
    init();
    dp[1]=0,dp[2]=2;
    sol(n);
}

题解文章被收录于专栏

主要写一些题目的题解