算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
A
六边形网格组成一个六边形,边长为a,b,c,a,b,c.(a,b,c<100)
问一共有多少个六边形

算法分析:
   不断的消去最外围的六边形, 直到有一个边是1为止. 复杂度O(n).

代码:
   http://codeforces.com/contest/216/submission/2007011

B
给一个点数为100的无向图,每个点度数最多是2. 问最少消去多少个点,可以使这个图2-染色.

算法分析:
   每个联通块不是链就是环, 如果是偶数的话可能可以2染色,如果是奇环一定要去掉一个才能2染色,如果是奇链的话... 统计一下奇链的个数.

代码:
   http://codeforces.com/contest/216/submission/2008126

C
题目描述太奇葩...

算法分析:
   贪心求解, 由于点数比较小,覆盖的时候直接暴力就好了.
   我还是很脑惨的写了个线段树优化到nlogn了,可惜由于末尾判断错误写挂了...

代码:
   http://codeforces.com/contest/216/submission/2013405

D
题目描述过于奇葩...

算法分析:
   把所有的bridge用vector存起来然后二分查找就可以了.
   太奇葩了,C和D唯一的难点就在理解题意???

代码:
   http://codeforces.com/contest/216/submission/2015729

E
给一个长度为n的k进制数(n<100,000, k<1,000,000,000),问这个序列有多少子串的数字根等于 m.

算法分析:
   k进制数x的数字根等于x mod (k-1) .
   预处理出前缀和mod(k-1)的值,统计有多少对值做差等于m就可以了.
   统计的过程很简单, 可以用map, 可以离散化之后直接统计...
   注意m = 0和m = k-1的情况, 还要注意最后减去所有的0...

代码: 
   http://codeforces.com/contest/216/submission/2013341
posted on 2012-08-15 16:25 西月弦 阅读(257) 评论(0)  编辑 收藏 引用 所属分类: 解题报告

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理