[综合] 百练 2815 城堡问题

百练2815城堡问题 #include<iostream> #include<cstdio> #include<queue> #include<cstring> #include<algorithm> usingnamespacestd...

[综合] 百练 4124 海贼王之伟大航路

百练4124海贼王之伟大航路 #include<iostream> #include<cstdio> #include<queue> #include<cmath> #include<cstring> #include<algori...

[综合] PKU ACM/ICPC暑假训练班总结

1Day：动态规划 动态规划考虑三点：状态定义，如何决策，边界条件 该状态选取是否可行：是否是最优子结构，是否有“无后效性”(此状态后的状态递推与如何达成此状态无关) 如该状态无法递推或有漏解：加一维状态细化问题分类，即使状态更复杂 遇到空间时间不足：滚动数组，状态空间压缩(集合表示等) 两种实现方...

[综合] 百练 4130 Saving Tang Monk [BFS+优先队列+状态压缩]

百练题目地址 判重3个状态就够了位置+钥匙 除了#位置，其他位置都可以经过多次 注意钥匙数可以为零 因为打蛇要time+2，所以用优先队列 蛇的数量<=5,所以1<<5的数就足够保存蛇的状态了 #include<iostream> #include<cstdio...

[综合] POJ 2524 宗教信仰 .

题目地址 水题求有多少个集合 #include<iostream> #include<cstdio> #include<queue> #include<map> #include<vector> #include<cctype>...

[综合] POJ 2492 A Bug's Life .

POJ1182食物链*的简易版本 此题目POJ题目地址 这类问题共同点就是1）分为固定几类，2）有类似一个环男-->女-->男 要点就是：1）思考集合与集合合并的时候两个根的关系 2）结点压缩的时候，结点与根的关系怎么根据边递推上去 #include<iostream> ...

[综合] POJ 1703 Find them, Catch them .

题目地址 #include<iostream> #include<cstdio> #include<queue> #include<map> #include<vector> #include<cctype> #includ...

[综合] POJ 1861 Network .

最最基础题 百练OJ有毒POJ是对的，在百练怎么都不对 题目地址 #include<iostream> #include<cstdio> #include<queue> #include<map> #include<vector> #in...

[综合] 百练 2560 Freckles .

题目地址 #include<iostream> #include<cstdio> #include<queue> #include<cmath> #include<map> #include<vector> #include&...

[综合] POJ 2236 Wireless Network .

题目地址 用集合表示是否可以相连接，一个集合里的都是可以互相连接的 当一个节点修好后，更新能与它相连的点可以通过遍历所有点 #include<iostream> #include<cstdio> #include<queue> #include<cmat...

[综合] POJ 1456 Supermarket [贪心+并查集]

题目地址 贪心：优先选利益最大的商品，从deadline向前推直到都放不了再选下一个商品利益最大的 关键是判断哪一些日子不能再放了，最简单的方法就是一个数组+一个for循环判断 但更快的是用并查集，p=find(deadline)当p>0，p就是可以放的日子否则放不了;放好后更新parent...

[综合] POJ 3264 Balanced Lineup .

题目地址 最基础的线段树题目，很明显的区间操作，所以第一时间要想到线段树 用线段树解题，关键是要想清楚每个节点要存哪些信息（当然区间起终点，以及左右子节点指针是必须的）， 以及这些信息如何高效更新，维护，查询。不要一更新就更新到叶子节点，那样更新效率最坏就可能变成O(n)的了。 #include...

[综合] POJ 3468 A Simple Problem with Integers -

题目地址 一般求和首先想到就是每个结点保存sum的值代表这个区间的和 那么求区间的和就是找到[s,e]这个区间的结点并返回该sum值，复杂度为O(logn) 但是这样子有个不好的地方就是假如最坏的情况下把1~n区间都加c值，那么每个1~n的叶子结点都要遍历到且+c,则时间复杂度就为O(nlogn) ...

[综合] POJ 2528 Mayor's posters -

题目地址 要用到离散化 一直RuntimeError发现原因是数组开在main()函数里应该是开不下导致的 还有个问题： boolb1=post(root->pLeft,s,mid);boolb2=post(root->pRight,mid+1,e);covered=b1||b2; 竟...

[综合] POJ 1151 Atlantis *

题目地址 一直WA一个一个字符比对正确代码，想吐槽的是答案输出只能%f！！！woc 还有犯了一些小错误比如坐标值y用int保存了 从左到右每个x值，把y的坐标分为n-1个区间，那么就转化为线段树了 #include<iostream> #include<cstdio> ...

[综合] POJ 3321 Apple Tree *

改变某点值，计算和很像树状数组 很难想到的是如何把它变为区间 具体做法是做一次dfs，记下每个节点的开始时间Start[i]和结束时间End[i]，那么对于i节点的所有子孙的开始时间和结束时间都应位于Start[i]和End[i]之间然后用树状数组C统计Start[i]到End[i]之间的附加苹果...

[综合] Trie图入门题

题目： 给N个模式串，每个不超过个字符，再给M个句子，句子长度< 100判断每个句子里是否包含模式串 N<10,M<10,字符都是小写字母 58 abcde defg cdke ab f abcdkef abkef bcd bca add ab qab f #include&l...

[综合] POJ 2007 Scrambled Polygon .

题目地址 就是把点逆时针顺序排序 把每个点看成从原点出发的向量 利用叉积逆时针转180°以内为正的性质就能逆时针将点排序了 #include<iostream> #include<cstdio> #include<vector> #include<algo...

[综合] 矢量表示及其计算

#include<iostream> #include<cstdio> #include<cmath> usingnamespacestd; structCVector{//向量doublex,y;CVector(doublex,doubley):x(x),y(y...

[综合] 点线表示及其计算

#include<iostream> #include<cstdio> #include<cmath> usingnamespacestd; structCVector{//向量doublex,y;CVector(doublex,doubley):x(x),y(y...