首页 > 其他分享 >牛客暑假多校 2023 第五场

牛客暑假多校 2023 第五场

时间：2023-08-02 09:24:01浏览次数：48  
标签：ch int 第五场 kN 多校 牛客 区间 include getchar

目录

写在前面

战犯在此。

我宣布二周年这首是神。

<iframe border="0" frameborder="no" height="86" marginheight="0" marginwidth="0" src="//music.163.com/outchain/player?type=2&id=2030210197&auto=0&height=66" width="330"></iframe>

以下按个人向难度排序。

G

尺取法，右端点单调右移过程中右移调整左端点，使区间内每种数都至少出现 1 次，4 出现至少 \(k\) 次即可。

//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
const int kN = 1e5 + 10;
//=============================================================
int n, k, a[kN];
int num, cnt[5];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  n = read(), k = read();
  for (int i = 1; i <= n; ++ i) a[i] = read();

  int l = 1, r = 0, ans = n;
  while (r < n && num != 4 || cnt[4] < k) {
    ++ r;
    if (cnt[a[r]] == 0) ++ num;
    ++ cnt[a[r]];
  }
  for (; r <= n; ) {
    while (1) {
      if (a[l] != 4) {
        if (cnt[a[l]] == 1) break;
      } else {
        if (cnt[a[l]] == k) break;
      }
      -- cnt[a[l]];
      ++ l;
    }
    if (num == 4 && cnt[4] >= k) ans = std::min(ans, r - l + 1);
    ++ r;
    cnt[a[r]] ++;
  }
  printf("%d\n", ans);
  return 0;
}

D

\(b\) 整除 \(c\)，则枚举 \(c\) 的因数即可得到所有可能的 \((a, b)\)，检查是否满足条件即可。

H

每次行动结束后的结果是原数列的一段前缀被清空，而清空某一段等价于对这一段做一个 01 背包，那么有个显然的 DP：

首先预处理 \(f_{i, j, k}\) 表示对区间 \([i, j]\) 做容量为 \(k\) 的 01 背包可以获得的最大价值，再设 \(g_{i, j}\) 表示前 \(i\) 次 行动清空了前缀 \(1\sim j\) 可以获得的最大价值，转移时考虑考虑上一次行动结束时空前缀的位置，和这一次行动准备清空哪一段，则有：

\[g_{i, j} = \max\left(\max_{1\le k<i}{\left( g_{i - 1, k} + f_{k + 1, j, sz_i} \right)}, g_{i - 1, j}\right) \]

预处理 01 背包时间复杂度 \(O(n^3)\)，但是上述转移时间复杂度是 \(O(n^2m)\)的，瓶颈在于 \(m\) 过大。

发现 \(sz\) 递增的结论没用上，又发现至多仅有 \(n\) 个 \(sz\) 是有用的，那么仅需取至多 \(n\) 个最大的 \(sz\) 出来参与上述转移即可。总时间复杂度变为 \(O(n^3)\) 级别。

