【2018.4.5】Shoi2017题集
2024-09-04 17:32:49
这三道题分别对应bzoj4868~4870,pdf没法往这放,因此放弃了。
T1:
方法1(正解):三分法
考虑暴力枚举最晚公布的时间x,关注到2操作是没有负面影响的1操作,所以如果A大于B,那么只需用2操作就可以了,否则先用1操作,不能用1操作后再用2操作。这样就能把b数组全部变成小于等于x,在加上额外的不愉快度就可以了。这个算法的时间复杂度是O(N2),可以拿60分。
如果你去打表就能发现不愉快度关于时间是一个下凸函数,可以用三分做。具体的证明是这样的:
1、修改代价关于时间是单调递减的,也就是说越晚出成绩修改代价越小;
2、额外代价关于时间是单调递增的,也就是说越晚出成绩额外代价越大;
3、最重要的一句,这两个函数的导数都是递增的。
感性的想一下,拿额外代价举例子,比如五个人的时间分别是1、2、2、3、3,时间从1改到2,需要额外代价的1个人(第一个人),但是从2改到3,需要额外代价的就变成了3个人,从3改到4所有的人都需要额外代价,也就是说刚开始额外代价增加慢,到后来额外代价增加快。
4、这样把这两个函数加起来,导数也是递增的,所以它是一个下凸函数(当然也有可能退化成单调函数)。
#include<cstdio>
#include<iostream>
#include<algorithm>
#define MN 100000
#define ll long long
using namespace std;
inline int read()
{
ll x = ; char ch = getchar();
while(ch < '' || ch > '') ch = getchar();
while(ch >= '' && ch <= ''){x = x * + ch - '';ch = getchar();}
return x;
} int n,m,t[MN+],s[MN+];
ll A,B,C,ans=1e18; ll calc(int tms)
{
ll sum=,left=,need=;
for(int i=;i<=n;++i) sum+=C*max(,tms-t[i]);
for(int i=;i<=m;++i)
if(s[i]>tms) need+=s[i]-tms;
else left+=tms-s[i];
if(B<A)return sum+need*B;
else if(left>=need) return sum+need*A;
else return sum+left*A+(need-left)*B;
} void Solve(int l,int r)
{
if(r-l<=)
{
for(int i=l;i<=r;++i) ans=min(ans,calc(i));
return;
}
int m1=(r-l+)/+l,m2=(r-l+)/*+l;
if(calc(m1)<calc(m2)) Solve(l,m2-);
else Solve(m1+,r);
} int main()
{
A=read();B=read();C=read();
n=read();m=read();int mx=;
for(int i=;i<=n;++i) mx=max(mx,(t[i]=read()));
for(int i=;i<=m;++i) mx=max(mx,(s[i]=read()));
Solve(,mx);
printf("%lld\n",ans);
return ;
}
T1-1
注意到有两个数据C=1016,如果考试现场写的时候怕爆炸,可以特判一下用足够的1、2操作让每个学生都不等待,因为这种情况只要有一个学生等待答案就不是最优。
三分法的时间复杂度……根据 T(n)=T(2n/3)+O(n) 可以知道复杂度大概是O(2n log3 n),比O(n log2 n)(二分)慢了不少,但好歹也是log级别的。
方法2:枚举DDL
直接枚举Deadline(最晚成绩公布时间),时间复杂度O(n)......
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#define MAXN 100005
#define INF 1e16
typedef long long LL;
using namespace std;
int n,m,a,b,c;
LL student[MAXN],course[MAXN];
int read()
{
int x=;char c=getchar();
while(c<''||c>'')c=getchar();
while(c>=''&&c<='')x=x*+c-'',c=getchar();
return x;
}
int main()
{
a=read(),b=read(),c=read(),n=read(),m=read();
int day=;LL cost=,mov=,left=,ans;
for(int i=;i<=n;i++)
{int t;t=read();student[t]++;day=max(day,t);}
for(int i=;i<=m;i++)
{int t;t=read();course[t]++;day=max(day,t);}
for(int i=;i<=day;i++)
{
cost+=student[i]*(day-i);
left+=course[i]*(day-i);
student[i]+=student[i-];//维护前缀和
course[i]+=course[i-];
}
ans=cost*c;
for(int i=day-;i>;i--)
{
mov+=(m-course[i]);//在这天后完结的课需要向前移动一天
left-=course[i];//前面的所有课程向后移动的范围减少了1天
cost-=student[i];//减掉希望在这天以前完结的学生一天的不满意度
if(c>=INF&&cost)continue;
LL p=left>?left:;
if(mov<p)p=mov;
if(a<b)ans=min(ans,p*a+(mov-p)*b+cost*c);
else ans=min(ans,mov*b+cost*c);
}
printf("%lld\n",ans);
return ;
}
T1-2
T2:
数学题ToT,和bzoj3884的坑爹程度有些相似。
最新文章
- RF Firefox Profile
- 调用0A中断输入字符串数据段的DUP定义
- DateUtil工具类
- VHDL的参数写在一个vhd文件里
- (转)关于URLDownloadToFile下载文件
- SharePoint 2013 本地开发解决方案以及远程调试
- Eclipse编译去除svn文件夹
- Angular.js 学习笔记
- OpenStack Nova 制作 Windows 镜像
- leetcode Database1(三)
- Oracle数据库程序包全局变量的应用
- [置顶] Linux下的截图小工具
- MVVM模式应用 之为ApplicationBarIconButton 添加Command操作属性
- iOS--导航栏样式
- QT:使用“状态模式”绘制界面
- 2014鞍山直播比赛H称号HDU5077(DFS修剪+通过计)
- 【android】WebView缓存数据收集
- windows和linux换行规则的区别
- UGUI动态更换精灵图片
- JVM概念以及常用设置
热门文章
- hadoop中修改端口号
- Caused by: java.lang.NoClassDefFoundError: com/sun/tools/javac/util/List at
- 远程文件拷贝(fastcopy为例)
- UVA 1661 Equation (后缀表达式,表达式树,模拟,实现)
- 图像处理框架 Core Image 介绍
- mysql dump 参数大全
- off-by-one&;doublefree. 看雪10月ctf2017 TSRC 第四题赛后学习
- ROP之linux_x64知识杂记
- hibernate的注解
- poi导出word模板项目实例(一个文件)