Graph and Queries

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

Problem Description

You are given an undirected graph with N vertexes and M edges. Every vertex in this graph has an integer value assigned to it at the beginning. You’re also given a sequence of operations and you need to process them as requested. Here’s a list of the possible operations that you might encounter:

1. Deletes an edge from the graph. The format is [D X], where X is an integer from 1 to M, indicating the ID of the edge that you should delete. It is guaranteed that no edge will be deleted more than once.

2. Queries the weight of the vertex with K-th maximum value among all vertexes currently connected with vertex X (including X itself). The format is [Q X K], where X is an integer from 1 to N, indicating the id of the vertex, and you may assume that K will always fit into a 32-bit signed integer. In case K is illegal, the value for that query will be considered as undefined, and you should return 0 as the answer to that query.

3. Changes the weight of a vertex. The format is [C X V], where X is an integer from 1 to N, and V is an integer within the range [-106, 106].

野生动物园

描述

cjBBteam拥有一个很大的野生动物园。这个动物园坐落在一个狭长的山谷内，这个区域从南到北被划分成N个区域，每个区域都饲养着一头狮子。这些狮子从北到南编号为1,2,3,…,N。每头狮子都有一个觅食能力值Ai，Ai越小觅食能力越强。饲养员cmdButtons决定对狮子进行M次投喂，每次投喂都选择一个区间[I,J]，从中选取觅食能力值第K强的狮子进行投喂。值得注意的是，cmdButtons不愿意对某些区域进行过多的投喂，他认为这样有悖公平。因此cmdButtons的投喂区间是互不包含的。你的任务就是算出每次投喂后，食物被哪头狮子吃掉了。

不差钱

描述

同学们一起看了小品《不差钱》，LX神突发奇想，想刁难一下十八居士，他让十八居士模拟一下点菜的过程。

输入格式

输入第一行为一个数price，表示价钱大于price的菜赵本山都不要。

以下几行表示点菜的过程，每行两个整数p，n

Robotic Sort

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

Problem Description

Somewhere deep in the Czech Technical University buildings, there are laboratories for examining mechanical and electrical properties of various materials. In one of yesterday’s presentations, you have seen how was one of the laboratories changed into a new multimedia lab. But there are still others, serving to their original purposes.

郁闷的出纳员

问题描述

OIER公司是一家大型专业化软件公司，有着数以万计的员工。作为一名出纳员，我的任务之一便是统计每位员工的工资。这本来是一份不错的工作，但是令人郁闷的是，我们的老板反复无常，经常调整员工的工资。如果他心情好，就可能把每位员工的工资加上一个相同的量。反之，如果心情不好，就可能把他们的工资扣除一个相同的量。我真不知道除了调工资他还做什么其它事情。

The kth great number

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

Problem Description

Xiao Ming and Xiao Bao are playing a simple Numbers game. In a round Xiao Ming can choose to write down a number, or ask Xiao Bao what the kth great number is. Because the number written by Xiao Ming is too much, Xiao Bao is feeling giddy. Now, try to help Xiao Bao.

The Experience of Love

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

Problem Description

A girl named Gorwin and a boy named Vivin is a couple. They arrived at a country named LOVE. The country consisting of N cities and only N−1 edges (just like a tree), every edge has a value means the distance of two cities. They select two cities to live，Gorwin living in a city and Vivin living in another. First date, Gorwin go to visit Vivin, she would write down the longest edge on this path(maxValue).Second date, Vivin go to Gorwin, he would write down the shortest edge on this path(minValue),then calculate the result of maxValue subtracts minValue as the experience of love, and then reselect two cities to live and calculate new experience of love, repeat again and again.

GTY’s gay friends

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Problem Description

GTY has n gay friends. To manage them conveniently, every morning he ordered all his gay friends to stand in a line. Every gay friend has a characteristic value ai , to express how manly or how girlish he is. You, as GTY’s assistant, have to answer GTY’s queries. In each of GTY’s queries, GTY will give you a range [l,r] . Because of GTY’s strange hobbies, he wants there is a permutation [1..r−l+1] in [l,r]. You need to let him know if there is such a permutation or not.

GTY’s birthday gift

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

Problem Description

FFZ’s birthday is coming. GTY wants to give a gift to ZZF. He asked his gay friends what he should give to ZZF. One of them said, ‘Nothing is more interesting than a number multiset.’ So GTY decided to make a multiset for ZZF. Multiset can contain elements with same values. Because GTY wants to finish the gift as soon as possible, he will use JURUO magic. It allows him to choose two numbers a and b(a,b∈S), and add a+b to the multiset. GTY can use the magic for k times, and he wants the sum of the multiset is maximum, because the larger the sum is, the happier FFZ will be. You need to help him calculate the maximum sum of the multiset.

二分快速幂

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)级的快速迭代平方运算，可以很高效地完成幂运算。