【清北学堂2018-刷题冲刺】Contest 7

Task 1:小奇采药

【问题描述】

 小奇是只天资聪颖的喵,他的梦想是成为世界上最伟⼤的医师。

 为此,他想拜喵星球最有威望的医师为师。

 医师为了判断他的资质,给他出了⼀个难题。

 医师把他带到⼀个到处都是草药的⼭洞里对他说:“小奇,这个⼭洞里有⼀些不同的草药,采每⼀株都需要⼀些时间,每⼀株也有它自身的价值。

 我会给你⼀段时间,在这段时间里,你可以采到⼀些草药。

 如果你是⼀只聪明的喵,你应该可以让采到的草药的总价值最⼤。”

【输入格式】

  第1 ⾏包括1 个整数T,表示数据组数。

 对于每组数据,第1 ⾏包括2 个整数,\(n\),\(m\),表示草药的数目和能用于采药的时间。

 接下来 \(n\) ⾏,每⾏两个整数 \(ti, vi\) 。

 保证\(m,ti,vi\) 在限制范围内均匀随机⽣成。

【输出格式】

 输出T ⾏,每⾏1 个数字,表示每组数据答案。

【样例输入】

herb.in herb.out
1 3
3 70
71 100
69 1
1 2

【数据规模与约定】

  • 对于30% 数据,\(1 <= n <= 20,1 <= m,vi,ti <= 10^4\)
  • 对于60% 数据,\(1 <= n <= 100, 1 <= m,vi,ti <= 10^5\)
  • 对于100% 数据,\(1 <= T <= 10,1 <= n <= 150,1 <= m,vi,ti<=10^9\)

 这个题目实际上是对NOIP普及组2015D1T1-洛谷【P1048】采药的改编。

 对于60%的数据很显然就是一个简单的0/1背包问题,直接推出递推式:

​ $$ f[ j ] = f[ j - v[ i ] ]+w[ i ] $$

 关键就是对于100%的数据,直接DP时间空间都不允许,10^9的范围下,\(O(nm)\)的算法无能为力。

 那么怎么处理呢?对于暴力可以DP,正解数据范围在\(10^9\)范围的题目,最常见的操作是搞一个矩阵出来。但是仔细观察会发现,很显然这个题不是用来搞矩阵的啊QWQ,根本构造不了好伐?

 注意到n和m范围差距悬殊之后,我们就意识到,这个题目可能可以搜索跑过去。考场上虽然想到了,但是一方面不擅长剪枝,另一方面总感觉复杂度不对,所以也就没敢乱搞。

 然而遗憾的是正解就是搜索+剪枝......这个题对剪枝的技巧要求还是比较高的。在写出来这个题以后,我感觉又回到了写【小木棍-数据加强版】的时候QWQ

  • 大块在前小块在后,先选大块再选小块,先排序再讲
  • 如果当前选用的体积情况已经不足以再添加哪怕最小的物品,就退出
  • 如果当前获得价值加上后面所有物品的价值也达不到原答案,就退出
  • 如果后面每一个物品都可以选上,就全选走人。(防止无效的抉择)

 然后就过了。。就过了。。过了。。。。

 搜索的复杂度果然是\(O(玄学)\)QWQ

 Talk is easy,show me the code.

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 160
#define int long long
using namespace std; int T,n,m,ans,sumv[MAXN],sumw[MAXN];
struct OBJ{
int v,w;
bool operator<(const OBJ &rhs)const{
return v>rhs.v;
}
}obj[MAXN]; void dfs(int pos,int use,int val){
ans=max(ans,val);
if(pos>n)return;//at the edge
if(use+obj[n].v>m)return; //cannot choose more;
if(val+sumw[pos]<=ans)return;//if val is not enough
if(use+sumv[pos]<=m){
ans=max(ans,val+sumw[pos]);
return;//one for all
}//if all can use
if(use+obj[pos].v<=m){
dfs(pos+1,use+obj[pos].v,val+obj[pos].w);
}//can choose
dfs(pos+1,use,val);
}
signed main(){
freopen("herb.in","r",stdin);
freopen("herb.out","w",stdout);
scanf("%lld",&T);
while(T--){
ans=0;
scanf("%lld%lld",&n,&m);
for(register int i=1;i<=n;++i){
scanf("%lld%lld",&obj[i].v,&obj[i].w);
}
sort(obj+1,obj+1+n);
for(register int i=n;i>=1;--i){
sumv[i]=sumv[i+1]+obj[i].v;
sumw[i]=sumw[i+1]+obj[i].w;
}
dfs(1,0,0);
printf("%lld\n",ans);
}
return 0;
}

Task 2:小奇的数列

【题目背景】

 小奇总在数学课上思考奇怪的问题。

