Post 16

Veröffentlicht am | Edited on

Your voice is full of beautiful memories we have yet to make.

B Xor Sum

链接：

https://ac.nowcoder.com/acm/contest/272/B

来源：牛客网

题目描述

给定一棵n个点的树，每个点有权值img。定义img表示 img 到 img 的最短路径上，所有点的点权异或和。

对于img，求所有img的异或和。

输入描述:

1
2
3
第一行一个整数n。
接下来n-1行，每行2个整数u,v，表示u,v之间有一条边。
第n+1行有n个整数，表示每个点的权值。

输出描述:

1
输出一个整数，表示所有的异或和，其中。

示例1

输入

1
2
3
4
5
4
1 2
1 3
1 4
1 2 3 4

输出

1
5

备注:

img

题解

这个题要注意是点权不是边权。。。这意味着LCA会被异或掉。。

所以不能两层前缀异或来做了。。我说我暴力怎么都不对。。

考虑每个点被经过了多少次！

由于树上两点路径唯一，假如我们把这个点从树上删掉，树会分成若干个联通块，任意不同联通块两点间的路径显然都是经过这个点的。

要想高效统计，我们可以把它看做有根树，这样任意一点被删除产生的联通块就是它所有子树和子树外的点，显然可以前缀和优化，注意题目中一条路径端点是升序，意味着每条路径只被计算一次，注意减半的实现（可以最后除二也可以边加边算）。

只需要一次DFS即可计算，时间复杂度

Code：

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 500005
int v[maxn] , n , ans , head[maxn] , ct , sz[maxn];
struct edge{
	int next , to;
}e[maxn<<1];
inline void add(int x , int y)
{
	e[++ct].next = head[x];
	e[ct].to = y;
	head[x] = ct;
}
void dfs(int x , int fx)
{
	sz[x] = 1;
	for(int i = head[x] ; i ; i = e[i].next)
	{
		int v = e[i].to;
		if(v == fx) continue;
		dfs(v , x) , sz[x] += sz[v];
	}

	long long tmp = 0;
	for(int i = head[x] , tot = n - sz[x] + 1; i ; i = e[i].next)
	{
		int v = e[i].to;
		if(v == fx) continue;
		tmp += 1ll * tot * sz[v] , tot += sz[v];
	}
	tmp += n - sz[x];
	if(tmp&1) ans ^= v[x];
}
int main()
{
	scanf("%d",&n);
	int x , y;
	for(int i = 1 ; i <= n - 1 ; ++i)
		scanf("%d%d",&x,&y) , add(x,y) , add(y,x);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&v[i]);
	dfs(1,1);
	printf("%d",ans);
}

NOWCODER PRACTICE 32 C balls

https://ac.nowcoder.com/acm/contest/272/C

题目描述

有一个盒子，里面有一个黑球和一个白球。每次随机取出盒子中的一个球，并将两个与取出球同色的球放进盒子（就是随机一种颜色将其个数+1）。

求n次取球后，盒子中白色球数目的期望。

输入描述:

1
输入一个整数n，表示取球次数。

输出描述:

1
输出一个实数，表示n次取球后白球数目的期望。答案保留7位小数。

示例1

输入

1
2

输出

1
2.0000000

说明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
若第一次取出白球：

放入两个白球，则现在有一个黑球两个白球，概率为1/2。

若第二次取出白球，则现在有一个黑球三个白球，概率为1/2*2/3=1/3，期望个数为1/3*3=1；

若第二次取出黑球，则现在有两个黑球两个白球，概率为1/2*1/3=1/6，期望个数为1/6*2=1/3。

若第一次取出黑球：

放入两个黑球，则现在有两个黑球一个白球，概率为1/2。

若第二次取出黑球，则现在有三个黑球一个白球，概率为1/2*2/3=1/3，期望个数为1/3*1=1/3；

