Dylan's Blog
0%

Posted on Edited on In

问题描述

Tehran 的一家每天 $24$ 小时营业的超市，需要一批出纳员来满足它的需要。超市经理雇佣你来帮他解决问题——超市在每天的不同时段需要不同数目的出纳员为顾客提供优质服务。他希望雇佣最少数目的出纳员。

经理已经提供给你一天的每一小时需要出纳员的最少数量——$R(0),R(1),⋯,R(23)$。表示从午夜到上午 $0:00$ 需要出纳员的最小数目，每一天，这些数据都是相同的。有 $N$ 人申请这项工作，每个申请者 $i$ 在每 $24$ 小时中，从一个特定的时刻开始连续工作恰好 $8$ 小时。定义 $t_i$ 为上面提到的开始时刻。也就是说，如果第 $i$ 个申请者被录取，他将从 $t_i$ 时刻开始连续工作 $8$ 小时。

输入

第一行为测试点的数目 $T$。

对于每组测试数据，第一行为 $24$ 个整数，表示 $R(0),R(1),R(2),⋯ ,R(23)$ 接下来一行一个正整数 $N$，表示申请者数目； 接下来 $N$ 行每行一个整数 $t_i$

输出

对于每个测试点，输出一行，包含一个整数，表示需要出纳员的最小数目。如果无解，输出 No Solution。

思路

一道差分约束很好的例题。本题思路引用了 这篇 Discuss

首先考虑约束关系。设：$r_i$ 为时间 $i$ 需要的人数 $t_i$ 为时间 $i$ 应聘的人数 $s_i$ 为时间 $i$ 以及之前录用的人数和

那么就存在约束关系： $s_i-s_{i-8}\geq r_i (8\leq i\leq 24)$ $s_i-s_{16+i}\geq r_i-s_{24} (1\leq i\leq 7)$ $s_i-s_{i-1}\geq 0 (1\leq i\leq 24)$ $s{i-1}-s_i\geq -t_i (1\leq i\leq 24)$

代码

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#define MAXN 1005
using namespace std;

int T, n, m, cnt, ans, tag[MAXN], need[MAXN], vis[MAXN], head[MAXN], dis[MAXN], num[MAXN];

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

queue<int> q;

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

