首页 > 代码库 > HDU 6107 Typesetting 倍增
HDU 6107 Typesetting 倍增
Typesetting
Problem Description
Yellowstar is writing an article that contains N words and 1 picture, and the i-th word contains ai characters.
The page width is fixed to W characters. In order to make the article look more beautiful, Yellowstar has made some rules:
1. The fixed width of the picture is pw. The distance from the left side of the page to the left side of the photo fixed to dw, in other words, the left margin is dw, and the right margin is W - pw - dw.
2. The photo and words can‘t overlap, but can exist in same line.
3. The relative order of words cannot be changed.
4. Individual words need to be placed in a line.
5. If two words are placed in a continuous position on the same line, then there is a space between them.
6. Minimize the number of rows occupied by the article according to the location and height of the image.
However, Yellowstar has not yet determined the location of the picture and the height of the picture, he would like to try Q different locations and different heights to get the best look. Yellowstar tries too many times, he wants to quickly know the number of rows each time, so he asked for your help. It should be noted that when a row contains characters or pictures, the line was considered to be occupied.
The page width is fixed to W characters. In order to make the article look more beautiful, Yellowstar has made some rules:
1. The fixed width of the picture is pw. The distance from the left side of the page to the left side of the photo fixed to dw, in other words, the left margin is dw, and the right margin is W - pw - dw.
2. The photo and words can‘t overlap, but can exist in same line.
3. The relative order of words cannot be changed.
4. Individual words need to be placed in a line.
5. If two words are placed in a continuous position on the same line, then there is a space between them.
6. Minimize the number of rows occupied by the article according to the location and height of the image.
However, Yellowstar has not yet determined the location of the picture and the height of the picture, he would like to try Q different locations and different heights to get the best look. Yellowstar tries too many times, he wants to quickly know the number of rows each time, so he asked for your help. It should be noted that when a row contains characters or pictures, the line was considered to be occupied.
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 ai, indicates i-th word consists of ai characters.
The third line contains one integer Q.
Then Q lines follow, each line contains the values of xi and hi, indicates the starting line and the image height of the image.
Limits
T≤10
1≤N,W,Q≤105
1≤pw,ai≤W
0≤dw≤W−pw
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 ai, indicates i-th word consists of ai characters.
The third line contains one integer Q.
Then Q lines follow, each line contains the values of xi and hi, indicates the starting line and the image height of the image.
Limits
T≤10
1≤N,W,Q≤105
1≤pw,ai≤W
0≤dw≤W−pw
Output
For each query, output one integer denotes the minimum number of rows.
Sample Input
22 7 4 31 331 22 25 23 8 2 31 1 311 1
Sample Output
2331
题意：
给你n个单词，放到宽度是W的文档里，每个单词不能跨行，在一行的连续的单词必须有空格隔开
现在，在第 xi 行 距离文档左边框 dw的位置 放一个 宽度pw ，长度hi 的 图片，现在把单词全部填上去，问最少占多少行（只要有单词或者图片都算被占）
题解：
设定f[i][j]，表示以 第 i 个单词 开始 给你 2^j行 能放到第几个单词
pw, dw,w是给定的，所以我们对于所有询问，无非就是 三种 宽度， 我们用倍增预处理三种宽度的 f 数组就行了
我写的挫，复杂度：O(Q*logn*logn + n*logn)
下面给出AC代码
#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define ls i<<1#define rs ls | 1#define mid ((ll+rr)>>1)#define pii pair<int,int>#define MP make_pairtypedef long long LL;typedef unsigned long long ULL;const long long INF = 1e18+1LL;const double pi = acos(-1.0);const int N = 2e5+10, M = 1e3+20,inf = 2e9;int f[N][25],n,w,pw,dw,a[N],g[N][25];LL sum[N];int main() { int T; scanf("%d",&T); while(T--) { scanf("%d%d%d%d",&n,&w,&pw,&dw); for(int i = 1; i <= n; ++i) scanf("%d",&a[i]); memset(g,0,sizeof(g)); memset(f,0,sizeof(f)); sum[0] = 0; for(int i = 1; i <= n; ++i) sum[i] = sum[i-1] + 1LL*a[i] + 1LL; for(int i = 1; i <= n; ++i) { int l = i,r = n; while(l <= r) { int md = (l + r) >> 1; if(sum[md] - sum[i-1] - 1<= 1LL*w) f[i][0] = md,l = md+1; else r = md-1; } l = i,r = n; int now = -1; while(l <= r) { int md = (l + r) >> 1; if(sum[md] - sum[i-1] - 1 <= 1LL*dw) now = md,l = md+1; else r = md-1; } if(now == -1) g[i][0] = i-1; else g[i][0] = now; l = g[i][0] + 1,r = n,now = -1; while(l <= r) { int md = (l + r) >> 1; if(sum[md] - sum[g[i][0]] - 1 <= 1LL*(w - pw - dw)) now = md,l = md+1; else r = md-1; } if(now != -1) g[i][0] = now; } for(int j = 1; j <= 18; ++j) for(int i = 1; i <= n; ++i){ if(f[i][j-1] == n) f[i][j] = n; else f[i][j] = f[f[i][j-1] + 1][j-1]; } for(int j = 1; j <= 18; ++j) for(int i = 1; i <= n; ++i){ if(g[i][j-1] == n) g[i][j] = n; else g[i][j] = g[g[i][j-1] + 1][j-1]; } int Q; scanf("%d",&Q); while(Q--) { int x,h; scanf("%d%d",&x,&h); x -= 1; int now = 0,l,r,ans; for(int i = 18; i >= 0; --i) if(((x>>i)&1) && now != n)now = f[now+1][i]; if(now == n) { l = 1; r = x,ans = 1; while(l <= r) { int md = (l+r)>>1; now = 0; for(int i = 18; i >= 0; --i) if(((md>>i)&1) && now != n)now = f[now+1][i]; if(now == n) ans = md,r = md-1; else l = md+1; } printf("%d\n",ans + h); continue; } int tmp = now; for(int i = 20; i >= 0; --i) if(((h>>i)&1) && now != n) now = g[now+1][i]; if(now == n) { printf("%d\n",h + x); continue; } tmp = now; l = 0; r = 100005,ans = 100005; while(l <= r) { int md = (l+r)>>1; now = tmp; for(int i = 18; i >= 0; --i) if(((md>>i)&1) && now != n)now = f[now+1][i]; if(now == n) ans = md,r = md-1; else l = md+1; } printf("%d\n",x + ans + h); } } return 0;}
Typesetting
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 199 Accepted Submission(s): 95
Problem Description
Yellowstar is writing an article that contains N words and 1 picture, and the i-th word contains ai characters.
The page width is fixed to W characters. In order to make the article look more beautiful, Yellowstar has made some rules:
1. The fixed width of the picture is pw. The distance from the left side of the page to the left side of the photo fixed to dw, in other words, the left margin is dw, and the right margin is W - pw - dw.
2. The photo and words can‘t overlap, but can exist in same line.
3. The relative order of words cannot be changed.
4. Individual words need to be placed in a line.
5. If two words are placed in a continuous position on the same line, then there is a space between them.
6. Minimize the number of rows occupied by the article according to the location and height of the image.
However, Yellowstar has not yet determined the location of the picture and the height of the picture, he would like to try Q different locations and different heights to get the best look. Yellowstar tries too many times, he wants to quickly know the number of rows each time, so he asked for your help. It should be noted that when a row contains characters or pictures, the line was considered to be occupied.
The page width is fixed to W characters. In order to make the article look more beautiful, Yellowstar has made some rules:
1. The fixed width of the picture is pw. The distance from the left side of the page to the left side of the photo fixed to dw, in other words, the left margin is dw, and the right margin is W - pw - dw.
2. The photo and words can‘t overlap, but can exist in same line.
3. The relative order of words cannot be changed.
4. Individual words need to be placed in a line.
5. If two words are placed in a continuous position on the same line, then there is a space between them.
6. Minimize the number of rows occupied by the article according to the location and height of the image.
However, Yellowstar has not yet determined the location of the picture and the height of the picture, he would like to try Q different locations and different heights to get the best look. Yellowstar tries too many times, he wants to quickly know the number of rows each time, so he asked for your help. It should be noted that when a row contains characters or pictures, the line was considered to be occupied.
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 ai, indicates i-th word consists of ai characters.
The third line contains one integer Q.
Then Q lines follow, each line contains the values of xi and hi, indicates the starting line and the image height of the image.
Limits
T≤10
1≤N,W,Q≤105
1≤pw,ai≤W
0≤dw≤W−pw
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 ai, indicates i-th word consists of ai characters.
The third line contains one integer Q.
Then Q lines follow, each line contains the values of xi and hi, indicates the starting line and the image height of the image.
Limits
T≤10
1≤N,W,Q≤105
1≤pw,ai≤W
0≤dw≤W−pw
Output
For each query, output one integer denotes the minimum number of rows.
Sample Input
22 7 4 31 331 22 25 23 8 2 31 1 311 1
Sample Output
2331
Source
HDU 6107 Typesetting 倍增
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。