首页 > 其他分享 >10.10 总结

10.10 总结

时间:2024-10-11 09:10:41浏览次数:8  
标签:总结 minn Minn int ll kMaxN ST 10.10

T1 美丽的子区间

还行吧,根据大眼观察法 可以看出当 \(x\) 为使用科技的次数时,函数 \(f(x)\) 等于使用 \(x\) 次科技的最小答案是一个单谷函数,可以三分,注意到使用 \(x\) 次科技的时候的第 \(i\) 个数的答案是 \(\min \limits_{j=\min(1,i-x+1)}^{i}\)。而且还要加上一个小贪心:把最小的放在最前面。

#include <fstream>
#include <cstring>

using namespace std;
using ll = long long;

const int kMaxN = 1e5 + 1;

ifstream cin("collect.in");
ofstream cout("collect.out");

ll n, k, o[kMaxN], a[kMaxN], s[kMaxN];

struct ST {
  static const int kMaxN = 2e5 + 5;
  ll n, log2[kMaxN], Maxn[kMaxN][20], Minn[kMaxN][20];
  ST() {}
  ST(ll n, ll a[]) {
    memset(Minn, 0x3f, sizeof(Minn));
    for (int i = 1; i <= n; i++) {
      Minn[i][0] = Maxn[i][0] = a[i];
    }
    for (int i = 2; i <= n; i++) {
      log2[i] = log2[i / 2] + 1;
    }
    for (int j = 1; j < 20; j++) {
      for (int i = 1; i + (1 << j - 1) <= n; i++) {
        Maxn[i][j] = max(Maxn[i][j - 1], Maxn[i + (1 << j - 1)][j - 1]);
        Minn[i][j] = min(Minn[i][j - 1], Minn[i + (1 << j - 1)][j - 1]);
      }
    }
  }
  ll Max(int l, int r) {
    int len = r - l + 1;
    return max(Maxn[l][log2[len]], Maxn[r - (1 << log2[len]) + 1][log2[len]]);
  }
  ll Min(int l, int r) {
    int len = r - l + 1;
    return min(Minn[l][log2[len]], Minn[r - (1 << log2[len]) + 1][log2[len]]);
  }
} st;

ll F(ll x) {
  ll ans = x * k;
  for (int i = 1; i <= n; i++) {
    ll o = st.Min(max(1ll, i - x), i);
    ans += o;
  }
  return ans;
}

int main() {
  cin >> n >> k;
  ll minn = 1e9, pos;
  for (int i = 1; i <= n; i++) {
    cin >> o[i];
    if (minn > o[i]) {
      pos = i;
      minn = o[i];
    }
  }
  for (int i = pos; i <= n; i++) {
    a[i - pos + 1] = o[i];
  }
  for (int i = 1; i < pos; i++) {
    a[i + (n - pos + 1)] = o[i];
  }
  st = ST(n, a);
  ll l = 0, r = n - 1;
  while (l < r) {
    ll mid1 = l + (r - l) / 3, mid2 = r - (r - l) / 3;
    ll ans1 = F(mid1), ans2 = F(mid2);
    if (ans1 > ans2) {
      l = mid1 + 1;
    } else {
      r = mid2 - 1;
    }
  }
  ll ans = 1e18;
  for (int i = max(0ll, l - 2); i <= min(n, r + 2); i++) {
    ans = min(ans, F(i));
  }
  cout << ans << '\n';
  return 0;
}

标签:总结,minn,Minn,int,ll,kMaxN,ST,10.10
From: https://www.cnblogs.com/GenesisCrystal/p/18457704

