当前位置： 首页 > news >正文

Codeforces Round #826 (Div. 3) E,F

news 来源：原创 2024/5/18 19:14:01

E - Sending a Sequence Over the Network dp

写了半天的搜索，原来是dp，，，

dp[i]表示前i个位置是否合法，对于i来说，如果前i-1个是合法的，那么前i+a[i]也是合法的；如果前i-1-a[i]是合法的，那么前i个也是合法的，这样一直递推下去就行

Codeforces Round #826 (Div. 3) A - F - 知乎 (zhihu.com)

#include <bits/stdc++.h>
#define int long long
#define lowbit(x) ((x)&(-x))
#define endl '\n'
#define double long double
using namespace std;
const int mod=1e9+7;
const int inf=3e18;
double qpow(double a,int b)
{
    double res=1;
    while(b)
    {
        if(b&1) res=res*a;
        a=a*a;
        b>>=1;
    }
    return res;
}
int dp[200005],t,n,a[200005];
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    //freopen("in.txt", "r", stdin);
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i],dp[i]=0;
        dp[0]=1;
        for(int i=1;i<=n;i++)
        {
            if(a[i]+i<=n) dp[i+a[i]]|=dp[i-1];
            if(a[i]+1<=i) dp[i]|=dp[i-1-a[i]];
        }
        if(dp[n]) cout<<"YES\n";
        else cout<<"NO\n";
    }
    system("pause");
    return 0;
}

F - Multi-Colored Segments 线段树二分

如果第i个线段的[l,r]内还有颜色的话答案就是0，否则就要向左去找离l最近的点，向右去找离r最近的点，然后两个值再比较；

这样大概思路其实就有了，我们可以写一个区间加法区间求和的线段树，然后对出现的每个区间都加1，这样枚举到第i个线段[l,r]时，第i个线段的颜色为c，那么将所有颜色为c的线段区间都-1，也就是都去掉，然后如果[l,r]的和还是1的话说明有相交的线段，答案就是0，否则去左边[1,l]找离l最近的点，我们可以根据区间的和来判断这个区间的走向，因为是离l最近，那么优先找的区间一定是[(1+l),l],也就是右半段，放在函数里就是[mid+1,r],如果区间和大于等于1的话说明这个区间里一定是有符合条件的点的，那就再去这个区间搜，否则就要去[l,mid]区间里搜，对于去找右边离r最近的点的方法也是一样的；注意一个关键的小点，枚举答案的时候因为颜色是小于等于n的，所以可以直接去枚举颜色而不是去枚举线段，这样会减少很多复杂度；虽然这种方式好想，但是因为用了query函数所以多了个log，总的复杂度是o(nlognlogn);

l，r的范围比较大，离散化一下就可以，注意求答案做差的时候需要是原来的值做差，而不是离散后的

o(nlognlogn)的代码

