首页 > 其他分享 >CF1834 Div.2 做题记录

CF1834 Div.2 做题记录

时间：2023-06-27 16:25:34浏览次数：45  
标签：ch 记录 int void long write CF1834 Div.2 define

A

题面

分类讨论即可

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
int n,s1,s2;
void solve(){
    read(n);
    s1=0,s2=0;
    for(int i=1;i<=n;i++){
        int x;
        read(x);
        if(x==1){
            s1++;
        }
        else{
            s2++;
        }
    }
    if(s2%2==0){
        if(s1-s2>0){
            write_endl(0);
        }
        else{
            int delta=-(s1-s2-1)/2;
            write_endl((delta+1)/2*2);
        }
    }
    else{
        if(s1-s2>0){
            write_endl(1);
        }
        else{
            int delta=-(s1-s2-1)/2;
            if(delta%2){
                write_endl(delta);
            }
            else{
                write_endl(delta+1);
            }
        }
    }
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t;
    read(t);
    while(t--){
        solve();
    }
    return 0;
}

B

题面

容易发现，将两个数位数补齐，找到第一个不同的位置，这一位取到极差，剩下为的差的绝对值都可以取到 \(9\)。令这一位 \(L'\) 取到 \(a\)，\(R'\) 取到 \(b(b>a)\)。那么对于后面的位数 \(L'\) 取 \(9\)，\(R'\) 取 \(0\)，显然 \(L'<R'\) 且 \(L',R'\in[L,R]\)。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
void solve(){
    string s,t,S="",T="";
    cin>>s>>t;
    for(int i=0;i<s.size();i++){
        S=S+s[s.size()-i-1];
    }
    for(int i=0;i<t.size();i++){
        T=T+t[t.size()-i-1];
    }
    int len=max(s.size(),t.size());
    for(int i=s.size()+1;i<=len;i++){
        S=S+'0';
    }
    for(int i=t.size()+1;i<=len;i++){
        T=T+'0';
    }
    int ans=0;
    for(int i=len-1;i>=0;i--){
        if(S[i]!=T[i]){
            int x=S[i]-'0',y=T[i]-'0';
            ans+=abs(x-y);
            ans+=i*9;
            break;
        }
    }
    write_endl(ans);
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t;
    read(t);
    while(t--){
        solve();
    }
    return 0;
}

C

题面

因为 Bob 只能在两个串中选择一个串操作，不能不操作，所以无论他两次操作的分别是哪两个串，两次操作后对应位还是对应，所以分类讨论 Bob 操作奇数次和偶数次，并可以得到对应时刻是 Bob 操作后结束还是 Alice 操作后结束。取较小值即可。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
int n;
string s,t;
void solve(){
    read(n);
    cin>>s>>t;
    s=' '+s;
    t=' '+t;
    int tot1=0,tot2=0;
    for(int i=1;i<=n;i++){
        if(s[i]!=t[i]){
            tot1++;
        }
    }
    for(int i=1,j=n;i<=n;i++,j--){
        if(s[i]!=t[j]){
            tot2++;
        }
    }
    int ans=1e9;
    if(tot1%2){
        ans=min(ans,tot1*2-1);
    }
    else{
        if(tot1==0){
            ans=min(ans,0);
        }
        else{
            ans=min(ans,tot1*2);
        }
    }
    if(tot2%2){
        ans=min(ans,tot2*2);
    }
    else{
        if(tot2==0){
            ans=min(ans,2);
        }
        else{
            ans=min(ans,tot2*2-1);
        }
    }
    write_endl(ans);
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t;
    read(t);
    while(t--){
        solve();
    }
    return 0;
}

D

题面

如果给到最后造成极差的两个区间，考虑分类，两个区间是包含关系，相交关系，相离关系。

  • 对于包含的情况，答案只有可能大区间的长度减去小区间的长度。
  • 对于相离的情况，答案只有可能是大区间的长度。
  • 对于相交的情况，答案为大区间的长度减去相交的长度，但这个不是很好处理，考虑转化为左边未相交的部分的长度和右边未相交部分的长度中的较大值，即 \(\max(l_i-l_j,r_i-r_j)\)。

于是我们有了一个简单的思路。将所有区间以右端点为关键字从小到大排序。通过二分可以找到相离的区间有哪些，这是一段前缀，我们可以动态维护前缀区间长度最大值。剩下的一段前缀的后缀里面有相交和包含关系的区间。根据前面的分析，我们可以用树状数组维护到 \(i-1\) 时，一段后缀中左端点的最小值，右端点的最小值，区间长度的最小值。

