C202207LYX-CSDN博客

原创 [JLOI2011]飞行路线

思路：一道最短路的题。。。分层最短路的板子。。。对于图中的所有节点uuu，他可以拆成k+1k + 1k+1个节点uju_juj，而且j∈\in∈[0,k]。分别表示当使用 jjj 次免费通行权限后到达 uuu 号节点的状态。对于，样例来说那个图的话（脑补）加工中。list[i][j]为到达i用了j次免费机会的最小花费。vis[i][j]为到达i用了j次免费机会的情况是否出现过。对于某些路径，我们可以选择使用机会，也可以选择不使用机会。之后就分两种情况：void spfa() {

2020-11-03 14:08:01 298

原创 [Usaco2018 Dec]Teamwork

思路：因为题面已经说了是连续的，所以就可以用一个线性的dp。设dp[i]以iii结尾的包装能力之和的最大值。设一个sum为dp[i]~dp[j]`包装能力的最大值。然后状态转移方程就是：dp[j]=Max(dp[j],dp[i−1]+(j−i+1)∗sum);dp[j] = Max(dp[j] , dp[i - 1] + (j - i + 1) * sum);dp[j]=Max(dp[j],dp[i−1]+(j−i+1)∗sum);code：#include <cstdio>

2020-11-03 14:06:46 200

原创挑选

//dp[i][j]表示前i个小朋友中左括号与右括号的差为j的最大实力值//dp1[i][j]表示前i个小朋友中左括号与右括号的差为j的方案总数。#include <cstdio>#include <algorithm>#include <cstring>using namespace std;const int maxn = 1e7 + 5;const int mod = 998244353;int n, w[maxn], c[maxn];long

2020-10-12 14:06:17 826 4

原创欧拉回路（模板题）

序言:首先感谢@G20222222_tly学长提供的关于dfs的思路一份。在此之前，如果看过我之前写的博客的同学，不必担心，只需要，忘记！引子：额，这道题，以平常的题目，过人的惊天数据来展示什么叫毒瘤。然后去看了一下题解，自己又重码了一遍，结果重新再来看的时候是一脸懵逼嗄。然后想了将近一晚上的思路终于有了起色。下面就是我的一些见解，和代码代码及其思路首先加入快读，是因为原代码是刚好卡着时间过的，如果要按照，本人目前所学的东西来写的话直接超时，不用说了。关于dfs最新的思路就是这样

2020-09-15 13:20:39 320

原创关于HASH再补充——HASH函数的方法及控制HASH表的长度和解决冲突的一些方法

序言：HASH表对我来说是真没有听懂，尤其是构造HASN函数…有同学也说再讲一下HASN那我也就把自学的另一点东西献出来吧。HASH表hash表主要是查找，对内存中的数据进行有效的快速查找它的查找时间复杂度是O（1）。构造一个设计一个哈希表的关键有三个：怎么控制哈希表的长度，怎么设计哈希函数，怎么处理哈希冲突怎样控制哈希表的长度HASH表的长度一般是定长的，在存储数据之前我们应该知道我们存储的数据规模是多大，应该尽可能地避免频繁地让HASH表扩容。但是如果设计的太大，那么就会浪费空间，因为我

2020-08-06 19:23:47 1184

原创引水入城

引子：今天我们又来考试了…今天全考的是搜索和最短路径全没复习，唯一对的就是这道我唯一会的BFSBFSBFS以及会打的BFSBFSBFS，所以顺利ACACAC题目描述：在一个遥远的国度，一侧是风景秀美的湖泊，另一侧则是漫无边际的沙漠。该国的行政区划十分特殊，刚好构成一个NNN 行 × MMM列的矩形，如上图所示，其中每个格子都代表一座城市，每座城市都有一个海拔高度。为了使居民们都尽可能饮用到清澈的湖水，现在要在某些城市建造水利设施。水利设施有两种，分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊

2020-08-01 10:21:45 1009 3

原创【2018-10-14普及模拟赛】Hash 键值

题目描述：Marser沉迷hash无法自拔，然而他发现自己记不住hash键值了……Marser使用的hash函数是一个单纯的取模运算，每一个数i被对应到i mod p。他现在有一个数列，他采用这种方法，把每一个数对应到一个键值i mod p。他想知道对于给定的模数p和键值r，所有对应到该键值的数的和为多少。同时，Marser可能会发现他的数列出了一些问题，所以他还想随时更改数列中任意一项的值。现在Marser有q个请求，每个请求可能是修改或是询问。对于每一个询问，你需要给出正确的答案。如果你不能在1s

2020-11-04 13:21:22 197

原创【模板】树状数组模板总结

前言：这章节的代码框架，真就是一个字背！什么是树状数组（又是这个问题哈）树状数组(Binary Indexed Tree(B.I.T)也称作Fenwick Tree)是一个区间查询和单点修改复杂度都为log(n)的数据结构。主要用于查询任意两点之间的所有元素之和。说白了，就是个数组,只是长得像树。questionquestionquestion：有一个一维数组长度为n，求区间[L,R]的和，并且可以对原数组某一元素进行修改？现在就引入LowbitLowbitLowbit的概念了。Low

2020-11-03 13:47:17 193

原创【模板】二叉堆模板总结

完全二叉树：如果一棵深度为k的二叉树，1至k-1层都是满的，即每层结点数满足2i-1，只有最下面一层的结点数小于2i-1，并且最下面一层的结点都集中在该层最左边的若干位置，则此二叉树称为完全二叉树。那么我们所学的二叉堆呢，总的来说就是一个数组。它可以被看作一棵完全二叉树。树中每个结点与数组中存放该结点中值的那个元素相对应。如图所示:：设数组AAA的长度为lenlenlen，二叉树的结点个数为sizesizesize，size≤lenize≤lenize≤len，则A[i]A[i]A[

2020-11-03 13:39:49 226

原创【NOIP2006】能量项链

题目描述在 Mars 星球上，每个 Mars 人都随身佩带着一串能量项链。在项链上有颗能量珠。能量珠是一颗有头标记和尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记必定等于后一颗珠子的头标记。因为只有这样，通过吸盘——Mars 人吸收能量的器官的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可被吸盘吸收的能量。如果一颗能量珠头标记为，尾标记为，后一颗能量珠头标记为，尾标记为，则聚合后释放出 Mars单位的能量，新珠子头标记为，尾标记为。思路：这道

2020-11-03 13:33:15 487

原创【区间dp】戳气球

index：从题来看，我第一次是没看懂是说的一个什么意思。不过有各位大佬，鼎力相助我才读懂这道题，并进而AC这道题思路：首先分析一下如果我戳破了第iii个，那么会留下i−1i-1i−1和i+1i+1i+1，但是此时你的和却跟i−1i-1i−1,iii,i+1i+1i+1都有关。从这个条件不难看出它是一个(i-1,i+1)的开区间。但是题目却要我们戳完所有的气球。怎么办呢？这是我们就可以，设两个端点最左端点和最右端点分别为：a[0]a[0]a[0]和a[n+1]a[n+1]a[n+1]且初值

2020-11-03 13:28:55 184

原创【模板】二分答案模板总结

定义：二分答案与二分查找类似，即对有着单调性的答案进行二分，大多数情况下用于求解满足某种条件下的最大（小）值。代码：为了保证解在二分搜索的区间里，故不同的问题有着不同（但相似）的写法template <typename T>int binary(T n) { int l = 1; int r = maxn; int ans = 0; while(l <= r) { int mid = (l + r) >> 1;

2020-11-03 13:24:21 428

原创【学习笔记】trie树模板总结

index：今天学了trietrietrie树，然后就想来写一写，不然等会模板都记不得了。操作：插入字符串：当需要插入一个字符串S时，我们令一个指针P起初指向根节点(可以理解为以根节点为起点，做好扫描准备)，然后依次遍历S中的每一个字符c：1、若P的c字符指针指向一个已经存在的节点Q，则令P=Q。2、若P的c字符指针指向空，则新建一个节点Q，令P的c字符指针指向Q，然后令P=Q。当S中的字符扫描完毕时，在当前节点P上标记它是一个字符串的末尾标记末尾是因为判断是不是为一个完整的单词而不

2020-10-31 11:10:51 152

原创【学习笔记】dfs模板总结

index:临近复赛，由于本人太蒟蒻，决定复习一下，那个搜索。。绝命搜索闷声发大财：code:code:code:void dfs() {//参数用来表示状态 if(到达终点状态) { ...//根据题意添加 return; } if(越界或者是不合法状态) { return; } if(特殊状态) {//剪枝 return ; } fo

2020-10-30 20:21:37 149

原创括号涂色

题目——洛谷题目描述：Petya遇到了一个关于括号序列的问题：给定一个字符串S，它代表着正确的括号序列，即（“(”）与（“)”）是匹配的。例如：“(())()” 和 “()”是正确的，“)()”与“(()”则不是正确的。在正确的括号序列中，一个左边的括号一定是匹配一个右边的括号（反之亦然）。例如，在下图中，第 3 个括号匹配第 6 个括号，第 4 个括号匹配第 5 个括号。现在你需要对一个正确的括号序列做涂色操作，严格满足以下三个条件：1、每个括号要么不涂色，要么涂红色，要么涂蓝色。2、一对

2020-10-30 20:10:20 366

原创暑假集训总结——区间DP，堆的概念及应用，STL（vector、set、pair、map、priority_queue），hash表，树状数组，图论

序言：经过长达十几天的集训，确实学了不少知识点。我想如果再不总结的话，6天之后又要忘完了。所以发一篇具有总结回忆性的博客，供大家回忆。目录会本人自己排列的时间的先后顺序来排列，可直接食用。目录：一、动态规划 1.区间DP二、 STL 1.vector 2.pair 3.set 4.map 5.priority_queue三、数据结构 1.字符串hash 2.hash表 3.树状数组 4.堆及其运用四、

2020-10-30 20:09:08 286

原创【忏悔的博客】2020普及组三校联考(八中)

index：我忏悔，出生没带眼睛，没加快读。中午听到老师说晚上要考试，我以为是晚读之后才开始（没有算时间只有两个小时）然后一上来看到大家都在考试了，有点慌，直接看第一题（直接跳过前面的所有）没有看到，要加快读，直到考试结束。。T1:零这道题，题面还好，就是要上我们求一个sumsumsum看是不是为零如果是输出YESYESYES，否则输出NONONO，感觉还好。但是没加快读，只有五十但是我还是发现我还个地方写爆了，本来只需要一个循环求出sumsumsum但是写了一个双重循环i=1−ni =

2020-10-29 13:37:28 146

原创关于打模拟的一些方法

摘抄自wikiindex：众所周知，模拟是十分恐怖的。模拟题目通常具有码量大、操作多、思路繁复的特点。由于码量大经常会出现难以查错的情况，在考试中写错是相当浪费时间。接下来就来讲讲写模拟的技巧。技巧：写模拟题时，遵循以下的建议有可能会提升做题速度：在动手写代码之前，在草纸上尽可能地写好要实现的流程。在代码中，尽量把每个部分模块化，写成函数、结构体或类。对于一些可能重复用到的概念，可以统一转化，方便处理：如，某题给你 “YY–MM-DD 时：分” 把它抽取到一个函数，处理成秒

2020-10-27 13:41:36 366

原创【忏悔的博客】2020普及组三校联考(西附)

index：我忏悔，出生没带眼睛，看错题了。T1把求模数理解成了求出模之后的结果。样例一直没过，卡了一小时，直到我开始检查我的模数是不是正确的时候才发现我题读错了然后脑子就反应不过来了，就直接我不知道怎么做了。之后读T2的时候，以为是一个普通的字符串问题做少了，就直接开始写结果错了。。。。T3大模拟碰到就废打了一半，时间到了。。。忏悔啊，没脸啊！！！好了，忏悔过了，之后该反省了。（先来题解）T1 模法师正常读了题就应该知道，这是个找规律。当k=0k = 0k=0时，如果查询的是一个

2020-10-26 13:52:43 232

原创考试题解

序言：有史以来，第一次第一名。被质疑。。。被某些人又开始找我的茬。。然后我写篇题解来澄清我并没有抄话说重启两次再加拔U盘，怎么会被说是抄的。。。再说即使是做过那也不得重打吗？数列问题：思路：一道公式题。当n=1n = 1n=1的时候，f[1] = 0;当n=2n = 2n=2的时候，f[2] = 1;当n=3n = 3n=3的时候，f[3] = 2;当n=4n = 4n=4的时候，f[4] = 2;当n=5n = 5n=5的时候，f[5] = 3;当n=6n = 6n=6的时候，

2020-10-07 13:44:45 203 2

原创部落卫队解题报告

题目描述：原始部落byteland中的居民们为了争夺有限的资源，经常发生冲突。几乎每个居民都有他的仇敌。部落酋长为了组织一支保卫部落的队伍，希望从部落的居民中选出最多的居民入伍，并保证队伍中任何2 个人都不是仇敌。给定byteland部落中居民间的仇敌关系，编程计算组成部落卫队的最佳方案。输入格式：第1行有2个正整数n和m，表示byteland部落中有n个居民，居民间有m个仇敌关系。居民编号为1，2，…， n。接下来的m行中，每行有2个正整数u和v，表示居民u与居民v是仇敌。输出格式：第

2020-09-15 14:03:45 353 1

原创 2020暑期牛客多校训练营第八场（K）Kabaleo Lite（贪心，高精度）

序言：考试考的这么差还写什么啊！好吧，既然都已经出来了，当然我就写了啊。第二题快餐店在考试的时候，老师说要爆longlonglong longlonglong，然而我的思路不配我写这道题然后我就去写第三题了现在我来讲一讲思路首先利润a[i]a[i]a[i]的范围最大是1e19所以必定超long long 所以我们就可以用__int128, long double 高精之类的然后因为最多可供a[1]a[1]a[1]个人选择，因为是选择连续的物品我们先求出前缀和，先用一个栈记录一下比只选

2020-09-15 13:19:25 130

原创如何统计字符串的个数

IndexIndexIndex:因为某人太菜，并不知道如何怎样转化所以就拿来写一下。定义：一个变量 = strlen(字符串数组)codecodecode：len=strlen(s);具体应用：【NOIP2018】标题统计简单题，但是我还是没得全分，只有四十就是统计字符80分代码：#include <bits/stdc++.h>using namespace std;char s[1000];int len, sum = 0;int main() { cin

2020-09-14 13:09:58 1448

原创考试总结

Index：Index：Index：今天全真考试没啥可说一开始把T1想难了花了将近四十分钟解决，然后发现C++只要写algorithmalgorithmalgorithm或者万能头就要打开函数库，哇~我直接瓦开然后又重新下了C++然后才开始继续写T2还好今天脑袋没有抽，居然把T3想出来了。。。。简单讲一下T1和T2，重点说一下T3 GM说思维很强T1 数你太美题目新颖。。。让我想到某菜这道题意思就是在两个序列里面分别找到一个最小的，然后进行合体合并，然后变成一个更小的，如果加起来的那个数等

2020-09-12 14:22:25 169 1

原创 Fake News

第三题 Fake News这道题，从题面的完全平方和那些数学知识我们就可以知道这道题就是道数学常识所以说我们能用的到一个公式——平方和:sn=n∗(n+1)∗(2n+1)/6s_n = n * (n + 1) * (2n + 1)/6sn=n∗(n+1)∗(2n+1)/6经过反复分析我们知道一定不能用普通算法做看那时间复杂度就知道必定超时所以说我们是能打表（妙蛙）通过打表可以发现只有当n==1n == 1n==1或者当n==24n == 24n==24的时候他们的和为完全平方数可以在10

2020-08-22 22:11:00 402 1

原创语言大师

第一题语言大师我在考试的时候发现我的cntcntcnt根本不会++后面才发现printf放错地方了额因为把printf放在循环里面只会更新一次就是当la==1la == 1la==1cnt=1cnt = 1cnt=1之后cnt>=2cnt >= 2cnt>=2的时候，他就不会更新了。。然后就没有然后了30分代码#include <cstdio>using namespace std;int l, k ,cnt;int main(){ scanf("

2020-08-22 22:08:06 158

原创神奇的幻方

题目描述：幻方是一种很神奇的 N ∗ N 矩阵：它由数字 1,2,3, … … , N ∗ N构成，且每行、每列及两条对角线上的数字之和都相同。当 N 为奇数时，我们可以通过以下方法构建一个幻方：首先将 1 写在第一行的中间。之后，按如下方式从小到大依次填写每个数 K(K = 2,3, … , N ∗ N) ：若 (K − 1) 在第一行但不在最后一列，则将 K 填在最后一行， (K − 1) 所在列的右一列；若 (K − 1) 在最后一列但不在第一行，则将 K 填在第一列， (K − 1)

2020-08-06 21:50:59 587

原创 JOIOJI

题目描述：JOIOJI桑是JOI君的叔叔。“JOIOJI”这个名字是由“J、O、I”三个字母各两个构成的。最近，JOIOJI桑有了一个孩子。JOIOJI桑想让自己孩子的名字和自己一样由“J、O、I”三个字母构成，并且想让“J、O、I”三个字母的出现次数恰好相同。JOIOJI桑家有一份祖传的卷轴，上面写着一首长诗，长度为N，由“J、O、I”三个字母组成。JOIOJIさん想用诗中最长的满足要求的连续子串作为孩子的名字。现在JOIOJI桑将这首长诗交给了你，请你求出诗中最长的、包含同样数目的“J、O、I”

2020-08-06 21:08:18 167

空空如也

空空如也