- 博客(64)
- 收藏
- 关注
RSS订阅原创 奖励关题解
题目传送门我就是一个成功的反例…直接正着推，直接推成了憨憨思路首先我们看题：n<=15n<=15n<=15，灵光一闪。淦哪！我们可以很肯定这是一个状压DP+DP+DP+期望DPDPDP。状态也十分清楚：f[i][j]f[i][j]f[i][j]为从到第iii轮，状态为jjj的最大期望值。然后再推到最后…如果你到了这个地步，那你就成功地和我一样成为铁憨憨了。因为f[i][j]f[i][j]f[i][j]这个状态可能在之前的iii轮中达不到jjj这个状态…那怎么办？怎么办
2021-01-16 15:22:20
245
原创 次短路 && k短路
文章目录次短路再了解次短路与kkk短路之前，我们先了解一下最短路。次短路次短路就是简化版的kkk短路，我们先把这个了解了。题目传送门这是一道典型的次短路问题。我们都知道次短路是由最短路改变而来的。但我们怎么改？什么时候改？那当然是修改的时候啦。我们再更新最短路时就把次短路更新掉。我们定义dist_fdist\_fdist_f为最短路，dist_sdist\_sdist_s为次短路。则我们更新有三种情况：1.当dist_f[v]>dist_f[u]+wdist\_f[v]>d
2020-12-21 13:51:45
214
原创 A*算法
文章目录思想基本准则A∗A^*A∗算法，又叫做A−starA-starA−star算法，是一种静态路网中求解最短路径最有效的直接搜索方法。思想我们首先来回忆一下BFSBFSBFS算法，我们的BFSBFSBFS算法每次都是从堆顶取出当前代价最小的状态进行扩展。那最先扩展到的就是最优的。但我们BFSBFSBFS算法这种贪心思想是不完善的：我们虽然当前的代价小，但不能保证后来的代价也小（正所谓目光短浅）。这样就会使搜索量增大。我们的A∗A^*A∗算法就是加上一个估价函数：不断从堆中取出“当前代价+预估代
2020-12-19 17:08:51
444
1
原创 k短路题解
文章目录思路代码题目传送门思路我们反向建一个图，跑一个最短路，这个值就作为估计函数。然后跑A∗A^*A∗算法就结了。代码#include <bits/stdc++.h>#include <queue>using namespace std;const int maxn=55,maxm=2500;int n,m,k,s,t;void read(int &x) { int f=1; x=0; char ch=getchar(); while(ch<
2020-12-19 17:08:09
150
1
原创 鱼肉炸弹题解
文章目录题目题目描述输入格式输出格式样例数据范围与提示思路建树DPDPDP代码题目题目描述舒克和贝塔终于下定决心要去营救被关押在众猫聚居的AAA城中的大米。AAA城的构造是很奇怪的。AAA城中的所有NNN栋建筑沿着一条直线排列，没有两栋楼的高度相同，而大米就被关押在其中的某栋建筑中。每一栋建筑的顶上都有一些猫在看守。如果按照从一端到另一端的顺序将所有的建筑编号为111~NNN，那么第iii栋建筑的高度为HiHiHi，顶上开始时的猫的数量为CiCiCi。每一只猫不但可以看守住其所在建筑的楼顶，还可以
2020-12-15 13:31:05
129
原创 二叉苹果树
文章目录思路代码题目传送门思路这道题就是一道比较经典的树形DPDPDP。我们令f[i][j]f[i][j]f[i][j]为以iii为根，保留jjj条边的最大值 。我们的状态转移方程式就为:f[u][j]=max(f[u][j],f[u][j-k-1]+f[v][k]+w);我们需要保留jjj条树枝，我们就在以uuu为根的树中选择另外j−k−1j-k-1j−k−1条树枝，然后再在以vvv为根的树中再选择kkk条树枝。那有些人就有疑问了，我们还有一条树枝呢？就是u→vu\rightarrow
2020-12-14 13:11:31
88
原创 求逆序对的各种算法
文章目录1.冒泡排序思想代码：2.归并排序思想代码3.树状数组思想代码线段树思想设AAA为一个有nnn个数字的有序集(n>1)(n>1)(n>1)，其中所有数字各不相同。如果存在正整数i,ji,ji,j使得1≤i<j≤n1 ≤ i < j ≤ n1≤i<j≤n而且A[i]>A[j]A[i] > A[j]A[i]>A[j]，则<A[i],A[j]><A[i], A[j]><A[i],A[j]>这个有序对称为AAA的一
2020-12-03 19:21:34
1802
2
原创 扫雷题解（暴力 && DP）
文章目录暴力思路代码DPDPDP思路代码题目传送门暴力我们的暴力很暴力。（不愧是暴力）DFSDFSDFS我…我TMTMTM还打DPDPDP。思路直接暴搜，每搜一格判断上格可不可以，所以我们要到了n+1n+1n+1才能判断是否符合要求。可以使用剪枝，否则会TLETLETLE。我们对于每个点只有两种方案：有无雷。至于剪枝：我们对于第xxx点进行选择后，看x−1x-1x−1这个点是否符合要求（我们x+1x+1x+1没确定，所以不能看xxx点是否符合要求）。代码#include <bi
2020-11-25 20:15:25
1112
原创 杯子题解
文章目录题目描述思路代码题目描述重庆八中在808080周年校庆的时候获捐nnn个杯子， 每个杯子有两个属性：一个是已装水量aiaiai，一个是可装水量bibibi（ai<=biai <= biai<=bi）。从一个杯子向另一个杯子倒xxx单位体积的水需要花费的时间是xxx秒。 现在用nnn 个杯子中的kkk个来装所有的水， 求最小的kkk， 以及最少花费的时间 ttt。第一行：一个正整数n（1<=n<=100）n（1 <= n <= 100）n（1<
2020-11-14 17:31:47
709
原创 2020 CSP-J 题解
文章目录T1T2T3T4T1题目传送门这道题就是一道水题，如果我们的正整数%2=1\%2=1%2=1的话，我们就输出−1-1−1；否则，我们就拆分。#include <bits/stdc++.h>using namespace std;int n;int main() { scanf("%d",&n); if(n%2) printf("-1"); else { for(int i=int(log(n)/log(2));i>=1;i--) { int
2020-11-13 19:18:28
674
原创 P2158 [SDOI2008]仪仗队
文章目录思路题目传送门思路我们其实可以发现，我们如果要(x,y)(x,y)(x,y)这个点能被看见的话，我们就需要gcd(x,y)==1gcd(x,y)==1gcd(x,y)==1。我们就可以打一个暴力：#include <bits/stdc++.h>using namespace std;int n,ans;int main() { scanf("%d",&n); for(int i=0;i<n;i++) { for(int j=0;j<n;j++
2020-11-02 13:06:01
114
1
原创 The XOR-longest Path
文章目录题目描述思路代码题目描述给定一棵NNN个点的带权树，求树上最长的异或和路径。思路我们先给个图：我们怎么求6−76-76−7之间的异或和呢？我们可以知道1−71-71−7的异或和就是5 ^ 3 ^ 11 ^ 8。1−61-61−6的异或和就是5 ^ 7 ^ 1，那这两个数异或起来就是5 ^ 3 ^ 11 ^ 8 ^ 5 ^7 ^ 1=3 ^ 11 ^ 8 ^ 7 ^ 1。可以发现一个规律，我们A−BA-BA−B的异或和就等于A−1A-1A−1的异或和再异或上B−1B-1B−1的异或和
2020-10-31 11:22:18
218
原创 The XOR Largest Pair
文章目录思路代码思路我们先暴力一下：for(int i=1;i<n;i++) { for(int j=i+1;j<=n;j++) ans=max(ans,a[i]^a[j]);}还能得828282分（脚出数据）。我们实际可以把这些数全部转换为二进制，然后存进字典树。我们既然要答案最大，则尽量让这两个数的二进制的相差的数位越大越好。我们就尽量往与当前位相反的指针上跑，如果没有就只能走原来的数位。这样就可以让答案最大。代码#include <bits/stdc++.h
2020-10-31 10:17:35
366
1
原创 字典树Trie
文章目录存储插入操作insertinsertinsert代码检索searchsearchsearch代码完整代码存储我们的字典树是这样的：我们的字典树是用一个二维数组进行维护的：Trie[P][c]=Q;我们的PPP是起始节点，ccc是字符的ASCLLASCLLASCLL码（但是我们大多数时候是会把它缩小一下，比如c−′a′c-'a'c−′a′），QQQ是终点节点。我们的字典树就这样储存。插入操作insertinsertinsert1.我们先从根节点111开始,令P=1P=1P=1，如果
2020-10-31 10:09:29
76
原创 疫情控制
文章目录思路输入二分倍增预处理dfsdfsdfs寻找路径未被驻扎的叶子节点checkcheckcheck函数代码题目传送门思路我们的方法是：二分+贪心+倍增。我们可以知道：如果这个时间可以让题意满足，则比它大的时间也可以让题意满足。所以有单调性，我们就可以二分答案。但checkcheckcheck函数怎么打呢？我们要使用贪心：显然我们希望每个军队都停留在深度更小的节点（从而管理更多的路径），所以我们就需要军队向上走。若一个军队可以走到根节点，则令其暂时停在根节点的子节点。否则走到能够走到的深
2020-10-30 19:10:58
391
1
原创 严格次小生成树
文章目录思路不严格次小生成树严格次小生成树题目传送门思路次小生成树分为两种：严格次小生成树和不严格次小生成树。不严格次小生成树我们都十分清楚最小生成树的求法：贪心。我们只需要改一下求法我们就可以求出次小生成树了。我们先求出最小生成树。然后我们就把没有加入的边先放进去。那么就一定会组成一个环。我们把这个环中的次大边减去（因为最大边一定是加入的边）。然后我们就得到一个生成树。但不一定是最小的。所以我们要把每一个没有加入的边都遍历一遍，求出最小的一个。但这样做出来的次小生成树有可能就等
2020-10-30 13:05:40
374
原创 小Z的矩阵
文章目录思路代码题目传送门思路我直接先打一个暴力：#include <bits/stdc++.h>using namespace std;int n,q,a[1005][1005],ans[500005],cnt;int ask() { int ans=0; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) ans=(ans+a[i][j]*a[j][i])%2;
2020-10-27 17:08:56
81
原创 火柴排队
文章目录思路代码题目传送门思路我们需要让∑i=1n(ai−bi)2\sum_{i=1}^{n}(a_i-b_i)^2∑i=1n(ai−bi)2最小化，也就是等于000，我们就需要让aaa序列和bbb序列所有元素对应相同。我们先离散化一下，然后就求最少几个操作使得bbb序列转换为aaa序列。我们再建立一个数组zzz。假设我们现在有离散化后的序列 a={4,3,1,2},b={1,3,2,4}a = \{4, 3, 1, 2\},b = \{1, 3, 2, 4\}a={4,3,1,2},b=
2020-10-26 12:55:52
50
原创 青蛙的约会
文章目录思路代码题目传送门思路我们可以列出一个方程：x+km≡y+kn(mod l)x+km≡y+kn(mod\ l)x+km≡y+kn(mod l)我们转换一下：l∣x+km−y−knl\mid x+km-y-knl∣x+km−y−kn⇒lz=x+km−y−kn\Rightarrow lz=x+km-y-kn⇒lz=x+km−y−kn⇒−x+y=lz+km−kn\Rightarrow -x+y=lz+km-kn⇒−x+y=lz+km−kn⇒−x+y=lz+k(m−n)\
2020-10-24 09:41:24
212
原创 P2568 GCD
文章目录思路代码题目传送门思路我们暴力的话，还是能骗一点分的：但我们一定要追求极致，否则，学什么竞赛啊！（不是我说的！）我们直接枚举素数：∑p∈prime∑i=1n∑j=1n[gcd(i,j)=p]\sum_{p∈prime}^{}\sum_{i=1}^{n}\sum_{j=1}^{n}[gcd(i,j)=p]∑p∈prime∑i=1n∑j=1n[gcd(i,j)=p]变形得：∑p∈prime∑i=1⌊np⌋∑j=1⌊np⌋[gcd(i,j)=1]\sum_{p∈prime}^{}
2020-10-23 14:32:57
112
1
原创 有依赖的背包问题
题目传送门思路我们可以把依赖关系用一棵树来表示，我们选了一个节点就节点的父亲都要选。然后我们可以把有依赖的背包问题看成是分组背包问题，每一个结点是看成是分组背包问题中的一个组，子节点的每一种选择我们都看作是组内的一种物品，因此我们可以通过分组背包的思想去写。但我们如何去遍历子节点的每一种选择，即组内的物品，我们的做法是从叶子结点开始往根节点做，并使用数组表示的邻接表来存贮每个结点的父子关系。#include <bits/stdc++.h>using namespace std;i
2020-10-22 15:53:09
95
原创 扩展欧几里得算法
文章目录定义定义扩展欧几里得算法(Extended Euclidean algorithm)(Extended\ Euclidean\ algorithm)(Extended Euclidean algorithm)，顾名思义就是欧几里得算法（辗转相除法）的扩展。已知整数a,ba,ba,b，扩展欧几里得算法可以在求a,ba,ba,b的最大公约数的同时，能找到整数x,yx,yx,y（其中一个很可能是负数），使它们满足贝祖等式：ax+by=gcd(a,b)ax+by
2020-10-20 13:34:21
148
原创 整除 && 模运算 && 同余
文章目录整除性质1.传递性：如果a∣ba\mid ba∣b且b∣cb\mid cb∣c，则a∣ca\mid ca∣c2.a∣ba|ba∣b且a∣ca|ca∣c等价于对于任意的整数x,yx,yx,y，有a∣(bx+cy)a|(bx+cy)a∣(bx+cy)3.设mmm不为000，则a∣ba|ba∣b等价于ma∣mbma|mbma∣mb4.设整数x,yx,yx,y满足下式：ax+by=1ax+by=1ax+by=1，且a∣n,b∣na|n,b|na∣n,b∣n，那么(ab)∣n(ab)|n(ab)∣n5.若b=
2020-10-18 15:56:03
667
原创 排列组合与盒子放球问题
文章目录前置知识：排列组合定义组合公式1.证明Cnm=Cnn−mC_n^m=C_n^{n-m}Cnm=Cnn−m2.证明CnmCmk=CnkCn−km−kC_n^mC_m^k=C_n^kC_{n-k}^{m-k}CnmCmk=CnkCn−km−k3.证明∑i=0nCni=2n\sum_{i=0}^nC_n^i=2^n∑i=0nCni=2n4.证明Cn+mk=∑i=0kCni×Cmk−iC_{n+m}^k=\sum_{i=0}^kC_n^i\times C_{m}^{k-i}Cn+mk=∑i
2020-10-17 08:05:46
2653
原创 约数之和
文章目录约数个数定理证明方法约数定理思路代码题目传送门约数个数定理我们对于一个大于111的整数nnn，nnn可以分解为 ∏i=1kpiai=p1a1× p2a2× p3a3...pkak\prod_{i=1}^kp_i^{ai}=p_1^{a_1}\times\ p_2^{a_2}\times\ p_3^{a_3}...p_k^{a_k}∏i=1kpiai=p1a1× p2a2× p3a3...pkak。则nnn的正约数个数就是f(n)=∏
2020-10-15 21:29:36
106
原创 矩阵快速幂 && 求Fibonacci第n项 && Fibonacci前n项和
文章目录求FibonacciFibonacciFibonacci第nnn项代码总结FibonacciFibonacciFibonacci前nnn项和方法1方法2代码求FibonacciFibonacciFibonacci第nnn项斐波那契数列是这样的一个数列，1，2，3，5，8...，1，2，3，5，8...，1，2，3，5，8...即前两项都是111，后面每一项都是其前面两项的和。现在要你求出该数列的第n项。(n<=2∗1092*10^92∗109)方法1： 我们都知道FibonacciFi
2020-10-06 19:58:52
206
原创 无向图的最小环问题
文章目录思路代码传送门思路这道题的nnn的数据很小，n≤100n\le100n≤100，所以我们就可以用FloydFloydFloyd算法来解决。我们算法模板：for(int k=1;k<=n;k++) { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(f[i][j]>f[i][k]+f[k][j]) f[i][j]=f[i][k]+f[k][j]; } }}每一次最外层循环，我们都求到
2020-10-01 14:14:44
134
原创 最大公约数与最小公倍数
文章目录题目描述思路证明nnn和n−1n-1n−1互质题目描述⼩YYY同学在学习数论之后灵机⼀动想出⼀个问题：请你找出两个数a,ba,ba,b，满⾜1≤a,b≤n1≤a,b≤n1≤a,b≤n且lcm(a,b)−gcd(a,b)lcm(a,b)−gcd(a,b)lcm(a,b)−gcd(a,b)尽量⼤。输出最⼤的lcm(a,b)−gcd(a,b)lcm(a,b)− gcd(a,b)lcm(a,b)−gcd(a,b)。其中gcd(a,b)gcd(a,b)gcd(a,b)表⽰aaa和bbb的的最⼤公约数，l
2020-09-26 07:33:01
94
原创 夏季特惠
文章目录题目描述思路代码题目描述Steam 2019Steam\ 2019Steam 2019年夏季促销开始了！⼩YYY同学决定⼊⼿⼀些游戏，⼩Y同学⼀共有xxx元的预算，该平台上所有的nnn个游戏均有折扣，标号为iii的游戏的原价aiaiai元，现价只要bibibi元（也就是说该游戏可以优惠ai−biai−biai−bi元,每款游戏最多只能购买⼀次），并且⼩YYY同学购买该游戏能获得快乐值为wiwiwi。由于优惠的存在，⼩YYY作为剁⼿党可能做出⼀些冲动消费导致最终买游戏的总费
2020-09-25 21:25:43
1685
原创 并查集
文章目录储存查询findfindfind优化：路径压缩合并例题冰茶姬（Disjoint−setDisjoint-setDisjoint−set）是一个可以动态维护若干个不重叠的集合，并且支持合并和查询的数据结构。储存某大侠有许多个朋友，他会杀掉朋友的敌人，也会和敌人的敌人成为朋友。但时间一久，他就不知道面前这个人是不是朋友。冰茶姬站了出来，大声一吼:“没事，你当你朋友的祖宗！”没错，冰茶姬就是这么实现的，认祖宗！。我们定义一个数组fafafa，存储iii的祖宗是谁。分辨这个人是否是朋友，我们只需要
2020-09-24 14:00:25
70
原创 木棒
文章目录思路代码：搜索初步1传送门思路我们可以从小到大枚举原始木棒的长度lenlenlen(也就是枚举答案)。当然，lenlenlen应该是所有木棒长度中和sumsumsum的约数，并且原始木棒长度的根数cntcntcnt就等于sum/lensum/lensum/len。对于每个lenlenlen，我们可以依次搜索每根原始木棒有哪些木棒拼成。则搜索所面对的状态包括：已经拼好的根数，正在拼的木棒的长度，每根木棒的使用情况。在每个状态下，我们就从尚未使用的木棒中选一根来尝试拼。但这个算法效率比较低，
2020-09-23 21:08:31
104
1
原创 八皇后问题
文章目录题目描述样例输出：思路搜索初步1题目描述在国际象棋棋盘上放置八个皇后，要求每两个皇后之间不能直接吃掉对方。样例输出：No. 11 0 0 0 0 0 0 00 0 0 0 0 0 1 00 0 0 0 1 0 0 00 0 0 0 0 0 0 10 1 0 0 0 0 0 00 0 0 1 0 0 0 00 0 0 0 0 1 0 00 0 1 0 0 0 0 0No. 21 0 0 0 0 0 0 00 0 0 0 0 0 1 00 0 0 1 0 0 0 00
2020-09-23 21:03:31
189
1
原创 特殊的质数肋骨 Superprime Rib
文章目录思路传送门搜索初步1思路这就是一个简单的DFS板题。代码1：#include <bits/stdc++.h>using namespace std;int n, sum = 1;bool o(int t) { for (int i = 2; i <= sqrt(t); i++) { if (t % i == 0) return 0; } return 1;}bool yu(int t) {
2020-09-23 20:57:11
389
原创 How Far Away?
文章目录题目描述思路代码题目描述村子里有nnn栋房屋，有一些双向道路将它们连接起来。每天，peoplepeoplepeople总是喜欢这样问：“如果我想从房子AAA到房子BBB多远？” 通常很难回答。但是幸运的是，这个村庄的答案始终是唯一的，因为道路的建造方式是每两栋房屋之间都有一条唯一的简单路径（“简单”意味着您不能两次访问某个地方）。您的任务是回答所有这些好you奇bing的人。输入格式第一行是单个整数TTT（T<=10T <= 10T<=10），表示测试用例的数量。对于每个
2020-09-23 20:48:39
303
1
原创 LCA算法 && 倍增
#include <bits/stdc++.h>#include <queue>using namespace std;int n,q,head[100005],cnt,d[100005],f[100005][105];struct node{ int to,next; }a[200005];void add_edge(int u,int v) { a[++cnt].to=v,a[cnt].next=head[u]; head[u]=cnt;}void bfs(
2020-09-23 13:23:44
505
原创 凸多边形的划分
文章目录思路代码传送门思路如上图所示，一个编号为111到666的六边形，我们考虑划分时边（1，6）（1，6）（1，6）会被哪个三角形选中，由顶点1,61,61,6构成的三角形可以是126，136，146，156126，136，146，156126，136，146，156。比如随便选取其中的一个三角形146146146，原图形就被划分为了三部分，最简单的蓝色三角形146146146，以及蓝色三角形上面的图形和下面的图形，由于划分的三角形不能交叉，所以不会存在像125125125这样会与1461461
2020-09-22 20:53:15
703
原创 烛光晚餐
文章目录思路代码传送门思路这就是一个二维费用问题。我们定义f[i][j]f[i][j]f[i][j]为前iii道菜小明的满意值为jjj的小红的满意值。所以状态转移方程式为：dp[i][j]=max(dp[i][j],dp[i−c][j−x]+y);但我们的的jjj可能小于000，也就是小明的满意值可能小于000。但我们的下标不可能小于000，所以我们需要特殊处理一下。把jjj全部右移500500500。f[j][k+500]=max(f[j][k+500],f[j-c][k-x+500]
2020-09-21 20:47:45
89
原创 ST算法 && RMQ问题
文章目录思路预处理代码(求最大值)预处理代码(求最小值)询问l−rl-rl−r最值代码【白话系列】倍增算法我们就直接讲一下RMQRMQRMQ（区间最值问题）问题。题目：求出数列aaa中下标在l−rl-rl−r之间的数的最大值是多少？（当然也可以求最小值）我们最简单的方法就是直接枚举l−rl-rl−r之间的数。但当数据过于大时，暴力就不太适合了。于是，STSTST算法应运而生。思路给定一个长度为nnn的数组aaa，STSTST算法可以能在O(N log N)O(N\ log
2020-09-21 13:46:27
85
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人