题目链接：Palindrome - HDU 6230 - Virtual Judge (vjudge.net) 从这里进也可以：Problem - 6230 (hdu.edu.cn) 题目大意 / Problem 有多组样例。 每组样例给一个字符串，问有多少个“一个半回文串”，一个半回文串的定义是，第一个回文串的右端点是第二个回文串的中心，第一个回文串的中心是第二个回文串的端点。 比如abcbab […]

题目传送门：Problem - 7224 (hdu.edu.cn) 题目 / Problem 在一条横轴上有n个点，每两个相邻的点有一条边，一共n-1条边，每个点上有一个权值a，走到一个点时就可以将某个点上的a所有质因子放入背包中，每条边有一个质数权值pri，只有当pri存在于当前背包中时才能通过这条边。 有M次询问，问能否从x走到y。 思路 / Thought 这道题容易想到用两个数组 arra […]

题目传送门：Problem - 7170 (hdu.edu.cn) 题意 / Problem 有N个包裹，可以在[l, r]的时间内去取，一次最多取k个，问最少取多少次可以取完所有包裹。 思路 / Thought 贪心的思想，确实很难想，但是题目做多了也容易想到，区间先排序。 将区间分两种方法排序，a数组根据r排序，b数组根据排序。 为使得取包裹次数尽可能少，就应该每次取包裹时间尽可能晚（因为这样 […]

题目链接：Problem - 7173 (hdu.edu.cn) 题意 / Problem 给定2个排列，P、Q，长度为N，给定一个长度为2N的序列S，问能够通过以下方法构造出S： 序列Q初始为空，每次从P或Q的最左侧选出一个数字放到序列Q的最右侧。 问构造的方案数，只要其中一步不同就算作不同方案。 方法一（DFS + 记忆化搜索）/ Solution1 这个应该不是正解，因为复杂度太离谱了。 这 […]

题目链接：Problem - 7139 (hdu.edu.cn) 题目 / Problem 给定一个N x M的地图和K堵墙（N, M, K <= 15），注意这里的墙在方格的边缘而非方格内，需要进行移动判定。 给一个起点(sx, sy)和终点(fx, fy)。 问最少移除几道墙可以从起点走到终点。 思路 / Thought 做题往往从数据范围小的变量入手，比如本题的K。 因为K很小，2的1 […]

题目链接：Problem - 7152 (hdu.edu.cn) 题目 / Problem 有T个测试用例。 给定一个长度为N的数组，进行Q次操作。 每次操作有两种模式，模式1：选择一个区间[l, r]，将其复制一份并插入到这个区间右端点的后面，大于N的部分自动剔除。模式2：查询当前数组第x位的元素。 求所有操作模式2的查询结果的异或和。 思路 / Thought 我直呼牛逼！ 首先不难想到，当进 […]

题目链接：Problem - 7140 (hdu.edu.cn) 题目 / Problem 有一个容量为M的背包，有N个物品（体积v，价值w），请问怎样选择可以使得物品恰好装满背包并使得价值的异或和最大。求出最大的异或和。 思路 / Thought 不难想到是一道dp题，状态dp[i][j][k]表示到i个物品为止，异或和为j，体积为k是否能够达到，也就是说dp的值为0或1。 但是这样更新出结果的 […]

题目传送门：Problem - 3555 (hdu.edu.cn) 题目大意 给定一个N，求[1, N]范围内的数字转换形成的字符串中包含"49"的数字。 (1 <= N <= 2^63-1) 思路 因为数据太大了，所以直接前缀和肯定行不通，所以需要数位dp。 典型的数位dp模板题。 代码