首页 > 其他分享 >CF1882 div.2 做题记录

CF1882 div.2 做题记录

时间：2023-09-26 15:35:12浏览次数：50  
标签：CF1882 ch 记录 int void long write div.2 define

A

题面

扫一遍，令 \(b_i\rightarrow b_{i-1}+1\)，若 \(b_i=a_i\)，\(b_i\rightarrow b_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;
const int inf=1e9;
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;
void solve(){
    read(n);
    int ans=0;
    for(int i=1;i<=n;i++){
        ans++;
        int x;
        read(x);
        if(ans==x){
            ans++;
        }
    }
    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

题面

因为集合不能为并集，钦定至少存在 \(x\) 不能被包含，求不包含 \(x\) 的集合的并集的大小，对于所有枚举的 \(x\) 求并集大小的最大值。

点击查看代码 
#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;
const int inf=1e9;
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=100;
int n,s[N][N],cnt[N],vis[100],ans[100];
void solve(){
    read(n);
    for(int i=1;i<=50;i++){
        vis[i]=0;
    }
    for(int i=1;i<=n;i++){
        read(cnt[i]);
        for(int j=1;j<=cnt[i];j++){
            read(s[i][j]);
            vis[s[i][j]]=1;
        }
    }
    int mx=0;
    for(int i=1;i<=50;i++){
        if(!vis[i]){
            continue;
        }
        for(int j=1;j<=50;j++){
            ans[j]=0;
        }
        for(int j=1;j<=n;j++){
            bool flag=1;
            for(int k=1;k<=cnt[j];k++){
                if(s[j][k]==i){
                    flag=0;
                    break;
                }
            }
            if(flag){
                for(int k=1;k<=cnt[j];k++){
                    ans[s[j][k]]=1;
                }
            }
        }
        int sum=0;
        for(int j=1;j<=50;j++){
            if(ans[j]){
                sum++;
            }
        }
        mx=max(mx,sum);
    }
    write_endl(mx);
}
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

题面

证明一个结论，如果删掉一个数，那么它后面的所有数都是可以选择加入到贡献的。假定删掉的数的位置为 \(x_1,x_2,x_3\dots x_m\)。考虑以奇数位置为分界点，将 \(x_{2\sim m}\) 分为若干段，从后往前处理每个段，将奇数位置的数加入贡献后，所有偶数位置的数都会变成奇数位置的数，从后往前加入贡献就可以保证每个数再删去时都在奇数位置上。只有最前面一段可能还有一段偶数位置的数，删去 \(a_{x_1}\) 即可。

从后往前枚举 \(x_1\)，并统计 \((x_1,n]\) 区间内的正数的和 \(sum\)，求删去 \(a_{x_1}\) 的贡献与 \(sum\) 的和的最大值。

点击查看代码 
#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;
const int inf=1e9;
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,s[N],a[N];
void solve(){
    read(n);
    for(int i=1;i<=n;i++){
        read(a[i]);
        if(a[i]>0){
            s[i]=a[i];
        }
        else{
            s[i]=0;
        }
    }
    s[n+1]=0;
    int ans=0;
    for(int i=n;i>=1;i--){
        s[i]=s[i+1]+s[i];
        if(i&1){
            ans=max(ans,a[i]+s[i+1]);
        }
        else{
            ans=max(ans,s[i+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

题面

先考虑以 \(1\) 为根的情况，模拟一条链 \(1\rightarrow 2\rightarrow 3\rightarrow 4\)。

点\(1\) 的修改是没有意义的，因为是所有点都被修改，等价于没变，所以直接令最后的异或值为 \(a_1\) 即可；
点 \(2\) 的修改值为 \(a_1\oplus a_2\)；
点 \(3\) 的修改值为 \(a_1\oplus a_2\oplus a_3\oplus a_1=a_2\oplus a_3\)；
点 \(4\) 的修改值为 \(a_1\oplus a_2\oplus a_2\oplus a_3\oplus a_4\oplus a_1=a_3\oplus a_4\)。

可以发现每个点的修改值都为 \(a_u\oplus a_{fa}\)，其中 \(fa\) 表示 \(u\) 在当前树下的父亲，若 \(u\) 为树的根，则不修改。这个修改值和 \(siz\) 都是换根好维护的，直接求出以 \(1\) 为根的树的答案，再换根求其它的答案。复杂度 \(O(n)\)。

E1

题面

赛时脑抽了，没想出来怎么还原，只知道怎么调整。

将两个序列分开，可以先还原每个序列再调整操作次数的差别。

先讲调整吧，将选择序列第一个数看作将序列顺着循环位移一次，选择最后一个数看作将序列逆着循环位移一次。如果序列长度为奇数，可以通过选择序列长度次 \(1\)，改变答案操作次数的奇偶性，将此操作看作调整 \(1\)。而先选第一个，再选最后一个，可以增加两次操作次数，将此操作看作调整 \(2\)。

还原可以每次将 \(1\sim x\) 移到 \(x+1\) 前。这个操作的话，假定 \(1\sim x\) 已经是一段连续的序列，先找到 \(x\) 的位置，选择其后面的一个数，因为选择的是后面的数，不会改变前面的数的相对顺序，所以 \(1\sim x\) 就到了序列的末尾。再找到 \(x+1\) 的位置，选择该位置 \(1\sim x\) 和 \(x+1\) 就已经连续了。

令还原两个序列的操作次数分别为 \(a,b\)。若 \(b-a\) 为偶数，只需要进行若干次调整 \(2\) 即可；若 \(b-a\) 为奇数，显然要进行一次调整 \(1\)，再进行若干次调整 \(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;
const int inf=1e9;
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=3000;
int n,m,a[N],b[N],tmp[N];
vector<int>ansa,ansb;
void worka(){
    for(int i=1;i<n;i++){
        int pos=0;
        for(int j=1;j<=n;j++){
            if(a[j]==i){
                pos=j;
                break;
            }
        }
        if(a[pos+1]==i+1){
            continue;
        }
        if(pos+1>n){
            for(int j=1;j<=n;j++){
                if(a[j]==i+1){
                    pos=j;
                    break;
                }
            }
            ansa.pb(pos);
            for(int i=1;i<=n;i++){
                tmp[i]=a[i];
            }
            int cnt=0;
            for(int i=pos+1;i<=n;i++){
                a[++cnt]=tmp[i];
            }
            a[++cnt]=tmp[pos];
            for(int i=1;i<pos;i++){
                a[++cnt]=tmp[i];
            }
            continue;
        }
        ansa.pb(pos+1);
        int cnt=0,Pos=0;
        for(int j=pos+2;j<=n;j++){
            tmp[++cnt]=a[j];
            if(a[j]==i+1){
                Pos=cnt;
            }
        }
        tmp[++cnt]=a[pos+1];
        for(int j=1;j<=pos;j++){
            tmp[++cnt]=a[j];
            if(a[j]==i+1){
                Pos=cnt;
            }
        }
        cnt=0;
        ansa.pb(Pos);
        for(int j=Pos+1;j<=n;j++){
            a[++cnt]=tmp[j];
        }
        a[++cnt]=tmp[Pos];
        for(int j=1;j<Pos;j++){
            a[++cnt]=tmp[j];
        }
    }
}
void workb(){
    for(int i=1;i<m;i++){
        int pos=0;
        for(int j=1;j<=m;j++){
            if(b[j]==i){
                pos=j;
                break;
            }
        }
        if(b[pos+1]==i+1){
            continue;
        }
        // cerr<<i<<' '<<pos<<' '<<b[pos]<<' '<<b[pos+1]<<endl;
        if(pos+1>m){
            for(int j=1;j<=m;j++){
                if(b[j]==i+1){
                    pos=j;
                    break;
                }
            }
            ansb.pb(pos);
            for(int i=1;i<=m;i++){
                tmp[i]=b[i];
            }
            int cnt=0;
            for(int i=pos+1;i<=m;i++){
                b[++cnt]=tmp[i];
            }
            b[++cnt]=tmp[pos];
            for(int i=1;i<pos;i++){
                b[++cnt]=tmp[i];
            }
            continue;
        }
        ansb.pb(pos+1);
        int cnt=0,Pos=0;
        for(int j=pos+2;j<=m;j++){
            tmp[++cnt]=b[j];
            if(b[j]==i+1){
                Pos=cnt;
            }
            // cerr<<b[j]<<' ';
        }
        tmp[++cnt]=b[pos+1];
        for(int j=1;j<=pos;j++){
            tmp[++cnt]=b[j];
            if(b[j]==i+1){
                Pos=cnt;
            }
        }
        // for(int i=1;i<=m;i++){
        //     cerr<<tmp[i]<<' ';
        // }
        // cerr<<endl;
        cnt=0;
        ansb.pb(Pos);
        for(int j=Pos+1;j<=m;j++){
            b[++cnt]=tmp[j];
        }
        b[++cnt]=tmp[Pos];
        for(int j=1;j<Pos;j++){
            b[++cnt]=tmp[j];
        }
    }
}
void solve(){
    read(n),read(m);
    for(int i=1;i<=n;i++){
        read(a[i]);
    }
    for(int i=1;i<=m;i++){
        read(b[i]);
    }
    worka();
    workb();
    int siza=ansa.size(),sizb=ansb.size(),delta=siza-sizb;
    // for(auto x:ansa){
    //     cerr<<x<<' ';
    // }
    // cerr<<endl;
    // for(auto x:ansb){
    //     cerr<<x<<' ';
    // }
    if(delta%2==0){
        if(delta>0){
            while(delta>0){
                delta-=2;
                ansb.pb(1);
                ansb.pb(m);
            }
        }
        else{
            while(delta<0){
                delta+=2;
                ansa.pb(1);
                ansa.pb(n);
            }
        }
    }
    else{
        if(n%2==0&&m%2==0){
            write_endl(-1);
            return;
        }
        if(n&1){
            for(int i=1;i<=n;i++){
                ansa.pb(1);
            }
            delta+=n;
        }
        else{
            for(int i=1;i<=m;i++){
                ansb.pb(1);
            }
            delta-=m;
        }
        if(delta>0){
            while(delta>0){
                delta-=2;
                ansb.pb(1);
                ansb.pb(m);
            }
        }
        else{
            while(delta<0){
                delta+=2;
                ansa.pb(1);
                ansa.pb(n);
            }
        }
    }
    write_endl(ansa.size());
    for(int i=0;i<ansa.size();i++){
        write_space(ansa[i]),write_endl(ansb[i]);
    }
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}

E2

题面

先咕着，主要还不会

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

相关文章

  • 基于Java的高校实习管理系统设计与实现（亮点：实习记录、实习打分、实习作业，功能新颖、老
    高校实习管理系统一、前言二、我的优势2.1自己的网站2.2自己的小程序（小蔡coding）2.3有保障的售后2.4福利三、开发环境与技术3.1MySQL数据库3.2Vue前端技术3.3SpringBoot框架3.4微信小程序四、功能设计4.1主要功能描述五、系统主要功能5.1管理员功能5.2公司功能5.3老师......
  • .net webapi限流记录
     一，WebApiThrottleASP.NETWebAPIratelimiterforIISandOwinhostinghttps://github.com/stefanprodan/WebApiThrottle 二，AspNetCoreRateLimitASP.NETCoreratelimitingmiddlewarehttps://github.com/stefanprodan/AspNetCoreRateLimit......
  • CF1882C Card Game
    某种程度上的抽卡游戏？有这样一个结论：一个后缀中\([i+1,n]\)中所有的正数都可以被取到，所以维护一个正数后缀和\(s_i\)，枚举每个位置\(i\)，如果\(i\)为奇数，答案对\(a_i+s_{i+1}\)取\(\max\)，否则对\(s_{i+1}\)取\(\max\)。下面证明这个结论：先依次取掉\([i+1,n]\)中的奇......
  • 日常记录
    日常记录汉字正则判断isChinese(str){constreg=/^(?:[\u3400-\u4DB5\u4E00-\u9FEA\uFA0E\uFA0F\uFA11\uFA13\uFA14\uFA1F\uFA21\uFA23\uFA24\uFA27-\uFA29]|[\uD840-\uD868\uD86A-\uD86C\uD86F-\uD872\uD874-\uD879][\uDC00-\uDFFF]|\uD869[\uDC0......
  • 【N76E003AT20】新唐MCU使用记录
    N76E003AT20可用引脚数量18个，内核为51系列，CPU最大主频：16MHz工作电压范围：2.4V~5.5V程序存储容量：18KB程序存储器类型：FLASHRAM总容量：1KB。此前用该单片机做为主控设计了车载感应控制盒，当时没有记录开发过程，现在有个项目，我选择该芯片做设计，在此简单记录一下过程与遇到的......
  • 2023.9.25记录
    做了做并查集[JSOI2008]星球大战JSOI2008]星球大战-洛谷|计算机科学教育新生态(luogu.com.cn)题意给定一个无向图，每次操作删除一个点，求每次操作后连通块的数量。思路可以用并查集做。按操作顺序不好计算连通块的数量，所以可以考虑按操作的逆向顺序计算。因为每两个连......
  • 数据结构学习记录（四）
    排序一、知识要点1、选择排序简单选择排序思想：在未排序的数组中选出一个最大值或最小值与序列首位元素交换，然后在剩下未排序序列再选出最大值或最小值与第二位元素交换，依次类推，直到排序完成typedefintElementType;//太简单了我就不写注释了voidSSSort(ElementType......
  • 日常记录--day9--2023-9月25日--周一
    日程：今天满课，累死了，早上7点起床，吃早饭，去工程实训课，今天上的是机器人实训，造了个小车。下午Java，学了类和对象，晚上7-8点复习了一下，之后进行经典力扣。学了什么：Java让人头疼，来了道力扣题，还要继续加油，继续学习Javaweb。PS:不想学习，想要成为鼠标垫......
  • 编译器优化记录(死代码消除+“激进的”死代码消除)
    编译器优化记录(3)——死代码消除+”激进的“死代码消除0.什么是死代码消除相信大家在写C++的时候，如果你定义了一个变量但是没有对其使用，大部分IDE都会对这个变量进行灰色的染色。又或者说，当你开了一个空的循环，在里面定义并使用了一堆和输出值/返回值没有关系的变量，这个时候IDE......
  • 【Azure App Services】多次操作App Service伸缩实例遇见限制操作记录
    问题描述多次操作AppServices，进行实例数的变化。达到限制后遇见报错：错误的具体描述为：{"status":"Failed","error":{"code":"Conflict","message":"Youhaveexceededthemaximumamountofscalechange......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99