昨天做TC手一抖浪费了涨rating的大好机会, 本来三题都会的500pt写挂了, 有个小bug, 1000pt本来就打算试试的最后没调试完, 其实再有一分钟就能debug完的, 最后只出了一题, 悲剧啊。
250pt: 水, 不解释
500pt:第一次在SRM上遇上图论, 最后没A真可惜, 这题我的做法就是先判断所有人形成的联通分量个数如果大于1就输出-1(两个没关系的人的差值可以为INF),否则考虑任意两个人的最大差距, 不难发现和两人间的最短路有关, 用Floyd求个最短路就解了。
#include <vector> #include <cstring> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> using namespace std; class Egalitarianism { public: int maxDifference(vector <string>, int); }; const int N = 55; const int INF = 1 << 29; int dis[N][N]; bool vis[N]; void dfs(int u, int n) { vis[u] = 1; for (int i = 0; i < n; i++) { if (!vis[i] && dis[u][i] == 1) dfs(i, n); } } int Egalitarianism::maxDifference(vector<string> vec, int d) { int n = vec.size(); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) dis[i][j] = INF; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (vec[i][j] == 'Y') { dis[i][j] = 1; dis[j][i] = 1; } memset(vis, 0, sizeof(vis)); int cnt = 0; for (int i = 0; i < n; i++) if (!vis[i]) { dfs(i, n); cnt++; } if (cnt > 1) return -1; for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]); int ans = 0; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (dis[i][j] != INF && i != j) ans = max(ans, dis[i][j]); return ans * d; } <%:testing-code%> //Powered by [KawigiEdit] 2.0!
1000pts:是个组合计数题目题意很难懂, 最后只想到了个类似暴力的dfs解法估计会T的没想到过了看了下时间最慢的一组跑了1.4秒, 应该不是正解。。。
#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <cstring> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> using namespace std; class Excavations2 { public: long long count(vector <int>, vector <int>, int); }; typedef long long LL; const int N = 55; LL C[N][N]; int n; int sum[N]; LL res; void init() { for (int i = 0; i < N; i++) { C[i][0] = C[i][i] = 1; for (int j = 1; j < i; j++) C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; } memset(sum, 0, sizeof(sum)); } void dfs(int d, int k, LL tmp, int cnt) { if (d == n - 1) { if (cnt < k) { res += tmp * C[sum[d]][k - cnt]; } return; } for (int i = 1; i <= sum[d]; i++) { if (i + cnt >= k) break; dfs(d + 1, k, tmp * C[sum[d]][i], cnt + i); } } long long Excavations2::count(vector<int> kind, vector<int> found, int K) { init(); n = found.size(); for (int i = 0; i < kind.size(); i++) { int typ = kind[i]; for (int j = 0; j < n; j++) if (found[j] == typ) { sum[j]++; break; } } res = 0LL; dfs(0, K, 1, 0); return res; } <%:testing-code%> //Powered by [KawigiEdit] 2.0!