若第二次取出白球，则现在有两个黑球两个白球，概率为1/2*1/3=1/6，期望个数为1/6*2=1/3。

所以白球期望数目为2个。

备注:

题解

一道不错的期望题。

先考虑暴力dp。

设f_{i,j}表示取$i$次后，有$j$个白球的概率是多少。

设计这个状态不难，因为很显然每次只会多一个球，因此只需要考虑上次取的是白球还是黑球。

因此

前面表示这次取黑球，后面是取白球的情况。

然后题目只有一个输入，很容易想到：打表！

发现答案是0.5

还有一种更神仙的做法：

白球黑球并没有本质的区别，对于一种取的可能性对黑白球取反的可能性是一样的，显然也是一一对应的。

因此答案就是1+n/2。（emmmm）

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 5005
double f[maxn][maxn] , ans;
int n;
int main()
{
	scanf("%d",&n);
	f[0][1] = 1;
	for(int i = 1 ; i <= n ; ++i)
		for(int j = 1 ; j <= i + 1; ++j)
			f[i][j] = f[i-1][j] * (i-j+1)/(i+1) + f[i-1][j-1] * (j-1)/(i+1);
	for(int i = 1 ; i <= n + 1; ++i)
		ans += (double)i * f[n][i];
}

D car

链接：

https://ac.nowcoder.com/acm/contest/315/D

来源：牛客网

题目描述

妞妞参加完Google Girl Hackathon之后,打车回到了牛家庄。

妞妞需要支付给出租车司机车费s元。妞妞身上一共有n个硬币，第i个硬币价值为p[i]元。

妞妞想选择尽量多的硬币，使其总价值足以支付s元车费(即大于等于s)。

但是如果从妞妞支付的这些硬币中移除一个或者多个硬币，剩下的硬币总价值还是足以支付车费的话，出租车司机是不会接受的。例如: 妞妞使用价值为2，5，7的硬币去支付s=11的车费,出租车司机是不会接受的，因为价值为2这个硬币是可以移除的。

妞妞希望能选取最大数量的硬币，使其总价值足以支付车费并且出租车司机能接受。

妞妞希望你能帮她计算最多可以支付多少个硬币。

输入描述:

1
2
3
输入包括两行, 第一行包括两个正整数n和s(1 <= n <= 10, 1 <= s <= 1000), 表示妞妞的硬币个数和需要支付的车费。
第二行包括n个正整数p[i] (1 <= p[i] <= 100)，表示第i个硬币的价值。
保证妞妞的n个硬币价值总和是大于等于s。

输出描述:

1
输出一个整数, 表示妞妞最多可以支付的硬币个数。

输入

1
2
5 9
4 1 3 5 4

输出

1
3

题解

实在是太。。。爆搜都能过吧。

不过我们还是可以写一个复杂度小一点的没有转移的状态压缩（没有dp 2333）

首先排个序（似乎不难想，主要是为了方便快速找到状态中的最小值），用三个数组保存每个状态的价值，最小值，用的个数。

然后就AC了。。

Code：

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 15
int p[maxn] , n , s , f[1<<maxn] , g[1<<maxn] , h[1<<maxn];
inline int calc(int s)
{
	int ans = 0;
	for(int i = 0 ; i < n ; ++i)
		if(s & (1 << i))
			ans += p[i];
	return ans;
}
inline int calc2(int s)
{
	for(int i = 0 ; i < n ; ++i)
		if(s & (1<<i))
			return p[i];
	return 0;
}
inline int calc3(int s)
{
	int ans = 0;
	for(int i = s ; i ; i -= i & -i)
		++ans;
	return ans;
}
int main()
{
	scanf("%d%d",&n,&s);
	for(int i = 0 ; i < n ; ++i)
		scanf("%d",p + i);
	std::sort(p , p + n);
	f[0] = 0;
	int S = (1 << n);
	for(int i = 1 ; i < S ; ++i)
		f[i] = calc(i) , g[i] = calc2(i) , h[i] = calc3(i);
	int ans = -0x7ffff;
	for(int i = 1 ; i < S ; ++i)
		if(f[i] >= s && f[i] - g[i] < s)
			ans = std::max(ans , h[i]);
	printf("%d",ans);
}

