Q779’s Blog

密码生成器 简单的小破密码生成器 qwq 也不知道搞了这个有啥用处 目前还比较脆弱，不支持不合法输入 反正就是个瞎搞的东西 qwq 代码： /* Name: 密码生成器1.0 Author: q779 Date: 2021.5.20 Function: { 可以生成长度4-256的密码 允许包含数字、大小写字母以及部分特殊字符 可以用于制作密码字典 } */ #include <iostream> #include <string> #include <vector> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iomanip> #include <random> using namespace std; #define num_start 0 #define num_end 9 #define Uppe...

三子棋模拟器 for linux 中考前一周开摆写的 采用的是minimax算法和 \(\alpha - \beta\) 剪枝 目前是基于规则的估价函数（因为q779不会AI） 目前在含C++环境的 ubuntu20.04 和 macOS Monterey 12.4下都是可以编译的 代码： //###### // // 三子棋 for linux // Dev By q779 // First Update 2021.6.6 // Latest Update 2022.7.23 // AI LEVEL 1.0 // //###### #include <iostream> #include <string> #include <vector> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iomanip> #incl...

洛谷P3538 [POI2012]OKR-A Horrible Poem 题解 题目链接：P3538 [POI2012]OKR-A Horrible Poem 题意： 给出一个由小写英文字母组成的字符串S，再给出q个询问，要求回答S某个子串的最短循环节。 如果字符串B是字符串A的循环节，那么A可以由B重复若干次得到。 第一行一个正整数n(n≤500 000)，表示S的长度。 第二行n个小写英文字母，表示字符串S。 第三行一个正整数q(q≤2 000 000)，表示询问次数。 下面q行每行两个正整数a,b(1≤a≤b≤n),表示询问字符串S[a…b]的最短循环节长度。 考虑循环节与原串的关系 首先循环节的长度一定是原串长度的因数 这样枚举长度就可以 \(O(\log n)\) 了 具体地，用欧拉筛预处理出 \(1\sim n\) 中所有数的最小因数 \(g_i\) ， 然后直接跳 \(g\) 数组即可 那么确定是否是原串的循环节呢？ 设当前枚举的串为 \(A\) （不是在说字符 \(\tt{A}\) 哦） 如果它是循环节，那么原串一定长这样 \[ A\dots AA ...

CF888E Maximum Subsequence 题解 题目链接：CF888E Maximum Subsequence 题意： 给定N个数，第i个数的值为Ai，你现在可以从中选择一些数字，问选出数字的和模P最大为多少。 输入第一行为N,P 第二行为N个数，第i个数字为Ai 1<=n<=35,1<=P<=1e9,0<=Ai<=1e9 模拟赛合并复杂度寄了，特写此篇题解 这个 \(n\le 35\) 就很明显是折半搜索 我们用 \(p,q\) 两个数组记录两部分搜索出来的所有可能的数 \(2^{17}=131072\) ，因此数组完全够 关键在于如何合并两部分的答案 直接两层循环枚举那么复杂度依旧是 \(O(2^n)\) （我就是这么寄的） 注意到 \(p,q\) 满足 \(0\le p_i,q_j<m\) 因此对于每个 \(p_i\) 我们只要找到最大的一个 \(q_j\) 满足 \[ p_i+q_j<m \] 正确性显然。 这样只要排个序然后维护双指针就好了 时间...

洛谷P1879 [USACO06NOV]Corn Fields G 题解 题目链接：P1879 [USACO06NOV]Corn Fields G 题意： 农场主 \(\rm John\) 新买了一块长方形的新牧场，这块牧场被划分成 \(M\) 行 \(N\) 列 \((1 \le M \le 12; 1 \le N \le 12)\)，每一格都是一块正方形的土地。 \(\rm John\) 打算在牧场上的某几格里种上美味的草，供他的奶牛们享用。 遗憾的是，有些土地相当贫瘠，不能用来种草。并且，奶牛们喜欢独占一块草地的感觉，于是 \(\rm John\) 不会选择两块相邻的土地，也就是说，没有哪两块草地有公共边。 \(\rm John\) 想知道，如果不考虑草地的总块数，那么，一共有多少种种植方案可供他选择？（当然，把新牧场完全荒废也是一种方案） 状压经典题 首先把每一行的情况压到状态 \(F_i\) 中 可以预处理所有状态（选择哪些种草）在行上是否合法 例如两块草不能相邻选，当然此时不用考虑可不可以种 判断依据如下 int mx=1<<n; for(int i=...

洛谷P2900 [USACO08MAR]Land Acquisition G 题解 题目链接：P2900 [USACO08MAR]Land Acquisition G 题意： Farmer John 准备扩大他的农场，眼前他正在考虑购买 \(N\) 块长方形的土地。 如果 FJ 单买一块土地，价格就是土地的面积。但他可以选择并购一组土地，并购的价格为这些土地中最大的长乘以最大的宽。比如 FJ 并购一块 \(3 \times 5\) 和一块 \(5 \times 3\) 的土地，他只需要支付 \(5 \times 5=25\) 元， 比单买合算。 FJ 希望买下所有的土地。他发现，将这些土地分成不同的小组来并购可以节省经费。 给定每份土地的尺寸，请你帮助他计算购买所有土地所需的最小费用。 第一行一个整数 \(N\)（\(1 \leq N \leq 5 \times 10^4\)）。 接下来 \(N\) 行，每行两个整数 \(w_i\) 和 \(l_i\)，代表第 \(i\) 块土地的长和宽。保证土地的长和宽不超过 \(10^6\)。 输出买下所有土地的最小费用。 斜率优化板子题...

CF479E Riding in a Lift 题解 题目链接：CF479E Riding in a Lift 题意： 现在有n个传送点呈序列排列，编号为1到n 每一次可以通过折跃从一个传送点传送到另一处传送点， 由于折跃需要消耗巨大的能量，因此每次传送的距离小于出发传送点到能量水晶的距离，能量水晶在编号为b的传送点上， 即对于编号为x的出发点，目标传送点的编号y要满足如下的要求： |x-y|<|x-b| (x≠y) 同时，由于能量水晶储存着巨大的能量，严禁随意接近，因此你不能传送到b号传送点。 无聊的你想知道，在a号传送点的你，经过k次折跃之后，能有多少种不同的传送点访问序列 输入一行四个数： n,a,b,k， 其中 2≤n≤5000,1≤k≤5000,1≤a,b≤n,且保证a≠b 输出一行为总的序列数，答案要对1000000007取模（1e9+7） dp大水题，模拟赛花了十几分钟就A了 用刷表法更新答案 每个点 \(j\) （除了 \(b\) ，它不更新）能更新的范围都是 \[ \left[\max(1,j-|j-b|+1),j) \cup (j,\min(n...

洛谷P2657 [SCOI2009] windy 数 题解 题目链接：P2657 [SCOI2009] windy 数 题意： 不含前导零且相邻两个数字之差至少为 \(2\) 的正整数被称为 windy 数。windy 想知道，在 \(a\) 和 \(b\) 之间，包括 \(a\) 和 \(b\) ，总共有多少个 windy 数？ 对于全部的测试点，保证 \(1 \leq a \leq b \leq 2 \times 10^9\)。 常规的数位dp，只需要记录上一位的数字即可 但是注意，最高位是不需要限制的 具体的，我们是从高位往低位做dp的 至于为什么高位往低位做dp，可以看下面的解释 因为低位开始会导致无法判断是否超过了当前的限制 例如 \(4234\) ，假设我们从高位开始做 如果以 \(4\) 开始，可以发现接下来一位不能超过 \(3\) 如果用 \(0 \sim 3\) ，则接下来没有任何限制 但是如果我们从低位开始做，比如填了一个 \(8\) 那么最后我们有可能推出来个 \(4238\) 之类的 因为无法判断 回到刚刚的问题，我们从高位往低位做数位dp 那么第...

洛谷P1410 子序列 题解 题目链接：P1410 子序列 题意： 给定一个长度为 \(N\)（\(N\) 为偶数）的序列，问能否将其划分为两个长度为 \(N / 2\) 的严格递增子序列。 【数据范围】 共三组数据，每组数据行数<=50，0 <= 输入的所有数 <= 10^9 第一组(30%)：N <= 20 第二组(30%)：N <= 100 第三组(40%)：N <= 2000 首先可以有个原始的思路 设 \(f_{i,j,k}\) 表示前 \(i\) 位，以 \(i\) 结尾的上升子序列长度为 \(j\) ，另一个上升子序列以 \(k\) 结尾是否可行。 如果仅仅用是否可行去做，比较浪费。 注意到我们一定希望 \(a_k\) 尽可能小，这个很好用dp去算 考虑把 \(k\) 这一维去掉，移到 \(f\) 里让它算。 设 \(f_{i,j}\) 表示以 \(i\) 结尾的上升子序列长度为 \(j\) ，不以 \(i\) 结尾的另一条上升子序列的结尾的最小值。 如果 \(a_i < a_{i+1}\) ，那么 \(a_{i+1}\...

CF914D Bash and a Tough Math Puzzle 题解 题目链接：CF914D Bash and a Tough Math Puzzle 题意： 给定长度为 \(n\) 的序列 \(a\)。\(m\) 次操作。操作有两种： 1 l r x：若能在 \(a_l\sim a_r\) 中 至多 修改一个数，使得 \(\gcd(a_l,a_{l+1},\cdots,a_r)=x\)，输出 YES，否则输出 NO。注意：我们不需要进行实际的改动。 2 i y：将 \(a_i\) 修改为 \(y\)。 \(1\le n\le 5\times 10^5\)，\(1\le m\le 4\times 10^5\)，\(1\le a_i,x,y\le 10^9\)。 设区间内不能被 \(x\) 整除的数的个数为 \(\text{cnt}\) 若 \(\text{cnt}=0\) ，则改不改无所谓 若 \(\text{cnt}=1\) ，则直接把那个数修改为 \(x\) 即可 若 \(\text{cnt}>1\) ，则无解，输出NO 考虑用线段树维护区间 \...

CF475D CGCDSSQ 题解 题目链接：CF475D CGCDSSQ 题意： 给出一个长度为 \(n\) 的序列和 \(q\) 个询问， 每个询问输出一行，询问满足 \(\gcd\{a_l,a_{l+1},\dots,a_r\}=x\) 的 \([l,r]\) 的对数 \(1 \le n \le 10^5,~1 \le q \le 3 \times 10^5,~1 \le a_i,x_i \le 10^9\) 这题有一个很有趣的结论。 区间 \(\gcd\) 最多有 \(\mathcal{O}(n\log \omega)\) 种可能的值（记 \(\omega = \max\{a_i\}\)） 即 \(l\) 固定时，\([l,r]\) 的区间 \(\gcd\) 至多有 \(\mathcal{O}(\log \omega)\) 种取值。 证明： 假设区间 \(\gcd\) 在 \(i\) 处发生了变化，此时新的 \(\gcd\) 一定是原 \(\gcd\) 的因数 因此新的 \(\gcd\) 至少缩小了一半，则至多有 \(\mathcal{O}(\log \omega)\...

洛谷P6225 [eJOI2019] 异或橙子 题解 题目链接：P6225 [eJOI2019] 异或橙子 题意： 序列上有n个值，第i个值为Ai 一段区间[l,r]的异或和为 A(l)^..^A(r) 一段区间[l,r]的答案是把所有区间[i,j]的异或和结果异或起来(l<=i<=j<=r) 例如 区间[2,4]的答案为 A2^A3^A4^(A2^A3)^(A3^A4)^(A2^A3^A4) 现在给定m次操作： 第一种操作输入i,j,将Ai值修改为j 第二种操作输入i,j,求区间[i,j]的答案 输入第一行为n,m 第二行n个值，为A1,...An 之后m行， 每一行输入操作的类型和对应的i,j 对于每个第二类操作，输出区间答案 n,m<=2e5 其实就是单点修改+查询下面这个柿子 \[ \bigoplus_{i=l}^{r}\bigoplus_{j=i}^{r}a_j \] 考虑区间中一个数的出现次数 设 \(l \le i \le r\) ，则 \(i\) 在区间 \([l,r]\) 的异或和的异...