【问题描述】

 给定⼀个长度为n 的数列,小奇定义,若⼀个区间\(,,[L,R](1 <= L,R <= n)\)满⾜:

 存在⼀个\(k(L <= k <= R)\), 使得对于任意的\(i(L <= i <= R)\),\(ai\) 能被\(ak\) 整除

 则称样的区间为可约的,其价值为\(R <= L\)。

 小奇想知道数列中所有可约区间的最⼤价值\(x\),以及价值为\(x\) 的可约区间个数\(num\),以及它们的左端点。

【输入格式】

 输⼊⽂件名为\(sequence.in\)

 第1 ⾏1 个整数\(n\)。

 第2 ⾏n 个整数,代表\(ai\)

【输出格式】

 输出⽂件名为\(sequence.out\)

 第1 ⾏2 个整数,\(num\) 和\(x\)。

 第2 ⾏\(num\) 个整数,从小到⼤输出所有价值为x 的区间的左端点L。

sequence.in sequence.out
5 1 3
4 6 9 3 6 2
sequence.in sequence.out
5 5 0
2 3 5 7 11 1 2 3 4 5

【数据规模与约定】

  • 对于30% 的数据,\(1 <= n <= 30; 1 <= ai <= 32\)
  • 对于60% 的数据,\(1 <= n <= 3000; 1 <=ai <= 2^{10}\)
  • 对于80% 的数据,\(1 <= n <= 300000; 1 <= ai <= 2^{20}\)
  • 对于100% 的数据,\(1 <= n <= 500000; 1 <= ai < 2^{31}\)

 暴力思路并不难想,直接枚举所有情况即可,有n3到n2几种不同的暴力。

 想要想到正解需要明白一个关键问题:

gcd和最小值类似,具有传递性。

 明白这一点,就会很容易想到可以用st表维护区间最小值和区间gcd,只要二者相等,该区间就符合条件。

 同时我们这里进行一个二分答案的优化,使复杂度优秀到可以随便水过这个题。

 数据量较大,建议写快读,复杂度O(nlogn)。

 思维难度并不大,但是区间求解gcd的方法确实很重要。

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 500010
using namespace std;
int n,arr[MAXN],st_min[MAXN][35],st_gcd[MAXN][35];
inline int read(){
int s=0;
char ch=getchar();
while('9'<ch||ch<'0'){
ch=getchar();
}
while('0'<=ch&&ch<='9'){
s=s*10+ch-'0';
ch=getchar();
}
return s;
}
inline int min(int x,int y){
return x<y?x:y;
}
int gcd(int x,int y){
return y?gcd(y,x%y):x;
}
inline bool can_use(int x){
//长度为x的区间有可用的吗?
int maxn=log2(x);
int maxl=n-(1<<maxn)+1;
for(register int i=1;i<=maxl;++i){
int _min=min(st_min[i][maxn],st_min[i+x-(1<<maxn)][maxn]);
int _gcd=gcd(st_gcd[i][maxn],st_gcd[i+x-(1<<maxn)][maxn]);
if(_min==_gcd){
// printf("len %d is ok\n",x);
// printf("sequence is [%d,%d] gcd=%d min=%d \n",i,i+x-1,_gcd,_min);
return true;
}
}
return false;
}
inline int get_ans(int x){
//长度为x的区间有可用的吗?
int cnt=0;
int maxn=log2(x);
int maxl=n-(1<<maxn)+1;
for(register int i=1;i<=maxl;++i){
int _min=min(st_min[i][maxn],st_min[i+x-(1<<maxn)][maxn]);
int _gcd=gcd(st_gcd[i][maxn],st_gcd[i+x-(1<<maxn)][maxn]);
if(_min==_gcd){
// printf("len %d is ok\n",x);
// printf("sequence is [%d,%d] gcd=%d min=%d \n",i,i+x-1,_gcd,_min);
cnt++;
}
}
return cnt;
}
inline void output(int x){
//长度为x的区间有可用的吗?
int maxn=log2(x);
int maxl=n-(1<<maxn)+1;
for(register int i=1;i<=maxl;++i){
int _min=min(st_min[i][maxn],st_min[i+x-(1<<maxn)][maxn]);
int _gcd=gcd(st_gcd[i][maxn],st_gcd[i+x-(1<<maxn)][maxn]);
if(_min==_gcd){
// printf("len %d is ok\n",x);
// printf("sequence is [%d,%d] gcd=%d min=%d \n",i,i+x-1,_gcd,_min);
printf("%d ",i);
}
}
printf("\n");
}
int main(){
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
n=read();
for(register int i=1;i<=n;++i){
arr[i]=read();
st_min[i][0]=arr[i];
st_gcd[i][0]=arr[i];
}
int maxn=log2(n);
for(register int i=1;i<=maxn;++i){
int maxl=n-(1<<i)+1;
for(register int j=1;j<=maxl;++j){
st_min[j][i]=min(st_min[j][i-1],st_min[j+(1<<(i-1))][i-1]);
st_gcd[j][i]=gcd(st_gcd[j][i-1],st_gcd[j+(1<<(i-1))][i-1]);
//区间最小值和区间gcd都具有传递性,可以用st表,线段树维护
}
}
//st表预处理区间最小值和区间gcd
int l=0,r=n;
while(r>l+1){
int mid=(l+r)>>1;
if(can_use(mid)){
l=mid;
}else{
r=mid-1;
}
}
int ans_len=can_use(r)?r-1:l-1;
int ans_num=get_ans(ans_len+1);
printf("%d %d\n",ans_num,ans_len);
output(ans_len+1);
return 0;
// printf("ans=%d\n",ans_len);
}

