Codeforces Round #261 (Div. 2)[ABCDE]
acm
题目地址:Codeforces Round #261 (Div. 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;}
题意：
在n个数中取出两个数，使得差值最大，问差值和有几种取法。
两种取法不同当且仅当：两种方法至少有一个不同位置的数。
分析：
很明显差值就是最大-最小。
如果两个数不是相同的，那么取法就是max_cnt * min_cnt了。
如果相同就要注意了，因为max_cnt * min_cnt里面有一些取法一样的数。
比如：5 1 1 1 1 1。
代码：
立即学习“前端免费学习笔记（深入）”；
/** 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;}
题意：
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<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;}
题意：
给出一些数a[n]，求(i, j),i
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;}
题意：
给出一个有向带权值的图，要求出最长递增链路的长度。也就是当前边的权值要大于前一条边的。
分析：
刚开始写了个搜索+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 <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;}
HTML怎么学习？HTML怎么入门？HTML在哪学？HTML怎么学才快？不用担心，这里为大家提供了HTML速学教程(入门课程)，有需要的小伙伴保存下载就能学习啦！
广告
收藏
收藏
收藏
Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
344
