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