题目背景
Input file: title.in
Output file: title.out
Time limit: 10 seconds
Memory limit: 512 megabytes
题目描述
休闲游戏玩家小 QQ 不仅在算法竞赛方面取得了优异的成绩,还在一款收集钻石的游戏中排名很高。

这款游戏一共有 nn 种不同类别的钻石,编号依次为 11 到 nn 。小 QQ 已经玩了这款游戏很久了,对于第 ii 种钻石,他已经收集到了 a_ia
i
​ 个。这款游戏最大的亮点就是,钻石只有一种获得途径,那就是从商城中购买。具体来说,第 ii 种钻石的单价为 b_ib
i
​ 点券。为了鼓励玩家充值,每种钻石都没有数量上限,只要肯充钱,就可以拥有任意多的钻石。但是这款游戏并没有开发 “丢弃道具” 功能,因此小 QQ 不能通过丢弃钻石去完成任务。

最近这款游戏推出了一个限时成就任务,完成任务的玩家可以获得荣誉称号,而完成任务条件则是: 给定正整数 kk 和 mm ,对于任意一个整数 x(2^k ≤ x ≤ n)x(2
k
≤x≤n) , a_x + a_{\lfloor{\frac{x}{2}}\rfloor} + a_{\lfloor{\frac{x}{4}}\rfloor} + _{\lfloor{\frac{x}{8}}\rfloor} + … + _{\lfloor{\frac{x}{2^k}}\rfloor}a
x
​ +a

2
x
​ ⌋
​ +a

4
x
​ ⌋
​ +

8
x
​ ⌋
​ +…+

2
k

x
​ ⌋
​ 都要是 mm 的倍数。

高玩小 QQ 当然想完成这个限时成就任务,但是在充钱之前他想知道他究竟需要多少点券才能完成这个任务。请写一个程序帮助小 QQ 计算最少需要的点券数量。

输入输出格式
输入格式:
第一行包含一个正整数 TT ,表示测试数据的组数。

每组数据第一行包含 99 个正整数 n, k, m, p, SA, SB, SC, A, Bn,k,m,p,SA,SB,SC,A,B ,其中 nn 表示钻石种类数, k, mk,m 表示任 务条件。

为了在某种程度上减少输入量, a[]a[] 和 b[]b[] 由以下代码生成:

unsigned int SA, SB, SC;int p, A, B;
unsigned int rng61(){
SA ^= SA << 16; SA ^= SA >> 5;
SA ^= SA << 1;
unsigned int t = SA;
SA = SB;
SB = SC;
SC ^= t ^ SA;
return SC;
}
void gen(){
scanf(“%d%d%d%d%u%u%u%d%d”, &n, &k, &m, &p, &SA, &SB, &SC, &A, &B);
for(int i = 1; i <= p; i++)scanf(“%d%d”, &a[i], &b[i]);
for(int i = p + 1; i <= n; i++){
a[i] = rng61() % A + 1;
b[i] = rng61() % B + 1;
}
}
输出格式:
对于每组数据,输出一行一个整数,即最少需要的点券数量。

输入输出样例
输入样例#1:
2
3 1 2 3 11111 22222 33333 1 1
1 5
2 3
3 6
7 2 3 7 11111 22222 33333 1 1
6 9
4 5
3 7
5 2
2 4
1 7
9 6
输出样例#1:
3
14
说明
1 ≤ T ≤ 101≤T≤10 ,
1 ≤ k ≤ 101≤k≤10 且 2^k ≤ n2
k
≤n ,
1 ≤ p ≤ min(n, 100000)1≤p≤min(n,100000) , 10000 ≤ SA, SB, SC ≤ 100000010000≤SA,SB,SC≤1000000 ,
1 ≤ A, B, ai, bi ≤ 10^71≤A,B,ai,bi≤10
7

子任务 11 ( 3030 分):满足 1 ≤ n ≤ 10001≤n≤1000 且 m = 2m=2 。

子任务 22 ( 4040 分):满足 1 ≤ n ≤ 10^51≤n≤10
5
且 m ≤ 200m≤200 。

子任务 33 ( 3030 分):满足 1 ≤ n ≤ 10^71≤n≤10
7
且 m ≤ 200m≤200 。

考虑一条链的情况 如果1~k和2~k+1相同 那么说明第二个的第一个和第一个的第k+1个在%m意义下是同余的

因为每次都/2所以可以发现这是一棵二叉树

那么每次要做的都是树上的链 那么我们考虑设f[x][i]表示把当前第x点改成%m余数是i的代价是多少设dp[x][i]表示从x节点出发 走到叶子节点他们的和都是i的最小代价 叶子:dp[x][i]=f[x][i],否则dp[x][i]=min(dp[y1][j]+dp[y2][j]+f[x][(i-j+m)%m])

直接预处理f[x][i]是非常简单的n*m的做法可搞

因为后面的只和最前面的2^(k+1)-1有关

但是显然复杂度不可以设fa[i]表示i节点跳跃k+1次后到达的节点

考虑所有的子树中的节点对我当前节点答案的影响

若x=fa[y],考虑y对f[x][i]的影响:

f[x][i]+=(iay)by,ayi


重写式子:
f[x][i]=i\sum_{y}b_y-\sum_{y}a_y\times b_y+m\sum_{a_y>i}b_y

如果树不是满的就强行补充到满

 


elijahqi

退役了 现在在商院 偶尔打CF,有时有ACM regional也去玩一下

发表评论