codeforces 22 C. System Administrator

http://codeforces.com/contest/22/problem/C
题意:要求用n个点m条边构造一个不允许有重边的图,满足当去掉点v的时候,剩下的n-1个不联通。如果有答案输出任意,没答案输出-1.
思路:首先如果n个点要联通。。至少有n-1条边,此时为一棵树。但是是不是边越多越好呢?显然是不可以的。满足去掉一个点使得n-1个点不联通的情况为,存在一个点u只和v相连,不和任意任何其他点相连,那么当去掉v点,u点就变成不可到达了。边数最多的情况就是,除了v点以外的n-1个点,每个点的度都是n-2(去掉自身以及u点还有n-2个点),,那么除去u点以外的n-1个点的度数就是(n-1)*(n-2),边数则为(n-1)*(n-2)/2,再加一条连接u的边,所以图的最大边数为(n-1)*(n-2)/2+1,最小为n-1.

如果有解,那么接下来的问题是构造。

我是按照如下方式构造的:

先构造一条链,将u点放在第一个,v点放在第二个。不妨当v=1时令u=2,否则u=1;

m-=n-1,如果m还有剩余,那么从第二个点开始,一直到第n-2个点,每个点与至少隔1个点的其他点相连,直到边数没有剩余。

 

 

codeforces 29 C. Mail Stamps

http://codeforces.com/contest/29/problem/C
题意:给出n个边的关系,保证可以构成一条链。正向或者反向输出这个链。
思路:由于下标很大(1E9),而关系个数只有1E5..需要离散化。。而且离散化的同时不能丢失边的关系。。。实际上。。直接用vector+map就好了。。。 map >e;即可。然后找到一个度为1的点。。做个dfs…

codeforces 31 C. Schedule

http://codeforces.com/problemset/problem/31/C
题意:给出n个借用教室的时间安排,可能会有冲突。要求恰好去掉一个时间安排使得剩下的时间安排不冲突。问多多少种方案。
思路:首先一个直觉是。。除非初始就没有任何冲突。。不然这个答案不会很大。。

如果没有任何冲突,那么答案为n,直接输出一遍就好。

以l为第一关键字,r为第二关键字升序sort下。

如果有一个冲突,那么要看是否有包含关系,如果有,需要去掉大的这个,方案数为1.如果只是相交,那么可以去掉任意一个。方案数为2.

如果有两个冲突,我要看这两个冲突涉及到几个时间安排,如果涉及到4个或者时间安排,那么不可能全部解决,die掉。

如果这两个冲突涉及到三个时间安排,也就是说中间的和两段的相交,那么可以取消中间的这个时间安排来解决冲突。方案数为1.

需要注意的是输出的时候要按照原来的顺序。。所以存的时候记得存一下id.因为排序以后会打乱原有。输出之前还要sort下。 忘了这个。。WA#22/。因为按照id未必是从小到大输出的。

 

 

codeforces 27 C. Unordered Subsequence

http://codeforces.com/contest/27/problem/C
题意:给出一个序列,问是否存在一个disordered的子序列。。输出长度并输出组成子序列的下表(1..n)。如果有多组,输出任意一组。
disordered的意思是。。升序或者降序(不严格也可以)之外的情况。
思路: 首先我们可以知道,我们要找的子序列至少需要三个点。因为两个点怎么看都是有序的。而如果有k个点(k>3)组成的子序列存在。。那么机智得去掉其中一些点,可以只剩三个 ,同样满足题意。所以我们只需要找到三个点即可。如果把点以下标为横坐标,值为纵坐标花在坐标系上,就是找一个v型或者倒v型的三个点。

第二,我们可以将找三个点的问题转化成用第一个点+找两个点的问题。我们可以证明,如果解存在,那么包含第一个点的解也一定存在。我们可以用反证法证明,如果我们选了第1个点,然后从第2个点到第n个点。。我们找不到两个点与第一个点构成一个v型,那么整个序列一定是升序或者降序,无解,与前提矛盾。

需要注意的,判断方向的时候我用了乘,可能会爆int,记得用long long 

 

 

codeforces 30 C. Shooting Gallery

