首页 > > 程序设计 > C/C++ >

hdu 6107--Typesetting(倍增)

2018-06-17 21:58:23来源：未知阅读 ()

题目链接

Problem Description

Yellowstar is writing an article that contains N words and 1 picture, and the i-th word contains

Input

The first line of the input gives the number of test cases T; T test cases follow.
Each case begins with one line with four integers N, W, pw, dw : the number of words, page width, picture width and left margin.
The next line contains N integers

Output

For each query, output one integer denotes the minimum number of rows.

Sample Input

2 7 4 3

1 3

1 2

2 2

5 2

3 8 2 3

1 1 3

1 1

Sample Output

题意：现在有一篇文章由 n 个单词构成，其中要放入一张图片，单词与单词之间要空一格，图片上不能放单词，单词之间的顺序不能变化，现在规定图片宽为pw，文章宽为w，图片左边距文章左边线宽为dw，现在Q次询问，每次给定图片高h和图片在文章中的起始位置（距离文章上边界）x，求最少多少行能放下图片与单词？

思路：先计算出固定宽为w、dw、w-dw-pw时以每个单词开头时下一行第一个单词的下标，根据dw和w-dw-pw可以计算出有图片占据行时以每个单词开始时的下一行第一个单词的下标，然后根据已求出的有图片和无图片占据行时以每个单词开始的下一行第一个单词的下标信息，进行倍增求出以每个单词开始时，向下2^i行的第一个单词的下标。

代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=1e5+5;
int n,w,pw,dw;
int a[N];
int lto[N],rto[N],to[N];
int s[N][20],t[N][20];

void cal(int *c,int W)
{
    int len=-1;
    for(int i=0,j=0;i<=n;i++)
    {
        while(len+a[j]+1<=W) len+=a[j]+1,j++;
        c[i]=j;
        len-=a[i]+1;
    }
}
void process()
{
    cal(lto,w);
    for(int i=0;i<=n;i++) s[i][0]=lto[i];
    to[n]=0;
    for(int i=n-1;i>=0;i--) to[i]=to[lto[i]]+1;
    for(int i=1;i<18;i++)
        for(int j=0;j<=n;j++)
           s[j][i]=s[s[j][i-1]][i-1];
    cal(lto,dw);
    cal(rto,w-dw-pw);
    for(int i=0;i<=n;i++) t[i][0]=rto[lto[i]];
    for(int i=1;i<18;i++)
        for(int j=0;j<=n;j++)
           t[j][i]=t[t[j][i-1]][i-1];
}
int main()
{
    int T; cin>>T;
    while(T--)
    {
       scanf("%d%d%d%d",&n,&w,&pw,&dw);
       for(int i=0;i<n;i++) scanf("%d",&a[i]);
       a[n]=w+5;
       process();
       int Q; scanf("%d",&Q);
       while(Q--)
       {
           int x,h,ans,tot=0; scanf("%d%d",&x,&h);
           ans=min(--x,to[0]);
           for(int i=0,tmp=ans;i<18;i++)
           {
               if(tmp&1) tot=s[tot][i];
               tmp>>=1;
           }
           for(int i=0,tmp=h;i<18;i++)
           {
               if(tmp&1) tot=t[tot][i];
               tmp>>=1;
           }
           ans+=h;
           ans+=to[tot];
           printf("%d\n",ans);
       }
    }
    return 0;
}