- 博客(81)
- 资源 (1)
- 收藏
- 关注
RSS订阅
原创 【博客总览大纲】
-------觉得自己做的到和不做的到，其实只在一念之间。---------欢迎参观小店搜索广度优先搜索BFS系列模板深度优先搜索DFS系列模板深搜和DP方法解决数的划分问题普通的搜索&枚举十字架数据结构线段树单点修改&区间求和&区间求最大值&区间求最小值[CF#458(Div. 1 + Div. 2, combined) D Bash and a Tough Math Puzzle](https://blog.csdn.net/qq_45660232/article/de
2020-05-23 00:17:11
226
1
原创 【BFS】BFS系列模板
走迷宫题目传送门题目描述：给定一个n*m的二维整数数组，用来表示一个迷宫，数组中只包含0或1，其中0表示可以走的路，1表示不可通过的墙壁。最初，有一个人位于左上角(1, 1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问，该人从左上角移动至右下角(n, m)处，至少需要移动多少次。数据保证(1, 1)处和(n, m)处的数字为0，且一定至少存在一条通路。输入格...
2020-04-08 21:59:59
969
原创 【模拟】模拟题杂集
题目描述：We have N pieces of ropes, numbered 1 through N. The length of piece i is ai.At first, for each i(1≤i≤N−1), piece i and piece i+1 are tied at the ends, forming one long rope with N−1 knots. Sn...
2020-03-24 23:47:09
474
原创 【DFS】关于深搜的系列问题
问题 F: Count Order题目描述：We have two permutations P and Q of size N (that is, P and Q are both rearrangements of (1, 2, ..., N)).There are N! possible permutations of size N. Among them, let P and Q ...
2020-02-22 15:21:20
448
原创 【bug记录】解决使用PrintWriter生成弹窗出现中文乱码的问题
先展示一波乱码展现的形式：导致乱码出现的代码：PrintWriter out = response.getWriter();response.setContentType("text/html; charset=UTF-8");out.println("<script>");out.println("alert('抱歉！注册失败,请确保两次输入的密码相同！');");out.println("history.back();");out.println("</script&g
2022-05-29 17:13:34
766
原创 【Graphviz绘制决策树】基于Graphviz绘制由字典形式表示的决策树图像
Step 1: 下载Graphviz安装包与Graphviz的安装戳一戳👉进入Graphviz下载官网（1）进入网站之后根据自身计算机的系统下载相应的安装包（2）下载之后将会得到一个如下图所示的文件（3）双击此文件进行安装此处注意选择第2项或第3项，这样会自动添加系统的环境变量当然，如果一不小心选错了，可以选择回退进行更改，也可以找到Graphviz的安装的位置，手动添加系统环境变量（随后将会讲述手动添加环境变量的具体步骤）文件并不是很大，简单起见，我就直接使用其提供的默认地址进行
2022-05-05 18:06:51
2574
原创 【计算几何】基础知识--求两个线段的交点
求两个线段的交点1、计算推导过程（参考：AcWing y总计算几何基础知识讲解）2、简单的示例代码：#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define x first#define y secondusing namespace std;typedef long long ll;typedef pair<double, d
2021-11-11 21:25:31
546
原创 【动态规划】第七届山东省省赛 Feed the monkey
Feed the monkey题目大意：有三种水果，分别是香蕉n1n_1n1个，桃子n2n_2n2个，苹果n3n_3n3个。小猴子要吃水果，每天可以吃其中一个，但是不能连续d1d_1d1天吃香蕉，连续d2d_2d2天吃桃子，连续d3d_3d3天吃苹果。求小猴子吃完所有水果的方案数。解题思路：动态规划。设状态f[i][j][k][s]f[i][j][k][s]f[i][j][k][s]表示香蕉剩余iii个,桃子剩余jjj个,苹果剩余kkk个且以sss结尾时的方案数。则只需分别考虑以三
2021-11-08 17:32:30
121
1
原创 【米勒拉宾模板】Palindromic Primes
Problem: J . Palindromic Primes记录个模板。题目大意：求 LLL 到 RRR 之间既是素数又是回文数的个数。解题思路：数据范围1e121e121e12。一般的前缀和做法解决不了。分析一下，对于一个回文数，都可以按位拆分成两部分。例如 123321123321123321，可以拆分为 123123123 和321321321 ，对于奇数位的整数12321，可以拆分为 123123123 和 212121，事实上，我们只要知道前半部分，后半部分就可以求出来，然后将前后两
2021-10-07 22:10:22
105
原创 【线段树-维护区间最小值和区间和】2021 ICPC网络赛第一场 D: Edge of Taixuan
Problem D: Edge of Taixuan评测传送门(ps: 评测时需要先花费一个币买下题目集后方可进行提交并评测。)题目大意：给出 nnn个结点，mmm次操作,每次操作给出一个区间 [l,r][l,r][l,r],和一个权值www，建立 lll 到 rrr 的完全图，边权均是 www。 计算出 “所有边的权值之和” 减去 “包含 nnn 个结点的最小生成树的权值”为最终所求答案，若无法构成最小生成树，输出指定字符串即可。解题思路：对于“所有边的权值之和”很容易就能求出来，简单画
2021-09-23 21:25:34
354
原创 【思维题】2017 CCPC现场赛秦皇岛站 问题 M: Safest Buildings
问题 M: Safest Buildings2021.09.12 中石油组队训练赛第九场赛时并没有做出来，考虑概率为 111 的时候，考虑错了。赛后参考博客顺利通过，感觉挺有意思，在此记录一波。参考博客中石油训练平台传送门题目大意：题目背景：绝地求生。不再多余赘述。直接从输入开始描述。输入第一行包含 n,R,rn,R,rn,R,r,一开始是一个以(0,0)(0,0)(0,0)为圆心，RRR为半径的一个圆,方便起见，我们称这个圆为C1C_1C1。给出 nnn 个点的坐标,每一个点都有自己唯
2021-09-12 21:57:29
143
原创 【矩阵快速幂】EOJ EOJ Monthly 2021.9 Sponsored by TuSimple A. Amazing Discovery
Problem A: Amazing Discovery评测传送门蒟蒻赛时就开了这么一个题，推了好久也还是推不出来????看了人家官方题解后，顺利AC。但是，这个推导过程有点搞怪啊，不是看了题解，我还真推不出来这个递推关系。官方题解：题解传送门下面我提供一些推导过程中的式子，可自行代入验证一波。S1=2aS_1 =2aS1=2aS2=2a2+2bS_2 = 2a^2+2bS2=2a2+2bS3=2a3+6abS_3 = 2a^3+6abS3=2a3+6abS4=2a4+2b2+
2021-09-11 22:00:07
152
原创 【链表+细节】一行盒子
一行盒子来源：2013年湖南省赛题目2021年8月25日LDUOJ训练赛LDU评测传送门训练赛时因在 交换两个值的位置处理出错（在下方注意事项中我会具体陈述），卡了好几发，在队友强力助攻下，一个样例直击 bugbugbug 要害，稍微一改，加个特判，啪的一下，哎呀，它过了，哈哈哈哈。可惜时间稍有欠缺，未能在赛时 AAA 掉，在赛后补题场上过的。在此纪念一波构思半小时，DeBugDeBugDeBug半小时，但未能在赛时AAA题的小小遗憾。题目大意：题意很清楚，完成 mmm 次操作，求奇数位置上
2021-08-25 21:28:32
77
原创 【基础莫队|暴力|扫描线＋树状数组】CF220 B: Little Elephant and Array
Problem Little Elephant and Array评测传送门题目大意：给出长度为 nnn 的一个序列，有 mmm 组询问，每组询问给出一个区间，左端点 lll ,右端点 rrr, 查询区间[l,r][l,r][l,r]中有多少个数 xxx 的出现次数恰好也等于 xxx, 符号语言表达就是cnt[x]=xcnt[x]=xcnt[x]=x.解题思路：对于这个题的解法有好多种，在这里我简单的分析一二。一：莫队解法对于莫队算法，最经典的题目应该是HH的项链, “查询一个区间有多少个互
2021-08-14 11:00:30
102
原创 【数论---组合数】组合数问题 & Irrelevant Elements
Problem 1: Contest2890 - 2021个人训练赛第38场 L：组合数问题I评测传送门题目大意:计算∑i=0n∑j=0min(i,m)(Cij%k==0)\sum_{i=0}^{n}{\sum_{j=0}^{min(i,m)}({C_i^j\%k==0})}∑i=0n∑j=0min(i,m)(Cij%k==0).解题思路：这个题的数据范围不是很大，因此可以借用杨辉三角的纵向递推关系来求组合数。对于能够被 kkk 整除的位置，我们用另外一个二维数组来进行标记这个位置所产生
2021-08-12 11:38:46
281
1
原创 【暑假训练1】2010年湖南省赛题解
写在前面训练日期：2021.07.19训练Result: 赛时AC 4题动力源泉：你想要的东西很贵，你想去的地方很远。索引导航写在前面Problem A: 汽水瓶Problem B: 弟弟的作业Problem C: 数字整除Problem D: 台球碰撞Problem E: 内部收益率Problem F: Biggest NumberProblem G: Repairing a RoadProblem A: 汽水瓶评测传送门题目详情：解题思路：这个题依据题目描述简单模拟即可，注意最后剩余
2021-07-21 15:05:43
223
2
原创 【操作系统】银行家算法的实现
文章检索器1 创作的小心思2 追根溯源3 算法设计3.1 银行家算法3.1.1 所需维护的数据结构3.1.2 算法步骤3.1.3 流程图1 创作的小心思该作旨在完成老师布置的实验任务，也借此机会系统的将银行家算法再学一遍。也可以蹭一波大家的热度，嘻嘻????，欢迎来访????????????2 追根溯源银行家算法（Banker’s Algorithm） 是一个避免死锁（Deadlock） 的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系
2021-05-04 00:35:25
12175
10
原创 【2021天梯赛】L2-L3补题记录
赛后感想据说今年的天梯赛比以往简单，咱也不知道，没啥感觉，第一次参加天梯赛，所以并不晓得以往正式赛难度如何，反正我这次是失败告终了，难受啊，本来拿个个人三等应该是势在必得的，遇到病毒之后惨了，强行卡了一个多小时，斩获0分????。哎，，不说了，都是辛酸泪啊。。。菜鸡流泪????。赛后补题那就先来解决病毒溯源这个毒瘤吧。看清题目，看清题目，看清题目。。。（ps:如果长链不唯一，输出最小序列）Problem 1 L2-083 病毒溯源（25）补题传送门解题思路：就是直接暴力的思路。病毒源
2021-04-28 00:24:09
853
8
原创 【二分图】2021年度训练联盟热身训练赛第五场 F: Group Project
Group Project传送门题目大意：现有两个班级，111 班和 222 班；两个班一共有 nnn 名同学,现在要将这 nnn 名同学分成若干个小组，每个小组由 222 名同学组成。小组内的两个同学若来自同一班级，则一定不会产生矛盾；若来自不同的班级，则可能会产生矛盾。给出 mmm 对关系，每对关系表示这两名同学若分在一个小组会发生矛盾。求最多能够划分出多少个小组，且每个小组内都不会产生矛盾。解题思路：因为同一班级的同学构成小组不会发生任何矛盾，所以应先在班级内部划分小组。若 1
2021-04-12 23:44:31
151
原创 【字符串哈希】2020牛客国庆集训派对day1 Problem A: ABB
Problem: ABB传送门题目大意：给出一个长度为 nnn 的字符串，问至少在原串的末尾添加多少个字符可以使这个串变为回文串。题意转换：在原串的基础之上，求包含末尾字符的最长的回文子串，若该最长回文子串的长度为 lenlenlen，则答案 ans=n−lenans = n - lenans=n−len;解题思路：算法：字符串哈希（双向哈希）看一波范围，n∈4e5n∈4e5n∈4e5。求最长回文子串，普通的做法是两层for循环来求，显然在该数据范围下不能使用该做法。那就换；有一个比较
2021-04-08 21:35:43
183
2
原创 【数论推导】Educational Codeforces Round 106 Problem D: The Number of Pairs
D-The Number of Pairs传送门题目大意：给定 c,d,xc,d,xc,d,x, 找出有多少对正整数对 (a,b)(a,b)(a,b) 满足下述等式：c•lcm(a,b)−d•gcd(a,b)=xc•lcm(a,b)-d•gcd(a,b)=xc•lcm(a,b)−d•gcd(a,b)=x解题思路:c•lcm(a,b)−d•gcd(a,b)=x;lcm(a,b)=a•bgcd(a,b);c•a•bgcd(a,b)−d•gcd(a,b)=x;c•lcm(a,b)-d•gcd(a,b
2021-03-31 20:28:41
126
原创 【数论---欧拉函数】龙哥的问题
AcWing 221. 龙哥的问题题目评测传送门题目描述：龙哥现在有一道题，要考考大家。给定一个整数 NNN，请你求出 ∑i=1i=Ngcd(i,N)\sum_{i=1}^{i=N}{gcd(i,N)}∑i=1i=Ngcd(i,N) 的值。输入：输入一个整数 NNN.输出：输出一个整数代表答案。数据范围：1<N<2311<N<2^{31}1<N<231输入样例：6输出样例：15解题思路：对于 gcd(i,N)=dgc
2021-03-08 20:12:28
313
1
原创 【线性DP】跳格子问题 + 光签题（取石子游戏）
Part 1 跳格子Part\ 1\ 跳格子Part 1 跳格子LDUOJ 测试平台传送门问题描述：NikolaNikolaNikola 现在已经成为一个游戏里的重要人物。这个游戏是由一行 NNN 个方格，NNN 个方格用 111 到 NNN 的数字表示。NikolaNikolaNikola 开始是在 111 号位置，然后能够跳到其他的位置，NikolaNikolaNikola 的第一跳必须跳到 222 号位置。随后的每一跳必须满足两个条件：如果是向前跳
2021-03-04 20:06:01
873
1
原创 【数据结构】第三届中国计量大学ACM程序设计竞赛个人赛 问题A: Arithmetic Problems(只含加减乘除的中缀表达式计算)
传送门题目大意：给出一个不含括号的且只含加减乘除运算符和数字的字符串作为待计算的中缀表达式。运算符的计算规则依据下方图片中描述的形式给出。目的：求中缀表达式的值。解题思路：定义两个栈，一个操作符栈，一个运算数栈。首先遍历表达式，遇到操作数直接入栈，遇到运算符将优先级高的 “乘除”（实际意义中的乘除，接下来的加减也是实际意义中的加减）做相应的运算并在操作数栈中存入运算后的结果；将优先级低的 “加减” 堆进运算符栈。经过上述的一遍操作，最后会留下一个只含加减运算以及相应的运算数在表达式中。例如：将1
2021-02-16 22:25:23
129
原创 【BFS】新飞行棋
测评地址传送门Description期末考试终于结束了。Andy同学感觉松了一口气，他决定重温小时候的快乐时光–下飞行棋。但是他弄丢了传统飞行棋需要的骰子，因此他发明了一种新型的飞行棋游戏，规则如下：棋盘上有n个格子，由近到远分别编号为1到n。对于1≤i≤n，第i个格子上写着一个正整数Ni。当玩家处于第a个格子时,他可以选择往后走Na步，或者往前倒退Na步。当然如果Na+a>n，那么他就只能选择后退；同理如果a−Na<1，那么他就只能选择前进。保证不会出现既不能前进又不能后退的格子。An
2021-01-31 00:43:55
280
2
原创 【DP】肥猪的钢琴床
A. 肥猪的钢琴床肥猪很喜欢睡懒觉，与此同时肥猪十分喜欢买各种各样神奇的床。今天肥猪买了一张很宽很宽的钢琴床，肥猪就在上面滚来滚去。这张钢琴床十分的有趣，因为它被分为n个部分，每一个部分是凸起来或者凹下去的，可是肥猪十分不喜欢相邻两个位置高低不同，因为他会滚不过去。肥猪从小就很喜欢这样的一句谚语：猪往高处走，水往低处流，所以肥猪很喜欢凸起来的部分而不喜欢凹下去的部分。现在肥猪可以把床中的某一些部分拿走，以让剩余部分所有凸起来的部分都是连起来的，这样肥猪就会很开心，因为他又可以滚来滚去了。肥猪希
2021-01-10 16:10:12
308
原创 【二分|公式推导】2020.11.24 实验室测试（2020）F:老和尚的考核
Description从前有座庙，庙里有个老和尚，老和尚的功夫高深莫测，有很多人都来到他的庙里，想要拜他为师，但是老和尚收徒的标准很高，他制定了多个考核项目，如果通过所有的考核内容，就可以正式的收他作为徒弟。现在迎来了他的第一项考核项目：给你一个容量为V的大水桶，并给出你一个时间t（以天为单位），在规定的时间内要将该水桶灌满水。前来挑战该项目的第一个人，他往水桶里灌水有一个规律，第一天只能灌入1体积的水，之后的每天灌入水的体积都比前一天多d体积。如果他能顺利通过该考核，请输出他灌满该水桶用了多少天；
2020-11-25 16:24:11
135
3
原创 【DP】方格取数
方格取数 [ Problem 4882 ] [ Discussion ]Description设有 n×mn×mn×m的方格图，每个方格中都有一个整数。现有一只小熊，想从图的左上角走到右下角，每一步只能向上、向下或向右走一格，并且不能重复经过已经走过的方格，也不能走出边界。小熊会取走所有经过的方格中的整数，求它能取到的整数之和的最大值。Input第一行有两个整数 n,m。接下来 n 行每行 m 个整数，依次代表每个方格中的整数。Output一个整数，表示小熊能取到的整数之和的最大值。Sam
2020-11-19 21:56:11
389
原创 【思维题】天气の子
I. 天气の子 [ Problem 4866 ] [ Discussion ]Description一位拥有操作天气超能力的少女说道：“呐，现在开始就要放晴了哦~”于是倾盆大雨停止了，天空放晴了……她发现一些路边的石柱接住了一些雨水，她很好奇，这些石柱接住了多少雨水呢？如下图所示，这是n 个石柱的侧视图，请计算按此排列的石柱接住了多少雨水（黑色为石柱，蓝色为雨水）。Input第一行，一个非负整数n（0≤n≤3×104 ），表示有n 个石柱。第二行，n 个非负整数组成的序列，表示石柱的高度h
2020-11-17 15:46:57
147
原创 【DP】字符串出现的次数
碰到这个题第二次了，第一次是在牛客上做过一次，当时没写出来，赛后看的题解补了一下，昨晚在LDU测试赛中再一次相遇，竟然忘了咋写的了，经过一番试错之后，顺利AC，在此记录一波。B. 有几个ACMDescription有一群人非常喜欢ACM 比赛，只要是跟ACM 相关的东西他们都非常在意。有一天，他们在鲁东大学的校园里看到了一个仅由”A”、”C”、”M”这三个字符组成的横幅。一时兴起，他们想要知道这个横幅里出现了几次”ACM”，你也是其中的一员，请编写一个程序解决这个问题。Input输入只有一行，包含
2020-11-17 13:49:37
403
原创 【容斥原理】第九届山东省赛 E. Four-tuples
E. Four-tuples评测平台DescriptionGiven l1,r1,l2,r2,l3,r3,l4,r4l1,r1,l2,r2,l3,r3,l4,r4l1,r1,l2,r2,l3,r3,l4,r4, please count the number of four-tuples (x1,x2,x3,x4)(x1,x2,x3,x4)(x1,x2,x3,x4) such that li≤xi≤rili≤xi≤rili≤xi≤ri and x1≠x2,x2≠x3,x3≠x4,x4≠x1x1≠x2
2020-10-22 15:36:02
124
1
原创 【矩阵快速幂】LDU第二次19级第二次质检 C加乐一眼题
C. 加乐一眼题 [ Problem 4306 ]Description亨亨随手出了一个序列：an=2∗an−1+n∗n,a0=0;由于加乐在寒假期间已经讲过矩阵快速幂了，所以亨亨把这个题命名为加乐一眼题，然而亨亨总喜欢骗，偷袭他的学弟学妹们，所以亨亨送给你们一句话：不会吧不会吧，真的有人觉得这是矩阵快速幂吧！！！Input输入n，在long long 范围内Output输出第n项对1e9+9取余的结果SamplesInput Copy1Output1Input Copy2Ou
2020-10-13 15:33:04
150
原创 【模拟&优先队列】UPC Contest2593 - 2020年秋季组队训练赛第十六场 问题 E: Elections
问题 E: Elections时间限制: 3 Sec 内存限制: 128 MB Special Judge题目描述Byteburg Senate elections are coming. Usually “United Byteland”, the ruling Byteland party, takes all the seats in the Senate to ensure stability and sustainable development. But this year ther
2020-10-06 16:54:02
222
原创 【DFS&反向建图&记忆化搜索】UPC Contest2592 - 2020年秋季组队训练赛第十四场 问题 D: Mysterious Treasure
问题 D: Mysterious Treasure时间限制: 1 Sec 内存限制: 128 MB题目描述WNJXYK and DIDIDI is playing a game. DIDIDI draws a directed graph G on the paper which contains n points, m directed edges and no cycle. WNJXYK starts from point 1. For every round, WNJXYK will ran
2020-10-05 21:17:23
127
原创 【数论】GCD
F. GCD-GCD-GCD [ Problem 4045 ]Description给你两个数a,m;问你在 [0,m − 1] 范围内有几个数 x 满足gcd(a,m) = gcd(a + x,m);Input第一行一个整数T；接下来T行，每行两个整数a,m;1 ≤ a < m ≤ 1e9Output针对每两个数，输出满足条件的x的数量。SamplesInput Copy34 95 1042 9999999967Output61999999996
2020-09-28 16:02:00
801
1
原创 【最短路】洛谷P1346 电车
题目传送门解题思路：关键在于建图。以每个站点为顶点，是否需要转换开关为边建图。之后就求一个最短路即可，这个题求最短路的方法有多种，鉴于数据这么小，那就用最暴力的 floydfloydfloyd吧，下面附上代码。上代码：#include<bits/stdc++.h>using namespace std;const int N = 110;int g[N][N];int n;void floyd(){ for(int k = 1;k <= n;k++) { fo
2020-09-16 11:02:22
93
原创 【枚举】UPC Contest2575 - 2020年秋季组队训练赛第八场 问题 B: Building Boundaries
问题 B: Building Boundaries时间限制: 1Sec1 Sec1Sec 内存限制: 128MB128 MB128MB题目描述Maarja wants to buy a rectangular piece of land and then construct three buildings on that land.The boundaries of the buildings on the ground must have rectangular sizes a1 × b1 ,
2020-09-15 16:20:51
252
原创 【字符串哈希】UPC Contest2569 - 2020年秋季组队训练赛第六场 G:Typo
问题 G: Typo时间限制: 10Sec10 Sec10Sec 内存限制: 128MB128 MB128MB题目描述It is now far into the future and human civilization is ancient history. Archaeologists from a distant planet have recently discovered Earth. Among many other things, they want to decipher the
2020-09-14 21:32:54
240
原创 【数学几何】UPC Contest2569 - 2020年秋季组队训练赛第六场 问题 H: The Biggest Triangle
问题 H: The Biggest Triangle时间限制: 3Sec3 Sec3Sec 内存限制: 128MB128 MB128MB SpecialSpecialSpecial JudgeJudgeJudgeThree infinite lines define a triangle, unless they meet at a common point or some of them are parallel.Given a collection of infinite lines,
2020-09-13 20:06:38
168
原创 【二进制枚举】 UPC Contest2574 - 2020年秋季组队训练赛第七场 J: Automatic Control Machine
问题 J: Automatic Control Machine时间限制: 1Sec1 Sec1Sec 内存限制: 128MB128 MB128MB题目描述The company has produced an Automatic Control Machine (ACM for short) that is very popular. Due to its complete and powerful features, the company is preparing to redesign af
2020-09-13 11:06:05
183
Windows下词法分析分析器Flex和语法分析器bison的使用说明.pdf
2021-12-19
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人