首页 > 其他分享 >CF1870 div1+div2做题记录

CF1870 div1+div2做题记录

时间：2023-09-19 22:13:06浏览次数：41  
标签：ch int void write 做题 inline div2 div1 define

A

题面

挺蠢的，无解条件为 \(n<k\) 或 \(x<k-1\)，即 \(\mathop{\mathrm{mex}}\not=k\)。先选 \(0\sim k-1\)，再选能选的最大值，当 \(x=k\)，选 \(x-1\)，否则选 \(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;
void solve(){
    int n,k,x;
    read(n),read(k),read(x);
    if(k-1>x||k>n){
        puts("-1");
        return;
    }
    int sum=(k-1)*k/2;
    if(x==k){
        sum+=(n-k)*(k-1);
    }
    else{
        sum+=(n-k)*x;
    }
    write_endl(sum);
}
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

题面

分位讨论，如果一个或上一个 \(b_i\)，对于它二进制上的每一个 \(1\) 的位置有什么影响。若 \(n\) 为偶数，显然或上之后这一位一定为 \(0\)，否则一定为 \(1\)。

对于 \(n\) 为奇数时，所有数在或上一个 \(b_i\) 后异或和一定不会变小，对于 \(n\) 为偶数时，或上一个 \(b_i\) 后异或和一定不会变大，所以要么全或，要么全不或。直接计算两个极端的值，然后按 \(n\) 的奇偶性以不同的顺序输出两个数。

点击查看代码 
#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=2e5+10;
int n,m,a[N],b[N];
void solve(){
    int xsum=0,osum=0;
    read(n),read(m);
    for(int i=1;i<=n;i++){
        read(a[i]);
        xsum^=a[i];
    }
    for(int j=1;j<=m;j++){
        read(b[j]);
        osum|=b[j];
    }
    if(n%2==1){
        write_space(xsum);
        int s=0;
        for(int i=1;i<=n;i++){
            s^=(a[i]|osum);
        }
        write_endl(s);
    }
    else{
        int s=0;
        for(int i=1;i<=n;i++){
            s^=(a[i]|osum);
        }
        write_space(s);
        write_endl(xsum);
    }
}
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

题面

如果存在一个 \(j\) 满足 \(j\le i,a_j\ge a_i\)，\(a_i\) 答案的左侧和上方的界限要划到对应行和对应列，同理右侧和下方也一样。按权值从大到小找答案即可。

点击查看代码 
#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=1e5+10;
vector<int>sum[N];
int n,a[N],k,ans[N];
void solve(){
    read(n),read(k);
    for(int i=1;i<=k;i++){
        sum[i].clear();
    }
    for(int i=1;i<=n;i++){
        read(a[i]);
        sum[a[i]].pb(i);
    }
    int mn=n+1,mx=0;
    for(int i=k;i>=1;i--){
        if(sum[i].size()==0){
            ans[i]=0;
            continue;
        }
        mn=min(mn,sum[i].front());
        mx=max(mx,sum[i].back());
        ans[i]=(mx-mn+1)*2;
    }
    for(int i=1;i<=k;i++){
        write_space(ans[i]);
    }
    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;
}

D

题面

因为要字典序最大，我们最基本要让 \(1\) 的值最大，找到代价最小的位置，如果有多个代价最小的位置，选最后一个位置，令该位置为 \(p\)，这样可以使得答案其它位置的答案也更大。如果此时还有多余的代价，因为 \(p\) 以前的位置都已经尽量大了，所以我们只能考虑将一些 \(p\) 处的贡献往后移动到代价更大的位置产生贡献，将所有的代价减去 \(p\) 后，能够发现这还是上述操作，重复进行操作直到 \(p=n\) 为止。看得出来，这个操作序列 \(p\) 的代价的序列就是原序列的单调栈中的权值，维护一个单调上升的单调栈就行。

点击查看代码 
#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=2e5+10;
int n,c[N],k,cnt[N],stk[N],top;
void solve(){
    read(n);
    for(int i=1;i<=n;i++){
        read(c[i]);
        cnt[i]=0;
    }
    read(k);
    top=0;
    for(int i=1;i<=n;i++){
        while(top&&c[stk[top]]>=c[i]){
            top--;
        }
        stk[++top]=i;
    }
    cnt[0]=inf;
    for(int i=1;i<=top;i++){
        cnt[stk[i]]=min(cnt[stk[i-1]],k/(c[stk[i]]-c[stk[i-1]]));
        cnt[stk[i-1]]-=cnt[stk[i]];
        k-=cnt[stk[i]]*(c[stk[i]]-c[stk[i-1]]);
    }
    for(int i=n-1;i;i--){
        cnt[i]+=cnt[i+1];
    }
    for(int i=1;i<=n;i++){
        write_space(cnt[i]);
    }
    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;
}

E

题面

令 \(f_{i,j}\) 表示前 \(i\) 个位置中能得否划分处若干个区间使得 \(\mathop{\mathrm{mex}}\) 异或得到 \(j\)。

可以用 \(O(n^2)\) 的复杂度处理出区间 \([i,j]\) 的 \(\mathop{\mathrm{mex}}\)。为了保证复杂度，需要去重，只存下 \(\mathop{\mathrm{mex}}_{[i,j]}/not=\mathop{\mathrm{mex}}_{[i,j-1]}\) 且 \(\mathop{\mathrm{mex}}_{[i,j]}/not=\mathop{\mathrm{mex}}_{[i+1,j]}\) 的 \(\mathop{\mathrm{mex}}\)。这样的 \(\mathop{\mathrm{mex}}_{[i,j]}\) 的数量是 \(O(n)\) 级别的。\(j\) 的可以转移来的位置只有存下来的 \(\mathop{\mathrm{mex}}_{[i,j]}\) 所对应的 \(i-1\)。复杂度就变成了 \(O(nV)\) 级别了。

点击查看代码 
#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=5e3+10,M=8192+10;
int n,a[N],mex[N][N],cnt[M];
bool f[N][M];
vector<pii>num[N];
void solve(){
    read(n);
    for(int i=1;i<=n;i++){
        read(a[i]);
    }
    int mx=*max_element(a+1,a+n+1);
    for(int i=0;;i++){
        if((1<<i)>mx+1){
            mx=(1<<i)-1;
            break;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=mx;j++){
            cnt[j]=0;
        }
        int pos=0;
        for(int j=i;j<=n;j++){
            cnt[a[j]]++;
            while(cnt[pos]){
                pos++;
            }
            mex[i][j]=pos;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            if(mex[i][j]!=mex[i][j-1]&&mex[i][j]!=mex[i+1][j]){
                num[j].pb(mp(i,mex[i][j]));
            }
        }
    }
    f[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=mx;j++){
            f[i][j]=f[i-1][j];
            if(f[i-1][j]){
                continue;
            }
            for(auto x:num[i]){
                int pre=x.first,nxt=x.second;
                f[i][j]|=f[pre-1][j^nxt];
            }
        }
    }
    for(int i=mx;i>=0;i--){
        if(f[n][i]){
            write_endl(i);
            break;
        }
    }
    for(int i=0;i<=mx;i++){
        cnt[i]=0;
    }
    for(int i=0;i<=n;i++){
        for(int j=0;j<=mx;j++){
            f[i][j]=0;
        }
        for(int j=0;j<=n;j++){
            mex[i][j]=0;
        }
        num[i].clear();
    }
}
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;
}

