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;
}