#include <bits/stdc++.h>
#define int long long
#define lowbit(x) ((x)&(-x))
#define endl '\n'
#define double long double
using namespace std;
const int mod=1e9+7;
const int inf=3e18;
double qpow(double a,int b)
{
    double res=1;
    while(b)
    {
        if(b&1) res=res*a;
        a=a*a;
        b>>=1;
    }
    return res;
}
struct segtree
{
    int val,lazy;
}tr[400005<<3];
void pushup(int p){tr[p].val=tr[p<<1].val+tr[p<<1|1].val;}
void build(int l,int r,int p)
{
    tr[p].lazy=0;
    if(l==r)
    {
        tr[p].val=0;
        return;
    }
    int mid=l+r>>1;
    build(l,mid,p<<1);
    build(mid+1,r,p<<1|1);
    pushup(p);
}
void pushdown(int p,int ln,int rn)
{
    if(tr[p].lazy)
    {
        tr[p<<1].lazy+=tr[p].lazy;
        tr[p<<1|1].lazy+=tr[p].lazy;
        tr[p<<1].val+=tr[p].lazy*ln;
        tr[p<<1|1].val+=tr[p].lazy*rn;
        tr[p].lazy=0;
    }
}
void update(int L,int R,int C,int l,int r,int p)
{
    if(L<=l&&r<=R)
    {
        tr[p].val+=C*(r-l+1);
        tr[p].lazy+=C;
        return;
    }
    int mid=l+r>>1;
    pushdown(p,mid-l+1,r-mid);
    if(L<=mid) update(L,R,C,l,mid,p<<1);
    if(R>mid) update(L,R,C,mid+1,r,p<<1|1);
    pushup(p);
}
int query(int L,int R,int l,int r,int p)
{
    if(L<=l&&r<=R) return tr[p].val;
    if(L>r||R<l) return 0;
    int mid=l+r>>1;
    pushdown(p,mid-l+1,r-mid);
    return query(L,R,l,mid,p<<1)+query(L,R,mid+1,r,p<<1|1);
}
struct node
{
    int l,r,c,id;
}a[400005];
vector<node>v[400005];
int t,n,b[400005],m,ans[400005];
void oper(int col,int x)
{
    for(int i=0;i<v[col].size();i++)
    {
        int l=v[col][i].l,r=v[col][i].r;
        update(l,r,x,1,m,1);
    }
}
int check1(int l,int r)
{
    if(query(l,r,1,m,1)<=0) return inf;
    if(l==r) return l;
    int mid=l+r>>1;
    if(query(mid+1,r,1,m,1)>0) return check1(mid+1,r);
    else return check1(l,mid);
}
int check2(int l,int r)
{
    if(query(l,r,1,m,1)<=0) return inf;
    if(l==r) return l;
    int mid=l+r>>1;
    if(query(l,mid,1,m,1)>0) return check2(l,mid);
    else return check2(mid+1,r);
}
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    //freopen("in.txt", "r", stdin);
    cin>>t;
    while (t--)
    {
        cin>>n;
        m=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i].l>>a[i].r>>a[i].c;
            b[++m]=a[i].l;b[++m]=a[i].r;
            v[i].clear();
        }
        sort(b+1,b+m+1);
        m=unique(b+1,b+m+1)-b-1;
        build(1,m,1);
        for(int i=1;i<=n;i++)
        {
            int l=lower_bound(b+1,b+m+1,a[i].l)-b;
            int r=lower_bound(b+1,b+m+1,a[i].r)-b;
            v[a[i].c].push_back(node{l,r,a[i].c,i});
            update(l,r,1,1,m,1);
        }
        for(int col=1;col<=n;col++)
        {
            oper(col,-1);
            for(int i=0;i<v[col].size();i++)
            {
                int l=v[col][i].l,r=v[col][i].r,id=v[col][i].id;
                ans[id]=inf;
                if(query(l,r,1,m,1)>0)
                {
                    ans[id]=0;
                    continue;
                }
                int c1=check1(1,l),c2=check2(r,m);
                if(c1!=inf) ans[id]=min(ans[id],b[l]-b[c1]);
                if(c2!=inf) ans[id]=min(ans[id],b[c2]-b[r]);
            }
            oper(col,1);
        }
        for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
        cout<<endl;
    }
    return 0;
}

还有一种方式是用multiset来二分的，将所有的l和r存入容器中，然后枚举的时候二分去找离l和r最近的点，感觉这个方法的复杂度是o(nlogn)的，但是好像没有想象中的那么优秀，就比上一个方法快100多ms；

Codeforces Round #826 (Div. 3) F // 线段树 - Jakon - 博客园 (cnblogs.com)