F

题面

考虑将 \(1\sim n\) 全部化为 \(k\) 进制，将其放到trie上，可以发现两种数列b分别为bfs序和dfs序得到的数列，答案要找的数就是bfs序减dfs序结果为 \(0\) 的点。考虑将trie拆成若干行，对于每行计算答案，可以二分找到贡献答案的范围。总复杂度 \(O(t\log n^3)\)。

点击查看代码 
#include<bits/stdc++.h>
#define ull unsigned long long
#define int __int128
#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,k,tot,L[100],R[100],ans;
void init(){
    ans=0,tot=0;
    for(int l=1,r;l<=n;l=r+1){
        r=min(l*k-1,n);
        L[++tot]=l,R[tot]=r;
    }
}
int get(int x,int cur){
    int ans=-x+1,mul=1;
    for(int i=cur-1;i;i--){
        mul=mul*k;
        ans+=x/mul-L[i]+1;
    }
    mul=1;
    for(int i=cur;i<=tot;i++){
        ans+=min(x*mul-1,n)-L[i]+1;
        mul*=k;
    }
    return ans;
}
void solve(){
    read(n),read(k);
    if(n<k){
        write_endl(n);
        return;
    }
    init();
    for(int i=1;i<=tot;i++){
        int ansl=R[i]+1,ansr=R[i]+1;
        int l=L[i],r=R[i];
        while(l<=r){
            int mid=(l+r)>>1;
            if(get(mid,i)>=0){
                ansl=mid;
                r=mid-1;
            }
            else{
                l=mid+1;
            }
        }
        l=L[i],r=R[i];
        while(l<=r){
            int mid=(l+r)>>1;
            if(get(mid,i)>0){
                ansr=mid;
                r=mid-1;
            }
            else{
                l=mid+1;
            }
        }
        ans+=ansr-ansl;
    }
    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;
}

