Hexo

P2240 部分背包问题 纯 C++11 风格的代码： 123456789101112131415161718192021#include <bits/stdc++.h>using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; vector<pair<double, pair<int, int> > > coins(n); for (auto &c : coins) { cin >> c.second.first >> c.second.second; c.first = (double)c.second.second/c.second.first; } sort(coins.begin(), coins.end(), greater<p ...

思维CheatSheet 思路 多角度思维 这个题有多少种思路，目前选择一条路。每个思路都要想一点。如果是dp，有多种方程，那每个都要考虑一下。 推导Observation 眼看出来的 基本公式，基于基本公式的Ob 卡住了 你想的题根本不是原问题 中间推导错了 题目读错了 换角度理解问题 转换问题的表示方法。换一种理解方式 常规推导 考虑答案由什么组成(拆分出可以维护的情况) 考虑最简单的几种情况(best case) 考虑状态的转移 什么会产生贡献，哪些会对答案产生贡献 考虑答案的单调性，时空转移 分类讨论 问题可以分为几种情况 贪心 什么构成答案最好（构造一个最好的答案） 计算操作的最大值最小值： 以某种贪心的策略一定可以达到最优，模拟这种策略的步骤 分析最大值 二分/枚举 如给定某个参数，是不是会好做一定 动态规划、递推 考虑问题的子结构 考虑状态是什么，如何转移 换一种更好的状态 简化子结构（去除冗余状态） 通过贪心优化转移，减少转移的数量 用数据结构 ...

