首页 > 其他分享 >Codeforces Round 857 (Div. 2)

Codeforces Round 857 (Div. 2)

时间：2023-03-11 14:55:24浏览次数：42  
标签：857 return ith int Codeforces find ans Div oplus

更好的阅读 第一次进入时加载缓慢，请耐心等待。

赛时降智，菜是原罪。

A. Likes

简单题。

#include <bits/stdc++.h>
using namespace std;
int T,n,a[11111],s[11111];
int main(){
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1; i<=n; i++)cin>>a[i];
        sort(a+1,a+n+1,[](int x,int y){return x>y;});
        int l=1,r=n+1;
        for(int i=1; i<=n; i++){s[i]=s[i-1]+(a[i]>0?1:-1);if(a[i]<0&&n+1==r)r=i;cout<<s[i]<<" ";}
        puts("");
        int now=0,nr=r;
        while(l<nr){
            a[++now]=1;
            l++;
            if(r<=n)a[++now]=-1,r++;
        }
        for(int i=1; i<=n; i++){s[i]=s[i-1]+a[i];cout<<s[i]<<" ";}
        puts("");
    }
    return 0;
}

B. Settlement of Guinea Pigs

简单题,形如 111111111...00000 或 101010101010..0 。

#include <bits/stdc++.h>
using namespace std;
int T;
int n;
int a[111111];
void solve(){
    cin>>n;
    for(int i=1; i<=n; i++)cin>>a[i];
    a[n+1]=2;
    int Not=0,Ans=0,total=0;
    for(int i=1; i<=n+1; i++){
        if(a[i]==1){Not++;}
        else {
            Ans=max(Ans,Not+(total?total/2+1:0));
            total+=Not;
            Not=0;
        }
    }
    cout<<Ans<<endl;
}
int main(){
    cin>>T;
    while(T--)solve();
    return 0;
}

C. The Very Beautiful Blanket

有 \(a_{1,1}\oplus a_{1,2}\oplus a_{2,1}\oplus a_{2,2}=a_{3,3}\oplus a_{3,4}\oplus a_{4,3}\oplus a_{4,4}\) 和 \(a_{1,3}\oplus a_{1,4}\oplus a_{2,3}\oplus a_{2,4}=a_{3,1}\oplus a_{3,2}\oplus a_{4,1}\oplus a_{4,2}\)。

即 \(a_{1,1}\oplus a_{1,2}\oplus a_{2,1}\oplus a_{2,2}\oplus a_{1,3}\oplus a_{1,4}\oplus a_{2,3}\oplus a_{2,4}=a_{3,3}\oplus a_{3,4}\oplus a_{4,3}\oplus a_{4,4}\oplus a_{3,1}\oplus a_{3,2}\oplus a_{4,1}\oplus a_{4,2}\)。

和 \(a_{1,1}\oplus a_{1,2}\oplus a_{2,1}\oplus a_{2,2}\oplus a_{3,1}\oplus a_{3,2}\oplus a_{4,1}\oplus a_{4,2}=a_{3,3}\oplus a_{3,4}\oplus a_{4,3}\oplus a_{4,4}\oplus a_{1,3}\oplus a_{1,4}\oplus a_{2,3}\oplus a_{2,4}\)。

#include <bits/stdc++.h>
using namespace std;
void solve(){
    int n,m;
    cin>>n>>m;
    cout<<n*m<<endl;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            printf("%d ",(i<<8)|(j));
        }
        puts("");
    }
}
int main(){
    int T;
    cin>>T;
    while(T--)
        solve();
    return 0;
}

D. Buying gifts

枚举第一个朋友的最大值，对于第二个朋友可以买的礼物用 set 存储即可。

