8月30日 AtCoder Regular Contest 101
题目链接:https://arc101.contest.atcoder.jp/

C – Candles

思路:
比较水的一题,发现点燃的$k$根蜡烛一定是相邻的。于是我们之间枚举k根蜡烛的位置就好了。

代码:

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <map>
#define MAXN 100005
#define LL long long
#define INF 1e9
using namespace std;

int n, k, x[MAXN], ans=INF;

int main()
{
    scanf("%d%d", &n, &k);
    for(int i=1; i<=n; i++) scanf("%d", &x[i]);
    for(int i=k; i<=n; i++)
    {
        if(x[i]<0) ans=min(ans, -x[i-k+1]);
        if(x[i]>=0 && x[i-k+1]<=0) ans=min(ans, x[i]-x[i-k+1]+min(x[i], -x[i-k+1]));
        if(x[i-k+1]>0) ans=min(ans, x[i]);
    }
    printf("%d\n", ans);
}

D – Median of Medians

思路:
好题。。

有一个很神奇的地方就是这题所求的Median of Medians是满足二分性的。首先我们有$n*(n+1)/2$个连续子串,我们设二分的值为$x$,如果至少有$n*(n+1)/4$个 中位数大于等于$x$的连续子串,那么答案就一定是大于等于$x$的,否则就是小于$x$,于是我们就可以根据这个进行二分。

接下来我们的问题就是如何求 中位数大于等于$x$的连续子串 的个数。我们可以将大于等于$x$的数视为1,将小于$x$的数视为-1,然后维护前缀和,记为$c[i]$。那么对于子串$[l, r]$,如果$c[l]<=c[r]$那么这个子串的中位数就是大于$x$的。对于符合要求$[l, r]$的个数,不难想到使用树状数组进行维护。

代码:

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <map>
#define MAXN 100005
#define LL long long
using namespace std;

int n, l=1e9, r, ans, a[MAXN], b[MAXN], c[MAXN];
LL t[MAXN*2];

void add(int x, int y)
{
    for(; x<=2e5; x+=(x&-x)) t[x]+=y;
}

LL ask(int x)
{
    LL sum=0;
    for(; x; x-=(x&-x)) sum+=t[x];
    return sum;
}

bool check(int mid)
{
    LL num=0;
    memset(t, 0, sizeof(t));
    for(int i=1; i<=n; i++)
    {
        if(a[i]<mid) c[i]=-1;
        else c[i]=1;
        c[i]=c[i]+c[i-1];
    }
    for(int i=0; i<=n; i++)
    {
        num+=ask(c[i]+1e5);
        add(c[i]+1e5, 1);
    }
    return num>=1LL*(n+1)*n/4;
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d", &a[i]);
        b[i]=a[i];
    }
    sort(b+1, b+n+1);
    l=1; r=n;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(check(b[mid])) ans=mid, l=mid+1;
        else r=mid-1;
    }
    printf("%d\n", b[ans]);
}

E – Ribbons on Tree

思路:
也是一道很好的题目,是一个计数类的树形DP。

看完题目后就觉得像是一个计数类的DP,于是按照常规的计数类DP思考如何转化和如何设计状态。首先是可以用容斥的思想,$ans=$所有情况 $-$ 至少一条边未覆盖情况 $+$ 至少两条边未覆盖情况$…..$

那么问题就来了,如何计算 至少$k$条边未覆盖的情况数。如果我们知道$k$条未覆盖的边的具体位置,很容易想到这棵树被分为了$k+1$个互不连通的区域(这里是区域,不一定要联通)。对于一个含有$x$个节点的区域,这个区域的可能情况数量$g(x)$为:

那么如果我们知道了$k$条未覆盖的边的具体位置,这种情况的方案数就是$g(x_1)*g(x_2)….*g(x_{k+1})$,$x_i$就是第$i$个区域的节点数。

