牛客周赛round35
title: 牛客周赛round35categories: - ICPCtags: - nullabbrlink: 6aff6830date: 2023-01-25...
关于位运算的一些需要搞清楚的边界
title: 关于位运算的一些需要搞清楚的边界categories: - ICPCtags: - nullabbrlink: 692da4c5date: 2023-01-22 00:00:00 最大的 int 型整数在二进制形式下表示为 0111 1111 1111 1111 1111 1111 1111 1111。这是一个 32 位的二进制数，其中最高位为符号位（0 表示正数），其余的位全部为 1。 这个二进制数对应的十进制值为 (2^{31} - 1)，即 2,147,483,647。 所以只有31位，>>30就可以取到最高位（在正数int范围内）
01trie特训2
title: 01trie特训2categories: - ICPCtags: - nullabbrlink: a2310147date: 2023-01-17 00:00:0001trie特训2题意：给定一个含有 n 个元素的数组 Ai，你可以选择两个不相交的子段。求出这两个子段内的数的异或和的差值的最大值。Sol：考虑枚举两段的分界点，对于较短的两段来说可能会有多个分界点但这样我们求的是答案的超集，一定会包括答案的。对于一个分界点，我们先考虑如果要求以左边区间必须包含分界点，那么我们只需要异或前缀和后找一个位置和它异或最大或最小，这是经典的01trie的应用。再考虑右边，我们需要做后缀异或和，做跑一遍trie。注意实际上可以不以分界点为选取的子段的端点，我们需要需要维护异或后结果的前缀最大值，后缀最小值，剩下同理。debug：我自己实现不好写的原因是没开第二个后缀异或和，在那一直用前缀和偏移位置，边界不好处理。//trie树 + 前缀异或和 + 枚举 #include<bits/stdc++.h> #define endl...
SDUT OJ——基于hh的项链的维护区间种类数
title: SDUT OJ——基于hh的项链的维护区间种类数categories: - ICPCtags: - nullabbrlink: 8d705e88date: 2023-01-09 00:00:00hh的项链：不带修改维护区间种类数https://www.luogu.com.cn/problem/P1972#submit 山东理工大学系列赛https://acm.sdut.edu.cn/onlinejudge3/contests/4125/problems/D Description给定一个长度为 $n$ 的序列 $a$ 和 $m$ 次询问，对于第 $i$ 次询问给定两个正整数 $[l, r]$，判断 $a_l \sim a_r$ 是否为合法序列。 定义：若区间 $[l, r]$ 中存在一个数 $a_i$ $(l \le i \le r)$ 出现在 $[1, l - 1]$ 或 $[r + 1, n]$ 中则为不合法序列。 Input输入的第一行包含两个正整数 $n, m$ $(1 \le n, m \le 10 ^ 5)$ 输入的第二行包含 $n$ 个数...
bitset专题
title: bitset专题categories: - ICPCtags: - nullabbrlink: e4c46669date: 2023-01-04 00:00:00bitsetbitset前身：普通状态压缩的优化以cf937G为例,对于邻接矩阵的由二维压缩到一维#include <bits/stdc++.h> using i64 = long long; void solve() { int n; std::cin >> n; std::vector<std::string> g(n), w(n); for (int i = 0; i < n; i++) { std::cin >> g[i] >> w[i]; } std::vector<int> e(n); for (int i = 0; i < n; i++) { for...