牛客练习赛67题解
A: 牛牛爱字符串
一道简单的模拟题稍微有点细节
注意不要输出多余的空格
并且不能有多余的0000这样的问题，但是要注意如果是0必须输出0，这是个易错的细节
这里读入用string和getline更方便，并且细节部分可以用个deque维护
代码：
#include<bits/stdc++.h>
#define LL long long
#define pb push_back
using namespace std;
string str;
int main(){
while(getline(cin,str)){
int n=str.size();str='#'+str;
bool fl=false;deque<char>v;v.clear();
for(int i=1;i<=n;i++)
if(str[i]>='0'&&str[i]<='9')v.pb(str[i]);
else if(v.size()){
if(fl)printf(" ");fl=true;
while(v.size()>1&&v.front()=='0')v.pop_front();
for(auto x:v)printf("%c",x);v.clear();
}
if(v.size()){
if(fl)printf(" ");
while(v.size()>1&&v.front()=='0')v.pop_front();
for(auto x:v)printf("%c",x);v.clear();
}
puts("");
}
return 0;
}B: 牛牛爱位运算
只要你知道位运算就知道，&操作是单调不增的
我们有了这个结论可以直接发现只选一个是最优的，因此这个的答案就是我们的所有数取个max就好了
代码：
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int main(){
int T;scanf("%d",&T);
while(T--){
int n,x,ma=0;scanf("%d",&n);
while(n--)scanf("%d",&x),ma=max(ma,x);
printf("%d\n",ma);
}
return 0;
}
C: 牛牛爱博弈
考试的时候写了个你nlogn的暴力找了找规律，发现是和3的倍数有关的然后就针对3取余然后讨论一下就可以
然后看了题解以后发现其实还是有可以推导的办法
我们发现是3的倍数才有必胜策略，因为2的次幂对3取余是1,2,1,2,....这样的
然后就特判可以ac
代码：
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int main(){
int T;scanf("%d",&T);
while(T--){
int x;scanf("%d",&x);
puts(x%3?"Alan":"Frame");
}
return 0;
}D: 牛妹爱数列
和题解的思路不太一样，方程的状态长得差不多，但是大概有一种更好理解的dp方法，就是优化的过程不太好理解
我们只需要定义一样的状态，然后枚举转移，发现是只和dp的值和0和1的前缀个数有关，然后我们记录一个pre代表前缀来转移过来的极值，然后每次利用这个对dp进行转移并且更新极值即可！
代码：
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e5+5,Inf=1e9;
int n,a[N],f[N][2],cnt[N][2],pre[2];
void rel(int &x,int y){x=x<y?x:y;}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),cnt[i][0]=cnt[i-1][0],cnt[i][1]=cnt[i-1][1],cnt[i][a[i]]++;
f[1][a[1]^1]=1,f[1][a[1]]=0,pre[0]=pre[1]=Inf;
for(int i=0;i<2;i++)rel(pre[i],f[1][i]-cnt[1][i^1]);
for(int i=2;i<=n;i++){
f[i][0]=cnt[i][1],f[i][1]=cnt[i][0];
for(int j=0;j<2;j++)rel(f[i][j],pre[j]+cnt[i][j^1]),rel(f[i][j],pre[j^1]+cnt[i][j]+1);
for(int j=0;j<2;j++)rel(pre[j],f[i][j]-cnt[i][j^1]);
}
printf("%d\n",f[n][0]);
return 0;
}E: 牛妹游历城市
整篇题解详细介绍这道题，作者写了3种正确性有保证，并且可以通过此题的做法！
1：考试的时候推出了一个结论，就是每一位只会用1次，然后我们可以通过这个，发现我们并不需要最短路，我们只要分位二分然后check判断1和n是否连通
因为只要连通1就可以到达n，然后我们每次check的复杂度是nlogn再乘上并查集的玄学复杂度，因为我们要分为把它插入并查集，具体只要判断最后并查集的连通性就好了
然后这题可能没有被卡得太严，正好卡着时限过题！
#include<bits/stdc++.h>
#define LL long long
#define pb push_back
using namespace std;
const int N=2e5+5;
int n,fa[N];LL a[N];bool usd[32];vector<int>e[32];
int find(int u){return fa[u]==u?u:fa[u]=find(fa[u]);}
void uni(int u,int v){if(find(u)!=find(v))fa[fa[u]]=fa[v];}
void insert(LL x,int i){for(LL k=0;k<32;k++)if(x&(1LL<<k))e[k].pb(i);}
bool check(){
for(int i=1;i<=n+32;i++)fa[i]=i;
for(LL k=0;k<32;k++)if(usd[k]){
for(auto x:e[k])uni(x,n+k+1);
if(find(1)==find(n))return true;
}
return false;
}
int main(){
int T;scanf("%d",&T);
while(T--){
for(LL k=0;k<32;k++)usd[k]=true,e[k].clear();
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]),insert(a[i],i);
if(!check()){puts("Impossible");continue;}
LL ans=0;
for(LL k=31;k>=0;k--){
usd[k]=false;
if(!check())usd[k]=true,ans+=(1LL<<k);
}
printf("%lld\n",ans);
}
return 0;
}2：看了官方题解以后，发现我们要定一个阈值，然后我们可以关于这个阈值来最短路，但是阈值之间来两两要连接，然后我们发现阈值是256是最优的，然后我们用一些位运算的技巧用按位或来搞一下，最后连边DIJ即可
#include<bits/stdc++.h>
#define LL long long
#define pii pair<LL,LL>
using namespace std;
const LL N=1e6+5,M=5e6+5,B=(1LL<<8),Inf=1e18;
struct Edge{LL to,w,nxt;}e[M];
LL n,fst[N],tote,s,t;LL dis[N];bool vis[N];
priority_queue<pii>que;
void adde(LL u,LL v,LL w){e[++tote]=(Edge){v,w,fst[u]};fst[u]=tote;}
void DIJ(LL s,LL t){
for(LL i=0;i<N;i++)dis[i]=Inf,vis[i]=false;
que.push(pii(0,s));dis[s]=0;
while(!que.empty()){
LL u=que.top().second;que.pop();
if(vis[u])continue;vis[u]=true;
for(LL i=fst[u],v,w;i;i=e[i].nxt){
v=e[i].to;w=e[i].w;
if(dis[v]>dis[u]+(LL)w)dis[v]=dis[u]+(LL)w,que.push(pii(-dis[v],v));
}
}
}
signed main(){
LL T;scanf("%lld",&T);
while(T--){
memset(fst,0,sizeof(fst));tote=0;
scanf("%lld",&n);s=(B<<3);t=(B<<3)+n-1;
for(LL i=0;i<B;i++)for(LL j=0;j<B;j++)if(i&j){
LL lb=(i&j)&-(i&j);
for(LL k=0;k<4;k++)adde(k*B+i,(4+k)*B+j,lb<<(k*8LL));
}
for(LL i=0;i<n;i++){
LL x,y;scanf("%lld",&x);
for(LL k=0;k<4;k++){
y=(x>>(k<<3LL))&(B-1);
assert(0<=y&&y<B);
adde(s+i,k*B+y,0);adde((4+k)*B+y,s+i,0);
}
}
DIJ(s,t);
if(dis[t]!=Inf)printf("%lld\n",dis[t]);else puts("Impossible");
}
return 0;
}3：但是其实上述两种各有劣势，第一种时间复杂度太高，第二种容易有细节错误，并且所需空间较大
然后我们考虑实际上我们只要针对于每个二进制的位考虑，用了上述每个点只会用一次的结论，然后我们位与位之间建图floyd即可，为什么是对的呢，我们考虑这个lowbit的过程是最低位，但是我们要求尽量最短路要尽量短，那么我们最短路如果有lowbit肯定会跑lowbit这样才能达到最优，因此我们直接floyd自然保证了最优性！
然后我们用点位运算技巧，预处理一下，建图即可，由于大小只会达到32，用floyd即可！
代码：
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e5+5;
const LL Inf=1e18;
int n;LL a[N],e[32][32],base[32];
int lowbit(int x){return x&-x;}
int main(){
int T;scanf("%d",&T);
while(T--){
for(int i=0;i<32;i++)for(int j=0;j<32;j++)e[i][j]=Inf;
for(int i=0;i<32;i++)base[i]=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
if(n==1){puts("0");continue;}
if(a[1]&a[n]){printf("%lld\n",lowbit(a[1]&a[n]));continue;}
for(int k=0;k<32;k++)for(int i=1;i<=n;i++)if(a[i]&(1LL<<k))base[k]|=a[i];
for(int i=0;i<32;i++){
e[i][i]=0;
for(int j=0;j<32;j++)if(base[i]&(1LL<<j))e[i][j]=(1LL<<j);
}
for(int k=0;k<32;k++)for(int i=0;i<32;i++)for(int j=0;j<32;j++)e[i][j]=min(e[i][j],e[i][k]+e[k][j]);
LL ans=Inf;
for(int i=0;i<32;i++)for(int j=0;j<32;j++)
if((a[1]&(1LL<<i))&&(a[n]&(1LL<<j)))ans=min(ans,(1LL<<i)+e[i][j]);
if(ans!=Inf)printf("%lld\n",ans);else puts("Impossible");
}
return 0;
}F: 牛妹的苹果树
这个套路很常见了，我们只要考虑直径的转移一定是从两个直径的最多4个端点中选出两个即可，然后我们可以暴力转移，具体的我们求lca可以用树剖lca来加速，当然欧拉序lca更好，但是这里树剖就可以过题了
然后我们用一个线段树维护一下直径的端点即可！
代码：
#include<bits/stdc++.h>
#define LL long long
#define pii pair<int,int>
using namespace std;
const int N=3e5+5;
struct Edge{int to,w,nxt;}e[N<<1];
int n,m,fst[N],tote,dep[N],siz[N],fa[N],son[N],top[N];LL dis[N];
void adde(int u,int v,int w){
e[++tote]=(Edge){v,w,fst[u]};fst[u]=tote;
e[++tote]=(Edge){u,w,fst[v]};fst[v]=tote;
}
int lca(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
u=fa[top[u]];
}
return dep[u]<dep[v]?u:v;
}
LL calcdis(int u,int v){
if(u==-1||v==-1)return 0;
return dis[u]+dis[v]-(dis[lca(u,v)]<<1);
}
void dfs(int u){
siz[u]=1;
for(int i=fst[u],v;i;i=e[i].nxt)if((v=e[i].to)!=fa[u]){
dep[v]=dep[u]+1;dis[v]=dis[u]+(LL)e[i].w;fa[v]=u;
dfs(v);siz[u]+=siz[v];
if(siz[v]>siz[son[u]])son[u]=v;
}
}
void dfs2(int u,int t){
top[u]=t;if(son[u])dfs2(son[u],t);
for(int i=fst[u],v;i;i=e[i].nxt)if((v=e[i].to)!=fa[u]&&v!=son[u])dfs2(v,v);
}
namespace seg{
pii t[N<<2];
pii merge(pii u,pii v){
pii res;LL now,md=0;
now=calcdis(u.first,u.second);if(now>md)md=now,res=pii(u.first,u.second);
now=calcdis(u.first,v.first);if(now>md)md=now,res=pii(u.first,v.first);
now=calcdis(u.first,v.second);if(now>md)md=now,res=pii(u.first,v.second);
now=calcdis(u.second,v.first);if(now>md)md=now,res=pii(u.second,v.first);
now=calcdis(u.second,v.second);if(now>md)md=now,res=pii(u.second,v.second);
now=calcdis(v.first,v.second);if(now>md)md=now,res=pii(v.first,v.second);
return res;
}
void build(int rt,int l,int r){
if(l==r){t[rt]=pii(l,-1);return;}
int mid=(l+r)>>1;
build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);
t[rt]=merge(t[rt<<1],t[rt<<1|1]);
}
pii ask(int rt,int l,int r,int L,int R){
if(L<=l&&r<=R)return t[rt];
int mid=(l+r)>>1;
if(R<=mid)return ask(rt<<1,l,mid,L,R);
if(L>mid)return ask(rt<<1|1,mid+1,r,L,R);
return merge(ask(rt<<1,l,mid,L,R),ask(rt<<1|1,mid+1,r,L,R));
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1,u,v,w;i<n;i++)scanf("%d%d%d",&u,&v,&w),adde(u,v,w);
dfs(1);dfs2(1,1);
seg::build(1,1,n);
while(m--){
int l,r;scanf("%d%d",&l,&r);
pii far=seg::ask(1,1,n,l,r);
printf("%lld\n",calcdis(far.first,far.second));
}
return 0;
}
字节跳动公司氛围 605人发布