HDOJ Monthly 2009.01 Problem "light"
http://acm.hdu.edu.cn/showproblem.php?pid=3275
这个题目比较简单。。。
我刚开始写的解题报告里面说：
- If the first lantern is off then install a switch to change the states of first k lanterns.
- Let the second lantern be the first one and repeat Step 1 until there are less than k lanterns.
- If all of the remaining lanterns are on then output the answer else output “-1”.
- Find the states of one lantern.
- Change all states of an interval.
这里说的线段树其实就是区间覆盖那种，统计一个点的奇偶值就查看这个点被覆盖的总数就好了。
因为这里的区间的大小总是K，所以其实用不着线段树，线性扫描就好了。。。
POJ Monthly Contest - 2010.1.24 - Problem A "Cake"
http://poj.grids.cn/contest/1774/problem-A/
这个题目是我出的，题意写的有点晦涩-.-!
不过简单表述起来还是挺简单的。
就是在一个圆上进行切割，每一次切割都要跨过整个圆。然后需要检查切割线，检查切割线的方法就是碰触切割出来的每一个小块。
说白了就是小块为点，相邻的小块连边，然后问进行点涂色，使得每一个边的两个端点至少有一个是涂色过了的。
解法：
通过一系列比较麻烦的几何处理之后，所求出来的图是一个二分图。然后求得二分匹配就是答案。
关于这个图是二分图的证明也有比较形象的理解，就是这个图是明显没有奇环的，所以就是二分图咯。。。
以前出的ACM的题目
在此记录一下：）
http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1352 一道简单图论题，求奇偶最短路。 没什么意思的一个题目，用来送分的。 难度： 简单 http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1353 一个搜索题，要删掉最少的点使得没有三点共线。 一个不是很难的搜索，但是非常有代表性，有很多通用性质的解法，这个题目是我写dlx论文的搜索的最初使的模型。这个题目的比较好的做法是反过来然后求可以最多找出多少点，使得没有三点共线。 难度： 中等 http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1355 无聊的数据结构题 难度： 中等 http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1361 求第k大数，我感觉是一个很难的数据结构题。 这个题目杭电oj添加的版本有问题。时间还有内存等等都没有控制好，我们oj的是正确的。 这是因为当时杭电刘老师加题目的时候不是我给的数据。。。他们拿到的数据是很老的版本的。。。 此题需要nlogn算法。 难度： 难 还有一个题目，因为有spj所以没有加到oj上，题意很简单，就是求一个n皇后的解。但是棋盘有一些限制，有一些格子是不能放皇后的。 算法就是dancing links… 难度： 难 http://acm.hdu.edu.cn/showproblem.php?pid=2692 一个很复杂很复杂的几何题。当时写标程的时候相当痛苦。。。 难度： 相当难 http://acm.hdu.edu.cn/showproblem.php?pid=2290 一个图论题，不难，利用了floyd的dp思想。 难度： 中等 http://acm.hdu.edu.cn/showproblem.php?pid=2295 又是dlx。当时是没有题目了，然后找这个题凑的数。。。数据有点弱，没有好好生成。 难度： 难 http://acm.hdu.edu.cn/showproblem.php?pid=3118 简单图论题 难度：简单 http://acm.hdu.edu.cn/showproblem.php?pid=3119 圆的面积并+容斥原理。 难度： 难 http://acm.hdu.edu.cn/showproblem.php?pid=3120 图论+搜索 难度： 难 http://acm.hdu.edu.cn/showproblem.php?pid=3121 挺难的搜索 难度： 难 http://acm.hdu.edu.cn/showproblem.php?pid=3122 计算几何+线性规划 难度： 很难 http://acm.hdu.edu.cn/showproblem.php?pid=3124 扫描线+数据结构 难度： 难 http://acm.hdu.edu.cn/showproblem.php?pid=3126 几何+图论（二分图匹配） 难度： 中等 http://acm.hdu.edu.cn/showproblem.php?pid=3127 DP。。。标程错了。。。不过数据没有错误。 难度： 中等 http://acm.hdu.edu.cn/showproblem.php?pid=3238 一个相当难得图论题。这个是我出的也是我做过的题目中最难的一道题。不知道有没有其他人把这个题目做出来哈。 难度： 非常难 还有一些sb的简单题就不说啦。
