四光年-CSDN博客

转载操作系统启动的步骤(转)

转自：http://blog.chinaunix.net/uid-26495963-id-3066282.html启动第一步－－加载BIOS当你打开计算机电源，计算机会首先加载BIOS信息，BIOS信息是如此的重要，以至于计算机必须在最开始就找到它。这是因为BIOS中包含了CPU的相关信息、设备启动顺序信息、硬盘信息、内存信息、时钟信息、PnP特性等等。在此之后，计算机心里就有谱了...

2019-12-22 16:27:39 731

原创 java锁+操作系统锁

记一次lost wake-up问题这个问题是在测试操作系统中信号量机制对进程的控制中发现的，其实还是对多线程了解的太少了。问题一：int idx=100000,然后我们每一个进程都idx--,是否会出现A进程取出idx=100的同时B也取出来idx=100,然后各自--再放回去，idx==99而不是idx=98？尽管计算机计算的速度非常快，但这个问题还是会发生的！不信你试试，记得...

2019-12-12 21:03:18 789

原创 dij费用流

1：为啥可以直接上去直接把是h函数全部都是变成0 因为一开始所有的边的值都是正数。咦，我们不是加上了反向边？但是这个时候因为反向边都是没有流量的啊。2：如果当前找到增广路了，这个增光路的流量流完了，那最短路的处理能够使得下次dijkstra的时候，这条路不变成增广路吗？3：如果单纯只是出现负边权，而没有出现负环，这个时候dijkstra其实就够了。但是如果出现了负环，就必须使用spfa处...

2019-12-02 13:43:44 484

原创 java反射机制

一：java反射机制是啥？1：定义：Java 反射机制是在运行状态中，对于任意一个类，都能够获得这个类的所有属性和方法，对于任意一个对象都能够调用它的任意一个属性和方法。这种在运行时动态的获取信息以及动态调用对象的方法的功能称为Java 的反射机制。反射个人理解就是在JVM运行期间可以通过字节码文件，不通过new的方式创建对象。2：用途：https://www.bil...

2019-12-02 13:09:51 240 4

原创 E. Maximum Subsequence

https://codeforces.com/contest/888/problem/E一半枚举，一半二分，orz#include<bits/stdc++.h>using namespace std;#define ll long longconst int maxn=50;ll a[maxn],n,m;int vis[40];set<ll> s1,...

2019-09-24 23:49:27 139

原创 Codeforces Round #588 (Div. 2) E. Kamil and Making a Stream

https://codeforces.com/contest/1230/problem/E题意：给定一棵树，树上每一个点都有一个点权，root=1。定义f(u,v)为u到v路径上所有点的点权的gcd(u为v的祖先)。让你求所有的f(i,j)之和。解法：暴力，直接dfs。用map存储当前点到所有祖先节点可能的gcd值，和gcd值出现的次数。不会t吗？不会！假设x为当前访问的结点，y为x的祖先...

2019-09-24 23:41:03 191

原创 2—sat 处女座与宝藏

建边方略：AND = 1 : ~x -> x ,~y -> y (两个数必须全为1)AND = 0 ： y -> ~x ,x -> ~y (两个数至少有一个为0)OR = 1 ： ~x -> y ,~y -> x (两个数至少有一个为1)OR = 0 ： x -> ~x ,y -> ~y (两个数全为0)XOR = 1 ：...

2019-09-18 10:58:15 93

原创 bzoj2152 点分治或树形dp

https://www.lydsy.com/JudgeOnline/problem.php?id=2152说是模板题。。。感觉处理冗余那里很容易搞错。树形dp//求树上两点之间距离小于k的点对的个数#include <bits/stdc++.h>using namespace std;#define ll long longconst int maxn=4e4+5...

2019-09-17 17:00:13 120 1

原创 H. Lexical Sign Sequence 2018 ICPC Asia Jakarta Regional Contest

http://codeforces.com/gym/102001/problem/H思路就是先让所有的地方都放上1，然后处理。超级巧妙的一点就是那个t变量，看代码吧。#include <bits/stdc++.h>using namespace std;const int maxn=100010;//边修改边加入可以用一个变量记录前面的修改然后更新后面的约束...

2019-09-07 10:35:36 239 1

原创约瑟夫环

http://codeforces.com/gym/101955/problem/K2018沈阳区域赛的一个题，我可真是菜，wa了无数发。目前遇到的约瑟夫的两个问题：n个人组成一个圈，开始从1喊道k。喊k的人出局。问最后剩的序号是几？f(n)=(f(n-1)+k)%n。f(n)表示的是n个人最后剩下的人的序号(0-n-1) 求第m个出局的人的序号。f(n,m)=( f(n-1,m-1...

