当前位置: 首页 > news >正文

NKOJ全TJ计划——NP11721

前言

我的做法也是成功的拿到了最优解,开一瓶可乐(其实只喝得起免费的学校饮用水)庆祝。顺便说一句,INTP男叫柯乐。但这显然并不是重点。
只是一个简单的小优化,大家可以看到,只有2行(显然不是章鱼的核聚变,不过用了以后可以直达RE-0ms,很强的)。
咳咳,扯远了。
言归正传:

题目内容

你有一个序列\(a_1, a_2, \dots, a_n\) 。 定义\(b_{l, r}\) 表示序列 \(\{a_i\} _ {l\leq i \leq r}\) 的中位数。
定义 \(c_{i,j}\) 为序列\(\{b_{i, j}\} _ {l\leq i \leq j \leq r}\) 的中位数。 求\(\{c_{i, j}\} _ {1\leq i \leq j \leq n}\) 的中位数是多少。
对于一个大小为\(m\) 的序列,我们定义它的中位数为第 \(\lceil(\frac{m}{2})\rceil\)小的数字。
\(n\leq 2000,a_i\leq10^9\)

思路

我们考虑求“中位数的中位数”,使用二分答案搭配树状数组求解。那这道题我们也可以使用二分答案。
类似的,当我们二分“中位数为\(x\)”时,我们把\(a\)\(< x\)的权值设为\(-1\),否则设为\(1\)
然后我们便可以求出\(f\)\(i\sim j\)\(\ge x\)的数较多,\(f_{i,j}=1\),否则为\(-1\)
随后我们便可以使用容斥,得到\(dp_{i,j}=f_{i,j}-dp_{i+1,j-1}+dp_{i+1,j}+dp_{i,j-1}\)
随后看看\(dp_{i,j}\)是否大于\(0\),累加\(1\ or\ -1\)后与\(\frac{n\times(n+1)}{4}\)比较大小。
然后就没有然后了。

代码

#include<bits/stdc++.h>
using namespace std;
#define N 2004
int t[N],n,m,i,j,a[N],s[N],p,f[N][N],dp[N][N],l,r,mid,ans,b[N];
int ch(int x){int p=0,k,t;for(int i=1;i<=n;i++){if(a[i]>=x) s[i]=s[i-1]+1;else s[i]=s[i-1]-1;}for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){if(s[j]-s[i-1]>0){f[i][j]=1;}else f[i][j]=-1;}}for(int i=n;i>=1;i--){for(j=i;j<=n;j++){dp[i][j]=f[i][j]+dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1];if(dp[i][j]>0){p++;}else p--;}}return p>0;
}
int main()
{cin>>n;for(i=1;i<=n;i++){scanf("%d",&a[i]);r=max(a[i],r);}l=1;while(l<=r){mid=(l+r)/2;if(ch(mid)){ans=mid;l=mid+1;}else{r=mid-1;}}cout<<ans;
}

以上便是可以通过这题的正确代码。

等一下,我知道你很想C,但你先别C。

思考题:以上的代码怎么修改,才能优化时间复杂度呢?

http://www.hskmm.com/?act=detail&tid=26320

相关文章:

  • 印度全球能力中心2030年展望与技术基建规划
  • NOI Linux 食用教程
  • 详细介绍:基于 Android 和 JBox2D 的简单小游戏
  • 基于深度学习的语音识别高效的系统设计与实现
  • CF2152H2 Victorious Coloring (Hard Version) 题解
  • 题解:P6162 [Cnoi2020] 四角链
  • 题解:P3301 [SDOI2013] 方程
  • # 20232321 2025-2026-1 《网络与系统攻防技术》实验一实验报告
  • 题解:CF1292E Rin and The Unknown Flower
  • 打印A3大小的PDF文件为A4幅面
  • 课程总结2
  • 解码查找算法与哈希表
  • 第二次课动手动脑合集
  • centos8的防火墙管理
  • 如何生成和制作PDF文件 - 实践
  • 1.2 马尔可夫决策过程(Markov Decision Process, MDP)
  • 博弈论dp复习笔记
  • 10.7阅读笔记
  • 如果你的微信支付界面出现“摇一摇”,说明你的隐私正在泄露
  • 多线程和网络总结
  • 8.RV1126-OPENCV 视频中添加LOGO - 指南
  • 学习记录:响应式系统、文件通知与游戏输入机制的异同
  • oppoR9m刷Linux系统: 制作 scatter.txt 和 导出手机preloader
  • 详细介绍:ASR技术(自动语音识别)深度解析
  • 1.1 采样问题 Sampling and Bandits
  • 10.7 NOIP 模拟赛 T2. 中心极限定理
  • 【题解】10.6 国庆中秋 提高组 热身赛
  • UCB-CS70_离散数学_个人笔记:至少和至多 - Zeeh
  • 几个重要的偏微分方程
  • 虚拟机器人学习自然语言指令技术解析