CF 训练2

news/2024/11/13 5:32:14/

688 div2 C Balanced Bitstring

思路:首先对于区间问题 , 我们可以先思考让它滑动滑动。对于[l,r],向后滑动一位后 ,[l+1 , r+1],因为两次的区间中 , [l+1 ,r]中所有数都是相同的 , 所以 可以得到s[l] = s[r+1] , 那么再向后滑动 , 就有 l+1 = r+2 , 一次类推 , 在1 ~ k中 , 每个数每次 +k , s[x] = s[x+k]的。那么我们就可以对于每个k的区间来进行处理 , 观察它们是否相同。但是对于 ? 的话 ,我们可以先不管他,最后看
1和0的个数是否都 <= k/2 就行了

void solve(){cin>>n>>k;string s;cin>>s;s = '#' + s;for(int i =1;i<=k;++i)str[i] = 0;for(int i=1;i<=k;++i){for(int j =i;j<=n;j +=k){if(s[j] == '?')continue;if(str[i] == 0)str[i] = s[j];else if(str[i] != s[j]){cout<<"NO"<<endl;return;}}}int cnt1 = 0 , cnt0 = 0;for(int i =1;i<=k;++i){if(str[i] == '1')cnt1++;else if(str[i] == '0')cnt0++;}if(cnt1 <=k/2 && cnt0 <= k/2){cout<<"YES"<<endl;return;}cout<<"NO"<<endl;
}

688 div2 D Tree Tag

思路:首先如果一开始 a和b的距离小于 da , 那么爱丽丝赢 。 如果b被追到了死角 , 那么必须db > 2*da 。 最后需要树有一段很长的距离,足够b来躲掉a,也就是树的直径 > 2a,bob才有可能赢

void dfs(int u , int fa){ for(auto to : g[u]){if(vis[to] || to == fa)continue;dis[to] = dis[u] + 1;vis[to] = 1;dfs(to , u);}
}void solve(){cin>>n>>a>>b>>da>>db;for(int i =1;i<=n;++i)g[i].clear();for(int i =1;i<n;++i){int u ,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u); }for(int i =1;i<=n;++i)vis[i] = 0 , dis[i] =  0;dis[a] = 0;dfs(a , 0);if(dis[b] <= da){cout<<"Alice"<<endl;return;}int ma = -1 , Q = 0;for(int i =1;i<=n;++i){if(dis[i] > ma)ma = dis[i] , Q =i;}for(int i =1;i<=n;++i)vis[i] = 0 , dis[i] =  0;dfs(Q , 0);ma = -1;for(int i =1;i<=n;++i){if(dis[i] > ma)ma = dis[i];}if(2 * da >= db){cout<<"Alice"<<endl;return;}cout<<"Bob"<<endl;}

962 div3 E Decode

思路 :还是区间01的问题 , 我们可以把0当作-1 , 1当作 1,如果区间中0和1的数量相等 , 那么就说明区间和为 0 ,对于一个区间为0的区间,我们思考它对答案的贡献。

假设区间为[l,r]的这样一段区间,它对答案的贡献是多少 , 首先左边的贡献是 l , 右边的贡献是 n-r+1 , 根据乘法原理 , 贡献为l*(n-r+1)。 

如何找区间 ,根据前缀和思想 , pre[r] - pre[l-1] = 0 -> pre[l-1] = pre[r]。那么接下来,可以用一个map进行优化 , 时间复杂度就应该是 Onlogn

void solve(){cin>>s;int n = s.size();s = '#' + s;for(int i =1;i<=n;++i)pre[i] = pre[i-1] + (s[i]=='1' ?1 : -1 );map<int,int>mp;int ans = 0;mp[0] =1;for(int i =1;i<=n;++i){ans +=(mp[pre[i]])*(n-i+1);mp[pre[i]] += (i+1); mp[pre[i]]%= mod;ans %= mod;}cout<<ans<<endl;
}

962 div3 F Bomb

思路: 观察到数据非常大 , k 是1e9 , 那么k次的优先队列询问肯定是不行了。这题其实是个很典的题,我们可以二分出来最后每个数的最大值,也就是说,每个数最后肯定会减到 那个最大值或者大于最大值。
那么对于如何二分,我们思考到 , 二分出来的x 越大 ,我们所需要减少的次数cnt 就越少,cnt <= k的话,x就有一个最小值 , 所以是在分界线的右边  ,当我们的cnt >= k 的话就需要 l  = mid , 否则
r = mid -1;
对于每个数可以用掉的次数为 cnt = (ai - x) / bi + 1,那么构成一个等差数列,其中的和也很容易算出来。

