欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

Codeforces Round #665 (Div. 2)

程序员文章站 2022-09-01 09:45:34
2020/8/21 晚上打完球就22:10了,愣是没报上名(cf打不开,然后就做了一下赛后交的过了3个题A - Distance and Axis数学题分类讨论一下即可#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)#pragma GCC optimize(2)#include#includeusing namespace std;int n,k;int...

2020/8/21 晚上打完球就22:10了,愣是没报上名(cf打不开,然后就做了一下赛后交的过了3个题

A - Distance and Axis

数学题分类讨论一下即可

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
using namespace std;
int n,k;
int main()
{
    IO;
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n>>k;
        int res=0;
        if(k>n)
        {
            res+=k-n;
        }
        else
        {
            if(k%2!=n%2) res++;
        }
        cout<<res<<endl;
    }
    return 0;
}

B - Ternary Sequence

贪心,先让第一个序列的2找第二个序列的1配对(加分), 然后看看第一个序列的1先找第二个序列的0和1配对(分数不变),最后找第二个序列2配对(减分)

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
ll x,y,z;
ll a,b,c;
int main()
{
    IO;
    int T;
    cin>>T;
    while(T--)
    {
        cin>>x>>y>>z;
        cin>>a>>b>>c;
        ll res=0;
        res+=2*min(z,b);
        y-=a;
        y-=b-min(z,b);
        if(y>0) res-=2*y;
        cout<<res<<endl;
    }
    return 0;
}

C - Mere Array

这题是个脑筋急转弯。首先先找到数组中最小的数mina如果想要交换两个数,那么两个数的最大公因数必须是mina,然后可以先把原数组排序不妨记作数组b[],如果a[i]!=b[i]说明原数组中该位置的值需要交换位置,那么这个数必须是mina的倍数,并且只要是这个数的倍数就一定能交换(我们可以考虑让它和mina所在位置交换)。因此只要位置不正确的数全都是mina的倍数就可以满足题意。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=200010;
int a[N],b[N];
int n;
int main()
{
    IO;
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n;
        int mina=1e9+1;
        for(int i=1;i<=n;i++) 
        {
            cin>>a[i];
            b[i]=a[i];
            mina=min(mina,a[i]);
        }
        sort(b+1,b+1+n);
        bool ok=1;
        for(int i=1;i<=n;i++)
            if(a[i]!=b[i]&&a[i]%mina!=0) 
            {
                ok=0;
                break;
            }
        if(ok) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

D - Maximum Distributed Tree

贪心:可以考虑统计每条边通过的次数,然后通过次数多的分配边权最大。
如何统计每条边通过次数?
考虑树中的一条边,如果将该边去掉将会分成两部分,可以统计该两部分的点的数量,该边的通过次数即两部分相乘一部分点数为sz那么另一部分即为n-sz那么该边通过次数即sz*(n-sz)。跑一个dfs即可统计出来。
目前有n-1条边待分配边权,有m个边权值,如果m>n-1,把前几个大数乘起来(保证所有边权乘起来等于k)分配给经过边数最多的那条边。如果m==n-1那么就一个边一个数贪心经过次数多的边权重大。如果m<n-1最后几条边权重是1。
(之前没考虑m>n-1这种情况wwwsTO)

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int mod=1e9+7;
const int N=100010,M=2*N;
int n,m;
int h[N],e[M],ne[M],idx;
vector<ll>w;
ll sz[N],p[N];
void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
void dfs(int u,int fa)
{
    sz[u]=1;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==fa) continue;
        dfs(j,u);
        sz[u]+=sz[j];
        w.push_back(1ll*sz[j]*(n-sz[j]));
    }
}
void init(int n)
{
    for(int i=0;i<=n;i++) h[i]=-1;
    w.clear();
    idx=0;
}
int main()
{
    IO;
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n;
        init(n);
        for(int i=1;i<n;i++)
        {
            int a,b;
            cin>>a>>b;
            add(a,b);
            add(b,a);
        }
        cin>>m;
        for(int i=0;i<m;i++) cin>>p[i];
        sort(p,p+m);reverse(p,p+m);
        dfs(1,-1);
        sort(w.begin(),w.end());reverse(w.begin(),w.end());
        ll res=0;
        if(m<=w.size())
        {
            for(int i=0;i<m;i++) res=(res+1ll*(w[i]%mod*p[i]%mod))%mod;
            for(int i=m;i<w.size();i++) res=(res+w[i])%mod;
        }
        else
        {
            int k=m-w.size();
            res=w[0]%mod;
            for(int i=0;i<=k;i++) res=res*p[i]%mod;
            for(int i=k+1;i<m;i++) res=(res+w[i-k]%mod*p[i]%mod)%mod;
        }
        cout<<res<<endl;
    }
    return 0;
}

