发表于 | 分类于 ， ， | 评论数： | 阅读次数：


很好的一篇文章

原文链接

并查集是我暑假从高手那里学到的一招，觉得真是太精妙的设计了。以前我无法解决的一类问题竟然可以用如此简单高效的方法搞定。不分享出来真是对不起party了。（party：我靠，关我嘛事啊？我跟你很熟么？）

来看一个实例，HDU1232畅通工程



首先在地图上给你若干个城镇，这些城镇都可以看作点，然后告诉你哪些对城镇之间是有道路直接相连的。最后要解决的是整幅图的连通性问题。比如随意给你两个点，让你判断它们是否连通，或者问你整幅图一共有几个连通分支，也就是被分成了几个互相独立的块。像畅通工程这题，问还需要修几条路，实质就是求有几个连通分支。如果是1个连通分支，说明整幅图上的点都连起来了，不用再修路了；如果是2个连通分支，则只要再修1条路，从两个分支中各选一个点，把它们连起来，那么所有的点都是连起来的了；如果是3个连通分支，则只要再修两条路……
阅读全文 »

发表于 | 分类于 ， | 评论数： | 阅读次数：




## 1529: 寻找最大数

Time Limit: 1 Sec  Memory Limit: 128 MB

Submit: 107  Solved: 53

上一题SubmitStatus标签打分编辑题目信息编辑测试数据下一题




## Description



给出一个整数n每次可以移动相邻数位上的数字，最多移动k次，得到一个新的整数，求这个新的整数的最大值是多少。

Input



多组测试数据。

每组测试数据占一行，每行有两个数N和K (1 ≤ N≤ 10^100; 0 ≤ K ≤ 100).

Output

每组测试数据的输出占一行，输出移动后得到的新的整数的最大值。

Sample Input

1990 1

100 0

9090000078001234 6

Sample Output

9190

100

9907000008001234

HINT

Source

阅读全文 »

发表于 | 分类于 ， ， | 评论数： | 阅读次数：


### Contest1068 - 2017“久源软件杯”安徽科技学院第八届程序设计大赛



关于举办“久源软件杯”

