CodeforcesRound#261(Div.2)[ABCDE]_html/css

來源：懂視網責編：小采時間：2020-11-27 15:54:47

CodeforcesRound#261(Div.2)[ABCDE]_html/css

CodeforcesRound#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軸，各種

推薦度：

點擊下載本文 文檔為doc格式

導讀CodeforcesRound#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軸，各種

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

題意：
在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<=(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

題意：
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; 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

題意：
給出一些數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 < j情況的數量了,你會發現跟求逆序對一樣了。這時就可以用線段樹或樹狀數組求逆序數對的方法解決這個問題了。不懂線段樹怎么解的可以看：HDU 1394 Minimum Inversion Number（線段樹求最小逆序數對）。

代碼：

/** Author: illuz * File: D.cpp* Create Date: 2014-08-16 00:18:08* Descripton: */#include #include #include #include #include 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 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

題意：
給出一個有向帶權值的圖，要求出最長遞增鏈路的長度。也就是當前邊的權值要大于前一條邊的。

分析：
剛開始寫了個搜索+map記憶化，然后就TLE了QvQ...
其實可以用數組的dp來做，先對邊從小到大排序，從小到達處理，對于相同的一類邊，進行對邊dp，然后更新對點dp。

@barty巨巨：

將所有邊按邊權從小到大排序，順序掃描，如果沒有重復邊權的話，對于(u, v, d)這條有向邊，可以直接用之前求的到u點的最長路徑+1來更新到v的最長路徑。
不過題目中沒有保證所有邊權不同，為了保證嚴格遞增，所以對于相同邊權需要做一個緩沖處理。

代碼：

/** Author: illuz * Blog: http://blog.csdn.net/hcbbt* File: E.cpp* Create Date: 2014-08-16 09:43:59* Descripton: */#include #include #include #include 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;}

聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com