//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define pr std::pair
#define mp std::make_pair
#define LL long long
const int kN = 200 + 10;
const int kM = 1e5 + 10;
const LL kInf = 1e15 + 2077;
//=============================================================
int n, m, a[kN], b[kN];
int sznum, sz[kM], useful[kN];
LL f[kN][kN][kN], g[kN][kN];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
void Init() {
  n = read(), m = read();
  for (int i = 1 ;i <= n; ++ i) a[i] = read(), b[i] = read();
  for (int i = 1; i <= m; ++ i) sz[i] = read();
  sznum = std::min(n, m);
  for (int i = 1, j = m - sznum + 1; i <= sznum; ++ i, ++ j) {
    useful[i] = sz[j];
  }
}
void DPf() {
  for (int l = 1; l <= n; ++ l) {
    for (int r = l; r <= n; ++ r) {
      int c = a[r], v = b[r];
      for (int i = 1; i <= 200; ++ i) f[l][r][i] = f[l][r - 1][i];
      for (int i = 200; i >= c; -- i) {
        f[l][r][i] = std::max(f[l][r][i], f[l][r - 1][i - c] + 1ll * v);
      }
      for (int i = 1; i <= 200; ++ i) {
        f[l][r][i] = std::max(f[l][r][i], f[l][r][i - 1]);
      }
    }
  }
}
void DPg() {
  for (int i = 1; i <= sznum; ++ i) {
    int s = useful[i];
    for (int j = 0; j <= n; ++ j) {
      g[i][j] = g[i - 1][j];
      for (int k = 0; k < j; ++ k) {
        g[i][j] = std::max(g[i][j], g[i - 1][k] + f[k + 1][j][s]);
      }
    }
  }
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  // freopen("std.txt", "w", stdout);
  Init();
  DPf(), DPg();
  LL ans = 0;
  for (int i = 0; i <= n; ++ i) ans = std::max(ans, g[sznum][i]);
  printf("%lld\n", ans);
  return 0;
}

C

赛时猜结论过了呃呃，估计八十车人也是这么过的。

数据水了，要不然就被卡死了。

咕一下先。

E

大力手玩题，但是我没脑子，玩不出来呜呜

题目中特别指出了区间要么是相互包含的要么是互不相交的，即所有区间按照包含关系构成了树状结构。在这种限制下逆序对的限制是比较宽松的，发现只要没有限制区间长度为 1 并且钦定逆序对为奇数，都能构造出来。于是我们再另外加入 \(n\) 个长度为 1 的区间，使得这棵树可以覆盖整个排列。

考虑递归地解决问题，钦定区间 \([l, r]\) 为 \(l\sim r\) 的一个排列，然后考虑如何若干个合法的小区间合并为一个大的合法区间。如果大的区间此时也合法那么皆大欢喜，否则考虑做一点小调整。我们考虑这些小区间中相邻的两个 \([l_1, r_1], [r_1 + 1, r_2]\)，\([l_1, r_1]\) 是 \(l_1\sim r_1\) 的一个排列，\([r_1 + 1, r_2]\) 是 \(r_1 + 1\sim r_2\) 的一个排列，那么只需交换 \(r_1\) 与 \(r_1 + 1\) 的位置即可在不影响小区间的情况下翻转大区间的奇偶性。

按照上述过程先对限制区间进行排序，再递归解决即可。递归过程中每个限制区间只会访问一次，则总时间复杂度上界是 \(O(n + m)\) 级别的。

//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
const int kN = 1e3 + 10;
//=============================================================
int n, m, ans[kN], pos[kN];
int num;
struct TMOperaO {
  int l, r, w, solved;
} a[kN << 1];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
bool cmp(TMOperaO fir_, TMOperaO sec_) {
  if (fir_.l != sec_.l) return fir_.l < sec_.l;
  return fir_.r > sec_.r;
}
void Dfs(int L_, int R_) {
  if (L_ == R_) return ;
  
  int sumw = 0;
  for (int i = L_ + 1, j; i <= R_; ++ i) {
    if (a[i].solved) continue;
    for (j = i; a[j].l <= a[i].r && j <= R_; ++ j);
    Dfs(i, j - 1);
    sumw += a[i].w;
  }
  a[L_].solved = 1;
  if (sumw % 2 == a[L_].w) return ;

  int p1 = L_ + 1;
  std::swap(pos[a[p1].r], pos[a[p1].r + 1]);
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  n = read(), m = read();
  for (int i = 1; i <= m; ++ i) {
    int l = read(), r = read(), w = read();
    if (l == r && w == 1) {
      printf("-1\n");
      return 0;
    }
    if (l == r) continue;
    a[++ num] = (TMOperaO) {l, r, w, 0};
  }
  for (int i = 1; i <= n; ++ i) {
    a[++ num] = (TMOperaO) {i, i, 0, 1};
    pos[i] = i;
  }
  std::sort(a + 1, a + num + 1, cmp);
  
  for (int i = 1, j; i <= num; ++ i) {
    if (a[i].solved) continue;
    for (j = i; a[j].l <= a[i].r && j <= num; ++ j);
    Dfs(i, j - 1);
  }
  for (int i = 1; i <= n; ++ i) ans[pos[i]] = i;
  for (int i = 1; i <= n; ++ i) printf("%d ", ans[i]);
  return 0;
}

