- 博客(4516)
- 收藏
- 关注
RSS订阅转载 CF 148D Bag of mice 题解
题面这是我做的第一道概率DP题；做完后发现没有后效性的DP是真的水；在这里说主要是再捋顺一下思路；设f[i][j]表示有i只白鼠，j只黑鼠是获胜的概率；显然：f[i][0]=1;然后分四种情况：1.先手刚好拿到白鼠:概率是i/(i+j);2.先手拿到黑鼠，后手拿到了白鼠：概率为0；3.先手拿到了黑鼠,后手拿到了也黑鼠，并且跑的是白鼠：概率是：:dp[i...
2019-09-30 15:06:00
522
转载 区间最值的优秀数据结构---ST表
ST表，听起来高大上，实际上限制非常多，仅仅可以求最值问题；为什么？先从原理看起；st表运用了倍增的思想：st[i][j] = min(st[i][j - 1],st[i + 2^(j - 1))][j - 1])；意义是：从i开始向后连续2^j个位置的最大值是，i开始向后连续2^(j-1)个位置的最大值和i+2^(j-1)开始向后连续2^(j-1)个位置的最大值；好了，...
2019-09-29 16:23:00
593
转载 洛谷 P1613 跑路 题解
题面这道题有着较小的n，所以求最短路时floyd也可以胜任；设g[i][j][k]表示目前从i到j存在权值为k的路径；由于边权均为1，所以g[i][j][k]=g[i][p][k-1]+g[p][j][k-1];对于f[i][j];如果i到j可以1步过去，那么=1；否则=inf；然后跑floyd就好了；#include <bits/stdc++.h>...
2019-09-29 14:38:00
512
转载 三校连训 异或 题解
异或 （xor.cpp/.c） 【题目描述】 给定一个正整数 n，在 [1,n]的范围内，求出有多少个无序数对(a,b)满足 gcd(a,b)=a xor b。【输入格式】 输入共一行，一个正整数 n。 【输出格式】 输出共一行，一个正整数表示答案。 【输入输出样例】 【输入样例】 3 【输出样例】 1 【样例解释】 只有(2,3)满足要求。 【数据范围】 对于 30%的数据，n≤10...
2019-09-29 14:34:00
319
转载 网络流之当前弧优化浅谈
在dinic中，我们会发现，dfs中每条边都会遍历至少一遍，那么我们可以把一定不会用到的边删去吗？答案是当然可以，这就用到了当前弧优化；其实这个优化在很久很久以前学习欧拉回路的时候就接触到了；每次增广一条路后可以看做“榨干”了这条路，既然榨干了就没有再增广的可能了。但如果每次都扫描这些“枯萎的”边是很浪费时间的。那我们就记录一下“榨取”到那条边了，然后下一次直接从这条边开始增...
2019-09-29 14:19:00
624
转载 LVS-dr 构建配置（直接路由模式）
在DR模式的群集中，LVS负载调度器作为群集的访问入口，但不作为网关使用；服务器池中的所有节点都各自接入Internet，发送给客户机的Web响应数据包不需要经过LVS负载调度器。第一步：关闭防火墙和selinuxsystemctl stop firewalldiptables -Fsetenforce 0第二步，配...
2019-09-29 11:35:00
115
转载 LVS-net构建操作
构建一，关闭全部防火墙和安全机制[root@localhost ~]# systemctl stop firewalld[root@localhost ~]# iptables -F[root@localhost ~]# setenforce 0二，调试器机安装两块网卡，要求不同网段的IP如上图三，调试器机开启路由转发功能[root@local...
2019-09-29 11:24:00
73
转载 分块的总结
分块，是一种优雅的暴力，它通过对数列分段，完成对数列一些区间操作和区间查询的操作，是一种根号算法。分块的功能： 1.区间加；2.区间减；3.。。。。。。 4.查询区间和 3.查询任意区间内有多少个数大于等于k(注意，这个功能是我们使用分块而不选择线段树的重要依据)在我的分块中，block表示原数组被分块后每块有多少个元素(不算最后一个)；...
2019-09-27 20:42:00
137
转载 洛谷 P2801 教主的魔法 题解
题面刚看到这道题的时候用了个树状数组优化前缀和差分的常数优化竟然AC了？(这数据也太水了吧~)本人做的第一道分块题，调试了好久好久，最后竟然没想到二分上还会出错！(一定要注意)仅此纪念；#include <bits/stdc++.h>#pragma GCC optimize(2)using namespace std;int a[1000010],...
2019-09-27 20:27:00
132
转载 [USACO13OPEN]照片Photo 题解
题面这道题似乎可以用单调队列优化DP做，但这里讲的是一种差分约束的思路;设s[i]表示1~i中选了多少个；s[b[i]]-s[a[i]-1]<=1;s[b[i]]-s[a[i]-1]>=1;s[i]-s[i-1]<=1;s[i]-s[i-1]>=0;然后跑SPFA最短路；但要注意：普通的SPFA根本就过不去，所以我...
2019-09-27 10:34:00
202
转载 [MtOI2019]永夜的报应 题解
题面题面说的乱糟糟的看起来似乎是个可持久化线性基；然而~一个式子搞定一切： a^b<=a+b那么把所有数异或起来便是答案；#include <bits/stdc++.h>using namespace std;int main(){ int n; cin>>n; long long ans=0...
2019-09-26 13:15:00
181
转载 [POI2011]SMI-Garbage 题解
题面想必各位大佬一定想到了把现在和目标值不一致的边加入到一个新建的图上；问题就变为了在新的图上寻找有多少个欧拉回路，并输出这些路径；我们可以用栈来记录情况，然后对于会回答稍微处理处理就好了；#include <bits/stdc++.h>#define inc(i,a,b) for(register int i=a;i<=b;i++)usin...
2019-09-25 16:02:00
191
转载 [ZJOI2008]骑士 题解
题面这道题稍微想一想就会联想到树形DP的入门题：没有上司的舞会；但是再想一想会发现这根本就不是一颗树，因为它比树多了一条边；这时候我们引入一个新的概念：基环树；顾名思义(??)，基环树就是在一颗树上填一条边构成的一个图；基环树也叫环套树（明明更像树套环）。我们在树上可以做的事情基本都可以在基环树上实现：比如树形DP基环树的基本解题思路就是找到在环上的两个点:S,T...
2019-09-24 14:21:00
143
转载 [ZJOI2007]时态同步 题解
题面这道题是一道比较水的XXOI题；我们可以发现，反着思考题目就变为了让所有叶子节点同时发出信号，然后这些信号同时到达根节点；可以证明，这样答案不会改变；那么我们可以自下而上dfs(),设f[u]表示以u为根，可以到达的最远距离；那么很显然，对于点u，它对答案的贡献度就是num(它子节点的个数)*f[u]-sum(f[v]);实现也比较容易，但要注意开long l...
2019-09-23 15:45:00
142
转载 web站点部署（基于tomcat构建成功后
web站点部署（基于tomcat构建成功后）-----------------------------------------------------cd /usr/local/tomcat8/webappsls上传一个包到此目录下meminfo.war浏览器可以访问了--------------------------------------------部署开源的站点下载官网：http...
2019-09-23 15:34:00
97
转载 洛谷 P1578 奶牛浴场 题解
题面1、定义有效子矩形为内部不包含任何障碍点且边界与坐标轴平行的子矩形。如图所示，第一个是有效子矩形（尽管边界上有障碍点），第二个不是有效子矩形（因为内部含有障碍点）。 2、极大有效子矩形：一个有效子矩形，如果不存在包含它且比它大的有效子矩形，就称这个有效子矩形为极大有效子矩形。（为了叙述方便，以下称为极大子矩形）3、定义最大有效子矩形为所有有效子矩形中最大的一个（或多个）。...
2019-09-23 13:57:00
146
转载 LOJ167 康托展开 题解
题面康托展开：康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的名次，因此是可逆的。X = A[0] * (n-1)! + A[1] * (n-2)! + … + A[n-1] * 0!A[i] 指的是位于位置i后面的数小于A[i]值的个数,后面乘的就是后面还有多少个数的阶乘这个算出来的数康拖展...
2019-09-23 11:56:00
146
转载 tomcat 多实例做
tomcat 多实例做解压部署tomcat程序tar xf apache-tomcat-8.9.16.tar.gzmv apache-tomcat-8.9.16 /usr/local/创建实例一个mkdir -p /usr/local/tomcat_instance/tomcat1拷贝程序目录下的conf文件放入个实例中cp -R /usr/local/apache-tomcat-8....
2019-09-22 12:11:00
68
转载 监控tomcat 状态(三种方法)
监控tomcat 状态一，打开java 监控页面vim /usr/local/tomcat8/webapps/memtest/meminfo.jsp<%Runtime rtm = Runtime.getRuntime();long mm = rtm.maxMemory()/1024/1024;long tm = rtm.totaMemory()/1024/1024;long fm ...
2019-09-21 17:02:00
1495
转载 三校联训 【NOIP模拟】寻找
题面“我有个愿望，我希望穿越一切找到你。”这是个二维平面世界，平面上有n个特殊的果实，我从(0,0)点出发，希望得到尽量多的果实，但是出于某种特殊的原因，我的运动方式只有三种（假设当前我在(x,y)）：1、我可以走到(x+1,y)2、我可以走到(x,y+1)3、我可以走到(x+1,y+1)现在我需要你的帮助，帮我找出我最多能够得到多少个果实。对于70%的数据1...
2019-09-21 16:17:00
98
转载 洛谷 P1809 过河问题 题解
题面这道题是一道贪心+DP的好题：首先排序是一定要干的事情。然后我们分情况处理：1.如果剩一个人，让最小的回来接他2.如果剩两个人，让最小的回来接，剩下的那两个人（即最大的两个人）过去，让次小的回来，最小的两个过去以上的两个方法一定是最优的，因为最大的人要不让最小的送，要不带一个次大的；将上面的意义转为DP方程就是：1.f[i]=f[i-1]+a[1...
2019-09-21 16:06:00
212
转载 有关多边形面积的总结
矢量矢量加减法：设二维矢量P = ( x1, y1 )，Q = ( x2 , y2 )。则矢量加法定义为： P + Q = ( x1 + x2 , y1 + y2 )，同样的，矢量减法定义为： P - Q = ( x1 - x2 , y1 - y2 )。矢量的点乘：P=(x1, y1)，Q=(x2, y2)。则向量的叉乘设矢量P = ( x1, y...
2019-09-20 20:38:00
204
转载 LOJ 103 字串查找 题解
题面这道题是KMP的模板。KMP需要注意的细节有很多，所以把这篇文章发上来供参考；#include <bits/stdc++.h>using namespace std;char a[1000010],b[1000010];int nxt[1000010];int n,m;void pre(){ nxt[1]=0; ...
2019-09-20 19:27:00
134
转载 基于端口的虚拟主机
基于端口的虚拟主机一，编辑server.xml文件修改里面文件 在server.xml 中再设置一个主键如图 二，启动/usr/local/tomcat8/bin/startup.sh转载于:https://www.cnblogs.com/123456likun/p/11558214.html...
2019-09-20 16:55:00
99
转载 洛谷 P2384 最短路 题解
题面这道题需要用到一个神奇的知识点：log(n*m)=log(n)+log(m)；所以对所有边权取个log，然后算log的最短路的同时维护乘积即可#include <bits/stdc++.h>#define int long longusing namespace std;struct littlestar{ int to; ...
2019-09-20 16:06:00
145
转载 POJ 2492 A Bug's Life 题解
题面这道题是一道标准的种类并查集：种类并查集是给每个结点一个权值。然后在合并和查找的时候根据情况对权值来进行维护。通过将原有的区间范围变大使并查集可以维护种类的联系：#include <iostream>#include <cstdio>using namespace std;int f[200010];int zhaob...
2019-09-20 15:02:00
231
转载 LOJ 10214 计算器 题解
题面k==1时，快速幂就好了；k==2时，exgcd就好了，但要注意取模范围的控制；k==3时，BSGS可以解决高次同余方程：然后就可以开心的A掉了，但要注意特殊情况的特判#include <bits/stdc++.h>using namespace std;long long KSM(long long a,long long...
2019-09-20 11:36:00
93
转载 tomcat配置ssl 加密
tomcat配置ssl 加密一，keytool -genkeypair -alias tomcat -keyalg RSA -keystore /usr/local/tomcat8/keystore然后按提示输入二, 修改server.xml 配置文件查看:ls -l /usr/local/tomcat8进入vim /usr/local/tomcat8/conf/server.xm...
2019-09-20 09:54:00
169
转载 tomcat 连接数据库mysql
tomcat 连接数据库 分两台机器(一台数据库机，一台tomcat机器)步骤首先mysql要装好启动tomcat装好启动一（tom机）：拉一个包然后解压tar xf SLSaleSystem.tar.gz -C /web/webapp二（tom机）：编辑Tonmat主配置文件vim /usr/local/tomcat8/conf/server.xml在...
2019-09-20 09:17:00
508
转载 nginx 均衡分配负载 搭配
Nginx均衡分配负载1进入主配置文件 vim /usr/local/nginx/conf/nginx.confupstream tomcat_server { server 192.168.200.112:8080 weight=1; server 192.168.200.113:8080 weight=1;}server { location ~* \.jsp$ { ...
2019-09-19 20:46:00
111
转载 洛谷 P2868 [USACO07DEC]观光奶牛Sightseeing Cows 题解
题面这道题是一道标准的01分数规划：但是有一些细节可以优化：不难想到要二分一个mid然后判定图上是否存在一个环S，该环是否满足∑i=1t(Fun[vi]−mid∗Tim[ei])>0但是上面的算法并不好实现，所以可以将两边同时乘上-1,使式子变为∑i=1t(mid∗Tim[ei]−Fun[vi])<0那么该问题就转化成了在每一个图中跑一边SPFA来寻...
2019-09-18 20:06:00
97
转载 洛谷 P1306 斐波那契公约数 题解
题面结论：gcd(F[n],F[m])=F[gcd(n,m)];F[n]=a和F[n+1]=bF[n+2]=a+b,F[n+3]=a+2b,…F[m]=F[m?n?1]a+F[m?n]bF[n]=a,F[n+1]=b,F[m]=F[m?n?1]a+F[m?n]F[m]=F[m?n?1]?F[n]+F[m?n]?F[n+1]gcd(F[n],F[m])=gcd(F[n],F[m?n?1...
2019-09-18 18:02:00
111
转载 POJ 3585 Accumulation Degree 题解
题面一句话题意：找一个点使得，使得从这个点出发作为源点，发出的流量最大，输出这个最大的流量这道题是换根法+二次扫描的模板；首先若确定1为原点，那么可以写出dp方程：当v的度是1时， g[u]+=g[v];否则g[u]+=min(g[v],star[i].w);但以上仅仅是有原点的做法，那么如果没有原点就只能是N^2了吗？当然不仅可能；我们从上到下开始dfs，设f[i]...
2019-09-18 13:46:00
110
转载 Notepad++安装json插件
https://blog.csdn.net/yyjunyao/article/details/81480138转载于:https://www.cnblogs.com/feifeicui/p/11540434.html
2019-09-18 11:04:00
47
转载 java动态更新枚举类
工作中遇到需要对枚举类的值进行动态更新 手动改不现实也不方便 现记录下来方便以后学习使用1.在工程utils包中添加动态更新枚举类得工具类(根据自己得项目，放到指定位置调用就可以)2.一开始陷入了误区，认为要根据我自己得枚举类去修改，addEnum和makeEnum方法因为网上示例都是两个参数得，而我的是5个的，弄了好久(被自己蠢晕)才发现，它是个数组啊。package ...
2019-09-16 15:20:00
728
转载 一些NOIP的要点汇总
1.dilworth定理：在一个序列中，最长下降子序列的个数(下降子序列的最小划分)就等于其最长不下降子序列的长度。2.floor(),ceil(),round()三个函数的返回值都是一个浮点数，floor()是把浮点数向下取整，ceil()是把浮点数向上取整，round()是把浮点数四舍五入；3.#define cin std::ios::sync_with_stdio(fal...
2019-09-16 13:41:00
125
转载 nginx 网络服务搭建lnmp
注：(蓝色是步骤 红色是命令)Nginx版本：社区版 www.nginx.org企业版 www.nginx.com（被F5收购） tengine tengine.taobao.org第一步：关闭防火墙，安全机制sysytemctl stop firewalldiptaoles -Fsetenforce 0第二步：安装需要的软件包(yum安装...
2019-09-16 09:52:00
128
转载 一道最大公约数的题：easy number
现有n个Zack，每个Zack有一个一个能力值，从这n个Zack中选出k个，使他们的最大公约数的值最大【输入格式】第一行有一个整数n，代表有n个Zack第二行n个整数ai，代表每个Zack的能力值【输出格式】一共n行，第n行为k=i情况下的能力值的最大公因数【样例输入】41 2 3 4【样例输出】4211...
2019-09-15 16:20:00
288
转载 有关最小生成树的一些心得
求最小生成树的两种算法：1.Kruskal算法(本质是贪心)1. 把图中的所有边按代价从小到大排序； 2.按权值从小到大选择边，所选的边连接的两个顶点ui,viui,vi,应属于两颗不同的树，则成为最小生成树的一条边，并将这两颗树合并作为一颗树。 这种做法可以通过并查集来维护连通性，总体复杂度是O(m+并查集的玄学复杂度)；#include<iostream...
2019-09-15 15:51:00
511
转载 洛谷 P1417 烹调方案 题解
题面这道题是一道典型的排序dpa[i]−b[i]∗(t+c[i])+a[j]−b[j]∗(t+c[i]+c[j])a[j]−b[j]∗(t+c[j])+a[i]−b[i]∗(t+c[i]+c[j])a[j]-b[j]*(t+c[j])+a[i]-b[i]*(t+c[i]+c[j])a[j]−b[j]∗(t+c[j])+a[i]−b[i]∗(t+c[i]+c[j])a[i]...
2019-09-15 15:37:00
74
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人