Dylan's Blog
0%

Posted on Edited on In

问题描述：

给一棵树，每条边有权。求一条简单路径，权值和等于$K$，且边的数量最小。

输入：

第一行：两个整数$n,k$ 第二至 $n$行：每行三个整数，表示一条无向边的两端和权值 (注意点的编号从$0$开始)

输出：

一个整数，表示最小边数量 如果不存在这样的路径，输出$-1$

思路：

对于静态统计树上路径的问题，点分治往往是一种可行的做法。这道题也就可以用点分治来做。

分治时对于根节点$p$，可以开一个数组$val$记录从$p$开始每个长度的链最少需要多少条边。需要注意的是，我们应该对每个子树先dfs一遍更新答案，再dfs一遍更新$val$数组。这是因为如果同时操作，计算时就会乱掉（可能两条链属于同一棵子树，这样两条链就有重复的边）。dfs时记录当前链的深度$dep$和边数$num$，就用$val[k-dep]+num$来更新答案。

代码：

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <algorithm>
#define MAXN 200005
#define MAXK 1000006
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;

int n, k, cnt, tot, root, ans, head[MAXN], size[MAXN], val[MAXK], f[MAXN];
bool vis[MAXN];

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

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

void getroot(int x, int fa)
{
    size[x]=1; f[x]=0; 
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa || vis[to]) continue;
        getroot(to, x);
        size[x]+=size[to];
        f[x]=max(f[x], size[to]);
    }
    f[x]=max(f[x], tot-size[x]);
    if(f[x]<f[root]) root=x;
}

void getdis(int x, int fa, int dep, int num, int op)
{
    if(op==0) val[dep]=min(val[dep], num);
    else val[dep]=INF;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa || vis[to]) continue;
        if(dep+edge[i].dis<=k) getdis(to, x, dep+edge[i].dis, num+1, op); 
    }
}

void update(int x, int fa, int dep, int num)
{
    ans=min(ans, val[k-dep]+num);
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa || vis[to]) continue;
        if(dep+edge[i].dis<=k) update(to, x, dep+edge[i].dis, num+1); 
    }
}

void divide(int x)
{
    vis[x]=1; val[0]=0;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(vis[to]) continue;
        if(edge[i].dis<=k) update(to, x, edge[i].dis, 1);
        if(edge[i].dis<=k) getdis(to, x, edge[i].dis, 1, 0);
    }
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(vis[to]) continue;
        if(edge[i].dis<=k) getdis(to, x, edge[i].dis, 1, 1);
    }
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(vis[to]) continue;
        tot=size[to]; root=0;
        getroot(to, x);
        divide(root);
    }
}

int main()
{
    f[0]=INF; ans=INF;
    memset(val, 0x3f, sizeof(val));

    scanf("%d%d", &n, &k);
    for(int i=1; i<n; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        x++; y++;
        addedge(x, y, z);
        addedge(y, x, z);
    }
    tot=n; root=0;
    getroot(1, 0);
    divide(root);
    if(ans==INF) printf("-1\n");
    else printf("%d\n", ans);
 }

Posted on Edited on In

8月18日 2018百度之星复赛 题目链接：http://bestcoder.hdu.edu.cn/contests/contest_show.php?cid=827

1001 - 没有兄弟的舞会

思路： 一个很简单的贪心吧。。。对于每一个节点选出它最大和最小的儿子（注意还可以不选），然后在没有选的里面贪心找一个最大和最小值加入答案。

代码：

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 <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#define MAXN 100005
#define LL long long
#define LB long double
#define INF 1e18
using namespace std;

int T, n, cnt, head[MAXN], maxson[MAXN], minson[MAXN], maxtag[MAXN], mintag[MAXN];
LL maxans, minans, w[MAXN], maxval[MAXN], minval[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 dfs(int x, int fa)
{
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        dfs(to, x);
        if(w[to]>maxval[x]) maxson[x]=to, maxval[x]=w[to];
        if(w[to]<minval[x]) minson[x]=to, minval[x]=w[to];
    }
    maxans+=maxval[x];
    minans+=minval[x];
    maxtag[maxson[x]]=1;
    mintag[minson[x]]=1;
}

