prom-main

微软编程之美热身赛

今年的赛季又开始了,只是轻度参与一下,骗件衣服穿穿,顺道权当做一下记忆修复,维护一下技能。

编程之美、TCO、GCJ 都已经有 schedule 了,今天清明扫墓归来,正好测试一下今年编程之美的平台,做了一下热身赛。

赛题挺有意思的,前两题难度不大,第三题感觉相当于 SRM 500 的难度左右,也挺有意思。反正做完了,做一下笔录。

题目和源代码都打包放在这里:warmup

第一题:传话游戏

这道题挺简单的,就是有一个字典,从一个源单词映射到一个目标单词。

然后给出一句话,每传一次,其中的每个单词就要从字典里面映射一次,有 N 个人,映射 N-1 次即可,主要是编码,没什么算法可言。

#include

include

include

include

include

using namespace std;

int main() { int T, N, M; map<string, string> mp; cin >> T; for(int t = 0; t < T; ++t) { cin >> N >> M >> ws; mp.clear(); for(int i = 0; i < M; ++i) { string a, b; cin >> a >> b >> ws; mp[a] = b; } string line; getline(cin, line); istringstream strin(line); cout << "Case #" << t+1 << ":"; while(strin >> line) { for(int i = 1; i < N; ++i) { map<string, string>::iterator it = mp.find(line); if(it != mp.end()) line = it->second; } cout << ' ' << line; } cout << endl; } return 0; }

第二题:长方形

这道题,给出一个 N x M 的坐标网格,给 K 个点,要将 K 个点放到这个阵里面去,使得可以构成四个顶点都属于 K 个点里面,而且边平行坐标轴的矩形数量最多,返回最多的矩形数量。

这个也不难,但是容易错,开始想当然让形状靠近正方形就会是最优解 O(1),但发现其实不对,然后修改了一下,枚举所有宽度,然后顺着放满,这样来便利一次来得到最优解 O(N),这样就过了,也完全不难。

#include

include

using namespace std;

typedef long long i64;

i64 c2(i64 m) { if(m < 2) return 0; else return m * (m-1) / 2; }

i64 T, N, M, K;

i64 test(i64 w) { i64 h = K / w; i64 d = K - w*h; if(d && h+1 > M || !d && h > M) return 0; return c2(w) * c2(h) + c2(d) * h; }

int main() { cin >> T; for(i64 t = 0; t < T; ++t) { cin >> N >> M >> K; if(N > M) swap(N, M); i64 ans = 0; for(i64 w = 1; w <= N; ++w) ans = max(ans, test(w)); cout << "Case #" << t+1 << ": " << ans << endl; } return 0; }

第三题:树上的三角形

这道题就有意思了,给出一棵无根树(顶点数最多 100000 个),边有一个整数权重,然后给出 Q 次查询(最多 100000 次),给出两个顶点,问它们之间的路径抽出来的边能否构成一个三角形。

开始想不到办法,各种折腾就不加描述了。然后想到了,直接说结果:

关键点在于,构成不了三角形的情况最坏的就是 1,1,2,3,5,8… 正好是一个 Fibonacci 数列!那么就是说,由于最长的边不超过 1000000000,也就是不超过 Fib(45) 左右,这意味着只要一条路径包括超过 45 条边,不用看就一定可以满足结果!

然后其他情况就是常规处理办法,但是常规处理办法也是要讲究效率的。所以我们就把节点 0 拉起来,用一次 dfs 把这棵树重构成一个有根树,记录好父链和节点高度。这样我们做一次 LCA(真佩服自己,还是没用模板自己把 LCA 写出来了,也不是很费劲)。

这样,每次查询节点 x – y,找到最近公共祖先 z,然后通过 (height(x)-height(z))+(height(y)-height(z)) 得到的就是 x 到 y 的路径长度 O(log(N)),如果长度大于 45 直接就输出 Yes,否则从 x 和 y 分别通过父链上溯到 z 可以得到不超过 45 个元素的列表,直接暴力排序测算一下能不能构成三角形,输出结果就可以了。

那么整体的算法效率:

DFS 有根化:O(N) 时间+空间

LCA:O(N*log(N)) 时间+空间

每次查询(考虑排序):O(log(N)45log(45))

这样的效率应该就可以接受过得了大数据了,下面是代码:

#include

include

include

using namespace std;

struct Edge { int x, y, d; Edge(int x=0, int y=0, int d=0) : x(x), y(y), d(d) {} };

bool operator < (const Edge& lhs, const Edge& rhs) { return lhs.x<rhs.x || lhs.x==rhs.x && lhs.y<rhs.y; }

int T, N, M, K; Edge ee[200000], *ptr; int _lca[20][100000], hgt[100000], len[100000], *pre = _lca[0]; int mxh, mxb; int stk[100], sz;

void dfs(const int& k) { for(Edge *p = lower_bound(ee, ee+N+N-2, Edge(k)); p->x == k; ++p) { if(pre[p->y] == -1) { pre[p->y] = k; hgt[p->y] = hgt[k]+1; len[p->y] = p->d; dfs(p->y); mxh = max(mxh, hgt[p->y]); } } }

int lca(int v, int w) { if(hgt[v] < hgt[w]) swap(v, w); for(int b = mxb; hgt[v] > hgt[w] && b >= 0; --b) if(hgt[v] - (1<<b) >= hgt[w]) v = _lca[b][v]; for(int b = mxb; v != w && b >= 0; --b) if(_lca[b][v] != -1 && _lca[b][v] != _lca[b][w]) v = _lca[b][v], w = _lca[b][w]; return v==w ? v : pre[v]; }

int main() { scanf("%d", &T); for(int t = 0; t < T; ++t) { printf("Case #%d:\n", t+1); scanf("%d", &N); ptr = ee; for(int i = 1, x, y, d; i < N; ++i) { scanf("%d%d%d", &x, &y, &d); ptr->x = x-1; ptr->y = y-1; ptr->d = d; ++ptr; ptr->y = x-1; ptr->x = y-1; ptr->d = d; ++ptr; } sort(ee, ee+N+N-2); // init_tree memset(pre, -1, sizeof(int)*N); pre[0] = hgt[0] = len[0] = mxh = 0; dfs(0); // init_lca pre[0] = 0; for(int b = 1; (1<<b)<=mxh; ++b) { mxb = b; for(int i = 0, p; i < N; ++i) { p = _lca[b-1][i]; _lca[b][i] = p==-1 ? -1 : _lca[b-1][p]; } } // do query for(scanf("%d", &M); M--;) { int x, y; scanf("%d%d", &x, &y); int z = lca(--x, --y); if(hgt[x]+hgt[y]-hgt[z]-hgt[z] > 45) { puts("Yes"); continue; } sz = 0; while(x != z) { stk[sz++] = len[x]; x = pre[x]; } while(y != z) { stk[sz++] = len[y]; y = pre[y]; } sort(stk, stk+sz); bool yes = false; for(int i = 2; !yes && i < sz; ++i) if(stk[i-2]+stk[i-1] > stk[i]) yes = true; puts(yes ? "Yes" : "No"); }

}
return 0;

}


【转载请附】愿以此功德,回向 >>

原文链接:https://www.huangwenchao.com.cn/2014/04/ms2014-warmup.html【微软编程之美热身赛】

发表评论

电子邮件地址不会被公开。 必填项已用*标注