#include <bits/stdc++.h>
using namespace std;
struct node{int x,y;};
void solve(){
    int n;
    cin>>n;
    multiset<int> Set;
    vector<node> a(n);
    for(node &i:a)scanf("%d %d",&i.x,&i.y),Set.insert(i.y);
    sort(a.begin(),a.end(),[](node x,node y){return x.x>y.x;});
    int now=-0x3f3f3f3f,ans=0x3f3f3f3f;
    for(int i=0; i<n; i++){
        Set.erase(Set.find(a[i].y));
        int x=a[i].x,y=a[i].y;
        if(now>=x)ans=min(ans,now-x);
        else{
            ans=min(ans,x-now);
            auto it=Set.lower_bound(x);
            if(it!=Set.end())ans=min(ans,(*it)-x);
            if(it!=Set.begin())ans=min(ans,abs(x-(*--it)));
        }
        now=max(now,y);
    }
    cout<<ans<<endl;
}
int main(){
    int T;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

E. Music Festival

定义 mx[i] 为第 \(i\) 个专辑的歌曲的最大值，明显的若先听第 \(i\) 个专辑，那么所有 mx[j]<=mx[i] 的专辑 \(j\) 对答案是没有贡献的，所以我们按 mx[i] 排序，定义 \(f_i\) 为 前 \(i\) 个专辑的最大值，枚举第 \(i\) 个专辑到底听几个即可进行转移。

注意本题卡 cin/cout ! 注意专辑内的歌曲顺序不能打乱！

#include <bits/stdc++.h>
using namespace std;

int sx[200000+1],dp[200000+1],mx[200000+1];
vector<int> a[200000+1];
int Len[200000+1];

void solve(){
    int n;
    scanf("%d",&n);
    for(int i=1; i<=n; i++){
        int k,mx=-0x3f3f3f3f;
        scanf("%d",&k);
        Len[i]=0;
        a[i].resize(k+1);
        for(int j=1; j<=k; j++){
            int x;
            scanf("%d",&x);
            if(x>mx)a[i][++Len[i]]=x,mx=x;
        }
        a[i].resize(Len[i]+1);
        sx[i]=i;
    }
    sort(sx+1,sx+n+1,[](int x,int y){return a[x][Len[x]]<a[y][Len[y]];});
    for(int i=1; i<=n; i++)mx[i]=a[sx[i]][Len[sx[i]]];
    dp[0]=0;
    for(int i=1; i<=n; i++){
        dp[i]=dp[i-1];
        int pos=sx[i];
        for(int j=1; j<=Len[pos]; j++){
            int othpos=lower_bound(mx+1,mx+n+1,a[pos][j])-mx;
            dp[i]=max(dp[i],dp[othpos-1]+Len[pos]-j+1);
        }
    }
    printf("%d\n",dp[n]);
    return ;
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        solve();
    }
    return 0;
}

F. The way home

贪心的想，演唱会只会在 w[i] 最高的地方演出。

定义 dp[i][j] 表示 目前在城市 i ,所有经过的城市中 w[i] 最大的城市为 j 的最小演唱次数，其次是最大钱数，进行转移即可，考虑到 n 比较小，可以用 floyd 进行预处理。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=3001;
ll value[N],dist[N][N],sx[N];
pair<ll,ll> ans[N];
void solve(){
    ll n,m,p;
    scanf("%lld %lld %lld",&n,&m,&p);
    for(ll i=1; i<=n; i++){
        scanf("%lld",&value[i]);
        sx[i]=i;
        for(ll j=1; j<=n; j++)dist[i][j]=i==j?0:1e18;
    }
    if(n>2)sort(sx+2,sx+n,[](ll x,ll y){return value[x]<value[y];});
    for(ll i=1; i<=m; i++){
        ll u,v,val;
        scanf("%lld %lld %lld",&u,&v,&val);
        dist[u][v]=min(dist[u][v],val);
    }
    for(ll k=1; k<=n; k++)for(ll i=1; i<=n; i++)
    for(ll j=1; j<=n; j++)dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
    for(ll i=2; i<=n; i++)ans[i]=make_pair(1e17,-1e17);
    ans[1]=make_pair(0,-p);
    for(ll i=1; i<=n; i++)
    for(ll j=1; j<=n; j++)
    if(dist[sx[i]][j]!=1e18){
        ll v=max(0ll,(dist[sx[i]][j]+ans[sx[i]].second+value[sx[i]]-1)/value[sx[i]]);
        ans[j]=min(ans[j],make_pair(ans[sx[i]].first+v,ans[sx[i]].second-v*value[sx[i]]+dist[sx[i]][j]));
    }
    if(ans[n].first>1e16)puts("-1");
    else cout<<ans[n].first<<endl;
    return ;
}
int main(){
    ll T;
    scanf("%lld",&T);
    while(T--){
        solve();
    }
    return 0;
}

