CoreJava 新闻api map转string 做推广 wcf loam算法测试 requirejs php零基础入门视频 sql视频教程 广告投放系统源码 jquery遍历元素 jq遍历元素 当前线程等待5秒 hbase集群搭建 coreldraw入门学习 idea全文搜索快捷键 matlab插值函数 android网络请求 python开发教程 python文件操作 python定义变量 python网页编程 python设置环境变量 python安装模块 java中的对象 java学习基础 javaabstract bat脚本 java游戏编程 手机模拟器下载 tampermonkey 0x00000057 js获取数组长度 抠图软件免费版 绘图软件下载 autocad2004迷你版 ftp客户端软件 平均值符号怎么输入 ps蒙版抠图 快剪辑怎么录制视频
当前位置: 首页 > 学习教程  > 编程语言

Codeforces Round #701 (Div. 2) 补题 AB

2021/2/13 18:21:18 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

A. Add and Divide 分析&#xff1a; 暴力枚举bxbxbx的每个操作次数&#xff0c;只需要枚举log2(109)29log_2(10^9)29log2​(109)29次 代码&#xff1a; #include<bits/stdc.h> using namespace std; int t,a,b; int main(){cin>>t;while(t--){int ans1000;cin&g…

A. Add and Divide

在这里插入图片描述
分析: 暴力枚举 b + x b+x b+x的每个操作次数,只需要枚举 l o g 2 ( 1 0 9 ) = 29 log_2(10^9)=29 log2(109)=29

代码:

#include<bits/stdc++.h>
using namespace std;
int t,a,b;
int main(){
    cin>>t;
    while(t--){
        int ans=1000;
        cin>>a>>b;
        int tmp=b;
        if(tmp==1) tmp++;
        for(int i=tmp;i<tmp+30;i++){
            int res=0,ta=a;
            while(ta>=i){
                ta/=i;
                res++;
            }
            ans=min(res+1+i-b,ans);
        }
        cout<<ans<<endl;
    }
}

B. Replace and Keep Sorted

在这里插入图片描述

分析:
结论: 答 案 : k + a [ r ] − a [ l ] − 1 − 2 r + 2 l 答案:k+a[r]-a[l]-1-2r+2l k+a[r]a[l]12r+2l

推导:
设左区间为 l l l,右区间为 r r r
对于左区间端点:
a [ l ] − 1 a[l]-1 a[l]1
对于右区间端点:
k − a [ r ] k-a[r] ka[r]
其他点 i i i
( a [ i ] − a [ i − 1 ] − 1 ) + ( a [ i + 1 ] − a [ i ] − 1 ) (a[i]-a[i-1]-1)+(a[i+1]-a[i]-1) (a[i]a[i1]1)+(a[i+1]a[i]1)
= a [ i + 1 ] − a [ i − 1 ] − 2 =a[i+1]-a[i-1]-2 =a[i+1]a[i1]2
为什么不用计算左右端点的另一边?因为下一个点/上一个点还会计算差值

累加:
∑ i = l + 1 r − 1 a [ i + 1 ] − a [ i − 1 ] − 2 \sum_{i=l+1}^{r-1}a[i+1]-a[i-1]-2 i=l+1r1a[i+1]a[i1]2
= a [ r ] − a [ l ] − 2 ( r − l − 1 ) =a[r]-a[l]-2(r-l-1) =a[r]a[l]2(rl1)
加上两个端点的值:
k + a [ r ] − a [ l ] − 1 − 2 r + 2 l k+a[r]-a[l]-1-2r+2l k+a[r]a[l]12r+2l

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,q,k,a[N],l,r;
int main(){
    cin>>n>>q>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    while(q--){
        cin>>l>>r;
        cout<<k+a[r]-a[l]-1-2*r+2*l<<endl;
    }
}

本文链接: http://www.dtmao.cc/news_show_700249.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?