相关文章

  • 剪映最新免VIP版,免费激活解锁所有VIP功能,打开即用!(2024.10.10)
    剪映免VIP版本https://pan.quark.cn/s/7a4affd0ef9b剪映是由字节跳动公司开发的一款全能易用的桌面端剪辑软件。这款软件最初是为满足手机用户的视频编辑需求而设计的,特别适合制作短视频和社交媒体内容。剪映的优势正是集中于「专业」、「创意」、「协同」三大功能上,可以......
  • 10.10日noip多校联考总结
    10.10日noip多校联考总结T1感觉就是个dij再多记录一个换乘次数然后就像普通dij一样跑就行了。但是必须得将换乘次数放进dis数组中当成一个状态记录下来,不能只记录在堆中,不然做法会假。T2发现m=0的部分分就是用一个数据结构维护区间最大子段和。m=1/2就是同时维护一个最大值......
  • 求 LCA 方法总结
    求LCA方法总结前言求LCA是十分基础的东西,但是方法众多。此篇介绍OI中常用的求法。倍增求LCA蒟蒻最先学的求LCA方法就是倍增求LCA。预处理和查询时间复杂度均为单\(\log\)。优点为好理解,比较简单,且便于处理路径数据。树剖LCA重链剖分。优点是预处理是线性复杂度,......
  • android11 开机动画黑屏优化(总结)
    一、开机向导引起的短暂黑屏在系统中默认是有开机向导的,首次开机会首选进入开机向导,然后进入锁屏桌面,如果某些原因引起开机向导卡顿,会造成短暂黑屏。可以修改如下:frameworks/base/packages/SettingsProvider/res/values/defaults.xmltruetrue再在产品mk中去掉这两个app:pac......
  • 10.10学习笔记
    事件概率1.事件事件是指在某个试验或观察中可能发生的结果或结果的集合。是样本空间的一个子集,可以包含一个或多个样本点,也可以是整个样本空间。事件用大写字母,如A,B,C等表示。1.1概念1.1.1基本事件基本事件是指试验中不可再分的最简单的事件。每个基本事件代表一个单一......
  • 今日总结
    今天了解了桶排序算法时间复杂度:平均时间复杂度:O(n+k),其中n是数据的数量,k是桶的数量。最坏时间复杂度:O(n^2),当所有数据都分配到同一个桶中时。空间复杂度:O(n+k),需要额外的空间来存储桶和数据。2.算法步骤初始化桶:根据数据的范围创建一定数量的桶。分配数......
  • 10.10 爆零赛(2023 炼石计划 NOIP 模拟赛 #2)
    炼石计划9月10日NOIP模拟赛#2【补题】-比赛-梦熊联盟(mna.wang)模拟赛恒等式:\(0+0+0+0=0\)。复盘T1好像可做。有个显然的\(n^2\)DP。推式子的时候猜到了\(\gcd=1\)的做法。进一步尝试正解未果。T2一眼只会爆搜。想到了\(b\timesb!\)的做法,应该能过\(......
  • Java日总结---多表查询&事务
    多表查询简介:设计员工和部门两个表点击查看代码#创建部门表CREATETABLEdept(didINTPRIMARYKEYAUTO_INCREMENT,dnameVARCHAR(20));#创建员工表CREATETABLEemp(idINTPRIMARYKEYAUTO_INCREMENT,NAMEVARCHAR(10),genderCHAR(1),--性别salaryDOU......
  • 10.10
    我本来以为打模拟赛有两种苦难一种是豪挂不止——『愤怒』一种是完全不会——『绝望』然后今天发现了被忽视的第三种——『哀伤』\(A\)不到一个小时想出来咋写,从思路到细节总之代码的整个流程跟题解都一模一样,但是写不出来。虽然不知道这个容斥的名字,但是我能清楚的记得刚上......
  • 24.10.10
    非常好双十模拟赛,使我的分数任意旋转都不变(〇),爱来自CDQZ。话说怎么双十模拟赛题面都是双十一啊(A数据范围弱化版:P2592。\(n,m\le10^7\)。把一个看作\(+1\)另一个\(-1\),那么合法序列即为前缀和的最大值与最小值的差\(\lek\)。在一维上不好写,上二维平面。把向右走一步......