好久没写一整套cf的解题报告了。自从区域赛完之后就没打,但是不能放下!

A.Elephant

题意:初始位置为0,每次可以走1,2,3,4,5步,问到达位置n最少需要多少步。

思路:肯定优先走5步,剩下的小于5的走一步。 n / 5 + (n % 5 != 0)

B.Chocolate

题意:给你一堆0,1序列,你可以把他们切成若干段,每一段一定只包含一个1,问你有多少种切法。

思路:可以用排列组合的思想,找出所有不相干的段,他们的切割点个数的乘积。

也可以用dp,d[i] 表示前i个点的切割方法。

C.Watering Flowers

题意:给定两个圆心和一堆点,问你如何确定两个圆的半径,可以覆盖所有点,并且 r1^2 + r2^2最小

思路:首先从贪心的角度想,两个圆上的圈上一定存在点,那么我们可以枚举一个点,假设这个点是圆心1圆边上的

那么扫一遍这n个点,所有在这个圆里面的都不管,不在这个圆内部的给圆2.这样可以用 n2的方法求出结果。

最后终测我的代码挂了。写的代码有问题,,漏掉了所有点被一个圆包括的那种情况。

D. Polyline

题意:给定三个点,问如何用线段链接这三个点,使得不存在线段相交的情况。

思路:我真的不知道这个题在这的意义是什么,让人体验一下hack的快感?

特判一下就可以了。 如果三个点在一条直线,那么就输出1.

如果两个点在一条直线,另外一个点在他们的外部,就是2,其他都是3.

我hack了6个人。。哈哈

E.XOR and Favorite Number

题意:给定n个数,m次查询,问一个区间内有多少组 l,r,他们的xor值等于k。

思路:这个题一看就是莫队算法,但是难就难在如何快速的扩展。

首先预处理出前缀xor值  sum[i]

这个扩展还是很巧妙地。假设我们已知一个区间,和这个区间内所有 xor 的情况的种类数。

那么在扩展一位的时候,我们就可以根据这以为的前缀 来得到有多少个 原区间内和其xor等于k的值。

 

 

Codeforces Round #323 (Div. 2) A,B,C,D

太弱了。E题至今看不懂题解意思。。 A。水题, 题意:太难读了!输入n个交点,输出所有没有经过过的交点的位置。 思路:标记一下直接判就行了。 ...

阅读全文

Codeforces Round #320 (Div. 1) [Bayan Thanks-Round] (A,B,C)

A。A Problem about Polyline 直接求/二分 题意:有一中图形 结构为 /\/\/\/\ 这样,给你一个点(a,b)让你求最小的x使得该点在这种图形上。 思路1. 当然可...

阅读全文

Codeforces Round #316 (Div. 2) 解题报告

A。Elections 题意:m*n的矩阵,每行代表每个某个城市对某个人的选举的票数,票最多的那个人并且下标最小的那个人获胜,求总票数最多且下标最小的人的编号。 ...

阅读全文

欢迎留言

*