bool spfa()
{
    memset(dis, -0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    memset(num, 0, sizeof(num));
    while(!q.empty()) q.pop();

    q.push(0); dis[0]=0;
    while(!q.empty())
    {
        int x=q.front(); q.pop();
        vis[x]=0;
        for(int i=head[x]; i; i=edge[i].next)
        {
            int to=edge[i].to;
            if(dis[to]<dis[x]+edge[i].dis)
            {
                dis[to]=dis[x]+edge[i].dis;
                num[to]=num[x]+1;
                if(num[to]>25) return false; 
                if(!vis[to]) vis[to]=1, q.push(to);
            }
        }
    }
    return true;
}

bool check(int mid)
{
    cnt=0;
    memset(head, 0, sizeof(head));

    for(int i=1; i<=7; i++) addedge(i+16, i, need[i]-mid);
    for(int i=8; i<=24; i++) addedge(i-8, i, need[i]);
    for(int i=1; i<=24; i++)
    {
        addedge(i-1, i, 0);
        addedge(i, i-1, -tag[i]);
    }
    addedge(0, 24, mid);
    return spfa();
}

int main()
{
    scanf("%d", &T);
    while(T--)
    {
        int l=0, r=1000, ans=-1;
        memset(tag, 0, sizeof(tag));

        for(int i=1; i<=24; i++) scanf("%d", &need[i]);
        scanf("%d", &n);
        for(int i=1; i<=n; i++)
        {
            int x;
            scanf("%d", &x);
            tag[x+1]++;
        }

        for(int i=0; i<=n; i++)
            if(check(i)) {ans=i; break;}
        if(ans==-1) printf("No Solution\n");
        else printf("%d\n", ans);
    }
}

Posted on Edited on In

问题描述：

$n$只奶牛构成了一个树形的公司，每个奶牛有一个能力值$p_i$，$1$号奶牛为树根。问对于每个奶牛来说，它的子树中有几个能力值比它大的。

输入：

第一行一个整数$n$，表示有$n$头奶牛 接下来$n$行为$1-n$号奶牛的能力值$p_i$ 接下来$n-1$行为$2-n$号奶牛的经理（树中的父亲）

输出：

共$n$行，每行输出奶牛$i$的下属中有几个能力值比$i$大

思路：

其实看完题后第一反应是树上启发式合并（不过应该可做，这种方法先坑着）。既然这是线段树合并的模版，那么还是先用这种方法做一遍吧。

首先离散化，然后对于每一个节点都建一颗权值线段树（里面都只有一个节点），接着dfs一遍，将每个节点儿子的线段树并在该节点上，然后跟新这个节点的答案就好了。

不过合并的操作复杂度是取决于线段树重合部分的大小，空间也要开很多倍。

代码：

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define MAXN 100005
using namespace std;

int n, m, cnt, tot, a[MAXN], b[MAXN], head[MAXN], root[MAXN], ans[MAXN];

struct Node {int size, ls, rs;} t[MAXN*20];
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 up(int root)
{
    t[root].size=t[t[root].ls].size+t[t[root].rs].size;
}

void insert(int &root, int l, int r, int x)
{
    root= ++tot;
    if(l==r) {t[root].size=1; return;}
    int mid=(l+r)>>1;
    if (x<=mid) insert(t[root].ls, l, mid, x);
    else insert(t[root].rs, mid+1, r, x);
    up(root);
}

int merge(int x, int y)
{
    if((!x) || (!y)) return x+y;
    t[x].ls=merge(t[x].ls, t[y].ls);
    t[x].rs=merge(t[x].rs, t[y].rs);
    up(x);
    return x;
}

int query(int root, int l, int r, int x, int y)
{
    if(r<x || l>y) return 0;
    if(l>=x && r<=y) return t[root].size;
    int mid=(l+r)>>1;
    return query(t[root].ls, l, mid, x, y)+query(t[root].rs, mid+1, r, x, y);
}

void dfs(int x)
{
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        dfs(to);
        root[x]=merge(root[x], root[to]);
    }
    ans[x]=query(root[x], 1, n, a[x]+1, tot);
}

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);
    m=unique(b+1, b+n+1)-b-1;
    for(int i=1; i<=n; i++) a[i]=lower_bound(b+1, b+m+1, a[i])-b;
    for(int i=2; i<=n; i++)
    {
        int x;
        scanf("%d", &x);
        addedge(x, i);
    }
    for(int i=1; i<=n; i++) insert(root[i], 1, n, a[i]);
    dfs(1);
    for(int i=1; i<=n; i++) printf("%d\n", ans[i]);
}

Posted on Edited on In

·9月4日 Codeforces Round #505 题目链接：http://codeforces.com/contest/1025

A - Doggo Recoloring

过水，就不说了。。

B - Weakened Common Divisor

思路： 首先我们不难想到将每一对数乘起来，然后求这些乘积的GCD，如果这个GCD为1则应该输出-1。但是这个GCD不一定是答案，但答案一定是这个GCD的约数。这时我就想到了找这个GCD最小的约数做为答案，但这样是会T的。于是我们考虑造成GCD不一定是答案的原因，然后我们可以将这个GCD与每一对中的一个数再求一遍GCD，这样的答案就是符合要求的了。

代码：

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 <bits/stdc++.h>
#define MAXN 150005
#define LL long long
using namespace std;

int n;
LL a[MAXN], b[MAXN], c[MAXN];

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

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        scanf("%lld%lld", &a[i], &b[i]);
        c[i]=a[i]*b[i];
    }
    LL ans=c[1];
    for(int i=2; i<=n; i++) ans=gcd(ans, c[i]);
    if(ans==1) printf("-1\n");
    else
    {
        for(int i=1; i<=n; i++)
        {
            if(gcd(ans, a[i])＞=1) ans=gcd(ans, ａ[i]);
            else ans=gcd(ans, ｂ[i]);
        }
        printf("%lld\n", ans);
    }
}

C - Plasticine zebra

