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

做题记录4

CF577B.Modulo Sum

思路

求是否存在一段非空子序列的和模 \(m\) 的值为 \(0\) ,可以先等价地对每一个数字都模 \(m\) 。对于一个长度为 \(n\) 的序列,显然有 \(n\) 段前缀和,并且前缀和模 \(m\) 的值有 \([0, m)\)\(m\) 种。根据抽屉原理,当 \(n > m\) 时,一定有至少两段前缀和的值是相同的,而这两段前缀和相间得到的这一段连续子序列的和模 \(m\) 的值是 \(0\) ,符合要求。
也就是说,当 \(n > m\) 时一定是 YES

\(n \leq m\) 时,这个问题就转化为了一个 01背包,由于 \(m \leq 10^3\) ,因此可以直接计算。
\(f_{i, j}\) 表示从第 \(i\) 个数开始,能否通过选取一些数使得这些数的和模 \(m\) 的值为 \(j\) ,就有状态转移方程:

\[f_{i, j} |= f_{i - 1, j} \]

\[f_{i, (j + a_i) \mod m} |= f_{i - 1, j} \]

考虑边界,有:\(f_{i, a_i} = 1\)

最后只需要判断是否存在一个 \(f_{i, 0} = true\) 就可以了。

代码

void solve(void) {int n, m;std::cin >> n >> m;std::vector<int> a(n + 1);for(int i = 1; i <= n; i++) {std::cin >> a[i];a[i] %= m;}if(n > m) {std::cout << "YES\n";return;}std::vector<std::vector<int>> f(2020, std::vector<int>(2020));for(int i = 1; i <= n; i++) f[i][a[i]] = 1;for(int i = 1; i <= n; i++) {for(int j = 0; j < m; j++) {f[i][j] |= f[i - 1][j];f[i][(j + a[i]) % m] |= f[i - 1][j];}if(f[i][0]) {std::cout << "YES\n"; return;}}std::cout << "NO\n";
}

CF25D. Roads not only in Berland

思路

操作数显然是联通块的数量减一。接下来考虑如何构造出一种输出方式。

可以用并查集维护这张图,一个联通块可以删边当且仅当联通块是一个环,构成环的这条边是多余的。所以记录一下每个联通块多出来的多余边,并且记录每个联通块的根节点,之后就可以按照下面的方式输出:

环边的两个节点 联通块的根和下个联通块的根连一条新边

代码

struct DSU {std::vector<int> p, siz;DSU(int n): p(n + 1), siz(n + 1, 1) {std::iota(p.begin(), p.end(), 0);}int find(int x) {if(x == p[x]) return p[x];return p[x] = find(p[x]);}bool unite(int a, int b) {int pa = find(a), pb = find(b);if(pa == pb) return false;if(siz[pa] < siz[pb]) std::swap(pa, pb);p[pb] = pa;siz[pa] += siz[pb];return true;}bool same(int u, int v) {return find(u) == find(v);}int size(int u) {return siz[find(u)];}
};void solve(void) {int n; std::cin >> n;DSU dsu(n);std::vector<PII> del;for(int i = 1; i < n; i++) {int u, v; std::cin >> u >> v;if(!dsu.unite(u, v)) del.emplace_back(u, v);}std::vector<int> roots;for(int i = 1; i <= n; i++) {if(dsu.p[i] == i) {roots.push_back(i);}}std::cout << (int)roots.size() - 1 << '\n';for(int i = 0; i < (int)roots.size() - 1; i++) {int u = del[i].x, v = del[i].y;int a = roots[i], b = roots[i + 1];std::cout << u << ' ' << v << ' ' << a << ' ' << b << '\n';}
}
http://www.hskmm.com/?act=detail&tid=23416

相关文章:

  • 银河麒麟V10服务器桌面SP1、SP2、SP3国防版集采版国防集采版教育版
  • 完整教程:华为eNSP环境安装和命令使用教程
  • [IOI 1998 / USACO2.2] 派对灯 Party Lamps 题解 + bitset浅谈
  • 解题报告-小 A 的树
  • 【React 状态管理深度解析:Object.is()、Hook 机制与 Vue 对比实践指南】 - 教程
  • 2025 --【J+S 二十连测】-- 第一套 总结
  • LSTM
  • 调和级数
  • 【实验报告】华东理工大学随机信号处理实验报告 - 详解
  • 页面置换算法
  • 推进电子设计革新:仿真(Emulation)如何引领下一代验证方式
  • AT_abc309_g [ABC309G] Ban Permutation
  • 在Mac上运行Windows 365的完整指南
  • 摩刻S10 动感单车 速度传感器故障及更换!
  • 2025盐酸优质厂家权威推荐榜:高纯度盐酸的品质之选
  • 2025硫酸优质厂家权威推荐榜:高品质与强供应口碑之选
  • 2025冰乙酸供应厂家权威推荐榜:品质卓越与市场口碑双重保障
  • 工业氨水优质厂家推荐:实力制造商深度解析与选购指南
  • 2025液碱厂家权威推荐榜:实力供应商深度解析与选择指南
  • 2025片碱厂家权威推荐榜:优质供应与实力生产口碑之选
  • 2025阳离子聚丙烯酰胺厂家推荐榜:高效絮凝与定制解决方案
  • 2025硫铵厂家权威推荐榜:实力生产与优质供应口碑之选
  • 2025年硫酸铵厂家权威推荐榜:实力生产与优质供应口碑之选
  • 2025年硫化钠厂家权威推荐榜:优质供应商与实力制造商精选
  • 2025 年热压机厂家 TOP 企业品牌推荐排行榜,深度剖析河北热压机,廊坊热压机,霸州热压机推荐这十家公司!
  • 【Anthropic好文】AI 代理的高效上下文工程
  • 请求分页管理方式
  • vim中leader和localleader对比
  • 详细介绍:[论文阅读] AI + 软件工程 | 从“事后补救”到“实时防控”,SemGuard重塑LLM代码生成质量
  • 2025 年转基因小鼠公司 TOP 企业品牌推荐排行榜,传统 KO 转基因小鼠,条件性 cKO 转基因小鼠,ROSA26 位点基因 KI 小鼠,Tol2 转基因小鼠模型,点突变敲入转基因小鼠公司推荐!