首页 > 其他分享 >P5308 [COCI2018-2019#4] Akvizna

P5308 [COCI2018-2019#4] Akvizna

时间:2024-11-05 15:21:35浏览次数:1  
标签:ch int mid long P5308 hh Akvizna 2019 define

原题链接

奶龙题,主要是凸性的证明,然后 wqs 二分求解即可。

轮数的选择是 \(1\) ~ \(n\),假如是 \(1\) 轮,答案显然为 \(1\),为 \(n\) 轮,答案就是 \(\sum_{i=1}^{n}i^{-1}\),从这里就可以直接猜出凸性了。

然后是不考虑轮数限制的求法,直接 dp 即可:\(f_{i}=\max\{f_j+\frac{i-j}{i}\}\),再减去个二分的 \(mid\)。

式子显然能够斜率优化,这个题就做完了。

注意精度,保险起见开long double

#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define ll long long
#define ld long double
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define ROF(i,j,k) for(int i=j;i>=k;i--)
int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return x*f;
}
const int N=1e5+10;
const ld eps=1e-12;
int n,k,g[N],q[N];ld f[N];
ld Y(int a){return f[a];}
ld X(int a){return (ld)a;}
ld slope(int a,int b){return (ld)(Y(a)-Y(b))/(X(a)-X(b));}
int calc(ld mid){
	int hh=1,tt=1;q[1]=0;
	memset(g,0,sizeof(g));
	FOR(i,1,n){
		while(hh<tt&&slope(q[hh],q[hh+1])-1.0/i>eps) hh++;
		f[i]=f[q[hh]]+(ld)(i-q[hh])/i-mid;
		g[i]=g[q[hh]]+1;
		while(hh<tt&&slope(q[tt],q[tt-1])-slope(q[tt],i)<eps) tt--;
		q[++tt]=i;
	}
	return g[n];
}
int main(){
	n=rd,k=rd;
	ld l=0,r=10000000;
	while(r-l>eps){
		ld mid=(l+r)/2.0;
		if(calc(mid)>=k) l=mid;
		else r=mid;
	}
	calc(l);
	double ans=f[n]+l*k;
	printf("%.9lf\n",ans);
	return 0;
}

标签:ch,int,mid,long,P5308,hh,Akvizna,2019,define
From: https://www.cnblogs.com/summ1t/p/18528086

相关文章

  • JOI Open 2019 Triple Jump 题解
    原题链接可以暴力枚举\(a,b\),然后\(c\in[2b-a,n]\),找区间最大值即可。对于我们选择的\(a,b\)间,若能在\((a,b)\)中找到某个下标\(i\),满足\(h_i\geh_a\)或\(h_i\geh_b\),那么选择\(i\)是更优的。理由很简单,无论是从\(a\toi\)还是从\(b\toi\),都会扩大\(c\)的......
  • [RoarCTF 2019]Easy Calc
    题目链接:https://buuoj.cn/challenges#[RoarCTF2019]EasyCalc打开环境后如下所示。查看该页面的源代码,发现存在"calc.php"文件,同时,提示设置了WAF。访问"calc.php"文件,发现该页面打印出了PHP源码。即。<?phperror_reporting(0);if(!isset($_GET['num'])){s......
  • [极客大挑战 2019]BuyFlag
    题目链接:https://buuoj.cn/challenges#[极客大挑战2019]BuyFlag打开环境后如下所示。发现右侧中存在一个菜单,并有"PAYFLAG"选项卡,访问其后,响应包如下。HTTP/1.1200OKServer:openrestyDate:Fri,25Oct202415:00:41GMTContent-Type:text/html;charset=UTF-8Con......
  • [ZJCTF 2019]NiZhuanSiWei
    题目链接:https://buuoj.cn/challenges#[ZJCTF2019]NiZhuanSiWei打开环境后如下所示。<?php$text=$_GET["text"];$file=$_GET["file"];$password=$_GET["password"];if(isset($text)&&(file_get_contents($text,'r')===......
  • [极客大挑战 2019]PHP
    题目链接:https://buuoj.cn/challenges#[极客大挑战2019]PHP打开环境后如下所示。题目提示"有一个良好的备份网站的习惯",因此,尝试爆破一下可能的备份文件名(如:backup.zip、www.zip等)。发现该网站的备份文件名为"www.zip",下载后,主要有"index.php"与"class.php"两个源码文......
  • [极客大挑战 2019]BabySQL
    题目链接:https://buuoj.cn/challenges#[极客大挑战2019]BabySQL打开环境后如下所示。尝试以下几种方法的万能密码:不加单引号。加单引号。加双引号。发现加入了单引号后,有SQL错误提示,但是可以发现,题目似乎过滤了用户输入的"or"。接下来,尝试双写绕过。发现可以成......
  • [SUCTF 2019]EasySQL
    题目链接:https://buuoj.cn/challenges#[SUCTF2019]EasySQL打开环境后,如下所示。尝试输入字符:1。尝试输入字符:0后,发现没有输出结果。尝试输入字符串"aaa"、"bbb"等后,发现都跟输入0的结果一致,而输入123、456等非0的内容,都与输入1一致,这里可以猜测(实际上需要比较......
  • [强网杯 2019]随便注
    题目链接:https://buuoj.cn/challenges#[强网杯2019]随便注打开环境后,如下所示。通过输入',确认该处是由单引号闭合。通过输入Payload:'unionselect1;#,可以发现后端对一些关键词进行了过滤。尝试堆叠注入,可以查询到数据库名以及当前使用的数据库中存在的表名。Payload:'%......
  • [极客大挑战 2019]LoveSQL
    题目链接:https://buuoj.cn/challenges#[极客大挑战2019]LoveSQL。打开环境后,如下所示。尝试SQL注入(万能密码)。Payload:admin'+or+1%3d1%3b%23。(笔者通过简单粗暴的尝试:①没有使用单引号;②使用单引号;③使用双引号,来确定后端拼接的SQL语句中的password参数系使用单引号......
  • [极客大挑战 2019]Secret File
    题目链接:https://buuoj.cn/challenges#[极客大挑战2019]SecretFile。打开环境后如下所示。通过BurpSuite抓包后,发现页面源代码如下。<!DOCTYPEhtml><html><styletype="text/css">#master{position:absolute;left:44%;bottom:0;text-align:c......