思路： 一开始什么思路都没有，卡了很久。后面有一种直觉就是如果头和尾相等，那么如何翻转都是不会增加答案的（虽然一直不会证明）。

设$1-i$的字符串为’zebra’，这样的话只要头尾不相等，在位置$i$进行一次操作，这样’zebra’的长度一定会增加。由于开始提到的‘直觉’，只要操作后头和尾相等就break出循环。

后面看了题解后，就更加奇怪了，不明白自己这种乱搞的做法为什么是对的。

代码：

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
#include <bits/stdc++.h>
#define MAXN 100005
#define LL long long
using namespace std;

char a[MAXN];
int ans=1, n, f[MAXN];

void print()
{
    for(int i=0; i<n; i++) printf("%c", a[i]);
    printf("\n");
}

int main()
{
    scanf("%s", a);
    n=strlen(a);
    for(int i=0; i<n; i++)
    {
        if(a[0]==a[n-1]) break;
        if(a[i]==a[i+1])
        {
            reverse(a, a+i+1);
            reverse(a+i+1, a+n);
        }
    }
    f[0]=1;
    for(int i=1; i<n; i++)
    {
        if(a[i]==a[i-1]) f[i]=1;
        else f[i]=f[i-1]+1;
        ans=max(ans, f[i]);
    }
    printf("%d\n", ans);
}

D - Recovering BST

思路： 其实这和平衡树并没有半毛钱关系，只是根据BST的性质让你做区间DP。

对于一个递增序列，你可以任意选一个数作为BST的根，这个数将序列分为两部分，分别作为这个根的左子树和右子树。然后这两个部分又是递增序列，于是可以这样递归下去DP。

大致的思路是这样，但要注意一些细节。首先是要记忆化以保证复杂度，然后就是要记录自己序列是在左子树还是右子树，以便判断是否符合要求（也就是边两端的数GCD>1）。

代码：

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
#include <bits/stdc++.h>
#define MAXN 705
#define LL long long
using namespace std;

int n, f[MAXN][MAXN][2], a[MAXN];

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

bool dp(int l, int r, int k, int fa)
{
    if(f[l][r][k]!=-1) return f[l][r][k];
    if(l==r) return 1;
    if(k==0)
    {
        for(int i=l; i<r; i++)
            if(gcd(a[i], a[r])>1 && dp(l, i, 0, i) && dp(i, r-1, 1, i)) return f[l][r][k]=1;
    }
    else
    {
        for(int i=l+1; i<=r; i++)
            if(gcd(a[l], a[i])>1 && dp(l+1, i, 0, i) && dp(i, r, 1, i)) return f[l][r][k]=1;
    }
    return f[l][r][k]=0;
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    memset(f, -1, sizeof(f));
    for(int i=1; i<=n; i++)
        if(dp(1, i, 0, i) && dp(i, n, 1, i))
        {
            printf("Yes\n");
            return 0;
        }
    printf("No\n");
}

Posted on Edited on In

问题描述：

我们定义某天的最小波动值为$min \lbrace |$该天以前某一天的营业额$-$该天营业额$| \rbrace $

第一天的最小波动值为第一天的营业额

你的任务是编写一个程序帮助Tiger来计算这一个值：每一天的最小波动值之和。

输入：

第一行为正整数$n(n<=32767)$，表示该公司从成立一直到现在的天数，接下来的$n$行每行有一个整数$ai(|ai|<=1000000)$，表示第$i$天公司的营业额，可能存在负数

输出：

仅一个整数，即每一天的的最小波动值之和（结果小于$2^{31}$）

思路：

我们就是要实现 动态插点，找前驱和后继 这三种操作。首先平衡树肯定是能够做到的，于是就码了一发Splay。

然后其实权值线段树也可以做到。我们先将这些值离散化，每个值对应一个叶子节点。于是我们对于每一个节点维护区间内最左边和最右边的位置就好了。

代码：

Splay代码：

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>
#define MAXN 100005
#define INF 1e9
using namespace std;

int n, m, x, root, tot, ans;

struct Node
{
    int son[2], fa, val, size, tag;
    void init(int x, int y)
    {
        son[0]=son[1]=0;
        size=1; val=x; fa=y;
    }
} t[MAXN];

