当前位置: 首页 > news >正文

CF2139虚拟游记

前言

CF2139 \(Div.2\) 难度。
由于刚上大学,开学有很多活动,连参加 vp 的时间都挤不出来。

A.Maple and Multiplication

题面

\(t\) 组数据,每组数据:
给定两个数 \(a,b\) ,你可以进行任意次操作:

  • 选择一个整数 \(x\) ,然后令 \(a\)\(b\) 乘以 \(x\)
    求使得 \(a=b\) 的最小操作次数。

思路

非常显然,不妨设 \(a\ge b\) ,则有:

  1. \(a=b\) ,则最少 \(0\) 次;
  2. \(b|a\) ,则最少 \(1\) 次 (\(x_b=\frac{a}{b}\)) ;
  3. 否则 \(2\) 次 (\(x_b=a,x_a=b\)) 。

实现

#include<iostream>
using namespace std;
int tt,a,b;
void solve(){cin>>a>>b;if(a<b)swap(a,b);if(a==b)puts("0");else if(a%b==0)puts("1");else puts("2");
}
int main(){cin>>tt;while(tt--)solve();return 0;
}

B.Cake Collection

题面

\(t\) 组数据,每组数据:
一共有 \(n\) 个烤箱,每个烤箱 \(i\) 每秒能烤出 \(a_i\) 个蛋糕,你在每一秒可以走到一个烤箱处,然后收集里面的所有蛋糕。
问在 \(m\) 秒内最多收集多少蛋糕。

思路

很简答,直接贪心:
将烤箱按照烤蛋糕个数从大到小排,然后遍历 \({a_n}\) 直到遍历完或 \(m=0\)
ans+=m*a[i] ,然后 --m 即可。

实现

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+5;
int tt,n,m,a[N];
long long ans;
void solve(){cin>>n>>m;ans=0;for(int i=1;i<=n;++i)cin>>a[i];sort(a+1,a+1+n,[](int x,int y){return x>y;});for(int i=1;i<=n;++i){if(m==0)break;ans+=1ll*m*a[i];--m;}cout<<ans<<endl;
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>tt;while(tt--)solve();return 0;
}

C.Cake Assignment

题面

\(t\) 组数据,每组数据:
给定两个整数 \(n,k\) ,你需要进行若干次操作:
刚开始 \(a=b=2^k\),你可以进行如下操作:

  1. \(b\leftarrow b+\frac{a}{2},a\leftarrow\frac{a}{2}\)
  2. \(a\leftarrow a+\frac{b}{2},b\leftarrow\frac{b}{2}\)
    使得最终 \(a=n\)

思路

场上思路

首先我们发现答案肯定和二进制有关。
\(n\) 的最低位 \(1\) 决定操作次数。

证明
定义 \(llb(x)=\log_2(lowbit(x))\)
刚开始时 \(llb(a)=llb(b)=k\)
于是 \(llb(\frac{a}{2})=llb(\frac{b}{2})=k-1\)
则有 \(a'=\frac{a}{2}/a+\frac{b}{2},b'=b+\frac{a}{2},\frac{b}{2}\)
\(llb(a')=llb(b')=k-1\)
同理可得 \(llb(a^{(n)})=llb(b^{(n)})=k-n\)

