追风者_-CSDN博客

原创 SCAU 2019年校赛部分题解

我的博客园传送门，阅读起来方便些18438 First Blood题意：∑i=1a\sum_{i=1}^a∑i=1a∑j=1b\sum_{j=1}^b∑j=1b(i+j) ，求和。思路：签到题，照着题目A就行了。view code#include<iostream>#include<string>#include<algorithm>#include<cstdio>#include<cstring>#include&lt

2020-08-27 17:41:11 1356

原创【爬虫初出茅庐】爬取并下载想要图片源码分析 + 分享

先上效果图。如搜取并下载【鬼灭之刃】和【刀剑神域】相关图片相关过程分析：（PS:因为刚学爬虫没几天，若大佬发现有什么问题欢迎指正）这里爬取的网站是免费提供图片的51贴图。若光爬取单一或者连续网页的图片是很简单的，但是如果要爬取用户输入的指定类型图片呢（如上述的【刀剑神域】），这就需要先找到用户输入串和对应url之间的联系。通过尝试发现，如找【天空之城】，改字符串直接包含在网页的url中：那么，第一步：我们可以将用户输入的串s填入https://www.51tietu.net/pic/

2020-05-27 18:22:55 812 1

原创【课设项目】图像的边缘识别和处理问题源码分享

先上效果图（原图/边缘识别对比）：1、系统概述：日常需求中，不难发现有很多图像描边的功能要求，以及图像平滑、降噪等优化需求。这时候，将一个图像数据化处理的技术就显得格外重要。通过对图像对应的矩阵信息进行梯度操作、阈值处理、边缘化保留和卷积，可以将一个个点阵转化为平滑的的图像点，实现图像到数据，再从数据到图像的转化。系统主要功能分四类：一个功能是图像数据采集，通过读取包含图像信息的t...

2020-04-16 21:55:14 523 6

原创 Floyd算法的深入理解尝试魔改核心代码

https://blog.csdn.net/qq_45492531/article/details/104452588在我这个博客中，一次训练的机会让我接触到了floyd算法。

2020-02-26 00:43:45 851 5

原创【mysql】Leetcode 刷题记录

这里写自定义目录标题欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题，有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个自定义列表如何创建一个注脚注释也是必不可少的KaTeX数学公式新的甘特图功能，丰富你的文章UML 图表FLowchart流程图导出与导入导出导入欢迎使用Markdown编辑器你好！这是你第一次使用 Markdown编辑器所展示的欢迎页。如果你想学习如何使用Mar

2021-10-08 22:09:41 220

原创 ACwing 311. 月之谜数位dp

题意：问你[l,r]内有多少数，是可以被其数位和整除的。思路：思路：直观想法，用dp[pos][sum1][sum2]dp[pos][sum1][sum2]dp[pos][sum1][sum2]，表示枚举到第pos位，组成sum1的数，累加和为sum2时的方案数。由于sum1很大，所以要考虑每步取模。想到，若给定一个m，问你有多少数是被m整除，这个就是一个裸的数位dp板子，用一个dp[pos][sum]dp[pos][sum]dp[pos][sum]就可以表示枚举到第pos位，逐步取模结果为sum

2021-08-10 00:03:49 250

原创 P3384 【模板】轻重链剖分/树链剖分

模板题记录一下AC代码：#include<iostream>#include<string>#include<algorithm>#include<cstdio>#include<cstring>#include<cmath>#include<map>#include <queue>#include<sstream>#include <stack>#include

2021-08-08 18:40:26 193

原创 2021HDU多校 1008 Lawn of the Dead 线段树

思路：按照题意，如果一个格子的上方一个格子和左边一个格子都走不了，那这个格子就走不了，一旦一个格子走的了，其下面的格子都走的了，右边的格子也都走的了（地雷除外）。那么考虑用线段树维护一行中能走到的格子和走不到的，走得到的为0，走不到的为1。那么询问区间[l,r]看最左边的0在哪，这个0一路到r的格子就都可以走。询问的区间就是一行里面每两个地雷之间的区间。AC代码：#include<iostream>#include<string>#include<algorith