安徽科技学院第八届程序设计大赛通知


     ACM 国际大学生程序设计竞赛 (International Collegiate Programming Contest）是由美国计算机协会（ACM）主办的一项旨在展示大学生创新能力、团队精神和在压力下编写程序、分析和解决问题能力的著名竞赛。2010年以来，我校参与了历届安徽省 ACM 程序设计竞赛，并取得了优异的成绩。为选拔省ACM 参赛队员，特举办“久源软件杯” 安徽科技学院第八届计算机程序设计大赛，热忱欢迎广大程序设计爱好者踊跃参加。

 

主办方：安徽科技学院教务处、信息与网络工程学院

承办方：信息与网络工程学院计算机系

赞助方：无锡久源软件股份有限公司（独家赞助）

 

一、 比赛时间：2017 年 4 月 22（周六）上午 8:00～12:00

二、比赛地点：计算机与网络实验中心（力行楼六楼）

三、参赛对象：14～16 级计算机、网络、信息、电子等专业

四、 报名方式（免费报名参赛）：

（1）报名网站： https://oj.ahstu.cc/JudgeOnline/contest_join.php?cid=1068

（2）请加入比赛 QQ 群：391668336（安科ACM官方群）

（3） 报名时间：2017 年 4 月 10日至 4月 21 日

五、比赛设奖：设一等奖8%、二等奖12%、三等奖15%、优秀奖若干

（1）一二三等奖都有丰厚的物质奖励

（2）一二等奖同学直接进入省ACM赛集训

六、竞赛相关：
阅读全文 »

发表于 | 分类于 ， ， | 评论数： | 阅读次数：

食物链














Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 70529 Accepted: 20875

Description

<div class=”ptx” lang=”en-US” style=”font-family:”Times New Roman”,Times,serif; font-size:14px”>
动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。 

现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。 

有人用两种说法对这N个动物所构成的食物链关系进行描述： 

第一种说法是”1 X Y”，表示X和Y是同类。 

第二种说法是”2 X Y”，表示X吃Y。 

此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。 

1） 当前的话与前面的某些真的话冲突，就是假话； 

2） 当前的话中X或Y比N大，就是假话； 

3） 当前的话表示X吃X，就是假话。 

你的任务是根据给定的N（1 <= N <= 50,000）和K句话（0 <= K <= 100,000），输出假话的总数。 

Input

阅读全文 »

发表于 | 分类于 ， ， | 评论数： | 阅读次数：

Max Sequence














Time Limit: 3000MS Memory Limit: 65536K
Total Submissions: 17678 Accepted: 7401

Description

<div class=”ptx” lang=”en-US” style=”font-family:”Times New Roman”,Times,serif; font-size:14px”>
Give you N integers a1, a2 … aN (|ai| <=1000, 1 <= i <= N). 



You should output S. 

Input

<div class=”ptx” lang=”en-US” style=”font-family:”Times New Roman”,Times,serif; font-size:14px”>
The input will consist of several test cases. For each test case, one integer N (2 <= N <= 100000) is given in the first line. Second line contains N integers. The input is terminated by a single line with N = 0.

Output

<div class=”ptx” lang=”en-US” style=”font-family:”Times New Roman”,Times,serif; font-size:14px”>
For each test of the input, print a line containing S.

Sample Input

5
-5 9 -5 11 20
0

Sample Output

40

Source

POJ Monthly–2005.08.28,Li Haoyuan

题解：这个题2479差不多，具体可以看2479的题解，不过感觉这道题的测试数据要比2479弱一些，轻松AC

//主要是刷几道dp练练手

阅读全文 »

发表于 | 分类于 ， ， | 评论数： | 阅读次数：
Maximum sum














Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 40596Accepted: 12663

Description

Given a set of n integers: A={a1, a2,…, an}, we define a function d(A) as below:
>
Your task is to calculate d(A).

Input

The input consists of T(<=30) test cases. The number of test cases (T) is given in the first line of the input.
Each test case contains two lines. The first line is an integer n(2<=n<=50000). The second line contains n integers: a1, a2, …, an. (|ai| <= 10000).There is an empty line after each case.

Output

Print exactly one line for each test case. The line should contain the integer d(A).

Sample Input

1

10
1 -1 2 2 3 -3 4 -4 5 -5

Sample Output

13

Hint

阅读全文 »

发表于 | 分类于 ， ， | 评论数： | 阅读次数：
Ubiquitous Religions














Time Limit: 5000MSMemory Limit: 65536K
Total Submissions: 34122Accepted: 16477

Description

There are so many different religions in the world today that it is difficult to keep track of them all. You are interested in finding out how many different religions students in your university believe in.You know that there are n students in your university (0 < n <= 50000). It is infeasible for you to ask every student their religious beliefs. Furthermore, many students are not comfortable expressing their beliefs. One way to avoid these problems is to ask
m (0 <= m <= n(n-1)/2) pairs of students and ask them whether they believe in the same religion (e.g. they may know if they both attend the same church). From this data, you may not know what each person believes in, but you can get an idea of the upper bound
of how many different religions can be possibly represented on campus. You may assume that each student subscribes to at most one religion.

Input

The input consists of a number of cases. Each case starts with a line specifying the integers n and m. The next m lines each consists of two integers i and j, specifying that students i and j believe in the same religion. The students are numbered 1 to n. The
end of input is specified by a line in which n = m = 0.

Output

阅读全文 »

发表于 | 分类于 ， ， | 评论数： | 阅读次数：

Is It A Tree?














Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 32052 Accepted: 10876

Description

<div class=”ptx” lang=”en-US” style=”font-family:”Times New Roman”,Times,serif; font-size:14px”>
A tree is a well-known data structure that is either empty (null, void, nothing) or is a set of one or more nodes connected by directed edges between nodes satisfying the following properties. 

There is exactly one node, called the root, to which no directed edges point. 

Every node except the root has exactly one edge pointing to it. 

There is a unique sequence of directed edges from the root to each node. 

For example, consider the illustrations below, in which nodes are represented by circles and edges are represented by lines with arrowheads. The first two of these are trees, but the last is not. 



In this problem you will be given several descriptions of collections of nodes connected by directed edges. For each of these you are to determine if the collection satisfies the definition of a tree or not.

Input

<div class=”ptx” lang=”en-US” style=”font-family:”Times New Roman”,Times,serif; font-size:14px”>
The input will consist of a sequence of descriptions (test cases) followed by a pair of negative integers. Each test case will consist of a sequence of edge descriptions followed by a pair of zeroes Each edge description will consist of a pair of integers;
the first integer identifies the node from which the edge begins, and the second integer identifies the node to which the edge is directed. Node numbers will always be greater than zero.

Output

<div class=”ptx” lang=”en-US” style=”font-family:”Times New Roman”,Times,serif; font-size:14px”>
For each test case display the line “Case k is a tree.” or the line “Case k is not a tree.”, where k corresponds to the test case number (they are sequentially numbered starting with 1).

阅读全文 »

发表于 | 分类于 ， ， ， | 评论数： | 阅读次数：

Network
















Time Limit: 1000MS Memory Limit: 30000K
Total Submissions: 16628 Accepted: 6597 Special Judge

Description

<div class=”ptx” lang=”en-US” style=”font-family:”Times New Roman”,Times,serif; font-size:14px”>
Andrew is working as system administrator and is planning to establish a new network in his company. There will be N hubs in the company, they can be connected to each other using cables. Since each worker of the company must have access to the whole network,
each hub must be accessible by cables from any other hub (with possibly some intermediate hubs). 

Since cables of different types are available and shorter ones are cheaper, it is necessary to make such a plan of hub connection, that the maximum length of a single cable is minimal. There is another problem — not each hub can be connected to any other one
because of compatibility problems and building geometry limitations. Of course, Andrew will provide you all necessary information about possible hub connections. 

You are to help Andrew to find the way to connect hubs so that all above conditions are satisfied. 

Input

阅读全文 »