首页 > 其他分享 >2024/10/10 模拟赛总结

2024/10/10 模拟赛总结

时间:2024-10-11 11:02:58浏览次数:11  
标签:10 int LL kMaxN 2024 vis long using 模拟

\(0+45+20+25=90\),T1 暴力写挂唐完了

#A. 植物收集

显然催熟次数一定小于 \(n\),否则不会更优。对于催熟次数 \(k\) 确定时,每个种子能形成的其他种子一定如下图:

那么这就变成了一个滑动窗口板子。由于当催熟次数 \(k\) 递增时,催熟的价格线性递增,买种子的价格单调不增,且减量单调递增。两个函数复合后一定是一个下凸的丹枫单峰函数,直接三分即可

// BLuemoon_
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int kMaxN = 2e5 + 5;

LL n, k, a[kMaxN], l, r, mid;
deque<int> q;

LL Chk(int x, LL ret = 0) {
  if (x == n + 1) {
    return 1e18;
  }
  q.clear();
  for (int i = n - x + 1; i <= n; i++) {
    for (; !q.empty() && a[q.back()] >= a[i]; q.pop_back()) {
    }
    q.push_back(i);
  }
  for (int i = n + 1; i <= n << 1; i++) {
    for (; !q.empty() && a[q.back()] >= a[i]; q.pop_back()) {
    }
    q.push_back(i), ret += a[q.front()];
    for (; !q.empty() && q.front() <= i - x; q.pop_front()) {
    }
  }
  return ret + k * x;
}

int main() {
  freopen("collect.in", "r", stdin), freopen("collect.out", "w", stdout);
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> a[i], a[i + n] = a[i];
  }
  for (l = 0, r = n; l < r;) {
    mid = (l + r) >> 1, (Chk(mid + 1) >= Chk(mid)) ? (r = mid) : (l = mid + 1);
  }
  cout << Chk(l) << '\n';
  return 0;
}

#B. 美丽子区间

令 \(f_i\) 为当 \(i\) 作为区间右端点时左端点最右在哪里,\(g_i\) 为当 \(i\) 为区间左端点时右端点最左在哪里,这部分可以用树状数组维护

然后就可以从这两个点跳,中间的就是满足条件的数量

// BLuemoon_
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int kMaxN = 2e5 + 5;

int n, a[kMaxN];
LL ans, f[kMaxN], g[kMaxN];
vector<int> v[kMaxN];

struct BIT {
  LL mx[2][kMaxN], mn[2][kMaxN], sm[kMaxN];
  BIT() { fill(mn[0], mn[2], 1e18), fill(mx[0], mx[2], -1e18); } 
  LL lb(LL x) { return x & -x; }
  void Updatemx(int x, LL y, int t) {
    for (; x <= n; mx[t][x] = max(mx[t][x], y), x += lb(x)){
    }
  }
  void Updatemn(int x, LL y, int t) {
    for (; x <= n; mn[t][x] = min(mn[t][x], y), x += lb(x)){
    }
  }
  void Updatesm(int x, LL y) {
    for (; x <= n; sm[x] += y, x += lb(x)){
    }
  }
  LL Querymx(int x, int t, LL ret = -1e18) {
    for (; x; ret = max(ret, mx[t][x]), x -= lb(x)) {
    }
    return ret;
  }
  LL Querymn(int x, int t, LL ret = 1e18) {
    for (; x; ret = min(ret, mn[t][x]), x -= lb(x)) {
    }
    return ret;
  }
  LL Querysm(int x, LL ret = 0) {
    for (; x; ret += sm[x], x -= lb(x)) {
    }
    return ret;
  }
};

BIT tr;

int main() {
  freopen("interval.in", "r", stdin), freopen("interval.out", "w", stdout);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  if (n <= 3) {
    return cout << "0\n", 0;
  }
  for (int i = 1; i <= n; i++) {
    f[i] = min(tr.Querymx(n + 1 - a[i], 0), tr.Querymx(a[i], 1)) - 1;
    tr.Updatemx(n + 1 - a[i], i, 0), tr.Updatemx(a[i], i, 1);
  }
  for (int i = n; i; i--) {
    g[i] = max(tr.Querymn(n + 1 - a[i], 0), tr.Querymn(a[i], 1)) + 1;
    tr.Updatemn(n + 1 - a[i], i, 0), tr.Updatemn(a[i], i, 1);
  }
  for (int i = 1; i <= n; i++) {
    (f[i] > 0) && (v[f[i]].push_back(i), 0);
  }
  for (int i = 1; i <= n; i++) {
    (g[i] <= n) && (tr.Updatesm(g[i], 1), 0);
    for (int j : v[i]) {
      ans += tr.Querysm(j);
    }
  }
  cout << ans << '\n';
  return 0;
}