这里有一个问题，为什么我们不需要考虑将信息分相离和相交来维护。考虑如果一个被包含的区间 \(j\) 去用相交的答案计算方式去算会不会使答案变大，答案是不会。\(l_i-l_j\le 0\) 而 \(r_i-r_j\le r_i-r_j+l_j-l_i\)，故而答案不会更大。相交的线段用包含的方式去计算的答案也不会更大，所以直接用树状数组维护到 \(i-1\) 时，每个后缀的信息即可。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=2e5+10;
int n,m;
struct seg{
    int l,r;
}s[N];
bool cmp(seg x,seg y){
    return x.r==y.r?x.l<y.l:x.r<y.r;
}
int c1[N],c2[N],c3[N],c4[N];
int lowbit(int x){
    return x&(-x);
}
void update1(int pos,int val){
    while(pos<=n){
        c1[pos]=max(val,c1[pos]);
        pos+=lowbit(pos);
    }
}
int query1(int pos){
    int ans=0;
    while(pos){
        ans=max(ans,c1[pos]);
        pos-=lowbit(pos);
    }
    return ans;
}
void update2(int pos,int val){
    pos=n-pos+1;
    while(pos<=n){
        c2[pos]=min(c2[pos],val);
        pos+=lowbit(pos);
    }
}
int query2(int pos){
    pos=n-pos+1;
    int ans=1e9;
    while(pos){
        ans=min(ans,c2[pos]);
        pos-=lowbit(pos);
    }
    return ans;
}
void update3(int pos,int val){
    pos=n-pos+1;
    while(pos<=n){
        c3[pos]=min(c3[pos],val);
        pos+=lowbit(pos);
    }
}
int query3(int pos){
    pos=n-pos+1;
    int ans=1e9;
    while(pos){
        ans=min(ans,c3[pos]);
        pos-=lowbit(pos);
    }
    return ans;
}
void update4(int pos,int val){
    pos=n-pos+1;
    while(pos<=n){
        c4[pos]=min(c4[pos],val);
        pos+=lowbit(pos);
    }
}
int query4(int pos){
    int ans=1e9;
    pos=n-pos+1;
    while(pos){
        ans=min(ans,c4[pos]);
        pos-=lowbit(pos);
    }
    return ans;
}
void solve(){
    read(n),read(m);
    for(int i=1;i<=n;i++){
        c1[i]=0;
        c4[i]=c2[i]=c3[i]=1e9;
        read(s[i].l),read(s[i].r);
    }
    sort(s+1,s+n+1,cmp);
    int ans=0;
    for(int i=1;i<=n;i++){
        int l=1,r=i-1,pos=0;
        while(l<=r){
            int mid=(l+r)>>1;
            if(s[mid].r<s[i].l){
                pos=mid;
                l=mid+1;
            }
            else{
                r=mid-1;
            }
        }
        ans=max(ans,max(query1(pos),(s[i].r-s[i].l+1)*(pos>0)));
        ans=max(ans,max(s[i].l-query2(pos+1),s[i].r-query3(pos+1)));
        ans=max(ans,s[i].r-s[i].l+1-query4(pos+1));
        update1(i,s[i].r-s[i].l+1);
        update2(i,s[i].l);
        update3(i,s[i].r);
        update4(i,s[i].r-s[i].l+1);
    }
    write_endl(ans*2);
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t;
    read(t);
    while(t--){
        solve();
    }
    return 0;
}

E

题面

已知第 \(300001\) 个质数为 \(4256233\)，所以大于等于该数的 \(\operatorname{lcm}_{[l,r]}\) 值均为无效。给定 \(x\) 和 \(y\)，\(\operatorname{lcm}(x,y)\) 和 \(x\) 相比，要么不变，要么至少翻倍。所以给定一个 \(r\)，\(\operatorname{[l,r]}\) 不重且有效的 \(l\) 最多只有 \(\log\) 个。枚举 \(r\)，用 set 维护小于 \(4256233\) 的 \(\operatorname{[l,r-1]}\)，总复杂度为 \(O(n\log^2 V)\)，其中 \(V\) 表示值域。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T &x){
        x=0;
        int f=1;
        char ch=getchar();
        while(ch>'9'||ch<'0'){
            if(ch=='-'){
                f=-1;
    }
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+(ch-'0');
            ch=getchar();
        }
        x=(f==1?x:-x);
    }
    template<typename T>
    inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>=10){
            write(x/10);
        }
        putchar(x%10+'0');
    }
    template<typename T>
    inline void write_endl(T x){
        write(x);
        putchar('\n');
    }
    template<typename T>
    inline void write_space(T x){
        write(x);
        putchar(' ');
    }
}
using namespace IO;
const int N=3e5+10,MX=4256233;
int n,a[N];
set<int>now,lst,ans;
int lcm(int x,int y){
    return x/__gcd(x,y)*y;
}
void solve(){
    read(n);
    set<int>().swap(ans);
    set<int>().swap(lst);
    for(int i=1;i<=n;i++){
        read(a[i]);
    }
    for(int i=1;i<=n;i++){
        set<int>().swap(now);
        now.insert(a[i]);
        for(auto x:lst){
            int s=lcm(x,a[i]);
            if(s<=MX){
                now.insert(s);
            }
        }
        set<int>().swap(lst);
        for(auto x:now){
            lst.insert(x);
            ans.insert(x);
        }
    }
    int mex=1;
    while(ans.count(mex)){
        mex++;
    }
    write_endl(mex);
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t;
    read(t);
    while(t--){
        solve();
    }
    return 0;
}