然后将所有数转化为二进制后,我们发现对于 \(n\) 将其右移至 \(llb(n')=0\) 再将其右移一位后
从小到大遍历 \(n'\) 的二进制数码 \(s\) ,输出 \(s_i+1\) 即可。
但是我也不会证。

题解

我们发现:

  • 执行 \(1\) 操作后 \(a>2^k\)
  • 执行 \(2\) 操作后 \(b>2^k\)

证明
只考虑 \(1\) 操作:
因为 \(a+b=2^{k+1}\)
\(a'=a+\frac{b}{2}=\frac{a}{2}+\frac{a+b}{2}=\frac{a}{2}+2^k>2^k\)
我们倒推即可。
好像我的做法也可以这么证明。

实现

场上

#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int tt;
ll k,x,c;
void solve(){cin>>k>>x;c=0;while(x%2==0){x>>=1;++c;}x>>=1;cout<<k-c<<endl;for(int i=1;i<=k-c;++i){if(x&(1ll<<i-1))cout<<"2 ";else cout<<"1 ";}cout<<endl;
}
int main(){cin>>tt;while(tt--)solve();return 0;
}

题解

#include<iostream>
#include<stack>
#define ll long long
using namespace std;
int tt;
ll a,b,k;
stack<int>ans;
void solve(){cin>>k>>a;b=(1ll<<k+1)-a;while(a!=1ll<<k){if(a>1ll<<k){ans.push(2);a-=b;b<<=1;}else{ans.push(1);b-=a;a<<=1;}}cout<<ans.size()<<endl;while(!ans.empty()){cout<<ans.top()<<" ";ans.pop();}cout<<"\n";
}
int main(){cin>>tt;while(tt--)solve();return 0;
}

D.Antiamuny Wants to Learn Swap

题面

定义
对于一个数列 \(A=\{a_n\}\)
给定两种操作:

  1. 选择一个下标 \(2\le i \le n\) ,然后交换 \(a_i,a_{i-1}\)
  2. 选择一个下标 \(3\le i \le n\) ,然后交换 \(a_i,a_{i-2}\)

我们定义:
\(f(A)\) 为只进行 1. 操作,使得 \(A\) 变为单调不降序列的最小操作次数。
\(g(A)\) 为进行至多 \(1\) 次 2. 操作与若干次 1. 操作,使得 \(A\) 变为单调不降序列的最小操作次数。
然后若 \(f(A)=g(A)\) 则称 \(A\)好的数列。

\(t\) 组数据,每组数据:
给定一个 \(n\) 的排列 \(a_n\)\(m\) 组询问 \((l_i,r_i)\)
你需要判断 \(\{a_l,...,a_r\}\) 是否为好的数列。
\(\sum n \le 5\times 10^5\)

思路

首先我们可以发现一个性质:
若存在 $1\le i < j < k \le n $ 满足 \(a_i>a_j>a_k\) ,则数列 \(\{a_n\}\) 一定不是好的数列,反之亦然。
我们对于每个 \(i\) 预处理出最小的满足上述条件的 \(R[i]=k\)
那么若 \(r<R[l]\) 就输出 Yes

实现

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=5e5+5;
int tt,n,sqn,m;
int a[N],mxl[N],mnr[N],R[N],l,r;
void solve(){cin>>n>>m;for(int i=1;i<=n;++i){cin>>a[i];mxl[i]=i-1;R[i]=n+1;while(mxl[i]>=1&&a[mxl[i]]<a[i])mxl[i]=mxl[mxl[i]];}for(int i=n;i>=1;--i){mnr[i]=i+1;while(mnr[i]<=n&&a[mnr[i]]>a[i])mnr[i]=mnr[mnr[i]];}for(int i=2;i<n;++i){if(mxl[i]>0&&mnr[i]<=n){R[mxl[i]]=min(R[mxl[i]],mnr[i]);}}R[n+1]=n+1;for(int i=n;i>=1;--i)R[i]=min(R[i+1],R[i]);for(int i=1;i<=m;++i){cin>>l>>r;if(r<R[l])cout<<"Yes\n";else cout<<"No\n";}
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>tt;while(tt--)solve();return 0;
}

E1.Maple and Tree Beauty (Easy Version)

题面

\(t\) 组数据,每组数据:
给定一颗以 \(1\) 为根的大小为 \(n\) 的树,以及一个整数 \(k\)
你需要给树上每个节点染上 \(1,0\) 颜色,其中恰好有 \(k\) 个颜色 \(1\)
对于叶子节点 \(i\) ,定义 \(s_i\) 为从根到 \(i\) 的路径上的节点颜色组成的字符串
你需要最大化 \(LCS(s_i)\) 的长度。

思路

首先我们发现,我们只需要最大化最长公共前缀 \(S\) 的长度即可。
我们可以贪心地证明:
因为若 \(s_{i,j}=S_{k}\) ,则必有 \(k\le j\) ,如果 \(s_{i,j}\ne S_{k}\) ,则与 \(S_{k}\) 相等的任务就交给了 \(i\) 的深度为 \(j\) 的节点 \(u\) 的儿子。
而其儿子节点的个数一定不小于 \(1\) ,于是所需染色的点更多。
那么我们可以直接 DP 。

实现

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const int N=1005;
vector<int>g[N];
int tt,n,k,a[N],h,sum;
bool dp[N],flag;
void dfs(int u,int d){++a[d];if(!g[u].size())h=min(h,d);for(auto v:g[u])dfs(v,d+1);
}
void solve(){int x;cin>>n>>k;for(int i=1;i<=n;++i){a[i]=dp[i]=0;g[i].clear();}for(int i=2;i<=n;++i){cin>>x;g[x].push_back(i);}h=n;dfs(1,1);dp[0]=1;sum=0;for(int i=1;i<=h;++i){for(int j=sum;j>=0;--j)dp[j+a[i]]|=dp[j];sum+=a[i];}if(sum<=k||sum<=n-k){cout<<h<<endl;return;}for(int i=0;i<=sum;++i){if(dp[i]){if(i<=k&&sum-i<=n-k){cout<<h<<endl;return;}}}cout<<h-1<<endl;
}
int main(){cin>>tt;while(tt--)solve();return 0;
}

E.Maple and Tree Beauty (Hard Version)

题面

和 E1 不同的是, \(1\le k\le n\le 2\times 10^5\)

思路

E1 的题解中, \(dp\) 数组只储存了 \(0/1\) ,可以使用 bitset 维护。
复杂度 \(O(\frac{n^2}{\omega})\) ,可以通过这题。
官方题解中使用了根号分类的思想,将复杂度降低至 \(O(\frac{n\sqrt{n}}{\omega}\)

实现

#include<iostream>
#include<bitset>
using namespace std;
const int N=2e5+5;
int tt,n,k,h,a[N],dep[N],son[N],sum;
bitset<N>dp;
void solve(){int x;cin>>n>>k;for(int i=1;i<=n;++i){a[i]=son[i]=0;}h=n;sum=0;dp.reset();dp[0]=1;dep[1]=1;a[1]=1;for(int i=2;i<=n;++i){cin>>x;++a[dep[i]=dep[x]+1];son[x]=1;}for(int i=2;i<=n;++i){if(!son[i])h=min(h,dep[i]);}for(int i=1;i<=h;++i){dp|=dp<<a[i];sum+=a[i];}if(sum<=k||sum<=n-k){cout<<h<<endl;return;}for(int i=1;i<=sum;++i){if(dp[i]&&i<=k&&sum-i<=n-k){cout<<h<<endl;return;}}cout<<h-1<<endl;
}
int main(){cin>>tt;while(tt--)solve();return 0;
}
http://www.hskmm.com/?act=detail&tid=18040

相关文章:

  • 新方向 - MKT
  • 翻斗幼儿园历险记-CTF-WP
  • .net8+winform+Antdui 制作 LOL 小助手
  • 深入解析:【Git】Git 简介及基本操作
  • hutool主要内容list
  • 20250916_QQ_Powershell
  • 完整教程:HTTP安全响应头--CSP(Content-Security-Policy)
  • 原码,反码,补码
  • Experiment1
  • 读书笔记:Oracle 自动索引:让数据库自己管索引?
  • 1_2025.9.26_1
  • 故障处理:Oracle RAC集群CTSS时钟同步故障案例分析与解决
  • Linux系统提权-web/普通用户-docker逃逸提权shell交互
  • PostgreSQL技术大讲堂 - 第106讲:分区表索引优化
  • 四边形不等式优化
  • 斜率优化
  • AI智能体:从认知到实践
  • Kinect屏幕边缘检测不灵敏的解决方案
  • 暴力拓客游戏小程序:助力商家高效引流与裂变的智能解决方案
  • vue3小坑之-为什么把ref定义的数组赋值给数组对象后取值为空数组?
  • 第二类斯特林数
  • 群论
  • 扫码签到赢大奖小程序:助力多场景获客的智能营销工具
  • docker 镜像/容器
  • jmeter命令行参数详细解释
  • RK3399:性能与能效的嵌入式先锋,解锁多场景应用潜力
  • 【C++STL详解】带头双向循环结构 + 双向迭代器,核心接口 + 排序效率 + 避坑指南 - 教程
  • TorchV知识库安全解决方案:基于智能环境感知的动态权限控制
  • VBA ETH功能应用 | “0”代码构建SOME/IP节点
  • ISUP协议视频平台EasyCVR在智慧灯杆综合管理中的应用