首页 > 其他分享 >CF1416 Div.1 VP记

CF1416 Div.1 VP记

时间：2023-05-03 12:11:39浏览次数：49  
标签：write CF1416 10 int void VP ch Div.1 define

好久没打CF了，感觉写代码能力有所下降，vp一场看看，差点被阻击没了。

A

CF题面

先考虑将某一个数字提出来，可以发现如果这个数字要对答案造成贡献，那么 \(k\) 最小为没有该数字的区间中最长的区间长度加一。

点击查看代码 
#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=3e5+10;
vector<int>sum[N];
int n,ans[N];
void solve(){
    read(n);
    for(int i=1;i<=n;i++){
        vector<int>().swap(sum[i]);
        ans[i]=n+1;
        sum[i].pb(0);
    }
    for(int i=1,x;i<=n;i++){
        read(x);
        sum[x].pb(i);
    }
    for(int i=1;i<=n;i++){
        if(sum[i].size()>1){
            sum[i].pb(n+1);
            int mx=0;
            for(int j=0;j<sum[i].size()-1;j++){
                mx=max(mx,sum[i][j+1]-sum[i][j]);
            }
            ans[mx]=min(ans[mx],i);
        }
    }
    write_space(ans[1]==n+1?-1:ans[1]);
    for(int i=2;i<=n;i++){
        ans[i]=min(ans[i],ans[i-1]);
        write_space(ans[i]==n+1?-1: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;
}

B

CF题面

无解很容易判，只需要知道和是不是 \(n\) 的倍数即可。

对于不是无解的，有一个很容易想到的想法，\(1\) 是个很好的中转站，可以将所有数全部放到 \(1\) 上，最后再从 \(1\) 上放回去。

于是我们有了以下策略：

  • 将 \(i\) 上的数变为 \(i\) 的倍数
  • 将 \(i\) 上的数全部移到 \(1\) 上
  • 最后将 \(1\) 上的数平均分配到 \(2\sim n\) 上

现在证明每一步都只需要一次操作。
后面两个操作显然。对于第一个操作，因为 \(p_i\ge 1\)，所以在做 \(i\) 之前，\(1\) 上的数大于等于 \(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=1e4+10;
int n,a[N];
void solve(){
    read(n);
    int sum=0;
    for(int i=1;i<=n;i++){
        read(a[i]);
        sum+=a[i];
    }
    if(sum%n){
        puts("-1");
        return;
    }
    sum/=n;
    vector<tuple<int,int,int>>ans;
    for(int i=2;i<=n;i++){
        ans.pb(make_tuple(1,i,i-1-(a[i]-1)%i));
        ans.pb(make_tuple(i,1,(a[i]-1)/i+1));
    }
    for(int i=2;i<=n;i++){
        ans.pb(make_tuple(1,i,sum));
    }
    write_endl(ans.size());
    for(auto x:ans){
        write_space(get<0>(x)),write_space(get<1>(x)),write_endl(get<2>(x));
    }
}
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

CF题面

看到异或第一反应 01trie。因为异或对于每一位是独立的，将所有数插入 01trie 后，可以算出 \(x\) 每一位为 \(0/1\) 会带来多少逆序对的贡献。

要算出每一位为 \(0/1\) 会带来的贡献，可以每一个点开一个vector，存储该点子树内的数在原序列中的位置分别为哪些。在树上提一个点出来，它的左右子树分别代表下一位为 \(0/1\) 的数，将两个vector提出来是两个有序序列，同时第二个序列代表的数一定大于第一个序列，\(O(n)\) 扫一遍可以得到 \(x\) 下一位为 \(0\) 的逆序对数，用总对数减去下一位为 \(0\) 的逆序对数即为下一位为 \(1\) 的逆序对数。

因为每个数最多比较 \(\log V\) 次，也最多属于 \(\log V\) 个vector，所以时空复杂度均为 \(O(n\log V)\)，\(V\) 代表值域。

注意：\(10^7\) 个vector空间常数也算挺大的，要稍微卡下空间。

点击查看代码 
#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=3e5+10,Lg=30;
int n,a[N],cnt=1;
ll tot[Lg+5][2];
struct node{
    int ch[2];
    vector<int>num;
}point[N*(Lg+5)];
void ins(int x,int id){
    int now=1;
    for(int i=Lg;i>=0;i--){
        int s=x>>i&1;
        if(!point[now].ch[s]){
            point[now].ch[s]=++cnt;
        }
        now=point[now].ch[s];
        point[now].num.pb(id);
    }
}
void dfs(int now,int p){
    int ls=point[now].ch[0],rs=point[now].ch[1];
    if(ls){
        dfs(ls,p-1);
    }
    if(rs){
        dfs(rs,p-1);
    }
    if(!ls||!rs){
        return;
    }
    int pos=0;
    ll s=0,sum=1ll*point[ls].num.size()*point[rs].num.size();
    for(auto x:point[ls].num){
        while(pos<point[rs].num.size()&&point[rs].num[pos]<x){
            pos++;
        }
        s+=pos;
    }
    tot[p][0]+=s;
    tot[p][1]+=sum-s;
}
void solve(){
    read(n);
    for(int i=1;i<=n;i++){
        read(a[i]);
        ins(a[i],i);
    }
    dfs(1,Lg);
    ll ans=0,sum=0;
    for(int i=0;i<=Lg;i++){
        if(tot[i][0]<=tot[i][1]){
            ans+=tot[i][0];
        }
        else{
            ans+=tot[i][1];
            sum+=(1ll<<i);
        }
    }
    write_space(ans),write_endl(sum);
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}

D

写完C时间就不怎么够了，D只能算是做的了，一做还做了两个多小时。

CF题面

看到删边，但没有加边，可以想到将操作反过来，变成加边（不会还有人想写LCT那个时代的眼泪吧）。因为维护的是连通性，所以可以给每次操作赋一个时间，给没删去的边赋上时间 \(inf\)，使用 Kruskal 维护最大生成树，得到每个时刻某个点属于哪个连通块。
但怎么维护某个时刻与某个点连通的点有哪些，线段树合并？显然不是很好。

这时候我们想起了一个被遗忘了很久的东西————Kruskal重构树，我们在求最大生成树时将一条边看作一个新点，从它向原来两棵树的根连边，可以发现在 \(t\) 时刻，与点 \(u\) 连通的点和边均在某个点的子树内，而这个点就是 \(t\) 时刻 \(u\) 所在重构树的根。最后可以通过求dfs序，让操作一变为求某一个区间的最大值，并将其变为 \(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=4e5+10,Q=5e5+10,M=3e5+10;
int n,m,q,val[N],fa[N],del[N],cnt;
struct edge{
    int u,v;
}G[N];
struct query{
    int opt,p;
}que[Q];
vector<int>e[N];
int getfa(int x){
    if(fa[x]!=x){
        fa[x]=getfa(fa[x]);
    }
    return fa[x];
}
void merge(int u,int v){
    u=getfa(u),v=getfa(v);
    if(u!=v){
        fa[u]=fa[v]=fa[cnt]=++cnt;
        e[cnt].pb(u);
        e[cnt].pb(v);
    }
}
int dfn[N],siz[N],a[N],idx;
void dfs(int u){
    dfn[u]=++idx;
    a[idx]=val[u];
    siz[u]=1;
    for(auto v:e[u]){
        dfs(v);
        siz[u]+=siz[v];
    }
}
pii mx[N<<2];
int ls(int p){
    return p<<1;
}
int rs(int p){
    return p<<1|1;
}
pii qmax(pii x,pii y){
    if(x.first==y.first){
        if(x.second>y.second){
            return x;
        }
    }
    if(x.first>y.first){
        return x;
    }
    return y;
}
void push_up(int p){
    mx[p]=qmax(mx[ls(p)],mx[rs(p)]);
}
void build(int p,int l,int r){
    if(l==r){
        mx[p]=mp(a[l],l);
        return;
    }
    int mid=(l+r)>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    push_up(p);
}
void update(int p,int l,int r,int pos,int v){
    if(l==r){
        mx[p]=mp(v,pos);
        return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid){
        update(ls(p),l,mid,pos,v);
    }
    else{
        update(rs(p),mid+1,r,pos,v);
    }
    push_up(p);
}
pii query(int p,int l,int r,int q_l,int q_r){
    if(q_l<=l&&r<=q_r){
        return mx[p];
    }
    int mid=(l+r)>>1;
    pii res;
    res=mp(0,0);
    if(q_l<=mid){
        res=qmax(res,query(ls(p),l,mid,q_l,q_r));
    }
    if(q_r>mid){
        res=qmax(res,query(rs(p),mid+1,r,q_l,q_r));
    }
    return res;
}
void solve(){
    read(n),read(m),read(q);
    cnt=n;
    for(int i=1;i<=n;i++){
        read(val[i]);
    }
    for(int i=1;i<=m;i++){
        read(G[i].u),read(G[i].v);
    }
    for(int i=1;i<=q;i++){
        read(que[i].opt),read(que[i].p);
        if(que[i].opt==2){
            del[que[i].p]=1;
        }
    }
    for(int i=1;i<=n*2;i++){
        fa[i]=i;
    }
    for(int i=1;i<=m;i++){
        if(!del[i]){
            merge(G[i].u,G[i].v);
        }
    }
    for(int i=q;i;i--){
        if(que[i].opt==2){
            merge(G[que[i].p].u,G[que[i].p].v);
        }
        else{
            que[i].p=getfa(que[i].p);
        }
    }
    for(int i=1;i<=cnt;i++){
        int x=getfa(i);
        if(!dfn[x]){
            dfs(x);
        }
    }
    build(1,1,cnt);
    for(int i=1;i<=q;i++){
        if(que[i].opt==1){
            pii ans=query(1,1,cnt,dfn[que[i].p],dfn[que[i].p]+siz[que[i].p]-1);
            write_endl(ans.first);
            update(1,1,cnt,ans.second,0);
        }
    }
}
signed main(){
    #ifndef ONLINE_JUDGE
        freopen("1.in","r",stdin);
        freopen("1.out","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}

标签：write,CF1416,10,int,void,VP,ch,Div.1,define
From： https://www.cnblogs.com/luoshen0/p/17368896.html

相关文章

  • 2022CVPR_Toward Fast, Flexible, and Robust Low-Light Image Enhancement（SCI_main）
    1.motivation（1）低光增强不能处理复杂的场景（2）需要耗费大量的计算2.contribution（1）节省计算（2）发明了自监督的SCI模块（SCI的核心是引入额外的网络模块（自校准照明）来辅助训练，而不是用于测试）大佬链接：(11条消息)低照度增强--论文阅读【《TowardFast,Flexible,andRobustLow-Light......
  • 从 VPG 到 PPO
    这篇博客总结自WoutervanHeeswijk在Medium的文章：ProximalPolicyOptimization(PPO)Explained策略梯度算法（VPG）从确定性策略开始强化学习的目标是学习一个好的决策策略\(\pi\)，随着时间的推移最大化奖励。确定性策略\(π\)的做法是基于状态\(s\)，利用策略函数\(\pi:s......
  • EVPN(1)
    目录基本概念EVPN基本介绍EVPN的设计何止强悍理解路由类型EVPN启动过程EVPN原理术语基本工作流程概述三张表再看工作流程问题MPLS&EVPN实验基本概念EVPN基本介绍EVPN的全称是EthnernetVirtualPrivateNetwork，直译为“以太网虚拟私有网络”，由2015年新增的RFC7432定义，RFC7432......
  • Codeforces Round 869 (Div.1 & Div.2) 题解
    2A.Politics因为编号为\(1\)的人一定不会离开，那么最后留下的人一定要和编号为\(1\)的人的所有参数都一致，所以计数即可。#include<bits/stdc++.h>#include<ext/pb_ds/assoc_container.hpp>#include<ext/pb_ds/tree_policy.hpp>#include<ext/pb_ds/hash_policy.hpp>u......
  • CamstarVP下拉选，筛选失效
    //CopyrightSiemens2019usingCamstar.WCF.ObjectStack;usingCamstar.WebPortal.FormsFramework;usingCamstar.WebPortal.FormsFramework.Utilities;usingCamstar.WebPortal.WCFUtilities;usingSystem;namespaceCamstar.WebPortal.WebPortlets{public......
  • CVPR'23｜向CLIP学习预训练跨模态！简单高效的零样本参考图像分割方法
    前言 本文提出了一种zero-shot的Referringimagesegmentation方法，该方法利用了来自CLIP的pre-train的跨模态知识。所提方法的性能明显优于所有基线方法和监督较弱的方法。本文转载自极市平台作者|CV开发者都爱看的仅用于学术分享，若侵权请联系删除欢迎关注公众号CV技术指南......
  • rempe-2023-Trace and Pace: Controllable Pedestrian Animation via Guided Trajecto
    #TraceandPace:ControllablePedestrianAnimationviaGuidedTrajectoryDiffusion#paper1.paper-info1.1MetadataAuthor::[[DavisRempe]],[[ZhengyiLuo]],[[XueBinPeng]],[[YeYuan]],[[KrisKitani]],[[KarstenKreis]],[[SanjaFidler]],[[OrLi......
  • CF1479 Div1 VP记录
    战况：别的不说，这个B1WA3发是真的精髓。A略B我们设此时在第一队队尾的为las0，在第二队队尾的为las1，要放的数为x。先考虑B1：显然有：如果las0等于x，放在第二队，如果las1等于x，放在第一队。考虑两边都不同的情况，我们想要这个x后面尽快跟上一个不同的数，依此来创造新的......
  • sun-2023-DeFeeNet-CVPR
    #DeFeeNet:Consecutive3DHumanMotionPredictionwithDeviationFeedback#paper1.paper-info1.1MetadataAuthor::[[XiaoningSun]],[[HuaijiangSun]],[[BinLi]],[[DongWei]],[[WeiqingLi]],[[JianfengLu]]作者机构::njust.edu.cnKeywords::#HMPJou......
  • agc020 vp记录
    a,b是签到题。[AGC020C]MedianSum一个集合由N个整数组成，请求出它的非空子集和的中位数。（\(N<=2000\)\(A_i<=2000\)） 发现所有的子集和是关于所有数的和对称的。即有\(X\)则有\(\sum{A_i}-X\)，于是通过背包优化的bitset算出所有能拼出的数，从$\frac{\sum{A_i}}{2}$......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99