2019-08-16 23:05:48 118

原创洛谷2774 转换成二分图用网络流

网络流24题呀，然后就使劲的各种建图搞，但发现还是搞不了。始终不能解决的问题就是，会出现相邻的方块，但是他们都被选了。还是太弱鸡了，这题是将整个图染成黑白相间的颜色。拿着整个图值的总和 - 我们最终扣掉的那些方格的值。所以就转换成求最小的扣掉的那些方格的值。建立二分图，左边是白方格集合X，右边是黑方格集合Y。然后在相邻的方格之间建边，也就是在X和Y之间建边。这个时候跑出的最大流就是最小割。...

2019-08-04 22:16:17 146

原创二维背包

第一道二维背包。给了一个n x y和3*n个数据。先将每一个小矩形长宽调倒过来变成两个。然后对于同样宽度的小矩形，以长度为体积，x为总价值走多重背包，记录最大背包价值。然后在以y为总价值，再进行一次背包。这样会少情况，而且价值最大为1e9，dp数组开不到。正解：dp[x][y]表示的是长x，宽y的布被分解的最大价值。转移方程在代码里。很巧妙#include <bits/stdc++...

2019-08-04 10:12:52 328

转载差分约束总结

推荐个文章http://www.cppblog.com/menjitianya/archive/2015/11/19/212292.html一：个人总结1：差分约束=题目给定条件的约束+每一个点相互之间默认的约束+每一个点本身的约束(比如说只能选一次)2：区间差分约束一般是将l-r转换成p[r]-p[l-1]。p[i]表示的是前i个数。从而转换成线性差分约束。3：至少则转换成&gt...

2019-08-04 10:07:33 104

原创 hdu1529 二分+差分

关键还是列出不等式，但是这个题对于未知数二分了一下可真是太sao了。#include<bits/stdc++.h>using namespace std;#define ll long long #define inf 0x3f3f3f3fconst int maxn1=30;const int maxn2=1000;int head[maxn1],ans=1,dis...

2019-08-04 10:06:33 141

原创 hdu 2874 森林上任意两点的之间的最短距离

lca模板题，tle了一上午。先用树剖，tle。再用targin离线搞是mle。。。优化了半天终于不mle了，又变成tle。。。最后发现是add函数ans变量没有写&，擦。以后长记性了#include <bits/stdc++.h>using namespace std;#define res register int#define ll long longcon...

2019-07-27 13:42:56 169

http://acm.hdu.edu.cn/showproblem.php?pid=3461题意：给出一个由N NN个字母组成的锁。给出M MM个区间[L,R] [L,R][L,R]，每次操作可以将某个区间中所有字母变为字典序中的下一个字母。特殊地，‘z’会变成’a’。如果一把锁通过对可操作区间的有限次操作可以得到另一个锁，那么认为这两个锁是相同的。请求出一共有多少种不同的锁%(1e9+7)...

2019-07-27 13:42:13 136

原创 hdu2121 朱刘算法不定根

hdu4009也可以做一下，据说是模板题，我愣是没看出来，从hdu4009才晓得加虚根，但这个题又懵逼了，不知道咋处理，加虚根也不会处理啊，对算法的理解还是不够。题解：1：加虚根root=0，从虚根向1-n的点都连接一个边权为sum的边。2：sum=样例中所有边的权值和+1，不懂就继续往下看。3：如果我们从虚根出发形成的最小树形图的值为ans。如果ans-sum>=sum，...

2019-07-27 13:42:06 208

原创 hdu3572 网络流好题

题意：给出v种机器，m个任务，给出每一个任务完成需要的时间p天，要在s-e时间段内完成，问可不可以完成（任务可以不连续完成）思路：这个题确实很不好想，0点作为源点S，1001为汇点T，往下看。1-500作为每个任务的点，S向第i个点连边，权值为p。 501-1000作为每一天的情况。第i个任务的完成的区间是s-e,那么就从i点向s+5000-e+5000区间的所有点都连接一个权值为1的点...

2019-07-20 17:33:51 171

原创 hdu1811 拓扑细节

很好的一个拓扑排序。一不小心就wa。。。对于a>b，连一条a到b的边，b>a就连一条b到a的边。a=b 就用并查集处理，这个地方很容易出错。解决的方法有很多种，我是通过vector，使得多个点所连向和被连上的边都集中到汇点上。最后拓扑排序，如果queue里面同时有2个入读为0的点，一定不完整。用拓扑排序也可以判断是否冲突。#include <bits/stdc++.h&...

