bzoj 5333 [Sdoi2018]荣誉称号

bzoj 5333 [Sdoi2018]荣誉称号

​​ 题目背景 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 kx ​ ⌋

​ 都要是 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]+=(i−ay)by,ay≤i f [ x ] [ i ] + = ( i − a y ) b y , a y ≤ i

f[x][i]+=(i−ay)by,ay≤i f [ x ] [ i ] + = ( i − a y ) b y , a y ≤ i

f[x][i]+=(m−ay+i)by,ay>i f [ x ] [ i ] + = ( m − a y + i ) b y , a y > i

重写式子： f[x][i]=i∑yby−∑yay×by+m∑ay>iby f [ x ] [ i ] = i ∑ y b y − ∑ y a y × b y + m ∑ a y > i b y

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

#include#include#include#include#define ll long longusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if(T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}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;}const int N=2e7;const int K=2100;const int M=220;const ll inf=1LL<<60;int n,k,m,a[N],b[N],fa[N],T;ll tmp[K],c[K][M],dp[K][M],f[K][M];void gen(){ n=read();k=read();m=read();p=read();SA=read();SB=read();SC=read();A=read();B=read(); //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++) a[i]=read(),b[i]=read();//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; }}int main(){// freopen("bzoj5333.in","r",stdin); T=read(); while(T--){ gen();int l;for (l=0;(1<>1;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。