int main()
{
    scanf("%d", &T);
    while(T--)
    {
        cnt=maxans=minans=0;
        for(int i=0; i<MAXN-1; i++) head[i]=maxson[i]=minson[i]=maxval[i]=minval[i]=mintag[i]=maxtag[i]=0;
        LL mintemp=0, maxtemp=0;
        scanf("%d", &n);
        for(int i=2; i<=n; i++)
        {
            int fa;
            scanf("%d", &fa);
            addedge(fa, i);
            addedge(i, fa);
        }
        for(int i=1; i<=n; i++) scanf("%lld", &w[i]);
        dfs(1, 0);
        if(w[1]>0) maxtag[1]=1, maxans+=w[1];
        if(w[1]<0) mintag[1]=1, minans+=w[1];
        for(int i=1; i<=n; i++)
        {
            if(!mintag[i]) mintemp=min(mintemp, w[i]);
        }
        for(int i=n; i>=1; i--)
        {
            if(!maxtag[i]) maxtemp=max(maxtemp, w[i]);
        }
        printf("%lld %lld\n", maxans+maxtemp, minans+mintemp);
    }
}

1002 - 序列期望

思路： 一道蛮好的期望题。我们可以先枚举最大值$h$，然后计算最大值为$h$时对答案的贡献。最大值恰好为$h$是的贡献不方便计算，我们可以先计算最大值小于等于$h$和最大值小于$h$的期望，利用一个容斥相减就好了。

代码：

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#define MAXN 100005
#define LL long long
#define LB long double
#define INF 1e18
#define p 1000000007
using namespace std;

int T, n, l[MAXN], r[MAXN], tag, lmax, rmax;

LL x[MAXN], y[MAXN];

LL ksm(LL x, LL y)
{
    LL sum=1;
    while(y)
    {
        if(y&1) sum=(sum*x)%p;
        y>>=1; x=(x*x)%p;
    }
    return sum;
}

LL cal(LL l, LL r) {return (l+r)*(r-l+1)/2%p;}

int main()
{
    scanf("%d", &T);
    while(T--)
    {
        lmax=rmax=0;
        LL up=0, down=1;
        scanf("%d", &n);
        for(int i=1; i<=n; i++)
        {
            scanf("%d%d", &l[i], &r[i]);
            lmax=max(lmax, l[i]);
            rmax=max(rmax, r[i]);
        }
        for(int i=lmax; i<=rmax; i++)
        {
            tag=0;
            LL sum1=1, sum2=1;
            for(int j=1; j<=n; j++)
            {
                if(r[j]>=i) x[j]=1;
                else x[j]=i-r[j]+1;
                y[j]=i-l[j]+1;
            }
            for(int j=1; j<=n; j++) sum1=sum1*cal(x[j], y[j])%p;
            for(int j=1; j<=n; j++)
            {
                if(x[j]==1) sum2=(sum2*cal(x[j]+1, y[j]))%p;
                else sum2=(sum2*cal(x[j], y[j]))%p;
            }
            up=(up+sum1-sum2+p)%p;
        }
        for(int i=1; i<=n; i++) down=(down*(r[i]-l[i]+1))%p;
        printf("%lld\n", up*ksm(down, p-2)%p);
    }
}

1003 - 带劲的and和

思路： 首先观察式子，就可以发现我们可以对每一个联通块分开维护。对于每一个联通块里面的权值我们不难想到$v_i&v_j$可以按位来维护，对于每一位分别记录有多少个数字在这一位上出现过。然后$max(v_i, v_j)$可以比较巧妙的先将权值排序进行维护，从小到大依次按顺序计算贡献。大概的思路就是这样，详细的看代码吧（懒）

代码：

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#define MAXN 100005
#define LL long long
#define LB long double
#define INF 1e18
#define p 1000000007
using namespace std;

int T, n, m, cnt, top, sta[MAXN], head[MAXN], vis[MAXN];

LL ans, w[MAXN], num[50];


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

bool CMP(int x, int y) {return w[x]<w[y];}

void dfs(int x)
{
    vis[x]=1; sta[++top]=x;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(vis[to]) continue;
        dfs(to);
    }
}

