牛客周赛round35
title: 牛客周赛round35 categories: ICPC tags: null abbrlink: 6aff6830 date: 2023-01-25 00:00:00 赛时由于思考问题不清晰，感觉仔细思考一会就不行了，侥幸过了最短路的构造题，写的时候也是不顺利，构造也确实没怎么练过。 E题就是个给你从1出发的最短路的结果，要求你给出图的构造，这种反向题目还真没仔细思考过。 此外特殊的是本题是无向图且所有边权为1，边权为1应该联想bfs，然后想到bfs根据到出发点的距离将图分为层，所以我们可以构造一棵树，每个点的到根的路径唯一，最短路就是深度。 做法：题目给定了边的数量m，考虑合法范围内的m的下界就是n-1个点，上界呢？ 思考哪些边加了也不会影响最短路 1.同层的点相互连边 2.距离为1的点的相互连边 可以提前算出来m的最大值，然后把m过大的情况判掉。 对于合法情况：我们保证把建树的边用掉，剩余多出来的边从上面两类中不断加，直到总边数==m ...
关于位运算的一些需要搞清楚的边界
title: 关于位运算的一些需要搞清楚的边界 categories: ICPC tags: null abbrlink: 692da4c5 date: 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特训2 categories: ICPC tags: null abbrlink: a2310147 date: 2023-01-17 00:00:00 01trie特训2 题意：给定一个含有 n 个元素的数组 Ai，你可以选择两个不相交的子段。求出这两个子段内的数的异或和的差值的最大值。 Sol：考虑枚举两段的分界点，对于较短的两段来说可能会有多个分界点但这样我们求的是答案的超集，一定会包括答案的。对于一个分界点，我们先考虑如果要求以左边区间必须包含分界点，那么我们只需要异或前缀和后找一个位置和它异或最大或最小，这是经典的01trie的应用。再考虑右边，我们需要做后缀异或和，做跑一遍trie。注意实际上可以不以分界点为选取的子段的端点，我们需要需要维护异或后结果的前缀最大值，后缀最小值，剩下同理。 debug：我自己实现不好写的原因是没开第二个后缀异或和，在那一直用前缀和偏移位置，边界不好处理。 //trie树 + 前缀异或和 + 枚举 #include<bits/stdc++.h> #define endl...
SDUT OJ——基于hh的项链的维护区间种类数
title: SDUT OJ——基于hh的项链的维护区间种类数 categories: ICPC tags: null abbrlink: 8d705e88 date: 2023-01-09 00:00:00 hh的项链：不带修改维护区间种类数 https://www.luogu.com.cn/problem/P1972#submit 山东理工大学系列赛 https://acm.sdut.edu.cn/onlinejudge3/contests/4125/problems/D Description 给定一个长度为 nnn 的序列 aaa 和 mmm 次询问，对于第 iii 次询问给定两个正整数 [l,r][l, r][l,r]，判断 al∼ara_l \sim a_ral∼ar 是否为合法序列。 定义：若区间 [l,r][l, r][l,r] 中存在一个数 aia_iai (l≤i≤r)(l \le i \le r)(l≤i≤r) 出现在 [1,l−1][1, l - 1][1,l−1] 或 [r+1,n][r + 1, n][r+1,n]...
bitset专题
title: bitset专题 categories: ICPC tags: null abbrlink: e4c46669 date: 2023-01-04 00:00:00 bitset bitset前身：普通状态压缩的优化 以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++) { ...