Codeforces Round 525 (Div. 2)

发表于 | 分类于 ，

Codeforces Round #525 (Div. 2)

A. Ehab and another construction problem

1
2
3
4
5
6
7
8
9
10
11
12
#include <cstdio>

using namespace std;

int main()
{
    int x;
    scanf("%d",&x);
    if(x==1) printf("-1\n");
    else printf("%d %d\n",x,x);
    return 0;
}

B. Ehab and subtraction

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn=1e5+10;
int a[maxn];

int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    sort(a,a+n);
    long long tmp=0;
    int i=0,cnt=0;
    while(i<n&&cnt<k)
    {
        printf("%d\n",a[i]-tmp);
        tmp=a[i];
        cnt++;
        while(i<n&&a[i]==tmp) i++;
    }
    while(cnt<k)
    {
        printf("0\n");
        cnt++;
    }
    return 0;
}

C. Ehab and a 2-operation task

题意

给定一个长度为$n$的序列，有如下两种操作：

  • 将序列中的前$i$个数加上$x$

  • 将序列中的前$i$个数模$x$

要求使用不多于$n+1$次操作，使该序列变为严格递增。

解法

构造一个模$n+1$答案为1,2,3……n的序列即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int maxn=1e4+10;

int main()
{
    int n;
    long long a[maxn];
    int x[maxn];
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    long long sum=0;
    int cnt=0;
    for(int i=n-1;i>=0;i--)
    {
        int tmp=(a[i]+sum)%(n+1);
        x[i]=i-tmp;
        if(x[i]<0) x[i]+=n+1;
        if(x[i]) cnt++;
        sum+=x[i];
    }
    printf("%d\n",cnt+1);
    for(int i=n-1;i>=0;i--)
        if(x[i]) printf("%d %d %d\n",1,i+1,x[i]);
    printf("2 %d %d\n",n,n+1);
    return 0;
}

D. Ehab and another another xor problem

题意

交互题。

有两个数$a,b$，对于每次询问? c d，返回cmp(a^c,b^d)的值，要求在62次询问之内求出$a,b$的值，其中$0≤a,b<2^{30}$.

思路

考虑二进制分解，从最高位向下求解。

假设前k位已经确定，对于第k位的值，询问(1,0),(0,1),有如下情况：

  • 如果$a[k],b[k]$均为0，则ask(1,0)=1,ask(0,1)=-1

  • 如果$a[k],b[k]$均为1，则ask(1,0)=-1,ask(0,1)=1

  • 如果$a[k]≠b[k]$，则两次返回的值相同，且所得值为后k+1位的比较结果；

    对于这种情况，需要在开始时ask(0,0)比较$a,b$后k位的大小，并根据比较的返回值更新该值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int query(int a,int b)
{
    int res;
    printf("? %d %d\n",a,b);
    fflush(stdout);
    scanf("%d",&res);
    return res;
}

int main()
{
    int a=0,b=0,x,y;
    int big=query(0,0);
    for(int i=29;~i;--i)
    {
        x=query(a^(1<<i),b);
        y=query(a,b^(1<<i));
        if(x==y)
        {
            if(big==1) a^=(1<<i);
            else b^=(1<<i);
            big=x;
        }
        else if(x==-1) a^=(1<<i),b^=(1<<i);
    }
    printf("! %d %d\n",a,b);
    return 0;
}

E. Ehab and a component choosing problem

题意

给定一个有$n$个结点的树，每个节点的点权为$a_u$.选定k个不相交的联通块，使$\frac{\sum\limits_{u \in s} a_u}{k}$的值最大，如果有多个解，最大化k的值。

思路

如果不需要最大化k的值，显然取k=1，最大联通块的值$w$即为所求解。

对于k>1的情况，只要求出值等于$w$的联通块数量即可求解。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn=3e5+10;
typedef long long ll;

int val[maxn],head[maxn],cnt=0;
ll mx=-0x3f3f3f3f,tot=0;

struct Edge { int nex,to; }edge[maxn<<1];

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

ll dfs(int u,int pre)
{
    ll ans=val[u];
    for(int i=head[u];~i;i=edge[i].nex)
        if(edge[i].to!=pre) ans+=max(dfs(edge[i].to,u),0ll);
    mx=max(ans,mx);
    return ans;
}

ll dfs2(int u,int pre)
{
    ll ans=val[u];
    for(int i=head[u];~i;i=edge[i].nex)
        if(edge[i].to!=pre) ans+=max(dfs2(edge[i].to,u),0ll);
    if(mx==ans) {
        tot++;
        return 0;
    }
    return ans;
}

int main()
{
    int n,u,v;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&val[i]);
    memset(head,0xff,sizeof head);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    dfs(1,0);
    dfs2(1,0);
    printf("%lld %lld\n",mx*tot,tot);
    return 0;
}

F. Ehab and a weird weight formula

题意

给定一个$n$个节点的树，每个节点有点权$a_u$，该树满足条件：对于树上的每个点（除权值最小的点），必有相邻的点$v$，使$a_v<a_u$。要求构建一棵树，使树的权重最小。生成树的权重计算如下：

  • 对于每个点$u$,$w+=deg_u \cdot a_u$($deg_u$为生成树中节点$u$的度)
  • 对于树上每条边${u,v}$,$w+=\lceil log_2(dist(u,v)) \rceil \cdot min(a_u,a_v)$，$dist(u,v)$为生成树上点$u,v$间的距离

思路

对于所给的树，有如下性质：对于节点$u$的所有子节点$v$，有$a_v>a_u$.即随着深度的增加，节点点权增加。

那么对于节点$u$，向上求第$1-2^k$倍的祖先节点$v$，用ST表求$\lceil log_2(dist(u,v)) \rceil \cdot min(a_u,a_v)+a[v]$的最小值，即可求出生成树的总权重。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;
const int maxn=5e5+10;

int a[maxn],root=1;
int dp[25][maxn];
ll ans=0;

vector<int> edge[maxn];

void dfs(int u,int pre)
{
    dp[0][u]=pre;
    for(int i=1;i<20;i++)
        if(dp[i-1][u]!=-1) dp[i][u]=dp[i-1][dp[i-1][u]];
    int d;
    ll tmp=0xffffffff;
    for(d=0;d<20&&dp[d][u]!=-1;d++)
        tmp=min(tmp,1ll*(d+1)*a[dp[d][u]]+a[u]);
    tmp=min(tmp,1ll*(d+1)*a[root]+a[u]);
    if(~pre) ans+=tmp;
    for(int i=0;i<edge[u].size();i++)
    {
        int v=edge[u][i];
        if(v!=pre) dfs(v,u);
    }
}

int main()
{
    int n,u,v;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(a[i]<a[root]) root=i;
    }
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    memset(dp,0xff,sizeof dp);
    dfs(root,-1);
    printf("%lld\n",ans);
    return 0;
}