int main()
{
    scanf("%d", &T);
    while(T--)
    {
        ans=cnt=0;
        for(int i=0; i<MAXN-1; i++) head[i]=vis[i]=0;
        scanf("%d%d", &n, &m);
        for(int i=1; i<=n; i++) scanf("%lld", &w[i]);
        for(int i=1; i<=m; i++)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            addedge(x, y);
            addedge(y, x);
        }
        for(int i=1; i<=n; i++)
        {
            if(vis[i]) continue;
            top=0;
            memset(num, 0, sizeof(num));
            dfs(i);
            sort(sta+1, sta+top+1, CMP);
            for(int j=1; j<=top; j++)
            {
                int temp=sta[j];
                for(int k=31; k>=0; k--)
                    if((w[temp]>>k)&1) ans=(ans+w[temp]*num[k]%p*(1LL<<k))%p, num[k]++;
            }
        }
        printf("%lld\n", ans);
    }
}

Posted on Edited on In

问题描述：

传统的Nim游戏是这样的：有一些火柴堆，每堆都有若干根火柴（不同堆的火柴数量可以不同）。两个游戏者轮流操作，每次可以选一个火柴堆拿走若干根火柴。可以只拿一根，也可以拿走整堆火柴，但不能同时从超过一堆火柴中拿。拿走最后一根火柴的游戏者胜利。

本题的游戏稍微有些不同：在第一个回合中，第一个游戏者可以直接拿走若干个整堆的火柴。可以一堆都不拿，但不可以全部拿走。第二回合也一样，第二个游戏者也有这样一次机会。从第三个回合（又轮到第一个游戏者）开始，规则和Nim游戏一样。

如果你先拿，怎样才能保证获胜？如果可以获胜的话，还要让第一回合拿的火柴总数尽量小。

输入：

第一行为整数$k$。即火柴堆数。第二行包含$k$个不超过$10^9$的正整数，即各堆的火柴个数 （$k<=100$）

输出：

输出第一回合拿的火柴数目的最小值。如果不能保证取胜，输出-1

思路：

如果已经弄清了NIM游戏的话，那么这道题应该也不难想到。

根据结论，如果要先手必胜，显然应该满足第三回合时所有堆的火柴数异或和大于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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAXN 10005
#define LL long long
using namespace std;

int n;
LL ans, sum, a[MAXN], base[MAXN];

bool CMP(LL x, LL y) {return x>y;}

bool insert(LL x)
{
    for(int i=31; i>=0; i--)
    {
        if(!(x>>i)) continue;
        if(!base[i]) {base[i]=x; return true;}
        x^=base[i];
    }
    return false;
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%lld", &a[i]);
    sort(a+1, a+n+1, CMP);
    for(int i=1; i<=n; i++)
    {
        if(insert(a[i])) ans+=a[i];
        sum+=a[i];
    }
    printf("%lld\n", sum-ans);
}

Posted on Edited on In

8月11日 Codeforces Round #503 题目链接：http://codeforces.com/contest/1020

A - New Building for SIS & B - Badge

过水，不说。。

C - Elections

思路： 算是一个比较简单的模拟（但是好像有大佬有$O(nlogn)$的做法）。。。枚举要得到多少选票，设为$x$，如果有其他党的选票大于x，就直接花钱买直到那个党选票小于x，如果这样最后选票不够x的话，就随便买选票直到有x张。这里买选票当然是尽可能买便宜的，然后总复杂度是$O(n^3)$的。

比赛时T了一发，然后大力卡了一下常数过了pretest。结果就很愉快地的因为TLE FST了….后面把最外层循环从1-n改为1-n/2+1就A了，想想自己真TM傻，卡常时这个都没有注意到。

代码：

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 <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#define LL long long
#define MAXN 3005
#define INF 1e18
using namespace std;

int n, m, p[MAXN], num[MAXN];
LL c[MAXN], ans=INF;

struct A {int p, tag; LL c;} a[MAXN];

void read1(LL &x)
{
    int f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    x*=f;
}

void read2(int &x)
{
    int f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    x*=f;
}

bool CMP1(A x, A y)
{
    if(x.p!=y.p) return x.p<y.p;
    else return x.c<y.c;
}

bool CMP2(A x, A y)
{
    return x.c<y.c;
}