#C. 字符序列

先考虑如何 \(O(26n)\) 求本质不同子序列个数

令 \(dp_{i,j}\) 为长度为 \(i\) 的前缀,以字符 \(j\) 结尾的本质不同子序列个数

那么如果 \(s_i\not=j\),\(dp_{i,j}=dp_{i-1,j}\),否则 \(dp_{i,j}=\displaystyle\sum_{i=1}^{26} dp_{i-1,j}\)

这个过程可以用矩乘优化,按上述 dp 模拟即可

// BLuemoon_
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int kMaxN = 500 + 5, kS = 26 + 5;
const LL kP = 1e9 + 7;

struct Mat {
  LL a[kS][kS];
  Mat operator*(const Mat &o) const {
    Mat ret;
    fill(ret.a[0], ret.a[kS], 0);
    for (int i = 0; i <= 26; i++) {
      for (int j = 0; j <= 26; j++) {
        for (int k = 0; k <= 26; k++) {
          (ret.a[i][k] += a[i][j] * o.a[j][k] % kP) %= kP;
        }
      }
    }
    return ret;
  }
};

LL n, ans;
string s;
Mat cnt;

Mat Calc(int x) {
  Mat ret;
  fill(ret.a[0], ret.a[kS], 0);
  for (int i = 0; i <= 26; i++) {
    (i != x) && (ret.a[i][i] = 1);
    if (i == x) {
      for (int j = 0; j <= 26; j++) {
        ret.a[i][j] = 1;
      }
    }
  }
  return ret;
}

int main() {
  freopen("subseq.in", "r", stdin), freopen("subseq.out", "w", stdout);
  cin >> n >> s, s = ' ' + s;
  fill(cnt.a[0], cnt.a[kS], 0);
  for (int i = 0; i <= 26; i++) {
    cnt.a[i][i] = 1;
  }
  for (int i = n; i; i--) {
    cnt = cnt * Calc(s[i] - 'a') * cnt;
  }
  for (int i = 0; i < 26; i++) {
    (ans += cnt.a[i][26]) %= kP;
  }
  cout << ans << '\n';
  return 0;
}

#D. 网络攻防

先抽出一颗 DFS 生成树,那么非树边一定是返祖边而非横跨边

\(k=1\) 是 tarjan 求割边板子,但是不好写,考虑树上差分

否则需要分类讨论:

  • 若删除两条非树边,那么不会影响连通性
  • 若删除一条割边,另外的边可以随便选,但要去掉两条割边互相选的情况
  • 若删除一条非割边的树边
    • 另一条边如果是非树边,这条非树边一定是唯一包含这条树边的返祖边,否则可以通过另一条返祖边维持连通性
    • 如果另一条也是非割边的树边,图不连通的充要条件是包含这两条边的返祖边边集相同,这部分证明可以自己画图感性理解一下
      • 对于充分性,删除这两条边,夹在这两条边之间的点就会被割掉
      • 对于必要性,如果有一条只跨过其中一条树边的非树边,两边之间的点集就可以通过多出的这条边联通

那么除了最后一种情况,前面都可以通过树上差分解决,最后一种情况要用 xor-hashing 来求边集,遍历一遍 map 即可求出答案

// BLuemoon_
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int kMaxN = 2e5 + 5;

int n, m, k, u[kMaxN], v[kMaxN], s[kMaxN], dep[kMaxN];
vector<pair<int, int>> g[kMaxN];
LL ans;
unsigned long long e[kMaxN], o[kMaxN];
unordered_map<unsigned long long, LL> mp;
bitset<kMaxN> vis, f;
mt19937 Rand(time(0) / 2 + 3247);

void DFS(int u) {
  for (auto [v, i] : g[u]) {
    if (!vis[v]) {
      vis[v] = 1, f[i] = 1, dep[v] = dep[u] + 1, DFS(v);
    }
  }
}
void DFS1(int u) {
  for (auto [v, i] : g[u]) {
    if (!vis[v]) {
      vis[v] = 1, DFS1(v), s[u] += s[v];
    }
  }
}
void DFS2(int u) {
  for (auto [v, i] : g[u]) {
    if (!vis[v]) {
      vis[v] = 1, DFS2(v), o[u] ^= o[v], mp[o[v]]++;
    }
  }
}

