在n*n的棋盘上面放k个国王，使得他们互相无法攻击，问有多少种摆法。 　　dp[i][j][x]表示前i行，状态为j，总共放了x个国王的方案总数。　　然后简单的转移一下即可。　　当然这样要炸。　　只需要在这之前把每行的合法情况筛选一下即可，这样的情况总数不到100。　　然后就可以了。 ...

 　　有一个n*n(n<=200)的01矩阵，问你是否可以通过交换整行和整列使得左上角到右下角的对角线上的数字都是1。 　　我们发现，题目模型可以转换。　　其实题目就是叫我们求是否存在一些1，这些1所在的行和列互不相同。　　我给一个小小的证明：　　假设我们选出了一个n个点的坐标。　　如果这n个...

 　　这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。注意：选出的k个子矩阵不能相互重叠。　　输入：第一行为n,m,k（1≤n≤100,1≤m≤2,1≤k≤10），接下来n行描述矩阵每行中的每个元素的分值(每个元素的分值的绝对值不超过3276...

 　　现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。　　答案对于31011取模。 　　先考虑错误的prim——　　这个是我的第一感，拿到题目，...

 　　求区间[A,B]中有多少数满足下面的条件。　　条件：该数相邻两位之差不小于2。 　　简单的数位dp。　　一个记忆化dfs就解决了。　　dp[i][j]表示剩余i位数，第i+1位为j的windy数总数。　　太简单了，不会的话自己看代码。1#include<cstring>2#incl...

　　有n个东西，k次扔出来。每次等概率扔出其中一个。　　你可以拿这个东西，但是有条件，得在拿到指定东西之后再拿，否则白拿。　　拿到一个东西，会获得其权值。可以是负数。 　　状压dp跑一发。　　一开始想写正着dp的，因为我觉得这样听挺容易想的。　　然而网上的大牛都说是倒着的。于是我倒着了。　　方程是这样的：　　...

 有n个人，每一个人有一个最恨的人。并且，每一个人有一个权值。一个人不可以和他最恨的人同时被选中。现在请你求出在这n个人中选出一些人，使得其权值和最大。（题解在“心塞史”后面）  注：蒟蒻第一次遇见这种基环树题QAQ。 先看样例。3102203301&nb...

 　　对于任何正整数x，其约数的个数记作g(x)。例如g(1)=1、g(6)=4。如果某个正整数x满足：g(x)>g(i)0<i<x，则称x为反质数。例如，整数1，2，4，6等都是反质数。现在给定一个数N，你能求出不超过N的最大的反质数么？（1<=N<=2,000,000,000...

  UPD(2018-04-01):用Latex重打了公式……把一个整数序列划分成任意连续的段，使得划分出来的每一段的价值和最大。对于某一段，价值的计算公式为 $V=ax^2+bx+c$，其中$x$ 为当前段的数值和。这题是博主大蒟蒻的第一道斜率优化D...

DLX  +  矩阵构建  （两个传送门）对于这一题，矩阵的构建和数独有比较大的不同，常量表也打了很长。我们要精确覆盖的信息有两种：1. 每种形状限用一次2. 每个格子限填一次然后对于每个位置的每种形状的每个形态，建立相应的行即可。常量表贼...

  IOI国历史研究的第一人——JOI教授，最近获得了一份被认为是古代IOI国的住民写下的日记。JOI教授为了通过这份日记来研究古代IOI国的生活，开始着手调查日记中记载的事件。日记中记录了连续N天发生的时间，大约每天发生一件。事件有种类之分。第i天(1<=i<=...

阿申准备报名参加GT考试，准考证号为N位数X1X2….Xn(0<=Xi<=9),他不希望准考证号上出现不吉利的数字。他的不吉利数学A1A2…Am(0<=Ai<=9)有M位，不出现是指X1X2…Xn中没有恰好一段等于A1A2…Am.A1和X1...

去博客园看该题解 　　给出a,b，求出[a,b]中各位数字之和能整除原数的数的个数。　　【约束条件】1≤a≤b≤10^181.所有的位数之和<9*18=1622.所以，dp[i][j][k][m]表示有i位（允许有前导0），数位和为k，模数为m，前i位与模数的模为j的符合条件的数的个数...

原文链接www.cnblogs.com/zhouzhendong/p/BZOJ3153.html直接用splay维护虚子树。细节真多。暂时还不会证明。可能是一个log或者两个log。先咕一咕，等证明它挂了或者证明它是对的或者我弃疗不证明了再更新。UPD(2019-04-10)：弃疗了证不出来不证了。只能证出复杂度上限是...

原文链接https://www.cnblogs.com/zhouzhendong/p/BZOJ2219.html　　求同余方程$x^AequivBpmod{C}$的解的个数，其中$C$为一个奇数。　　$1leqA,Bleq10^9,1leqlfloorC/2floorleq5imes10^8$  &...