标签：ch,int,void,write,做题,inline,div2,div1,define
From： https://www.cnblogs.com/luoshen0/p/17714053.html

相关文章

  • cf1869 div.1,div.2做题记录
    赛时总结div.2A题面对于任意一个区间，我们可以通过一次操作将区间内的数变得全部相同。如果区间内的全部数都相同，那么我们再做一遍区间操作，当这个区间长度为偶数时，区间异或和为\(0\)，会清空区间；当区间长度为奇数时，区间内的数不会发生改变。但我们可以将一个长度为奇数的区间拆成......
  • CF1858E1 做题笔记
    题目链接赛时没做出来，晚上补了一下，发现是一种很好玩的数据结构。由于可以离线又要支持删除后$k$个又要支持撤销操作，不会写主席树只能选择操作树。对序列按照时间建成一颗操作树，处于某个点的回合时，这个序列的样子就是它以及它的祖先。来依次考虑某个操作，设当前是序列的末尾......
  • MYSQL SQL做题总结
    一.关于join1.内外左右连接2.交叉联结（corssjoin）使用交叉联结会将两个表中所有的数据两两组合。如下图，是对表“text”自身进行交叉联结的结果：3.三表双双连接力扣题目a与b表笛卡尔积，再与c表左连接。SELECTa.student_id,a.student_name,b.subject_name,count(c.subject......
  • ARC165 做题记录
    有点结论场的感觉了。A题面简单题。证明一个结论，只要\(n\not=p^q(p\text{是}n\text{的一个质因子})\)，都是有解的，反之无解。先证明\(n=p^q\)无解，假定\(n\)分解为\(p^a\timesp^b(a\leb,a+b=q)\)，此时两数的\(\mathop{\mathrm{lcm}}\)为\(p^b\)。若\(b=q\)，则\(p^b......
  • PWN做题笔记1
    原题在某个名字被51cto屏蔽了的CTF刷题网站，题目为ret2text题目属于栈溢出给出了地址和端口，压缩包中有一个二进制程序pwnfile命令可以看到是64位ELF程序，这里pwn是文件名checksec发现没有开启任何安全措施程序运行如下：ida64反汇编，发现gets输入没有边界检查0x70，存在注入：secure函数调用......
  • 2023.9 做题纪要 #2
    目录2023.9.14P3920[WC2014]紫荆花之恋CF1408HRainbowTriples2023.9.15CF1534GANewBeginningCF1696GFishingprincePlaysWithArrayAgain2023.9.14哇哦，居然出现了第二篇博客。前两天whk，顺便感了个冒，所以whk也没咋看。今天还没完全恢复，浅更一下吧。先把AGC优先......
  • YNOI 做题记
    YNOI做题记偶然有一天做到了其中的一道题，于是便开始做相关的题了……[Ynoi2015]我回来了-洛谷这之一场联考搬过来的题……于是考场上写了一个\(O((n+m)\log^2n)\)的代码，然后成功被卡掉，非常慢速。其实离线，将每一个伤害答案变化的时间做出来，然后加入时间序列后，树状数组......
  • 九月做题记录（距 CSP 还有 1 个月）
    P3959[NOIP2017提高组]宝藏发现\(n\)是很小的，考虑状压。我们先记录下当前的树包含了哪些节点，然后因为转移时肯定会需要经过了多少边，也就是树的深度。我们记录\(\text{expand(i)}\)表示当前选的集合为\(i\)时，扩展一次后的集合。\(\text{road(i,j)}\)表示选的集合为......
  • 2023.9 做题记录
    虽然第一天是8.31，但确实是开学第一个月，就一块算进去了。P2824法一：二分答案，将大于等于\(mid\)的数设为\(1\)，小于的设为\(0\)，最后位置上如果是\(1\)说明大于等于\(mid\)，否则小于，时间复杂度\(O(n\logn)\)，空间复杂度线性。法二（待做）：线段树分裂，时间复杂度和空间复杂度均......
  • P5665 [CSP-S2019] 划分 做题记录
    题目传送门题目描述2048年，第三十届CSP认证的考场上，作为选手的小明打开了第一题。这个题的样例有\(n\)组数据，数据从\(1\simn\)编号，\(i\)号数据的规模为\(a_i\)。小明对该题设计出了一个暴力程序，对于一组规模为\(u\)的数据，该程序的运行时间为\(u^2\)。然而这个程序......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99