思路： 没特殊声明，在本题0算偶数，不要把前导零算进来了 数位入门题，我又写了一堆，开始不知道算不算，就瞎写了一个，结果答案大了，如何算上又把前导零算上了，特判前导零但为了少写一个参数直接硬写，然后写错了。时因为是两遍，以为是一遍，然后出现了不能解释的结果。 把每个数位是否出现状压到的二进制位里，一个整数的二进制位通过异或来表示某个数位出现的次数是奇数次还是偶数次。 ，表示当前为第len位，出现的数位的集合cnt，每个数位出现次数奇偶的集合pos，表示len个数位使得cnt里的数位合法或者使新添的数位合法的方案数，这是唯一的。 Code： #include<iostream> #i...

思路：这个数位卡我时间又卡我空间，时间和空间限制都很小，时间就500ms。  我想通过再开一个数组记录访问过的状态是否与本次输入有关，来避免每次都要初始化数组，同时又不用多开一维（会爆空间，），即便如此还是会超时，因为它有组数据，所以如果每次都重新算一遍的话，铁定超时，与是否初始化的时间开销无关。 然后参考了一位博主的博客，我数位白学了。 对于我解这题固有的思路而言，"判断是否"并没有体现在的状态中，所以这样产生的值是依赖于的，仅能应用在当前数据上，如果数据量大就会。 但是完全可以采取更优的方案消除状态与输入的相关性。（无论你取什么值，都是一个常量，永远不会改变。）以前也有过消除状态与输入的相...

思路：简单的数位取2表示出现过13，取1表示当前位是1，否则取0 状态：，长度为，当前数值的值为，状态是，这个状态是能保证结果唯一的 Code： #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<queue> #include <vector> #include<map> #include<set> #include<utility&g...

题意：有一个旅行家计划乘马车旅行。他所在的国家共有m个城市，在城市之间有p条道路相连接。从某个城市沿着某条道路到相邻的城市需要乘坐马车。而乘坐马车需要使用车票，每用一张车票只可以通过一条道路。每张车票上都记有马的匹数，从一个城市移动到另一个城市的所需时间等于城市之间道路的长度除以马的数量的结果。这位旅行家一共有n张车票，第i张车票上的马的匹数是ti.一张车票只能用一次，并且换乘所需时间可以忽略。求从城市a到城市b所需要的最短时间。如果无法到达城市b输出"Impossible"。 思路：虽然可以把城市当作顶点，道路看成边建图，但是由于车票相关的限制，无法直接用算法求解。应为比较小，可以考虑一下状...

题意：一行给出科目名称，截止时间，需要的时间，超出截止时间多久就扣多少分，求一个做作业的顺序使扣的分最少，并按字典序打印顺序。科目的名称是按字典序给出的 思路：状压入门二进制位表示一个数有没有被取 指的是已做作业结合的上一个集合，指由上一个集合到集合做的是什么作业，表示到集合已经过了多久，就是做了集合的作业会扣的最少的分。 一个细节点是，每次优先遍历字典序大的作业去得到的状态，这样保证前面选择的作业字典序最小 Code： #include<iostream> #include<cstdio> #include<cstring> #include<cma...

题意：n 个城市已及 m 条路 以及对应路费 c，要求遍历所有城市最少的路费，每个城市不能超过2次。 思路：三进制位表示一个城市被走过的次数，三进制没有位运算，可以预处理三进制位每一位的权值以及每个十进制数的三进制表示。状态方程：表示访问中所有的点后最后到达城市（感觉紫书上对旅行商的解析不太好）转移方程： Code: #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<queue&gt...

问题描述：给定一个给顶点组成的带权有向图的距离矩阵。要求从顶点出发，经过每个顶点恰好一次后在回到顶点.问所经过的边的总权重的最小值是多少？   所有可能的路线共有种，尽管很小了，仍然无法枚举每一种情况。用跑遍求解不能保证求出的最小值经过了所有的城市。 方法一：记忆化搜索 ，表示从出发访问剩余所有顶点的最小花费，每个元数的选取与否对应到的二进制位里初始化：，使得最终结果都回到了起点.状态方程中的一维表示的一个集合，对于不是整数（不是单纯的一个数）的情况，很多时候很难确定一个合式的递推顺序，因此使用记忆化搜索就可以避免这个问题。 记忆化搜索真的妙，思路清晰，很好懂也很好写。 部分代码： int n...

