占坑，回头补。

OJ是跑在LAMP的环境中，Linux+Apache+Mysql+Php

Desert King

Time Limit: 3000MS Memory Limit: 65536K

Description

David the Great has just become the king of a desert country. To win the respect of his people, he decided to build channels all over his country to bring water to every village. Villages which are connected to his capital village will be watered. As the dominate ruler and the symbol of wisdom in the country, he needs to build the channels in a most elegant way.

Dropping tests

Time Limit: 1000MS Memory Limit: 65536K

Description

In a certain course, you take n tests. If you get ai out of bi questions correct on test i, your cumulative average is defined to be

$$100*\frac{\sum_{i=1}^na_i}{\sum_{j=1}^nb_j}$$

Qin Shi Huang’s National Road System

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

Problem Description

During the Warring States Period of ancient China(476 BC to 221 BC), there were seven kingdoms in China —- they were Qi, Chu, Yan, Han, Zhao, Wei and Qin. Ying Zheng was the king of the kingdom Qin. Through 9 years of wars, he finally conquered all six other kingdoms and became the first emperor of a unified China in 221 BC. That was Qin dynasty —- the first imperial dynasty of China(not to be confused with the Qing Dynasty, the last dynasty of China). So Ying Zheng named himself “Qin Shi Huang” because “Shi Huang” means “the first emperor” in Chinese.

Minimum Spanning Tree

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

Problem Description

XXX is very interested in algorithm. After learning the Prim algorithm and Kruskal algorithm of minimum spanning tree, XXX finds that there might be multiple solutions. Given an undirected weighted graph with n (1<=n<=100) vertexes and m (0<=m<=1000) edges, he wants to know the number of minimum spanning trees in the graph.

(本帖排版有问题，回头需要重新整理)

生成树计数就是统计一张图中一共有多少种构造生成树的方案。

大概要用到组合数学等等的数学知识。

问题的引入

以下内容均来自NOI2007国家集训队论文 周冬 《生成树的计数及其应用》：

Matrix-Tree定理(Kirchhoff矩阵-树定理)。Matrix-Tree定理是解决生成树计数问题最有力的武器之一。它首先于1847年被Kirchhoff证明。在介绍定理之前，我们首先明确几个概念：

Transfer water

Time Limit: 5000/3000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Others)

Problem Description

XiaoA lives in a village. Last year flood rained the village. So they decide to move the whole village to the mountain nearby this year. There is no spring in the mountain, so each household could only dig a well or build a water line from other household. If the household decide to dig a well, the money for the well is the height of their house multiplies X dollar per meter.

开始学习最小树形图，模板题。

Ice_cream’s world II

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

Problem Description

After awarded lands to ACMers, the queen want to choose a city be her capital. This is an important event in ice_cream world, and it also a very difficult problem, because the world have N cities and M roads, every road was directed. Wiskey is a chief engineer in ice_cream world. The queen asked Wiskey must find a suitable location to establish the capital, beautify the roads which let capital can visit each city and the project’s cost as less as better. If Wiskey can’t fulfill the queen’s require, he will be punishing.

继续复盘下一场Regional！

【A】-_-///

【B】模拟（之前每次遇到模拟、暴搜都直接跳了，题目太长也是一个原因…下次是在不行可以尝试一下）

【C】数论 互质、容斥？

【D】数学推导（方差）+贪心

【E】签到DP

【F】-_-///

【G】最小割的灵活运用

【H】搜索+打表

【I】签到题

【J】-_-///

【K】计算几何、置换群（Polya计数）

【L】AC自动机+树链剖分