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

2022牛客多校（九）

news 来源：原创 2024/5/1 6:28:04

2022牛客多校（九）

文章目录

  • 2022牛客多校（九）
    • 一、比赛小结
    • 二、题目分析及解法（基础题）
    • A、Car Show
    • B、Two Frogs
    • C、Global Positioning System
    • E、Longest Increasing Subsequence
    • G、Magic Spells
    • I、The Great Wall II
    • 三、题目分析及解法（进阶题）

一、比赛小结

比赛链接："蔚来杯"2022牛客暑期多校训练营9

二、题目分析及解法（基础题）

A、Car Show

题目链接：A-Car Show

题意：

给定一个长为n的包含1,2,…,m的序列，求有多少区间[L,R]包含所有1,2,…,m。

题解：

双指针

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 5;
int t[maxn];
vector<int> pos[maxn];
int n, m;
int nxt[maxn];
bool vis[maxn];
int ans[maxn];
signed main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) ans[i] = nxt[i] = n + 1;
  for (int i = 1; i <= n; i++) cin >> t[i], pos[t[i]].push_back(i);
  for (int i = 1; i <= m; i++)
    if (pos[i].size())
      for (int j = 0; j < pos[i].size() - 1; j++)
        nxt[pos[i][j]] = pos[i][j + 1];
  int cnt = 0;
  for (int i = 1; i <= n; i++) {
    if (!vis[t[i]]) {
      cnt++;
      vis[t[i]] = 1;
    }
    if (cnt == m) {
      ans[1] = i;
      break;
    }
  }
  for (int i = 2; i <= n; i++) ans[i] = max(ans[i - 1], nxt[i - 1]);
  // for (int i = 1; i <= n; i++) cout << nxt[i] << " ";
  // cout << endl;
  // for (int i = 1; i <= n; i++) cout << ans[i] << " ";
  // cout << endl;
  int res = 0;
  for (int i = 1; i <= n; i++) res += (n - ans[i] + 1);
  cout << res << endl;
  return 0;
}

B、Two Frogs

题目链接：B-Two Frogs

题意：

河道里有 n 个荷叶排成一排，从第 i ( < n ) 个荷叶出发可以跳到第 ( i , i + a_i ] 个荷叶上，有两只青蛙从第1个荷叶出发，每一步都独立地等概率随机地跳向后边的荷叶，求两只青蛙以相同步数到达第n个荷叶的概率。

题解：

概率 dp ，推出式子即可

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 8e3 + 5;
const int mod = 998244353;
int n;
int a[maxn], inva[maxn];
int sum[maxn][maxn];
int quickpow(int a, int b) {
  int res = 1LL;
  while (b) {
    if (b & 1) res = 1LL * res * a % mod;
    a = 1LL * a * a % mod;
    b >>= 1LL;
  }
  return res;
}
int getinv(int a) { return quickpow(a, mod - 2); }
signed main() {
  clock_t startTime = clock();
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  memset(sum, 0, sizeof sum);
  cin >> n;
  for (int i = 1; i <= n - 1; i++) cin >> a[i];
  for (int i = 1; i <= n - 1; i++) inva[i] = getinv(a[i]);
  sum[n][0] = 1;
  for (int i = n - 1; i >= 1; i--) {
    for (int j = 1; j <= n; j++) {
      int tmp = sum[i + 1][(j - 1)] - sum[i + a[i] + 1][(j - 1)];
      sum[i][j] = (sum[i + 1][j] + tmp * inva[i]) % mod;
    }
    sum[i][0] = sum[i + 1][0];
  }
  int ans = 0;
  for (int j = 1; j <= n; j++) {
    int tmp = sum[1][j] - sum[2][j];
    ans = (ans + tmp * tmp) % mod;
  }
  cout << ans << endl;
  clock_t endTime = clock();
  // cout << "Time: " << (double)(endTime - startTime) / CLOCKS_PER_SEC << "s";
  return 0;
}

C、Global Positioning System

题目链接：C-Global Positioning System

题意：

有 n 个坐标未知的三维点，给出 m 对点的相对位置关系，要修改恰好一个关系使得存在一组三维点坐标满足所有关系，找出所有可以被修改的关系。
题解：

不难发现，存在一组三维点坐标满足所有相对位置关系，当且仅当图上所有回路的矢量和为0

如果存在回路的矢量和不为0 ⃑，那么需要被修改的边就是所有这些回路的交集。由于保证有解，交集不会为空，也不需要考虑无法修改一条边使得所有回路的矢量和均为0 ⃑的情况。

