ABC246 简要题解
2022/4/2 23:49:34
本文主要是介绍ABC246 简要题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
A
由题意模拟,在已知的 \(3\) 个点中仅出现 \(1\) 次的横坐标即为缺失的那个,纵坐标同理。
int a,b,c,d,e,f,x,y; map<int,int> cnt1,cnt2; signed main(){ cin>>a>>b>>c>>d>>e>>f; ++cnt1[a],++cnt1[c],++cnt1[e]; ++cnt2[b],++cnt2[d],++cnt2[f]; if(cnt1[a]==1) x=a; if(cnt1[c]==1) x=c; if(cnt1[e]==1) x=e; if(cnt2[b]==1) y=b; if(cnt2[d]==1) y=d; if(cnt2[f]==1) y=f; cout<<x<<" "<<y; return 0; }
B
由题意计算。
double a,b,c; signed main(){ a=(double)read(),b=(double)read(); c=sqrt(a*a+b*b); printf("%.7lf %.7lf",a/c,b/c); return 0; }
C
除了当前 \(a_i<x\) 时对其执行一次操作会使总代价减少 \(a_i\),此外执行 \(t\) 次操作就会使总代价减去 \(t\times x\)。那么优先执行完这部分操作,然后按 \(a\) 的大小降序执行。
int n; ll a[200005],k,x,sum,s; signed main(){ n=read(); k=read(); x=read(); for(rg int i=1;i<=n;++i) a[i]=read(),sum+=a[i]/x,s+=a[i],a[i]%=x; if(sum>=k) return 0*printf("%lld",s-k*x); k-=sum; s-=sum*x; sort(a+1,a+1+n); for(rg int i=n;i>=1&&k;--i) --k,s-=a[i]; printf("%lld",s); return 0; }
D
枚举 \(a\),将 \(a\) 看作参数,对 \(b\) 求偏导 \(f'(b)=3b^2+2ab+a^2\),\(a,b\) 非负时 \(f'(b)\) 始终非负,因此 \(f(b)\) 单增,于是二分 \(b\) 即可。
ull x,ans=-1; signed main(){ cin>>x; for(rg ull a=0;a<=1000000;++a){ ull l=0,r=a; while(l<r){ const ull mid=(l+r)/2ull; if(a*a*a+a*a*mid+a*mid*mid+mid*mid*mid>=x) r=mid; else l=mid+1; } const ull mid=l,v=a*a*a+a*a*mid+a*mid*mid+mid*mid*mid; if(v>=x) ans=min(ans,v); } cout<<ans; return 0; }
E
根根据走的方向建分层图,同层代价为 \(0\),跨层代价为 \(1\),根据象棋规则 01bfs 即可。
int n,ax,ay,bx,by,ans[2005][2005][4]; char s[2005][2005]; deque<pair<pii,int> > q; int dx[]={1,1,-1,-1},dy[]={1,-1,1,-1}; inline pair<pii,int> mp(int a,int b,int c){ return mkp(mkp(a,b),c); } signed main(){ cin>>n>>ax>>ay>>bx>>by; for(rg int i=1;i<=n;++i){ scanf("%s",s[i]+1); for(rg int j=1;j<=n;++j){ s[i][j]=(s[i][j]=='.'); for(rg int k=0;k<4;++k) ans[i][j][k]=inf; } } for(rg int k=0;k<4;++k) q.push_back(mp(ax,ay,k)),ans[ax][ay][k]=1; while(!q.empty()){ const int x=q.front().fi.fi,y=q.front().fi.se,d=q.front().se; q.pop_front(); for(rg int k=0;k<4;++k){ if(k==d) continue; const int tx=x+dx[k],ty=y+dy[k]; if(s[tx][ty]&&ans[tx][ty][k]>ans[x][y][d]+1) ans[tx][ty][k]=ans[x][y][d]+1,q.push_back(mp(tx,ty,k)); } const int tx=x+dx[d],ty=y+dy[d]; if(s[tx][ty]&&ans[tx][ty][d]>ans[x][y][d]) ans[tx][ty][d]=ans[x][y][d],q.push_back(mp(tx,ty,d)); } const int mn=*min_element(ans[bx][by],ans[bx][by]+4); printf("%d",(mn==inf)?-1:mn); return 0; }
F
相当于求并集,考虑容斥,而 \(n\) 很小,可直接枚举钦定必须包含于哪些串中;对于有 \(k\) 个可供使用的字符,那么方案数即为 \(k^L\)。
int n,l,ans; char s[25]; bitset<26> b[25]; signed main(){ cin>>n>>l; const int S=(1<<n); for(rg int i=1;i<=n;++i){ scanf("%s",s+1); const int len=strlen(s+1); for(rg int j=1;j<=len;++j) b[i][s[j]-'a']=1; } for(rg int i=1;i<S;++i){ bitset<26> now; now.set(); int cnt=0; for(rg int j=0;j<n;++j) if((i>>j)&1) now&=b[j+1],++cnt; if(cnt&1) ans=(ans+ksm(now.count(),l))%djq; else ans=(ans-ksm(now.count(),l)+djq)%djq; } printf("%d",ans); return 0; }
G
假设最后答案为 \(v\),考虑如何实现选到 \(v\) 的过程:设 \(f_{v,x}\) 表示已经走到节点 \(x\),之后能有几个取到 \(v\) 的选择。若 \(a_x=v\) 则为一种方案(已经走到了节点 \(x\),自己是先手,对方已经无法清零 \(x\)),然后只能在 \(subtree_x\) 内选取,此时对方有一次机会将 \(subtree_x\) 内某个值为 \(v\) 的点删掉,那么就可以得到 \(f_{v,x}=\max(0,-1+\sum_{y\in son_x}f_{v,y})+[a_x=v]\)
然后这个 sb 写了线段树合并然后发现答案其实满足满足单调性,将 \(=v\) 的限制换为 \(\geq v\) 的限制后就可以直接二分 \(v\)。
int n,a[200005],f[200005]; vec e[200005]; void dfs(int x,int fa,const int v){ for(int y:e[x]) if(y!=fa) dfs(y,x,v),f[x]+=f[y]; f[x]=max(f[x],0),f[x]+=(a[x]>=v); } bool calc(int v){ return memset(f,-1,sizeof(f)),dfs(1,0,v),f[1]; } signed main(){ n=read(); for(rg int i=2;i<=n;++i) a[i]=read(); for(rg int i=1,u,v;i<n;++i) u=read(),v=read(),e[u].epb(v),e[v].epb(u); int l=0,r=1000000000; while(l<r){ const int mid=(l+r+1)>>1; if(calc(mid)) l=mid; else r=mid-1; } printf("%d",l); return 0; }
Ex
不会,摆烂。
(还真 tm 是 ddp 啊,说好的老外不会科技的呢?)
这篇关于ABC246 简要题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01UniApp 中组件的生命周期是多少-icode9专业技术文章分享
- 2024-11-01如何使用Svg Sprite Icon简化网页图标管理
- 2024-10-31Excel数据导出课程:新手从入门到精通的实用教程
- 2024-10-31Excel数据导入课程:新手入门指南
- 2024-10-31RBAC的权限课程:新手入门教程
- 2024-10-31Svg Sprite Icon课程:新手入门必备指南
- 2024-10-31怎么配置 L2TP 允许多用户连接-icode9专业技术文章分享
- 2024-10-31怎么在FreeBSD上 安装 OpenResty-icode9专业技术文章分享
- 2024-10-31运行 modprobe l2tp_ppp 时收到“module not found”消息提醒是什么-icode9专业技术文章分享
- 2024-10-31FreeBSD的下载命令有哪些-icode9专业技术文章分享