int main()
{
    read2(n); read2(m);
    for(register int i=1; i<=n; ++i) read2(a[i].p), read1(a[i].c), num[a[i].p]++;
    for(register int i=1; i<=n/2+1; ++i)
    {
        sort(a+1, a+n+1, CMP1);
        for(register int j=1; j<=n; ++j) a[j].tag=0;
        LL cost=0; int res=0, pnt=1;
        for(register int j=1; j<=m; ++j)
        {
            if(j==1)
            {
                pnt+=num[j];
                res+=num[j];
                continue;
            }
            for(register int k=pnt; k<=pnt+num[j]-i; ++k)
            {
                cost+=a[k].c; a[k].tag=1;
                res++;
            }
            pnt+=num[j];
        }
        sort(a+1, a+n+1, CMP2);
        for(register int j=1; res<i; ++j)
        {
            if(a[j].tag || a[j].p==1) continue;
            res++;
            cost+=a[j].c;
        }
        ans=min(ans, cost);
    }
    printf("%lld\n", ans);
}

D - The hat

思路： 交互题，比赛时少看到一个条件连题目都没有弄懂。菜死了QWQ

相邻的同学手上数字不会相差超过1，这是一个很神奇的条件。我们设数组$b[i]=a[i]-a[i+n/2]$，根据上面的条件可以发现$b[i]-b[i+1]$只能为$\lbrace -2, 0, 2 \rbrace$，在某种意义下我们可以把数组$b$的取值视为是连续的，这个性质也很有意思。

显然有$b[i]=-b[i+n/2]$，答案也就是求一点$i$使得$b[i]=0$。因为上面的性质，我们就可以使用二分求解。有一点要注意的是如果$b$中有一个元素为奇数时，那么$b$中的所有元素都是奇数，这样就直接输出-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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define MAXN 100005
using namespace std;

int n, ans, a[MAXN], b[MAXN];

int main()
{
    scanf("%d", &n);
    printf("? %d\n", 1); fflush(stdout);
    scanf("%d", &a[0]);
    printf("? %d\n", n/2+1); fflush(stdout);
    scanf("%d", &a[n/2]);
    b[0]=a[0]-a[n/2]; b[n/2]=a[n/2]-a[0];
    if(b[0]%2) {printf("! -1\n"); fflush(stdout); return 0;};
    int l=0, r=n/2;
    while(1)
    {
        int mid=(l+r)/2;
        printf("? %d\n", mid+1); fflush(stdout);
        scanf("%d", &a[mid]);
        printf("? %d\n", n/2+mid+1); fflush(stdout);
        scanf("%d", &a[n/2+mid]);
        b[mid]=a[mid]-a[n/2+mid];
        if(b[mid]==0) {ans=mid; break;}
        if(b[mid]*b[l]<0) r=mid;
        else l=mid;
    }
    printf("! %d", ans+1);
}

E - Sergey’s problem

思路： 神题啊。。。首先有一个很简单的思路，假设一个确定了$1~i-1$号节点的集合，那么对于$i$号节点，如果集合中的点不与节点$i$相邻，那么就把$i$号节点加入集合中。

那么这样就会有一个问题，就是可能会有节点无法加入集合，并且集合中的点无法到达它（CF上第三个点就能够HACK掉）。于是我们先从小到大扫一遍确定出一个集合，集合内编号小的点不会向编号大的点连边。然后从大到小扫一遍这个集合，如果编号大的点有一条边连向了集合内编号小的点，那就把编号小的点移除集合。这样就可以保证满足题目的条件，因为第二遍移出集合的点一定能一步内到达，第一遍移出集合的点一定能两步内到达。

代码：

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
#include <iostream>
#include <cstring>
#include <cstdio>
#define MAXN 1000005
using namespace std;

int n, m, cnt, top, head[MAXN], ans[MAXN];
bool vis[MAXN];

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

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

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        addedge(x, y);
    }
    for(int i=1; i<=n; i++)
        if(!vis[i]) for(int j=head[i]; j; j=edge[j].next)
                if(edge[j].to>i) vis[edge[j].to]=1;
    for(int i=n; i>=1; i--)
        if(!vis[i])
        {
            ans[++top]=i;
            for(int j=head[i]; j; j=edge[j].next) vis[edge[j].to]=1;
        }
    printf("%d\n", top);
    for(int i=1; i<=top; i++) printf("%d ", ans[i]);
}