首页 > 其他分享 >cf1849做题记录

cf1849做题记录

时间：2023-08-13 21:01:18浏览次数：61  
标签：ch val 记录 int void cf1849 write 做题 define

A

题面

分类讨论 \(b+c\) 和 \(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;
void solve(){
    int a,b,c;
    read(a),read(b),read(c);
    if(b+c<a){
        write_endl((b+c)*2+1);
    }
    else{
        write_endl(a*2-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

题面

可以发现因为每次选的是血最多的，所以影响实际死亡顺序的是最后一击前的血量。以血量模 \(k\) 的余数为第一关键字（如果血量模 \(k\) 的余数为 \(0\) 则看作余数为 \(k\)），以编号为第二关键字排序即可。

点击查看代码 
#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=3e5+10;
int n,k;
struct node{
    int id,val;
}a[N];
bool cmp(node x,node y){
    return x.val==y.val?x.id<y.id:x.val>y.val;
}
void solve(){
    read(n),read(k);
    for(int i=1;i<=n;i++){
        read(a[i].val);
        a[i].val=(a[i].val-1)%k+1;
        a[i].id=i;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++){
        write_space(a[i].id);
    }
    putchar('\n');
}
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

题面

每次排序时的前缀 \(0\) 和后缀 \(1\) 都是没有意义的，该在最前面的还在最前面，该在最后面的还在最后面。所以维护两个数组 \(nxt_i\) 表示 \([i,n]\) 中第一个 \(1\) 的位置，\(pre_i\) 表示 \([1,i]\) 中最后一个 \(0\) 的位置，每次排序会修改的部分只有 \([nxt_l,pre_r]\) 这个部分。注意的是当 \(nxt_l>pre_r\) 时，整个序列没有修改，将修改操作变为 \([0,0]\) 即可。答案为不同的操作数量，用 map 计数一下就行。

点击查看代码 
#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 nxt[N],pre[N],n,m;
char s[N];
void solve(){
    read(n),read(m);
    for(int i=1;i<=n;i++){
        s[i]=getchar();
        while(s[i]!='0'&&s[i]!='1'){
            s[i]=getchar();
        }
    }
    for(int i=1;i<=n;i++){
        if(s[i]=='0'){
            pre[i]=i;
        }
        else{
            pre[i]=pre[i-1];
        }
    }
    nxt[n+1]=n+1;
    for(int i=n;i;i--){
        if(s[i]=='1'){
            nxt[i]=i;
        }
        else{
            nxt[i]=nxt[i+1];
        }
    }
    map<pii,int>vis;
    for(int i=1;i<=m;i++){
        int l,r;
        read(l),read(r);
        if(nxt[l]>pre[r]){
            vis[mp(0,0)]=1;
        }
        else{
            vis[mp(nxt[l],pre[r])]=1;
        }
    }
    write_endl(vis.size());
}
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

题面

对于一个非零段，如果从左端开始，则可以将该非零段的右边第一个 \(0\) 的位置染色，从右端开始则可以将左边第一个 \(0\) 的位置染色。如果有 \(2\)，可以从 \(2\) 的位置开始，将左右的第一个 \(0\) 都染色。所以我们先将有 \(2\) 的非零段和其左右的第一个 \(0\) 染色。剩下的 \(0\) 直接贪心染色。对于从左往右的每个非零段，如果左侧的第一个 \(0\) 未染色，则将其染色，否则将右侧的第一个 \(0\) 染色，最后剩下的 \(0\) 单独染一次色即可。

点击查看代码 
#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,a[N],b[N];
void solve(){
    int ans=0;
    read(n);
    for(int i=1;i<=n;i++){
        read(a[i]);
    }
    for(int i=1,j;i<=n;i=j+1){
        int flag=0;
        for(j=i;j<=n;j++){
            if(!a[j]){
                break;
            }
            flag=max(flag,a[j]);
        }
        if(flag==2){
            ans++;
            for(int k=i-1;k<=j;k++){
                b[k]=1;
            }
        }
    }
    for(int i=1,j;i<=n;i=j+1){
        int flag=0;
        for(j=i;j<=n;j++){
            if(!a[j]){
                break;
            }
            flag=max(flag,a[j]);
        }
        if(flag==1){
            ans++;
            if(i>1&&!b[i-1]){
                for(int k=i-1;k<j;k++){
                    b[k]=1;
                }
            }
            else{
                for(int k=i;k<=j;k++){
                    b[k]=1;
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(!b[i]){
            ans++;
        }
    }
    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;
}

E

题面

在确定右端点 \(j\) 的情况下，可能合法的区间有 \(j\) 个，令 \(f_i\) 表示左端点为 \(i\) 时区间的合法性。如果此时我们在后面加上一个 \(a_{j+1}\)，可能影响区间的情况只有 \(a_{j+1}\) 为新区间的最大值和区间最小值。\(a_{j+1}\) 是区间最大值会使区间变得合法，是区间最小值会使区间变得不合法。
可以预处理出 \([1,j]\) 中最后一个大于 \(a_{j+1}\) 的数的位置 \(mx_{j+1}\) 和最后一个小于 \(a_{j+1}\) 的数的位置 \(mn_{j+1}\)，如果不存在大于或不存在小于的数则为 \(0\)。如果 \(a_j\) 大于 \(a_{j+1}\) 则 \(a_{j+1}\) 会在左端点在一段区间中时最小值，将 \(f_{[mn_{j+1}+1,j]}\) 赋值为 \(0\)，反之则为最大值，将 \(f_{mx_{j+1}+1,j}\) 赋值为 \(1\)。用线段树维护 \(f\) 数组的权值，只需要实现区间赋 \(0/1\)，求所有权值和的操作。

点击查看代码 
#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=1e6+10;
int n,a[N],pre_mn[N],pre_mx[N],stk[N],top;
namespace Seg_Tree{
    int ans[N<<2],tag[N<<2];
    int ls(int p){
        return p<<1;
    }
    int rs(int p){
        return p<<1|1;
    }
    void f(int p,int l,int r,int val){
        tag[p]=val+1;
        ans[p]=(r-l+1)*val;
    }
    void push_down(int p,int l,int r){
        if(tag[p]){
            int mid=(l+r)>>1;
            f(ls(p),l,mid,tag[p]-1);
            f(rs(p),mid+1,r,tag[p]-1);
        }
    }
    void push_up(int p){
        ans[p]=ans[ls(p)]+ans[rs(p)];
    }
    void update(int p,int l,int r,int q_l,int q_r,int val){
        if(q_l<=l&&r<=q_r){
            f(p,l,r,val);
            return;
        }
        int mid=(l+r)>>1;
        push_down(p,l,r);
        if(q_l<=mid){
            update(ls(p),l,mid,q_l,q_r,val);
        }
        if(q_r>mid){
            update(rs(p),mid+1,r,q_l,q_r,val);
        }
        push_up(p);
    }
}
void solve(){
    read(n);
    for(int i=1;i<=n;i++){
        read(a[i]);
    }
    for(int i=1;i<=n;i++){
        while(top&&a[stk[top]]>a[i]){
            top--;
        }
        pre_mn[i]=stk[top];
        stk[++top]=i;
    }
    top=0;
    for(int i=1;i<=n;i++){
        while(top&&a[stk[top]]<a[i]){
            top--;
        }
        pre_mx[i]=stk[top];
        stk[++top]=i;
    }
    int ans=0;
    for(int i=2;i<=n;i++){
        if(a[i-1]<a[i]){
            Seg_Tree::update(1,1,n,pre_mx[i]+1,i-1,1);
        }
        else{
            Seg_Tree::update(1,1,n,pre_mn[i]+1,i-1,0);
        }
        ans+=Seg_Tree::ans[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;
}

F

题面

对于这种划分到两个集合的题要能够惯性想到二分图上去，想到二分图上后就好做了。

这里有两种做法解决本题。

第一种做法，二分答案，只连接异或和小于二分的权值 \(x\) 的边，判断是否为二分图即可，如果为二分图，则说明所有异或和小于 \(x\) 的数对都不同时在一个集合中，答案肯定大于等于 \(x\)。但这里有个问题，在 \(x\) 较大时，连的边是接近 \(n^2\) 的此时我们一次染色判断二分图复杂度太大，需要考虑优化建图。
有一个结论是，对于一个排好序的数组 \(val\)，如果存在一个 \(i\) 使得 \(x>val_i\oplus val_{i+4}\)，此时一定是无解。
证明：令 \(y=val_i\oplus val_{i+4}\)，\(y\) 的最高位为 \(a\)，必然的是 \(val_i\) 第 \(a\) 位为 \(0\)，\(val_{i+4}\) 的第 \(a\) 位为 \(1\)。根据鸽巢原理，\(val_i,val_{i+1},val_{i+2},val_{i+3},val_{i+4}\) 这 \(5\) 个数在第 \(a\) 位上至少有三个数相同，也就意味着至少会有三个数两两异或和小于 \(x\)，必然不是二分图，同理 \(x>val_i\oplus val_{i+5}\)，\(x>val_i\oplus val_{i+6}\) 等也是一样的。
这个结论让我们的边数从原来的 \(n^2\) 级别变成了与 \(n\) 同阶。如果无解，那么加上更多边一定无解；如果有解，那么问题就变成了是否会存在 \(x>val_i\oplus val_{i+4}\) 且不加该边时原图为二分图的情况，答案为不能。回到开始的分类讨论，假定 \(val_i,val_{i+1},val_{i+2}\) 第 \(a\) 位均为 \(0\)，那么在 \(i\) 连边时会连出奇环，假定 \(val_{i+2},val_{i+3},val_{i+4}\) 第 \(a\) 位为 \(1\)，那么在 \(i+2\) 连边时会连出奇环，所以上述问题所说的情况一定不存在。

点击查看代码 
#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,a[N],col[N],val[N],pos[N],flag=0;
vector<pii>id;
vector<int>e[N];
void dfs(int u,int color){
    col[u]=color;
    for(auto v:e[u]){
        if(!col[v]){
            dfs(v,3-color);
        }
        if(col[v]!=3-color){
            flag=0;
            return;
        }
    }
}
bool check(int x){
    for(int i=1;i<=n;i++){
        e[i].clear();
        col[i]=0;
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=min(i+3,n);j++){
            if((val[i]^val[j])<x){
                e[i].pb(j);
                e[j].pb(i);
            }
        }
    }
    flag=1;
    for(int i=1;i<=n;i++){
        if(!col[i]){
            dfs(i,1);
        }
    }
    return flag;
}
void solve(){
    read(n);
    for(int i=1;i<=n;i++){
        read(a[i]);
        id.pb(mp(a[i],i));
    }
    sort(id.begin(),id.end());
    for(int i=1;i<=n;i++){
        pos[id[i-1].second]=i;
        val[i]=id[i-1].first;
    }
    if(n==2){
        puts("10");
        return;
    }
    int l=1,r=(1<<30)-1,ans=0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)){
            ans=mid;
            l=mid+1;
        }
        else{
            r=mid-1;
        }
    }
    check(ans);
    for(int i=1;i<=n;i++){
        write(col[pos[i]]-1);
    }
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}

第二种做法，每次选出最小的边，要答案最大，这条边的两个端点显然应该属于不同集合。我们一直加边，直到加边后图不再是二分图。但其实没必要是图，一棵树就已经能够把哪个点属于哪个集合定下来了，根据这个思路，我们只需求出完全图的最小异或生成树，对其进行黑白染色，就是最后的划分结果。求完全图图的最小异或生成树类似于CF888G，感兴趣的可以直接看01trie，这里就不给出代码了。

标签：ch,val,记录,int,void,cf1849,write,做题,define
From： https://www.cnblogs.com/luoshen0/p/17627257.html

相关文章

  • [nc 记录] CF13333E Road to 1600
    赛时没做出来一直在往随机想。题意挺明确。发现到\(n\timesn\)这个条件，联想到做过的CF1172D，递归去掉一行一列的基本想法就有了。那么让两个棋子从右下开始，走完多出的一行一列，然后走进剩余的\((n-1)\times(n-1)\)。真可以？这就是*2400的构造？这我还能想不出来？只用构造......
  • Django实现文件上传、文件列表查看、修改、限流和日志记录8
    Django实现文件上传、文件列表查看、修改、限流和日志记录8本章节，总结一些部署项目遇到的报错，希望会有所帮助NameError:name'datetime'isnotdefined报错“logging.info('用户{}在{}登录成功'.format(username,datetime.now()))NameError:name'datetime'isnotd......
  • 跳槽！阿里工作100+天，菜鸡职业生涯的一点记录
    系列文章目录和关于我-Cuzzz-博客园(cnblogs.com)零丶序言来阿里100天了（准确说是137天，转正后就想写的，但是一直拖延了40天+），在互联网哀鸿遍野的当下，工作不到两年的我选择跳槽，并拿到蚂蚁、字节、pdd、阿里的offer，最终选择阿里，并在阿里转正并度过100天+，写文记录下这段时光。......
  • Django实现文件上传、文件列表查看、修改、限流和日志记录7
    Django实现文件上传、文件列表查看、修改、限流和日志记录7不管调用的接口在内网，还是外网都需要做好限制保证接口的访问和限流降级处理，本章节新增限流功能。限流功能主要针对两个方面：IP和用户针对IP限流文件列表接口进行限流处理，限制每分钟每个IP访问10次，你可以使用Dja......
  • Django实现文件上传、文件列表查看、修改、限流和日志记录6
    Django实现文件上传、文件列表查看、修改、限流和日志记录6对于已经上传的文件，现在已经实现了文件的查看修改，美中不足的是：需要查看每个文件需要提前记住文件名指定文件名进行查看和修改。为此，新增一个上传文件的列表功能，在通过模版按钮跳转路由到查看和修改页面。实现逻辑查看......
  • Django实现文件上传、文件列表查看、修改、限流和日志记录4
    Django实现文件上传、文件列表查看、修改、限流和日志记录4本章添加用户认证功能，属于安全模块。用户认证在Django中，默认情况下，用户的用户名和密码是存储在数据库中的。Django提供了内置的用户模型（User模型），它可以管理用户的认证和授权。配置数据库在file_upload/settings.py......
  • 学习了几种定位方式--记录
    fromseleniumimportwebdriverfromtimeimportsleepfromselenium.webdriver.common.byimportBy#通过ID来定位#driver=webdriver.Chrome()#driver.maximize_window()#driver.get('http://www.baidu.com')#sleep(3)#driver.find_element(By.ID,'kw�......
  • XSS--labs通关记录
    XSS--labs通关记录level1(无过滤)查看网页源代码<!DOCTYPEhtml><!--STATUSOK--><html><head><metahttp-equiv="content-type"content="text/html;charset=utf-8"><script>window.alert=function(){confirm(......
  • Django实现文件上传、文件列表查看、修改、限流和日志记录2
    Django实现文件上传、文件列表查看、修改、限流和日志记录2本章节优化新增功能使用ssh秘钥连接远程服务器进行文件上传使用ssh私钥连接远程服务器上传文件使用SSH私钥连接远程服务器并上传文件，你可以使用paramiko库来实现SSH连接和文件传输的功能。首先，确保你已经生成了SSH......
  • git常用命令记录
    git仓库初始化gitinit查看git仓库状态gitstatus将文件加入缓存区gitadd.gitaddtest_*将缓存区的文件提交到仓库gitcommit-m"提交信息"将本地仓库代码push到远程仓库gitpushoriginbranch_name分支管理gitbranch#显......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99