2021-07-31 20:02:01 183

原创 2021牛客多校5 D Double Strings dp 数学

思路：先预处理出dp[i][j]dp[i][j]dp[i][j]表示a的前i位和b的前j位能组成的相同子序列个数。然后对于每个a[i]<b[j]的位置，前面有dp[i−1][j−1]dp[i-1][j-1]dp[i−1][j−1]的方案数，乘上后面 ∑k=1min(len1−i,len2−j)Clen1kClen2k\sum_{k=1}^{min(len1-i,len2-j)}C_{len1}^{k}C_{len2}^{k}∑k=1min(len1−i,len2−j)Clen1kClen2k

2021-07-31 18:47:06 152

原创 E2. Array and Segments (Hard version) 思维线段树区间最值维护

题意：给你若干区间，选出若干区间，对其区间内元素值-1，使得最后序列最大-最小的值最大思路：首先一点，枚举每个aia_iai当最大值，那么所有不包括i这个位置的区间都选上，让它们去减。然后询问一次区间最小值mi，a[i]-mi就是当前枚举得到的一个解，每次比较更新答案即可。上面的操作可以用线段树维护，我们可以先对所有区间-1，同时预处理出以i位置为区间L,R端点的区间，然后遍历1->n的点，每一次，把以i这个位置为左端点的区间+1回来，然后询问区间最值，完了后，对以i这个点为右端点的区间再-1

2021-07-30 16:34:14 109

原创 2021HDU多校1 Xor sum 字典树

题意：问你能不能找到一个最小的区间【L,R】,使得区间异或和>=k，同时保证左端点最小。思路：选取区间[l,r][l,r][l,r]，其值等效于sumr异或suml−1sum_r 异或 sum_{l-1}sumr异或suml−1，那我们就利用一个字典树，在枚举右端点时，查询满足与当前sumrsum_rsumr异或起来大于等于k且下标最大的前缀位置。插入时，每次更新走过当前路径上的点时的最大下标。这样在查询的时候，我们先贪心从高位开始走异或起来和k逐位相同的路线，然后看k该位为0时，我们若

2021-07-23 14:32:50 198

原创 CodeForces - 1191F Tokitsukaze and Strange Rectangle cdq分治

题意：选任意底长的框把若干点框起来，有多少种方法。思路：看到这种X-Y还带有计数的，想到cdq分治（二维偏序）。每次我就看xj<=xix_j <= x_ixj<=xi&&yj>=yiy_j>=y_iyj>=yi的点有多少，分别统计这个点左边有多少个、右边有多少个。然后左右的数量相乘就是以当前i为底的贡献。考虑到有y相同的，这里会产生重复，就需要统一特判一下所有y相同的，相邻两个间独立计数。AC代码：#include<iostrea

2021-05-29 21:11:36 129

原创【洛谷】 P3157 动态逆序对 cdq分治三维偏序

思路：把问题转化成插入元素，也就是整个过程倒过来看，设一开始（还没插入元素前时）的Ti=0T_i = 0Ti=0，那么即是求：Ti<=TjT_i<=T_jTi<=TjPosi>PosjPos_i > Pos_jPosi>PosjVali<ValjVal_i < Val_jVali<Valj或者Ti<=TjT_i<=T_jTi<=TjPosi<PosjPos_i < Pos_jPosi<

2021-05-26 22:47:55 116

原创【洛谷】 P3810 【模板】三维偏序（陌上花开）

