题意在一个$N$行$M$列的棋盘上放若干个炮（可以是$0$个），使得没有一个炮可以攻击到另一个炮，请问有多少种放置方法。输出方案数模$9999973$的结果数据范围：$1 \le n,m \le 100$题解首先，每一行或每一列的炮一定小于等于$2$由于每一行的炮可以直接进行限制，因此需要记录每一行的炮的数量考虑用 $f[i][j][k]$ 表示前$i$行中有$1$个炮的列有$j$个，有$2...

题意给出数列$a,b$，可交换各个数列中相邻的数，求最小的交换次数，使得$$\sum(a_i-b_i)^2$$最小，答案对$99999997$取模数据范围：$1 \le n \le 1000000$题解对目标式化简$$ \begin{aligned} \sum(a_i-b_i)^2 &= \sum(a_i^2-2a_ib_i+b_i^2) \\ &= \sum a_i^2 +...

题意：在 $ N×N $ 的棋盘里面放 $ K $ 个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 $ 8 $ 个格子。数据范围： $ 1 \le N \le 9,0 \le K \le N * N $题解：算法：状压dp使用 $stt[]$ 记录每一种状态，二进制下从低位到高位记录此行从左到右是否放置国王。并且由于有...

题意多重背包数据范围：$0 \le w \le 4 \cdot 10^4,1 \le n \le 100$题解设$w$为价值，$v$为体积，$c$为数量多重背包的状态转移方程为$$f[i][j]=\max(f[i-1][j-kv]+kw)$$其中$k \in [1,c]$由于$i$一定从$i-1$转移而来，所以第一维可以去掉$$f[j]=\max(f[j-kv]+kw)$$但是这样$dp$的...

题意给出一个$01$串，第$i$位上有$p_i$的概率为$1$，否则为$0$极长的连续$x$个$1$贡献为$x^3$，求期望总贡献数据范围：$1 \le N \le 100000$题解若前面已有$x$个连续$1$，当前位也为$1$，增加的贡献为$$(x+1)^3-x^3=3x^2+3x+1$$现在我们加上概率，以$f[i]$表示前$i$位的期望，但是此时我们无法表示$2$次方项和$1$次方项...

题意最短路计数数据范围：$1 \le n \le 2000,0 \le m \le n(n-1)$题解在跑最短路的同时维护一个$cnt[i]$即可若能够更新$dis[v]$，则$cnt[v]=cnt[u]$若相等，则$cnt[v]+=cnt[u]$代码：#include<iostream> #include<cstdio> #include<cstring>...

题意：求不大于 $n$ 的最大高合成数。高合成数指一个数，任何比它小的自然数的因子数目均比这个数的因子数目少。数据范围： $1 \le N \le 2000000000$题解：对于一个数 $x$ ，由算术基本定理$$x=\prod p_i^{a_i}$$则其因子数目为$$\prod (a_i+1)$$ 根据贪心，在因子数目数目一定时，$x$ 应为最小，此时 $x$ 才为高合成数。不妨设 $p...