首页 > 其他分享 >20240927 随机训练

20240927 随机训练

时间：2024-09-27 18:13:06浏览次数：11  
标签：return 训练 int 个数 cin 20240927 MAXN 随机 MOD

GYM 105350 E

题目描述

给定一个大小为 \(N\) 的数组 \(A\)。

我们定义一个大小为 \(N\) 的数组 \(B\) 是有效的当且仅当：

  • 对于 \(\forall 1\le i\le N,1\le B_i \le N\)，如果从 \(B\) 中移除 \(B_i\)，则数组 \(B\) 恰好有 \(A_i\) 个不同的数。

求有多少个不同的由有效数组 \(B\) 组成的多重集合。

思路

分类讨论。

首先很容易想到，\(A\) 中至多有两种数字，且两种数字的差为 \(1\)。因为删除一个数字后不同数字数量至多减少一。否则输出 \(0\)。

  • 若 \(A\) 中只有一个数字 \(x\)，那么有两种情况：
    • 如果 \(x=N-1\)，那么有可能所有数互不相同，有 \(1\) 种情况。
    • 如果 \(2x\le N\)，那么有可能每个数的数量 \(\ge 2\)，所以删掉哪个数都不变。这里要从 \(N\) 个数选出 \(x\) 个数用，并且每个数数量 \(\ge 2\) 且总和为 \(N\)，根据插板法，有 \(C_{N-x-1}^{x-1}\cdot C_N^x\) 种情况。
  • 若 \(A\) 中有两个数 \(x,x-1\)，且 \(x-1\) 出现了 \(y\) 次，那么有三种情况：
    • 若 \(x-y\le 0\)，则无解，因为总共有 \(x\) 个数，其中有 \(y\) 个数出现了一次，所以无解。
    • 若 \(2(x-y)+y>N\)，则无解，因为有 \(x-y\) 个数至少出现 \(2\) 次，\(y\) 个数出现 \(1\) 次。
    • 否则，我们要从 \(N\) 个数中选出 \(x-y\) 个数，再从 \(N-(x-y)\) 个数中选出 \(y\) 个数，同时那 \(x-y\) 个数每个数出现至少两次，且总共出现 \(N-y\) 次，通过插板法可知总共有 \(C_{N}^{x-y}\cdot C_{N-x+y}^y\cdot C_{N-x-1}^{x-y-1}\) 种情况。

空间复杂度 \(O(N)\)，时间复杂度 \(O(N\log N)\)。

代码

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 300001, MOD = 998244353;

int t, n, a[MAXN], cnt, f[MAXN], inv[MAXN], Inv[MAXN];

void work() {
  f[0] = inv[1] = Inv[0] = 1;
  for(int i = 1; i < MAXN; ++i) {
    f[i] = 1ll * f[i - 1] * i % MOD;
    inv[i] = (i > 1 ? 1ll * (MOD - MOD / i) * inv[MOD % i] % MOD : 1);
    Inv[i] = 1ll * Inv[i - 1] * inv[i] % MOD;
  }
}

int C(int n, int m) {
  return (n < m ? 0 : 1ll * f[n] * Inv[m] % MOD * Inv[n - m] % MOD);
}

void Solve() {
  cin >> n;
  set<int> s;
  for(int i = 1; i <= n; ++i) {
    cin >> a[i];
    s.insert(a[i]);
  }
  if(s.size() > 2 || (s.size() == 2 && *s.begin() != *next(s.begin()) - 1)) {
    cout << "0\n";
    return;
  }
  cnt = 0;
  for(int i = 1; i <= n; ++i) {
    cnt += (a[i] == *s.begin());
  }
  if(s.size() == 1) {
    int ans = (*s.begin() == n - 1), res = *s.begin();
    if(2 * res <= n) {
      ans = (ans + 1ll * C(n - res - 1, res - 1) * C(n, res) % MOD) % MOD;
    }
    cout << ans << "\n";
  }else {
    int res = *next(s.begin()) - cnt;
    if(res <= 0 || 2 * res + cnt > n) {
      cout << "0\n";
      return;
    }
    cout << 1ll * C(n - cnt - res - 1, res - 1) * C(n, res) % MOD * C(n - res, cnt) % MOD << "\n";
  }
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  work();
  for(cin >> t; t--; Solve()) {
  }
  return 0;
}