思路：三维偏序的模板题。思想就是：1.先对x进行排序，然后可以把区间分割成[l,mid]和[mid+1,r][l,mid]和[mid+1,r][l,mid]和[mid+1,r]的子区间。2.对于右区间，所有左区间内的元素都是“有可能”对其产生贡献的（因为固定了x左边小右边大）。那么现在考虑第二维y，对于这个[l,r][l,r][l,r]区间进行对y的排序。3.排序完后进行遍历，对于当前i，如果他是左区间的，就用树状数组单点更新他的z值；如果他是右区间的，说明i之前有的元素已经更新过的元素满足：

2021-05-26 14:34:07 262

原创【洛谷】 P2717 寒假作业 cdq分治树状数组

题意：给定一个长度为 n 的正整数序列，求出有多少个连续子序列的平均值不小于 k。思路：对于平均值的问法，先所有a[i]-k，然后问题就转化成有多少个区间，其和大于等于0。若先处理前缀和，那么就是在问，我当前如果固定了右端点是iii，那么我要知道前面有多少个数是<=sum[i]<=sum[i]<=sum[i]的，这个就转化成一个cdq分治的问题了，类似于求逆序对。AC代码：#include<iostream>#include<string>#incl

2021-05-25 16:45:02 156

原创 P2345 [USACO04OPEN]MooFest G cdq分治树状数组

题意：横坐标上若干点，坐标为X[i]，每个点有个权值val，问你所有两两max(val[i],val[j])∗∣X[i]−X[j]∣max(val[i],val[j])*|X[i]-X[j]|max(val[i],val[j])∗∣X[i]−X[j]∣的和思路：比较裸的cdq分治题目，我们把题意条件分成两部分：对于当前i要计数的有1.val[j]比当前val[i]小的（这样val[i]才用得上）。2.同时要知道他们的坐标来求和。对于第一点，我们只需要先按照val从小到大排序，这样对于i，满足第一

2021-05-23 22:54:56 243 2

原创 Points in Rectangle (II) LightOJ - 1267 树状数组离散化

<font color=#000033 size=3=3 face=“黑体”>题意：给若干点和若干个矩形，问你每个矩形包含了多少个点思路：其实问题就转化成，对于每个矩形求横坐标∈[x1,x2x_1,x_2x1,x2]，纵坐标满足∈[y1,y2y_1,y_2y1,y2]的点的个数。对点离散化后，我们先求[x1,x2x_1,x_2x1,x2]内纵坐标小于等于(y1-1)的个数，再求这个区间内小于等于y2的个数，后者-前者即是答案。考虑用树状数组维护，现在离散化后的x就是我们查询的区

2021-05-22 22:33:32 111

原创【网络流24题】P4016 负载平衡问题最小费用最大流

题目描述GG 公司有 nn 个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最少搬运量可以使 nn 个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。思路：可以唯一确定最后各自都相等时的值each=sum/neach = sum/neach=sum/n。将a[i]重新赋值为a[i] -= each。建图：对于a[i]为正的部分，相当于流出量，由s连出。对于a[i]为负的部分，相当于流入量，连向t，费用都为0。然后相邻的再连边，流量为inf，费用为1（相当于每个数流动时需要消耗

2021-03-26 23:40:58 156

原创【网络流24题】P4174 [NOI2006] 最大获利最大权闭合子图

思路：将题中的点和边都看成事件。由于选边的时候要选成对的点，且边事件依赖于点事件的发生，满足闭合图的性质。建图：建立源点，连向有正贡献的边事件（也看成一个点），流量为对应贡献，这个点再向依赖的点连流量为inf的边，依赖点是负贡献，它们各自向汇点连流量为负贡献的绝对值的边。这个时候对这个二分图跑求一个最小割，即是最小损失，然后用正贡献和-最小损失即是答案。关于正确性，如果割掉用户边，就相当于减少了收益，可看成损失。若割掉了中转站的边，相当于付出了代价，看成损失。而流量为inf的边不会被割，也就解决.

2021-03-26 23:05:47 110

原创【网络流24题】 P2774 方格取数问题最小割

