weixin_30455023-CSDN博客

转载数论函数与莫比乌斯反演

数论函数取整函数　　定义对于实数 $x$，记 $⌊x⌋$ 为不超过 $x$ 的最大整数。$\lfloor x \rfloor$ 也是满足如下关系的唯一整数：$\lfloor x \rfloor ≤x<\lfloor x \rfloor+1$　　对于正整数 $n$，$1$ 到 $n$ 中 $d$ 的倍数有 \(⌊\frac{n}{...

2019-10-01 23:20:00 526

转载。。。

https://www.cnblogs.com/onioncyc/p/8461267.htmlhttps://www.cnblogs.com/yydyz/p/10441165.htmlhttps://www.cnblogs.com/chenxiaoran666/p/Mobius.htmlhttps://blog.csdn.net/skywalkert/article/details...

2019-09-30 19:47:00 487

转载 Copy_Excel_To_Excel#--此脚本用于将目标表格写入新的表格--

#--此脚本用于将目标表格写入新的表格--#!/usr/bin/python3# -*-coding:utf-8-*-#python读取Excel中单元格的内容返回的有5种类型ctype : 0 empty,1 string, 2 number, 3 date, 4 boolean, 5 error#显示单元格属性方法sheet.cell(row,col).ctype...

2019-09-30 18:15:00 708

转载 Find_Excel_From_Dir获取特定目录下的excel表格，将数据复制出来

1 # -*- coding: utf-8 -*- 2 # -主要思路-，获取解压后的日志文件包 3 # -获取特定目录下的excel表格，将数据复制出来 4 import xdrlib ,sys 5 import xlrd 6 import os 7 import time 8 class Search_Excel_From_Dir:...

2019-09-30 18:14:00 323

转载更新的Main函数

1 # -*- coding: utf-8 -*- 2 # -*- 先解压日志文件压缩包-*- 3 # -*- 在已经解压的文件包里面找到目标excel文件 -*- 4 # -*- 将文件路径作为列表返回，获取路径下文件，读取复制到新excel文件-*- 5 # -*- 将数据表格自动生成 -*- 6 import sys 7 import time 8...

2019-09-30 18:12:00 113

转载递归解压压缩包_模块更新(需要下载对应的解压程序)

1 #!/usr/bin/python3 2 # -*-coding:utf-8-*- 3 import os 4 import shutil 5 import time 6 import sys 7 import subprocess 8 sys.setrecursionlimit(10000)#设置函数递归的最大深度，防止无限递归导致堆栈溢出和系统崩...

2019-09-30 18:12:00 255

转载 C# ling to sql 取多条记录最大时间

var _setList = (from f in _postgreDbContext.settlements group f by ( new { f.settlement_code })into g ...

2019-09-30 09:14:00 184

转载 P5490 【模板】扫描线

扫描线模板，注意点在注释里注意数组大小code：#include<bits/stdc++.h>#define gc getchar#define ll long longusing namespace std;const ll N=1e5+7;template <class I>inline void read(I &x) { l...

2019-09-29 19:32:00 109

转载 bzoj2306 [Ctsc2011]幸福路径倍增 Floyd

题目传送门https://lydsy.com/JudgeOnline/problem.php?id=2306题解倍增 Floyd。令 $f[i][j][k]$ 表示走了 $2^i$ 步，从 $j$ 到 $k$ 的距离最大值。然后转移就是 \(f[i][j][k] = \max\limits_{l=1}^n f[i-1][j][l] + p \cdot f[i-1...

2019-09-29 11:14:00 96

转载 bzoj2085 [Poi2010]Hamsters 矩阵快速幂+字符串hash

题目传送门https://lydsy.com/JudgeOnline/problem.php?id=2085题解考虑暴力 DP 的做法。令 $dp[i][j]$ 表示以 $j$ 为开头的子串，并且已经总共出现 $i$ 次的最小长度。\[dp[i][j] = \min_{k=1}^n\{dp[i-1][k] + len_j - LC(j, k) \}\]其中 \(...

2019-09-29 08:48:00 123

转载 bzoj1875 [SDOI2009]HH去散步矩阵快速幂

题目传送门https://lydsy.com/JudgeOnline/problem.php?id=1875题解如果没有这个“不能立刻沿着刚刚走来的路走回”，那么这个题就是一个常规的矩阵乘法。考虑一下这个限制怎么解决。因为限制的是边，我们不妨考虑和边有关的矩阵。首先把一条无向边拆成两个有向边，如果边 $A$ 的终点和边 $B$ 的起点相同，那么我们就说从边 $A$ ...

2019-09-28 21:35:00 125

转载打板子

记录打板子的速度...（争取每周都打一轮）数据结构：　　并查集　　Trie　　可持久化Trie　　树状数组　　线段树　　树链剖分　　Splay　　动态树　　主席树　　树套树　　分块　　点分治　　cdq分治　　整体二分　　莫队　　带修莫队　　树上莫队　　树上带修莫队数学　　线性筛　　数论分块　　gcd　　exgcd　　线性求逆元欧拉定理...

2019-09-28 18:30:00 199

转载 bzoj1706 [usaco2007 Nov]relays 奶牛接力跑矩阵快速幂

题目传送门https://lydsy.com/JudgeOnline/problem.php?id=1706题解换个方法定义矩阵乘法：先加再取 $\min$。对于一个 $n\times m$ 的矩阵 $A$，和一个 $m\times l$ 的矩阵 $B$ 它们的乘积 $C$ 是一个 $n \times l$ 的矩阵。\[C_{i, j} = \mi...

2019-09-28 18:14:00 120

转载 bzoj1297 [SCOI2009]迷路矩阵快速幂

题目传送门https://lydsy.com/JudgeOnline/problem.php?id=1297题解如果每一条边没有边权，那么就是一般的矩阵快速幂。因为边权 $\in [1, 9]$，所以我们可以把每一个点拆成 $9$ 个点，对于一条边权为 $w$ 的边 $x \to y$，可以建立一条边 $x_{w-1}\to y_0$。然后 \(x_i\to...

2019-09-28 16:46:00 124

转载 Eclipse 的快捷键

1、代码折叠的快捷键，默认是： Ctrl+Shift+Numpad_Divede(小键盘的/号) Ctrl+Shift+Numpad_Multiply(小键盘的*号)2、删除一行：Ctrl+D3、代码单行注释：Ctrl+/转载于:https://www.cnblogs.com/personblog/p/11603414.html...

2019-09-28 15:56:00 78

转载 loj2542 「PKUWC2018」随机游走 MinMax 容斥+树上高斯消元+状压 DP

题目传送门https://loj.ac/problem/2542题解肯定一眼 MinMax 容斥吧。然后问题就转化为，给定一个集合 $S$，问期望情况下多少步可以走到 $S$ 中的点。考虑 dp 的话，令 $dp[x]$ 表示从 $x$ 开始走的答案。如果 $x \in S$，那么 $dp[x] = 0$；否则，\(dp[x] = 1 + \frac...

2019-09-28 11:38:00 157

转载 P4707 重返现世扩展 MinMax 容斥+DP

题目传送门https://www.luogu.org/problem/P4707题解很容易想到这是一个 MinMax 容斥的题目。设每一个物品被收集的时间为 $t_i$，那么集齐 $k$ 个物品所需时间就是 $\{t_i\}$ 中的第 $n-k+1$ 大的时间。所以我们不妨把 $k$ 看成原来的 $n-k+1$，这个 $k \leq 11$。然后根...

2019-09-28 09:15:00 129

转载 bzoj4036 [HAOI2015]按位或状压DP + MinMax 容斥

题目传送门https://lydsy.com/JudgeOnline/problem.php?id=4036题解变成 $2^n-1$ 的意思显然就是每一个数位都出现了。那么通过 MinMax 容斥，可以把问题转化为对于一个集合 $S$，求 $S$ 中至少有一个元素出现的概率。这个问题等价于求 $S$ 中没有任何一个元素出现的概率，即出现的数都是 $S$ 的补...

2019-09-27 20:55:00 116

转载 hdu4336 Card Collector MinMax 容斥

题目传送门https://vjudge.net/problem/HDU-4336http://acm.hdu.edu.cn/showproblem.php?pid=4336题解minmax 容斥模板题。一个集合 $S$ 的至少有一个邮票出现的最早时间是 $\frac 1{\sum\limits_{i\in S} p_i}$。时间复杂度 $O(2^n)$。#in...

2019-09-27 19:46:00 134

转载 MinMax 容斥学习笔记

基本形式\[\max(S) = \sum_{T\subseteq S, T \neq \varnothing} (-1)^{|T|-1}\min(T)\]证明不提供数学证明。简要讲一下抽象理解伪证：考虑从大到小排名为 $i$ 的数，这个数会作为集合 $T$ 的最小值出现时，那么 $T$ 剩下的所有值都是从大于它的数中选取的。那么选取方案就是 \(\binom{i...

2019-09-27 16:58:00 830

转载 bzoj4455 & loj2091 [Zjoi2016]小星星容斥原理+树形DP(+状压DP?)

题目传送门https://lydsy.com/JudgeOnline/problem.php?id=4455https://loj.ac/problem/2091题解很不错的一道题。（不过在当时考场上应该是签到吧有一种很显然是错的的树形 DP 方法：令 $dp[x][i]$ 表示树上 $x$ 对于图上 $i$ 这个点，然后转移的时候直接枚举 $x$ 的孩子和 ...

2019-09-27 15:00:00 109

转载 Linux Shell编程参考大全

　　本文记录Linux Shell编程中常用基本知识，方便快速入门以及查询使用。本文主要分为以下几个部分：一、Shell中的变量任何编程语言中，有关变量的定义，作用范围，赋值等都是最最基本的知识。0、默认变量首先介绍几个shell中的默认变量。变量含义$0当前脚本名称$1脚本接收的第一个参数$2脚...

2019-09-27 13:50:00 109

转载 bzoj5161 最长上升子序列状压DP(DP 套 DP) + 打表

题目传送门https://lydsy.com/JudgeOnline/problem.php?id=5161题解回顾一下以前用二分求 LIS 的方法：令 $f[i]$ 表示长度为 $i$ 的 LIS 的最后一位的最小值。可发现不管目前 DP 到了哪儿，这个东西永远是递增的。关于 LIS 的题目的大都可以维护一些和这个东西有关的状态，所以我们考虑状压这个数组。因为这个数组...

2019-09-27 09:18:00 125

转载 bzoj4903 & loj2264 [Ctsc2017]吉夫特 Lucas 定理+状压DP

题目传送门https://lydsy.com/JudgeOnline/problem.php?id=4903https://loj.ac/problem/2264http://uoj.ac/problem/300题解真 - 签到题。对于一个组合数，直接进行 Luca 定理。\[\binom nm = \binom {\frac n2}{\frac m2} \binom {...

2019-09-26 21:52:00 143

转载 bzoj4145 [AMPPZ2014]The Prices 状压 DP

题目传送门https://lydsy.com/JudgeOnline/problem.php?id=4145题解好像这道题有不少方法呢。...谁叫这道题有点简单，所以方法多呗。我的方法：求出 $f[S]$ 表示要在同一家商店购买 $S$ 中的物品的最小代价。然后 $dp[S]$ 表示购买 $S$ 中的商品的最小代价。枚举子集转移即可。时间复杂度 \(O(m...

2019-09-26 20:37:00 104

转载 bzoj3812 主旋律容斥+状压 DP

题目传送门https://lydsy.com/JudgeOnline/problem.php?id=3812题解考虑对于图的联通性的 DP 的一般套路：总方案 - 不连通的方案。那么我们只需要求出使得整个图不强联通的方案数即可。假设我们钦定了一个 $p$ 点，然后通过枚举包含 $p$ 点的强连通分量来转移。但是会遇到一些问题：不像无向图，无向图的不连通只需要保证没有边相...

2019-09-26 19:55:00 92

转载 bzoj3717 [PA2014]Pakowanie 贪心+状压DP

题目传送门https://lydsy.com/JudgeOnline/problem.php?id=3717题解这道题大概也就只能算常规的状压 DP 吧，但是这个状态和转移的设计还是不是很好想。首先很显然，要优先把物品往大的包里面装，直到装不了别人再去装下一个。可以考虑贪心的策略，如果这个背包还能塞下的话，那么一定要去塞，这样至少是不会差的。所以令 $dp[S]$ 表示要...

2019-09-26 11:01:00 111

转载 bzoj2669 [cqoi2012]局部极小值状压DP+容斥

题目传送门https://lydsy.com/JudgeOnline/problem.php?id=2669题解可以发现一个 $4\times 7$ 的矩阵中，有局部最小值的点最多有 $2\times 4 = 8$ 个，所以我们可以状压一下每个局部最小值的位置有没有被选。从小到大填入每一个格子，那么如果一个点的周围有没有被填上的局部最小值，那么这个格子不可以被填。所以预处...

2019-09-26 08:08:00 105

转载 bzoj2560 串珠子状压DP

题目传送门https://lydsy.com/JudgeOnline/problem.php?id=2560题解大概是这类关于无向图的联通性计数的套路了。一开始我想的是这样的，考虑容斥，那么就是令 $dp[i][S]$ 表示我钦定了 $i$ 个连通块必须断开其余随意的方案数，然后 DP 完以后容斥加起来就可以了。但是这样是 $O(3^nn)$ 的，好像没有前途。然...

2019-09-25 19:56:00 102

转载 bzoj2004 [Hnoi2010]Bus 公交线路矩阵快速幂+状压DP

题目传送门https://lydsy.com/JudgeOnline/problem.php?id=2004题解如果 $N$ 没有那么大，考虑把每一位分配给每一辆车。假设已经分配到了第 $i$ 位，那么想要知道合不合法，我们需要知道每一辆车的上一个停靠点距离现在有多少的距离。考虑直接状压这个东西，发现它的数据量为 $P_{p}^k$，很大。但是我们可以发现，每一个位...

2019-09-25 17:22:00 111

转载「校内训练 2019-04-23」越野赛车问题动态dp+树的直径

题目传送门http://192.168.21.187/problem/1236http://47.100.137.146/problem/1236题解题目中要求的显然是那个状态下的直径嘛。所以这道题有一个非常简单的做法——线段树分治。直接把每一条边按照 $l, r$ 的区间放到线段树上进行分治，遍历的时候用并查集维护直径就可以了。时间复杂度为 \(O(n\log^2n)...

2019-09-25 15:02:00 151

转载 bzoj5210 最大连通子块和动态 DP + 堆

题目传送门https://lydsy.com/JudgeOnline/problem.php?id=5210题解令 $dp[x][0]$ 表示以 $x$ 为根的子树中的包含 $x$ 的连通块的点权和最大值，$dp[x][1]$ 为 $x$ 的所有孩子中的子树的连通块点权和最大值。于是有这样的式子：\[dp[x][0] = \max(w_x+\sum_{y\...

2019-09-25 07:18:00 90

转载抗癌日记

oifive与病魔的抗争，疾病是否可以打败他？其实就是模拟赛和互测总结啦会填坑…2019-08-26【高二组】模拟赛 1T1原题可以转化为在原图中删去一些点，使得图中度数最小的丶最大。我们注意到每次决定这个值的只有度数最小的点，只有删去它才可能影响答案。于是考虑贪心，每次删去度数最小的丶，并维护答案。复杂度 $O（n\log n）$。T2模拟，逻辑要想清楚，从基本...

2019-09-25 00:42:00 349

转载 gcd 环

首先可以特判出 $15$ 以下的点（其实我还是觉得判 $12$ 以下就行了）首先可以发现对于质数 $p$，若 $3p>n$，那么以 $p$ 为最小质因子的数一定不会在答案中。设\[k=upper\_bound(p+1,p+tot+1,n)-p-1\\t=upper\_bound(p+1,p+tot+1,n/3)-p-1\]可以除去不会使用的质数。...

2019-09-25 00:39:00 166

转载动态 DP 学习笔记

似乎 NOIP2019D2T3 把这个东西宣传的很到位啊。我才不会告诉你我已经学过一遍了早就忘了。以 bzoj4712 洪水为例。首先我们有一个暴力 DP 的式子。令 $dp[x]$ 表示以 $x$为根的子树的最小代价，$v[x]$ 表示每个点的权值。于是转移就是：\[dp[x] = \min(v[x], \sum_{y\in child_x} dp[y]...

2019-09-24 16:20:00 89

转载 bzoj4987 Tree 树上背包

题目传送门https://lydsy.com/JudgeOnline/problem.php?id=4987题解一道还不错的题咯。很容易发现一个结论：这 $k$ 个点构成的一定是一个连通块，并且走的时候应该是按照某种类似于 dfs 的遍历方式连续走的。可以发现，最终答案应该有：从根的某个子树走出来，到某个子树中去的这样的情况，也有可能是从根到某个子树中去的情况；同时，过程中...

2019-09-24 07:48:00 112

转载 bzoj1190 [HNOI2007]梦幻岛宝珠背包

题目https://lydsy.com/JudgeOnline/problem.php?id=1190题解好神仙的一道题啊。既然 $w_i = a_i\cdot 2^{b_i}$，那么不妨按照 $b_i$ 来分组，每一组内部先做一个 01 背包，记为 $f[i][j]$。然后考虑怎么求出最后的总答案。下面就是很妙的部分了：$dp[i][j]$ 表示前 \(i...

2019-09-23 21:23:00 96

转载 Win10下IIS配置 C#项目的部署与发布

1.找到控制面板：【开始】菜单鼠标右击，打开【控制面板】2.打开控制面板，点击【程序】，点击【启动或关闭windows功能】下一步，点击【启动或关闭wondows功能】3.开始修改IIS了，我是这样勾上的，有可能比较多。4.验证ISS是否正确安装，等待几分钟后IIS配置完成。在浏览器输入http:...

2019-09-23 16:14:00 503

转载 bzoj1004 [HNOI2008]Cards Burnside 引理+背包

题目传送门https://lydsy.com/JudgeOnline/problem.php?id=1004题解直接 Burnside 引理就可以了。要计算不动点的个数，那么对于一个长度为 $x$ 的循环，必须全部是红色、蓝色、绿色三种。所以显然可以 DP。令 $dp[i][j][k]$ 表示前 $i$ 个循环，$j$ 张牌选了红色，$k$ 张牌选了蓝色，剩...

2019-09-23 15:27:00 123

转载 bzoj4922 [Lydsy1706月赛]Karp-de-Chant Number 贪心+背包

题目传送门https://lydsy.com/JudgeOnline/problem.php?id=4922题解记录每一个串的没有匹配的右括号 $)$ 的数量为 $a_i$，为匹配的左括号 $($ 的数量为 $b_i$。令 $h$ 表示前面的所有括号序列的剩下的未匹配的左括号 $($。可以发现，每一个串的作用就是先让 $h$ 减少 $a_i$，如果...

2019-09-23 11:42:00 104

空空如也

空空如也