[原文链接] C++冷知识(逐渐更新) - By 种下一颗草莓 1. 输入 输出 4种输入输出方式 scanf 和 printf cin 和 cout puts gets getchar putchar 3 4 都是针对字符的，3针对字符串，4针对单个字符。 1. 单个字符 以方式1 4 输入单个字符时，空格 回车都会吸收，算作一个…

兰道函数 对于所有非负整数，兰道函数$g(n)$定义为对称群$S_{n}$的所有元素的秩之中，最大的一个。或者说，$g(n)$是$n$的所有整数分拆之中的最小公倍数。 例如${displaystyle 5=2+3}, {displaystyle lcm(2,3)=6}$没有其他5的分割方式能得出一个更大的最小公倍数，故此${displaystyle…

这个是原题链接 关键在于发现题目是逆序对，实际上你在赛场上直接猜结论（确实需要一定的勇气，毕竟数据不够多，罚时等等）也是可以的，那么我们来推导一下这个性质。 $$\sum{(a_i-b_i)^2} = \sum{[a_i^2 + b_i^2 - 2a_ib_i]} = \sum{(a_i^2 + b_i^2)} - 2\sum {a_ib_i}$$…

最长上升子序列(LIS) 1. $\mathcal{O}(n^2)$ 做法 设 $dp_{i}$ 表示以i 结尾的答案。所以先枚举一个 $i$ ，再从$1$ 开始枚举 $j$ ，每次看到小于 $a_{j}$ 的数，取一个最大的更新 $dp_{i}$ 。 2. $\mathcal{O}(nlog_n)$ 做法 状态设计： $dp_i$ 表示长度为 $…

一. 01背包 01背包问题关键在于某个物品取还是不取，状态可以从上一个占用空间转移而来。 for(int i = 1; i <= n; i++) { for(int j = m; j >= c[i]; j--) { dp[j] = max(dp[j], dp[j - c[i]] + w[i]); } } 二. 完全背包 完全背包问题就…

颜色限制（restriction） 时间限制: 1000ms 空间限制: 524288kB 输入文件名: restriction.in 输出文件名: restriction.out 题目描述 有一个 $n$ 点 $m$ 边的无向图，有 $k$ 种颜色编号为 $0∼k−1$，每条边有一种颜色。对于每种颜色，请判断假如删去所有这种颜色的边，得到的图是否…

2. 摘 Galo(OvO) 1s/512M [XOJ]仅评测链接 2.1 题目描述： 0v0 在野外看到了一棵 Galo 树，看到食物的 0v0 瞪大了眼睛，变成了 OvO 。 这棵 Galo 树可以看做是一棵以 $1$ 号点为根的$n$个点的有根树，除了根节点 以外，每个节点i都有一个 Galo ，美味度为$w[i]$。 OvO…