有一个 mm 行 nn 列的方格图，每个方格中都有一个正整数。现要从方格中取数，使任意两个数所在方格没有公共边，且取出的数的总和最大，请求出最大的和。思路：任意一个方格都和周围四个互斥，那么就构成了一个二分图，且可以用(i+j)的奇偶性区分两部。我们想要实现选or不选某个点（在二分图中），来看有没有把它的值加入贡献。考虑网络流，让源点向其中一部连流量为对应值的边，另一部向汇点连流量为对应值的边。二分图内部连流量无限。建图完后，会发现问题转化成了割掉多少边使得损失最小，这就是一个求最小割的问题了。关于

2021-03-26 22:17:35 176

原创 Codeforces Round #710 (Div. 3) ABCDE 题解

我的博客园传送门，看的方便些A. Strange Table签到题，算出对应行列即可。view code#include<iostream>#include<string>#include<algorithm>#include<cstdio>#include<cstring>#include<cmath>#include<map>#include <queue>#include<s

2021-03-26 00:54:21 468

原创 Codeforces Round #708 (Div. 2) ABC1C2题解

A. Meximization我的博客园传送门，看到方便些第i位优先放等于i-1的，没有的话就后面随便填了。view code#include<iostream>#include<string>#include<algorithm>#include<cstdio>#include<cstring>#include<cmath>#include<map>#include <queue>#i

2021-03-18 00:36:59 146

原创 Codeforces Round #706 (Div. 2) D. Let‘s Go Hiking 博弈思维

思路：A要赢的大前提就是当前x是一个波峰。因为如果是一个直线单调的话如1 2 3 4 5（或者5 4 3 2 1），不管A选哪个位置，B直接在他下一个位置封死，A就直接GG。现在考虑波峰的时候，那A就有两条路可以走，走左边或者走右边都可以（这个时候B就不能直接封死A了）。但是如果B能在别的地方挑一条比这两条路还长的路，那A还是输。当B选不到更长的路的时候，就会尽量的恶心A，走两条路中较长的那一条，这个时候A走较短的话必输，所以AB这时候必须相向而行。这个时候这条路的长度是奇数的话A就能赢了，且是唯一的一

2021-03-10 23:01:54 465 3

原创 Codeforces Global Round 13 ABC题解

我的博客园传送门，看的方便些A. K-th Largest Value思路：操作就是0变1,1变0。那么只用统计1有多少个就知道第x大是谁了。view code#include<iostream>#include<string>#include<algorithm>#include<cstdio>#include<cstring>#include<cmath>#include<map>#include

2021-03-01 00:40:24 2242 3

原创 Codeforces Round #699 (Div. 2) ABC题解

我的博客园传送门，看的方便点A. Space Navigation思路：分别统计往px和py方向的步数，看看能不能分别大于等于px和py。view code#include<iostream>#include<string>#include<algorithm>#include<cstdio>#include<cstring>#include<cmath>#include<map>#include &

2021-02-06 00:42:24 497 1

原创 A. Acing the contest 状压dp 背包

A common programming contest format includes teams with three contestants working to solve the maximum amount of programming challenges in the less amount of time using a single computer. Some contests have been created using a similar idea. In this contes

2021-02-01 12:25:04 252

原创【AtCoder】E - Magical Ornament 图论状压dp

题意：告诉你有哪些两两可以相邻，问你能不能排列出一个包含一串数的序列，且序列长度最小。思路：不知道是不是想复杂了。写完感觉不是这个位置的题该有的难度（应该是我太菜了）。1.首先，建图，相邻的对就连边，把题意转化成在该图上跑出一个最短路径包含序列中的所有点（点可重复）。2.因为走的点的先后顺序未知，所以我们只能通过bfs得到单次从s开始到各点的最短路径，下一步要考虑顺序问题。3.用dp[i][j]dp[i][j]dp[i][j]表示，走完i所表示的集合中的点，且最后一步是走到第j个点时的最优解。其中i

