Codeforces Round #595 (Div. 3) 题解

题解 比赛-Codeforces
题目链接 编辑文章

A.Yet Another Dividing into Teams

B.Books Exchange

题意

题解

把关系连边后,可以发现一定是形成若干个环,那么 $O(n)$ 搜索一遍即可。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const int N=200005;
bool vis[N];
int t,n,a[N],ans[N];

int dfs(int x,int res)
{
    vis[x]=1;
    if (vis[a[x]]) return ans[x]=res;
    return ans[x]=dfs(a[x],res+1);
}

signed main()
{
    t=read();
    while (t--)
    {
        memset(vis,0,sizeof(vis));
        n=read();
        for (int i=1;i<=n;i++) a[i]=read();
        for (int i=1;i<=n;i++)
        {
            if (vis[i]) continue;
            dfs(i,1);
        }
        for (int i=1;i<=n;i++) printf("%d ",ans[i]);
        puts("");
    }
    return 0;
}

C.Good Numbers

题意

题解

正向的凑不太现实,考虑反向来减。可以发现 $3^{38} > 10^{18}$ ,所以可以先得到 $sum=\sum_{i=0}^{38} 3^i$ 。

与 $2$ 的性质相似,$3^x > \sum_{i=0}^{x-1} 3^i$ 。所以从大到小枚举 $i$ ,如果能减就减去 $3^i$ 。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar(); ll f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

ll t,n,sum,f[40];

signed main()
{
    f[0]=sum=1;
    for (int i=1;i<=38;i++) f[i]=f[i-1]*3,sum+=f[i];
    t=read();
    while (t--)
    {
        n=read();
        ll d=sum-n;
        for (int i=38;~i;i--) if (f[i]<=d) d-=f[i];
        printf("%lld\n",d+n);
    }
    return 0;
}

D.Too Many Segments

题意

题解

经典线段覆盖的思路,只可能是线段之间完全覆盖的情况使答案减小。所以按右端点从小到大排序(或者左端点从大到小),枚举所有线段,能放就放,否则加入答案。用线段树维护。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const int N=200005;
struct Tree {
    int left,right,mx,d;
} tree[N<<2];
struct node {
    int l,r,id;
} s[N];
int n,k;
vector <int> v;

inline void pushup(int x) { tree[x].mx=max(tree[x<<1].mx,tree[x<<1|1].mx); }

inline void pushdown(int x)
{
    tree[x<<1].mx+=tree[x].d;
    tree[x<<1|1].mx+=tree[x].d;
    tree[x<<1].d+=tree[x].d;
    tree[x<<1|1].d+=tree[x].d;
    tree[x].d=0;
}

void build(int x,int l,int r)
{
    tree[x].left=l;
    tree[x].right=r;
    if (r-l>1)
    {
        int mid=(l+r)>>1;
        build(x<<1,l,mid);
        build(x<<1|1,mid,r);
    }
}

void update(int x,int l,int r,int d)
{
    if (l<=tree[x].left && r>=tree[x].right) tree[x].mx+=d,tree[x].d+=d;
    else
    {
        if (tree[x].d) pushdown(x);
        int mid=(tree[x].left+tree[x].right)>>1;
        if (l<mid) update(x<<1,l,r,d);
        if (r>mid) update(x<<1|1,l,r,d);
        pushup(x);
    }
}

int query(int x,int l,int r)
{
    if (l<=tree[x].left && r>=tree[x].right) return tree[x].mx;
    else
    {
        if (tree[x].d) pushdown(x);
        int mid=(tree[x].left+tree[x].right)>>1,ans=0;
        if (l<mid) ans=max(ans,query(x<<1,l,r));
        if (r>mid) ans=max(ans,query(x<<1|1,l,r));
        return ans;
    }
}

signed main()
{
    n=read(); k=read();
    for (int i=1;i<=n;i++) s[i].l=read(),s[i].r=read(),s[i].id=i;
    sort(s+1,s+n+1,[](node x,node y){ return x.r<y.r; });
    build(1,1,s[n].r+1);
    for (int i=1;i<=n;i++)
    {
        int res=query(1,s[i].l,s[i].r+1);
        if (res>=k) v.emplace_back(s[i].id); //不能放
        else update(1,s[i].l,s[i].r+1,1);
    }
    printf("%lu\n",v.size());
    for (auto i:v) printf("%d ",i);
    return 0;
}

