The 2014 ACM-ICPC Asia Regional Anshan Online

Posted on 2014-09-13 Edited on 2018-03-07 In ACM-比赛

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

~~【B】计算几何（点的旋转）~~

【C】DP+状态压缩

【D】离散数学+DP （感觉可出）

~~【E】概率DP~~

【F】LCT模板题（-_-///LCT是啥！！！！）

~~【G】签到题~~

【H】染色+搜索

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

【J】物理题，数论，高斯消元法（感觉可出）

HDU 1068 Girls and Boys 二分图最大独立集（最大二分匹配）

Posted on 2014-09-12 Edited on 2016-01-11 In ACM-训练

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.

HDU 3367 Pseudoforest 最大生成树

Posted on 2014-09-09 Edited on 2016-01-11 In ACM-训练

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.

The 2014 ACM-ICPC Asia Mudanjiang Regional First Round

Posted on 2014-09-08 Edited on 2016-01-11 In ACM-比赛

~~【A】签到题~~

~~【B】构造~~

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

【D】DP（背包）+状态压缩（感觉可出）

【E】线段树

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

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

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

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

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

HDU 1811 Rank of Tetris 拓扑排序+并查集

Posted on 2014-09-07 Edited on 2016-01-11 In ACM-训练

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。

HDU 1589 Find The Most Comfortable Road 最小生成树+枚举

Posted on 2014-09-07 Edited on 2016-01-11 In ACM-训练

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

STL中优先队列的使用

Posted on 2014-09-06 Edited on 2016-01-11 In 算法学习

STL中有一个优先队列的容器可以使用。

头文件

queue 队列容器

vector 向量容器

操作

优先级队列支持的操作

调用	功能
q.empty()	如果队列为空，则返回true，否则返回false
q.size()	返回队列中元素的个数
q.pop()	删除队首元素，但不返回其值
q.top()	返回具有最高优先级的元素值，但不删除该元素
q.push(item)	在基于优先级的适当位置插入新元素

HDU 2489 Minimal Ratio Tree 最小生成树+DFS

Posted on 2014-09-06 Edited on 2018-09-23 In ACM-训练

Minimal Ratio Tree

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

Problem Description

For a tree, which nodes and edges are all weighted, the ratio of it is calculated according to the following equation.

Given a complete graph of n nodes with all nodes and edges weighted, your task is to find a tree, which is a sub-graph of the original graph, with m nodes and whose ratio is the smallest among all the trees of m nodes in the graph.