Chenfan Blog

Do cool things that matter.

0%

自从上次网赛发现这么个东西之后,深深地感受到了bitset的强大,0.0。

正常的bool占用1字节空间,bitset可以把这个缩到1bit,空间上8倍优化。正常用起来可能会跟位运算状态压缩类似,但是其中的每个位又能进行单独操作,所以确实相当方便。

下面是原版的文档:

class template

std::bitset

Read more »

【A】-_-///

【B】线段树+位运算(感觉可出)

【C】地图BFS,找最长线

【D】地图BFS,加上各种复杂情况的最短路-_-

【E】-_-///

【F】三分+圆与线段的交点,计算几何

【G】-_-///

【H】线段树+树链剖分

【I】后缀数组+二分

【J】DFS搜索

这场网赛当时自己完成了的也就是两道地图题,过去好久了才想到还是该记录下来…

Read more »

【A】极角排序+树状数组

【B】计算几何,凸包(队友已出)

【C】-_-///不懂

【D】数论,概率密度

【E】图的连通性+Floyed传递闭包+bitset

【F】贪心

【G】签到题

【H】区间维护+线段树+DFS序(可以看看)

【I】BFS地图题(当时好多人坑在摄像头上面了,现在有一点点思路,分层图,一会看看)

【J】-_-/////

貌似除了这两题巨坑的,剩下的都有能出的可能性

Read more »

【A】签到题

【B】后缀数组

【C】染色,DP(感觉可出)

【D】BFS搜索,有点麻烦

【E】博弈论,Nim博弈

【F】BFS状态搜索

【G】概率DP+状态压缩

【H】异或+构造

【I】矩阵快速幂(队友已出)

【J】树的分治

【K】类模拟退火的方向修正搜索、三分

Read more »

【A】无向图的双联通子图计数、DP+状态压缩

【B】计算几何(点的旋转)

【C】DP+状态压缩

【D】离散数学+DP (感觉可出)

【E】概率DP

【F】LCT模板题(-_-///LCT是啥!!!!)

【G】签到题

【H】染色+搜索

【I】阅读理解+记忆化搜索

【J】物理题,数论,高斯消元法(感觉可出)

Read more »

Girls and Boys

Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Problem Description

the second year of the university somebody started a study on the romantic relations between the students. The relation “romantically involved” is defined between one girl and one boy. For the study reasons it is necessary to find out the maximum set satisfying the condition: there are no two students in the set who have been “romantically involved”. The result of the program is the number of students in such a set.

Read more »

Pseudoforest

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Problem Description

In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. The maximal pseudoforests of G are the pseudoforest subgraphs of G that are not contained within any larger pseudoforest of G. A pesudoforest is larger than another if and only if the total value of the edges is greater than another one’s.

Read more »

【A】签到题

【B】构造

【C】遍历+floodfill染色或并查集

【D】DP(背包)+状态压缩 (感觉可出)

【E】线段树

【F】图形题 搜索+状态压缩

【G】数论,某种不定方程……ZOJ上到现在只过了4个人,还找不到题解-_-///

【H】回文数变种+dfs枚举构造 又是构造-_-///

【I】字符串哈希+DP或者暴力

【J】直接模拟,字符串细节操作

Read more »

Rank of Tetris

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Problem Description

自从Lele开发了Rating系统,他的Tetris事业更是如虎添翼,不久他遍把这个游戏推向了全球。

为了更好的符合那些爱好者的喜好,Lele又想了一个新点子:他将制作一个全球Tetris高手排行榜,定时更新,名堂要比福布斯富豪榜还响。关于如何排名,这个不用说都知道是根据Rating从高到低来排,如果两个人具有相同的Rating,那就按这几个人的RP从高到低来排。

终于,Lele要开始行动了,对N个人进行排名。为了方便起见,每个人都已经被编号,分别从0到N-1,并且编号越大,RP就越高。 同时Lele从狗仔队里取得一些(M个)关于Rating的信息。这些信息可能有三种情况,分别是”A > B”,”A = B”,”A < B”,分别表示A的Rating高于B,等于B,小于B。

Read more »

find the most comfortable road

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Problem Description

XX星有许多城市,城市之间通过一种奇怪的高速公路SARS(Super Air Roam Structure—超级空中漫游结构)进行交流,每条SARS都对行驶在上面的Flycar限制了固定的Speed,同时XX星人对 Flycar的“舒适度”有特殊要求,即乘坐过程中最高速度与最低速度的差越小乘坐越舒服 ,(理解为SARS的限速要求,flycar必须瞬间提速/降速,痛苦呀 ), 但XX星人对时间却没那么多要求。要你找出一条城市间的最舒适的路径。(SARS是双向的)。

Input

Read more »