时隔一年（差两天）来做还是不会做，甚至连我当时写的是什么都没看懂，这充分凸显了写博客的必要性。题意求 $\le N$ 的最大数 $x$ ，满足 $\forall 1\le i\le x$ ，$i$ 的约数个数 $<$ $x$ 的约数个数。题解直接上搜索。先预处理可能会被用到的质数表，对于每个质数，搜索它可能会被用几次，最后如果约数个数大于当前最大值 或 约数个数相等但数值较小 都对答案...
题意求：$$\dfrac {1}{x}+\dfrac {1}{y}=\dfrac {1}{n!}$$的正整数解 $(x,y)$ 的组数。题解对方程进行化简：$$\dfrac {x+y}{x\times y}=\dfrac {1}{n!}$$交叉相乘：$$x\times y=n!\times (x+y)$$化为 $y$ 的表达式：$$y=\dfrac{n!\times x}{x-n!}$$显然...
题意求所有在树上直径的节点。点数 $N\le 200000$ 。题解我百度谷歌搜了一圈硬是没看到一个像样的题解，去提交记录里面看代码读懂的方法。先跑第一遍 $dfs$ ，记录以 $x$ 为根的子树中深度的最大值 $mx[x]$ 和次大值 $mx2[x]$ ，两者相加再 $+1$ 即为这个子树的直径。然后再跑一遍，对于每个节点 $x$ ，遍历所有子节点 $y$ ，并对子节点向上最大深度 $up...
题意一个有向图，求：至少选多少个起点才可以遍历整个图至少加几条边，能满足从任意一个点出发都能遍历整张图其中点数 $N\le 100$ 。题解显然可以先缩点，然后对题意进行转化：入度为 $0$ 的点的个数加最少的边，让整张图成一个环问题 $1$ 很显然，对于问题 $2$ ，可以把所有入度为 $0$ 和出度为 $0$ 的节点相连，所以答案即为两者的较大值。#include<bits/std...
题意有 $N$ 个长度相同的字符串，问恰好与其中 $K$ 个匹配的字符串有多少个。定义满足如下条件的字符串 $x$ 和 $y$ 为匹配的：$len_x=len_y$$\forall 1\le i\le len_x \ , \ x[i]='?' \ or \ x[i]=y[i]$其中 $N\le 15$ ，字符串长度 $len\le 50$ 。题解看数据范围，可以对 $N$ 进行状压。先预处理...
题意学生排队去食堂吃饭，每个学生都有不同的口味 $\text{T}[]$ 。食堂做第 $1$ 到菜不需要时间，之后在口味为 $x$ 的菜后做口味为 $y$ 的菜花费的时间为 $x\oplus y$ 。为了节省总等待时间，食堂有时会不按排队顺序做，但每个同学最多忍受他后面的 $\text{B}[i]$ 个同学在他之前打饭。求等待总时间的最小值。其中人数 $N\le 1000$ ，$\text{...
题意在 $N\times M$ 的棋盘上放若干个炮，要求不能互相攻击，求方案个数。其中 $N,M\le 100$ 。题解将题意转化一下就是每行每列都不能放超过 $2$ 个棋子，那么可以用 $f[i][j][k]$ 表示前 $i$ 行，有 $j$ 列是有 $1$ 个棋子，有 $k$ 列是有 $2$ 个棋子的合法方案数。那么没有棋子的列数即为 $M-j-k$ 。然后分类讨论。不放继承上一步的状态...
题意动物园的笼子环形排列，每个小朋友能看到从站的位置开始往后共 $5$ 个笼子的动物，每个小朋友都有喜欢和害怕的动物。可以移走一部分笼子。定义每个小朋友是开心的，当且仅当下列条件之一满足：在视线范围内至少有一个喜欢的动物没被移走。在视线范围内至少有一个害怕的动物被移走。求最优方案，使得开心的小朋友尽可能多。其中动物数 $N\le 10000$ ，小朋友个数 $C\le 50000$ 。题解动...
题意在 $N\times M$ 的图中部署炮兵，只有平原才能部署。每个炮兵的攻击范围为上下左右各延申两格，求方案数。其中 $N\le 100,M\le 10$ 。题解跟 玉米田 差不多，但是因为前两行都对当前状态有影响，所以需要多一维。如果直接开 $\text{f}[105][1024][1024]$ 的数组空间就爆了，所以需要预处理每一行合法的状态。可以发现合法的状态最多 $60$ 种，所...
题意在一个 $N\times M$ 的田地里种草，有的地方不能种，要求不能有两块相邻的。求方案数。其中 $N,M\le 12$ 。题解状压dp。把图存下来，每次枚举时判断状态合不合法即可。$$\text{f}[i][j]+=\text{f}[i-1][k]$$#include<bits/stdc++.h>
#define ha 100000000
using namespace...
题意在 $N\times N$ 的棋盘里摆 $k$ 个国王，每个国王可以攻击周围 $8$ 个格子，求国王互不侵犯的摆法有多少种。其中 $N\le 9$ 。题解显然状压dp。可以预处理每一行的合法方案存在 $\text{s}[]$ ，合法方案即没有两个相邻的。用 $\text{f}[i][j][k]$ 表示在第 $i$ 行，合法方案编号为 $j$ ，放了 $k$ 个棋子的方案数。枚举上一行的状...
题意给出一棵树，定义 $\mathrm{dep}[i]$ 为 $i$ 的深度，$\mathrm{LCA}(i,j)$ 为 $i$ 与 $j$ 的最近公共祖先。有形如 $\text{(x y)}$ 的询问，求 $\sum\limits_{i \le x} \text{dep}(\text{LCA}(i,y))^k$ 。其中点数 $N\le 50000$ ，询问数 $M\le 50000$ 。...
题意给出一棵树，定义 $\mathrm{dep}[i]$ 为 $i$ 的深度，$\mathrm{LCA}(i,j)$ 为 $i$ 与 $j$ 的最近公共祖先。有形如 $\text{(l r z)}$ 的询问，求 $\sum\limits_{l\leq i\leq r} \mathrm{dep}[\mathrm{LCA}(i,z)]$ 。其中点数 $N\le 50000$ ，询问数 $M\l...
题意一棵树，每个节点有权值和信仰值。旅行时只在与起点信仰相同的节点停留，并获得权值。有如下操作：单点修改信仰值单点修改权值查询 $(x,y)$ 路径上权值和查询 $(x,y)$ 路径上权值最大值其中节点数 $N\le 100000$ ，操作数 $M\le 100000$ ，宗教个数 $C\le 100000$ 。题解显然每个宗教需要单独维护，但每个宗教开个线段树空间要爆，所以用动态开点线段树...