2019-07-20 17:33:22 95

原创 hdu3938 离线化+并查集

题意：定义两个节点间的距离为两个节点所有路径上经过的点中任意相邻两点的边最长的那一对点的边的权值。给出q次询问，每次给出一个L，让你判断到底有多少组点满足条件满足V(i,j)<=L解法：之前有做过类似的，知道是先对点从小到大排序，然后枚举边，用并查集。q次询问，O(m*q)复杂度肯定就凉凉啊。所以这里采用离线化处理。将q次询问的L从小到大排序。然后最后一次性输出。#include ...

2019-07-20 17:32:43 129

原创树状数组的总结

仅是个人总结，刚开始学还是看别的博客比较好。我推荐一个比较好的。https://blog.csdn.net/qq_39553725/article/details/76696168一：单点修改，区间查询(常见树状数组的基本用法)int a[maxn],c[maxn],n;//a是记录原值的数组，c就是树状数组，n表示的是个数int lowbit(int x){ return x&amp...

2019-07-03 23:12:47 113

原创洛谷2704 状压dp

思路：这个状压确实挺强。第i行的不仅仅和i-1行有关系，还和i-2行有关系。一般的思路好像解决不了问题，咋搞?我们定义一个数组dp[105][1<<10][1<<10]，dp[i][t1][t2]，i表示的是当前行，t1表示的是当前行的状态，t2表示的是i-1行的状态。假设t3表示的是i-2行的状态，枚举i-2行，i-1行，i行。则当满足三个条件0==t1 & ...

2019-06-11 17:41:39 162

原创 C. 小花梨判连通

https://acm.ecnu.edu.cn/contest/173/problem/C/题意：给你k张图，每个图有点和边。输出每个点1 2...n的点在每张图里面都联通的点的个数。思路：染色也行，并查集也行。在k张图里面给每个点染色。比如有3个点，4张图。染色情况如下点1：1 1 1 1点2：1 1 2 2点3：1 1 2 2将每个点的k个染色情况作为...

2019-05-25 23:54:19 98

原创 2019河北省大学生程序设计竞赛（重现赛）

记得补题！https://ac.nowcoder.com/acm/contest/903#questionB：大佬跟我说可以直接矩阵快速幂加速。。。怎末做呢？构建一个2*2的矩阵t第一行是1 0，第二行是q q。然后就是套矩阵快速幂就可以了。递推公式是Si=Si-1+(ai-1)*q。在取模的情况下，有一个确定的递推公式，让你求第n个数，一般都是矩阵快速幂。至于求逆元咋搞，我还没想明白...

2019-05-25 23:51:18 338

原创 URl和URI 通俗的例子

统一资源标志符URI就是在某一规则下能把一个资源独一无二地标识出来。拿人做例子，假设这个世界上所有人的名字都不能重复，那么名字就是URI的一个实例，通过名字这个字符串就可以标识出唯一的一个人。现实当中名字当然是会重复的，所以身份证号才是URI，通过身份证号能让我们能且仅能确定一个人。那统一资源定位符URL是什么呢。也拿人做例子然后跟HTTP的URL做类比，就可以有：动物住址协议://地球...

2019-05-08 10:54:01 2345

原创 hdu5289 st表

刷题太少。。。感觉巧妙的是查询的过程，枚举r。l只能递增。(比如[2,4] 不满足,那么[2,5],肯定不满足，所以[2,4]不满足的时候就l++)#include <bits/stdc++.h>using namespace std;#define ll long longconst int maxn=1e5+10;int stmax[maxn][20],stmin[m...

2019-04-24 16:40:43 130

原创 String与数值类型的转换