I

哈，这题的核心 idea 我还拿出来出过超级弱化版，我真牛逼：https://www.luogu.com.cn/problem/U150104。

考虑把题目中的式子拆成三段分别考虑。

先做个前缀/后缀异或，区间异或变成了两点异或。然后考虑拆位，枚举 \(r_1\) 的同时统计前缀中某一位为 0/1 的数量，即可求得某个前缀的第一段的贡献，第三段同理。

再考虑中间一段，仍然考虑拆位，枚举 \(r_2\) 的同时统计前缀中某一位为 0/1 的位置的第一段的贡献，统计贡献时将三段相乘即可。不太好描述，详见代码。

总时间复杂度 \(O(n\log v)\) 级别。

//
/*
By:Luckyblock
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define LL long long
const LL p = 998244353;
const int kN = 2e5 + 10;
//=============================================================
int n;
LL a[kN], prea[kN], sufa[kN], presum[kN], sufsum[kN];
LL ans, cntpre[2], cntsuf[2], sum[2];
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
void Init() {
  for (int i = 1; i <= n; ++ i) prea[i] = prea[i - 1] ^ a[i];
  for (int i = n; i; -- i) sufa[i] = sufa[i + 1] ^ a[i];
  
  for (int i = 0, j = 1; i <= 30; ++ i, j <<= 1) {
    cntpre[0] = cntpre[1] = 0;  
    for (int k = 0; k <= n; ++ k) {
      int l = prea[k] & j ? 1 : 0;
      presum[k] = (presum[k] + 1ll * j * cntpre[l ^ 1] % p) % p;
      ++ cntpre[l];
    }
  }
  for (int i = 1; i <= n; ++ i) presum[i] = (presum[i - 1] + presum[i]) % p;

  for (int i = 0, j = 1; i <= 30; ++ i, j <<= 1) {
    cntsuf[0] = cntsuf[1] = 0;
    for (int k = n + 1; k >= 0; -- k) {
      int l = sufa[k] & j ? 1 : 0;
      sufsum[k] = (sufsum[k] + 1ll * j * cntsuf[l ^ 1] % p) % p;
      ++ cntsuf[l];
    }
  }
  for (int i = n; i >= 1; -- i) sufsum[i] = (sufsum[i + 1] + sufsum[i]) % p;
}
void Solve() {
  for (int i = 0, j = 1; i <= 30; ++ i, j <<= 1) {
    sum[0] = sum[1] = 0;
    for (int r2 = 1; r2 < n; ++ r2) {
      int l = prea[r2] & j ? 1 : 0;
      if (r2 >= 2) {
        ans = (ans + sum[l ^ 1] * j % p * sufsum[r2 + 1] % p) % p;
      } 
      sum[l] = (sum[l] + presum[r2]) % p;
    }
  }
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  n = read();
  for (int i = 1; i <= n; ++ i) a[i] = read();
  Init();
  Solve();
  printf("%lld\n", ans);
  return 0;
}

写在最后

学到了什么：

  • 多余的物品，有用的物品。
  • 有条件没用？再看两眼。
  • 预处理大法好。
  • 构造某种数量要求的逆序对。

标签：ch,int,第五场,kN,多校,牛客,区间,include,getchar
From： https://www.cnblogs.com/luckyblock/p/17599666.html

相关文章

  • 2023牛客暑期多校5 I The Yakumo Family
    题意RanfeelsboringathomeandwantstoproposeamathproblemwithYukariandChen!So,here'sTheYakumoFamilyProblem:Givenanintegerarraya,trytocalculatethevalueofthefollowingequationmodulo\(998244353\):\[\sum_{1\lel_1\le......
  • 2023年多校联训NOIP层测试1
    咕~2023年多校联训NOIP层测试1T1luoguP6882[COCI2016-2017#3]Imena50ptsT26ptsT3luoguP7535[COCI2016-2017#4]Kas15ptsT410pts......
  • 2023牛客暑期多校训练营4
    A.BoboStringConstruction题意：给出一个01字符串t，要求构造一个长为n的01字符串s，使得新的字符串t+s+t不会有超过两个子串tSolution答案要么全0串要么全1串带进去看看成不成立就行了voidsolve(){ intn;cin>>n; strings0(n,'0'); strings1(n,'1'); stringt;cin>>t; ......
  • 牛客多校第三场-D-Ama no Jaku
    D-AmanoJaku_2023牛客暑期多校训练营3做法：2-sat先贴个代码，晚点补上思路#include<bits/stdc++.h>usingnamespacestd;#defineendl"\n"typedeflonglongll;constintN=2e3+5;chara[N][N];std::vector<int>edge[N];//bel数组记录某个点在哪个连通块里面int......
  • 2023暑假杭电多校做题记录
    杭电0101原本以为单组询问要O(log)做，想了很久不会。发现数据范围是3000，于是直接暴力枚举相遇的点，excrt解两个同余方程即可，通过预处理可以做到\(O(nm+mlog)\)然后确实有加强版的题目CF500G大概可以转化成区间余数最小的问题，但是没研究明白，sad杭电0208线段树维护矩阵板题，比......
  • 牛客第四场补题 AFHJL
    牛客第四场补题AFHJLJ.Qu'est-ceQueC'est?题意：构建一个n个数的数组，满足：\(-m<=a_i<=m\)对于所有的\(1\lel<r\len\)都有\(\sum^{r}_{i=l}a_i\ge0\)思路：简单翻译就是最小字段和必须大于等于0。先来做一个简单版本：要求必须区间长度为2的情况下所有都满足上面的关系。......
  • 牛客暑假多校 2023 第四场
    目录写在前面ALFJH写在最后写在前面比赛地址：https://ac.nowcoder.com/acm/contest/57358。那时，天下人的口音，言语，都是一样。他们往东边迁移的时候，在示拿地遇见一片平原，就住在那里。他们彼此商量说，来吧，我们要作砖，把砖烧透了。他们就拿砖当石头，又拿石漆当灰泥。他们说，来吧，我......
  • 【题解】[2023牛客多校] Qu'est-ce Que C'est?
    题目传送门：[2023牛客多校]Qu'est-ceQueC'est?题意给定\(n，m\)构造\(a_{1},a_{2},...,a_{n}\)，其中\(a_{i}\in[-m,m]\)之间取值。需要保证序列任意连续子段和都非负。\(0\leqn,m\leq5000\)分析记录合法序列的最小后缀。通过最小后缀来判断下一个数的取值范围。......
  • 暑假牛客多校第四场 2023-7-28
    未补完L.WearetheLights算法：反向构造做法：  我们用c_on,r_on,c_off,r_off分别表示倒着推的行灯打开的集合、列灯打开的集合、列灯关闭的集合、行灯关闭的集合。倒着推时，我们先考虑on的情况。为了偷懒，我们就只考虑行的情况，因为列的情况实际上是一样的。  打开......
  • HDU 暑假多校 2023 第四场
    目录写在前面731773237314732173227318写在最后写在前面补题地址：https://acm.hdu.edu.cn/listproblem.php?vol=64，题号7312~7323。我是飞舞。小子们哪，你们要自守，远避偶像。Dearchildren,keepyourselvesfromidols.——约翰一书以下按照个人向难度排序。7317签到，特......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99