GYM 105350 F

题目描述

我们定义一个数组 \(B\) 的 \(\operatorname{MAD}(B)\) 为至少出现两次的最大值，如果没有数出现两次，则 \(\operatorname{MAD}(B)=0\)。

给定数组 \(A\)，求 \(\sum \limits_{l=1}^{N-1}\sum\limits_{r=l+1}^N \operatorname{MAD}([A_l,A_{l+1},\dots,A_r])\)。

思路

我们考虑固定 \(r\)，看对应的 \(l\) 和其 \(\operatorname{MAD}\)。图像如下：

image

接着我们考虑转移到 \(r+1\)：

image-20240927174226456

这里高出来了蓝色部分是因为 \(A_{r+1}\) 变得出现了两次，所以在这里会增加 \(\operatorname{MAD}\) 的值。这个很显然能用线段树维护。

空间复杂度 \(O(N)\)，时间复杂度 \(O(N\log N)\)。

代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAXN = 200001;

struct Segment_Tree {
  int l[MAXN << 2], r[MAXN << 2], lazy[MAXN << 2], id[MAXN << 2], Min[MAXN << 2];
  ll sum[MAXN << 2];
  void build(int u, int s, int t) {
    l[u] = s, r[u] = t, sum[u] = Min[u] = lazy[u] = 0;
    if(s == t) {
      id[u] = s;
      return;
    }
    int mid = (s + t) >> 1;
    build(u << 1, s, mid), build((u << 1) | 1, mid + 1, t);
  }
  void tag(int u, int x) {
    sum[u] = max(sum[u], 1ll * x * (r[u] - l[u] + 1)), Min[u] = max(Min[u], x), lazy[u] = max(x, lazy[u]);
  }
  void pushdown(int u) {
    tag(u << 1, lazy[u]), tag((u << 1) | 1, lazy[u]), lazy[u] = 0;
  }
  void update(int u, int s, int t, int x) {
    if(s > t) {
      return;
    }
    if(l[u] >= s && r[u] <= t) {
      tag(u, x);
      return;
    }
    pushdown(u);
    if(s <= r[u << 1]) {
      update(u << 1, s, t, x);
    }
    if(t >= l[(u << 1) | 1]) {
      update((u << 1) | 1, s, t, x);
    }
    sum[u] = sum[u << 1] + sum[(u << 1) | 1];
    Min[u] = min(Min[u << 1], Min[(u << 1) | 1]);
  }
  int Binary_Search(int u, int x) {
    if(Min[u] >= x) {
      return 1919810;
    }
    if(l[u] == r[u]) {
      return id[u];
    }
    pushdown(u);
    if(Min[u << 1] < x) {
      return Binary_Search(u << 1, x);
    }
    return Binary_Search((u << 1) | 1, x);
  }
  ll Getsum(int u, int s, int t) {
    if(s > t) {
      return 0ll;
    }
    if(l[u] >= s && r[u] <= t) {
      return sum[u];
    }
    pushdown(u);
    return (s <= r[u << 1] ? Getsum(u << 1, s, t) : 0ll) + (t >= l[(u << 1) | 1] ? Getsum((u << 1) | 1, s, t) : 0ll);
  }
}tr;

int t, n, a[MAXN];
ll ans;
map<int, int> id;

