Contest1592 - 2018-2019赛季多校联合新生训练赛第二场(部分题解)

时间:2022-04-13 20:14:12

Contest1592 - 2018-2019赛季多校联合新生训练赛第二场

D 10248 修建高楼(模拟优化)

H 10252 组装玩具(贪心+二分)

D 传送门

题干

题目描述
C 市有一条东西走向的“市河”。C 市的市长打算在“市河”的其中一条岸边自东往西的 n 个位置(可以将这 n 个位置看成在一条直线上,且位置不会重叠)依次建造高楼。
C 市的设计部门设计了 T 个方案供市长挑选(方案编号为 到 T)。每个方案都提供了建造的每幢高楼的高度,自东向西依次为 h1,h2,h3,…,hn-,hn。每幢楼房的高度在 到 n 之间(包括 和 n),且各不相同。
市长在挑选设计方案时,喜欢 n 幢高楼中任意 幢(包括不连续的 幢)有一定的“梯度美”。所谓“梯度美”是指这 幢高楼满足:
第j幢的高度hj-第i幢的高度hi=第k幢的高度hk-第j幢的高度hj(≤i<j<k≤n)
市长喜欢方案中这种“梯度美”现象越多越好。请编程帮市长挑选一下设计方案吧。 输入
T+ 行。
第一行两个整数 T 和 n,分别表示设计部门提供的方案总数和打算建造的高楼数。
接下来每一行表示一种方案。第 i+ 行表示第 i 种方案,每行 n 个整数,依次表示每幢高楼打算建造的高度。 输出
输出共 行。
包含两个整数,第一整数为出现“梯度美”次数最多的方案,第二个整数为对应方案“梯度美”出现的次数。如果出现“梯度美”次数最多的方案有多个,输出方案编号较小的方案。 样例输入 样例输出 提示
输入*有2个方案,打算建造5幢高楼。
第一个方案每幢高楼高度依次为3,,,,,其中第1幢,第4幢和第5幢高度出现“梯度美”(,,),这3幢高楼的后一幢比前一幢依次高1。
第二个方案每幢高楼高度依次为3,,,,,没有出现“梯度美”。
(≤T≤,且 ≤n≤)

题解:

  考察知识点:模拟优化

    这道题,昨天下午考完试一直在看,看了好久好久,一直在找nlogn复杂度的算法(为什么要找nlogn复杂度的算法呢?因为我感觉,如果t=50,n=2000,那么

    就有1e6个楼房,而1e5的数据范围需要nlogn的时间复杂度,然后,就一直找不到在哪可以logn,呜呜呜~~~~)

    实属无奈,然后,就找老师要了一份标程,标程如下:

 #include<stdio.h>
#include<string.h>
int main()
{
int t,n,a[],ans=-,ans1=,b[]= {},c;
scanf("%d%d",&t,&n);
for(int q=; q<t; q++)
{
memset(b,,sizeof(b));
c=;
for(int i=; i<n; i++)
{
scanf("%d",&a[i]);
b[a[i]+]=i;
}
for(int i=;i<n-;i++)
for(int j=i;j<n-;j++)
if(b[*a[j]-a[i]+]>j)
c++;
if(c>ans)
ans1=q,ans=c;
}
printf("%d %d",ans1+,ans);
return ;
}

    照着标程理解了一下,具体做法是枚举i,j楼的高度,判断是否存在满足条件的k楼,是个O(n^2)的复杂度,很纳闷,这怎么能过呢?????

  其实,在找老师要标程前,在ACM的群里问了一下,一个初三大佬,五分钟敲出的这道题,一发AC,这,这也太厉害了吧%%%%%%%

  Contest1592 - 2018-2019赛季多校联合新生训练赛第二场(部分题解)差距太大了

  之所以要他写代码,是因为,标程里将memset()放到了循环内,然后,他说,将memset()放循环里很不好,有时候会因此而超时,然后,没有然后了。。。

  巨巨代码:

 #include <cstdio>
using namespace std; int hi[];
int pos[]; int main()
{
int t,n;
scanf("%d%d",&t,&n); int ans = ;
int ansp = ;
for(int l=; l<=t; ++l)
{
for(int i=; i<=n; ++i)
scanf("%d",hi+i); for(int i=; i<=n; ++i)
pos[hi[i]<<] = i; int curans = ;
for(int i=;i <= n-;++i)
for(int j=i+;j <= n;++j)
if(i<pos[hi[i]+hi[j]] && pos[hi[i]+hi[j]]<j)
++curans; if(curans>ans)
{
ans = curans;
ansp = l;
}
}
printf("%d %d\n",ansp,ans); return ;
}

  具体思路是,枚举i,k,判断有没有满足条件的 j 。

  偷偷把他的代码改成我的风格,哈哈哈

AC代码:

 #include<iostream>