#include <bits/stdc++.h>
#define int long long
#define lowbit(x) ((x)&(-x))
#define endl '\n'
#define double long double
using namespace std;
const int mod=1e9+7;
const int inf=1e9+7;
double qpow(double a,int b)
{
    double res=1;
    while(b)
    {
        if(b&1) res=res*a;
        a=a*a;
        b>>=1;
    }
    return res;
}
struct segtree
{
    int val,lazy;
}tr[400005<<3];
void pushup(int p){tr[p].val=tr[p<<1].val+tr[p<<1|1].val;}
void build(int l,int r,int p)
{
    tr[p].lazy=0;
    if(l==r)
    {
        tr[p].val=0;
        return;
    }
    int mid=l+r>>1;
    build(l,mid,p<<1);
    build(mid+1,r,p<<1|1);
    pushup(p);
}
void pushdown(int p,int ln,int rn)
{
    if(tr[p].lazy)
    {
        tr[p<<1].lazy+=tr[p].lazy;
        tr[p<<1|1].lazy+=tr[p].lazy;
        tr[p<<1].val+=tr[p].lazy*ln;
        tr[p<<1|1].val+=tr[p].lazy*rn;
        tr[p].lazy=0;
    }
}
void update(int L,int R,int C,int l,int r,int p)
{
    if(L<=l&&r<=R)
    {
        tr[p].val+=C*(r-l+1);
        tr[p].lazy+=C;
        return;
    }
    int mid=l+r>>1;
    pushdown(p,mid-l+1,r-mid);
    if(L<=mid) update(L,R,C,l,mid,p<<1);
    if(R>mid) update(L,R,C,mid+1,r,p<<1|1);
    pushup(p);
}
int query(int L,int R,int l,int r,int p)
{
    if(L<=l&&r<=R) return tr[p].val;
    if(L>r||R<l) return 0;
    int mid=l+r>>1;
    pushdown(p,mid-l+1,r-mid);
    return query(L,R,l,mid,p<<1)+query(L,R,mid+1,r,p<<1|1);
}
struct node
{
    int l,r,c,id;
}a[200005];
vector<node>v[200005];
multiset<int>L,R;
int t,n,b[400005],m,ans[400005];
void oper(int col,int x)
{
    for(int i=0;i<v[col].size();i++)
    {
        int l=v[col][i].l,r=v[col][i].r;
        update(l,r,x,1,m,1);
    }
    for(int i=0;i<v[col].size();i++)
    {
        int l=b[v[col][i].l],r=b[v[col][i].r];
        if(x==-1)
        {
            L.erase(L.find(l));R.erase(R.find(r));
        }
        else
        {
            L.insert(l);R.insert(r);
        }
    }
}
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    //freopen("in.txt", "r", stdin);
    cin>>t;
    while (t--)
    {
        cin>>n;
        m=0;
        L.clear();R.clear();
        for(int i=1;i<=n;i++)
        {
            cin>>a[i].l>>a[i].r>>a[i].c; a[i].id=i;
            b[++m]=a[i].l;b[++m]=a[i].r;
            L.insert(a[i].l);R.insert(a[i].r);
            v[i].clear();
        }
        sort(b+1,b+m+1);
        m=unique(b+1,b+m+1)-b-1;
        build(1,m,1);
        for(int i=1;i<=n;i++)
        {
            int l=lower_bound(b+1,b+m+1,a[i].l)-b;
            int r=lower_bound(b+1,b+m+1,a[i].r)-b;
            v[a[i].c].push_back(node{l,r,a[i].c,i});
            update(l,r,1,1,m,1);
        }
        for(int col=1;col<=n;col++)
        {
            if(v[col].size()==0) continue;
            oper(col,-1);
            for(int i=0;i<v[col].size();i++)
            {
                int l=v[col][i].l,r=v[col][i].r,id=v[col][i].id;
                ans[id]=inf;
                if(query(l,r,1,m,1)>0)
                {
                    ans[id]=0;
                    continue;
                }
                auto it1=R.lower_bound(a[id].l);
                if(it1!=R.begin()) ans[id]=min(ans[id],a[id].l-*prev(it1));
                auto it2=L.lower_bound(a[id].r);
                if(it2!=L.end()) ans[id]=min(ans[id],*it2-a[id].r);
            }
            oper(col,1);
        }
        for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
        cout<<endl;
    }
    return 0;
}

最后一种就是真正的o(nlogn)了，去掉了query函数，直接是写了一个二分函数，看懂了第一个方法，再看这个的写法也比较容易了，这其实也算是一个查询的函数了，不过这是查询下标而已