2021-01-30 23:44:02 368 3

原创 Codeforces Round #697 (Div. 3) ABCDE 题解

=>我的博客园传送门，阅读更方便<=久违的cf服务器爆炸场A. Odd Divisor思路：任何一个数都可以写成n=k2m，其中k是一个奇数n = k2^m，其中k是一个奇数n=k2m，其中k是一个奇数，若k=1，那么n就一定是一个2的幂。view code#include<iostream>#include<string>#include<algorithm>#include<cstdio>#include<cstrin

2021-01-26 11:29:57 245

原创 Codeforces Round #695 (Div. 2) B. Hills And Valleys 思维

思路：这个题一开始为了考虑出所有可能的情况写的很麻烦。。。比如考虑改变当前点后对两端波峰波谷的影响之类的。后来发现其实就一个思路：最优策略肯定是，当前这个点要么变成左端点一样的值，要么和右端点相等（a[i]=a[i−1]或者a[i]=a[i+1]a[i]=a[i-1]或者a[i]=a[i+1]a[i]=a[i−1]或者a[i]=a[i+1]），因为改变这个点最多只会影响相邻的两个点的状态，所以先记录没改之前[i-1,i+1]的波峰波谷个数，再看两次改变之后的波峰波谷个数，两次取个最小的（就是能消除掉最多的

2021-01-09 11:35:16 1285

原创 Codeforces Round #693 (Div. 3) ABCDE题解

A. Cards for Friends思路：折纸游戏，看长宽能各折多少次，就是2的几次方，相乘即可。view code#include<iostream>#include<string>#include<algorithm>#include<cstdio>#include<cstring>#include<cmath>#include<map>#include <queue>#inclu

2021-01-05 00:52:08 579 2

原创 AtCoder Beginner Contest 187 ABCDE 题解

A - Large Digits思路：签到题，读入字符串即可。view code#include<iostream>#include<string>#include<algorithm>#include<cstdio>#include<cstring>#include<cmath>#include<map>#include <queue>#include<sstream>#i

2021-01-02 23:10:00 277

原创 Codeforces Round #690 (Div. 3) ABCDE题解

我的博客园传送门A. Favorite Sequence思路：照着模拟即可。view code#include<iostream>#include<string>#include<algorithm>#include<cstdio>#include<cstring>#include<cmath>#include<map>#include <queue>#include<sstr

2020-12-16 10:04:22 296 1

原创 Codeforces Round #688 (Div. 2) ABC题解

A. Cancel the Trains签到题，看两边有无相同相对位置出发的，加入计数即可。view code#include<iostream>#include<string>#include<algorithm>#include<cstdio>#include<cstring>#include<cmath>#include<map>#include <queue>#include&lt

2020-12-04 23:43:12 329

原创 Codeforces Round #682 (Div. 2) ABC 题解

A. Specific Tastes of Andre题意：构造一个长度为n且任意子串和整除其长度的序列。思路：n个1就行。view code#include<iostream>#include<string>#include<algorithm>#include<cstdio>#include<cstring>#include<cmath>#include<map>#include <queu

2020-11-14 09:53:39 250

原创 Gym 101466 E - Text Editor KMP + 二分答案

题意：给你一个主串和模式串，找出模式串最大的前缀，使得其在主串中的出现次数大于等于n。思路：首先会想到KMP。但是如果直接拿模式串一位一位匹配是O(n2)的时间复杂度，肯定过不了。我们发现模式串长度越长，越不容易满足要求。所以这里有个单调性，可以来二分。我们二分答案可能的长度，然后用这么长的前缀丢进KMP里面，看看能否满足，如果发现可以，就把长度调大一点，反之调小一点。时间复杂度O(nlogn)。最后注意KMP用来计数时，每次匹配完不能直接j=0, i -= p.size()，因为这样会使得指针回溯

2020-10-13 13:34:55 207

空空如也

空空如也