题目描述
题目中的树是一棵m层满n叉树, 且树的每一条边的边权都只能从集合S中唯一的选出来, 最后题目要求树中所有的节点到根节点的距离和的最小值(对p取模)。
样例
input:
5 2 3 10
1 2 3 4 5
output:
6
求解
(贪心,排序, 前缀和, 快速幂, 龟速乘) $O(nlogn)$
由题意可知, 每一条树边都会被孩子节点(或者以孩子节点为子树的节点)计入结果, 并且每一条树边被计入结果的次数是固定不变的, 因此我们让计入结果次数多的边的边权尽量小, 让记入结果次数少的边的边权尽量大。
另外观察可知, 位于树中同一层的边计入结果的次数都是一样多的。因此, 同一层的边权可以累加起来再乘以计入结果的次数;
本题的用于取模的p很大, 因此乘法要用龟速乘取模。
C++ 代码
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
const int N = 200010;
LL p;
int k, m, n;
LL e[N];
LL qadd(LL a, LL k, LL p)
{
LL res = 0;
while(k)
{
if(k & 1) res = (res + a) % p;
a = (a + a) % p;
k >>= 1;
}
return res;
}
LL qmi(int a, int k, LL p)
{
LL res = 1;
while(k)
{
if(k & 1) res = qadd(res, a, p);
a = qadd(a, a, p);
k >>= 1;
}
return res;
}
// ver_num(n, m) 返回深度是m的满n叉树中的节点个数;
LL ver_num(int n, int m)
{
return (qmi(n, m, p) - 1) / (n - 1);
}
int main()
{
while(cin >> k >> m >> n >> p)
{
for(int i = 1;i <= k;i ++) scanf("%lld", &e[i]);
sort(e + 1, e + k + 1);
for(int i = 1;i <= k;i ++) e[i] = (e[i - 1] + e[i]) % p;
int l = 1;
LL res = 0;
for(int i = 1, j = 1;i < m;i ++, j ++)
{
int r = l + pow(n, j) - 1; // 取模之后的前缀和数组区间求和一定要是正数
res = (res + qadd(ver_num(n, m - i), ((e[r] - e[l - 1]) % p + p) % p, p)) % p;
l = r + 1;
}
printf("%lld\n", res);
}
return 0;
}
回来啦,从前的学长又回来啦!!!
这几天被虐的超级惨😫
果然以后还是要多写题解才行/(ㄒoㄒ)/~~
怎么发表情啊
我这儿是Win + ‘.’ 😁
笔记本可能不行
我的就是笔记本啊哈哈
等会去找你,教教我如何发表情
嘿嘿 苦笑 呲牙 强颜欢笑 憨笑
水一题....