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

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

ACM

Title address: Codeforces Round #261 (Div. 2)

A - Pashmak and Garden

Question:
A square whose sides are parallel to the coordinate axis. Given two points of this square, find the other two points.

Analysis:
Determine whether it is parallel to the X-axis or parallel to the Y-axis, various ifs.

Code:

/**  Author:      illuz <iilluzen>*  File:        A.cpp*  Create Date: 2014-08-15 23:35:17*  Descripton:   */#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>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  <br> <br> <p></p> <p class="sycode"> </p> <h2> B - Pashmak and Flowers</h2> <p> Question meaning: <br> Take two numbers out of n numbers so that the difference is the largest. There are several ways to take the sum of the differences. <br> The two methods are different if and only if: the two methods have at least one number in a different position. </p> <p> Analysis: </p> <p> It is obvious that the difference is the maximum-minimum. </p> <p> If the two numbers are not the same, then the method is max_cnt * min_cnt. <br> If they are the same, please pay attention because there are some numbers in max_cnt * min_cnt that have the same method. <br> For example: 5 1 1 1 1 1. </p> <ol> <li> Then we can think about it this way, we can choose 5 kinds for the first time, and (5-1) for the second time, but here (i,j) and (j,i) are both It has been taken, so it has to be halved, so the result is n*(n-1)/2. </li> <li> Or you can think about it this way. In order to avoid duplication, we stipulate that the position taken for the first time must be before the second time. If pos1 is taken for the first time, then only (n-1) clocks can be taken next time; If pos2 is taken for the first time, it will be (n-2) for the second time.... The total is (n-1)*n/2. </li> </ol> <p> Code: </p> <p> </p> <pre name="code" class="sycode">/**  Author:      illuz <iilluzen>*  File:        B.cpp*  Create Date: 2014-08-15 23:51:15*  Descripton:   */#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>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  <br> <br> <p></p> <p class="sycode"> </p> <h2> C - Pashmak and Buses</h2> <p> Question meaning: <br> n people take a car, and there are k cars taking them to d places to play. Asked how they arranged it so that no one of them was together all the time on this day (the victory of the FFF group). </p> <p> Analysis: <br> Equivalent to: d rows and n columns, each position is filled with an integer from 1 to k, and it is required that no two columns are exactly the same. <br> Just search it, as long as you have a solution. </p> <p> Code: </p> <p> </p> <pre name="code" class="sycode">/**  Author:      illuz <iilluzen>*  File:        C.cpp*  Create Date: 2014-08-16 00:47:18*  Descripton:   */#include<cmath>#include<cstdio>#include<string>#include<cstring>#include<iostream>#include<algorithm>using 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  <br> <br> <p></p> <p class="sycode"> </p> <h2> D - Pashmak and Parmida's problem</h2> <p> Question meaning: <br> Given some numbers a[n], find the number of (i, j), i<j such that: f i a> f(j, n, a[j]). <br> f(lhs, rhs, x) refers to the number of values ​​​​of a[k] = x } in the range { [lhs, rhs]. </j></p> <p> Analysis: <br> Obviously: <br> 1. f(1, i, a[i]) refers to how many values ​​there are in the number including a[i] before a[i] =a[i]. <br> 2. f(j, n, a[j]) refers to how many values ​​in the number including a[j] after a[j] = a[j]. </p> <p> Although the range of a[x] is not small, the range of n is 1000, which is not very large, so we can use map to preprocess f(1, i, a[i]) and f(j, n, a[j]), denoted as s1[n], s2[n]. </p> <p> This becomes finding the number of situations that satisfy s1[i] > s[j], i  </p>
<p> Code: </p> <p> </p> <pre name="code" class="sycode">/**  Author:      illuz <iilluzen>*  File:        D.cpp*  Create Date: 2014-08-16 00:18:08*  Descripton:   */#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <map>using namespace std;#define rep(i,n) for(int i=0;i=(b);i--)typedef long long ll;#define lson(x) ((x) > 1;		build(l, m, lson(pos));		build(m + 1, r, rson(pos));		update(pos);	}	// add the point x with y	void modify(int l, int r, int pos, int x, ll y) {		if (l == r) {			node[pos].w += y;			return;		}		int m = (l + r) >> 1;		if (x > 1;		ll res = 0;		if (x  m)			res += query(m + 1, r, rson(pos), x, y);		return res;	}} sgm;ll t, a[N];int s1[N], s2[N];map<ll int> mp;int main() {	while (cin >> t) {		mp.clear();		rep (i, t) {			cin >> a[i];			mp[a[i]]++;			s1[i] = mp[a[i]];		}		mp.clear();		for (int i = t - 1; i >= 0; i--) {			mp[a[i]]++;			s2[i] = mp[a[i]];		}		sgm.build(1, t, ROOT);		ll ans = 0;		rep (i, t) {			ans += sgm.query(1, t, ROOT, s2[i] + 1, t); 			sgm.modify(1, t, ROOT, s1[i], 1);			//cout  <br> <br> <p></p> <p class="sycode"> </p> <h2> E - Pashmak and Graph</h2> <p> Question meaning: <br> Given a directed weighted graph, it is required to find the length of the longest increasing link. That is, the weight of the current edge is greater than the previous edge. </p> <p> Analysis: <br> I just wrote a search map memoization, and then TLE QvQ... <br> In fact, you can use the dp of the array to do it, first sort the edges from small to large, and then sort the edges from small to large. Arrival processing, for the same type of edge, perform the opposite edge dp, and then update the opposite point dp. </p> <p> @bartyjuju: </p> <p> Sort all the edges from small to large according to the edge weights, and scan them sequentially. If there are no repeated edge weights, for (u, v, d) this directed Edge, you can directly use the previously found longest path to u point 1 to update the longest path to v. <br> However, the question does not guarantee that all edge weights are different. In order to ensure strict increment, a buffering process is required for the same edge weights. </p> <p> Code: </p> <p> </p> <pre name="code" class="sycode">/**  Author:      illuz <iilluzen>*  Blog:        http://blog.csdn.net/hcbbt*  File:        E.cpp*  Create Date: 2014-08-16 09:43:59*  Descripton:   */#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;#define repf(i,a,b) for(int i=(a);i <br> <br> <p></p> <p class="sycode"> <br> </p> </algorithm></cstring></cstdio></iostream></iilluzen>