牛客练习赛32 D

https://ac.nowcoder.com/acm/contest/272/D

来源：牛客网

题目描述

小p和他的朋友约定好去游乐场游玩，但是他们到了游乐场后却互相找不到对方了。
游乐场可以看做是一张n个点，m条道路的图，每条道路有边权wi，表示第一次经过该道路时的花费（第二次及以后经过时花费为0）。
现在，小p要去找他的朋友，但他的朋友行踪很诡异，小p总是要遍历完这n个点才能找到他，同时小p希望总花费最小。
找到朋友的方案可能不唯一（具体看样例解释），小p想知道在这所有的方案中，有多少条边在每个方案中都会被经过。

输入描述:

1
2
第一行两个整数n, m. p，分别表示点数,边数,小p的初始位置。
接下来m行，每行两个整数u, v, w表示从u到v有一条无向边，边权为w。

输出描述:

1
输出一个整数k，表示必须经过的边的数量。

示例1

输入

1
2
3
4
5
6
7
8
5 7 1
1 2 3
2 3 7
1 3 5
2 4 2
1 5 3
5 4 3
2 5 3

输出

1
2

说明

1
2
3
4
5
6
样例解释：

几种可能的方案如下：

可以证明，4 - 2和1 - 3这两条边在所有方案中都被经过。
(以上每种方案的总花费均为13，同时可以证明没有比这更优的策略)

示例2

输入

1
2
3
4
3 3 1
1 2 1
1 3 1
2 3 2

输出

1
2

示例3

输入

1
2
3
4
3 3 1
1 2 2
2 3 2
1 3 2

输出

1
0

备注:

保证图联通，保证无自环，保证无重边

题解

其实这道题做法不难想啊。

正解是什么Tarjan之类的，反正没想到也不会证。

宇宙第二的最神的DXC学长表示可以主席树（我会的好少啊qwq），并且成功Hack掉了我的做法。

然后我去掉了访问标记改成了暴力跳，想先写个正确的暴力。

结果发现AC了。。。

这个复杂度很假，以至于我都没法分析，最坏好像是

但是好像并不好卡，需要根号平衡之类的。

Code：

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 200005
int head[maxn] , ct , n , m , ans , f[maxn] , tot , g[maxn] , h[maxn] , dep[maxn];
bool calc[maxn] , mst[maxn] , vis[maxn];
struct edge{
    int fr , to , dis;
    bool operator<(const edge& x)const{
        return dis < x.dis;
    }
}er[maxn<<1];
struct E{
    int next , to , dis;
}e[maxn<<1];
int find(int x)
{
    if(f[x] != x) return f[x] = find(f[x]);
    return f[x];
}
void dfs(int x , int fx , int dis , int num)
{
    g[x] = fx;
    h[x] = dis;
    dep[x] = dep[fx] + 1;
    for(int i = head[x] ; i ; i = e[i].next)
    {
        int v = e[i].to;
        if(v == fx) continue;
        dfs(v , x , e[i].dis , i);
    }
}
inline void mark(int u , int v , int dis)
{
    if(dep[u] < dep[v]) std::swap(u , v);
    while(dep[u] > dep[v])
    {
        if(h[u] == dis) calc[u] = true;
        u = g[u];
    }
    if(u == v) return ;
    while(u != v)
    {
        if(h[u] == dis) calc[u] = true;
        if(h[v] == dis) calc[v] = true;
        u = g[u] , v = g[v];
    }
    return ;
}
inline void add(int x , int y , int dis)
{
    e[++ct].next = head[x];
    e[ct].to = y;
    e[ct].dis = dis;
    head[x] = ct;
}
int main()
{
//  freopen("data.in","r",stdin);
//  freopen("my.out","w",stdout);
    int k;
    scanf("%d%d%d",&n,&m,&k);
    for(int i = 1 ; i <= m ; ++i)
        scanf("%d%d%d",&er[i].fr , &er[i].to , &er[i].dis);
    std::sort(er+1,er+m+1);
    for(int i = 1 ; i <= n ; ++i)
        f[i] = i;
    for(int i = 1 ; i <= m && tot < n - 1 ; ++i)
    {
        int fr = er[i].fr , to = er[i].to;
        if(find(fr) != find(to))
        {
            f[find(fr)] = find(to);
            ++tot;
            mst[i] = true;
        }
    }
    ct = 1;
    for(int i = 1 ; i <= m ; ++i)
        if(mst[i]) add(er[i].fr , er[i].to , er[i].dis) , add(er[i].to , er[i].fr , er[i].dis);
    dfs(1,1,-1,0);
    for(int i = 1 ; i <= m ; ++i)
        if(!mst[i])
            mark(er[i].fr , er[i].to , er[i].dis);
    for(int i = 2 ; i <= n ; ++i)
        if(!calc[i]) ++ans;
    printf("%d",ans);
}