F-Reverse and Swap

F题Reverse and Swap
留个坑,回来补这题数据结构
2020/8/23补
方法一:
首先这题单点修改,区间查询无疑线段树可以做。
考虑如何进行区间交换?
由于数组线段树固定做儿子和右儿子的下标父节点 u 左孩子u<<1 右孩子u<<1|1,传统方式不宜进行区间交换,因此采用指针方式记录左右孩子(主席树方式)那么区间交换直接交换左右孩子即可,而区间反转则是递归交换左右子树直到叶子节点。
尝试用懒标极维护区间操作:lazy看成一个二进制数(状态压缩),对于一个节点如果lazy^id!=0说明id中的1所在的位置lazy中也是1那么表示需要该节点的左右子树。
于是区间反转则是在根节点直接打上标记tree[root].lazy^=(1<<(k+1))-1;
区间交换则tree[root].lazy^=1<<(k+1);
参考大佬题解

// [1 2 3 4        5 6 7 8]           1000   id:3
// [1 2 3 4]      [5 6 7 8]           0100   id:2
// [1 2] [3 4]  [5 6] [7 8]           0010   id:1 
// [1][2][3][4][5][6][7][8]           0001   id:0
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<vector>
#include<set>
#include<map>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=(1<<18)+10;
int n,q;
ll a[N];
struct node
{
    int l,r;
    ll s;
    int id,lazy;
}tree[40*N];
int cnt,root;
void pushup(int u)
{
    tree[u].s=tree[tree[u].l].s+tree[tree[u].r].s;
}
void pushdown(int u)
{
    if(tree[u].id&tree[u].lazy)
    {
        swap(tree[u].l,tree[u].r);
        tree[u].lazy^=tree[u].id;
    }
    tree[tree[u].l].lazy^=tree[u].lazy;
    tree[tree[u].r].lazy^=tree[u].lazy;
    tree[u].lazy=0;

}
void build(int &u,int l,int r)
{
    u=++cnt;
    tree[u].id=r-l+1;
    tree[u].lazy=0;
    if(l==r)
    {
        tree[u].s=a[l];
        return;
    }
    int mid=l+r>>1;
    build(tree[u].l,l,mid);
    build(tree[u].r,mid+1,r);
    pushup(u);
}
void modify(int u,int l,int r,int pos,int x)
{
    if(l==r)
    {
        tree[u].s=x;
        return;
    }
    pushdown(u);
    int mid=l+r>>1;
    if(pos<=mid) modify(tree[u].l,l,mid,pos,x);
    else modify(tree[u].r,mid+1,r,pos,x);
    pushup(u);
}
ll query(int u,int l,int r,int vl,int vr)
{
    if(vl<=l&&r<=vr) return tree[u].s;
    pushdown(u);
    int mid=l+r>>1;
    ll v=0;
    if(vl<=mid) v+=query(tree[u].l,l,mid,vl,vr);
    if(vr>mid) v+=query(tree[u].r,mid+1,r,vl,vr);
    pushup(u);
    return v;
}
void rev(int k)
{
    tree[root].lazy^=(1<<(k+1))-1;
    if(tree[root].id&tree[root].lazy)
    {
        swap(tree[root].l,tree[root].r);
        tree[root].lazy^=tree[root].id;
    }
}
void swp(int k)
{
    tree[root].lazy^=1<<(k+1);
    if(tree[root].id&tree[root].lazy)
    {
        swap(tree[root].l,tree[root].r);
        tree[root].lazy^=tree[root].id;
    }
}
int main()
{
    IO;
    cin>>n>>q;
    for(int i=1;i<=1<<n;i++) cin>>a[i];
    build(root,1,1<<n);
    while(q--)
    {
        int op,x,y;
        cin>>op;
        if(op==1)
        {
            cin>>x>>y;
            modify(root,1,1<<n,x,y);
        }
        else if(op==2)
        {
            cin>>x;
            rev(x);
        }
        else if(op==3)
        {
            cin>>x;
            swp(x);
        }
        else 
        {
            cin>>x>>y;
            cout<<query(root,1,1<<n,x,y)<<endl;
        }
    }
    return 0;
}

