Codeforces Round #261 (Div. 2)[ABCDE]_html/css_WEB-ITnose

Codeforces Round #261 (Div. 2)[ABCDE]

ACM

题目地址:Codeforces Round #261 (Div. 2)

A - Pashmak and Garden

题意：
一个正方形，它的边平行于坐标轴，给出这个正方形的两个点，求出另外两个点。

分析：
判断下是否平行X轴或平行Y轴，各种if。

代码：

/**  Author:      illuz *  File:        A.cpp*  Create Date: 2014-08-15 23:35:17*  Descripton:   */#include #include #include #include using namespace std;const int N = 0;int main() {	int x1, y1, x2, y2, x3, y3, x4, y4;	int a;	while (cin >> x1 >> y1 >> x2 >> y2) {		if (x1 == x2) {			a = y1 - y2;			cout   

  
  
  
 B - Pashmak and Flowers
  
 题意： 
 在n个数中取出两个数，使得差值最大，问差值和有几种取法。 
 两种取法不同当且仅当：两种方法至少有一个不同位置的数。
  
 分析：
  
 很明显差值就是最大-最小。
  
 如果两个数不是相同的，那么取法就是max_cnt * min_cnt了。 
 如果相同就要注意了，因为max_cnt * min_cnt里面有一些取法一样的数。 
 比如：5 1 1 1 1 1。
  

那么我们可以这样考虑，第一次可以取5种，第二次可以取(5-1)钟，但是这里面(i,j)和(j,i)都取过，所以得减半，所以结果就是n*(n-1)/2。
   
或者可以这样考虑，我们为了不要取重复，规定第一次取的位置肯定在第二次前面，如果第一次取pos1，那么下次只能取(n-1)钟；如果第一次取pos2，第二次就(n-2)....累计就是(n-1)*n/2了。
  
 代码：
  
 
  
/**  Author:      illuz *  File:        B.cpp*  Create Date: 2014-08-15 23:51:15*  Descripton:   */#include #include #include #include using namespace std;#define repf(i,a,b) for(int i=(a);i> t) {		repf (i, 0, t - 1) {			cin >> a[i];		}		sort (a, a + t);		if (a[0] == a[t - 1]) {			cout = 0 && a[i] == a[t - 1])			mmax++, i--;		cout   

  
  
  
 C - Pashmak and Buses
  
 题意： 
 n个人坐车，有k辆车带他们去d个地方玩。问怎么安排使得这d天他们没有一对人一直在一起的（FFF团的胜利）。
  
 分析： 
 相当于：d行n列，每个位置填一个1～k的整数，要求不能有两列完全一样。 
 爆搜过去即可，只要有解就行了。
  
 代码：
  
 
  
/**  Author:      illuz *  File:        C.cpp*  Create Date: 2014-08-16 00:47:18*  Descripton:   */#include#include#include#include#include#includeusing namespace std;const int N = 1110;int a[N], sum;int n, d, k, m[N][N];void dfs(int x) {    if(sum >= n)		return;    if(x >= d) {        for (int i = 0; i   

  
  
  
 D - Pashmak and Parmida's problem
  
 题意： 
 给出一些数a[n]，求(i, j),i f(j, n, a[j])。
 f(lhs, rhs, x)指在{ [lhs, rhs]范围中，a[k]的值=x }的数量。
  
 分析： 
 很明显： 
 1. f(1, i, a[i])就是指a[i]前面包括a[i]的数中，有几个值=a[i]。 
 2. f(j, n, a[j])就是指a[j]后面包括a[j]的数中有几个值=a[j]。
  
 虽然a[x]范围不小，但是n的范围是1000，不是很大，所以我们可以用map预处理出f(1, i, a[i])和f(j, n, a[j])，记为s1[n], s2[n]。
  
 这样就变成求满足s1[i] > s[j]， i   
 代码：
  
 
  
/**  Author:      illuz *  File:        D.cpp*  Create Date: 2014-08-16 00:18:08*  Descripton:   */#include #include #include #include #include