标签：ch,记录,int,void,long,write,CF1834,Div.2,define
From： https://www.cnblogs.com/luoshen0/p/17507528.html

相关文章

  • git冲突报错记录
    (base)kaka@KakadeMacBook-Prodatahub-aws%gitpullwarning:redirectingtohttps://source.fundpark.com/FP-IT/datahub-aws.git/Updating24a2e479..f588ccbberror:Yourlocalchangestothefollowingfileswouldbeoverwrittenbymerge:code/Comman......
  • Git 如何将现在修改追加到之前提交的提交记录上
    重要：操作前，请做好备份暂存某个文件的命令gitstash--文件路径将本地所有修改先暂存起来gitstashgitlog找到想要追加的commitid的前一次提交的idgitrebase-i想追加的commid的前一次的commitid弹出的框中将要修改的commit记录前的pick修改为edit(如果是想删......
  • 0308记录之前的一些问题
    1.头文件里可以进行同名声明，编译可通过。2. initializerelementisnotconstant：全局变量是保存在静态存储区的，因此在编译的时候只能用常量进行初始化，而不能用变量进行初始化。全局变量的内存地址直接存储变量的值。3.线程的属性可通过pthread_attr_init进行设定，pthread_a......
  • OE引领学员向世界500强企业学习 《刷下最大的企业游学团记录大全》
    2023年6月5号，OE杰青商学院率领近200位学员到中国游学，创下了马来西亚纪录大全《最多人参与的企业游学团》。这次游学团的联办单位有中国国际贸易学会区域经贸合作工作委员会、启迪环宇创新（北京）科技有限公司、中国会展网及旅游与媒体GoTraz。OE杰青商学院创办人兼董事长DatukWira......
  • 实际案例分析 - 根据应用程序日志的记录，反查出哪一行 ABAP 代码产生的这条日志试读版
    本文的写作动机来自笔者知识星球一个朋友的提问：调用bapi创建主数据的时候报错，没有未物料组分配特性参数文件，这个是什么原因？实际查看，特性文件已经生成了这个朋友提供的是应用程序日志(即ApplicationLog)里的截图。关于应用程序日志的详细用法，笔者之前的文章已经做过介绍。......
  • 记录--巧用 overflow-scroll 实现丝滑轮播图
    这里给大家分享我在网上总结出来的一些知识，希望对大家有所帮助前言:近期我在项目中就接到了一个完成轮播图组件的需求。最开始我也像大家一样，直接选择使用了知名的开源项目"Swiper"，但是后来发现它在移动端项目中某些测试环境下会白屏一段时间。无论如何调试都不能修复这个问......
  • 记录去重保留一条和联表删除的排坑过程
    因为接触的数据库比较多，各个库之间有些细节有出入没有注意就会踩坑一、场景要求生产库中有一张主表tbl_invoice_xbk5和明细表tbl_invoice_item_xbk5，关联字段是主表的INV_ID和明细表的ID对应，由于前期设计缺陷，发现主表中INVOICE_NO字段有重复数据，需要去重只保留一条，且对应的明细......
  • html2canvas使用记录
    1.生成图片有白边/黑边设置backgroundColor:#ffffff2.本地生成图片没有白边/黑边，打包后生成图片有白边/黑边查看打印容器/父级是否有定位，宽度过大/过小等，去掉定位或限宽3.生成图片模糊设置scale参数4.文字错位设置字体5.外链图片不显示设置useCors:true，同时将打印区的......
  • Windows Common Log File System (CLFS) Driver，也称为CLFS.sys，是Windows操作系统中的
    WindowsCommonLogFileSystem(CLFS)Driver，也称为CLFS.sys，是Windows操作系统中的一个驱动程序。它提供了一个通用的日志文件系统框架，用于记录和管理系统、应用程序和服务的日志。CLFS.sys文件的路径通常位于Windows操作系统的系统目录中。具体的路径取决于安装Windows的......
  • Nginx反向代理&记录用户IP地址企业案例
    反向代理机器节点：lb0110.0.0.30#lb01是反向代理服务器（包括负载均衡的功能）www0110.0.0.40www0210.0.0.50【演示反向代理功能】 图片解读：使用客户端机器www01，访问负载均衡lb01（反向代理），看到了www01，www02页面信息在www01服务器上检测客户端信息，发现请求是10.0.0.3......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99