如果所有回路的矢量和均为0 ⃑，也就是已经有解的情况下，有且只有图中的桥边可以被修改。

要判断前述两种情况，只需要任取一棵生成树，考虑所有的非树边与树上路径构成的简单回路即可，这是因为图上所有回路都是这些简单回路的线性组合。

这样问题就转化为树上的路径覆盖问题，树上差分即可。这里如果取DFS树作为生成树，所有非树边都是返祖边，就不需要求LCA了。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
int read() {
  int a = 0, fh = 1;
  char c = getchar();
  while (c > '9' || c < '0') {
    if (c == '-') fh = -1;
    c = getchar();
  }
  while ('0' <= c && c <= '9') {
    a = a * 10 + c - 48;
    c = getchar();
  }
  return a * fh;
}
#define MN 500005
#define pii pair<int, int>
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define vc vector
int n, m;
int fa[MN], dep[MN], anc[MN][21], eid[MN], tag[MN][2];
bool vis[MN];
struct vec {
  int x, y, z;
  vec() {}

  vec(int X, int Y, int Z) { x = X, y = Y, z = Z; }
} loc[MN], w[MN];
vec operator+(vec a, vec b) { return vec(a.x + b.x, a.y + b.y, a.z + b.z); }
bool operator==(vec a, vec b) { return a.x == b.x && a.y == b.y && a.z == b.z; }
vc<pair<int, vec> > e[MN];
void dfs(int x) {
  //	cerr<<"dfs: "<<x<<" "<<fa[x]<<endl;
  vis[x] = 1;
  dep[x] = dep[fa[x]] + 1;
  anc[x][0] = fa[x];
  for (int i = 1; i <= 19; ++i) anc[x][i] = anc[anc[x][i - 1]][i - 1];
  for (auto i : e[x]) {
    int v = i.x;
    if (vis[v]) continue;
    fa[v] = x;
    loc[v] = loc[x] + i.y;
    dfs(v);
  }
}
int LCA(int x, int y) {
  if (dep[x] < dep[y]) swap(x, y);
  for (int i = 19; i >= 0; --i)
    if (dep[anc[x][i]] >= dep[y]) x = anc[x][i];
  if (x == y) return x;
  for (int i = 19; i >= 0; --i)
    if (anc[x][i] != anc[y][i]) x = anc[x][i], y = anc[y][i];
  return anc[x][0];
}
int u[MN], v[MN];
vc<int> ans, err;
void DFS(int x) {
  for (auto i : e[x]) {
    int v = i.x;
    if (fa[v] != x) continue;
    DFS(v);
    for (int i = 0; i < 2; ++i) tag[x][i] += tag[v][i];
  }
  if (tag[x][0] == err.size() && !tag[x][1] && x != 1) ans.pb(eid[x]);
}
signed main() {
  //	freopen("4.in","r",stdin);
  //	freopen("4.out","w",stdout);
  n = read(), m = read();
  for (int i = 1; i <= m; ++i) {
    u[i] = read(), v[i] = read();
    int x = read(), y = read(), z = read();
    w[i] = vec(x, y, z);
    e[u[i]].pb(mp(v[i], vec(x, y, z)));
    e[v[i]].pb(mp(u[i], vec(-x, -y, -z)));
  }
  dfs(1);
  for (int i = 1; i <= m; ++i) {
    int x = u[i], y = v[i];
    if (fa[x] == y || fa[y] == x) {
      assert((loc[x] + w[i]) == loc[y]);
      if (fa[y] == x) swap(x, y);
      eid[x] = i;
      continue;
    }
    int g = LCA(x, y);
    bool op = ((loc[x] + w[i]) == loc[y]);
    //	else cerr<<"! "<<x<<" "<<y<<" "<<g<<endl;
    tag[x][op]++;
    tag[y][op]++;
    tag[g][op] -= 2;
    if (!op) err.pb(i);
  }
  // for(auto i:err)cerr<<"err: "<<i<<endl;
  DFS(1);
  if (err.size() == 1) ans.pb(err.back());
  sort(ans.begin(), ans.end());
  if (!ans.empty() && ans.front() == 0)
    ans = vector<int>(ans.begin() + 1, ans.end());
  printf("%lld\n", (int)ans.size());
  for (auto i : ans) printf("%lld ", i);
  return 0;
}

E、Longest Increasing Subsequence

题目链接：E-Longest Increasing Subsequence

题意：

构造一个1,2,…,n的排列，使其恰好有m个不同的最长上升子序列。

