首页 > 其他分享 >P5503 灯塔 题解

P5503 灯塔 题解

时间:2023-10-02 17:45:27浏览次数:42  
标签:ch int 题解 P5503 pos 决策 ans 灯塔 define

决策单调性二分

传送门

数据加强版:P3515

前置知识:二分,决策单调性


首先很容易写出答案式子:

\[ ans_{i}=\max_{j=i}^{n}{(a_{j}-a_{i}+\lceil \sqrt{\left| i-j \right |} \rceil)} \]

先将向上取整符号拆掉,只要在输出时处理就行。

再将绝对值符号拆掉,分 \(j<i\) 和 \(j>i\) 的情况考虑,至于 \(i=j\) 的情况,将 \(ans_{i}\) 初始化为 \(0\) 就行。

我们只考虑 \(j<i\) 的情况,另一种情况将数组反过来跑一遍取最大值就行。

设关于 \(i\) 的函数 \(f_{j}{(i)}=a_{j}+\sqrt{i-j}\),对于不同的 \(j\),函数图像随 \(i\) 的变化大概是这样的:

我们来分析一下这张图:图中曲线即 \(f_{j}{(i)}\) 的函数图像,是上凸包,函数的 \(j\) 就是最低点对应的 \(i\)。对于 \(ans_{i}\),最优决策点是函数图像与直线 \(x=i\) 的最高交点。

设 \(pos_{i}\) 为 \(ans_{i}\) 的最优决策点对应的 \(j\),可以发现:

对于 \(\forall i'<i\),有 \(pos_{i'}\le pos_{i}\)。

对于 \(\forall i'>i\),有 \(pos_{i'}\ge pos_{i}\)。

然后就可以整体二分来解决了!对 \(i\) 的区间关于中点 \(mid\) 二分,对 \(j\) 的区间关于当前 \(ans_{mid}\) 的最优决策点二分,注意找最优决策点时还要满足 \(j<i\)。


\(\mathcal{Code}\):

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define db double
#define il inline
#define re register
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define F(i,a,b) for(re int (i)=(a);(i)<=(b);(i)++)
#define DF(i,a,b) for(re int (i)=(a);(i)>=(b);(i)--)
#define G(i,u) for(re int (i)=head[u];(i);(i)=nxt[(i)])
inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}return x*f;}
const int N=100010;
int n;
int a[N];
db ans[N];
il db clac(int i,int j)
{//为了满足决策单调性,保证正确性,计算不能取整 
	return a[j]-a[i]+sqrt(i-j);
}//函数图像是一个个凸包,最优凸包不断向右上方延申,满足决策单调性
il void solve(int li,int ri,int lj,int rj)
{
	if(li>ri) return ;
	int i=(li+ri)>>1,pos=lj;
	F(j,lj,min(i,rj)) if(clac(i,pos)<clac(i,j)) pos=j;
	ans[i]=max(ans[i],clac(i,pos));//取j<i和j>i的最优解
	solve(li,i-1,lj,pos);//满足i-1的决策最优点在i的决策最优点pos的左边
	solve(i+1,ri,pos,rj);//满足i+1的决策最优点在i的决策最优点pos的右边
}
int main()
{
	n=read();
	F(i,1,n) a[i]=read();
	solve(1,n,1,n);//j<i的情况
	reverse(a+1,a+n+1);
	reverse(ans+1,ans+n+1);
	solve(1,n,1,n);//j>i的情况
	reverse(a+1,a+n+1);
	reverse(ans+1,ans+n+1);
	F(i,1,n) printf("%d\n",(int)(ceil(ans[i])));
	return 0;
}

标签:ch,int,题解,P5503,pos,决策,ans,灯塔,define
From: https://www.cnblogs.com/MooSheng/p/17740263.html

