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

QBXT2025S刷题 Day2

今天的题目

\(rk38\)

T1

这道题想了 \(1h\) 差不多。
这道题其实可以直接转化成选一个点,把覆盖着这个点线段全部删掉,使得左右两边都有线段。
可以维护每个点被多少个区间覆盖,左面有多少个区间,右面有多少个区间。
这个可以差分。
注意,\([1,6]\)\([7, 8]\) 之间是没有点的,但是他们之间的那一段也得考虑。
因此我们可以把所有区间都乘以 \(2\),就相当于在他们中间插入一个点。
这是代码:

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <ctime>using std::cin;
using std::cout;
const int N = 8e5 + 10;int l[(int)2e5 + 10];
int r[(int)2e5 + 10];
int rin[N];
int lin[N];
int cnt[N];
std::vector<int> p;void read(int &x)
{char c = getchar();x = 0;int f = 1;while (c < '0' || c > '9'){if (c == '-')f = -f;c = getchar();}while (c >= '0' && c <= '9'){x = x * 10 + c - '0';c = getchar();}x = x * f;
}int main()
{int t;read(t);while (t--){p.clear();memset(lin, 0, sizeof(lin));memset(rin, 0, sizeof(rin));memset(cnt, 0, sizeof(cnt));int n;read(n);for (int i = 1; i <= n; ++i){read(l[i]);read(r[i]);p.push_back(l[i]);p.push_back(r[i]);}std::sort(p.begin(), p.end());p.erase(std::unique(p.begin(), p.end()), p.end());int maxval = 0;for (int i = 1; i <= n; ++i){l[i] = std::lower_bound(p.begin(), p.end(), l[i]) - p.begin() + 1;r[i] = std::lower_bound(p.begin(), p.end(), r[i]) - p.begin() + 1;l[i] *= 2;r[i] *= 2;cnt[l[i]]++;cnt[r[i] + 1]--;maxval = std::max(maxval, r[i]);}for (int i = 1; i <= n; ++i){rin[1]++;rin[l[i]]--;lin[r[i] + 1]++;lin[maxval + 1]--;}int ans = 1e9 + 7;for (int i = 1; i <= maxval; ++i){cnt[i] += cnt[i - 1];lin[i] += lin[i - 1];rin[i] += rin[i - 1];if (lin[i] && rin[i])ans = std::min(ans, cnt[i]);}if (ans == 1e9 + 7)cout << -1 << '\n';elsecout << ans << '\n';}return 0;
}

T2

这道题有一个结论部分分,就是 \(q = 0\) 的时候。
考虑在第一列随便放,然后容易证明,后面 \(m - 1\) 列每一列要么和前一列一样,要么是前一列取反。
所以答案是 \(2^n * 2^{m - 1}\)
然后在对第一个部分分暴力就行。

正解:

结论:\(a_{i,j} = a_{i - 1, j} \oplus a_{i, j - 1} \oplus a_{i - 1, j - 1}\)
易推出:\(a_{i,j} = a_{1, 1}\oplus a_{i, 1}\oplus a_{1, j}\)
因此,如果我们已经知道 \(a_{i,j}\)
假设 \(a_{1, 1} = 0,1\)
这个可以通过 \(\mathcal{2-SAT}\) 建边。
如果无解,就是 \(0\)
如果有解,就是 \(2^{\frac{连通块个数}{2}}\)

#include <iostream>using std::cin;
using std::cout;
const int N = 6e5 + 10;
const int mod = 1e9 + 7;int n, m, q;
int cnt;
int go[N << 1];
int pow2[N << 1];int find(int x)
{if (go[x] == x)return x;return go[x] = find(go[x]);
}
void merge(int x, int y)
{x = find(x);y = find(y);if (x != y){go[x] = y;cnt--;}
}
void read(int& x)
{x = 0;char c = getchar();int f = 1;while (!isdigit(c)){if (c == '-')f = -f;c = getchar();}while (isdigit(c)){x = x * 10 + c - '0';c = getchar();}x = x * f;
}int main()
{int n, m, q;read(n), read(m), read(q);cnt = 2 * (n + m);pow2[0] = 1;for (int i = 1; i <= 2 * (n + m); ++i)go[i] = i;for (int i = 1; i <= 2 * (n + m); ++i)pow2[i] = 1ll * pow2[i - 1] * 2 % mod;cout << pow2[n + m - 1] << '\n';bool f = true;while (q--){int x, y, c;read(x), read(y), read(c);if (!f){cout << 0 << '\n';continue;}merge(x, y + n + c * (n + m));merge(x + n + m, y + n + (!c) * (n + m));if (find(x) == find(x + n + m)){cout << 0 << '\n';f = false;}elsecout << pow2[cnt / 2 - 1] << '\n';}return 0;
}

T3

\(3\) 个部分分可以输出字符串的大小。
结论:答案是
\(\displaystyle\sum^n_{d = 1}\dfrac{\lfloor\dfrac{n}{d}\rfloor}{\displaystyle\prod_{i \in colors} \text{cnt}_i!}\)

T4

不会。
听不懂。
Pasted image 20251003213840

http://www.hskmm.com/?act=detail&tid=23795

相关文章:

  • PyCharm中搭建PyTorch和YOLOv10开发环境 - 实践
  • 基于PCIe(XDMA)的多路(1-32路)信号采集与回放子系统, 多路视频、AD、光纤等信号,支持PR over PCIe
  • Spring事务管理:@Transactional注解
  • AI元人文的未来:软硬件协同发展研究报告——声明Ai研究
  • 个人主页网址
  • 10.3考试t3(similarity)solution
  • 安卓渗透测试流
  • 日志|寻找旋转排序数组中的最小值|寻找两个正序数组的中位数|二分查找
  • 有关三角剖分的性质
  • 西门子通信-自制示意
  • Vue之刷新页面会触发的生命周期函数
  • 傅里叶的一生
  • Dos命令学习(新手)
  • 吴恩达深度学习课程一:神经网络和深度学习 第一周:深度学习简介
  • 实用指南:AI Agent开发平台如何设计?核心架构与工作流实战案例详解
  • Numercial result of HAA-DRSM
  • 防重复提交的实现
  • Day25错误(error)与异常(exception)的简单认识
  • 算法课第一次作业
  • 1. 对拍板子
  • Luogu P14122 [SCCPC 2021] Direction Setting题解 最小费用流
  • MySQL_基础
  • 5 qoj14553 序列与整数对 题解
  • AT_arc064_d [ARC064F] Rotated Palindromes
  • vscode代码块格式转换器
  • 二分模板
  • 如何控制事务?
  • C语言速成秘籍——跳转语句(goto) - 实践
  • 五子棋-下满了格子平局
  • 从免疫原性突破到技术迭代:全人源抗体如何重塑靶向治疗格局?