隆1-CSDN博客

原创 Visio 安装暴雷记录

office2016家庭学生版中，安装visio2021后，插入word的vsdx图形右键显示unkown类型，无法识别，给学习工作带来很多麻烦！尝试安装Visio许多版本，遇到很多bug，最终安装Visio 专业版 2019解决问题！

2022-11-26 14:49:13 3489 1

原创最近点对算法

最近点对算法问题描述二维平面上n个点，求最近的两点距离？如例： P1 (1，0)、P2 (2，4)、P3 (3，4) P4 (3，5)、P5 (3，1)、P6 (5，6) P7 (6，3)、P8 (7，1)、P9 (7，2）最短距离点对有3对，(P2,P3)、(P3,P4)、(P8,P9),最短距离为1.方法一：蛮力法两遍循环，枚举任意两点P[i...

2019-04-24 10:41:11 1012

原创状态压缩DP

先来了解状态压缩：大多数人应该做过了洛谷P1433，这里就不用这个例子了，介绍个新例子了解下状态表示：捷凡P116看到m≤20的字迹，就要有意识：能不能压缩状态，明显将边压缩成状态.每个边的编号i即为生成树2进制状态第i位，为1，即生成树包含这条边。样例图：其中一棵生成树：二进制枚举所有的生成树状态，枚举原则：一颗树，n-1条边，首先保证n-1条...

2018-11-21 08:40:21 210

原创树专题---连通域问题

树专题—连通域问题在acm竞赛树型问题中，经常会遇到与连通域相关问题。将树拆成m个连通块的方案数或者统计包含节点i的连通域的数目。在此，我们对此类问题进行总结。类型一：拆成m个互斥连通域题目：牛客国庆集训派对Day3 题意：树拆成m个互斥且不为空的连通域，拆有时间次序，问拆的不同方案总数。分析：如果没有什么经验，这道题一时半会还真想不到什么办法解决。当...

2018-10-03 22:38:03 455

原创 Codeforces Round #510 (Div. 2) E---谈处理数差平方和问题的套路技巧

CF 510(Div.2) E、Vasya and Magic Matrix题意： n*m的矩阵中，每个格子有一个整数a[i][j]，人能从格子(xi,yi) 走到格子(xj,yj),当且仅当a[xi][yi] >a[xj][yj]) ,其花费为距离的平方，如果有多个能走的点，等概率选择其中某个点，仅当没有格子能走了，才停止。问人在格子(r , c)，将要花费额的期望(P/Q)%(...

2018-09-19 20:11:21 248

原创矩阵快速幂处理一类线性递推组问题

最近两场比赛，都涉及到此类问题！以前没注意过这种问题，都在状态转移方程推出后，止步于n太大！事后总结，线性递推可以用矩阵来表示，进而快速幂解决n太大的问题！例1：牛客小白月赛7 J 方格填色题意：n×m矩阵填黑白两色，行相同相邻两个不能同为白色，相邻两列不全为黑色 (n≤5，m≤1e18),问填色的方案数mod 1e9+7的值.令黑色为1，白色为0，即每一列...

2018-09-16 17:52:48 491 4

原创 KEIL4 的操作技巧

1、不小心删除了Project-Window(左栏项目窗口) (1) 左边项目栏存在(2) 不小心删去了左侧项目栏(3) Menu中找到View->单击Project Windows选项(4) 重现...

2018-09-13 17:04:21 4692 1

原创斐波拉契数列前n项和的求法

一、递推关系构建系数矩阵–矩阵快速幂⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪S[n]=S[n−1]+fac[n]fac[n+1]=fac[n]+fac[n−1]fac[n]=fac[n]{S[n]=S[n−1]+fac[n]fac[n+1]=fac[n]+fac[n−1]fac[n]=fac[n]\begin{cases} S[n] = S[n-1] + fac[n] \\ ...

2018-09-13 13:52:53 3244

原创回文树的应用

回文树的应用听说，这个算法能将一些难处理的字符串题目变成裸题，菜菜学学！没想到18南京网络赛碰到了，居然想不起来了，可恶！计蒜客 30998 题目：问字符串(‘0’~’9’)里面不同本质的数字字符串代表的数字之和模(1e9+7). 回文树裸题，设置en[i]数组，来记录节点代表回文串的末尾在字符串中的id，代表的数字取模我们可以用前缀和来实现： 444...

2018-09-05 08:45:02 353

原创树上倍增的应用

树上倍增的应用归根到底，树上倍增的应用就是求LCARMQ + 树上深搜int fa[N][20];int toUsed = 1;struct node{ int to; int nxt;}p[N*2];void mkedge(int u,int v){ p[toUsed].to = v; p[toUsed].nxt = head[u]; ...

2018-08-31 20:15:01 1151

原创牛客练习赛25 a-贝利福斯数(素数筛法的应用)

题目链接题意：定义ax+1 为新的数，如果ax+1 不能分解成两个ay+1之积，那么称为素数！求[1,n] 里的能分解成两个ax+1素数之积的数的个数。很毒奶的题目！首先数据非常大！而且有坑点！先说说性质吧！ (ax + 1) * (ay + 1) = a[ axy + x + y ] + 1 仍然为一...

2018-08-26 13:53:37 223

原创扩展KMP的应用

FZU-1901 题意：字符串S，问满足S[i] = S[i+P],（i ∈[0,Size -P-1]）,升序顺序输出P的取值。很裸的ex_kmp的定义题！判断Next[j] == Size - j +1 ，以S[j]开头后缀子串是S的一个前缀子串。 /***********************************...

2018-08-26 13:32:58 620

原创 hunnu oj 11564 Easy Delete (二分图最小顶点覆盖)

题目链接题意：二维平面n个点，值0或1，拥有erase一行or一列的能力，但0点不能被删去，问erase的最少次数？(n最多1000) 在不搞二分图等图论专题，就凉了！比赛时，推导到最小顶点覆盖数，但不明白最小顶点覆盖数 == 二分图最大匹配数。心真的好痛！贴个模型： 1 -1 1 删...

2018-08-19 11:21:49 262

原创 2018 上海大都会赛 H、A Simple Problem with Integers(带暴力成分的线段树)

题目链接题意：对数组进行两个操作: 1、C L R 修改区间[L,R]上每个值为本身的平方，取mod 2018 2、Q L R 查询区间[L,R]的数值和说说感受吧！这道题，我暴力打表，在2018内的数分为两种：一种自幂的所有数中初始段不会出现第两次，后面会形成环；另外一种是初始就在循环内；另外我猜想了所有循环...

2018-08-08 10:58:16 387

原创 18杭电多校(hdu 6351) Beautiful Now （置换群 + dfs暴搜+剪枝）

题目链接一个范围在1~1e9的数字，问做k次两数位互相交换数值(可自己与自己交换)，不能有前导0，问最小值和最大值。先说说自己心里的感受，比赛时想到枚举所有的排列，然后每个排列逐一比较交换次数，选择交换次数不大于k的最大值和最小值。可是突然脑袋卡了，想不起置换群的操作了，突然想起排序后贪心，陷入5h的贪心……，太难理清逻辑了，比赛结束后，又是2h...

2018-08-07 10:59:14 284

原创 2018 上海大都会赛 J、Beautiful Numbers(数位dp)

题目链接题意：问[1,N]里多少个数能够被其数位数字之和整除。(N<=1e12) 扯到数位，求区间满足此特征数字的个数，典型数位dp！我们统计12位数字全为9，也就是这些数的数位和有大小约束，不超过108. 所以这里我们的dp[i][sum][num][mod] 记录的是前12-i为数位的代表的10进制值%mod为sum...

2018-08-06 00:47:06 398

原创 Wannafly挑战赛21 C、大水题 (DP)

题目链接题意：一个数组，元素有两个特征值： id 和 val，问可将左右端点id相同的一段数(不能为1个)截下，可截多段，问截取的总和val可以取得的最大值。先讲讲我的解题思路：由于题目是截取一段数，很容易联想到区间dp，例：2……2……2……2 ，这里从第一个2出发，可以不截取，可以选择截取的终点是第2、3、4……个点2，选择的多样性，必然...

2018-08-06 00:26:08 183

原创牛客网暑期ACM多校训练营（第六场）I-Team Rocket(树状数组处理区间最大值)

题目链接题目：n个区间[l,r],m个操作：给数b，删去包含点b^res的区间，记录每个区间i第几次操作时被删去，每次操作删去的区间数。 res是上次删除的区间编号的乘积%998244353，如果上次未删区间，即res为0。遇到题目，想了好久才整理出题目本质！首先我们按左端点从l小到大的顺序排序，实际上是个离散化过程！ ...

2018-08-05 16:12:23 205

原创可持续化Tried的应用1：18湖北省赛(I. Five Day Couple)

题意：数组a[1……n], 给m个区间询问：问a[l……r]中一个数异或b的最大值。数值范围1~1e9。遇到’在一组数中找一个数与数b的异或值最大’这类问题，一般都是将数组建01字典树，因为高位与b对应的数位互异，则异或值大于所有低位之和，这是最优策略：保证高位为1.这道题因为限定了数组的区间，我们需要将思路转化到‘前缀和’上，当前位上与b对应的数位...

2018-08-05 09:36:18 155

原创 Wannafly挑战赛9 C、列一列 (多重hash查询)

题目链接题目大意：给斐波拉契数列的一项值Ak，问k值(1&amp;lt;=k&amp;lt;=100000)因为斐波拉契后面的项都已经是大数范畴，所以我们很难记录实际值！我们选择用5个质数取模，得到的5个余数，表示这项值！暴力打表，证实可以抗碰撞（没有两个项的余数数组一模一样）！时间复杂度为O（T*5*n）！常用hash质数：https://blog.csdn.ne...

2018-07-28 10:27:47 118

原创 wannafly 15 C、小球碰撞 (欧拉+快速幂求逆元)

题目链接：https://www.nowcoder.com/acm/contest/113/C题意：小球的初位置x可以在[L,R]上任意一点,他会弹跳掉到点（2i-1）x,问掉到[L,R]里的次数的期望值%998244353的值.预处理F[t]有点难，我们需要求出5e6个数的逆元（快速矩阵幂logMod），会超时！我们先将ji[t]（所有奇数的阶乘求出（表示(2t-1)!）)...

2018-05-26 11:45:54 2284

原创 Wannafly挑战赛14 C、可达性 (tanjar 缩点 )

题目链接：https://www.nowcoder.com/acm/contest/81/C题目：给n点、m条边（无自环、重边），取出最少点能跑到所有点，输出点数和升序输出这些点（如果有多种情况，输出字典序最小的点集）tarjan 缩点裸题！ 1、修改模板两点即可！添加u的回边连接点v已经不在栈里，即v已经属于一个确定的强连通分量 flag[v],这个分量即可删去，因为能通过其它点跑...

2018-05-04 13:56:06 115

原创 2018年湘潭大学程序设计竞赛 D、Fibonacci进制 (思维题）

题目链接：https://www.nowcoder.com/acm/contest/105/D题目：意思是将x表示成第i位的位权为Fibonacci[i]的01字符串，在将01字符串表示的 2进制数转化的10进制数输出(有多种表示，输出最小的）。思路：找到最低的最高位，一步步缩减x，直到x为0！ 1、前i-1位全为1表示的数<=x&...

2018-05-04 13:15:50 174

原创 HUNNU oj 11757 Brackets (括号dp)

题目链接：http://acm.hunnu.edu.cn/online/?action=problem&type=show&id=11757题意：给偶数长的由‘(’、‘）’组成的字符串s，问是否为合法括号序列或进行一段连续序列翻转（‘(’->‘）’、‘)’->‘(’）是否为合法序列。(len(s)<=5000)·这是博主大一暑假省赛的热身赛...

2018-04-25 00:38:57 193

原创 EOJ Monthly 2017.12 不见了的人口数据 (Hard)

题目链接题意：一棵树树上节点都有一个值ai,都条边的长度为1，现在知道每个节点的代价值为 all 节点t与它的距离即t节点的值积的和pi，问所有的ai的值.（0<=ai<=1000，n<=250000）p[i]=∑j=1ndist(i,j)×aj,dist（i，j）表示节点i与节点j之间最近距离.p[i]=∑j=1ndist(i,j)×aj,dist（i...

2018-04-16 15:18:53 140

原创牛客网练习赛15 C、吉姆的奇思妙想（数学单调性 + 二分法）

题目链接题意：给你正整数a、b，求出s取某个整数时，Ei的最小值。（各参数的范围相当复杂）Ei=ai×∑1≤j≤L,degj≤s(deg2j×freqj)+bi×∑1≤j≤L,degj>s(M×freqj)=∑1≤j≤L,degj≤s(ai×deg2j×freqj−bi×M×freqj)+bi×M×∑1≤j≤Lfreqj=∑1≤j≤L,degj≤s(ai×deg2j...

2018-04-14 12:45:31 222 1

原创 2018 湖南多校（2）----CSU 2030 World Cup Draw （阅读理解题 + 蛮力DFS）

题目链接题意：这题意很折腾人！（针对我这种code差还英文差的人！）一共有32支队各自都有自己上季度的排名和自己属于的联盟；4个Seeding Pot （储存罐），由顶向底各有八个队名；从Pot1按顺序倒空所有Pot(罐子倒空，是从顶到底倒顺序倒得）；倒出的每个队分入到8组中去（A—H组）。 i) 同Pot队伍不能放入到相同的组去；（Pot里的队伍每个组放1个） ii)...

2018-04-13 19:00:29 17497

原创 hdu 3949 Xor ( 线性基解第k小子集异或和）

题目链接题意： T组测试，每次测试给n个long long 型数字，做Q次询问第k小的子集异或和值。线性基的异或和是无法进位，A[i] > all{ 0……i-1的所有线性基的异或组合}，实际相当于二进制，求第k最小，实际求k的二进制表达中为1的项位置. (第i位不为0即对应于线性基中第i位不为0的基在要选的组合中。必须注意的是：线性基无法凑成子集异或和为0的情况。所...

2018-04-12 15:56:29 607

原创 hdu 5544 Ba Gua Zhen (线性基 + 图的DFS遍历求环）

题目链接题意：题目说的很抽象，需要提炼：先将图中所有环的异或和求出为val，再从中取出若干val（不同环的），求最大的异或和。（保证是连通图）1、求环的异或和值，用图的DFS遍历来搜索出结果；需要辅助数组vis[i], vis[u]==0标注节点u已经遍历完成，vis==1标注已经遍历，但未完全，仍在遍历其后代，显然我们遍历到当前v与u连边 (vis[...

2018-04-12 01:12:28 202

原创 hdu 2059 龟兔赛跑（简单DP）

题目链接题意：题目很有趣，也没有刁难的地方！按由近至远给出了充电站到起点的距离（0<dist[1]<dist[2]…<dist[n]<L），和兔子的速度vr，乌龟的自行车充电的速度vt1、没有充电的速度vt2，自行车充电后最远行驶距离C，充电花费的时间time，问乌龟采取最优的策略，兔子赢了，输出“Good job,rabbit!”，输了，输出“What a...

2018-04-11 14:05:40 210

原创 2018 湖南多校（2）----CSU 2037 Mars (后缀自动机 + DFS）

题目链接：http://acm.csu.edu.cn/csuoj/problemset/problem?pid=2037由于博主水平有限，无法解出这道题！查阅了国科大大佬alpc_qleonardo的博文，感觉写的非常好，顿时思路变清晰，感觉对后缀自动机了解了一点，所以这篇文章只是对大佬文章的带有个人的理解的译文！题意：给你一个长度不超过10000的01字符串，不超过1000次查询...

2018-04-11 12:38:09 298

原创 2017沈阳网络赛 number number number

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6198题意：斐波拉契数列f[0]=0、f[1]=1,f[n]=f[n-1]+f[n-2]（n>=2）,求不能用k个斐波拉契数之和表示的最小数。flag：找规律***规律是：f[2*k+2]-1推荐看 RBS <<根据递推公式构造系数矩阵用于快速幂>>时间复杂度： O(...

2018-04-06 08:19:01 143

原创 2018年东北农业大学春季校赛 K、wyh的数列

题目链接：https://www.nowcoder.com/acm/contest/93/K题意：斐波拉契数列f[0]=0、f[1]=1 , f[n]=f[n-1]+f[n-2]（n>=2）;求f[a^b]%c.（a、b<=2^64、2<=c<=1000）***因为a、b可等于2^64，则类型应该为 unsigned long long ；***c值非常小，我们可以暴力...

2018-04-05 23:20:33 144

原创 2018湖南多校第一场 F、Fleecing the Raffle

题目链接：http://acm.csu.edu.cn/csuoj/problemset/problem?pid=2019题意：其它n个人放写自己的字条进盒子里，你玩老千，放x张写你自己的字条进盒子，庄家依次抽p张纸条为中奖户（不放回），必须抽中你且不被发现（即只能抽中一张你的名字），问你放x后，得到你中奖且不被发现的最大概率。flag：数学这题真的坑爹！用纯数学推导真...

2018-04-05 21:46:59 207

题目链接：https://www.nowcoder.com/acm/contest/93/I 题意： n件物品，都有各自的val、weight，问挑选k件物品的单位重量的价值最大；flag：0-1整数规划问题推荐看：https://blog.csdn.net/hzoi_ztx/article/details/54898323最开始二分区间为[ 0 , max { val[i]/weight[...

2018-04-05 20:05:32 224 1

原创第13届广东工业大学ACM程序设计大赛 H、哲哲的疑惑

题目链接：https://www.nowcoder.com/acm/contest/90/Hflag：组合数学题意：问给n种颜色，有l个不同球，对每种方案，如果有k种颜色没有用到，即产生不满意值为C（k，m），总不满意值为多少？*** 按照题目来，枚举所有涂色剩下颜色的数目k，即求出其方案数（满射公式），再乘上不满意值，结果太难合并了！我想了两天，崩溃了！完全无法合并成简洁公...

2018-04-05 00:27:16 175

原创 CSU 2020 Card Hand Sorting

题目链接：http://acm.csu.edu.cn/csuoj/problemset/problem?pid=2020湖南多校第一场C题题意：给出n张扑克牌，问只需要调动多少张牌使得牌相同类型的牌相邻、牌值升序或降序。flag：最长上升子序列*** 这个问题是非常繁琐的，比赛时一直都往贪心方面想！我们执着于找到一种最优排序结果，但是其实反过来想总共才多少种结果（满足题意的最终排序）...

2018-04-02 20:02:25 387

原创第十四届浙江财经大学程序设计竞赛 B、Bazinga

题目链接：https://www.nowcoder.com/acm/contest/89/B题目：求区间[L,R]内所有与K互质的数之积取模K；(1<= L,R<=1e18，1<=K<=1e5)，最多20组测试数据；flag：数论**长度区间为K的里面的数取模K后，余数集合均一样,为{0,1,2,3,4,5,6……K-1}；例： K=6， [1,6]求模6的余数集合=...

2018-03-25 09:03:15 449 1

转载分布式和集中式的版本控制的区别！

Chapter: 开始了解Git1. 先谈谈版本控制的一些事2. Git诞生背后的一些故事3. 版本控制：集中式VS分布式4. Git的思想和基本工作原理5. Git在Windows下的安装前面提到，Linus一直痛恨CVS及SVN这些集中式的版本控制系统，为什么呢？Git是分布式版本控制系统，那么集中式和分布式版本控制系统又有什么区别呢？先说集中式版本控制系统，版本库是集中存放在中央服务器的，而...

2018-03-20 00:44:16 2111

原创 Wannafly挑战赛9 A、找一找

题目链接：https://www.nowcoder.com/acm/contest/71/A暴力题，但有技巧做出O(nlogn)!***对任何i∈[1,1e6]，依次枚举i的倍数j∈[1,1e6/i],判断i*j是否在数组中，存在证明i是我们要找的，结束j的遍历！***设n=1e6，最多做遍历的次数为：不用担心时间LTE！#include <iostream>#includ...

2018-03-19 23:07:52 143

逆波兰表达式实现

空空如也