Task 3:切蛋糕

【问题描述】

 小奇买了⼀块⽣日蛋糕,这是⼀块矩形蛋糕,它由\(N * M\) 个小蛋糕组成,每个蛋糕的美味指数为\(T[ i ][ j ]\)。

 为了把蛋糕分给众⼈,小奇决定横着切\(A-1\) ⼑,再把得到的A 块各竖着切\(B-1\) ⼑,分成\(B\)块,这样⼀共有\(A - B\) 块。为了使⼤家都⾼兴,他希望让美味指数之和最少的那个蛋糕的美味指数最⼤。请你告诉他这个值吧。注意,你不能把小蛋糕切碎。

【输入格式】

 输⼊第⼀⾏四个数\(,,,N,M,A,B\)

 接下来\(N\)⾏,每⾏\(M\)个整数。

【输出格式】

 输出⼀⾏,表示最小值的最⼤值。

champion.in champion.out
5 4 4 2 3
1 2 2 1
3 1 1 1
2 0 1 3
1 1 1 1
1 1 1 1

【数据规模与约定】

  • 对于30% 的数据,有\(A=B=2\)
  • 对于60% 的数据,有\(A=2\)
  • 对于100% 的数据,有\(,1 <= N,M <= 500; 0 <= T[ i ][ j ] <= 4000; 1 <= A <= N; 1 <= B <= M\)。

 最小值最大,很显然二分最小值。

 考虑二分如何判断该值能否满足条件:

  • 先考虑一维的玩法:直接一个一个往前贪,如果可以就累加分割次数,分割次数够了true。
  • 二维同理,先控制行的变量,搞出来可以产生大于等于此答案的最小的行距。
  • 累加行维度上的分割次数,次数足够就true。
  • 注意维护二维前缀和。

 难度一般。code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 510
using namespace std;
int n,m,a,b,s,mp[MAXN][MAXN],sum[MAXN][MAXN];
inline bool can_use(int k){
//值x是否可用?
// printf("div_num=%d\n",k);
int x_bg=0,x_cnt=0;//行列的始末
for(register int i=1;i<=n;++i){
int y_bg=0,y_cnt=0;
for(register int j=1;j<=m;++j){
int val=sum[i][j]-sum[i][y_bg]-sum[x_bg][j]+sum[x_bg][y_bg];
//当前方块的大小
if(val>=k){
// printf("div in [%d,%d]\n",i,j);
y_bg=j;
y_cnt++;
//计数,划分
}
}
if(y_cnt>=b){
// printf("y is dived. div in [%d,%d]]\n",x_bg,i);
x_bg=i;
x_cnt++;
}
}
// printf("k=%d x_d/iv=%d\n",k,x_cnt);
if(x_cnt>=a){
// puts("is ok\n");
return true;
}else{
// puts("No\n");
return false;
}
}
int main(){
freopen("champion.in","r",stdin);
freopen("champion.out","w",stdout);
scanf("%d%d%d%d",&n,&m,&a,&b);
for(register int i=1;i<=n;++i){
for(register int j=1;j<=m;++j){
scanf("%d",&mp[i][j]);
sum[i][j]=mp[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
}
}
// for(register int i=1;i<=n;++i){
// for(register int j=1;j<=m;++j){
// printf("%2d ",sum[i][j]);
// }
// printf("\n");
// }
int l=0,r=sum[n][m];
while(r>l+1){
int mid=(l+r)>>1;
// printf("l=%d r=%d \n",l,r);
if(can_use(mid)){
l=mid;
}else{
r=mid-1;
}
}
int ans=can_use(r)?r:l;
printf("%d ",ans);
return 0;
}
上一篇:poj1830:开关问题


下一篇:《操作系统_FCFS和SJF》