m ≤ 10^9，要求 n ≤ 100。

题解：

记m的二进制表示为b_k b_(k-1)…b_0，其中b_k=1，b_i∈{0,1}。

先构造2,1,4,3,6,5,…,2k,2k-1，然后低到高依次考虑m的二进制位。

如果b_i=1，就在第2i个数之后插入一个大于2k的数字p_i，适当取值使得这些p_i是递增的。

这样原序列的LIS长度会是k+1，包含p_i (i<k)的上升序列长度可能不够。

只需要紧接着每个p_i (i<k)再插入一些递增的数字，并重新调整每个p_i的取值即可。

容易发现p_i (i<k)后边需要插入的数字个数就是m的二进制表示下第i位往上连续0的个数。

这样构造出来的排列长度不超过3⌊log_2⁡m ⌋+1。

代码：

#include <bits/stdc++.h>
using namespace std;
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int m;
    scanf("%d", &m);
    int len = 32 - __builtin_clz(m);
    vector<int> cnt(len);
    for (int i = 0, la = -1; i < len; i++) {
      if (m >> i & 1)
        cnt[la = i]++;
      else if (la >= 0)
        cnt[la]++;
    }
    vector<int> res;
    int low = 0, high = 2 * len - 2;
    for (int i = 0; i < len; i++) {
      if (i > 0) res.push_back(low + 2), res.push_back(low + 1), low += 2;
      for (int j = 0; j < cnt[i]; j++) res.push_back(++high);
    }
    printf("%zu\n", res.size());
    for (size_t i = 0; i < res.size(); i++)
      printf("%d%c", res[i], " \n"[i + 1 == res.size()]);
  }
  return 0;
}

G、Magic Spells

题目链接：G-Magic Spells
题意：

给定k个字符串 S 1 , S 2 , . . . , S k S_1,S_2,...,S_k S1​,S2​,...,Sk​ ，求有多少个本质不同的公共回文子串

题解：

PAM 裸题

代码：

#include <bits/stdc++.h>
#define ll long long
#define int long long
#define endl "\n"
#define P pair<int, int>
#define f first
#define s second
using namespace std;
const int inf = 0x3f3f3f3f;
int t;
int n, m, k;
struct PAM {
  int sz, tot, last;
  string ss;
  struct node {
    int cnt, fail, len;
    array<int, 26> ch;
    node() {
      cnt = 0, fail = 0;
      fill(ch.begin(), ch.end(), 0);
    }
  };
  vector<node> st;
  int new_node(int l) {
    sz++;
    st.emplace_back();
    st[sz].len = l;
    return sz;
  }
  void init()  //初始化要先init，再一个个insert
  {
    sz = -1;
    last = 0;
    tot = 0;
    ss = '$';
    new_node(0);
    new_node(-1);
    st[0].fail = 1;
  }
  int getfail(int x) {
    while (ss[tot - st[x].len - 1] != ss[tot]) x = st[x].fail;
    return x;
  }
  void insert(char c) {
    ss += c;
    tot++;
    int now = getfail(last);
    if (!st[now].ch[c - 'a']) {
      int x = new_node(st[now].len + 2);
      st[x].fail = st[getfail(st[now].fail)].ch[c - 'a'];
      st[now].ch[c - 'a'] = x;
    }
    last = st[now].ch[c - 'a'];
    st[last].cnt++;
  }
  PAM(const string &s1) {
    init();
    for (char c : s1) insert(c);
  }
};
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> k;
  string ss;
  vector<PAM> pam;
  for (int i = 0; i < k; i++) {
    cin >> ss;
    PAM solve(ss);
    pam.emplace_back(solve);
  }
  vector<int> a(k, 0), b(k, 1);
  int ans = 0;
  function<void(vector<int> &)> dfs = [&](vector<int> &idx) {
    for (int i = 0; i < 26; i++) {
      int flag = 1;
      vector<int> f1(k, 0);
      for (int j = 0; j < k; j++) {
        f1[j] = pam[j].st[idx[j]].ch[i];
        flag &= (bool)f1[j];
      }
      if (flag) {
        ans++;
        dfs(f1);
      }
    }
  };
  dfs(a);
  dfs(b);
  cout << ans << endl;
  return 0;
}

I、The Great Wall II

题目链接：I-The Great Wall II

题意：

给定长为 n 的整数序列，将其分为非空的k段使得每一段的最大值之和最小，对k=1,2,…,n分别求解。

题解：

f[i][j] 表示前i个数分成j段的最小得分。

