- 博客(38)
- 收藏
- 关注
RSS订阅原创 Verilog Practice in [HDLBits]
Proceduresalways blocks (combinational)procedural blocks 的作用和 assign 语句差别不大，但是相比于assign语句提供了更多的语法（比如if-else，case等等）。比如下面这种写法就是等价的：assign out1 = a & b | c ^ d;always @(*) out2 = a & b | c ^ d;即可以使用always @(*)隐式的触发always，也可以使用always @(a,b...)显式
2021-05-11 18:41:09
145
原创 [Python] [LeetCode] [每日一题] 1011. 在D天内送达包裹的能力
题意：有一艘货轮在D天内往返于A B港口运送货物，货物重量的序列为weights（不可改变顺序），求一个最小的货轮载重能力，使得货轮能够在D天内运送完所有货物。思路：第一反应是二分答案，因为载重能力越强，所需时间越少。考虑是否能O(n)检查答案。对于货物x，假如可以在当天装上货轮，那么留到第二天装上货轮一定不比当天装货优，因此直接扫描序列，每一天尽可能装更多的货物，检查D天内是否能装完。复杂度O(nlog(n*weight))class Solution: def shipWithinDay
2021-04-26 19:20:11
180
原创 [Python] [LeetCode] 146. LRU 缓存机制
双向链表+哈希表这个设计题蛮有意思的，学到了很多最近访问的放在前，许久未访问的放在后，同时支持动态空间、末尾删除，顶端插入。第一时间想到双向链表。但是链表不支持O(1)查询，因此加一个哈希表。双向链表指针指向自己代表null，这样的话delete和insert操作就不必判空重载__repr__方便输出调试LRU支持 get put 方法get()使用哈希表取得目标节点的指针，返回键值。同时删除被访问节点并插入表头。 O(1)put()先判断是否已经存在于表中，如在表中则修改键值并删除节
2021-04-13 19:25:14
97
原创 [Python] [LeetCode] 22. 括号生成 最优美的暴力
我也不知道该怎么形容，我见过最优美而简洁的搜索方法。这就是暴力美学吧。不用额外的剪枝，直接通过状态上的定义就可以去重。至于为什么要这么定义，我们分析以下状态：假设我们现在有一个有效的括号序列s[n-1]，该括号序列有n-1对括号，要生成具有n+1对括号的有效序列，我们只能合法的加上一对括号，具体来说有三种情况：(s[n-1]) s[n-1]() ()s[n-1]这三种情况都可以被以下格式概括：(s[n-1])s[0] (s[n-2])() ()s[n-1]其余的解释我只能想到排除法：介于递推
2021-04-11 23:27:33
123
原创 [Python] [LeetCode] 456. 132模式
单调队列变体注意到132模式中32为时序上有序，联想到单调队列由于枚举1的时候需已经计算过32，因此反向遍历靠近1的要足够高，因此维护从栈底到栈顶的单增序列加入任意元素至栈中时，弹出小于它的元素。此时可以将弹出的元素看做2，当前的元素看做3，只要是被弹出的元素，必定是被一个更大的元素所弹出，切该元素必定在被弹出元素的前方。因此仅需判断所有被弹出的元素中的最大值是否大于当前枚举的元素即可class Solution: def find132pattern(self, nums: List[i
2021-04-11 22:46:43
98
原创 [Python] [LeetCode] 1458. 两个子序列的最大点积 双百
设dp[i][j]为nums1的前i位和nums2的前j位中取出的等长子序列的最大点积。假设新加入nums1[i]和nums2[j]至子序列，则：dp[i][j] = dp[i-1][j-1] + nums1[i] * nums2[j](乘积可能为负)假设不加入任何数，则：dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])发现转移方程仅与i-1有关，可以节省空间class Solution: def maxDotProduct(s.
2021-04-11 22:31:02
113
原创 [Python] [LeetCode] 338. 比特位计数
经典递推设f[num]为当前数字含有的二进制1的个数如果当前数为奇数，则二进制末尾为1，f[num]=f[num>>1] + 1如果当前数为偶数，则二进制末尾为0，f[num]=f[num>>1]class Solution: def countBits(self, num: int) -> List[int]: ans = [0] for i in range(1, num + 1): ans.appen
2021-04-11 21:55:01
101
原创 [Python] [LeetCode] 剑指 Offer 52. 链表的公共节点
被秀到了判断两链表是否有交点，有则输出交点，无则输出 null这道题解法很多，最简洁的解法为：# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution: def getIntersectionNode(self, headA: ListNode, head
2021-04-10 16:50:37
106
原创 Python dict类型 哈希表实现
reference:https://blog.csdn.net/qq_37049781/article/details/83959365
2021-04-10 16:28:43
134
原创 [Python] [LeetCode] 剑指Offer 65. 不用加减乘除做加法 （Python负数存储原理）
基本思路写出真值表，^得到当前位运算后结果，&得到进位，考虑到进位会进一步引发进位，要while循环至进位为0。由于每一位的操作相同，每次直接整体操作，无需按位操作。注意的点Python中的负数以补码形式储存，这就意味着其高位有无穷个1。此题限制在32位有符号整数的语境中，因此开头先用0x7FFFFFFFF获取0 ~ 32位，运算后判断是否为负数，如果为负数则需补齐高位的所有1。补齐方法：直接用 ~ 会将运算结果也取反，因此先对0 ~ 32位取反，再全部取反，相当于对32位之后全部取反。妙
2021-04-10 14:58:21
106
原创 Python 实现 快速排序
快排原理：https://blog.csdn.net/weixin_42109012/article/details/91645051def sort(L, R, ar): if L >= R: return lf, rg = L, R # 指定L处的数字为基准x while lf < rg: while rg > lf and ar[rg] >= ar[L]: rg -= 1 # 仅
2021-04-09 00:38:10
104
原创 [模拟考试题][神题]Star Sky[状压DP][BFS][差分]
题意：给你n个排成一排的灯，0代表开着，1代表关着，有k盏开着的灯。现在你有m种不同长度的电线，可以使得leni那么长的区间反转（0变1,1变0）。现在问你使得整个区间的灯全部开着的最少的操作数。N 真心神题。首先我们观察到序列上的操作都是对于一整段区间而言的，自然想到差分（自然个鬼啊！！），我们将序列用异或差分，然后对一个区间的取反操作变成了对端点的取反。满足条件的序列是全为0的。k
2017-10-24 21:58:34
500
原创 Bzoj - 4552 排序 [二分答案] [线段树]
4552: [Tjoi2016&Heoi2016]排序Time Limit: 60 Sec Memory Limit: 256 MBSubmit: 1400 Solved: 710[Submit][Status][Discuss]Description在2016年，佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题，现在他在研究一个难题，需要你来帮
2017-10-23 21:24:17
380
原创 NOIP 普及组 车站分级 [拓扑排序][线段树优化连边][虚点优化]
3294 车站分级 2013年NOIP全国联赛普及组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold题解题目描述 Description一条单向的铁路线上，依次有编号为1, 2, …, n的n个火车站。每
2017-10-12 20:58:00
825
原创 Bzoj - 1499 [Noi2005] 瑰丽华尔兹 [DP][单调队列优化]
1499: [NOI2005]瑰丽华尔兹Time Limit: 3 Sec Memory Limit: 64 MBSubmit: 1715 Solved: 1043[Submit][Status][Discuss]Description你跳过华尔兹吗？当音乐响起，当你随着旋律滑动舞步，是不是有一种漫步仙境的惬意？众所周知，跳华尔兹时，最重要的是有好的音乐。但是很少有几个
2017-10-11 09:51:27
355
原创 Bzoj - 1443 [JSOI2009]游戏Game [二分图博弈]
1443: [JSOI2009]游戏GameTime Limit: 10 Sec Memory Limit: 162 MBSubmit: 1245 Solved: 575[Submit][Status][Discuss]DescriptionInput输入数据首先输入两个整数N,M，表示了迷宫的边长。 接下来N行，每行M个字符，描述了迷宫。Out
2017-09-22 13:54:53
497
原创 Bzoj 2721 [Violet 5]樱花 [数论]
2721: [Violet 5]樱花Time Limit: 5 Sec Memory Limit: 128 MBSubmit: 648 Solved: 380DescriptionInputOutputSample InputSample OutputHINTSource
2017-09-22 09:51:29
418
原创 POJ - 2096 Collecting Bugs
HomeProblemStatusContestUserGroupForumArticleLogoutSakura_ SubmitFavoriteSubmissionsLeaderboardTime limit10000 msCase time limit2000 m
2017-09-19 17:15:10
528
原创 [洛谷P1550] [USACO08OCT]打井Watering Hole [最小生成树]
题目背景John的农场缺水了！！！题目描述Farmer John has decided to bring water to his N (1 <= N <= 300) pastures which are conveniently numbered 1..N. He may bring water to a pasture either by building a well in
2017-09-19 15:44:23
604
原创 [洛谷P1353] [USACO08JAN]跑步Running [DP]
题目描述The cows are trying to become better athletes, so Bessie is running on a track for exactly N (1 ≤ N ≤ 10,000) minutes. During each minute, she can choose to either run or rest for the whole minu
2017-09-19 15:35:49
455
原创 Bzoj-1131 Sta [DFS]
1131: [POI2008]StaTime Limit: 10 Sec Memory Limit: 162 MBSubmit: 1629 Solved: 611[Submit][Status][Discuss]Description给出一个N个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大Input给出一个数字N,代表有N个点.N
2017-09-18 17:18:37
538
原创 Vijos-2164 神秘的咒语 [LCIS最长公共上升子序列]
描述身为拜月教的高级间谍，你的任务总是逼迫你出生入死。比如这一次，拜月教主就派你跟踪赵灵儿一行，潜入试炼窟底。据说试炼窟底藏着五行法术的最高法术：风神，雷神，雪妖，火神，山神的咒语。为了习得这些法术，要付出艰辛的努力，但是回报同样十分丰厚。拜月希望你告诉他咒语的长度为多少。（你：“请问您想知道咒语的具体内容吗？”拜月：“想，但是vijos不支持special judge。”-_-原来大
2017-09-18 16:29:05
1041
原创 Vijos-1603 迷宫 [矩阵快速幂]
首页题库训练讨论比赛Sakura_ / Vijos / 题库 /迷宫背景还是一道水题描述在某个神秘的星球上有一个游乐园游乐园里有一个奇怪的迷宫，迷宫内有n个点，每个点之间都可能会有一条有向边（可能会有自环
2017-09-18 15:08:41
427
原创 NOIP 2014 解方程 [模运算][哈希？]
#20. 【NOIP2014】解方程 统计 描述 提交 自定义测试已知多项式方程：a0+a1x+a2x2+...+anxn=0a0+a1x+a2x2+...+anxn=0求这个方程在[1,m][1,m]内的整数解（nn和mm均为正整数）。输入格式第一行包含22个整数nn、mm，每两个整数之间用一个空格隔开。接下来的n+1n+1行每行包
2017-09-18 11:15:33
800
原创 NOIP 2014 飞扬的小鸟 [DP]
#20. 【NOIP2014】解方程 统计 描述 提交 自定义测试已知多项式方程：a0+a1x+a2x2+...+anxn=0求这个方程在[1,m]内的整数解（nn和mm均为正整数）。输入格式第一行包含22个整数n、m，每两个整数之间用一个空格隔开。接下来的n+1n+1行每行包含一个整数，依次为a0,a1,a2,...,a
2017-09-18 10:55:57
648
原创 NOIP 2014 联合权值 [DFS]
#16. 【NOIP2014】联合权值 统计无向连通图 GG 有 nn 个点，n−1n−1 条边。点从 11 到 nn 依次编号,编号为 ii 的点的权值为 WiWi，每条边的长度均为 11。图上两点 (u,v)(u,v) 的距离定义为 uu 点到 vv 点的最短距离。对于图 GG上的点对 (u,v)(u,v)，若它们的距离为 22，则它们之间会产生Wv×WuWv×Wu
2017-09-18 10:48:55
624
原创 POJ-3744 Scout YYF I [概率DP][矩阵快速幂]
Scout YYF ITime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 9408 Accepted: 2751DescriptionYYF is a couragous scout. Now he is on a dangerous mission wh
2017-09-18 10:34:43
563
原创 登月计划 [扩展回旋阿姆斯特朗算法]
题目大意： 求 a ^ x mod p = b 恩，普通阿姆斯特朗算法会T，但是这是扩展回旋阿姆斯特朗算法的裸题啊，不说了直接上，打板#include <cstdio>#include <cstring>#include <iostream>#include <cmath>using namespace std;typedef long long dnt;const int N
2017-09-15 22:09:12
467
原创 Bzoj - 1415 聪聪可可 [概率][记忆化搜索]
用f[i][j]表示从聪聪在 i ， 可可在 j 时的期望步数 用to[i][j]表示从聪聪在 i ， 可可在 j 时聪聪的下一步，用Spfa预处理 然后对于每个位置 x -> y tmp 为走两步后的位置 f[x][y] = (f[tmp][y] + f[tmp][v]) / (y点的度数 + 1) （v为所有与y相邻的点）+ 1#include <bits/stdc++.h>#defi
2017-09-14 17:13:20
294
原创 HDU - 3853 Loop [Maho shoujo] [概率DP]
概率题一般要倒推 f[i][j]表示在（i, j）时到（r, c）的期望步数 考虑在位置（i, j） 时 f[i][j] = f[i][j] * p[i][j][1] + f[i][j + 1] * p[i][j][2] + f[i + 1][j] * p[i][j][3] 移项 （f[i][j] - f[i][j] * p[i][j][1]） = f[i][j + 1] * p[i][j][
2017-09-14 17:06:02
296
原创 [Noi2010] D1T3 海拔 (网络流（迷~） 对偶图 + 最短路)
大概意思就是把图分成两部分，中间交界处的边权和要最小。 裸的最小割，但是Dinic要TEL（不知道ISAP会不会） 所以就建对偶图跑最短路#include <bits/stdc++.h>using namespace std;const int N = 505;int n, head[N * N], top, S, E;struct Rod{ int y, nxt, w; R
2017-09-14 11:32:09
510
原创 [Noi2010] D1T2 超级钢琴 (ST表 线段树 主席树)
大概就是对于每个i求一下可行区间里的最大值。 但是有可能次大值也在答案中。 所以每次选取最大值时顺便将次大值也加入堆中。 复杂度O(n log n) #include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <map>#include <queue>#define INF 0
2017-09-14 11:28:39
415
原创 [Noi2010] D1T1 能量采集 (欧拉函数)
由结论可知所求数对于i, j来说为gcd(i, j) 推一下公式 ans = n * m + 2 * sigma(i = 1 i <= n) sigma(j = 1 j <= m) gcd(i, j) 由 n = sigma(d | n) phi(d) 得 （略去n * m 及 2） ans = sigma(i = 1 i <= n) sigma(j = 1 j <= m)
2017-09-14 11:25:14
356
原创 动态规划（DP）优化之斜率优化讲解
“DP的斜率优化——对不必要的状态量进行抛弃，对不优的状态量进行搁置，使得在常数时间内找到最优解成为可能。斜率优化依靠的是数形结合的思想，通过将每个阶段和状态的答案反映在坐标系上寻找解答的单调性，来在一个单调的答案（下标）队列中O（1）得到最优解。”在呈交给教练的总结里，我这样写到。确实，集训了几天，对斜率优化感受颇多，就此写一下自己的理解。斜率优化的思想在2004年国家集训队员周源大神撰写的《浅谈
2017-06-01 16:23:51
5339
2
原创 NOIP 2009 模拟测试总结
NOIP 2009 模拟测试总结前序题目的难易安排挺合适的，第一题Spy和第二题Son都可以简单通过，从第三题开始就有点难度了。第三题Trade就有点难度，代码倒不难，只是模型转换和双向BFS方法难想到（其实第四题DFS也是万万想不到的），还有Tarjan加上拓扑排序的方法有些恶心……第四题靶形数独，貌似只能搜索，只不过有技巧。好了，开始正题。Question1: 潜伏者 Spy非常简单的一道题，
2017-03-10 17:05:27
401
原创 2.24 --- 2.25 动态规划专题小测 及 NOIP 2008 模拟 总结
2.24 — 2.25动态规划专题小测 及NOIP 2008 模拟 总结前序 ： 谈谈感受这两天考下来觉得收获很大，既认识了自己的不足，又为我以后的复习指明了方向。开学以来，学习压力固然是有的，但我却越发得想要回到机房，隐约有种“手痒”的感觉。从小升初后的暑假集训到现在结束了寒假集训重回机房，我已经习惯了，甚至爱上了竞赛生活，就算未来有一天我退役了，我相信这段时光依旧会深深的烙印在我的心上。（好了
2017-02-25 17:11:27
354
原创 2017.2.18 NOIP2010测验
**#2017.2.18 模拟NOIP测验Question 1全国信息学奥林匹克联赛（NOIP2010）复赛提高组1．机器翻译 (translate. pas/c/cpp) 【问题描述】 小晨的电脑上安装了一个机器翻译软件， 他经常用这个软件来翻译英语文章。 这个翻译软件的原理很简单， 它只是从头到尾， 依次将每个英文单词用对应的中文含义来替换。 对于每个英文单词， 软件会先在内存中查找这个
2017-02-19 12:57:22
487
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人