int main() {
  freopen("attack.in", "r", stdin), freopen("attack.out", "w", stdout);
  cin >> n >> m >> k;
  for (int i = 1; i <= m; i++) {
    cin >> u[i] >> v[i], g[u[i]].push_back({v[i], i}), g[v[i]].push_back({u[i], i});
  }
  vis[1] = 1, DFS(1);
  for (int i = 1; i <= m; i++) {
    (!f[i]) && (dep[v[i]] > dep[u[i]] ? (s[v[i]]++, s[u[i]]--) : (s[u[i]]++, s[v[i]]--));
  }
  vis.reset(), vis[1] = 1, DFS1(1);
  for (int i = 2; i <= n; i++) {
    ans += !s[i];
  }
  if (k == 1) {
    return cout << ans << '\n', 0;
  }
  ans += (ans * (m - ans) + ans * (ans - 1) / 2);
  for (int i = 2; i <= n; i++) {
    ans += (s[i] == 1);
  }
  for (int i = 1; i <= m; i++) {
    if (!f[i]) {
      e[i] = uniform_int_distribution<unsigned long long>(0, 1e18)(Rand);
      o[v[i]] ^= e[i], o[u[i]] ^= e[i];
    }
  }
  vis.reset(), vis[1] = 1, DFS2(1);
  for (auto [x, y] : mp) {
    (x != 0) && (ans += y * (y - 1) / 2);
  }
  cout << ans << '\n';
  return 0;
}

标签:10,int,LL,kMaxN,2024,vis,long,using,模拟
From: https://www.cnblogs.com/bluemoon-blog/p/18457898

相关文章

  • DATAGERRY REST API身份验证绕过漏洞(CVE-2024-46627)
    0X01产品描述:        ‌DATAGERRY是一个灵活的开源CMDB和资产管理工具,它完全将数据模型的定义留给用户。‌用户只需在一个易于使用的webfrontend中定义自己的对象类型(如服务器、路由器、租赁线路、位置等)。通过DATAGERRY的导出API,存储在DATAGERRY中的CMDB对象可以轻......
  • 2024前端高频面试题之一
    1.从输入URL到页面显示发生了什么(1)缓存查询(查询优先级:浏览器缓存,系统缓存,路由器缓存)(2)DNS解析,把网址解析唯一IP【网址是为了方便记忆】(3)执行tcp三次握手,建立http链接(4)浏览器拿到返回的数据渲染页面【可能存在跨域问题】(5)断开tcp连接2.fetch和ajax的......
  • 2024-10-11 自定义渲染之arco-design-vue table的columns的title ==》使用DOM插入子元
    嗯...不知我没找到arco对应tabletitle的自定义渲染的正确方式 但我已经找了1个小时了,既然没找到就自己插入吧业务场景如下: 给表头插入一个必填的符号*,就这么简单的需求。代码如下:constelements:any=document.querySelectorAll('.arco-table-th-title');elements.f......
  • 【2024-10-10】以理考文
    20:00不要怕,无论什么困难的事,只要硬着头皮去做,就闯过去了。                                                 ——林海音公司在不久前提交了涉密资质认证的申请,我是小......
  • 华为机顶盒ec6108v9a刷机笔记
    背景: 家里的不用的机顶盒,联通版,品牌是华为ec6108v9a。芯片是rk312x目的:让机顶盒能支持无线投屏。现状:该机顶盒的无线网络口被关闭,没办法打开,且按照网络上的开机狂按待机键,仍然无法进入刷机界面,没办法实现u盘刷机。经过无数次的狂按待机失败,只能放弃,后来通过华为STB管理软件......
  • 图像数据增强库综述:10个强大图像增强工具对比与分析
    在深度学习和计算机视觉领域,数据增强已成为提高模型性能和泛化能力的关键技术。本文旨在全面介绍当前广泛使用的图像数据增强库,分析其特点和适用场景,以辅助研究人员和开发者选择最适合其需求的工具。数据增强的重要性数据增强在深度学习模型训练中扮演着至关重要的角色,其......
  • 20222322 2024-2025-1 《网络与系统攻防技术》实验一实验报告
    1.实验内容1.1本周学习内容本周学习主要围绕缓冲区溢出漏洞(攻击)展开1.2实验内容简述“pwn1”是一个Linux可执行文件正常运行时会调用“foo”函数。“foo”函数的功能是对用户输入的字符串进行简单回显。此程序中还包含另一个代码片段“getShell”,具有返回一个可用Shell的......
  • 网络安全(黑客技术)2024年三个月自学手册
    ......
  • 网络安全(黑客技术)2024年三个月自学手册
    ......
  • 2024最新免费申请一年期HTTPS证书方法!
    2023年11月中旬,阿里云和华为云首先宣布不再提供一年期免费SSL证书,改为提供三个月有效期的证书。腾讯云也在2024年3月中旬跟进,取消了免费一年期SSL证书的供应。目前,虽然免费一年期SSL证书已经不多见,但还有一些平台如JoySSL提供无限制的免费一年期SSL证书申请,包括单域名证书、......