[综合] POJ 3544 贪心

这题周末的时候去被虐的时候做过但是那时的题目描述和现在不同； 那题是说把猪送城市，输出按猪的顺序到城市的映射，而POJ的题目却是按城市的顺序输出猪。 明显的，我们可以得到单位的重量的猪送到每个城市挣的钱，这样有个排序。 将猪的重量排序这样又有一个排序。于是乎...重的猪挣大钱，轻的猪挣小钱。按照桶排...

[综合] [U]Packing Rectangles

很久没有做题了，详细统计呢有两个月了。浪费了两个月做了一些无关痛痒的事情。在这里对我的队友说声对不起了...接下来好好做题吧..尽量多做点多感悟一点。 分析： 这题在题目里面说得很清楚了，有6种情况，其实这六种情况只是4个矩形的不同摆法。和他的长宽怎么摆是没有关系的。其中1-5的情况是固定的，因为这...

[综合] [U]The Clocks 枚举

很少去自己构建枚举法，一般遇到题就是直接的DFS,BFS显然这样的编码复杂度很高。太久没有做题了连这道水题都用了我一上午，也对自己的思维有帮助吧，简单的事情复杂化了。实在不是我所希望的啊...调试了N久都没弄出来！ 好吧说说这题的思路： 首先明确的一点就是这题不需要用到DFS，用DFS和BF...

[综合] [U]Arithmetic Progressions 枚举

简单的枚举题。 题意是在一个集合S中求等差数列，输出等差数列的首项与公差。集合S中的元素是两个非负数的平方和。题目给出等差数列的项数，集合元素的范围。 思路：用一个bool数组记录该位置的数是否属于集合S。如果直接枚举公差很容易超时。这里可以减枝，使用一个list数组将bool数组中有效的元素全部保...

[综合] [U]Cow Pedigrees DP

很明显的DP但是要注意的东西很多。不能盲目初始化，另外看的DP课件说的就是DP的特征，最优子结构，最优局部特性。找到DP的关键就在这里。 /* ID:nocows LANG:C++ PROG:nocows */ #include<stdio.h> #defineMAXN201 #def...

[综合] [U]Longest Prefix DP

茅厕顿开的一道DP题！那真是！突然知道了想通了！那编出来的速度真是快啊！ 抓牢DP的特征，构建DP方程~嘿嘿~ /* ID:sevenst4 LANG:C++ PROG:prefix */ #include<stdio.h> #include<iostream> #defi...

[综合] [U]Cow Tours

简单的模拟题，如果是要找周期性的话，真不会啊~.... /* ID:sevenst4 LANG:C++ PROG:ttwo */ #include<stdio.h> usingnamespacestd;charmap[20][20]; voidrotate(int&x,int&...

[综合] [U]2.4.3 Cow Tours

总算是做到了一点点的图论题了~意味着后面的难题要来了 还是觉得自己太懒，不愿去花时间，不愿意相信自己。 这个题呢，有点点意思，本来我的代码超时的，随手改了点小东西，没预料到过的竟然过了~哇哈哈哈~另类的秒掉了。 解题思路很简单，但是求解过程中会绕很多圈子，有点头疼。 枚举不在一个联通图中的两个点，做...

[综合] [U]2.4.4 Bessie Come Home 简单最短路问题

很简单的最短路问题，其中的关键就在于有些农场是没有牛的，这些农场可以走，但不能算在最终答案中，毕竟题中需要的是牛的最短路径。将'Z'点作为源点，进行一次赤裸裸的单源点最短路径，就可以得出答案了。代码中我用一个hash函数把所有的字母下标点都规整到[1,52]这个范围内。 /* ID:sevenst...

[综合] [U]2.4.5 Fractions to Decimals 简单的语言控制题

简单的语言控制，考察代码的熟悉程度。 代码比较丑陋，但是能ac...... /* ID:sevenst4 LANG:C++ PROG:fracdec */ #include<stdio.h> usingnamespacestd;structnode {intnum;intleft; }...

[综合] [U]3.1.1 Agri-Net 简单的最小生成树问题Ford