题意：定义一个数若以某个数字作为支点，左右力矩（到支点的距离乘数字大小）相等，则称这个数是平衡的。求区间中有多少个平衡数。比如，以第二位为支点，左边的力矩是，右边的力矩是 思路：这道入门题是我大意了（锤子入门题，不能秒解的题还是入门题？） 这道题求的答案时需记忆化搜索次，是的位数 ，表示当前是第位，支点是第位，平衡值为，这个状态是能保证结果唯一的 看到状态就很明确要怎么做了，但是为什么这么做？可以保证的是，某个数如果是平衡数，有且仅有一个支点（0除外）所以以每一位当支点算出来的总答案是不会重的（0除外） 比较特殊，不管以哪一位当支点它都是平衡数，所以总答案最后减去多算的0就是最终答案了。 心路...

题意：求以内有多少个数的二进制位里的数量大于的数量，数据范围。 思路：把转为二进制，记忆化搜索二进制数，（写数位一定要看清参数，参数写反把自己搞蒙了，血亏）。二进制的前导零是无效的，当前的长度、出现的次数以及出现的次数三个状态才能保证结果一样（写这么多题了我居然没加出现的次数这个状态） Code： #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<queue> #include...

题意：找里有多少个数包含了. 思路：典型的特定数字问题，数位入门题。 ,表示第位，当前位是不是，是否出现了.刚开始没有加第三维，一直对不上案例，后面发现只有两维的保存的结果不一定能通用，比如: 前两个可以是同一个结果，但第三个和前两个不一样，可以任意取。 Code： #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e3+7; inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch &...

题意：题目意思就是给你L到R区间，和一个数字K，然后让你求L到R区间之内满足最长上升子序列长度为K的数字有多少个；比如就是上升子序列长为的数字 思路： 的状态应该包含长度、状态、以及题目的要求（刚开始没考虑到以后每组的答案受到前面答案的影响，没有多开一维数组存就错了）最长上升子序列有个的解法，数组存最长上升子序列对应有哪些点，这不是它主要的作用，遍历时我们需要把出现在中可能性更大的点放进去，所以数组存的有些点不一定是最长上升子序列对应的点，但是数组的长度就是的长度。考虑到中最多只有个数字，所以用将数组状压到二进制，表示没存这个数，表示存了这个数。用位运算模拟数组的操作，只是这里不能用的，所以这...

思路：数位的一道入门题 ，表示第位，第是否是的结果。 Code： #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e3+7; inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); } while (ch >= 48 && ch &lt...

思路： 1.与前面的题不同的是，这是一类无修改统计链信息的问题2.一个串能重排形成是回文串当且仅当其字符数量均为偶数或者恰好有一个奇数，实际上对于任意的一条路径我们只关注其任意字符的奇偶性3.因为只有个字符，所以可以用二进制状压到4，表示节点到根结点的异或值5.假设现在我们处理以为根的子树，如果一条链从开始，一直连到他的某一个子树中的点，贪心地，这个点的深度一定是所有满足条件的点中最深的5.维护最长的路径的长度6.以为根的子树中，考虑怎么更新：(1)从儿子的子树中来,是所有的儿子(2)和子树中的某个点连接起来(3)考虑跨子树组合成一条链7，两个点的简单路符合要求一定满足下列条件之一：(1)(2...

思路： 1.题目要求维护的颜色数量，因此和模板类似的考虑什么情况下会对答案产生贡献2.维护颜色出现的次数，维护出现次数大于的颜色种类数3.显然出现次数的颜色都对有贡献4.颜色每次出现，必有5.将每次查询用容器存储，方便离线操作复杂度： MyCode: #include<bits/stdc++.h> using namespace std; const int maxn=2e5+7,maxm=4e5+7; typedef long long ll; inline ll read(){ ll s = 0, w = 1; char ch = getchar(); while (ch &l...