二分快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13

long long doexp(int x,int y)
{
    long long i=1,j=x;
    long long k;
    if (x==1||y==1) return x;
    while (y)
    {
        if (y&1) i=(i*j)%k;
        j=(j*j)%k;
        y=y>>1;
    }
    return i;
}

利用了二分log(n)级的快速迭代平方运算，可以很高效地完成幂运算。

Missing number

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

Problem Description

There is a permutation without two numbers in it, and now you know what numbers the permutation has. Please find the two numbers it lose.

占坑，回头补。

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.