拿以前的代码过来秒掉了，这代码可以作为一块好的模板了....... /* ID:sevenst4 LANG:C++ PROG:agrinet */ #include<stdio.h> usingnamespacestd;intmain() {freopen("agrinet.in","...

[综合] [U]3.1.2 Score Inflation 赤裸裸的多重背包问题

如题: 前段时间看了点背包九讲，没能沉住气看完，后面还是要好好加工一下啊。这种背包水题还是能秒掉的。 /* ID:sevenst4 LANG:C++ PROG:inflate */ #include<stdio.h> #defineMAXT10000 #defineMAXP10000 ...

[综合] [U]3.1.5 Contact 小技巧题

刚开始做这题的时候思路错了，把他想成字符串模式匹配题了。通过构建长度在[A,B]之间的字符串，然后再对主字符串进行模式匹配，想想要用kmp算法，对于这个我还不是很懂....打算好好学习一下kmp,后来估计了一下时间，发现必须超时。 转而一想： 其实需要的只是在主字符串中的一些子集，通过直接遍历主字符...

[综合] [U]3.1.6 Stamps 会错意的DP题

3章第一节有道题敲不出来啊~~~没办法，只能把后面的题先给敲咯~ 这个题呢... 首先本巨菜想了一个很傻很水很烂的DP方程。使得自己的程序果断崩了... 开了一个10001*200的二维boolean数组，[面额][张数]这样来DP，因为最大的面额只有10000，再通过循环数组的方法，勉强使得空间...

[综合] [U]3.2.1 Factorials 有点点意思的水题

以前在XTU的比赛中做过这个题，当时没过，到后面还是用了个猥琐的方法过的。 可能是不记得了当时用的高精度法没过，这次看到这题直接采用赤裸裸的高精度，结果...在本地跑那速度.....==|||| 于是乎，还是采用了猥琐的方法；但是为什么每次mod100000呢？？而每次mod10000就WA呢？ 解...

[综合] [U]3.2.2 Stringsobits 组合，递推

很快就发现了这题的递推特性。简直是赤裸裸啊~ 定义一个数组([串长度][串中'1'的个数]=种类数)这就是一个排列啊~ 用一个简单的递推方程求解出来C(n,i)=C(n-1,i)+C(n-1,i-1); 然后从首位n开始判断,∑C[n-1][i](i∈[0,l]) 若和大于等于当前的第k个数则说明，...

[综合] [U]3.2.3 Spinning Wheels 模拟

用的最简单的方法过的,赤裸裸的模拟题。 估计一下时间复杂度，发现模拟可以做，果断模拟了，不过模拟得不好，太慢了。最好是学会bitset类,这样省空间。用bool要用掉8位.用360位的bitset可以直接判断了，不需要每次扫扫扫... 代码果断很丑: /* ID:bysen LANG:C++ PR...

[综合] [U]3.2.4 Feed Ratios 枚举

简答的枚举题，其他的不多说了.... 切掉之后看了下题解，复习了一遍高斯消元法和克莱姆法则。发现还是数学方法好啊。 虽然枚举很省coding时间,于是乎，抱着节省code时间的态度,决定开始用模板类..... 克莱姆法则有几条重要的 1.非齐次线性方程，系数矩阵D=0时，有无穷多解。D≠0时，有唯一...

[综合] [U]3.2.5 Magic Squares 康托展开+BFS

这题和八数码十分相似，或许是我的遗留问题吧....敲完总是不过，各种错误。迟迟下不了手的原因就在于对空间的把握问题。要节约空间就必须设计一个好的hash函数,不然时空开销大。关键在于哈希怎么弄了？八位数--->87654321如果采用这么大的空间，空间消耗太大，许多内存都没采用，不行... 后...

[综合] [POJ]1077 Eight 八数码:康托展开+BFS

嗯~很久以前没敲过的题，当时不懂状态压缩，不懂A*。因而没过... 现在用的康托展开+普通的BFS还是过了360ms也算是一个进步吧~ A*现在还是没有勇气去写...加油！时间给我的不多了！~ （用C++TLE了...改为G++就过了...） Code： #include<stdio.h&g...