当前位置:Gxlcms > mysql > CodeforcesRound#261(Div.2)[ABCDE]

CodeforcesRound#261(Div.2)[ABCDE]

时间:2021-07-01 10:21:17 帮助过:17人阅读

Codeforces Round #261 (Div. 2)[ABCDE] ACM 题目地址:Codeforces Round #261 (Div. 2) A - Pashmak and Garden 题意 : 一个正方形,它的边平行于坐标轴,给出这个正方形的两个点,求出另外两个点。 分析 : 判断下是否平行X轴或平行Y轴,各种if。 代码 :

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。

  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 
*  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
#include
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

题意
给出一些数a[n],求(i, j),i的数量,使得: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 
*  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 version
struct 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' dp

int 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;
}

人气教程排行