GreenHatHGのBlog

HDU1024-Max Sum Plus Plus HDU1024 解析题意在n个数中选出m组数, 每组数连续且不能相交,使得这m组的和是所有m组数中最大的。 每组数也可以叫做每一段 例如: 122 6 -1 4 -2 3 -2 3选两组数,当我们选{4,-2,3},{3}这两组数时可得到最大的和8 DP参考： https://blog.csdn.net/zuzhiang/article/details/78450380 定义二维数组dp，dp[i][j]，表示前 j 项所构成 i 子段的最大和，且必须包含着第j项，即以第j项结尾 求dp[i][j]，有两种情况: dp[i][j] = dp[i][j-1]+a[j]，把第j项融合到第 j-1 项的子段中，子段数没变 dp[i][j] = dp[i-1][t]+a[j]（i-1<= t<j）,把第 j 项作为单独的一个子段，然后找一下i-1个子段时，最大的和，然后加上a[ j ] ，字段数由i-1变成i 然后比较上面两种情况，取最大的。即 dp[i][j] = max(dp[i] ...

HDU1231最大连续子序列 HDU1231 解析（转移方程好求，但是栽在了求位置上面，后来才想起是后往前推。） 转移方程 dp[i]表示以i结尾的最大连续子序列的和 1状态转移方程：dp[i] = max(dp[i - 1] + num[i],num[i]) 记录位置 根据转移方程求最大值，这样就能找到最大连续子序列的最后一个元素，然后根据这个位置再向前找起始位置即可 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556/*2019-04-14 11:46:05124MS 1628K*/#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int MAXN = 1e5+10;const int INF = 0x3f3f3f3f;int arr[MAXN];int dp[MAXN];int ...

HDU1217-Arbitrage HDU12171Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Problem Description Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that 1 US Dollar buys 0.5 British pound, 1 British pound buys 10.0 French francs, and 1 French franc buys 0.21 US dollar. Then, by converting currencies, a clever trader can start with 1 US dollar and ...

HDU1518—-Square 题目链接：HDU1518 分析参考：https://blog.csdn.net/guodongxiaren/article/details/23126997 题意就是好多棍子，看能不能拼成正方形。主要注意的有几点： 所有棍子都要用到，不能剩余 输入已经保证大于4根棍子了。所以无需判断可能小于3根棍子的情况 棍长的总数首先要是4的倍数，才能进行。否则直接输出 “no” 当前面前提满足以后，再满足3 根棍子拼好，就完工了。最后一根一定能拼好。 解法就是运用dfs方法不断尝试，当一个结果不符合题意时，就回溯到上一个结果。 此外，我们还可以提前对数据进行排序，将数据从大到小排序，以提高查找速率。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475/*421MS 1320K2019-04-12 22:40:37*/#includ ...

Dijkstra—链式向前星—快速幂 题目链接：牛客283H-图论一顿套模版 解析题目求的是乘积，但是又因为W一定是2的整数次幂。所以我们可以将乘法换为加法，2^x * 2^y = 2^(x+y) 只要我们求出x+y的最小值，那么对应其答案也是最小值。算2^x可以运用快速幂解决 所以总体上我们可以用dij+优先队列优化+链式向前星+快速幂解决 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107/*运行时间(ms) 使用内存(KB) 代码长度 使用语言 提交时间62 4188 1543 C++ 2019-03-28 10:53:59*/#include <cstdi ...

