7月26日 Educational Codeforces Round 47
题目链接:http://codeforces.com/contest/1009

A – Game Shopping & B – Minimum Ternary String

简单,不讲。。。

C – Annoying Present

思路:
其实也比较水。。。首先参数$x$对答案的贡献是不会变的,根据一些小学数学知识可以知道:当$d$为正时,选取的位置越靠边贡献越大;当$d$为负时,选取的位置越靠中间贡献越大。因此分类讨论一下就好了。

代码:

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

LL ans, n, m, x, d;;

int main()
{
    scanf("%lld%lld", &n, &m);
    for(int i=1; i<=m; i++)
    {
        scanf("%lld%lld", &x, &d);
        ans+=n*x;
        if(d>0) ans+=(n-1)*n/2*d;
        else
        {
            if(n&1) ans+=(n/2)*(n/2+1)*d;
            else ans+=n*n/4*d;
        }
    }
    printf("%lf\n", (double)ans/n);
}

D – Relatively Prime Graph

思路:
虽然是构造一张图,其实和图论没有什么关系。。。

看懂题意以后可以发现你就是要在$1-n$内找出$m$对互素的数,于是可以暴力枚举,知道枚举出$m$对数。因为这是实在是太暴力了,比赛时还在怀疑算法不够优秀。其实互质数对的分布是玄学的,所以一般是不好卡你暴力的,再加上CF的神机,放心的打就好了。(实测46ms)
代码:

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

int n, m, cnt;
pair<int, int> ans[100005];

int gcd(int x, int y) {return y==0 ? x : gcd(y, x%y);}

void solve()
{
    for(int i=1; i<=n; i++)
    {
        for(int j=i+1; j<=n; j++)
            if(gcd(i, j)==1)
            {
                ans[++cnt].first=i; ans[cnt].second=j;
                if(cnt==m) return;
            }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    if(m<n-1)
    {
        printf("Impossible\n");
        return 0;
    }
    solve();
    if(cnt<m) printf("Impossible\n");
    else
    {
        printf("Possible\n");
        for(int i=1; i<=m; i++) printf("%d %d\n", ans[i].first, ans[i].second);
    }
}

E – Intercity Travelling

思路:
一看题目,哇,和JXOI的风格好像的QVQ,都是小清新的期望计数题。虽然是期望,不过同样是套了期望的说法的一些计数类问题。

首先想到$n^2$的暴力DP,先处理前缀和。设$g[i]$为有多少种方法到达$i$点,$f$就是答案所求的东西,那么DP的方法就如下面代码所示:

g[0]=1;
for(int i=1; i<=n; i++)
{
    scanf("%lld", &a[i]);
    a[i]=(a[i]+a[i-1])%p;
}
for(int i=1; i<=n; i++)
    for(int j=0; j<i; j++)
    {
        f[i]=(f[i]+f[j]+a[i-j]*g[j])%p;
        g[i]=(g[i]+g[j])%p;
    }

然后我们打表发现$g[i]$就是$2^{i-1}$,又发现$f[i]$只由$a$中的元素组成,且组成方法与$a$中元素的值无关。于是再次打表,打出$f[i]$由$a$中的元素怎么构成,于是发现$$h[i]=\sum_{j=0}^{j-1}h[j]+2^{i-2}$$其中$h[n+1-i]$为构成$f[n]$(即答案)中$a[i]$的系数。即:$$f[n]=\sum_{i=1}^{n}a[i]*h[n+1-i]$$
代码:

#include <bits/stdc++.h>
#define LL long long
#define MAXN 1000006
#define p 998244353
using namespace std;

LL n, ans, h[MAXN], g[MAXN], a[MAXN], sum[MAXN];

int main()
{
    scanf("%lld", &n);
    g[1]=g[0]=1;
    for(int i=2; i<=n; i++) g[i]=(g[i-1]*2)%p;
    for(int i=1; i<=n; i++) scanf("%lld", &a[i]), a[i]=(a[i]+a[i-1])%p;

    for(int i=1; i<=n; i++)
    {
        h[i]=(sum[i-1]+g[i-1])%p;
        sum[i]=(sum[i-1]+h[i])%p;
    }
    for(int i=1; i<=n; i++) ans=(a[i]*h[n-i+1]+ans)%p;
    printf("%lld\n", ans%p);
}

F – Dominant Indices

思路:
一直没有学树上启发式合并。膜题解发现要用这种操作,于是学了一下。个人理解就是遍历每个节点,然后从每个节点再开始另一个搜索,处理出该节点子树的信息,这样显然最坏是$O(N^2)$的。然而我们可以从先遍历节点,回溯时保留父亲节点重儿子的信息,这样从父亲节点开始的另一个搜索就可以不用搜重儿子。于是我们保证了时间复杂度在$O(logn)$。

这道题也是类似,要求子树重节点最多的那一层,于是就按照启发式合并去做就好了。
代码:

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

int n, cnt, maxnum, maxans, siz[MAXN], head[MAXN], dep[MAXN], ans[MAXN], num[MAXN], tag[MAXN];

struct Edge {int next, to;}edge[MAXN*2];

void addedge(int from, int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}

void dfs1(int x, int fa)
{
    siz[x]=1;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        dep[to]=dep[x]+1;
        dfs1(to, x);
        siz[x]+=siz[to];
    }
}

void update(int x)
{
    if(num[dep[x]]>maxnum) maxnum=num[dep[x]], maxans=dep[x];
    if(num[dep[x]]==maxnum && dep[x]<maxans) maxans=dep[x];
}

void add(int x, int fa, int op)
{
    num[dep[x]]+=op;
    update(x);
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        add(to, x, op);
    }
}

void dfs2(int x, int fa, int keep)
{
    int maxson=-1, maxsize=0;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        if(siz[to]>maxsize) maxson=to, maxsize=siz[to];
    }

    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa || to==maxson) continue;
        dfs2(to, x, 0);
    }
    if(maxson!=-1) dfs2(maxson, x, 1);

    num[dep[x]]++;
    update(x);
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa || to==maxson) continue;
        add(to, x, 1);
    }
    ans[x]=maxans;

    if(keep==0)
    {
        num[dep[x]]--;
        update(x);
        for(int i=head[x]; i; i=edge[i].next)
        {
            int to=edge[i].to;
            if(to==fa) continue;
            add(to, x, -1);
        }
        maxnum=maxans=0;
    }
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);  
        addedge(x, y);
        addedge(y, x);
    }
    dfs1(1, 0);
    dfs2(1, 0, 1);
    for(int i=1; i<=n; i++) printf("%d\n", ans[i]-dep[i]);
}

发表评论

邮箱地址不会被公开。 必填项已用*标注