好文收藏夹

[HDU - 3501] Calculation 2 这篇文章以后的更新都会在  https://two-plus-two-make-four.blogspot.com/2020/01/hdu-3501-calculation-2.html 题意 给你一个正整数  n ，计算小于  n  且与  n  不互质的 正整数 的和 注意是 小于  n，这告诉了你在 n = 1 时应该输出 0 想法 欧拉函数入门题 小于  n  且与  n  互质的数的和等于  n * φ(n) / 2 考虑以下事实： 如果 a, b 互质，则 b - a, b 互质（反证法） 把所有小于 n 且与 n 互质的数列出来，得到一张长度为 φ(n) 的表 [a1, a2, ..., am] 接着根据上述推论，列出一张新的表 [n - a1, n - a2, ..., n - am] 神奇的事情发生了 根据我们的推理，两张表都是小于 n 且与 n 互质的数，那么？ 这两张表是 相同 的！ （数学之美 两表对应项相加得 n，两表长度均为 φ(n)，命题得证 题解 剩下的内容就很 naive 了 主要就是调调精度之类的技术细节 某教练：不要使用  #define int long long  ！ 某教练：把常量都  const  出来！ 直接上代码吧 # include "bits/stdc++.h" using namespace std ; typedef long long ll; typedef unsigned long long ull; template < typename Tp> inline void read (Tp &x) { x = 0 ; bool neg = 0 ; char c = getchar(); for (; ! isdigit (c); c = getchar()) { if (c == '-...

[LightOJ - 1289] LCM from 1 to n 这篇文章以后的更新都会在  https://two-plus-two-make-four.blogspot.com/2020/01/lightoj-1289-lcm-from-1-to-n.html 题意 求 (1, 2, ..., n) 的 最小公倍数   (lcm)  ，多组测试数据 一些想法 MicroMaker  神犇说是和 φ 函数有关的一些东西，但是想了半天似乎并没有什么思路 于是就有了一个很暴力的想法 其实还有一个更  naive  的想法，先把质数表跑出来，再预处理出每个质数的次方之类的信息，然后二分查找什么的，都扯到压缩数据了。。。 题解 先用线性筛把  1 ~ 1e8  的所有质数给筛出来 然后考虑这样一个客观事实（来自官方题解） lcm(1, 2, ..., n + 1)  = lcm(1, 2, ..., n) * p  这里的  p  是指素数，如果  n + 1  =  p ^ k  ，那么就得到那样的递推式 lcm(1, 2, ..., n)  其它情况 有了递推式就好办了 接下来就到了喜闻乐见的  O(n) 过一亿  时间 看到  CSDN  上有人手写  bitset ，感觉自带的  bitset  效率也不错啊。。。   STL 依赖症患者 以下是丑陋的代码： # include "bits/stdc++.h" using namespace std ; typedef long long ll; typedef unsigned long long ull; template < typename Tp> inline void read (Tp &x) { x = 0 ; bool neg = 0 ; char c = getchar(); for...

比赛地址 STring 和括号匹配是类似的，开一个栈记一下就好了。事实上只要记栈中的元素个数。 代码 Minimum Sum 单调栈板子题。 代码 Tree Restoring 首先找到 $d=\max\left\{a_i\right\}$，那么直径的长度为 $d$。 设 $cnt_i$ 表示满足 $a_j=i$ 的 $j$ 的数量，分类讨论一下： 若 $d$ 为奇数，则应有 $$ \begin{cases} cnt_i\geq 2,&i\in[\frac{d+1}{2}+1,d]\\ cnt_i=2,&i=\frac{d+1}{2}\\ cnt_i=0,&i\in[1,\frac{d-1}{2}] \end{cases} $$ 若 $d$ 为偶数，则应有 $$ \begin{cases} cnt_i\geq 2,&i\in[\frac{d}{2}+1,d]\\ cnt_i=1,&i=\frac{d}{2}\\ cnt_i=0,&i\in[1,\frac{d}{2}-1] \end{cases} $$ 代码 ~K Perm Counting 转化问题：给出一个 $n\times n$ 网格，其中 $(i,i\pm k)$ 是黑色的，其它格子是白色的，你需要选择 $n$ 个格子使得没有两个格子在同一行或同一列，求不选择黑色格子的方案数。 首先可以考虑容斥。设 $f_i$ 为选了至少 $i$ 个黑色格子的方案数，则答案为 $$ \sum_{i=0}^n(-1)^i(n-i)!f_i $$ 考虑计算 $f_i$。容易发现一件事是每个黑格子最多只会与两个黑格子冲突。我们把每个黑格子向与它冲突的黑格子连边，则会形成若干条链。然后对于每条链 DP。设 $dp_{i,j,0/1}$ 表示前 $i$ 位选了 $j$ 个，当前没选/选的方案数。 这样子最后需要卷积合并；有一种简单的方法是将所有链连成一条，并在交接处特判转移，就不需要卷积合并了。 代码 Sugigma: The Showdown 考虑游戏怎样才可以无限进行。 假如先手能到达某个点 $u$，且第一棵树上存在一条边 $...