相关文章

  • 题解 Codeforces Round 901 (Div. 1) / CF1874A~E
    题解CodeforcesRound901(Div.1)/CF1874A~E比赛情况:过了AB。赛后发现B是假复杂度。https://codeforc.es/contest/1874A.JellyfishandGameProblemAlice&Bob又在博弈,Alice手上有\(n\)个苹果,第\(i\)个苹果的价值是\(a_i\);Bob手上有\(m\)个苹果,第\(i\)......
  • [题解]AT_abc240_f [ABC240F] Sum Sum Max
    思路题目要求的是\(\max_{a=1}^{n}\{\sum_{i=1}^{a}\sum_{j=1}^{a}{A_j}\}\),所以我们将\(\sum_{i=1}^{a}\sum_{j=1}^{a}{A_j}\)化简一下,得:\[i\timesA_1+(i-1)\timesA_2+\dots+1\timesA_x\]在\(a\)每增加\(1\)时,这个和\(s\)将会变为\(s+......
  • [题解]AT_abc245_f [ABC245F] Endless Walk
    思路首先我们可以发现,在任意一个节点数量大于\(1\)的强连通分量中的点都满足条件。所以,我们可以对这张图跑一边TarJan。但是这样是错的,因为我们还需要考虑节点数量为\(1\)的强连通分量。如果这种连通分量能够到达任意一个节点数量大于\(1\)的强连通分量,那么,这个连通分......
  • CSES.1141 C++题解
    题意传送门有一个长度为\(n\)的歌单,问最长多少首歌互不相同?每首歌用一个\(1-10^9\)的整数表示。样例输入812132742样例输出5算法双指针算法。桶思想。对于歌单中重复出现的数,可以用桶来存储。定义两个指针i,j,i指向大数,j指向小数。当出现某个桶的数大于1时,则......
  • CF1878C Vasilije in Cacak 题解
    题目传送门简化题意有\(t\)组询问,每次询问是否能从\(1\simn\)中选择\(k\)个数使得它们的和为\(x\)。解法考虑临界情况,从\(1\simn\)中选择最小的\(k\)个数时和为\(\sum\limits_{i=1}^ki=\dfrac{(k+1)k}{2}\),从\(1\simn\)中选择最大的\(k\)个数时和为\(......
  • Codeforces 1765H 题解
    题目大意题目大意给定一个\(n\)个点和\(m\)条边的有向图,并给定\(p_1,p_2,\cdots,p_n\)表示第\(i\)个点的拓扑序必须小于等于\(p_i\),求出每个点的最小拓扑序。题解题解题目要求拓扑序尽量小,转换一下就是在反图上拓扑序尽量大。考虑拓扑排序,当一个点不得不入队......
  • UVA10054 The Necklace 题解
    好可恶一道题,怎么没人告诉我输出之间有空行(思路是先抽象成图,然后跑一边dfs记录边的前后顺序。对于不能成环的情况,只需要再开个数组记录度数判断奇点即可。若存在奇点则break掉,剩下的跑dfs、//producedbymiya555//stupidmistakes:1.多测要清空2.输出之间有空行//ideas:d......
  • 题解 hdu 1269 迷宫城堡
    找点图论练习题写,发现hdu又寄了,那就发到blog里吧。思路:tarjan缩点判断DAG中点数是否为1。若是,则该图为强连通图。 //producedbymiya555//stupidmistakes:多测记得清空//ideas:tarjan模板#include<bits/stdc++.h>usingnamespacestd;constintN=10010;intn,m,low[......
  • 题解 小 a 和 uim 之大逃离
    题目链接首先可以想到设状态\(k_1,k_2\)表示小\(a\)和小\(uim\)分别表示他们目前取得的得分,那么最终的答案便是\(k_1=k_2\)的时候。但是这样设置状态的复杂度无疑是高的。并且十分浪费,所以考虑设\(z\)表示\(k_1-k_2\)的值。那么\(z=0\)就是答案。接着考虑如何处......
  • SP9494 ZSUM - Just Add It 题解
    题目传送门前置知识快速幂解法推式子:\(\begin{aligned}Z_n+Z_{n-1}-2Z_{n-2}&=(Z_n-Z_{n-2})+(Z_{n-1}-Z_{n-2})\\&=(S_n+Q_n-S_{n-2}-Q_{n-2})+(S_{n-1}+Q_{n-1}-S_{n-2}-Q_{n-2})\\&=((n-1)^k+n^k+(n-1)^{n-1}+n^n)+((n-1)^k+(n-1)^{n-1})\\&=n^n+n^k+......