一：借用大数包BigInteger—>String 用toString方法 String—>BigInteger 通过BigInteger的构造器 BigInteger(Stringval) 将BigInteger的十进制字符串表示形式转换为BigInteger。 BigInteger(Stringval, intradix...

2019-04-21 12:00:17 268

原创对象包装器和自动装箱

一道很经典的面试题阅读下面程序输出结果：package Main; public class Main { public static void main(String[] args) { Integer i1 = new Integer(97); Integer i2 = new Integer(97); System.out.p...

2019-04-21 11:44:08 76

转载 java静态绑定、动态绑定

绑定：一个方法的调用与方法所在的类关联起来。java中的绑定分为静态绑定和动态绑定，又被称作前期绑定和后期绑定。　　静态绑定：（final、static、private）在程序执行前已经被绑定，也就是说在编译过程中就已经知道这个方法是哪个类的方法，此时由编译器获取其他连接程序实现。java中private类型的方法是默认为final的，不能被子类继承的。　　动态绑定：在运行根...

2019-04-21 10:35:08 97

原创洛谷1417 排序后的01背包

https://www.luogu.org/problemnew/show/P141总结：序列最优为dp 选与不选，且有sum：极有可能是背包选与不选，且有sum，且物品选择的顺序也影响结果：极有可能是按照某种顺序排列后再来个背包。（怎样获得这种顺序呢？我们选两个元素，让A先发生与B后发生和 B先发生A后发生的情况进行比较，然后就可以获得某种排序方式，本题就是这样）看到这个题第...

2019-04-16 16:34:11 160

原创全排列算法

一:c++ STLnext_permutation和prev_permutationbool next_permutation(iterator start,iterator end)next_permutation是求字典序的下一个排列，prev_permutation是求字典序的上一个排列。如果当前序列存在下一个序列，那么next_permutation返回的是ture，否则返...

2019-04-10 17:07:27 82

原创 java 数组排序的方法

从不依靠，从不寻找。非常沉默，非常骄傲。欢迎大家批评指正！一：Arrays里面的sort函数1）：基本数据类型升序排列：Arrays.sort(Object[]); Arrays.sort(Object[],l,r);给数组[l，r)区间的变量排序2）：基本数据类型降序排列：不好意思，查了api发现没有这个操作。你可以将升序排列后的数组再逆置，或者是你可以自定义排序函数。...

2019-04-03 18:05:29 138

原创 poj1160

又是动态规划的经典题序列最优化！从m个里面选n个！dp！#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<queue>#define M 1000001#define LL long longusing na...

2019-04-01 23:07:25 255

原创矩阵任意局部转置不变

http://codeforces.com/contest/1136/problem/CC. Nastya Is Transposing Matricestime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputN...

2019-03-17 18:37:08 951

原创 __int128取代欧拉降幂

链接：https://ac.nowcoder.com/acm/contest/392/B来源：牛客网找到了心仪的小姐姐月月后，华华很高兴的和她聊着天。然而月月的作业很多，不能继续陪华华聊天了。华华为了尽快和月月继续聊天，就提出帮她做一部分作业。月月的其中一项作业是：给定正整数A、B、P，求ABmodPABmodP的值。华华觉得这实在是毫无意义，所以决定写一个程序来做。但是华华并不会写程...

2019-03-09 23:09:29 280

原创洛谷1282 背包

感觉还是对背包问题不太熟练。思路：先把n个卡牌第一层加起来记为sum1，第二层卡牌加起来记为sum2。如果sum1<sum2,就将上下层翻转。使得sum1>sum2。V=sum1-sum2.所以我们就将问题转换成了，背包总体积为V，n个物品，每个物品的价值为1，体积为(a[i]-b[i])*2。求使得剩余体积尽量小的背包问题。体积会出现负数，所以要加以处理。#includ...

2019-02-27 14:39:28 178

原创矩阵快速幂洛谷1306

第一道矩阵快速幂，其实就是普通的快速幂再加上一个矩阵乘法就行了。对斐波那契序列有gcd(f[a],f[b])=f(gcd(a,b)),c++有一个函数__gcd(注意是两个_);#include <bits/stdc++.h>#include <algorithm>using namespace std;#define inf 0x3f3f3f3f#de...

2019-02-27 08:30:29 158

原创 bzoj4010 拓扑排序优先最小值

优先选最小值并不是直接建图进行拓扑排序，优先选最小值不同于求拓扑排序的最小字典序。思路：反向建图，优先选取最大值进行拓扑排序，最后倒序输出数组（或者记录的时候可以倒着记录，最后正着输出）#include <bits/stdc++.h>using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;co...

2019-02-27 08:25:48 232

原创 Magic ship

http://codeforces.com/contest/1117/problem/C 思路：二分感觉这个题挺好的，一开始的思路是能不能直接找构造方法？发现不行，然后在想搜索，还是不行。没想到是二分，还是做题太少了。主要的思想就是先让风刮二分的天数n天，然后计算这个位置到终点x、y坐标的差的绝对值和len。如果len<=n那么就一定能走到。把风刮船船的位移矢量和船自身的位移矢量分...

2019-02-27 08:24:26 157

原创 Fix a tree 拓扑消外向树

http://codeforces.com/contest/698/problem/B#include <bits/stdc++.h>using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int maxn=200005;int fa[maxn],N,in[maxn],vis[ma...

2019-02-26 18:12:19 133

校园导游—数据结构报告

空空如也