2021牛客寒假算法基础集训营2
B.牛牛抓牛妹
题解：
感情这个题目很妙。
分层图+瞎几把搜索。
我们可以发现题目中最多就只有7个锁，，那我们可以建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);
}
题解 文章被收录于专栏
主要写一些题目的题解
投递中国农业发展银行等公司10个岗位 >
查看5道真题和解析