void up(int x)
{
    t[x].size=t[t[x].son[0]].size+t[t[x].son[1]].size+1;
}

void rotate(int x)
{
    int y=t[x].fa, z=t[y].fa;
    int k1=t[y].son[1]==x, k2=t[z].son[1]==y;
    t[z].son[k2]=x; t[x].fa=z;
    t[y].son[k1]=t[x].son[k1^1]; t[t[x].son[k1^1]].fa=y;
    t[x].son[k1^1]=y; t[y].fa=x;
    up(y); up(x);
}

void splay(int x, int k)
{
    while(t[x].fa!=k)
    {
        int y=t[x].fa, z=t[y].fa;
        if(z!=k)
        {
            if((t[z].son[1]==y)^(t[y].son[1]==x)) rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
    if(k==0) root=x;
}

int findnext(int k, int op)
{
    int x=root;
    x=t[x].son[op];
    while(t[x].son[op^1]) x=t[x].son[op^1];
    return x;
}

void insert(int k)
{
    int fa=0, x=root;
    while(x) fa=x, x=t[x].son[k>t[x].val];
    x=++tot;
    if(fa) t[fa].son[k>t[fa].val]=x;
    t[x].init(k, fa);
    splay(x, 0);
}

int main()
{
    insert(-INF);
    insert(INF);
    scanf("%d%d", &n, &x);
    insert(x);
    ans+=x;
    for(int i=2; i<=n; i++)
    {
        scanf("%d", &x);
        insert(x);
        int y=t[findnext(x, 0)].val;
        int z=t[findnext(x, 1)].val;
        ans+=min(x-y, z-x);
    }
    printf("%d\n", ans);
}

权值线段树代码：

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
62
63
64
65
66
67
68
69
70
71
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAXN 33000
#define mid (l+r>>1)
#define ls root<<1
#define rs root<<1|1
#define INF 1e9
using namespace std;

int n, ans, a[MAXN], b[MAXN], vis[MAXN], maxpos[MAXN*4], minpos[MAXN*4];

void up(int root)
{
    maxpos[root]=max(maxpos[ls], maxpos[rs]);
    minpos[root]=min(minpos[ls], minpos[rs]);
}

void update(int root, int l, int r, int x)
{
    if(l>x || r<x) return ;
    if(l==r) {maxpos[root]=minpos[root]=l; return;}
    update(ls, l, mid, x);
    update(rs, mid+1, r, x);
    up(root);
}

int queryl(int root, int l, int r, int x, int y)
{
    if(l>y || r<x) return 0;
    if(l>=x && r<=y) return maxpos[root];
    return max(queryl(ls, l, mid, x, y), queryl(rs, mid+1, r, x, y));
}

int queryr(int root, int l, int r, int x, int y)
{
    if(l>y || r<x) return n+1;
    if(l>=x && r<=y) return minpos[root];
    return min(queryr(ls, l, mid, x, y), queryr(rs, mid+1, r, x, y));
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d", &a[i]);
        b[i]=a[i];
    }
    b[0]=-INF; b[n+1]=INF;
    for(int i=0; i<MAXN*4; i++) minpos[i]=n+1;

    sort(b+1, b+n+1);
    unique(b+1, b+n+1);
    for(int i=1; i<=n; i++)
    {
        int pos=lower_bound(b+1, b+n+1, a[i])-b;
        if(vis[pos]) continue;
        vis[pos]=1;
        update(1, 1, n, pos);

        if(i==1) ans+=a[i];
        else
        {
            int x=queryl(1, 1, n, 1, pos-1);
            int y=queryr(1, 1, n, pos+1, n);
            ans+=min(a[i]-b[x], b[y]-a[i]);
        }
    }
    printf("%d\n", ans);
}

Posted on Edited on In

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

C - Candles

思路： 比较水的一题，发现点燃的$k$根蜡烛一定是相邻的。于是我们之间枚举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
#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]$的个数，不难想到使用树状数组进行维护。

代码：

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
#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]$

代码：

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
62
63
64
#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

思路：

代码：

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
#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);
}