G. Gasoline prices

明显的，每一次操作是对两条路径的第 i 个节点进行取交（两个区间的交集）操作，考虑暴力对其进行取交操作。

不明显的，我们要优化暴力。

考虑并查集进行优化，减少无意义的计算，若 \(a\) 至 \(b\) 和 \(c\) 至 \(d\) 进行了取交操作， \(e\) 至 \(f\) 和 \(c\) 至 \(d\) 也进行了取交操作,那么再对 \(a\) 至 \(b\) 和 \(e\) 至 \(f\) 进行了取交操作是没有意义的。（\(a,b\) 的 \(lca\) 是 b, \(c,d,e,f\) 同理）

考虑并查集维护什么，可以发现，我们只用维护长度 \(2^i\) 的段（该段的端点 \(a,b\) 满足 \(a\) 是 \(b\) 的 祖先或满足 \(b\) 是 \(a\) 的祖先），方便计算，主要是空间开不下。

算法的主体已经确定：暴力修改加并查集剪掉无用计算，每一次修改的长度都是 \(2^i\) ，时间复杂度为 \(O(\text{能过})\) 。

对于暴力，一共有两种情况：

  • 同向，若两个长度是 \(2^i\) 的段已经在同一个集合，直接返回，否则递归处理两个长度为 \(2^{i-1}\) 的子区间，顺便合并两个段所在的集合。

  • 逆向，和同向相似，只是递归的子区间不同。

考虑并查集的套路，扩展域即可同时维护两种情况。

暴力合并两个点：

// 合并两个点
void merge(int x,int y){
    x=find(x,f1),y=find(y,f1);
    if(x==y)return;
    ans=1ll*ans*1ll*ksm(max(0ll,1ll*(R[x]-L[x]+1)),mod-2)%mod;
    ans=1ll*ans*1ll*ksm(max(0ll,1ll*(R[y]-L[y]+1)),mod-2)%mod; // 撤销贡献
    f1[x]=y;
    L[y]=max(L[x],L[y]);
    R[y]=min(R[x],R[y]);
    ans=1ll*ans*1ll*1ll*max(0ll,1ll*(R[y]-L[y]+1))%mod; // 加上新贡献
}

暴力合并两个长度为 \(2^i\) 的同向段：

// 合并同向等长段
void merge1(int x,int y,int ith){
    if(find(x,f2[ith])==find(y,f2[ith]))return; // 剪枝
    if(ith==0)return merge(x,y),void(); // 直接合并
    f2[ith][find(x,f2[ith])]=find(y,f2[ith]); // 并查集合并
    merge1(x,y,ith-1);
    merge1(ST[x][ith-1],ST[y][ith-1],ith-1); // 暴力合并两个子段
}

暴力合并两个逆向段：

// 合并逆向等长段
void merge2(int x,int y,int ith){
    if(find(x,f2[ith])==find(y+n,f2[ith]))return; // 剪枝
    if(ith==0)return merge(x,y),void();
    f2[ith][find(x+n,f2[ith])]=find(y,f2[ith]);// 并查集合并
    f2[ith][find(x,f2[ith])]=find(y+n,f2[ith]);
    merge2(x,ST[y][ith-1],ith-1); // 与合并同向等长段不同
    merge2(ST[x][ith-1],y,ith-1); // 暴力合并两个子段
}

总代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN=2e5+11,mod=1e9+7;

int ST[MAXN][18],depth[MAXN];

int h[MAXN],nt[MAXN<<1],to[MAXN<<1],linkcnt;

int L[MAXN],R[MAXN],n,ans=1;