看standing发现了一个神奇的做法自己写一下
方法二:
把线段树看成一层一层的,可以发现反转和交换操作都是在同层进行,因此可以以层数记录lazy,方法一是用swap操作实现reverse操作,同样其实也可以用reverse操作实现swap:可以先把上一层每个区间进行reverse然后把该层的每个区间再reverse实际上实现的就是swap操作。
之前说过传统线段树不宜进行区间反转等操作,这个方法秒在不进行区间反转操作,只记录每层的区间是否需要进行反转,仅仅在查询和更改时候进行相应的坐标变化即可。

// [1 2 3 4        5 6 7 8]   level:3
// [1 2 3 4]      [5 6 7 8]   level:2
// [1 2] [3 4]  [5 6] [7 8]   level:1
// [1][2][3][4][5][6][7][8]   level:0
// 区间交换 level=2 只需要先反转level=3 然后再反转level=2即可
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<vector>
#include<set>
#include<map>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=(1<<18)+10;
int n,q;
int b[20];
ll a[N];
struct node
{
    int l,r,level;
    ll val;
}tree[4*N];
void pushup(int u)
{
    tree[u].val=tree[u<<1].val+tree[u<<1|1].val;
}
void build(int u,int l,int r,int level)
{
    tree[u]={l,r,level};
    if(l==r)
    {
        tree[u].val=a[l];
        return;
    }
    int mid=l+r>>1;
    build(u<<1,l,mid,level-1);
    build(u<<1|1,mid+1,r,level-1);
    pushup(u);
}
void modify(int u,int pos,int x)
{
    if(tree[u].l==tree[u].r)
    {
        tree[u].val=x;
        return;
    }
    if(b[tree[u].level]) pos=tree[u].r-(pos-tree[u].l);
    int mid=tree[u].l+tree[u].r>>1;
    if(pos<=mid) modify(u<<1,pos,x);
    else modify(u<<1|1,pos,x);
    pushup(u);
}
ll query(int u,int l,int r)
{
    if(tree[u].l==l&&r==tree[u].r) return tree[u].val;
    int lnow=l,rnow=r;
    if(b[tree[u].level])
    {
        lnow=tree[u].r-(r-tree[u].l);
        rnow=tree[u].r-(l-tree[u].l);
    }
    ll v=0;
    int mid=tree[u].l+tree[u].r>>1;
    if(rnow<=mid) v+=query(u<<1,lnow,rnow);
    else if(lnow>mid) v+=query(u<<1|1,lnow,rnow);
    else
    {
        v+=query(u<<1,lnow,mid);
        v+=query(u<<1|1,mid+1,rnow);
    }
    return v;
}
int main()
{
    cin>>n>>q;
    for(int i=1;i<=1<<n;i++) cin>>a[i];
    build(1,1,1<<n,n);
    while(q--)
    {
        int op,x,y;
        cin>>op;
        if(op==1)
        {
            cin>>x>>y;
            modify(1,x,y);
        }
        else if(op==2)
        {
            cin>>x;
            b[x]^=1;
        }
        else if(op==3)
        {
            cin>>x;
            b[x]^=1;
            b[x+1]^=1;
        }
        else 
        {
            cin>>x>>y;
            cout<<query(1,x,y)<<endl;
        }
    }
    return 0;
}

要加油哦~

本文地址:https://blog.csdn.net/Fighting_Peter/article/details/108166990

相关标签: Codeforces