#include<cstdio>
using namespace std;
const int maxn=+; int t,n;
int h[maxn];
int pos[*maxn]; int Solve()
{
for(int i=;i <= n;++i)
pos[h[i]<<]=i;//2*h[j]的位置
int res=;
for(int i=;i <= n-;i++)
for(int k=i+;k <= n;++k)
if(pos[h[i]+h[k]] > i && pos[h[i]+h[k]] < k)//判断(i,k)之间有没有h[i]+h[k]
res++;
return res;
}
int main()
{
scanf("%d%d",&t,&n);
int resTot=,resPos=;
for(int kase=;kase <= t;++kase)
{
for(int i=;i <= n;++i)
scanf("%d",h+i);
int res=Solve();
if(resTot < res)
resTot=res,resPos=kase;
}
printf("%d %d\n",resPos,resTot); return ;
}

H 传送门

题干:

题目描述
小华打算用 n 种(编号为 到 n)材料组装玩具。其中第 i 种材料的数量为 Xi 个。组装一个玩具需要第 i 种材料 Yi 个。小华另外有 m 个万能材料,每个万能材料可以作为 n 种材料中的任意一个材料使用。
请编程计算小华最多可以组装多少个玩具? 输入
输入共3行。
第1行两个整数n和m,分别表示小华有n种材料和m个万能材料。
第2行n个正整数,其中第i个整数Xi表示小华第i种材料有Xi个。
第3行n个正整数,其中第i个整数Yi表示小华组装一个玩具需要第i种材料Yi个。 输出
输出共 行。
一个整数,表示小华最多可以组装多少个玩具。 样例输入 样例输出 提示
输入中小华只有1个编号为1的材料,另外还有1个万能材料。组装一个玩具需要编号为1的材料1个。所以可以用1个编号为1的材料和1个万能材料分别组装1个玩具,共可以组装2个玩具。 输入数据保证1≤n≤, ≤m≤^,≤Xi, Yi≤^。

题解:

  考察知识点:贪心

  相关变量解释:

 struct Node
{
int x,y;
int tot;//tot=x/y : 第i种材料可以贡献tot个玩具
}toy[maxn];

  贪心思路:

    (1) : 首先,按照tot从小到大排序,明确一点,影响答案的是最小的 tot ,所以,我们要把 m 尽可能多的用在 tot 小的材料上。

    (2) : 从1开始往后遍历,查找和toy[1].tot相等的材料,判断 m 是否可以使其 +1,如果可以,toy[ i ].tot++(对于所有的满足toy[ i ].tot == toy[1].tot的 i 均更新),并更新 m ;

    (3) : 重复(2)过程,直到toy[1].tot == toy[n].tot。

    (4) : 输出 toy[1].tot + (剩余的m可以增加的toy[i].tot)。

  好了,思路有了,那就开始码程序吧.............

  码好了,交一发,wa,改改,再交,还是wa,接着改,接着wa.....................

  然后,找华师大的巨巨讨思路,巨巨说,二分..............

Contest1592 - 2018-2019赛季多校联合新生训练赛第二场(部分题解)今晚码程序,加调试,历经两个小时,终于AC了,不容易啊!

  二分思路:

    在贪心的基础上,对 n 种材料进行二分( [1,n] ),判断所有 toy[ i ].tot 小于 toy[mid].tot 材料是否可以通过使用 m 使 toy[ i ].tot == toy[mid].tot;

    如果可以 l = mid,反之 r=mid,通过二分查找所有的材料可以到达的最大的tot(tot <= toy[n].tot,即不一定要把 m 全部用完)

  具体细节看代码:

AC代码:

 #include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
const int maxn=1e5+; int n,m;
struct Node
{
int x,y;
}toy[maxn]; bool cmp(Node _a,Node _b){
return _a.x/_a.y < _b.x/_b.y;
}
int Check(int curTot)
{
ll need=;//此处需要用long long
for(int i=;i <= n && toy[i].x/toy[i].y <= curTot;++i)
{
//材料i组装成 curTot 个玩具需要的总材料为 curTot*toy[i].y
//再减去初始含有的材料 toy[i].x
need += 1ll*curTot*toy[i].y-toy[i].x;//如果 curTot > 2,toy[i].y == 1e9
if(need > m)
return -;
}
return need;
}
int Solve()
{
sort(toy+,toy+n+,cmp);
int l=,r=n+;
while(r-l > )//二分查找所有的材料可以到达的最大的tot
{
int mid=l+((r-l)>>);
int curTot=toy[mid].x/toy[mid].y; if(Check(curTot) != -)
l=mid;
else
r=mid;
}
int curTot=toy[l].x/toy[l].y;
ll need=Check(curTot+);//判断能否组装成curTot+1个玩具,作用是消除x的影响
if(need == -)
return curTot; m -= need;
need=;
for(int i=;i <= l;++i)
need += toy[i].y;//不必考虑x的影响,因为在curTot+1处已将x用完
return curTot++m/need;
}
int main()
{
// freopen("C:\\Users\\lenovo\\Desktop\\in.txt","r",stdin);
scanf("%d%d",&n,&m);
for(int i=;i <= n;++i)
scanf("%d",&toy[i].x);
for(int i=;i <= n;++i)
scanf("%d",&toy[i].y); printf("%d\n",Solve());
return ;
}