但实际上我们并不知道$k$条未覆盖边的位置,并且枚举这$k$条边的复杂度也是不满足要求的,这时我们就可以换一个思路,利用树形DP(虽然思路变了,但是上面的结论都是要用到的)。我们设$f[i][j][k]$为在$i$的子树中,$i$所在联通块大小为$j$,未覆盖边数的奇偶性为$k$($k$为0或1),$j$可能为0,此时表示$i$所在联通块为任意大小。方程的转移就看代码好了,实在是讲不清楚。最后答案就是$f[1][0][1]-f[1][0][0]$

代码:

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define MAXN 5005
#define p 1000000007
#define LL long long
using namespace std;

int n, cnt, head[MAXN], size[MAXN];
LL f[MAXN][MAXN][2];

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 dfs(int x, int fa)
{
    size[x]=1; f[x][1][0]=1;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        dfs(to, x);
        for(int j=size[x]+size[to]; j>=0; j--)
        {
            LL tx=f[x][j][0], ty=f[x][j][1];
            f[x][j][0]=(f[to][0][0]*tx+f[to][0][1]*ty)%p;
            f[x][j][1]=(f[to][0][0]*ty+f[to][0][1]*tx)%p;
            for(int k=max(1, j-size[x]); k<=min(j, size[to]); k++)
            {
                f[x][j][0]=(f[x][j][0]+f[to][k][0]*f[x][j-k][0]%p+f[to][k][1]*f[x][j-k][1]%p)%p;
                f[x][j][1]=(f[x][j][1]+f[to][k][0]*f[x][j-k][1]%p+f[to][k][1]*f[x][j-k][0]%p)%p;
            }
        }
        size[x]+=size[to];
    }
    LL temp=1;
    for(int i=2; i<=size[x]; i+=2)
    {
        temp=temp*(i-1)%p;
        f[x][0][0]=(f[x][0][0]+f[x][i][1]*temp)%p;
        f[x][0][1]=(f[x][0][1]+f[x][i][0]*temp)%p;
    }
}

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);
    }
    dfs(1, 0);
    printf("%lld\n", (f[1][0][1]-f[1][0][0]+p)%p);
}

F – Robots and Exits

思路:

代码:

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define MAXN 100005
#define p 1000000007
#define LL long long
using namespace std;

int n, m, cnt, x[MAXN], y[MAXN], a[MAXN], b[MAXN];
LL t[MAXN];

struct Node {int a, b;} c[MAXN];

bool CMP(Node x, Node y)
{
    if(x.a!=y.a) return x.a<y.a;
    return x.b>y.b;
}

void add(int x, int y)
{
    for(; x<=cnt; x+=(x&-x)) t[x]=(t[x]+y)%p;
}

LL ask(int x)
{
    LL sum=0;
    for(; x; x-=(x&-x)) sum=(sum+t[x])%p;
    return sum;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) scanf("%d", &x[i]);
    for(int i=1; i<=m; i++) scanf("%d", &y[i]);
    for(int i=1, j=1; i<m && j<=n; i++)
    {
        while(x[j]<y[i]) j++;
        while(x[j]>=y[i] && x[j]<=y[i+1])
        {
            a[++cnt]=x[j]-y[i];
            b[cnt]=y[i+1]-x[j];
            c[cnt].a=a[cnt]; c[cnt].b=b[cnt];
            j++;
        }
    }
    sort(a+1, a+cnt+1); sort(b+1, b+cnt+1);
    for(int i=1; i<=cnt; i++)
    {
        c[i].a=lower_bound(a+1, a+cnt+1, c[i].a)-a;
        c[i].b=lower_bound(b+1, b+cnt+1, c[i].b)-b;
    }
    sort(c+1, c+cnt+1, CMP);
    for(int i=1; i<=cnt; i++)
        if(c[i].a!=c[i-1].a || c[i].b!=c[i-1].b) add(c[i].b, (ask(c[i].b-1)+1)%p);
    printf("%d\n", (ask(cnt)+1)%p);
}

发表评论

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