void Solve() {
  cin >> n;
  for(int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  tr.build(1, 1, n);
  id.clear();
  ans = 0;
  for(int i = 1; i <= n; ++i) {
    if(id.count(a[i])) {
      tr.update(1, tr.Binary_Search(1, a[i]), id[a[i]], a[i]);
    }
    ans += tr.Getsum(1, 1, i);
    id[a[i]] = i;
  }
  cout << ans << "\n";
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  for(cin >> t; t--; Solve()) {
  }
  return 0;
}

GYM 105350 G

题目描述

给定一个大小为 \(N\)，以 \(1\) 为根的树。最开始，所有结点的权值均为 \(0\)。有以下四种操作：

  • 令 \(u\) 子树内所有权值加 \(x\)。
  • 令 \(u\) 所有儿子权值加 \(x\)。
  • 查询 \(u\) 子树内权值最大值。
  • 查询 \(u\) 所有儿子权值最大值。

思路

由于在 dfs 序中一个结点的儿子是不连续的，所以我们考虑调整一下这个 dfs 序：

  • 当递归到结点 \(u\) 时，我们先把它的所有儿子丢进 dfs 序里。
  • 然后递归到它的所有儿子里。

这样很明显儿子就是连续的了，但子树却不一定连续。但通过观察可以发现，子树最多会被分成两个部分：根节点和除了根节点的部分。

所以使用线段树维护即可。

空间复杂度 \(O(N+M)\)，时间复杂度 \(O(Q\log N)\)。

代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAXN = 300005;

struct Segment_Tree {
  int l[MAXN << 2], r[MAXN << 2];
  ll Max[MAXN << 2], lazy[MAXN << 2];
  void build(int u, int s, int t) {
    l[u] = s, r[u] = t, Max[u] = lazy[u] = 0;
    if(s == t) {
      return;
    }
    int mid = (s + t) >> 1;
    build(u << 1, s, mid), build((u << 1) | 1, mid + 1, t);
  }
  void tag(int u, ll x) {
    Max[u] += x, lazy[u] += x;
  }
  void pushdown(int u) {
    tag(u << 1, lazy[u]), tag((u << 1) | 1, lazy[u]), lazy[u] = 0;
  }
  void update(int u, int s, int t, ll x) {
    if(s > t) {
      return;
    }
    if(l[u] >= s && r[u] <= t) {
      tag(u, x);
      return;
    }
    pushdown(u);
    if(s <= r[u << 1]) {
      update(u << 1, s, t, x);
    }
    if(t >= l[(u << 1) | 1]) {
      update((u << 1) | 1, s, t, x);
    }
    Max[u] = max(Max[u << 1], Max[(u << 1) | 1]);
  }
  ll Getmax(int u, int s, int t) {
    if(s > t) {
      return -(ll)(1e18);
    }
    if(l[u] >= s && r[u] <= t) {
      return Max[u];
    }
    pushdown(u);
    return max((s <= r[u << 1] ? Getmax(u << 1, s, t) : -(ll)(1e18)), (t >= l[(u << 1) | 1] ? Getmax((u << 1) | 1, s, t) : -(ll)(1e18)));
  }
}tr;

int n, q, dfn[MAXN], sz[MAXN], st[MAXN], End[MAXN], tot = 1;
vector<int> e[MAXN];

void dfs(int u, int fa) {
  sz[u] = 1, st[u] = tot + 1;
  for(int v : e[u]) {
    if(v != fa) {
      dfn[v] = ++tot;
    }
  }
  End[u] = tot;
  for(int v : e[u]) {
    if(v != fa) {
      dfs(v, u);
      sz[u] += sz[v];
    }
  }
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> q;
  for(int i = 1, u, v; i < n; ++i) {
    cin >> u >> v;
    e[u].emplace_back(v);
    e[v].emplace_back(u);
  }
  tr.build(1, 1, n);
  dfn[1] = 1;
  dfs(1, 0);
  for(int i = 1, op, u, x; i <= q; ++i) {
    cin >> op >> u;
    if(op == 1) {
      cin >> x;
      tr.update(1, dfn[u], dfn[u], x), tr.update(1, st[u], st[u] + sz[u] - 2, x);
    }else if(op == 2) {
      cin >> x;
      tr.update(1, st[u], End[u], x);
    }else if(op == 3) {
      cout << max(tr.Getmax(1, st[u], st[u] + sz[u] - 2), tr.Getmax(1, dfn[u], dfn[u])) << "\n";
    }else if(op == 4) {
      cout << tr.Getmax(1, st[u], End[u]) << "\n";
    }
  }
  return 0;
}

AT AGC023 F

题目描述

给定一个 \(N\) 个结点的树，每个结点上都有一个数字 \(0\) 或 \(1\)。你要将这些点排成一行，使得没有结点在其祖先之前。求这些节点上数的最小逆序对数量。

思路

我们考虑把哪个数放在前面更优

标签：return,训练,int,个数,cin,20240927,MAXN,随机,MOD
From： https://www.cnblogs.com/yaosicheng124/p/18436324

相关文章

  • 20240927
    FunisCounting我们可以发现数组\(a\)必须是\(x\)或\(x-1\),然后分类讨论即可#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=1e6+5,mod=998244353;intinv[N],f[N],g[N],t,n,a[N];intC(inta,intb){if(......
  • java窗口登录界面实现随机验证码
    创建窗口内容及验证码更换代码示例：packageframe;importjava.awt.event.ActionEvent;importjava.awt.event.ActionListener;importjavax.swing.JButton;importjavax.swing.JFrame;importjavax.swing.JLabel;importjavax.swing.JTextField;publicclassJframeexte......
  • 编码训练营的真相：投资还是风险？
    所以，如果你像大约7年前的我一样，你可能会问自己“我如何进入科技领域，找到一份软件开发人员的工作，并赚大钱？”或类似的东西。好吧，好消息是我可能有您正在寻找的答案！什么是编码训练营？编码训练营是一门类似课堂的结构化课程，可以在线或面对面，教您如何编码。听起来很简单，但实际上......
  • Python从0到100（五十八）：机器学习-随机森林及对复杂数据集分类
    随机森林通过构建多个决策树来完成分类或回归任务。随机森林的核⼼思想是通过多个弱学习器（决策树）的集成来构建⼀个强学习器，从⽽提⾼模型的泛化能⼒和稳定性。1.基本原理随机森林的基本原理如下：从训练集中随机抽取⼀定数量的样本（有放回抽样），构建⼀个决策树（称为⾃助采样法或......
  • CNN网络训练WISDM数据集：模型仿真及可视化分析
    卷积神经网络（CNN）因其强大的特征提取能力和深度学习架构而备受推崇，CNN在处理图像数据时展现出的卓越性能，使其成为解决各种视觉识别任务的首选工具。WISDM数据集是一个广泛用于运动估计研究的基准数据集，它包含了多个视频序列，每个序列都记录了摄像头在不同方向上移动时捕捉到的......
  • （6-3-03）CLIP模型训练与微调（3）训练模型+模型微调+调试运行
    6.3.4 训练模型文件train.py是训练CLIP模型的主程序，首先根据命令行参数指定的模型名称加载相应的配置文件，然后创建一个CLIPWrapper模型实例，并根据命令行参数初始化数据模块。接着，使用PyTorchLightning的Trainer对象进行训练。importyamlfromargparseimportA......
  • 代码随想录算法训练营第一天| 704. 二分查找、27. 移除元素、977.有序数组的平方。
    704.二分查找总结：防止int溢出：classSolution{public:intsearch(vector<int>&nums,inttarget){intleft=0;intright=nums.size()-1;while(left<=right){intmiddle=(left+right)/2;//intmid=(right-left)/......
  • 2024牛客暑期多校训练营1——A,B
    题解：更新：k=1的时候要乘n代码：#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=5e3+5;typedeflonglongll;typedefpair<int,int>PII;intT;intn,m,mod;intfac[N][N];intdp[N][N];intper[N];intpower(inta,int......
  • ShiftAddAug：基于乘法算子训练的最新无乘法网络方案 | CVPR'24
    不包含乘法的运算符，如移位和加法，因其与硬件的兼容性而日益受到重视。然而，采用这些运算符的神经网络（NNs）通常表现出比具有相同结构的传统NNs更低的准确性。ShiftAddAug利用成本较高的乘法来增强高效但功能较弱的无乘法运算符，从而在没有任何推理开销的情况下提高性能。将一个ShiftAd......
  • 2024.9.25训练记录
    上午whk下午noip模拟T1：结论题。考场想不出来。只需要顺序做第一个1前的数。原因：考虑三个数时的情况。顺序是\((a^b)^c\)或者\(a^{(b^c)}\)。相当于，比较\(b^c\)和\(bc\)的大小。显然有：\(b,c\geq2\)时，\(b^c\geqbc\)。所以按照正常顺序做，在\(A_i\geq2\)时......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99