E.By Elevator or Stairs?

题意

有个 $n(\le 2\times 10^5)$ 层的楼房。从第 $i$ 层 $\rightarrow$ 第 $(i+1)$ 层,走楼梯要 $a_i$ 分钟,电梯要 $b_i$ 分钟。电梯可以从任意楼层一次性到达其它任何楼层,但每次等电梯需要花费 $c$ 分钟。可以多次搭乘电梯,问到第 $n$ 层最少需要多久。

题解

DP水题。用 $f[i][0/1]$ 表示当前到了 $i$ 层,上次是走楼梯/坐电梯的最小时间。方程式显然为:

$$\begin{cases} f[i][0]=\min(f[i-1][0],f[i-1][1])+a_{i-1} \\ f[i][1]=\min(f[i-1][0]+c,f[i-1][1])+b_{i-1} \end{cases}$$

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const int N=200005;
int n,m,a[N],b[N],f[N][2];

signed main()
{
    n=read(); m=read();
    for (int i=1;i<n;i++) a[i]=read();
    for (int i=1;i<n;i++) b[i]=read();
    memset(f,0x3f,sizeof(f));
    f[1][0]=0;
    printf("0 ");
    for (int i=2;i<=n;i++)
    {
        f[i][0]=min(f[i-1][0],f[i-1][1])+a[i-1];
        f[i][1]=min(f[i-1][0]+m,f[i-1][1])+b[i-1];
        printf("%d ",min(f[i][0],f[i][1]));
    }
    return 0;
}

F.Maximum Weight Subset

题意

题解

先将题目中给出的 $k+1$ ,这样 $k$ 表示两点之间的最小距离。

树形DP。用 $f[x][dep]$ 表示在以 $x$ 为根的子树中,深度至少为 $dep$ ($x$ 的深度为 $0$)的点才能取,这时的最大权值。初值为 $f[x][0]=a[x]$ 。

对于每个 $x$ ,枚举 $dep$ 转移,设 $y$ 为 $x$ 的子节点。如果 $dep=0$ ,意味着选了 $x$ ,这时可以在以 $y$ 为根的子树中深度至少为 $k-1$ 的点中选择,所以

$$f[x][0]=\max (\sum f[y][k-1])\tag{1}$$

当 $dep\neq 0$ 时,说明各个 $y$ 为根的子树中可选的深度不同:如果选了一个子树在深度 $dep-1$ 处选,那么其它子树,假设根节点为 $z$ ,就受两个距离限制,所以取最大值为 $\max(dep-1,k-dep-1)$ 。方程式为

$$f[x][dep]=\max (f[y][dep-1]+\sum f[z][\max(dep-1,k-dep-1)])\tag{2}$$

最后还应该让答案随深度保持单调不增,因为不一定每次都选距离严格 $=k$ 的节点。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const int N=205;
struct Edge {
    int next,to;
} edge[N<<1];
int cnt,head[N],n,m,a,b,s[N],f[N][N];

inline void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void dfs(int x,int fa)
{
    f[x][0]=s[x];
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (y==fa) continue;
        dfs(y,x);
    }
    for (int i=head[x];i;i=edge[i].next) //dep=0
    {
        int y=edge[i].to;
        if (y==fa) continue;
        f[x][0]+=f[y][max(0,m-1)];
    }
    for (int j=1;j<n;j++) //枚举 dep
    {
        for (int i=head[x];i;i=edge[i].next)
        {
            int y=edge[i].to;
            if (y==fa) continue;
            int cur=f[y][j-1];
            for (int k=head[x];k;k=edge[k].next)
            {
                int z=edge[k].to;
                if (z==fa || z==y) continue;
                cur+=f[z][max(j-1,m-j-1)];
            }
            f[x][j]=max(f[x][j],cur);
        }
    }
    for (int i=n-2;~i;i--) f[x][i]=max(f[x][i],f[x][i+1]);
}

signed main()
{
    n=read(); m=read()+1;
    for (int i=1;i<=n;i++) s[i]=read();
    for (int i=1;i<n;i++)
    {
        a=read(); b=read();
        add(a,b);
        add(b,a);
    }
    dfs(1,0);
    return !printf("%d",f[1][0]);
}

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空