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[at]gmail.com>*  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 << x1 + a << ' ' << y1 << ' ' << x2 + a << ' ' << y2 << endl;		} else if (y1 == y2) {			a = x1 - x2;			cout << x1 << ' ' << y1 + a << ' ' << x2 << ' ' << y2 + a << endl;		} else {			if (abs(x1 - x2) != abs(y1 - y2)) {				cout << -1 << endl;				continue;			}			cout << x1 << ' ' << y2 << ' ' << x2 << ' ' << y1 << endl;		}	}	return 0;}

B - Pashmak and Flowers

Question meaning:
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.
The two methods are different if and only if: the two methods have at least one number in a different position.

Analysis:

It is obvious that the difference is the maximum-minimum.

If the two numbers are not the same, then the method is max_cnt * min_cnt.
If they are the same, please pay attention because there are some numbers in max_cnt * min_cnt that have the same method.
For example: 5 1 1 1 1 1.

1. 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.
2. 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.

Code:

/**  Author:      illuz <iilluzen[at]gmail.com>*  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<=(b);i++)typedef long long ll;const int N = 2e5 + 10;ll t, mmax, mmin;ll a[N];int main() {	while (cin >> t) {		repf (i, 0, t - 1) {			cin >> a[i];		}		sort (a, a + t);		if (a[0] == a[t - 1]) {			cout << 0 << ' ' << t * (t - 1) / 2 << endl;			continue;		}		mmax = 0;		mmin = 0;		int i = 0;		while (i < t && a[i] == a[0])			mmin++, i++;		i = t - 1;		while (i >= 0 && a[i] == a[t - 1])			mmax++, i--;		cout << a[t - 1] - a[0] << ' ' << mmin * mmax << endl;	}	return 0;}

C - Pashmak and Buses

Question meaning:
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).

Analysis:
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.
Just search it, as long as you have a solution.

Code:

/**  Author:      illuz <iilluzen[at]gmail.com>*  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 < d; i++)			m[i][sum] = a[i];        sum++;        return;    }    for(int i = 1; i <= min(k, 1001); i++) {        a[x] = i;        dfs(x + 1);    }}int main() {    while (~scanf("%d%d%d", &n, &k, &d)) {        memset(m, 0, sizeof(m));        sum = 0;        dfs(0);        if(sum < n)			puts("-1");        else {            for(int i = 0; i < d; i++) {                for(int j = 0; j < n; j++)					printf("%d ", m[i][j]);                puts("");            }        }    }    return 0;}

D - Pashmak and Parmida's problem

Question meaning:
Given some numbers a[n], find the number of (i, j), i f(j, n, a[j]).
f(lhs, rhs, x) refers to the number of values ​​​​of a[k] = x } in the range { [lhs, rhs].

Analysis:
Obviously:
1. f(1, i, a[i]) refers to how many values ​​there are in the number including a[i] before a[i] =a[i].
2. f(j, n, a[j]) refers to how many values ​​in the number including a[j] after a[j] = a[j].

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].

This becomes finding the number of situations that satisfy s1[i] > s[j], i < j. You will find that it is the same as finding the reverse order pairs. At this time, you can solve this problem by using a line segment tree or a tree array to find pairs of inverse ordinal numbers. If you don’t know how to solve the line segment tree, you can read: HDU 1394 Minimum Inversion Number (line segment tree finds the minimum inversion number pair).

Code:

/**  Author:      illuz <iilluzen[at]gmail.com>*  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<(n);i++)#define repu(i,a,b) for(int i=(a);i<(b);i++)#define repd(i,a,b) for(int i=(a);i>=(b);i--)typedef long long ll;#define lson(x) ((x) << 1)#define rson(x) ((x) << 1 | 1)const int N = 1e6 + 10;const int ROOT = 1;// below is sement point updated versionstruct seg {	ll w;};struct segment_tree { 	seg node[N << 2];	void update(int pos) {		node[pos].w = node[lson(pos)].w + node[rson(pos)].w;	}	void build(int l, int r, int pos) {		if (l == r) {			node[pos].w = 0;			return;		}		int m = (l + r) >> 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 <= m)			modify(l, m, lson(pos), x, y);		else			modify(m + 1, r, rson(pos), x, y);		update(pos);	}	// query the segment [x, y]	ll query(int l, int r, int pos, int x, int y) {		if (x <= l && r <= y)			return node[pos].w;		int m = (l + r) >> 1;		ll res = 0;		if (x <= m)			res += query(l, m, lson(pos), x, y);		if (y > 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 << s1[i] << ' ' << s2[i] << ' ' << ans << endl;		}		cout << ans << endl;	}	return 0;}

E - Pashmak and Graph

Question meaning:
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.

Analysis:
I just wrote a search map memoization, and then TLE QvQ...
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.

@bartyjuju:

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.
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.

Code:

/**  Author:      illuz <iilluzen[at]gmail.com>*  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<=(b);i++)const int N = 3e5 + 10;struct Edge {	int x;	int y;	int w;	bool operator <(const Edge& e) const {		return w < e.w;	}} e[N];int n, m;int edge[N], node[N];		// edges and nodes' dpint main() {	while (~scanf("%d%d", &n, &m)) {		memset(edge, 0, sizeof(edge));		memset(node, 0, sizeof(node));		repf (i, 1, m) {			scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].w);		}		sort(e + 1, e + m + 1);		repf (i, 1, m) {			int j = i;			while (j <= m && e[i].w == e[j].w) {		// update edges' dp				int x = e[j].x;				edge[j] = max(edge[j], node[x] + 1);				j++;			}			j = i;			while (j <= m && e[i].w == e[j].w) {		// update nodes' dp				int y = e[j].y;				node[y] = max(edge[j], node[y]);				j++;			}			i = j - 1;		}		int ans = 0;		repf (i, 1, m)			ans = max(ans, edge[i]);		printf("%d\n", ans);	}	return 0;}