- 博客(22)
- 收藏
- 关注
RSS订阅原创 [NOI2010] 能量采集
分析等价于求 ∑i=1n∑j=1m((gcd(i,j)−1)⋅2+1)\sum_{i = 1}^{n}\sum_{j = 1}^{m}((\gcd(i,j) - 1) \cdot2+1)∑i=1n∑j=1m((gcd(i,j)−1)⋅2+1)化简 ∑i=1n∑j=1m(2⋅gcd(i,j)−1)=∑i=1n∑j=1m2⋅gcd(i,j)−n⋅m=2⋅∑i=1n∑j=1mgcd(i,j)−n⋅m\sum_{i = 1}^{n}\sum_{j = 1}^{m}( 2\cdot\gcd(i,j) -
2021-07-24 12:12:10
115
1
原创 核电站
题目核电站题目背景A市发生能源危机，被迫大量使用核能发电，A市领导决定在郊区建造核电站，但是有的地方地形复杂，无法建造核电站。题目描述A市可以近似成一个N∗MN * MN∗M的矩形，用 0,10,10,1 表示，000 表示平地，可以建造核电站，111 表示地势复杂区，无法建造，A市领导又不希望核电站离得过于太近，于是规定每个核电站周围888个方向的方格上都不能造核电站，如图：由于资金短缺，最多只能建造kkk个核电站，求在郊区建造kkk个发电站的方案数输入格式第111行：描述郊区的大小,两个
2021-02-02 20:40:50
295
原创 [COGS] 赛艇表演
[COGS] 赛艇表演题目描述题目描述输入格式输出格式样例输入样例输出数据范围解题过程思路代码感想题目描述题目描述小明去某个地区观看赛艇比赛，这个地区共有n个城市和m条道路，每个城市都有赛艇比赛，在第i个城市观看赛艇表演的价钱为ai，去其他城市观看也需要支付赛艇表演的价格。任意两个城市之间通过一条公路连接，并且道路是双向通行的，观看赛艇比赛时经过的每一条道路都要支付一定的过路费，观看完比赛返回家时经过的每一条道路也要支付过路费。对于每个城市u，你需要为小明确定一个城市v，使得从u出发，前往v看赛艇表
2020-10-06 23:50:30
175
原创 [luogu P2114] 起床困难综合症
[luogu P2114] 起床困难综合症题目描述解题过程思路代码感想题目描述点击此处查看题目描述解题过程思路位运算，每一个二进制位只有两个选择 000 或 111 ，那么我们可以设置一个全 111 串和一个全 000 串进行模拟，最终尽可能的选多的 111 ，贪心法代码#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>#include &l
2020-10-06 18:57:44
101
原创 [luogu P2704] 炮兵阵地
[luogu P2704] 炮兵阵地题目描述解题过程思路流程题目描述点击此处查看题目描述解题过程思路这道题的列数的数据范围很小，我们考虑用状态压缩进行动态规划流程设 a[i]a[i]a[i] 表示第 iii 行的地形(0101用十进制存储) 先存储二进制地形，山峰 HHH 表示 111 ，平原就不用管，表示 000设 dp[i][j][k]dp[i][j][k]dp[i][j][k] 表示在上一行的状态为 kkk 时，第 iii 行的状态为 jjj 时的最大炮台数直接暴力往上枚举整个状态的
2020-10-06 07:43:58
103
原创 [COGS] 电梯
[COGS] 电梯题目描述题目描述输入格式输出格式样例输入样例输出提示解题过程搜索&DP差分优化差分实现代码感想题目描述题目描述无所事事的Cinzo决定用坐电梯的方式来打发时间。他住在一个N层的房子中，最底下为1层，最高处为N层。他从他家所在的第A层出发，并决定连续坐K次电梯。但由于迷信的缘故，B在中国被视为是不幸运的，所以整座楼并没有第B层。也是因为这个原因，如果Cinzo想从第X层出发到达第Y层，他希望Y能满足|X - Y| < |X - B|。每次电梯到达后，Cinzo都会将电
2020-10-04 21:04:21
151
原创 [数据结构]稀疏表 ST表
稀疏表 ST表写在前面正文内容实现初始化过程查询后记写在前面有错误请指出正文内容ST表 是一个维护区间 最大值 或 最小值 的数据结构ST表 用 O(nlogn)O(n \log n)O(nlogn) 的时间预处理，O(1)O(1)O(1) 的时间查询设 f[i][j]f[i][j]f[i][j] 表示为 下标 iii 起，2j2^j2j 个数中的最大值，用倍增实现很好理解实现本博客以最大值为例初始化设维护的数组为 a[i]a[i]a[i]f[i][0]=a[i]f[i][0]
2020-10-04 20:37:25
126
原创 [数论]扩展欧几里得
扩展欧几里得导语正文讲解代码结语导语这是一个有关数论的知识，涉及最大公约数正文讲解设 aaa ， bbb 是两个正整数，求 xxx ， yyy 满足 ~~~~~~~~ ~~~~~~~~ &nbs
2020-09-30 22:18:16
57
原创 [位运算]常见的位运算
状态压缩里常见的位运算写在前面正文x&(-x)未完待续…写在前面正文x&(-x)返回 x 的二进制数最低位为１的权值例如10100最低位的1权值是41001010最低位的1权值是2111最低位的1权值是1未完待续…...
2020-09-26 20:55:40
175
原创 [luogu P1990] 覆盖墙壁
[luogu P1990] 覆盖墙壁题目描述解题过程思路代码感想题目描述点击此处题目描述解题过程递推思路本蒟蒻弱弱地看了题解才知道思路f[i]f[i]f[i] 表示铺满前 iii 列墙壁的方案数如果最后以这种状态结尾，方案数是 f[i−1]f[i - 1]f[i−1]如果以这种状态结尾，方案数就是 f[i−2]f[i-2]f[i−2]如果放 L 形，因为 L 形可以翻转，所以方案数要乘 2 ，放两个 L 形结尾，方案数就是 f[i−3]f[i - 3]f[i−3]放两个 L 形 和
2020-09-13 13:50:42
129
原创 [luogu P1928] 外星密码
[luogu P1928] 外星密码题目描述解决过程思路代码感想题目描述点击此处查看题目描述解决过程递归思路递归求解，遇到括号就进行下一层，记得要匹配一下括号，还要加上输出括号后面的 ~~~~ 举个例子af[43bc]deaf[43bc]deaf[43bc]de遇到 afafaf 直接输出即可，然后找到一个 [[[ ，求出数字 434343 然后向后查找找到能够匹配的 ]]] ，然后循环 43434
2020-09-13 12:30:28
284
原创 [luogu P3799] 妖梦拼木棒
[luogu P3799] 妖梦拼木棒题目描述解决过程思路代码感想题目描述点击此处查看题目描述解决过程暴力不多阐述，很显然是无法AC的解决此题需要用到组合数思路这道题要求拼成等边三角形，我们设三边长为 a,b,ca ,b ,ca,b,c 则 a=b=ca = b = ca=b=c ，由于是用四根拼成，那么其中必有两条边相等，在此我们设 a=ba = ba=b ，c=i+jc = i+jc=i+j，把数据存到桶里面，桶为 fff那么需要 f[c]>=2f[c] >= 2f[c]&
2020-09-13 11:25:50
133
原创 [组合数学]康托展开
康托展开写在前面正文公式举个例子康托展开逆康托展开后记写在前面康托展开 是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。通俗一点来说就是 每一个排列 都代表 一个自然数表示他在 所有排列中 的 排名很明显可以用暴力搜索，此处不过多阐述正文主要讲解康托展开的实现以及逆康托展开的实现，推荐习题 P1088【火星人】公式康托展开 ：X=an(n−1)!+an−1(n−2)!+...+a1⋅0X = a_
2020-09-13 09:52:30
106
原创 [NOIP2000] 单词接龙
[NOIP2000] 单词接龙题目描述题目描述输入格式输出格式样例输入样例输出题解思路代码实现感想题目描述题目描述单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at 和 atide 间不能相连。输入格式输入的第一行为一个单独的
2020-08-30 20:01:09
294
原创 [字符串]KMP算法实现字符串匹配
KMP算法实现字符串匹配写在前面正文目的举一个简单的例子流程流程next数组后记写在前面本蒟蒻初学KMP，肯定会有很多错误，请大家指出正文目的说道字符串匹配，大家首先想到的应该是朴素算法，一位一位匹配，匹配失败向右移动一位接着匹配，算法的时间复杂度是 O(n)O(n)O(n)举一个简单的例子A = “aababaabaab”B = “aabaab”（制作不易）暴力算法时间直接上天，这时候要是能自动跳过一些错误就好了比如 ：直接跳到就可以避免匹配一大堆了怎么做到呢流程流程
2020-08-27 22:34:36
326
1
原创 [平衡树]旋转Treap实现平衡树
旋转Treap实现平衡树写在前面正文目的操作旋转右旋左旋更新节点数插入删除后记写在前面首先你需要了解 二叉搜索树（百度链接）。这就是一个标准的二叉搜索树，是一颗满二叉树很好，树高 lognlog nlogn ,查询的复杂度也就是 lognlog nlogn。但是总有 毒瘤 的出题人卡数据，把你的树卡成链查询复杂度为 nnn，这肯定不行啊，时间复杂度跟暴力一样了，怎么才能把树造的平衡一点呢。正文Treap 的由来是 Tree + Heap 既是一棵树，又有堆的性质，所以我们有时候叫他树堆
2020-08-24 13:00:05
202
原创 [HNOI 2014] 米特运输
[HNOI 2014] 米特运输题目描述题目题目描述解题过程感想题目描述一道题目题目描述解题过程感想本人真是太弱了，再接再厉谢谢大家
2020-08-19 10:41:14
82
原创 [東方S2] 伊吹萃香
[東方S2] 伊吹萃香题目描述题目题目描述输入格式输出格式样例输入样例输出输出说明数据范围解决过程思路代码感想题目描述题目题目描述在幻想乡，伊吹萃香（いぶき すいか）是能够控制物体密度的鬼王。因为能够控制密度，所以萃香能够制造白洞和黑洞，并可以随时改变它们。某一天萃香闲着无聊，在妖怪之山上设置了一些白洞或黑洞，由于引力的影响，给妖怪们带来了很大的麻烦。于是他们决定找出一条消耗体力最少的路，来方便进出。已知妖怪之山上有N个路口(编号1…N)，每个路口都被萃香设置了一定质量白洞或者黑洞。原本在各个路口
2020-08-18 23:13:42
240
原创 [最近公共祖先]tarjan算法实现LCA
tarjan算法实现LCA写在前面正文目的举个简单的例子朴素算法流程1.存储询问2.遍历代码1.定义2.记录查询3.并查集基本操作4.遍历后记写在前面本蒟蒻晚上闲得无聊，随便写写，感谢大家的观看有错误请多多指出正文本文讲解如何使用 tarjan算法 求LCAtarjan算法是一种 离线 算法目的首先了解一下 LCALCA（Least CommonAncestors），即最近公共祖先，是指这样一个问题：在有根树中，找出某两个结点u和v最近的公共祖先（另一种说法，离树根最远的公共祖先）
2020-08-17 22:51:14
243
原创 [USACO Feb09] 牡牛和牝牛
[USACO Feb09] 牡牛和牝牛题目描述题目题目描述输入格式输出格式样例输入样例输出输出说明解决过程思路代码感想题目描述题目题目描述约翰要带N(1≤N≤100000)只牛去参加集会里的展示活动，这些牛可以是牡牛，也可以是牝牛．牛们要站成一排．但是牡牛是好斗的，为了避免牡牛闹出乱子，约翰决定任意两只牡牛之间至少要有K(O≤K<N)只牝牛．请计算一共有多少种排队的方法．所有牡牛可以看成是相同的，所有牝牛也一样，答案对5000011取模。输入格式一行，输入两个整数N和K.输出格式一个
2020-08-16 09:12:32
466
原创 [网络流]EK算法实现最大流
EK算法实现最大流写在前面正文目的举个简单的例子流程1.找路具体操作2.修改流量具体操作3.建反向边具体操作代码1.定义2.BFS寻找路径3.更新边4.调用后记写在前面本蒟蒻好激动啊，这是我第一次 写博客 如有错误请指出，谢谢。本博客为了能更加通俗易懂，没有使用例如：增广路，残量网络等词语。正文本文将讲解EK算法求最大流目的首先要了解求最大流是干啥的给定指定的一个有向图,其中有两个特殊的点源S(Sources)和汇T(Sinks),每条边有指定的容量(Capacity),求满足条件的从S到
2020-08-14 16:04:14
846
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人