Codeforces ラウンド #261 (ディビジョン 2)[ABCDE]_html/css_WEB-ITnose

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

ACM

質問アドレス: Codeforces Round #261 (Div. 2)

A - パシュマクと庭園

質問の意味:
正方形、その辺は平行この正方形の 2 つの点が与えられたときに、座標軸に移動して、他の 2 つの点を見つけます。

分析:
X 軸に平行か Y 軸に平行かを、さまざまな if で判断します。

コード:

/**  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 - パシュマックと花

質問:
n 個の数値から差が最大になるように 2 つの数値を取り出してください。 の合計を求める方法はいくつかあります。違い。
2 つの方法は、異なる位置に少なくとも 1 つの数字がある場合にのみ異なります。

分析:

差が最大値と最小値であることは明らかです。

2 つの数値が同じでない場合、メソッドは max_cnt * min_cnt です。
max_cnt * min_cnt には同じ方法の数値がいくつかあるため、同じ場合は注意してください。
例: 5 1 1 1 1 1。

1. すると、このように考えることができます。初回は 5 種類、2 回目は (5-1) を取ることができますが、ここでは (i,j) と (j,i) が取られており、したがって、Half を減算する必要があるため、結果は n*(n-1)/2 になります。
2. または、重複を避けるために、最初に取られる位置は 2 回目より前でなければならないと規定します。pos1 が初めて取られる場合、(n-1) のみとなります。クロックは次回取得できます。最初に取得した位置が pos2 の場合、2 回目は (n-2) になります。累積結果は (n-1)*n/2 になります。

コード:

/**  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 - パシュマックとバス

質問:
n 人が車に乗り、d 個の場所に行くために k 台の車があります。この日（FFFグループの勝利）、彼らの誰もずっと一緒にいなかったようにどうやって手配したのかと尋ねました。

分析:
d 行 n 列に相当し、各位置に 1 から k までの整数を入力します。完全に同じ 2 つの列はないことが必要です。
解決策がある限り、検索してください。

コード:

/**  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 - パシュマクとパルミダの問題

質問:
いくつかの数値 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 <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 と Graph

質問:
有向加重グラフが与えられた場合、最も長く増加するリンクの長さを見つけます。つまり、現在のエッジの重みは前のエッジよりも大きくなります。

分析:
検索 + マップのメモ化を書き、次に TLE QvQ...
実際、配列の dp を使用してそれを行うことができます。最初にエッジを小さいものから大きいものに並べ替えてから、小さいものはエッジをクラス化し、エッジ dp を実行してからポイント dp を更新します。

@bartyJuju:

エッジの重みに従ってすべてのエッジを小さいものから大きいものまで並べ替え、それらを順番にスキャンします。 繰り返されるエッジの重みがない場合、有向エッジ (u、v、d) については、直接使用できます。以前に計算されたポイント u+1 への最長パスを使用して、最長パスを v に更新します。
ただし、この質問は、すべてのエッジの重みが異なることを保証するものではありません。厳密な増加を保証するには、同じエッジの重みに対してバッファリング プロセスが必要です。

コード:

rree