当前位置：网站首页>bzoj 5333 [Sdoi2018]荣誉称号

bzoj 5333 [Sdoi2018]荣誉称号

2022-08-09 06:34:00 【51CTO】


​ ​http://www.elijahqi.win/archives/3488​​​
题目背景
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 
       
       
 ​ ⌋
      
      

      
      
    
       
       
  • 1.
    • 
       
       
  • 2.
    • 
       
       
  • 3.
    • 
       
       
  • 4.
    • 
       
       
  • 5.
    • 
       
       
  • 6.
    • 
       
       
  • 7.
    • 
       
       
  • 8.
    • 
       
       
  • 9.
    • 
       
       
  • 10.
    • 
       
       
  • 11.
    • 
       
       
  • 12.
    • 
       
       
  • 13.
    • 
       
       
  • 14.
    • 
       
       
  • 15.
    • 
       
       
  • 16.
    • 
       
       
  • 17.
    • 
       
       
  • 18.
    • 
       
       
  • 19.
    • 
       
       
  • 20.
    • 
       
       
  • 21.
    • 
       
       
  • 22.
    • 
       
       
  • 23.
    • 
       
       
  • 24.
    •


​ 都要是 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.
    • 
       
       
  • 4.
    • 
       
       
  • 5.
    • 
       
       
  • 6.
    • 
       
       
  • 7.
    • 
       
       
  • 8.
    • 
       
       
  • 9.
    • 
       
       
  • 10.
    • 
       
       
  • 11.
    • 
       
       
  • 12.
    • 
       
       
  • 13.
    • 
       
       
  • 14.
    • 
       
       
  • 15.
    • 
       
       
  • 16.
    • 
       
       
  • 17.
    • 
       
       
  • 18.
    •


输出格式：
对于每组数据，输出一行一个整数，即最少需要的点券数量。

输入输出样例
输入样例#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<cstdio>
       
       
#include<cctype>
       
       
#include<cstring>
       
       
#include<algorithm>
       
       
#define ll long long
       
       
using 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<<l)-1<n;++l);
       
       
        for (int i=1;i<=n;++i) a[i]%=m;int bin=1;
       
       
        for (int i=n+1;i<=(1<<l)-1;++i) a[i]=b[i]=0;n=(1<<l)-1;
       
       
        for (int i=0;i<=k;++i) bin<<=1;
       
       
        for (int i=1;i<bin;++i) memset(c[i],0,sizeof(ll)*(m+1)),fa[i]=i,c[i][a[i]]=b[i],tmp[i]=(ll)a[i]*b[i];
       
       
        for (int i=bin;i<=n;++i) fa[i]=fa[i/bin],c[fa[i]][a[i]]+=b[i],tmp[fa[i]]+=(ll)a[i]*b[i];
       
       
        for (int i=1;i<bin;++i)
       
       
            for (int j=m-2;~j;--j) c[i][j]+=c[i][j+1];
       
       
        for (int i=1;i<bin;++i)
       
       
            for (int j=0;j<m;++j) f[i][j]=j*c[i][0]-tmp[i]+m*c[i][j+1];
       
       
        for (int i=bin>>1;i<bin;++i) for (int j=0;j<m;++j) dp[i][j]=f[i][j];
       
       
        for (int i=bin/2-1;i;--i){
       
       
            for (int j=0;j<m;++j){
       
       
                dp[i][j]=inf;
       
       
                for (int k=0;k<m;++k) dp[i][j]=min(dp[i][j],dp[i<<1][k]+dp[i<<1|1][k]+f[i][(j-k+m)%m]);
       
       
            }
       
       
        }printf("%lld\n",dp[1][0]);
       
       
    }
       
       
    return 0;
       
       
}
      
      

      
      
    
       
       
  • 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.
    •


原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_15744996/5557783

边栏推荐

猜你喜欢

随机推荐