f[i][j] = f[k][j-1] + max(k+1, i)   0<=k<I

代码：

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 8005;
const int INF = 0x3f3f3f3f;
struct Node {
  int v, dp, mi;
  Node() {}
  Node(int _v, int _dp, int _mi) : v(_v), dp(_dp), mi(_mi) {}
} stk[MAXN];
int a[MAXN], dp[2][MAXN], top;
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  int now = 0, la = 1;
  for (int i = 0; i <= n; i++) dp[now][i] = INF * (i > 0);
  for (int k = 1; k <= n; k++) {
    swap(now, la);
    for (int i = 0; i <= n; i++) dp[now][i] = INF;
    stk[top = 0] = Node(INF, INF, INF);
    for (int i = 1; i <= n; i++) {
      int mdp = dp[la][i - 1];
      while (stk[top].v <= a[i]) mdp = min(mdp, stk[top].dp), top--;
      stk[top + 1] = Node(a[i], mdp, min(stk[top].mi, mdp + a[i])), ++top;
      dp[now][i] = stk[top].mi;
    }
    printf("%d\n", dp[now][n]);
  }
  return 0;
}

三、题目分析及解法（进阶题）

相关文章：

  • Java常用类
  • [C/C++]_[初级]_[关于编译时出现有符号-无符号不匹配的警告-sizeof使用注意事项]
  • aarch64服务器-部署mysql
  • PDF转为网页文件怎么转？这篇文章告诉你
  • Java 基本数据类型-包装类-String的相互转换（总结+代码实现）
  • JUC并发编程
  • Spring注解驱动系列总结
  • 记一次mysql 命令行登录报错（error while loading shared libraries: libssl.so.1.1）
  • PyTorch中DataLoader及其与enumerate（）用法介绍
  • mac 使用 PyQt5 和 py_designer 搭建窗体
  • 嵌入式SQL开发
  • 对于HTTP协议，什么是长连接和短连接？
  • ReentrantLock读写锁
  • leetcode 1680. Concatenation of Consecutive Binary Numbers（连接连续的二进制数）
  • Python数据分析之时间序列的处理
  • 分享一款快速APP功能测试工具
  • [ 一起学React系列 -- 8 ] React中的文件上传
  • 2019年如何成为全栈工程师？
  • crontab执行失败的多种原因
  • CSS 专业技巧
  • Git学习与使用心得（1）—— 初始化
  • JAVA_NIO系列——Channel和Buffer详解
  • JavaScript的使用你知道几种？(上)
  • node 版本过低
  • npx命令介绍
  • python学习笔记 - ThreadLocal
  • 道格拉斯-普克 抽稀算法 附javascript实现
  • 发布国内首个无服务器容器服务，运维效率从未如此高效
  • 微信开源mars源码分析1—上层samples分析
  • LIGO、Virgo第三轮探测告捷，同时探测到一对黑洞合并产生的引力波事件 ...
  • ​​​​​​​Installing ROS on the Raspberry Pi
  • $forceUpdate()函数
  • ( )的作用是将计算机中的信息传送给用户,计算机应用基础 吉大15春学期《计算机应用基础》在线作业二及答案...
  • （3）选择元素——（14）接触DOM元素（Accessing DOM elements）
  • (iPhone/iPad开发)在UIWebView中自定义菜单栏
  • （顶刊）一个基于分类代理模型的超多目标优化算法
  • （附源码）springboot教学评价 毕业设计 641310
  • （附源码）ssm高校社团管理系统 毕业设计 234162
  • （三）elasticsearch 源码之启动流程分析
  • (图)IntelliTrace Tools 跟踪云端程序
  • （学习日记）2024.03.12：UCOSIII第十四节：时基列表
  • (转)VC++中ondraw在什么时候调用的
  • (转)创业的注意事项
  • （转）微软牛津计划介绍——屌爆了的自然数据处理解决方案(人脸/语音识别，计算机视觉与语言理解)...
  • .net 程序 换成 java,NET程序员如何转行为J2EE之java基础上（9）
  • .net 微服务 服务保护 自动重试 Polly
  • .NET大文件上传知识整理
  • .NET关于 跳过SSL中遇到的问题
  • .net专家（张羿专栏）
  • .sys文件乱码_python vscode输出乱码
  • []C/C++读取串口接收到的数据程序
  • [ABP实战开源项目]---ABP实时服务-通知系统.发布模式
  • [ACL2022] Text Smoothing: 一种在文本分类任务上的数据增强方法
  • [android] 练习PopupWindow实现对话框
  • [android] 天气app布局练习