牛客小白月赛99
\(A\) 牛客 NC275617 材料打印 \(AC\)
-
\(by+a \times \min(x,y)\) 即为所求。
点击查看代码
int main() { ll t,a,b,x,y,i; cin>>t; for(i=1;i<=t;i++) { cin>>a>>b>>x>>y; cout<<b*y+a*min(x,y)<<endl; } return 0; }
\(B\) 牛客 NC275619 %%% \(AC\)
-
观察样例发现和 \(\log_{2}\) 相关，自然而然地想到每次减少一半左右。
-
容易发现每次取 \(mod=\left\lfloor \frac{n}{2} \right\rfloor+1\) ，从而使 \(n\) 变成 \(\left\lfloor \frac{n}{2} \right\rfloor-1\) 是最优情况。
- 取 \(mod=\left\lfloor \frac{n}{2} \right\rfloor-1\) 不如 \(mod=\left\lfloor \frac{n}{2} \right\rfloor+1\) 优。
点击查看代码
int main() { ll t,n,ans,i; cin>>t; for(i=1;i<=t;i++) { cin>>n; ans=0; while(n!=0) { n%=(n/2+1); ans++; } cout<<ans<<endl; } return 0; }
\(C\) 牛客 NC275634 迷宫 \(AC\)
-
\(DFS\) 处理出起点、终点所在的连通块，分别记作 \(S,E\) 。若 \(E\) 中存在一个点或与其相邻的点可以被 \(S\) 中点使用一次超能力到达则合法。
点击查看代码
int hang[1010],lie[1010],vis[1010][1010],dx[5]={0,1,-1,0,0},dy[5]={0,0,0,1,-1},n,m; char s[1010][1010]; void dfs1(int x,int y) { vis[x][y]=1; hang[x]=1; lie[y]=1; for(int i=1;i<=4;i++) { int nx=x+dx[i],ny=y+dy[i]; if(1<=nx&&nx<=n&&1<=ny&&ny<=m&&vis[nx][ny]==0&&s[nx][ny]!='#') { dfs1(nx,ny); } } } void dfs2(int x,int y) { vis[x][y]=1; if(hang[x]==1||hang[x-1]==1||hang[x+1]==1||lie[y]==1||lie[y-1]==1||lie[y+1]==1) { cerr<<x<<" "<<y<<endl; cout<<"YES"<<endl; exit(0); } for(int i=1;i<=4;i++) { int nx=x+dx[i],ny=y+dy[i]; if(1<=nx&&nx<=n&&1<=ny&&ny<=m&&vis[nx][ny]==0&&s[nx][ny]!='#') { dfs2(nx,ny); } } } int main() { int sx,sy,ex,ey,i,j; cin>>n>>m; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { cin>>s[i][j]; if(s[i][j]=='S') { sx=i; sy=j; } if(s[i][j]=='E') { ex=i; ey=j; } } } dfs1(sx,sy); memset(vis,0,sizeof(vis)); dfs2(ex,ey); cout<<"NO"<<endl; return 0; }
\(D\) 牛客 NC275683 又是一年毕业季 \(AC\)
-
在前 \(n+1\) 个质数里找到一个最小的不在 \(\{ a \}\) 中出现过的质数即可。
点击查看代码
int prime[300010],vis[3000010],f[3000010],len=0; void isprime(int n) { memset(vis,0,sizeof(vis)); for(int i=2;i<=n;i++) { if(vis[i]==0) { len++; prime[len]=i; } for(int j=1;j<=len&&i*prime[j]<=n;j++) { vis[i*prime[j]]=1; if(i%prime[j]==0) { break; } } } } int main() { int t,n,a,i,j; cin>>t; isprime(3000000); for(j=1;j<=t;j++) { memset(f,0,sizeof(f)); cin>>n; for(i=1;i<=n;i++) { cin>>a; if(a<=3000000&&vis[a]==0) { f[a]=1; } } for(i=1;i<=n+1;i++) { if(f[prime[i]]==0) { cout<<prime[i]<<endl; break; } } } return 0; }
\(E\) 牛客 NC275713 多米诺骨牌 \(AC\)
-
同 CF56E Domino Principle ，处理出向右的最远延伸距离。
-
删掉被包含的小区间，然后取 \(m\) 个长度较大的彼此不相交区间即可。
点击查看代码
struct node { int x,r,L,R; }a[200010]; int len[200010]; bool cmp(node a,node b) { return a.x<b.x; } int main() { int t,n,m,nn,pos,ans=0,i,j; cin>>t; for(j=1;j<=t;j++) { cin>>n>>m; ans=nn=pos=0; for(i=1;i<=n;i++) { cin>>a[i].r; } for(i=1;i<=n;i++) { cin>>a[i].x; } sort(a+1,a+1+n,cmp); for(i=1;i<=n;i++) { a[i].L=a[i].R=i; } for(i=n;i>=1;i--) { while(a[i].R+1<=n&&a[i].x+a[i].r>=a[a[i].R+1].x) { a[i].r=max(a[i].r,a[a[i].R+1].x+a[a[i].R+1].r-a[i].x); a[i].R=a[a[i].R+1].R; } } for(i=n;i>=1;i--) { while(a[i].R+1<=n&&a[i].x+a[i].r>=a[a[i].R+1].x) { a[i].R=max(a[i].R,a[a[i].R+1].R); } } for(i=1;i<=n;i++) { if(a[pos].R>=a[i].R) { continue; } else { nn++; pos=i; len[nn]=a[i].R-a[i].L+1; } } sort(len+1,len+1+nn,greater<int>()); for(i=1;i<=min(nn,m);i++) { ans+=len[i]; } cout<<ans<<endl; } return 0; }
\(F\) 牛客 NC275719 自爆机器人
-
考虑在 \(i,j\) 两栋墙壁中移动的本质是消耗 \(2|x_{i}-x_{j}|\) 的时间。
-
除去 \(n\) 的必须消耗时间外，以 \(m-1\) 段墙壁间的区间作为物品跑完全背包即可。
-
\(m-1\) 段的区间长度中至多有 \(\sqrt{n}\) 个本质不同的长度，去重后时间复杂度为单次查询时间复杂度为 \(O(t\sqrt{n})\) 。
点击查看代码
int x[200010],a[200010],f[200010]; int main() { int T,n,m,t,ans,i,j,k; cin>>T; for(k=1;k<=T;k++) { cin>>n>>m>>t; ans=0; memset(f,0,sizeof(f)); for(i=1;i<=m;i++) { cin>>x[i]; } sort(x+1,x+1+m); for(i=1;i<=m-1;i++) { a[i]=2*(x[i+1]-x[i]); } sort(a+1,a+m); a[0]=unique(a+1,a+m)-(a+1); f[0]=1; for(i=1;i<=a[0];i++) { for(j=a[i];j<=t-n;j++) { f[j]|=f[j-a[i]]; } } for(i=t-n;i>=0;i--) { if(f[i]==1) { ans=i+n; break; } } cout<<ans<<endl; } return 0; }
\(G\) 牛客 NC275735 大鱼吃小鱼
-
考虑进行差分，接着进行前缀和即可计算某一时刻鱼的重量的总和。
-
考虑将重量进行离散化，树状数组维护原重量方便差分的询问。
-
吃掉不超过自身当前重量的鱼本质上是一个近似斐波那契求和的过程，迭代上界大约在 \(43\) 次左右，时刻离散化后暴力进行迭代即可。
点击查看代码
struct node { ll pos,val,tim; }q[200010]; ll b[100010],l[100010],r[100010],y[100010],cnt=0; void add(ll pos,ll val,ll tim) { cnt++; q[cnt].pos=pos; q[cnt].val=val; q[cnt].tim=tim; } bool cmp(node a,node b) { return a.tim<b.tim; } struct BIT { ll c[200010]; ll lowbit(ll x) { return (x&(-x)); } void add(ll n,ll x,ll val) { for(ll i=x;i<=n;i+=lowbit(i)) { c[i]+=val; } } ll getsum(ll x) { ll ans=0; for(ll i=x;i>=1;i-=lowbit(i)) { ans+=c[i]; } return ans; } }T; int main() { ll t,n,x,pos,ans,sum,num,last,i,j,k,h; cin>>t; for(h=1;h<=t;h++) { cin>>n>>x; cnt=0; for(i=1;i<=n;i++) { cin>>l[i]>>r[i]>>y[i]; b[i]=y[i]; } sort(b+1,b+1+n); b[0]=unique(b+1,b+1+n)-(b+1); for(i=1;i<=n;i++) { pos=lower_bound(b+1,b+1+b[0],y[i])-b; add(pos,y[i],l[i]); add(pos,-y[i],r[i]); } sort(q+1,q+1+cnt,cmp); ans=x; for(i=1;i<=cnt;i=j+1) { j=i; while(q[j+1].tim==q[j].tim&&j+1<=cnt) { j++; } for(k=i;k<=j;k++) { T.add(b[0],q[k].pos,q[k].val); } sum=x; last=0; while(1) { num=T.getsum(upper_bound(b+1,b+1+b[0],sum)-b-1); if(num==last) { break; } else { sum+=num-last; last=num; } } ans=max(ans,sum); } cout<<ans<<endl; } return 0; }
总结
- \(D\) 把调和级数的时间复杂度算错了，吃了 \(1\) 发罚时；因为清空不当，吃了 \(2\) 发罚时。
- \(F\) 赛时没切可能是因为太着急了（？）。