- 博客(208)
- 收藏
- 关注
RSS订阅
原创 机器学习之爱情动作片（k值法）
这里写自定义目录标题前言假设思路开搞代码前言在胡乱看了几本书以后，终于开始进行实战，搜了几个实战例子，终于看到一个适合我的。这次的任务要求很简单，就是区分爱情片和动作片，不过电脑没有人脑那么丰富多彩，人只需要大致看一看就可以分别，但是电脑要给数据让他学习。假设我们需要的数据有只有两个，就是一部电影的打斗动作数量和爱情动作数量，对于动作电影来说，打斗动作明显是多于爱情动作的，反之则相反。用一个二维数组来表示（如图）。思路那我们用什么办法来量化这个标准呢，一个明显的比较算法也可以勉勉强强做出来，但是
2021-10-09 16:04:09
661
原创 hash计算在txt,doc中的细节（电子物证检验）
在txt中任意打入一个字符，保存后计算hash值，然后加上一个空格中再删除一个空格，重新计算hash值，比较hash值大小这是两次的结果输入1然后计算hash值随意一个位置加入一个空格后删除
2021-04-22 21:55:43
886
原创 取证基础之机械硬盘的物理结构揭秘（1）
机械硬盘是一个集机，电，磁于一体的精密设备，因为技术成熟，性能稳定，容量大，价格低等优点，是目前世界最为普及的一种存储介质。同时经过五十多年的发展，他的价格已经从每GB超过1000w美元到达每GB只要0.04美元了。磁盘的外壳及盘表信息如今主要的硬盘品牌有希捷和西部数据主要的尺寸有3.5英寸，2.5英寸和1.8英寸但是不管哪种硬盘都会有一个金属的外壳保护着硬盘内部的重要构造，并且贴上一个盘标，注明硬盘的品牌，型号，容量，产地，序列号等（在取证中需要关注）硬盘的设计是为了保护其内部的灵敏的机械.
2020-11-16 10:00:01
1042
原创 5911. 【NOIP2018模拟10.18】Travel
题目大意：EZ同学家里非常富有，但又极其的谦虚，说话又好听，是个不可多得的人才。EZ常常在假期环游世界，他准备去N（N<=100000）个国家之多，一些国家有航线连接，由于EZ同学有一定的强迫症，任意两个国家之间都能通过航路直接或间接到达，并且这样的路径仅有一种。（简单来说，这些国家构成了一棵树）由于EZ是C国人，因此将C国（1号国家）作为整棵树的根每个国家有一个旅游热度A[i]和影...
2018-10-19 19:01:44
432
原创 5910. 【NOIP2018模拟10.18】DuLiu(瞎搞)
题目大意：具体来说，这N道题每题都有一个毒瘤值，它们构成了一个序列。李Fee心目中有一个理想的毒瘤值序列，这个序列并不一定每一题的毒瘤值都是原本N道题中出现的，所以李Fee准备进行一些改动。这些改动体现在毒瘤值上就是将某道题的毒瘤值改为所有题的毒瘤值的二进制异或值。但是，改动题目是很麻烦的，他想算出最少需要多少次改动才能将原本的毒瘤值序列改成理想的毒瘤值序列，李Fee忙于出毒瘤题，他想请发明O(...
2018-10-19 16:12:55
306
原创 5909. 【NOIP2018模拟10.16】跑商（圆方树+树链剖分+SET）
题目大意：基三的地图可以看做 n 个城市，m 条边的无向图，尊者神高达会从任意一个点出发并在起点购买货物，在旅途中任意一点卖出并最终到达终点，尊者神高达的时间很宝贵，所以他不会重复经过同一个城市，但是为了挣钱，他可能会去绕路。当然，由于工作室泛滥，所以一个城市的货物价格可能会发生改变。但是尊者神高达智商不足，他可能在一个很蠢的节点把货物卖掉，所以尊者神高达想知道每一次跑商最多能赔多少钱。思路：...
2018-10-17 08:11:41
335
原创 5908. 【NOIP2018模拟10.16】开荒（虚树+lca+线段树）
题目大意：师门可以看做以 1 为根的一棵树，师门中的每一个人都有一定的装备分数。一共会有 q 个事件。每个事件可能是一次开荒，也可能是因为开荒出了好装备而导致一个人的装分出现了变化。对于一次开荒，会有 k 个人组织，由于师门的号召力很强，所以所有在组织者中任意两个人简单路径上的人都会参加。思路：我们可以设一个dis[i]dis[i]dis[i]表示每个点到根节点的权值和，然后我们发现修改是修...
2018-10-17 08:03:25
365
原创 5907. 【NOIP2018模拟10.16】轻功（）
题目大意：一共有 n 个木桩，要求从起点（0）开始，经过所有梅花桩，恰好到达终点 n,尊者神高达一共会 k 种门派的轻功，不同门派的轻功经过的梅花桩数不同，花费时间也不同。但是尊者神高达一次只能使用一种轻功，当他使用别的门派的轻功时，需要花费 W 秒切换（开始时可以是任意门派,不需要更换时间）。由于尊者神高达手残，所以经过某些梅花桩（包括起点和终点）时他不能使用一些门派的轻功。尊者神高达想知道他...
2018-10-17 07:45:42
284
原创 5906. 【NOIP2018模拟10.15】传送门（树形dp）
题目大意：8102年，Normalgod在GLaDOS的帮助下，研制出了传送枪。但GLaDOS想把传送枪据为己有，于是把Normalgod扔进了一间实验室。这间实验室是一棵有n个节点的树。现在Normalgod在一号节点，出口也在一号节点，但为了打开它，必须经过每一个节点按下每个节点的开关，出口才能打开。GLaDOS为了杀死Normalgod，开始在实验室里释放毒气，因此Normalgod必须尽...
2018-10-15 22:25:37
280
原创 5905. 【NOIP2018模拟10.15】黑暗之魂(darksoul)(tarjan缩点+环前缀和+单调队列)
题目大意：oi_juruo热爱一款名叫黑暗之魂的游戏。在这个游戏中玩家要操纵一名有 点生命值的无火的余灰在一张地图中探险。地图中有n个篝火（也就是存档点）。在篝火处休息可以将生命值恢复满。每个篝火都会向其他篝火的其中之一连有一条通道（显然，通道是双向的），这些篝火之间都相互可达。也就是说，这是一张n个点，n条边的无向连通图。每条通道里都有一些怪物，经过oi_juruo的分析，他得到了每条边的怪物...
2018-10-15 22:07:28
269
原创 5904. 【NOIP2018模拟10.15】刺客信条（AC）
题目大意：故事发生在1486 年的意大利，Ezio 原本只是一个文艺复兴时期的贵族，后来因为家族成员受到圣殿骑士的杀害，决心成为一名刺客。最终，凭借着他的努力和出众的天赋，成为了杰出的刺客大师。刺客组织在他的带领下，为被剥削的平民声张正义，赶跑了原本统治意大利的圣殿骑士首领-教皇亚历山大六世。在他的一生中，经历了无数次惊心动魄、扣人心弦的探险和刺杀。这次的故事就是他暗杀一位作恶多端的红衣主教。...
2018-10-15 21:52:13
275
原创 P2575 高手过招(博弈)
题目大意：有一个n*20的棋盘，上面有若干棋子对于一个棋子，能将它向右移动一格，如果右边有棋子，则向右跳到第一个空格，如果右边没有空格，则不能移动这个棋子，如果所有棋子都不能移动，那么将输掉这场比赛思路：我们考虑sg函数，显然最后一个状态下，右边全是一是必赢的，然后我们暴力搜出所有sg函数的，这样就可以o（1）判断了。程序：#include<cstdio>#include...
2018-10-12 14:13:35
226
原创 poj 2054 Color a Tree(贪心)
题目大意：给你一棵树，你要给这棵树染色，染色的代价为时间乘上接点的代价。还有一个要求是这个节点被染色一定要父亲也被染色。思路：显然我们第一个染根节点，只有一条链也很简单。但是如果有很多儿子要选择哪一个呢。仔细思考我们发现染色可以想成是一个合并过程。我们设now[i]为合并到i的所有结点费用的平均值，cnt[i]为节点i合并的节点数。每次染色后染色费用更新，这样合并n-1就好了，顺序就选出来了...
2018-10-12 14:09:07
176
原创 UVA378 Intersecting Lines(计算几何)
题目大意：给你了两条线段，要你求他们是平行还是重合还是有交点，如果有交点就输出交点。思路：我们只需要一次跨立实验就可以判断两条线段是否重合，如果有向面积为0说明平行，如果两次叉积都为0说明重合，现在只需要讨论如何求交点了。求交点：略略略…（直接看程序）程序：#include<cstdio>#include<cstdlib>#include<algori...
2018-10-09 22:25:21
476
原创 UVA10902 Pick-up Sticks
题目大意：在一个坐标轴上抛棍子，问你哪些棍子上面没有被别的棍子覆盖过，输出个数和哪些棍子。思路：这是一道线段求相交的题目，用斜率显然可以做，但是好像讨论的要比较多…我们可以用向量来做，用A线段两个端点分别与B线段做两次跨立实验，如果叉积都为0说明线段重合，符号不同说明相交，符号相同说明不相交。程序：#include<cstdio>#include<cmath>...
2018-10-09 22:13:52
168
原创 UVA190 Circle Through Three Points（计算几何）
题目大意：给你三个不共线的点，求过三点圆的方程。写出一般式和标准式。思路：这题要求我们求出过给定三个点的圆的两个方程，一个是标准式，一个是一般式。 标准式：(x-h)2+(y-k)2=r^2 一般式：x2+y2+cx+dy-e=0; 学过三角形的同学都能知道，三角形的外心过三角形三点，所以圆心就是三角形外心，然后半径为一个点到圆心的距离。这样标准式答案就出来了。(h,k)是圆心坐标，r是半径...
2018-10-09 22:05:56
355
原创 U41568 Agent1（瞎搞+组合数）
题目大意：有n个互不相同的整数，分成A,B两组满足下面的关系A队中能力最大的Agent的能力值要小于BB队能力最弱的Agent的能力值。A,BA,B两队都要有人参战。思路：我们考虑枚举一个i一定是A队的，那么左边可以任意选就是2(i-1)，右边除了全空都可以选2(n-i)-1，然后相乘为2n-1-2i-1,后面的是个等比数列，直接等比数列求和就好了，前面的是一个常数列随便搞搞。程序：...
2018-10-09 21:16:26
177
原创 U41570 War1（网络流）
题目大意：ENLIGHTENED总部有NN个Portal，编号为11~NN，编号为ii的Portal初始能量值为A[i]A[i]，在Portal之间有MM条LINK，每条LINK着连接着两个不同Portal，被连接着的两个Portal可以相互传输能量，每个Portal最多总共只能向其连接着的Portal传输A[i]A[i]点能量，现在ENLIGHTENED行动指挥想让每第ii个Portal的能量...
2018-10-09 21:09:44
158
原创 P1070 道路游戏（）
题目大意：小新正在玩一个简单的电脑游戏。游戏中有一条环形马路，马路上有 n n个机器人工厂，两个相邻机器人工厂之间由一小段马路连接。小新以某个机器人工厂为起点，按顺时针顺序依次将这 n n个机器人工厂编号为1-n1−n，因为马路是环形的，所以第 nn 个机器人工厂和第 1 1个机器人工厂是由一段马路连接在一起的。小新将连接机器人工厂的这 n 段马路也编号为 1-n1−n，并规定第 i i段马路...
2018-10-08 20:42:25
386
原创 P1290 欧几里德的游戏
题目大意：欧几里德的两个后代Stan和Ollie正在玩一种数字游戏，这个游戏是他们的祖先欧几里德发明的。给定两个正整数M和N，从Stan开始，从其中较大的一个数，减去较小的数的正整数倍，当然，得到的数不能小于0。然后是Ollie，对刚才得到的数，和M，N中较小的那个数，再进行同样的操作……直到一个人得到了0，他就取得了胜利。下面是他们用(25，7)两个数游戏的过程：Start：25 7Sta...
2018-10-08 20:28:16
794
原创 5899. 【NOIP2018模拟10.6】资源运输(矩阵树定理)
题目大意：要你求一张图的生成树的边权乘积期望。思路：这题是一个矩阵树和变元矩阵树定理的应用题，矩阵树可以求出来生成树的数量，变元后的矩阵树可以求出所有生成树乘积和，然后除一下就好了。矩阵树写法如下：先定义两个矩阵，一个是度数矩阵，一个是连接矩阵，用度数矩阵剪掉连接矩阵，然后去掉一行一列，然后高斯消元，把对角线所有数乘起来就好了。程序:#include<cstdio>#i...
2018-10-08 19:46:59
167
原创 5895. 【NOIP2018模拟10.5】旅游
题目大意：思路：这题目比较特殊点在于他的边权是2^i，比赛的时候傻，没有想到有什么用，后来看到题解，如果构出一颗最小生成树，那么最短路一定在最小生成树上面，这样子就变成了一棵树上在原图中的奇点要配对，因为树上的一些奇怪性质，我们可以之间贪心得出答案，最后答案就是所有边权加上最小生成树上面贪心的结果。程序：#include<cstdio>#include<cstdlib...
2018-10-06 14:42:37
244
原创 2242: [SDOI2011]计算器(数论)
题目大意：给你三个操作1:求a^b=x(%p)2:求a*b=x(%p)3:求a^x=b(%p)思路：这是数论里面比较好的题了，第一问快速幂，第二问扩展gcd，第三问BSGS。第三问a^x=b(%p),因为过p个肯定有一个循环节,飞马小定理可得，那么我们把x分成根号p块，设为a ^(i*m)a ^j=b(%p)，移项可得aj=b∗ine(ai∗m)a^j=b*ine(a^{i*m})a...
2018-09-27 16:23:47
162
原创 5884. 【NOIP2018模拟A组9.25】蒲公英的约定（瞎搞）
题目大意：Step 1：首先把 c 和 lastans 按位异或得到 b，最开始 lastans 是 0Step 2：如果这天的 b 等于 0，则说明他们已经长出了所有要长出的种子，哥哥与弟弟的交 流结束(输入文件也到此结束)Step 3：如果这天的 b 不等于 0，弟弟会求出一个最小的非负整数 x 使得 (即a^x同余于b模p)，[题目保证可以找到这样的 x]Step 4：lastans...
2018-09-27 11:46:31
182
原创 5883. 【NOIP2018模拟A组9.25】到不了（启发式合并）
题目大意：维护一个森林，支持连边操作和查询两点 LCA 操作思路：启发式合并，每次把小的树连接到大的树上面就好了，暴力重构lca数组，维护个根，就可以快速得出lca了还可以离线lct，这个我不是很懂…晚上可以问问dalao们程序：#include&lt;cstdio&gt;#include&lt;iostream&gt;#include&lt;algorithm&gt;#def
2018-09-27 11:38:41
246
原创 5882. 【NOIP2018模拟A组9.25】雪人(线段树)
题目大意：给定一个长度为 N 的序列，每次操作可以选选择一个数，这个数和它右边的数比大小，如 果这个数比较大，就和右边的数交换，然后和右边的数接着比大小直到某一次它右边的数比 他大或者他右边没有数了。求最小的操作次数使得序列变为升序。思路：因为交换是不会改变相对顺序的，所以从左往右找，找到一个数右边有比他大的就要答案加一。程序：#include<cstdio>#includ...
2018-09-27 11:35:28
238
原创 P4889 kls与flag
题目大意：有nn个OI选手，每个人插了一个flag。有一天因为某种原因，flag都被触发了，所以地上有一排nn根竹竿，竹竿的间距均为一个单位长度，高度在1\sim m1∼m之间。kls看到这些竹竿，感觉不好看，于是准备把它们全部放倒。在这之前，kls想到了一个数学问题。每根竹竿可以往左倒或者往右倒。如果两根竹竿在选择方向放倒之后，它们的顶端可以重合，那么称它们是优秀的。现在kls想要知道，有...
2018-09-25 20:48:14
275
原创 bzoj 3626: [LNOI2014]LCA 树链剖分
题目大意：给你一颗树，然后每次询问l,r,z表示从l~r所有的点和z点的lca的深度和。思路：这题贼有意思，发现自己根本想不出来！只好%%%biao暴力求解很慢，觉得如果是比赛最多60分，那我们要怎么思考这题呢，我们先把z点到根的路径全部赋值为1，然后枚举l到r，正好他们到根的点和就是lca的深度和，这样就解决了一个询问的和小数据的答案，接下来我们发现，这个东西是有累加性的，如果你把l~r...
2018-09-25 19:30:12
156
原创 noiac！B. delete
题目大意：长度为nn的序列AA，从中删去恰好kk个元素（右边的元素往左边移动），记cntcnt为新序列中Ai=iAi=i的元素个数（即权值与下标相同的元素的个数）。求cntcnt的最大值。思路：一开始肯定是想到dp，f[i][j]为前i个删了j个的最大值，显然状态不怎么好转移，那就设改改想法，设f[i][j]为前i个取了j个。然后得出dp方程j==a[i]的时候加一，不然就是背包问题选或者不...
2018-09-22 19:22:18
404
原创 noiAC！A. count
题目大意：长度为n+1的序列A，其中的每个数都是不大于n的正整数，且n以内每个正整数至少出现一次。对于每一个正整数k=1,…,n+1，求出的本质不同的长度为k的子序列(不一定要连续)的数量。对109+7取模。思路：这题思路还是很好想的，先算出n+1个数的子序列数量，然后剪掉重复的数量就好了，重复的数量很好算，就只和两个相同的字符的位置有关，然后就AC了。程序：#include<c...
2018-09-22 19:07:54
506
原创 牛客 188E
题目大意：小w是欧拉的粉丝众所周知现在小w想求这个东西有m次询问，每次询问F(n)对998244353取mod思路：每一个项分类讨论，线性筛出mu，然后预处理d^k，枚举一个d然后就好了程序：#include<cstdio>#include<cstdlib>#include<iostream>#define LL long long#...
2018-09-21 21:50:59
148
原创 5872. 小A的任务
程序：思路：把给出的式子拆开来，然后分类讨论一下就好了。程序：#include<cstdio>#include<iostream>#include<algorithm>#include<cmath>#include<cstring>#define LL long long#define N 10000005con...
2018-09-20 18:54:30
250
原创 5873. 小p的属性
题目大意：思路：把问题转化一下，就是在一个二维的平面上，有些点有权值，你每次都可以向右或者向上走，经过一个点后得到他的权值，并且每走一步都会再次加上他的权值，问你走k步的最大权值是多少，k=10e9。我们发现他每次走都会走到某个点上，这样答案才会更优，所以我们把所有点的横坐标纵坐标拿出来离散，然后插入点值，这样就可以不用枚举坐标了。先预处理前缀和！程序：#include<cstd...
2018-09-20 18:50:18
256
原创 poj Musical Theme(后缀数组)
前言：jz大佬说初二不会后缀数组就退役吧，然后我看了看高二的自己竟然苟过了三年…哈哈哈哈哈哈题目大意：求一个最长重复不相交的字符串，长度必须大于5思路：因为原题比较长，也没有上面说的那么裸，所以我们先用每个数剪掉前面一个数，然后就转化成上面那样了，然后用后缀数据求出来就好了。具体后缀数组应用：我们先分析一个判定性问题，如何判断两个字符串是相同且不重叠的。解决这个问题要用到里面的he...
2018-09-17 21:07:00
200
原创 P1306 斐波那契公约数(矩阵快速幂)
题目大意：对于Fibonacci数列：1,1,2,3,5,8,13……大家应该很熟悉吧~~~但是现在有一个很“简单”问题：第n项和第m项的最大公约数是多少？思路：这题有点好玩，首先他是一个结论题，知道结论很好做不知道结论就推一推把，思考一段时间可以发现gcd(f[n],f[m])==f[gcd(n,m)];然后矩阵快速幂求答案就好了。这里主要是结论的证明和如何想到。想到还是比较简单的，...
2018-09-10 11:58:34
243
原创 5862. 【NOIP2018提高组模拟9.9】孤独(容斥)
题目大意：思路：这题十分的有意思，考虑经典容斥，答案=选择第一个话题能交流的人数的k次方+选择第二个话题交流的人数的k次方+….-选择一二两个话题都能交流的人数的 k 次方+… 复杂度为m*2^n。发现我们每次转移m的复杂度太高了，我们考虑去怎么优化他的转移，观察可得这是个子集问题，设一个dp[i]，为i子集的方案数，就等于他所有的父亲加起来。这样子优化到了o（n*2^n）程...
2018-09-09 21:37:26
410
原创 5861. 【NOIP2018提高组模拟9.9】失意
题目大意：思路：这题是一个贪心堆优化的题目，思路还是挺好想的，前几天做过一个类似的区间问题，答案就是这些数最小的右节点，减去最大的左节点。然后用排序左节点，用堆维护右节点，然后限制数量，每次弹出元素的时候求值。程序：#include<cstdio>#include<iostream>#include<cstring>#inclu...
2018-09-09 21:28:59
343
原创 5860. 【NOIP2018提高组模拟9.9】荒诞
题目大意：思路：这是一道分析题目的程序，读懂了题目就可以发现是求出1~i所有数的平方和，证明很简单。程序：#include<cstdio>#include<iostream>#include<algorithm>#include<cstring>#define LL long long#define mo 100...
2018-09-09 21:22:46
299
原创 5858. 朝圣 (ntt)
题目大意：朝圣刚回来，国王就准备举办盛大的宴会，由于你很闲，所以你来帮国王筹备宴会。 现在需要为宴会准备水果，由于你国物质匮乏，所以全国一共只有 n 个苹果，m 个梨。 由于国王具有 “精神错乱” 的特质，所以他将会从这 n + m 个水果中随机拿出 k 个，用于这次宴会。 你听说领主们都有一个癖好，如果宴会中的苹果的数量是一个质数，那么他们就会很 高兴。但是因为国王是随机选的水果，所以...
2018-09-08 14:42:20
303
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人