还有一个细节就是最后我们用掉的次数可能小于k ,那么多出来的这几次 直接×二分出来的x即可

void solve(){cin>>n>>k;for(int i =1;i<=n;++i)cin>>a[i];for(int i =1;i<=n;++i)cin>>b[i];auto check =[&](int x){int cnt = 0;for(int i =1;i<=n;++i){if(a[i] >= x){cnt += (a[i]-x)/b[i] + 1;}}return cnt >= k;};int l=0 ,r = 2e10;while(l < r){int mid = (l+r+1)>>1;if(check(mid))l =mid;else r = mid -1;}int cnt = 0;int sum = 0;for(int i= 1;i<=n;++i){if(a[i] >= l){int m =(a[i]-l)/b[i] + 1;sum += a[i]*m - m*(m-1)*b[i]/2;cnt += m;}}cout<<sum + l*(k - cnt)<<endl;
}

很细节的一道题 , 多多思考🤔。


http://www.ppmy.cn/news/1505460.html

相关文章

【C++ | 泛型编程】C++函数模板详解(定义、使用、特化、重载)

&#x1f601;博客主页&#x1f601;&#xff1a;&#x1f680;https://blog.csdn.net/wkd_007&#x1f680; &#x1f911;博客内容&#x1f911;&#xff1a;&#x1f36d;嵌入式开发、Linux、C语言、C、数据结构、音视频&#x1f36d; &#x1f923;本文内容&#x1f923;&a…

基于Orangepi全志H616学习Python3

目录 一、功能需求 二、Python的安装和环境搭建 三、Python的基础学习 3.1 Python的特点&#xff1a; 3.2 编写并运行第一个Python程序&#xff1a; 3.3 标识符&#xff1a; 3.4 关键字&#xff1a; 3.5 注释&#xff1a; 3.6 行与缩进&#xff1a; 3.7 多行语句&…

医院不良事件监测预警上报系统,PHP不良事件管理系统源码

不良事件上报系统&#xff0c;支持医院进行10大类医疗安全&#xff08;不良&#xff09;事件的上报管理&#xff1b;帮助医院管理部门更好把控不良事件的发生趋势&#xff0c;分析医院内部潜在的问题和风险&#xff0c;采取适当的管理措施&#xff0c;有效加强质量控制&#xf…

【Material-UI】Autocomplete 组件中的虚拟化功能(Virtualization)详解

文章目录 一、虚拟化概述二、实现虚拟化的步骤1. 引入依赖2. 自定义 Popper 组件和 Listbox 组件3. 代码详解4. 性能优化 三、实际应用场景1. 大规模数据列表2. 高性能需求的应用 四、总结 在现代 Web 开发中&#xff0c;处理大量数据时&#xff0c;性能优化显得尤为重要。Mate…

揭秘LoRA:利用深度学习原理在Stable Diffusion中打造完美图像生成的秘密武器

文章目录 引言LoRA的原理LoRA在角色生成中的应用LoRA在风格生成中的应用LoRA在概念生成中的应用LoRA在服装生成中的应用LoRA在物体生成中的应用结论 引言 在生成式人工智能领域&#xff0c;图像生成模型如Stable Diffusion凭借其出色的生成效果和广泛的应用场景&#xff0c;逐…

Android 多语言切换

文章目录 在系统设置修改语言创建资源目录创建资源文件示例验证 代码手动切换语言在Application中设置新的语言环境在MainActivity / BaseActivity中设置新的语言环境验证 问题1. makeText()方法context传入是Application的context&#xff0c;无法获取正确的资源字符串原因解决…

[Git] fatal: the remote end hung up unexpectedly

1 问题介绍 在使用Git进行代码管理和版本控制的过程中&#xff0c;许多开发者可能会遇到这样一个错误提示&#xff1a;fatal: the remote end hung up unexpectedly。这是一种常见的错误&#xff0c;通常出现在将本地代码推送&#xff08;push&#xff09;到远程仓库&#xff…

C语言——预处理和指针

C语言——预处理和指针 预处理宏宏定义宏的作用域带参的宏 文件包含条件编译 指针指针的概念指针的定义指针变量初始化指针一维整型数组 预处理 编程的流程分为&#xff1a;编辑、编译、运行、调试四个阶段&#xff1b; 预处理属于编译阶段&#xff0c;编译过程又可以分为&…