首页 / HTML / CodeforcesRound#261(Div.2)[ABCDE]_html/css_WEB-ITnose

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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了CodeforcesRound#261(Div.2)[ABCDE]_html/css_WEB-ITnose，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含7402字，纯文字阅读大概需要11分钟。

内容图文

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

ACM

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

A - Pashmak and Garden

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

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

代码：

/**  Author:      illuz <iilluzen[at]gmail.com>*  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。

  1. 那么我们可以这样考虑，第一次可以取5种，第二次可以取(5-1)钟，但是这里面(i,j)和(j,i)都取过，所以得减半，所以结果就是n*(n-1)/2。
  2. 或者可以这样考虑，我们为了不要取重复，规定第一次取的位置肯定在第二次前面，如果第一次取pos1，那么下次只能取(n-1)钟；如果第一次取pos2，第二次就(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 #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 <iilluzen[at]gmail.com>*  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<j的数量，使得：f(1, i, a[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 <iilluzen[at]gmail.com>*  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<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

题意：
给出一个有向带权值的图，要求出最长递增链路的长度。也就是当前边的权值要大于前一条边的。

分析：
刚开始写了个搜索+map记忆化，然后就TLE了QvQ...
其实可以用数组的dp来做，先对边从小到大排序，从小到达处理，对于相同的一类边，进行对边dp，然后更新对点dp。

@barty巨巨：

将所有边按边权从小到大排序，顺序扫描，如果没有重复边权的话，对于(u, v, d)这条有向边，可以直接用之前求的到u点的最长路径+1来更新到v的最长路径。
不过题目中没有保证所有边权不同，为了保证严格递增，所以对于相同边权需要做一个缓冲处理。

代码：

/**  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 #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;}

内容总结

以上是互联网集市为您收集整理的CodeforcesRound#261(Div.2)[ABCDE]_html/css_WEB-ITnose全部内容，希望文章能够帮你解决CodeforcesRound#261(Div.2)[ABCDE]_html/css_WEB-ITnose所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/398446.html

来源：【匿名】