基础知识 求和符号 \[ \sum_{i=1}^{n}=a_1+a_2+a_3+...+a_n \] 求和符号的性质 结合律 \[ \sum_{i=1}^{n} \sum_{j=1}^{n} a_i b_j = \sum_{j=1}^{n} \sum_{i=1}^{n} a_i b_j \] 分配率 \[ \sum_{i=1}^{n} a_i \cdot k = (\sum_{i=1}^{n}a_i) \cdot k= k\sum_{i=1}^{n}a_i \\ \sum_{i=1}^{n}\sum_{j=1}^{n}a_i b_j = \sum_{i=1}^n (a_i\sum_{j=1}^n b_j) = (\sum_{j=1}^{n}b_j)\cdot(\sum_{i=1}^{n}a_i) = (\sum_{i=1}^{n}a_i)\cdot(\sum_{j=1}^{n}b_j) \] 改变枚举对象 令 \(z=x+y\) \[ \sum_{x=0}^a\sum_{y=0}^b f(x,y) = \sum_{z=0}^{a+b}\sum ...

Trie Trie 是一个用树来存储字符串的结构。 基本操作 插入一个字符串 查找一个字符串是否在树中 维护对应字符串的附加信息(如个数之类的) 模板 P2580 于是他错误的点名开始了 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include <bits/stdc++.h>using namespace std;const int maxn = 1e4 + 5;const int maxnode = maxn * 50;const int sigma_size = 26;#define c ((ch)-'a')int child[maxnode][sigma_size], val[maxnode];int sz, n;void insert(string s) { int u = 0; // 从根节点 u = 0 开始插入 for (char ch : s) { ...

AtCoder Grand Contest 047 AtCoder Grand Contest 047 A. Integer Product 给定 \(n\) 个浮点数，计算有多少个 \((i, j)\) 使得 \(A_{i} \cdot A_{j}\) 是整数 \(2\leq N \leq 200 \ 000\) , $ 0 < A_{i} ^{4}$ , \(A_{i}\) 最多 \(9\) 为小数. 思路 通过题设条件缩小范围， 枚举 由于数据比较大，不能直接暴力做。判断是整数这个条件不太好集体维护。所以要找出题目中的特性，看看有没有机会让范围缩小。最好是可以 先考虑 \(A_{i} \cdot A_{j}\) 什么情况下是整数。发现，对于任意有限小数 \(x\), 可以在乘上 \(10^{n}\) 后肯定会变成整数。所以每个数必然是 \(k\cdot 2^{m}\cdot 5^{n}\) 的形式, 通过乘 \(10^{n}\) 把分母上的 \(2^{m}\cdot 5^{n}\) 约去. 而之前的 \(k\) 不影响答案。所以我们只要 ...

线段树 线段树是一种用来维护区间性质的数据结构，此篇不讲解基础，而是讲解在算法竞赛中的应用。读者需要至少会写线段树懒标记维护区间求和操作。 目前使用的模板 我的懒标记的定义是： 已经维护好了当前节点，但子节点还没维护好. 普通版本 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950const int maxn = 1e5 + 5;int n, m;typedef long long typec;#define lson (o<<1)#define rson (o<<1|1)#define mid ((l+r)>>1)#define len(x,y) ((y)-(x)+1)typec sumv[maxn*4], addv[maxn*4];typec A[maxn], qans, v;int ql, qr;void build(int o, int l, int r) { addv[o] = 0; ...

Educational Codeforces Round 92 (Rated for Div. 2) link A. LCM Problem 构造 给定区间 \([l,r]\) 求 \(2\) 个在里面的数，使得它们的最小公倍数也在区间内，否则输出-1 -1 . 可以知道 \(l, l*2\) 是2个最小的可能组合，只要判断 \(l*2 > r\) 即可. B. Array Walk 贪心 由于可以折返的步数比较少。我们可以枚举折返的步数。当折返的步数固定为 \(j\) 的时候。有2种情况， \(j\) 步都是折返后又回来。这种情况最远走到了 \([1,k-2j]\) \(j-1\) 步是折返后又回来，最后一步是折返后不回来。这种情况的区间是 \([1,k-2(j-1)-1]\) 可以证明：若折返，则必定是在当前区间的最大两个相邻元素间折返。 那么我们用前缀和的方式求出 \([1,i]\) 的和还有最大相邻元素的位置。那么分情况讨论这两种情况的最大值。最后取个更优的解即可 \(O(n)\) 1234567891 ...

Week1 : 树 概念 vollständige Baum 完全树(所有节点有相同孩子个数) \(k\)-verzweigte Baum k叉树 数学归纳法 证明完全二叉树的深度为 \(log_{2}(n+1)\) Induktionsanfang: ==n = 1==: Laut induktiver Definition enthält jeder Unterbuam mindestens einen Knoten. n=1 bedeutet also, dass der Baum ein Blatt ist. Die Tiefe ist 1. Zu zeigen ist also: \(1 \leq \log _{2}(n+1)\) . Es gilt \(\log _{2} 2=1 \geq 1\) Induktionsvoraussetzung: ==Für alle \(k \leq n\) gilt, dass== die Tiefe eines s vollständigen 2-verzweigten Baumes mi ...

ArchLinux完整安装 首先贴几个有用的链接 https://www.viseator.com/2017/05/17/arch_install/ https://wiki.archlinux.org/ Vmware Workstation虚拟机安装 下载iso镜像 https://www.archlinux.org/download/ 这个链接里面找一个网站的版本下载，这里选择了163。然后下载里面的archlinux-日期-x86_64.iso 这个文件 image-20200602094003121 创建虚拟机 点击创建新的虚拟机 image-20200602094126559 然后选择镜像 image-20200602094239435 操作系统选择Linux 5.x 64位。VirtualBox可以直接Archlinux 64位 然后给虚拟机命名，然后选择cpu和内存大小。这个根据系统配置自行选择。我选择了2个2核处理器，4g内存。后面默认过去，到磁盘大小，我给了20g。然后后面的一直默认即可。 开启此虚 ...

软件技术 编译环境设置 下载Maven 到这个链接 里下载maven的包 image-20200507114645077 然后解压到某个目录下， 配置环境变量 把maven目录下的bin目录添加到path里面 image-20200507114852666 然后可以用 mvn -v 检查配置情况 image-20200507115027756 Lecture 2 Software lifecycle 分析问题 要从问题中提取功能，然后记录在backlog上： 比如说： Bumpers is a game where cars drive on a game board and can crash each other. 
 In each collision, there is a winning car. 
 The car that wins all collisions is the winner of the game. 
 The player can start and stop the game ...