A tokitsukaze and Counting

https://ac.nowcoder.com/acm/contest/308/A

给出3个整数L，R，x。tokitsukaze想知道，闭区间[L,R]中，x的倍数出现了几次。

1
2
3
1≤L≤R≤10^18

1≤x≤10^18

题解

简单差分。。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define LL long long
int t;
LL L , R , x;
int main()
{
	scanf("%d",&t);
	while(~(--t))
	{
		scanf("%lld%lld%lld",&L,&R,&x);
		printf("%lld\n",R/x - (L-1)/x);
	}
}

B tokitsukaze and RPG

https://ac.nowcoder.com/acm/contest/308/B

tokitsukaze最近沉迷一款RPG。
这个RPG一天有k分钟，每一天从第1分钟开始。
有n种怪物，第i种怪物每天第一次出现的时间为Xi分钟，第二次出现的时间为2Xi分钟，第三次出现的时间为3Xi分钟……同一时刻出现的怪物种类越多，打怪获得的经验也越高。
为了高效练级，tokitsukaze想知道在一天内出现怪物种类最多的时间点会出现多少种怪物，这样的时间点有多少个。

题解

一眼筛法。

结果忘了筛法复杂度正确是在1~n的情况下，忘了排序结果被卡成nk。。。

排序后把相同的数放在一起处理即可。

我怎么净做水题

时间复杂度

Code:

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <vector>
#define maxn 100005
#define maxR 1000005
int x[maxn] , p[maxR] , n , k , c[maxR];
std::vector<int> v;
int main()
{
    scanf("%d%d",&n,&k);
    for(int i = 1 ; i <= n ; ++i)
        scanf("%d",&x[i]);
    for(int i = 1 ; i <= n ; ++i)
        c[x[i]] ++;
    for(int i = 1 ; i <= k ; ++i)
        if(c[i]) v.push_back(i);
    for(int i = 0 ; i < (int)v.size() ; ++i)
        for(int j = 1 ; j * v[i] <= k ; ++j)
            p[j * v[i]] += c[v[i]];
    int ans = -0x7ffffff , tot = 0;
    for(int i = 1 ; i <= k ; ++i)
    {
        if(p[i] > ans) ans = p[i] , tot = 1;
        else if(p[i] == ans) ++tot;
    }
    if(ans == -0x7ffffff) tot = n , ans = 0;
    printf("%d %d\n",ans , tot);
}

接下来两个小时学会可持久化Trie与可持久化SegmentTree。。

21:47，表示对可持久化Trie的正确性不是很明白。。。可能没有完全理解原理，明天写一个可持久化的详细介绍顺便加几道题吧。