比赛地址 Divide a Cuboid 如果有一边长为偶数，答案为 $0$。 否则找到最长的边切开。 代码 Colorful Slimes 枚举循环右移的次数，相当于每种颜色都可以通过选择某个范围内的颜色得到，直接取最小的即可。 代码 AND Grid 我们只需要想办法造两个矩阵使得整个图连通且两个矩阵不交。 通过人类智慧可以想到造成这样 #####. .....# #..... .##### #####. .....# #..... .##### #####. .....# #..... .##### 把左边并上原图作为第一个矩阵，右边并上原图作为第二个矩阵。 代码 Teleporter 显然 $1$ 城市的目的地只能为自己。 那么剩下的只有 $n-1$ 条边了，相当于一棵树，直接 DFS 一遍，子树高 $\geq k$ 时就断掉父边接到 $1$ 城市去。 代码 Salvage Robots 推荐食用 官方题解 。 考虑将所有机器人移动转化一下，变为出口以及边界移动。 设 $dp_{u,l,d,r}$ 表示出口已经到过的范围是以 $(u,l)$ 为左上角、$(d,r)$ 为右下角的矩形，最多能救的机器人数。 转移考虑一下往哪边扩大，容易算出能救的机器人（排除掉已消失的）所在的范围，通过前缀和即可算出数量，然后就可以转移了。 这么讲非常的不清楚，再次推荐使用 官方题解 。 我真的讲不清楚 /kel $dp$ 开 int 开不下，可以开 short 。 代码 Namori 戳这里

UVa Luogu 分析 这个东西应该叫做最大密度子图。 我们要让 $\frac{\sum E}{\sum V}$ 最大，显然是分数规划。 二分答案 $mid$，那么 $$ \frac{\sum E}{\sum V}>mid\Longrightarrow\sum E-mid\sum V>0 $$ 问题变为，选一个点的代价是 $mid$，选一条边的收益是 $1$，选一条边必须选它的两个顶点，求最大收益。 显然是一个最大权闭合子图问题，那么最大收益即为边数减最小割。 这样子就能求出最大值了，然而题目要方案，直接找到所有与源点相连的点输出就好了。 代码 // =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #include <bits/stdc++.h> #define re register using namespace std; inline int read() { int X=0,w=1; char c=getchar(); while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); } while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar(); return X*w; } const int N=2000+10,M=10000+10; const double eps=1e-9; const int inf=0x3f3f3f3f; int n,m,s,t,x[M],y[M]; vector<int> ans; struct edge { int v; double w; int nxt; } e[M<<1]; int head...

【洛谷P4503】【CTSC2014】企鹅QQ 题目背景 PenguinQQ  是中国最大、最具影响力的 SNS（Social Networking Services）网站，以实名制为基础，为用户提供日志、群、即时通讯、相册、集市等丰富强大的互联网功能体验，满足用户对社交、资讯、娱乐、交易等多方面的需求。 题目描述 小Q  是  PenguinQQ  网站的管理员，他最近在进行一项有趣的研究——哪些账户是同一个人注册的。经过长时间的分析， 小Q  发现同一个人注册的账户名称总是很相似的，例如  Penguin1 ， Penguin2 ， Penguin3  ……于是  小Q  决定先对这种相似的情形进行统计。 小Q  定义，若两个账户名称是相似的，当且仅当这两个字符串等长且恰好只有一位不同。例如  “Penguin1”  和  “Penguin2”  是相似的，但  “Penguin1”  和  “2Penguin”  不是相似的。而  小Q  想知道，在给定的  n  个账户名称中，有多少对是相似的。 为了简化你的工作， 小Q  给你的  N  个字符串长度均等于  L  ，且只包含大小写字母、数字、下划线以及 ‘@’ 共64种字符，而且不存在两个相同的账户名称。 输入格式 第一行包含三个正整数  N  ， L  ， S  。其中  N  表示账户名称数量， L  表示账户名称长度， S  用来表示字符集规模大小，它的值只可能为 2 或 64。 若  S  等于 2，账户名称中只包含字符 ‘0’ 和 ‘1’ 共2种字符； 若  S  等于 64，账户名称中可能包含大小写字母、数字、下划线以及 ‘@’ 共64种字符。 随后  N  行，每行一个长度为  L  的字符串，用来描述一个账户名称。数据保...

【CF961F】k-substrings 题意 给定一个长度为  n  的字符串  S 我们设  S  的  k-子串  是  S[k … n - k + 1] ，设字符串  t  是字符串  T  的  奇正确前后缀  当且仅当满足以下条件： t  长度为奇数 |t| < |T| t  是  T  的  border （既是前缀又是后缀） 对于  k = 1 … n / 2  上取整，求  S  的  k-子串  的最长  奇正确前后缀  长度。无解输出  -1 2 ≤ n ≤ 1,000,000 官方题解 枚举某个前缀（指题目要求的相同前后缀中的前缀）的中心位置  i ，那么对应后缀的中心位置已经确定了（ n - i + 1 ），可以二分答案求出对于每个中心位置  i  最大的符合要求的相同前后缀（设长度为  2 * x + 1 ），然后更新  ans[i - x]  为  2 * x + 1 ；最后把每个  ans[i]  用  ans[i - 1] - 2  尝试更新一下 其实以上做法也基于这个结论？ ans[i - 1] <= ans[i] + 2 ，这个可以容易地用反证法证明（类似  kmp  ） 因此从  ans[(n + 1) / 2]  开始求就行了 参考代码： # pragma GCC optimize( "Ofast,no-stack-protector,unroll-loops,fast-math" ) # pragma GCC target( "sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native" ) # include "bits/stdc++.h"...