云剪贴板 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

上面的链接来自(26 封私信 / 85 条消息) 严格鸽 - 知乎 (zhihu.com)

#include <bits/stdc++.h>
#define int long long
#define lowbit(x) ((x)&(-x))
#define endl '\n'
#define double long double
using namespace std;
const int mod=1e9+7;
const int inf=3e18;
double qpow(double a,int b)
{
    double res=1;
    while(b)
    {
        if(b&1) res=res*a;
        a=a*a;
        b>>=1;
    }
    return res;
}
struct segtree
{
    int val,lazy;
}tr[400005<<3];
void pushup(int p){tr[p].val=tr[p<<1].val+tr[p<<1|1].val;}
void build(int l,int r,int p)
{
    tr[p].lazy=0;
    if(l==r)
    {
        tr[p].val=0;
        return;
    }
    int mid=l+r>>1;
    build(l,mid,p<<1);
    build(mid+1,r,p<<1|1);
    pushup(p);
}
void pushdown(int p,int ln,int rn)
{
    if(tr[p].lazy)
    {
        tr[p<<1].lazy+=tr[p].lazy;
        tr[p<<1|1].lazy+=tr[p].lazy;
        tr[p<<1].val+=tr[p].lazy*ln;
        tr[p<<1|1].val+=tr[p].lazy*rn;
        tr[p].lazy=0;
    }
}
void update(int L,int R,int C,int l,int r,int p)
{
    if(L<=l&&r<=R)
    {
        tr[p].val+=C*(r-l+1);
        tr[p].lazy+=C;
        return;
    }
    int mid=l+r>>1;
    pushdown(p,mid-l+1,r-mid);
    if(L<=mid) update(L,R,C,l,mid,p<<1);
    if(R>mid) update(L,R,C,mid+1,r,p<<1|1);
    pushup(p);
}
int query(int L,int R,int l,int r,int p)
{
    if(L<=l&&r<=R) return tr[p].val;
    if(L>r||R<l) return 0;
    int mid=l+r>>1;
    pushdown(p,mid-l+1,r-mid);
    return query(L,R,l,mid,p<<1)+query(L,R,mid+1,r,p<<1|1);
}
struct node
{
    int l,r,c,id;
}a[400005];
vector<node>v[400005];
int t,n,b[400005],m,ans[400005];
void oper(int col,int x)
{
    for(int i=0;i<v[col].size();i++)
    {
        int l=v[col][i].l,r=v[col][i].r;
        update(l,r,x,1,m,1);
    }
}
int check1(int L,int l,int r,int p)
{
    if(l>L) return inf;
    if(r<=L)
    {
        if(tr[p].val<=0) return inf;
        if(l==r) return l;
    }
    int mid=l+r>>1;
    pushdown(p,mid-l+1,r-mid);
    int pos=check1(L,mid+1,r,p<<1|1);
    if(pos!=inf) return pos;
    else return check1(L,l,mid,p<<1);
}
int check2(int R,int l,int r,int p)
{
    if(r<R) return inf;
    if(l>=R)
    {
        if(tr[p].val<=0) return inf;
        if(l==r) return l;
    }
    int mid=l+r>>1;
    pushdown(p,mid-l+1,r-mid);
    int pos=check2(R,l,mid,p<<1);
    if(pos!=inf) return pos;
    else return check2(R,mid+1,r,p<<1|1);
}
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    //freopen("in.txt", "r", stdin);
    cin>>t;
    while (t--)
    {
        cin>>n;
        m=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i].l>>a[i].r>>a[i].c;
            b[++m]=a[i].l;b[++m]=a[i].r;
            v[i].clear();
        }
        sort(b+1,b+m+1);
        m=unique(b+1,b+m+1)-b-1;
        build(1,m,1);
        for(int i=1;i<=n;i++)
        {
            int l=lower_bound(b+1,b+m+1,a[i].l)-b;
            int r=lower_bound(b+1,b+m+1,a[i].r)-b;
            v[a[i].c].push_back(node{l,r,a[i].c,i});
            update(l,r,1,1,m,1);
        }
        for(int col=1;col<=n;col++)
        {
            oper(col,-1);
            for(int i=0;i<v[col].size();i++)
            {
                int l=v[col][i].l,r=v[col][i].r,id=v[col][i].id;
                ans[id]=inf;
                if(query(l,r,1,m,1)>0)
                {
                    ans[id]=0;
                    continue;
                }
                int c1=check1(l,1,m,1);
                int c2=check2(r,1,m,1);
                if(c1!=inf) ans[id]=min(ans[id],b[l]-b[c1]);
                if(c2!=inf) ans[id]=min(ans[id],b[c2]-b[r]);
            }
            oper(col,1);
        }
        for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
        cout<<endl;
    }
    return 0;
}

