首页 > 其他分享 >CF1338 Div.1 做题记录

CF1338 Div.1 做题记录

时间：2023-06-08 15:44:24浏览次数：50  
标签：ch 记录 int void CF1338 long write Div.1 define

A

CF题面

假定用到的最大的数是 \(x\)，那么一个数最大可以增大 \(2^x-1\)。题目只要求不降，所以求出将 \(a_i<a_{i-1}\) 变成 \(a_i=a_{i-1}\) 时需要增大的最大值。求出这个数的二进制位数即可。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pb push_back
#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=1e5+10;
int n,a[N];
void solve(){
    read(n);
    int mx=0;
    for(int i=1;i<=n;i++){
        read(a[i]);
        if(i>=2){
            mx=max(mx,a[i-1]-a[i]);
        a[i]=max(a[i],a[i-1]);
        }
    }
    int ans=0;
    while(mx){
        ans++;  
        mx>>=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;
}

B

CF题面

结论题。

先看最小值，当确定一个 \(deg\not =1\) 的点为根时，若所有叶子节点的 \(dis\) 奇偶性相同，则为 \(1\)，否则为 \(3\)。前者显然，后者考虑设计一个构造方案。令 \(dis\) 为奇数的点为奇点，\(dis\) 为偶数的为偶点。将奇点到父亲的边权赋为 \(1\)，将偶点到父亲的边权赋为 \(2\)，将剩下的边权赋为 \(3\)。这样构造，偶点到偶点和奇点到奇点的路径异或和一定为 \(0\)，对于一个奇点到偶点的路径 \((u,v)\)，\(u\) 到 \(lca\) 的距离 \(dis_{u,lca}\) 和 \(v\) 到 \(lca\) 的距离 \(dis_{v,lca}\) 必然一奇一偶，这意味着路径上会有奇数个 \(3\)，相互抵消后就是 \(1\oplus 3\oplus 2\)，异或和为 \(0\)。

再看最大值，因为权值可以赋无穷大，所以异或值相同的路径有很多种，我们需要考虑的只是 \(dis=2\) 的路径，即父亲相同的两个叶子节点，两个数异或和为 \(0\) 只能是两个数相同，所以一个点到叶子节点的边权必须相同。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pb push_back
#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=1e5+10;
int n,flag[N],tot[N],dis[N],x;
vector<int>e[N];
void dfs(int u,int fa){
    if(flag[u]){
        x=(dis[u]&1);
    }
    for(auto v:e[u]){
        if(v==fa){
            continue;
        }
        tot[u]+=flag[v];
        dis[v]=dis[u]+1;
        dfs(v,u);
    }
}
void solve(){
    read(n);
    for(int i=1,u,v;i<n;i++){
        read(u),read(v);
        e[u].pb(v);
        e[v].pb(u);
    }
    int rt=0;
    for(int i=1;i<=n;i++){
        if(e[i].size()!=1){
            rt=i;
        }
        else{
            flag[i]=1;
        }
    }
    dfs(rt,0);
    bool fl=0;
    for(int i=1;i<=n;i++){
        if(flag[i]){
            if(x^(dis[i]&1)){
                fl=1;
            }
        }
    }
    if(fl){
        write_space(3);
    }
    else{
        write_space(1);
    }
    int ans=n-1;
    for(int i=1;i<=n;i++){
        if(tot[i]){
            ans-=(tot[i]-1);
        }
    }
    write_endl(ans);
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}

C

CF题面

规律题。

通过打表找规律可以得到，三三一组，\(a\) 的值域范围只为 \(2^{2x}\sim 2^{2x+1}-1,x\in N\)，对应的 \(b\) 值域范围为 \(2^{2x+1}\sim 2^{2x+1}+2^x-1,x\in N\)，且将其划分为四块后，出现的顺序为 \(1,3,4,2\)，划分后的块依然满足这个性质。所以我们可以找到 \(a\) 属于哪个块，\(b\) 递归寻找，\(c=a^b\)。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pb push_back
#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;
struct node{
    int a,b,c;
};
int dfs(int B,int idx){
    if(!B){
        return 0;
    }
    if(idx<=B){
        return dfs(B/4,idx);
    }
    else if(idx<=2*B){
        return 2*B+dfs(B/4,idx-B);
    }
    else if(idx<=3*B){
        return 3*B+dfs(B/4,idx-B*2);
    }
    else{
        return B+dfs(B/4,idx-B*3);
    }
}
node query(int tot){
    int B=1,st=1;
    while(st+B<=tot){
        st+=B;
        B<<=2;
    }
    node res;
    res.a=B+tot-st;
    res.b=dfs(B/4,tot-st+1)+B*2;
    res.c=res.b^res.a;
    return res;
}
void solve(){
    read(n);
    node x=query((n-1)/3+1);
    if(n%3==1){
        write_endl(x.a);
    }
    else if(n%3==2){
        write_endl(x.b);
    }
    else{
        write_endl(x.c);
    }
}
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

CF题面

这场比较正常的题。

通过画图可以发现，合法的情况大概长成这个样子image
相交的图形之间有边，还原到树上，可以发现中间、间这一块大的相当于在原树上找到一个毛毛虫模型（一条链周围加几个点），求它的最大独立集。令 \(f_{u,0/1}\) 表示点 \(u\) 不选/选，最大独立集的大小。
可以写出方程式

\(f_{u,0}=\max\{\max(f_{v,0},f_{v,1})\}+(deg_u-2)\times[deg_u\ge 2]\)
\(f_{u,1}=\max\{f_{v,0}\}+1\)

其中 \(deg_u-2\) 表示忽略选择的儿子和父亲，其它儿子都可以被选择，且选择更优。答案在中途统计即可。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pb push_back
#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=1e5+10;
int n,f[N][2],ans;
vector<int>e[N];
void dfs(int u,int fa){
    f[u][0]=f[u][1]=0;
    for(auto v:e[u]){
        if(v==fa){
            continue;
        }
        dfs(v,u);
        ans=max(ans,f[u][1]+f[v][0]+1);
        ans=max(ans,f[u][0]+(int)(e[u].size())-2+max(f[v][0],f[v][1]));
        f[u][1]=max(f[u][1],f[v][0]);
        f[u][0]=max(f[u][0],max(f[v][0],f[v][1]));
    }
    f[u][1]++;
    if(e[u].size()>=2){
        f[u][0]+=e[u].size()-2;
    }
    ans=max(ans,f[u][0]);
    ans=max(ans,f[u][1]);
}
void solve(){
    read(n);
    for(int i=1;i<n;i++){
        int u,v;
        read(u),read(v);
        e[u].pb(v);
        e[v].pb(u);
    }
    dfs(1,0);
    write_endl(ans);
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}

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

相关文章

  • redis应用场景--记录文章，图文，或者视频的浏览次数
    在阅读博客文章时，你可以看到一篇文章被阅读的次数，如果使用mysql，那么在设计article表时，就必须设置一个view_count字段来记录这篇文章被阅读的次数。但这种方式相比于使用redis，并不是一种好的办法，原因在于，每次更新view_count字段的值都是一个比较费力的过程。首先，程序需要根据文......
  • C#使用webview2摸拟网页提交的一些记录
    想要在C#使用中webview2，最好使用VS2019及以上版本，最低支持.net4.5版本，所以在win7系统上就可以进行开发了ReoGrid是一个类Excel的控件，非常好用，两者搭在一起，可以实现一些自动化的输入工作，非常的方便，Excel的内容可以直接粘贴到这个控件里面 下面说说使用过程中遇到的问题：1、安......
  • OSM踩坑记录
    1.下载数据从https://www.openstreetmap.org/下载数据（如'map.osm'）2.转换格式安装gdal，我用的cudacondainstall-cconda-forgegdal如果报错可能需要回到base(退出虚拟环境)再更新一下condacondaupdate--all 然后转换数据，从osm到geojsonogr2ogr-fGeoJSONmap......
  • 反思记录
    我需要每个月，甚至每周，对我最近的工作、学习、生活做一些总结与反思。每天处于一个浑浊的状态，这样非常并不好，我需要定期反思总结，日报有点频繁，那就每周和每个月吧。（其实日报也不是不行）2023.06.07头皮发麻，发现自己的水平远远不够，要做的、要学的事情还有特别特别多。记录一下需要学......
  • 3D机械手手眼标定（记录）
    经过多次在百度上的搜索，目前理清了3D机械手手眼标定的流程。由于没有实际的机械手做实验，所以本文内容没有得到实际的验证。以下内容是基于眼在手上为基础叙述的。眼在手外目前没有研究。首先我们要知道眼在手上的标定目标是计算相机到机械手的变换矩阵。在进行手眼标定之前需要获......
  • 3D UX-net 训练记录
    3DUX-net训练记录题外话：如果自己跑过nnunet或者其他模型的大佬会更容易上手，但是对于第一次跑模型的小白来说，这个模型也是很好上手和跑通的！本人就是小白，这是我跑通的第一个模型。首先先去官网下载所需的代码和论文（跑之前可以先不看论文，我就是）官网：GitHub-MASILab/3DUX-Net......
  • 记录一次.NET6环境使用Visual Studio 2022 V17.6.2版本的异常
    开发环境C#开发环境VisualStudio2022V17.6.2版本。目标框架：.NET6.0错误内容：系统是BlazorServer框架的系统页面，在使用VisualStudio2022V17.6.2版本编译后，执行出现：TimeStamp:2023/6/613:35:07MachineName:Light.YangAppDomainName:SajetServerAppOS:Microsoft......
  • CH58x\CH57x硬件SPI操作外部flash学习记录
    官方提供的58x的spi例程，spi主机模式下的发送方式有三种单字节发送，FIFO连续发送，DMA连续发送。本文分别对SPI0主机模式下三种发送模式进行使用。本次使用的是CH582m做为主机，W25Q64FV作为从机。一、单字节发送本次调试中实现对W25Q64FVflas进行读id，擦除，写入，读取。在进行主要操作......
  • 关于CloudFront-Distribution-SSL-证书过期的更新替换操作记录
    提前说明：载止今天,AWSCloudFront还是只支持IAM类型的证书今天笔者主要讲述当AWSCloudFrontDistribution的SSL证书过期后，如何进行更新1、假定已经知道某个CloudFrontDistribution使用的SSL证书将要过期2、进入CloudFrontDistributions页面，找到指定的Distribution，  ......
  • 一次简单的蓝牙相关安卓代码逆向记录
    前言本来工作方面和安卓根本没任何交集，把这个过程记录下来，只是一个小总结。涉及到的知识点有，安卓逆向，Smali修改，安卓apk签名，蓝牙连接，ADB。基本需求手里有一个设备，是支持双模蓝牙的。也就是经典蓝牙使用的名称和MAC地址，和低功耗蓝牙使用的是一样的。之前其他人开发过一个......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99