邻接矩阵，邻接表，链式向前星 参考： ACM图论之存图方式 邻接矩阵邻接矩阵是三种存图方式中最简单也最为暴力的一种存图方式了。 存图思想使用一个矩阵来描述一个图，对于矩阵的第i行第j列的值，表示编号为i的顶点到编号为j的顶点的权值 代码实现对于邻接矩阵来说，它的代码实现都十分简单，二维数组就可以了。 1234567891011121314151617181920#include <cstring>//最大顶点数const int MAXV = 1e3;//邻接矩阵,Map[i][j]:顶点i到顶点j的权值int Map[MAXV][MAXV];memset(Map, 0, sizeof(Map));// 增加边// 新增顶点`i`到顶点`j`的边，权值为`w`Map[i][j] = w;// 删除边// 删除顶点`i`到顶点`j`的边Map[i][j] = 0;// 查询边// 查询顶点`i`到顶点`j`的边权Map[i][j]; 优点使用邻接矩阵来进行建图存图有以下优点 简单易学 这个肯定不用多说，哪怕是没学过线性代数的童鞋也很容易理解这样的存图方式。 代码易写， ...

洛谷P2819图的m着色问题, POJ 1129 Channel Allocation 模板题—洛谷P2819图的m着色问题 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354/*代码 C++11，0.77KB提交时间 2019-04-04 15:54:31耗时/内存277ms, 888KB*/#include <cstdio>using namespace std;const int MAXN = 1E3;bool gra[MAXN][MAXN] = {false}; //判断两个点是否连通int color[MAXN] = {0}; //存每个点已经涂成的颜色,值为0则是没有被涂色int n, k, m, e1, e2, ans = 0;bool check(int num){ for(int i = 1; i <= num; i++) { ...

L2-016 愿天下有情人都是失散多年的兄妹 L2-016 愿天下有情人都是失散多年的兄妹 思路找到并标记两人的5代以内祖先，如果发现已标记过的祖先，就说明两人有共同祖先 存储和查找输入的数据包含一个人的ID、性别和父母的ID，为了方便可以就用一个结构体来存储数据，声明一个结构体数组， 其数组下标代表这个人的id，结构体属性有父母id。另外开辟一个数组空间来保存性别，一个数组空间保存标记信息。 坑点测试数据里面可能会判断某个人的父亲，或者母亲和某个人是否能结婚，所以也要标记父母的性别 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566#include <cstdio>#include <cstring>using namespace std;const int MAXN = 100005;//sex[i]:编号为i的人的性别，vis[i]：编号为i的人是否已经标记，f ...

FZU-1649-PrimeNumberOrNot-大素数判断 题目FZU-1649 思路普通素数筛法不能用于大数。此时只能用别的算法——米勒-拉宾素数测试 我们知道对于某个素数P,由费马定理得 a^p \ mod \ p \equiv a于是就有了希望使用这个来判断某个p是否是素数 但$a^p \ mod \ p \equiv a$不是p是素数的充分条件 存在有名但是极端稀少的Carmichael数，它们不是素数但是满足费马小定理，比如561, 1105, 1729, 2465, 2821,6601, 8911, 10585, 15841, 29341…。 所以如果我们只是随机的从1和p-1之间（这里p是一个待判断的正整数）取一个数a计算$a^p \ mod \ p \equiv a$的值，如果该值不是a，那么我们100%肯定p不是素数。但如果$a^p \ mod \ p \equiv a$的值是a，p可能是素数也可能不是。 费马小定理的一个特殊情况，如果n是一个素数，那么phi(n)=n-1，而任意不大于n的数a都与n互质，于是费马小定理的推论为： a^{n-1}=1\ m ...

CodeForces-236B-求因子个数 题目CodeForces-236B 题目大意先算出q=i*j*k，然后算q的因子的个数，最后把这个因子和加起来mod上一个数 记录下求解因子个数的办法 123456789101112131415161718192021222324252627282930313233343536373839404142434445/*2019-03-15 15:00:3592ms*/#include <cstdio>using namespace std;const int MAXN = 1e6 + 10;const int MOD = 1073741824;int arr[MAXN];void init(){ arr[1] = 1; for(int i = 2; i < MAXN; i++) //初始化，每一个数最少有两个因子，１和它本身 arr[i] = 2; //i*j得到一个数，代表这个数有因i和j，如果i,j相等,因子个数+1,否则+2 for(int i = 2; i*i < MAXN; i++) ...