- 博客(194)
- 收藏
- 关注
RSS订阅
原创 一些模版（基础）
高精度：加法#include<iostream>#include<cstdio>#include<cstring>#include<string> using namespace std; char a1[1000],b1[1000
2018-12-29 23:22:53
149
原创 CSP202303T3LDAP——vector+unordered_map
个，每个用户具有这些属性中若干个，一些属性可能有也可能没有，每个属性有一个值。找出并输出每一个匹配表达式相匹配的用户的 DN值。表示或，两个表达式有一个可以找到匹配的用户即成立。表示与，两个表达式都要可以找到匹配的用户即成立。个用户，每个用户有一个。表示属性a的值不为b。
2024-03-24 20:16:32
261
原创 202109CSPT4收集卡牌
枚硬币交换一张没有获得过的卡。求获得所有种类的牌的概率。如果这张卡牌已经获得，就会转化为一枚硬币。种不同的卡牌,每一次抽卡获得第。
2024-03-10 20:15:08
364
原创 202112CSPT4磁盘文件操作
全为空且上次占用id号全为目标id号，则恢复删除结果并输出OK；全为同目标id，则删除id号以及值val并输出OK；如果成功写入则输出写入成功的最右位置，否则输出-1。:从L开始到R或遇到第一个其他非空id号为止，写入。:查找单点P的id号以及val值；
2024-03-02 14:18:41
370
原创 **202303CSPT4星际网络II
如果地址已经分配满或分配给别人则分配失败，输出NO；地址是否完整地分配给了某个用户。若是，回答该用户的编号；检查单点地址是否被分配，分配输出用户id,否则输出0。
2024-02-22 14:25:08
368
原创 202012CSPT5星际旅行
内所有点的三维坐标分别相加之后求平方之和，再mod1,000,000,007；内所有点的三维坐标分别变换为。内所有点的三维坐标分别增加。内所有点的三维坐标分别乘。个点,每个点有三维坐标。
2024-02-05 15:34:11
783
原创 202104CSPT5疫苗运输
题意：有n个点，m条环路线，每条路线有若干个点且有一辆车b在环线上不断运行，每辆车0时刻从路线的起点出发，到下一点需要若干时间。从一条线路切换到另一条线路需要两辆车同时同地，现在求从点1到其他各个点的最小时间。
2024-02-02 17:10:26
321
原创 201712CSPT4行车路线
题意：一个无向连通图有n个点，m条边，每一条边有权值和一个编号id。id=0时，经过该边花费为其权值；当id=1时，经过该边花费为连续经过id为1的边的权值平方。求从1到n最小花费。
2024-01-30 15:40:57
392
原创 201903CSPT5 317号子任务
题意：有n个点，m条无向边。n个点中有一些是行星发动机点，现在要求计算出每个点最近的k个行星发动机点的最短路径之和，如果某个点能够达到的行星发动机点不足k个，则求其能到达行星发动机点的最短路径之和。
2024-01-24 14:45:00
776
原创 201703CSPT4 地铁修建---最小生成树（从小到大对边排序～ Kruscal法）
本题与最小生成树思路相似，与之不同的最小生成树的结束条件是当图中所有的点都在树上，而题的结束条件应当是第一个点和最后一个点连通。所以我们改变结束条件，可以使用Kruscal算法，从小到大对边排序，在构建生成树时就可以解决问题。连通，隧道建设需要时间，即边的权值，求。条边，选择若干条路径构建隧道使得从。题目大意：给定一个无向简单图，有。
2024-01-17 13:24:22
378
1
原创 201812CSPT4数据中心——最小生成树（从小到大找出生成树的最长边）
本题主要注意审题，理解题目要求的是最小生成树中的最长边。可以使用Kruscal算法，因为它是按边从小到大求解的，可以更加方便解决问题。个点，m条路径，现在找出它的最小生成树和它最小生成树中的最长边。题目大意：一个无向图有。
2024-01-17 09:54:38
367
原创 2023 03 CSPT2 垦田计划——二分
取决于耗时最长的区域。为了加快开垦进度，准备在部分区域投入额外资源来缩短开垦时间：在第。单位资源可供使用，试计算开垦最少需要多少天。CSP认证的真题，标准的二分答案。区域可以同时开垦，所以总耗时。单位资源，便可将其开垦耗时缩短。单位资源，将其开垦耗时缩短为。
2023-09-10 11:21:53
203
原创 [NOI1997] 最优乘车 最短路径+巧妙建图
本题最重要的是如何将其转化为最短路的问题，如果我们按照公交线路建图，就是模拟无法解决。所以我们换个思路建图，从左向右将一条线路的站点，都与这条线路的站点相连。这样建图可以使同一条线路上的任意两点间的距离为1，最少换乘次数=最少乘车次数-1。而最少乘车次数就转化为在权值全为1的图的最短路。条巴士线路的信息，从左至右按运行顺序依次给出了该线路上的所有站号相邻两个站号之间。寻找一个最优乘车方案，使他在从饭店乘车到公园的过程中换车的次数最少。最后再注意输入格式，用字符串来读入，还要把第一行行末空格给去掉。
2023-08-18 11:54:24
147
原创 邮递员送信 单源最短路+反向建边
就是标准的单源最短路；而返回的时候就是多到一，多源最短路比较麻烦。这时候我们邻接矩阵倒过来，从多到一的最短路变式的路径“反向建边”，就变成一到多的单源最短路。邮递员每次只能带一样东西，运送每件物品过后必须返回邮局。求送完东西后回到邮局最少需要的时间。有一个邮递员要送东西，邮局在节点。所有的道路都是单行的，共有。样东西，其目的地分别是节点。
2023-08-15 17:53:40
132
原创 部落划分 最小生成树+并查集+贪心
一道最小生成树的变式题,把所有野人之间的距离预处理一下，每次找到最小的一条边，把这两个野人合成一个部落，一直重复，一共有k个部落，我们只需要找n-k条边，这些都是最小距离，所以剩下的就是最大了。个部落,两个部落的距离,定义为部落中距离最近的那两个居住点的距离。对于任意一种部落划分的方法，都能够求出两个部落之间的距离，聪聪希望求出一种部落划分的方法，使靠得最近的两个部落尽可能远离。个野人居住坐标，野人总共被分为了。
2023-08-11 14:23:22
119
原创 公路修建 最小生成树prim算法
首先审题，可以知道城市选择一个与它最近的城市，再计算公路总长度，这可以看出最小生成树的板子。再看规则一说明是无向图，而规则二其实不起作用，是迷惑项。因为每个城市找最近的，所以三个以上城市成环的情况是不可能出现的。个城市,政府决定修建公路,在每一轮中，每个城市选择一个与它最近的城市，申请修建通往该城市的公路。政府负责审批这些申请以决定是否同意修建。最小生成树有两个算法一个是Kruskal，它适用于稀疏图。而本题属于稠密图，使用Kruskal会超时，所以改用Prim算法。计算出将要修建的公路总长度。
2023-08-08 14:36:16
156
原创 [SCOI2005] 繁忙的都市 并查集/最小生成树
对于分值最大的道路分值尽量小，可能想到二分法来求，但其实不需要，我们只需要按照最小生成树的思路来构造一棵树，整棵树都是最小的，那么最大值一定小了。个路口，交叉路口之间有道路相连，两个交叉路口之间最多有一条道路相连接。这些道路是双向的，且有一个分值。本题主要是最小生成树的运用，第一问求道路数，每个点都能直接或间接连接最少情况就是一棵树，所以直接输出。求选出了几条道路，分值最大的那条道路的分值是多少。
2023-08-04 15:46:42
99
原创 kotori的设备 二分+贪心
题目要求能使用时间的最大值，我们使用二分答案法。对于二分使用的时间，若设备原有能量大于使用时间需要的能量，则不需要使用充电宝。否则用充电器充电，记录需要的能量，再比较需要的能量总和和充电器最多提供的能量。当所有设备的能量消耗速度的总和小于等于充电宝的充电速率时，可以无限使用。有一个充电宝，每秒可以给接通的设备充能。把这些设备一起使用，直到其中有设备能量降为。，最多能将这些设备一起使用多久。个可同时使用的设备,第。
2023-08-01 16:13:09
127
原创 [USACO08FEB] Meteor Shower S BFS
本题要求计算最少需要多少时间可以看出需要使用广度搜索，需要注意的是我们需要计算每个格子化为焦土的时间，这个时间应该是最小值。个时刻中，移动到相邻的格子中。计算最少需要多少时间才能到达一个安全的格子。个相邻的格子都化为焦土，无法在这些格子上行走。开始行动，只能在第一象限中，平行于坐标轴行动，每。流星会将它所在的格子，以及周围。会坠落在农场上，其中第。
2023-07-27 12:02:06
181
原创 海底高铁 前缀和+贪心
个城市,每个城市之间有一段铁路，经过两个相邻的城市之间，必须单独购买这一小段的车票，第。段铁路要经过多少次，再比较两者谁便宜。本题数据比较大，需要使用前缀和来统计区间和。对于每一小段铁路要么全部买纸票，要么全部刷卡。元的工本费购买一张卡，然后乘坐这段铁路一次就只要扣。个城市,求最少会花掉多少的钱。段铁路购买纸质单程票需要。元，或购买卡，对于第。
2023-07-25 12:28:46
66
原创 倒水问题 BFS+记忆化搜索
对于这个问题，最基本的思路肯定是需要利用两个桶反复取水倒水，最后得到目标值。然而，因为每次都会有6个状态入队，所以说重复的做法有非常多。当从一个水壶倒进另一个水壶时，如果第一个水壶倒空，或者第二个水壶装满就不能再倒了。因为水壶无刻度有容量，这意味着从水井取水但不把水壶装满是无意义的。种操作，并压入队列，记下这个状态后继续搜索。解决问题的目标是给出一系列倒水的步骤，使水壶中的水量恰好是。里有若干水所需要的步骤数，步骤数最小的才入队，简化步骤。是6加仑，水量是8加仑，则从水壶。倒进水壶B时，让水壶。
2023-07-20 10:32:25
261
原创 CSP-S 2019————Emiya 家今天的饭————DP+思维
题解：本题主要考查DP+思维。简要题意：一个矩阵，要求每行只选一个节点，每列选的节点不能超过所有选的节点的一半，不能不选，给出每个节点的选择方案数，求总方案数。1.DP+思维：(1).维护每列已选的节点复杂度太大，应该不行，所以先不考虑每列不超过一半，求出总数，再减去不合法的方案数，应用逆向思维转换问题。(2).设dp[i][j][k]dp[i][j][k]dp[i][j][k]表示前i...
2020-01-28 22:28:33
540
原创 Codeforces 831D Office Keys————DP/二分
题解：本题主要考查DP/二分。简要题意：给你nnn个人，有kkk把钥匙，终点为mmm.每个人要求拿一把钥匙到终点，问多长时间，能够使得所有人都到达。把所有人的位置以及钥匙的位置全部sort一遍，1.二分：排序后，前一个去的钥匙位置一定在后一个人取得钥匙前面，否则交叉浪费时间。然后二分最长时间，从左向右验证。2.DP：设dp[i][k]dp[i][k]dp[i][k]表示前iii个人，前jj...
2020-01-22 16:02:41
172
原创 USACO06NOV Corn Fields————状压DP
题解：本题主要考查状压DP简要题意：有m∗nm*nm∗n的田地，000表示贫瘠，不能用来种草;111表示肥沃，可以种草。要求没有哪两块草地有公共边，求共有几种方案。1.状压DP：数据范围为(1≤m≤12;1≤n≤12)(1≤m≤12;1≤n≤12)(1≤m≤12;1≤n≤12)，应该状压。状压DP一般步骤：(1).预处理：处理每一行的情况，用f[i]f[i]f[i]表示；(2).判断合法性...
2019-12-21 19:47:56
146
原创 [JSOI2008]星球大战————并查集+思维
题解：本题主要考查并查集。简要题意：nnn个点mmm条边，整数kkk，表示将删除的点的数。求出每一次删除之后连通块的个数。1.并查集：因为题目要求删除之后连通块的个数，想到要用并查集。可是并查集删除操作实现起来很难时间复杂度会很高，怎么办？所以我们要使用逆向思维！把删除转换成连接，从后往前处理。记录点与点之间是否联通，联通且没有被删除就连上。再恢复点再判断。接下来就是并查集判断联通块了。代码...
2019-12-15 13:15:21
89
原创 P1472奶牛家谱 Cow Pedigrees————树形DP
题解：本题主要考查树形dp。简要题意：一些二叉树总共有NNN个节点，每一个节点的度是000或222。树的高度为KKK，高度是从根到最远的那个叶子所需要经过的结点数。有多少不同的树结构。1.树形dp：先设dp[i][j]dp[i][j]dp[i][j]表示iii个点小于等于jjj层的方案数,考虑dp过程：一般树形背包，除非是多叉树用分组背包只能用dfs写，否则可以先考虑写一个记忆化搜索(是一篇...
2019-12-03 21:05:01
179
原创 NOIp2016提高组 蚯蚓————单调队列
题解：本题主要考查单调队列。简要题意：题面1.单调队列：(1).对于505050分的q=0q=0q=0,也就是蚯蚓不会增长和合并果子差不多，我们就可以用优先队列处理。(2).对于858585分的数据，和合并果子的思想差不多，就是没被切的蚯蚓加一定长度。用优先队列和数组模拟都不好处理，这就需要转换思想。利用差分的思想，没被切的蚯蚓加一定长度就是被切的减少，每次再记录累计加的长度即可。代码如...
2019-11-30 15:37:42
159
原创 [JLOI2014]松鼠的新家————树链剖分
题解：本题主要考查树链剖分。简要题意：一颗树，有n个房间，并且有n-1根树枝连接。小熊维尼先去a1a_1a1，再去a2a_2a2最后到ana_nan，每走到一个房间，他就可以从房间拿一块糖果吃，最后一个房间不用，求每个房间至少需要放多少个糖果。1.树链剖分：路过的点都加一，可以想到树链剖分，每一次将a[i]a[i]a[i]到a[i+1]a[i+1]a[i+1]的节点加一，在一次修改后，因...
2019-11-24 21:24:44
112
原创 CSP-S2019 括号树————栈+前缀和+dfs+树
题解：本题主要考察栈和dfs+树。简要题意：一颗树的每个结点上有一个括号，可能是 ((( 或 )))。sis_isi是个括号串，但不一定是合法括号串，sis_isi中有多少个互不相同的子串是合法括号串。sis_isi共有kik_iki个不同子串是合法括号串， 你只需要告诉小 Q 所有i×kii×k_ii×ki的异或和。1.栈+前缀和：首先我们看题，求合法的括号子串。我们就可以用栈来存...
2019-11-20 22:07:01
626
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人