庆祝第100篇文章完成！题意一棵有边权的树，有的节点是转播站，有的节点是用户节点。要让用户看到电视，代价为根节点到当前用户节点的路径和，重复的路径不重新计算。每个用户可以支付一定的钱。求在不亏本的情况下，最多可以让多少个用户看到电视。其中点数 $N\le 3000$ 。题解树上背包的裸题。用 $f[x][i]$ 表示在以 $x$ 节点为根的子树中选 $i$ 个用户的最大收益。转移方程式为：$...
题意给出 $S$ ，求所有正约数之和 $=S$ 的数。数据组数 $k\le 100$ ， $S\le 2\times 10^{9}$ 。题解约数和为：$$\begin{matrix} \prod_{i=1}^n \end{matrix}\begin{matrix} \sum_{j=0}^{a_i} {p_i}^j \end{matrix}$$可以先预处理 $\le \sqrt{S}$ 的质数...
题意在树上放一些山贼集团的分部，每个分部可以收取根节点到它路径上所有节点的保护费。在节点 $i$ 建立分部 $j$ 花费 $s[i][j]$ 。对于每一个节点，如果它被多个分部收保护费，就可能产生收益或损失。求最优的放置方法，可以得到最大利润。其中点数 $N\le 100$ ，分部个数 $P\le 12$ 。题解看到 $P$ 的范围，显然可以对节点上放置分部的状态进行状压。因为每个分部收取的...
题意给出 $A,B$ ，求 $gcd(A,B)$ 。其中 $A,B\le 10^{3000}$ 。题解数据范围很大，显然要用二进制求 $gcd$ 。其它都是板子。#include<bits/stdc++.h>
using namespace std;
struct bigint {
int len,s[3005];
bigint() { memset(s,0,...
一年前做了然而却还是不会系列。题意给出 $a_0,a_1,b_0,b_1$ ，需要求 $x$ ，使得$$\begin{cases} gcd(x,a_0)=a_1 \\ lcm(x,b_0)=b_1 \end{cases}$$题解显然，对于$$gcd(x,y)=k$$我们可以将其化为$$gcd(\dfrac{x}{k},\dfrac{y}{k})=1$$又因为$$lcm(x,y)=k$$可以化...
题意一个有点权和边权的无向图，求 所有点权和为 $0$ 的子图 的最小生成树的权值和。其中点数 $N\le 16$ 。题解看了半天题才得到上面的题意，看到 $N\le 16$ ，显然是状压。用 $f[id]$ 表示当前点集状态为 $id$ 时的最优解，当 $i$ 和 $j$ 状态内的点权和为 $0$ 时，转移方程式很显然：$$f[i|j]=f[i]+\text{Kruskal}(j)$$对每...
时隔一年（差两天）来做还是不会做，甚至连我当时写的是什么都没看懂，这充分凸显了写博客的必要性。题意求 $\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$ 种，所...