【题解】牛客小白月赛6
题目比较基础,但涵盖的知识点很多,最后两道题是赛后写的。
完整代码请搜索LittleFall的提交记录
A-鲲
两人在周长l的圆环上比赛游泳一周,A的速度始终为a,B的速度为b,两人同时从起点同向出发,当两人圆周距离大于k时,B可以选择反向游,先回到起点的人胜。给出l,k,a,b,问两者回到起点的时间差。
A的到达时间恒定为l/a,B只有两种策略:1.一直向前,2.向前一段再向后。
若b>=a则B只能选择策略1,到达时间为l/b。
当b<a时,两者相距为k的时间为k/(a−b),策略2总花费时间为2∗k/(a−b)。
选择策略2有一个条件,即B到达终点时A距离终点至少还有k,即2∗k/(a−b)∗a<=l−k
复杂度O(1)
ll l = read(),k=read(),a=read(),b=read(); double tb = (double)l/b; if( 2*k<l && b<a && 2*k*a<=(l-k)*(a-b) ) tb = min(tb, 2.0*k/(a-b)); printf("%.2f\n", tb - (double)l/a );
B-鹏
n个整数的序列,求先上升后下降的段出现了几次。
判断上升,再判断下降,计数。
O(n)
int n =read(),ans = 0; int now = read(),up=0; for(int i =1;i<n;i++) { int t=read(); if(t>now) up=1; else if(t<now) { if(up==1) { up=0; ans++; } } now =t; } printf("%d\n",ans );
C-桃花
给出一棵树,求树的直径(最长的链)长度。
从根节点dfs一次,找到最远的点x。再从x开始dfs一次,找到最远的点y,则x到y是树的一条直径。
证明可以百度,大意是反证距离任意点最远的点都是直径的端点。
O(n)
vector<int> save[M]; int dis[M]; int ans,xp = -1; void find(int p) { if(dis[p]>xp) { xp = dis[p]; ans = p; } for(auto x:save[p]) { if(dis[x]==-1) { dis[x] = dis[p] + 1; find(x); } } } int main(void) { int n = read(); for(int i=1;i<n;i++) { int a = read(),b=read(); save[a].push_back(b); save[b].push_back(a); } memset(dis,-1,sizeof(dis)); dis[1] = 0; find(1); memset(dis,-1,sizeof(dis)); xp = -1; dis[ans] = 0; find(ans); printf("%d\n",xp+1 ); return 0; }
D-字符串丝带
开一个数组表示遍历到当前位置时出现过的各个字母数量,再开一个数组记录每个位置的答案。
O(n+m)
char save[M]; int record[256]; int ans[M]; int main(void) { int n = read(), m=read(); scanf("%s",save+1); for(int i=1;save[i];i++) { record[save[i]]++; ans[i] = record[save[i]]; } for(int i=0;i<m;i++) { printf("%d\n",ans[read()] ); } return 0; }
E-对弈
五子棋,给出下棋顺序,判断谁先赢。
每走一步需要判断输赢,我的方法是以当前走的棋子为中心判断左右9格,上下9格,左上右下9格,左下右上9格是否有连续的5个相同颜色棋子。将数组整体向右下平移即可不考虑边界。
const int go[4][2] = {{1,1},{0,1},{1,0},{-1,1}}; //1,1 - n,n对应 5,5 - n+4,n+4, 所有棋子横纵坐标+4 int save[M][M]; int main(void) { int n=read(),m=read(); int ans = 0, ansstep = m, player = -1; //1表示htbest,-1表示whz for(int step = 1;step<=m; step++) { player *= -1; int x=read()+4,y=read()+4; save[x][y] = player; for(int k = 0;k<4;k++) { int px = x - 4*go[k][0], py = y-4*go[k][1]; int lx = 0,alx = 0; for(int cnt = 0;cnt<9;cnt++) { if(save[px][py]==player) { lx++; alx = max(alx,lx); } else { lx = 0; } px +=go[k][0],py+=go[k][1]; } if(alx>=5) { ans = player; ansstep = step; goto end; } } } end: if(ans==0) printf("UNK %d\n",m); else if(ans==1) printf("HtBest %d\n",ansstep ); else printf("WHZ %d\n",ansstep ); return 0; }
F-发电
1e6个元素,1e6个操作,三种:1.单点乘,2.单点除,3.区间求积,模1e9+7输出
树状数组改造一下,将加换成乘,0换成1,加上取模,求区间积时用之后的除以之前的。
除以一个数就是乘以它的逆元,用费马小定理。
复杂度O(nlogn)
class BinTree: vector<ll> { public: explicit BinTree(int k = 0) //默认初始化一个能保存k个元素的空树状数组 { assign(k + 1, 1); //有效下标从1开始,0仅作逻辑用处 } int lowbit(int k){return k & -k;} ll sum(int k)//求第1个元素到第n个元素的和 { return k > 0 ? (sum(k - lowbit(k)) * at(k))%MOD : 1; } int last()//返回最后一个元素下标 { return size() - 1; } void add(int k, ll w) //为节点k加上w { if(k > last())return; at(k) *= w; at(k) %= MOD; add(k + lowbit(k), w); } }; ll power(ll a, ll b) { ll ans = 1; while(b) { if(b & 1) ans = ans * a % MOD; a = a * a % MOD; b >>= 1; } return ans; } ll inv(ll a){ return power(a, MOD - 2); } int main(void) { int n=read(),m=read(); BinTree bt(n); while(m--) { int op=read(),x=read(),y=read(); if(op==1) bt.add(x,y); else if(op==2) bt.add(x,inv(y)); else { ll ans = bt.sum(y) * inv(bt.sum(x-1)) % MOD; cout<<ans<<endl; } } return 0; }
G-指纹锁
维护一个存储着值在1e7以内的集合,1e6个操作,包括三种:
1.添加x,若集合内有值与x相差k以内,忽略本次操作;
2.删除x,删除集合内所有与x相差k以内的数;
3.查询x,如果集合内有与x相差k以内的数则输出Yes,否则输出No.
用set,预先添加一个特别大的数如1e9+7,如果lower_bound(x-k)<=x+k,说明集合内有值与x相差k以内。
复杂度O(nlogn)
set<int> st; int select(int val) { auto it = st.lower_bound(val); if(it==st.end()) return MOD; return *it; } int main(void) { int m=read(),k=read(); char op[10]; int val; for(int i = 0 ;i<m;i++) { scanf("%s%d",op,&val); if(op[0]=='a') { if(select(val-k) > val+k) st.insert(val); } else if(op[0]=='d') { int pval = select(val-k); while(pval<=val+k) { st.erase(pval); pval = select(val-k); } } else { printf("%s\n",select(val-k)<=val+k?"Yes":"No" ); } } return 0; }
H-挖沟
最小生成树。
按最小生成树做AC了,但是题目中说要求∑d[i][j]最小,我无法证明这个问题可以转换成最生成树问题。
Kruskal,O(ElogE)
struct Edge { int x,y,p; }save[M]; int fa[M]; int getfa(int p) { return p==fa[p]?p:fa[p]=getfa(fa[p]); } int main(void) { int n=read(),m=read(); for(int i=0;i<m;i++) { save[i].x=read(); save[i].y=read(); save[i].p=read(); } sort(save,save+m,[](Edge &a,Edge &b){return a.p<b.p;}); for(int i =1;i<=n;i++) fa[i]=i; int ans = 0; for(int i=0;i<m;i++) { int x= getfa(save[i].x),y=getfa(save[i].y); if(x!=y) { ans+=save[i].p; fa[y]=x; } } cout <<ans<<endl; return 0; }
I-公交线路
给出一张图,求s点到t点的最短距离
dijkstra
复杂度O(N^2)
//链式前向星 int tot = 0; int fst[N]; int pnt[M],nxt[M],pri[M]; void add(int x, int y, int prior) { pnt[++tot] = y; pri[tot] = prior; nxt[tot] = fst[x]; fst[x] = tot; } //dijkstra int dis[N],vis[N]; int main(void) { #ifdef _LITTLEFALL_ freopen("in.txt","r",stdin); #endif int n=read(),m=read(),s=read(),t=read(); for(int i =0;i<m;i++) { int x = read(),y=read(),p=read(); add(x,y,p); add(y,x,p); } //dijkstra memset(dis,0x3f,sizeof(dis)); dis[s] = 0, vis[s]=1; int now = s; while(now!=t) { for(int i = fst[now];i;i=nxt[i]) { int y = pnt[i]; dis[y] = min(dis[y],dis[now]+pri[i]); } int xm = INT_MAX, tmp = 0; for(int i =1;i<=n;i++) if(vis[i]==0&&dis[i]<xm) tmp = i, xm = dis[i]; now = tmp; vis[now] = 1; } printf("%d\n",vis[t]?dis[t]:-1 ); return 0; }
J-洋灰三角
给定n,k,p,数列,求an的前n项和Sn
(感谢我的大佬队友们帮我想清了公式)
如果k=1,那么an = 1+(n-1)p,等差数列,Sn = n+pn(n-1)/2
否则,,等比数列,最后算得
同样需要快速幂和逆元,复杂度O(1)
ll power(ll a, ll b) { ll ans = 1; while(b) { if(b & 1) ans = ans * a % MOD; a = a * a % MOD; b >>= 1; } return ans; } ll inv(ll a){ return power(a, MOD - 2); } int main(void) { #ifdef _LITTLEFALL_ freopen("in.txt","r",stdin); #endif ll n = read(),k=read(),p=read(); if(k==1) cout<<(n+p*n*(n-1)/2)%MOD<<endl; else { ll kn = power(k,n); ll ans = kn*k + (p-1)*kn - (n*p+1)*k + (n-1)*p+1; ans = (ans%MOD+MOD)%MOD; ans = ans * inv( (k-1)*(k-1) ) %MOD; cout <<ans<<endl; } return 0; }