相关文章：

  • MPLS 虚拟专用网络 配置实验
  • AppCode 2022Improves compatibility
  • 【 java 多线程】同步锁 (Lock) 解决线程的安全问题
  • 计算机学院第三周语法组及算法组作业
  • Java数据结构 | 二叉树的基本操作
  • IP分片--为什么单次最大传输1472个字节
  • QT中QThread的各个方法,UI线程关系，事件关系详解(5)
  • Flask-05-——（注册功能的实现，六、1将用户提交的注册数据保存在数据库 六、2 发送AJAX请求 六、3验证码的获取六、4验证码倒计时）
  • 【C++】入门（上）
  • MySQL进阶实战1，数据类型与三范式
  • TYUT太原理工大学2022需求工程考试选择题自测版
  • Xilinx selectIO 资源的使用——input方向
  • Day1——数组 二分查找、移除一个数
  • QT中QThread的各个方法,UI线程关系，事件关系详解(3)
  • RNN模型与NLP应用：文本处理与词嵌入-2
  • ----------
  • 分享的文章《人生如棋》
  • [译]前端离线指南（上）
  • 2017-08-04 前端日报
  • Angular 响应式表单 基础例子
  • C++入门教程（10）：for 语句
  • Mocha测试初探
  • nginx（二）：进阶配置介绍--rewrite用法，压缩，https虚拟主机等
  • Vue实战(四)登录/注册页的实现
  • 从伪并行的 Python 多线程说起
  • 将 Measurements 和 Units 应用到物理学
  • 问:在指定的JSON数据中（最外层是数组）根据指定条件拿到匹配到的结果
  • 优化 Vue 项目编译文件大小
  • #Ubuntu（修改root信息）
  • (70min)字节暑假实习二面（已挂）
  • (a /b)*c的值
  • (AngularJS)Angular 控制器之间通信初探
  • （ｃ语言）strcpy函数用法
  • (搬运以学习)flask 上下文的实现
  • （超详细）语音信号处理之特征提取
  • （附源码）php投票系统 毕业设计 121500
  • （附源码）spring boot校园拼车微信小程序 毕业设计 091617
  • （附源码）springboot优课在线教学系统 毕业设计 081251
  • （三）centos7案例实战—vmware虚拟机硬盘挂载与卸载
  • （十八）用JAVA编写MP3解码器——迷你播放器
  • (十五)使用Nexus创建Maven私服
  • （四）图像的%2线性拉伸
  • （算法设计与分析）第一章算法概述-习题
  • （学习日记）2024.03.25：UCOSIII第二十二节：系统启动流程详解
  • (转)程序员疫苗：代码注入
  • （转）人的集合论——移山之道
  • (轉貼) 資訊相關科系畢業的學生，未來會是什麼樣子？(Misc)
  • .net mvc部分视图
  • .net 获取url的方法
  • .Net 垃圾回收机制原理（二）
  • .NET 中各种混淆（Obfuscation）的含义、原理、实际效果和不同级别的差异（使用 SmartAssembly）
  • 。Net下Windows服务程序开发疑惑
  • // an array of int
  • @Autowired和@Resource的区别
  • @modelattribute注解用postman测试怎么传参_接口测试之问题挖掘