xuxuxuxuxu

未归档提高模拟赛

提高模拟赛

来自【xuxuxuxuxu】 795 浏览 0 回复 2020-03-09

xuxuxuxuxu

+关注

提高模拟赛

图

题目描述

一张无自环、无重边的图，每个点有一个点权，对于每条边 $(x,y)$ ，点 $x$ 和点 $y$ 的点权必须不同。
假设这张图有 $k$ 种不同的点权，那么这张图就是一种 $k$ 色图。

定义函数 $g(n,k)$ 的值为所有 $n$ 个点的 $k$ 色图中的边数最大值。

现在给出三个整数 $n,l,r$ ,求： $\displaystyle \left(\sum_{i=l}^{r} g(n, i)\right)\bmod 998244353$

输入描述:

第一行输入一个整数 $T(1≤T≤10^3)$ ，表示数据组数。
对于每组数据，输入三个整数 $n,l,r$ 。

输出描述:

对于每组数据，输出一行一个整数表示答案。

输入

5
3 1 1
3 2 2
5 2 4
10 3 9
1000 123 789

输出

数据范围

对于 30% 的数据， $l,r,n≤10$
对于 60% 的数据， $l,r,n≤10^6$
对于 100% 的数据， $l,r,n≤10^9$ , $T≤10^3$

位运算

题目描述

定义 $popcount(x)$ 为 $x$ 在二进制下， $1$ 的个数。

求 $\sum_{i=l}^{r} \lfloor \frac{i}{popcount(i)} \rfloor$ ，由于答案可能很大，你只需要输出答案对 $998244353$ 取模后的结果即可。

输入描述:

第一行 $2$ 个整数表示 $l,r$

输出描述:

输出一行一个整数表示答案。

输入

1 4

输出

样例解释
$\lfloor \frac{1}{1} \rfloor +\lfloor \frac{2}{1} \rfloor + \lfloor \frac{3}{2} \rfloor + \lfloor \frac{4}{1} \rfloor=8$

数据范围
对于 30% 的数据， $l,r≤10^7$
对于 60% 的数据， $l,r≤2^{30}$
对于 80% 的数据， $l,r≤2^{40}$
对于 100% 的数据， $l,r≤2^{60}$

树

题目描述

给定一个 $n$ 个节点的树，其中第 $i$ 个节点的点权为 $val_i$ ，每条边都带有边权。

我们定义 $dis(x,y)$ 为从 $x$ 节点出发，到达点 $y$ 的最短路径长度。

现在xuxuxuxuxu想找到一个点对 $(x,y)$ ，满足 $x≠y$ ，要求最小化

$\sum_{i=1}^{n} val_i \times min(dis(x,i),dis(y,i))$

xuxuxuxuxu并不关心这个点对是什么，因为满足要求的点对可能有很多个，所以你只需要输出该权值即可。

输入描述:

第一行 $1$ 个正整数表示 $n$

第二行 $n$ 个正整数，第 $i$ 个表示 $val_i$

之后 $n−1$ 行，每行给定 $u,v,w$ ,表示 $u,v$ 间有一条长度为 $w$ 的边。

输出描述:

输出一行一个整数表示答案。

输入

6
1 1 4 5 1 4
1 2 1
2 3 1
2 4 4
3 5 5
3 6 14

输出

数据范围
对于 10% 的数据， $n≤100$
对于 30% 的数据， $n≤1000$
对于另外 20% 的数据，保证图为菊花
对于另外 20% 的数据，保证图为链
对于 100% 的数据， $n≤200000$ ，保证点权边权的大小不超过 $100000$ 且为正整数。

比赛题解

举报

收藏

赞

相关专栏

39篇文章 0订阅

评论加载中...