http://codeforces.com/contest/30/problem/C
题意:给出n个target在一个二维平面上。给出每个target的坐标,出现的时间,以及击中的概率。target出现之后就会瞬间消失,枪移动的单位速度为1,射击不需要时间。问能击中的target的最大期望是多少。

思路:路径dp。。。按照时间升序排列。 dp[i]表示到第i个target出现的时候的期望。

codeforces 14 C. Four Segments

http://codeforces.com/problemset/problem/14/C
题意:给出四条边的坐标,问能否形成一个边与坐标轴平行的矩形。边可能退化成点。
思路:首先第一步,检查有没有边退化成点以及是否有不平行的边。

第二步,检查两个方向的边是否各有两条。。

第三步,将所有点的坐标排序。。然后看8个点是否会因为重合而变成4个.。

 

codeforces 18 C. Stripe

http://codeforces.com/contest/18/problem/C
题意:将一个序列分成两个非空的部分,保证和相等,问有多少种方法。
思路:做过一个三部分的。。。两部分直接一个前缀和就好了把。。。有一个需要注意的是。。判断负数是否是奇数的时候需要加个绝对值。。。

codeforces 12 C. Fruits

http://codeforces.com/contest/12/problem/C
题意:有n个价格价格,m个要买的东西(可能有相同的种类,设为k种),把n个标签中拿出k个给个贴上。。。问最大价钱和最少价钱分别是多少。
思路:贪心。不过要按照map的value排序。。然后发现其实不用排序。。因为map的key值其实不影响。

vector降序排列的话。。直接 sort(v.rbegin(),v.rend());就好。

 

 

 

codeforces 16 C. Monitor

http://codeforces.com/contest/16/problem/C
题意:给定长宽a,b和分辨率x:y,注意分辨率x:y未必是最简比。问将现有的size裁剪成比例为x:y,使得面积最大的长宽是多少。
思路:可以通过找 x,y能扩大的倍数为k,找到一个最大的k使得k*x<=a&&k*y<=b。可以二分搞,但其实也可以不用。能扩大的最大的倍数其实就是 min(a/x,b/y). ps:收获了gcd更简单的一种写法。 直接 return b?gcd(b,a%b):a;

在linux mint 上安装 Oracle JDK 的方法

1. Open up the Terminal (Alt + F2 > Terminal).

2. Remove OpenJDK installation.

3. Download Oracle JDK from here. You are looking for a linux version with tar.gz extension. Also choose the right version from 32-bit (x86)  and 64bit (x64) one.

4. Change directory into one with downloaded tarball. In my case $HOME/Downloads.

5. Extract tarball. Replace with a name of dowloaded file. (just press Tab and it will be autocompleted.)

6. As a root create a folder in /opt where jdk will be stored.

7. Move extracted folder to /opt/java. In my case, version number was 1.7.0_25.

8. Make JDK system default.

9. Test installed java version.

java version “1.7.0_25” Java(TM) SE Runtime Environment (build 1.7.0_25-b15) Java HotSpot(TM) 64-Bit Server VM (build 23.25-b01, mixed mode)

 

codeforces 612 C. Replace To Make Regular Bracket Sequence

http://codeforces.com/contest/612/problem/C
题意:其实就是栈的基本操作。。水题。

codeforces 612 B. HDD is Outdated Technology

http://codeforces.com/contest/612/problem/B
水。

codeforces 612 A. The Text Splitting

http://codeforces.com/contest/612/problem/A
水题…直接枚举就好。

codeforces 612 D. The Union of k-Segments

http://codeforces.com/contest/612/problem/D

题意:给出n个线段信息,每个线段以l,r的形式给出。给定k。要求从作到右给出至少有k个线段覆盖的区间的信息。并使得区间数目尽可能少。

思路:很经典的一类问题…又想起了当年在tyvj上海洋兄给我的那个把线段比喻成公路,把两个端点比喻成收费站的比喻了。做法是把所有点的信息按照从小到大排序,并且记录点的类型信息,如果点相同,那么我们规定入口处的优先级高。用pair来搞的话。。可以把入口的type规定成-1,出口规定成1.然后从最左边的点开始扫,遇到-1的点厚度+1,遇到1的点厚度-1.当厚度为k的时候记录区间信息。