int f1[MAXN],f2[18][MAXN<<1];

int ksm(int x,int y){
    int cur=1;
    for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)cur=1ll*cur*x%mod;
    return cur;
}

// UNION_FIND_SETS
int find(int u,int *UNION_FIND_SETS){
    return UNION_FIND_SETS[u]==u?u:UNION_FIND_SETS[u]=find(UNION_FIND_SETS[u],UNION_FIND_SETS);
}

void link(int u,int v){
    nt[++linkcnt]=h[u],h[u]=linkcnt,to[linkcnt]=v;
}

void dfs_init(int u,int father){
    depth[u]=depth[father]+1;

    f1[u]=u;
    for(int i=0; i<=17; i++)
        f2[i][u]=u,f2[i][u+n]=u+n;

    ST[u][0]=father;
    for(int i=1; i<=17; i++)
        ST[u][i]=ST[ST[u][i-1]][i-1];

    for(int i=h[u]; i; i=nt[i]){
        if(to[i]==father)continue;
        dfs_init(to[i],u);
    }
}

int LCA(int u,int v){
    if(depth[u]<=depth[v])swap(u,v);
    for(int i=17; i>=0; i--)if(depth[ST[u][i]]>=depth[v])u=ST[u][i];
    if(u==v)return u;
    for(int i=17; i>=0; i--)if(ST[u][i]!=ST[v][i])u=ST[u][i],v=ST[v][i];
    return ST[u][0];
}

int kth_fa(int u,int dist){
    for(int i=0; i<=17; i++)
        if(((1<<i)&dist))u=ST[u][i];
    return u;
}

// 合并两个点
void merge(int x,int y){
    x=find(x,f1),y=find(y,f1);
    if(x==y)return;
    ans=1ll*ans*1ll*ksm(max(0ll,1ll*(R[x]-L[x]+1)),mod-2)%mod;
    ans=1ll*ans*1ll*ksm(max(0ll,1ll*(R[y]-L[y]+1)),mod-2)%mod;
    f1[x]=y;
    L[y]=max(L[x],L[y]);
    R[y]=min(R[x],R[y]);
    ans=1ll*ans*1ll*1ll*max(0ll,1ll*(R[y]-L[y]+1))%mod;
}

// 合并同向等长段
void merge1(int x,int y,int ith){
    if(find(x,f2[ith])==find(y,f2[ith]))return;
    if(ith==0)return merge(x,y),void();
    f2[ith][find(x,f2[ith])]=find(y,f2[ith]);
    merge1(x,y,ith-1);
    merge1(ST[x][ith-1],ST[y][ith-1],ith-1);
}

// 合并逆向等长段
void merge2(int x,int y,int ith){
    if(find(x,f2[ith])==find(y+n,f2[ith]))return;
    if(ith==0)return merge(x,y),void();
    f2[ith][find(x+n,f2[ith])]=find(y,f2[ith]);
    f2[ith][find(x,f2[ith])]=find(y+n,f2[ith]);
    merge2(x,ST[y][ith-1],ith-1);
    merge2(ST[x][ith-1],y,ith-1);
}

