Q779’s Blog

CF645D Robot Rapping Results Report 题解 题目链接：CF645D Robot Rapping Results Report 题意： \(n\) 个机器人，每个机器人有一个不同的级别，级别介于 \(1\sim n\)，高级别的可以打败低级别的，现在给出 \(n\) 个机器人的 \(m\) 场比赛胜负情况，问最少需要前几场比赛就可以确定每个机器人的级别。 输入格式 第一行两个整数 \(n\) 和 \(m\) 表示机器人个数和比赛场数，之后 \(m\) 行每行两个整数 \(u\) 和 \(v\) 表示机器人 \(u\) 打败机器人 \(v\)。 输出格式 如果这 \(m\) 场比赛可以确定每个机器人的级别则输出最少需要前几场比赛就可以确定，否则输出 \(-1\)。 数据范围 \(2\leq n\leq 10^5\)，\(1\leq m\leq \min(\frac{n\times (n-1)}{2},10^5)\)。 不难发现这里有个单调性 即越多的边越有可能确定每个机器人的级别 当然如果所有边都不能确定的话，就输出无解即可 所以解法一：二分可能...

OI易错点-C++语法 不保证本文内容完全正确，仅仅是个人总结！！ islower，isalpha，isdigit 这种函数，返回值不是bool！！ 在不同的机器上跑出来是不一样的！！！！不要直接加上它！！! lower_bound(begin,end,x,greater<int>()) 返回第一个小于等于 \(x\) 的位置 去重 m=unique(b+1,b+1+n)-b-1; string 的 == 和 find() 是 \(O(n)\) 的！ 注意 char 数组后面有个 \0 ，因此多测一般不用清空，但是\0后面的不会被清空！ next_permutation(a+1,a+1+n) 是下一个排列！到了5 4 3 2 1这种就结束了！！ 同理有 prev_permutation(a+1,a+1+n) 凡是位运算都加个括号，比如 \(\&\) 的优先级比 == 还要低！！！（待考证） 判断两数的奇偶性是否相同不可以用异或！因为高位还有数！ __gnu_pbds的头文件可以用 #include <bits/extc++.h> memcpy(a,...

洛谷P2704 [NOI2001] 炮兵阵地 题解 题目链接：P2704 [NOI2001] 炮兵阵地 题意： 司令部的将军们打算在 \(N\times M\) 的网格地图上部署他们的炮兵部队。 一个 \(N\times M\) 的地图由 \(N\) 行 \(M\) 列组成，地图的每一格可能是山地（用 \(\texttt{H}\) 表示），也可能是平原（用 \(\texttt{P}\) 表示），如下图。 在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示： 如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。 图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。 现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。 对于 \(100\%\) 的数据，\(N\le 100\)，\...

CF898F Restoring the Expression 题解 题目链接：CF898F Restoring the Expression 题意： 给你一个数字字符串s，现在你要这个字符串切割成三个部分a,b,c, 即s=a+b+c(这里的+为字符串相加，即后面的字符串拼接在前面的字符串后面) 同时要满足a，b，c三个字符串代表的十进制数字满足 a+b=c (注意a,b,c都不能有前导0，如数字 0099 是非法的) 问是否有这样一种分隔方式,题目保证有一组解，输出+号最靠前的一组答案 输入一行一个字符串s, 输出一行，形如a+b=c，满足s=a+b+c（注意要输出'+'号和'='号） |s|<=1e6,'0'<=si<='9' input: 12345168 output: 123+45=168 模拟赛秒出结论，结果脑抽挂了。。 这题是字符串哈希，其实很好想 一般的字符串哈希函数都是这么定义的 ...

CF808G Anthem of Berland 题解 题目链接：CF808G Anthem of Berland 题意： 给定 \(s\) 串和 \(t\) 串，其中 \(s\) 串包含小写字母和问号，\(t\) 串只包含小写字母。 假设共有 \(k\) 个问号。 你需要给把每个问号变成一个小写字母，共有 \(26^k\) 种可能。 对于每种可能，设 \(t\) 匹配 \(s\) 的次数为 \(f_i\)，请输出 \(\max(f_i)\) 。 \(1\leq |s|,|t|\leq 10^5,|s|\times |t|\leq 10^7\) 样例三告诉你了，这题不是贪心。 设 \(f_i\) 表示前 \(i\) 个字符的最大答案 似乎不好转移，因为我们不知道上一个放的 \(t\) 在哪里 显然 \(f_i\) 可以从 \(f_{i-m}\) 转移过来，因为这里正好可以放得下一个 \(t\) 但是 \(t\) 是可以重叠放的，例如 \(t=\tt{aabaa}\) 于是我们直接跳 \(m\) 的 \(\tt{fail}\) 数组，然后一个个转移吗？ 不，因为我们不知道 \(...

密码生成器 简单的小破密码生成器 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...