int main(){
    scanf("%d",&n);
    for(int i=2; i<=n; i++){
        static int f;
        scanf("%d",&f);
        link(f,i);
    }
    dfs_init(1,0);
    for(int i=1; i<=n; i++){
        scanf("%d %d",&L[i],&R[i]);
        ans=1ll*1ll*ans*max(0ll,1ll*(R[i]-L[i]+1))%mod;
    }
    int Q_sum;
    scanf("%d",&Q_sum);
    for(int Text=1; Text<=Q_sum; Text++){
        int a,b,c,d,lca_of_a_b,lca_of_c_d,T;
        scanf("%d %d %d %d",&a,&b,&c,&d);
        
        lca_of_a_b=LCA(a,b);
        lca_of_c_d=LCA(c,d);
        
        // 合并同向等长段
        T=min(depth[a]-depth[lca_of_a_b],depth[c]-depth[lca_of_c_d]);
        for(int i=17; i>=0; i--)if((T&(1<<i)))merge1(a,c,i),a=ST[a][i],c=ST[c][i];

        T=min(depth[b]-depth[lca_of_a_b],depth[d]-depth[lca_of_c_d]);
        for(int i=17; i>=0; i--)if((T&(1<<i)))merge1(b,d,i),b=ST[b][i],d=ST[d][i];

        // 合并逆向等长段
        if(a==lca_of_a_b){
            T=depth[b]-depth[lca_of_a_b]+1;
            for(int i=17; i>=0; i--){
                if((T&(1<<i))){
                    T^=(1<<i);
                    merge2(b,kth_fa(c,T),i);
                    b=ST[b][i];
                }
            }
        }
        else{
            T=depth[a]-depth[lca_of_a_b]+1;
            for(int i=17; i>=0; i--){
                if((T&(1<<i))){
                    T^=(1<<i);
                    merge2(a,kth_fa(d,T),i);
                    a=ST[a][i];
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

标签：857,return,ith,int,Codeforces,find,ans,Div,oplus
From： https://www.cnblogs.com/dadidididi/p/17206044.html

相关文章

  • 练习记录-cf-div2-A-D
    上课的时候抓紧时间写的，状态不好，c也没过，估计换个环境也很难想吧ALikes题意点赞，a<0表示取消赞a>0表示增加赞，a数组乱序输出如何排让赞数价值最多分别记录大于0和小......
  • Codeforces Round 857 (Div. 2)（持续更新）
    Preface貌似CF的Div1/Div2分场就有1900的分界线，大号打不了Div2就很难受同时我对自己的水平有清晰的认知，现在打这种纯Div1的场肯定就是纯被虐，所以也不敢去Div1所以索性开......
  • Vue实现div可拖动组件 并可操纵盒子大小
    Vue实现div可拖动组件并可操纵盒子大小借鉴文章:https://blog.csdn.net/qq_46103732/article/details/128902192场景：在pc端项目中会碰到弹框后多个页面重叠的场景，类似......
  • vue動態產生div及v-model數據綁定
    html模板遍歷會涉及到v-model對值的綁定，這里的思路是根據數組中的下標尋找對應行數據<divclass="row"v-for="item,indexinitems"><divclass="col-3">......
  • CFR-857解题报告
    比赛传送门A.TheVeryBeautifulBlanket题意：构造一个\(n\timesm\)的矩阵，使得任意\(4\times4\)的子矩阵中，左上\(2\times2\)与右下\(2\times2\)的矩阵的异......
  • [Codeforces Round 857 (Div. 1)][Codeforces 1801A~1801G（部分）]
    FST哩，好似！本来能+80的，现在只加了30，相当于掉了50分捏1801A-TheVeryBeautifulBlanket题目大意：要求构造一个\(n\timesm\)的矩阵\(B\)，使得对任意一个\(4\times4\)......
  • Codeforces Round 856 (Div. 2)
    Preface补题，话说这场题目数量好少的说……除了E题有点新花样前面题目都很简单的说，不过最后一天疯狂卡自然溢出的Hash，WA了一页可还行A.PrefixandSuffixArraySB题，我......
  • CodeForces 1789F Serval and Brain Power
    洛谷传送门CF传送门很牛逼的题啊！感觉套路很实用，感谢ntf。考虑\(totlen=cnt\timeslen\le80\)。若\(cnt\le3\)，可以\(O(|S|^{2cnt-1})\)暴力枚分割点。\(c......
  • CF1780F Codeforces Round 846 (Div. 2) F. Three Chairs
    https://codeforces.com/contest/1780/problem/F计算\[\sum_{i,j,k}[gcd(min(a_i,a_j,a_k),max(a_i,a_j,a_k))=1]\]对\(a_i\)排序，则需计算\[\sum_{i<k......
  • HTML5 Canvas 与 SVG 与 div
    动态创建元素并能够移动它们的最佳方法是什么？例如，假设我想创建一个矩形、圆形和多边形，然后选择这些对象并将它们四处移动。我知道HTML5提供了三个元素可以使这成为......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99