首页 > 代码库 > vmware以及schlumberger题解
vmware以及schlumberger题解
先是vmare的:具体的题目我就不描述了。
1. 贪吃的小明。直接数个数,统计个数,就可以完成。使用map,应该输入implement这一类,我认为很简单,但是我只过了33%。
1 /* 2 ID: y1197771 3 PROG: test 4 LANG: C++ 5 */ 6 #include<bits/stdc++.h> 7 #define pb push_back 8 #define FOR(i, n) for (int i = 0; i < (int)n; ++i) 9 #define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl10 typedef long long ll;11 using namespace std;12 typedef pair<int, int> pii;13 const int maxn = 1e3 + 10;14 string s[] = {"ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX" };15 void solve() {16 int n, a, b, c;17 string s1, s2;18 a = b = c = 0;19 map<string, int> m;20 cin >> n;21 for (int i = 0; i < 6; i++) m[s[i] ] = i;22 for (int i = 0; i < n; i++) {23 cin >> s1 >> s2;24 if(m[s1] > m[s2]) a++;25 else if(m[s1] < m[s2]) b++;26 else c++;27 }28 cout << a << " " << b << " " << c << endl;29 if(b < a) {30 cout << "MingMing Win" << endl;31 } else {32 cout << "LiangLiang Win" << endl;33 }34 35 }36 int main() {37 //freopen("test.in", "r", stdin);38 //freopen("test.out", "w", stdout);39 solve();40 return 0;41 }
2. 贾昆的谍报计划,可以从任意点开始,最长下降路径,更leetcode https://leetcode.com/problems/longest-increasing-path-in-a-matrix/这道题一致吧, 我认为是一样,因为上升和下降是完全一致的。这题我也没100%ac,但是我写的在leetcode可以ac啊,我不知道什么情况。我好想知道怎么回事了,set判重导致的错误,换priority_queue就可以。
1 /* 2 ID: y1197771 3 PROG: test 4 LANG: C++ 5 */ 6 #include<bits/stdc++.h> 7 #define pb push_back 8 #define FOR(i, n) for (int i = 0; i < (int)n; ++i) 9 #define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl10 typedef long long ll;11 using namespace std;12 typedef pair<int, int> pii;13 const int maxn = 1e3 + 10;14 int a[510][510];15 int cnt[510][510];16 struct node {17 int v, x, y;18 bool operator<(const node & t) const {19 return v < t.v;20 }21 };22 int dx[] = {0, 1, 0, -1};23 int dy[] = {1, 0, -1, 0};24 void solve() {25 set<node> se;26 int n, m, x, y; cin >> n >> m;27 for (int i = 0; i < n; i++) {28 for (int j = 0; j < m; j++) {29 cin >> x; a[i][j] = x;30 se.insert({x, i, j});31 cnt[i][j] = 1;32 }33 }34 int res = 0;35 while(!se.empty()) {36 int p = se.begin()->v;37 x = se.begin()->x; y = se.begin()->y;38 //cout << p << " " << x << " " << y << " " << res << endl;39 res = max(res, cnt[x][y]);40 se.erase(se.begin());41 for (int i = 0; i < 4; i++) {42 int cx = x + dx[i], cy = y + dy[i];43 if(cx < 0 || cx >= n || cy < 0 || cy >= m) continue;44 if(a[cx][cy] <= p) continue;45 cnt[cx][cy] = max(cnt[x][y] + 1, cnt[cx][cy]);46 }47 }48 cout << res << endl;49 }50 int main() {51 freopen("test.in", "r", stdin);52 //freopen("test.out", "w", stdout);53 solve();54 return 0;55 }
3.旗帜计数,这道题比较变态,很难,后来查了一下,是cf原题,转移方程+快速幂,转移方程不好搞,链接在这里http://codeforces.com/problemset/problem/93/D注意,这题是div1的第4道题,当时ac的不到100人左右。
schlimberger
1. mumuchacha的珍珠手链,求固定窗口内最大值,直接滑动窗口O(1)的转移,很简单,或者是前缀和,代码难度比较低。直接过。
1 /* 2 ID: y1197771 3 PROG: test 4 LANG: C++ 5 */ 6 #include<bits/stdc++.h> 7 #define pb push_back 8 #define FOR(i, n) for (int i = 0; i < (int)n; ++i) 9 #define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl10 typedef long long ll;11 using namespace std;12 typedef pair<int, int> pii;13 const int maxn = 1e5 + 10;14 int n, m;15 int a[maxn * 2];16 void solve() {17 int cur = 0;18 cin >> n >> m;19 for (int i = 1; i <= n; i++) {20 cin >> a[i];21 a[i + n] = a[i];22 if(i < m) cur += a[i];23 }24 int res = a[1];25 for (int i = m; i <= n + m; i++) {26 cur += a[i];27 if(i - m > 0) cur -= a[i - m];28 res = max(res, cur);29 }30 cout << res << endl;31 32 33 }34 int main() {35 //freopen("test.in", "r", stdin);36 //freopen("test.out", "w", stdout);37 int i; cin >> i;38 while(i--)39 solve();40 return 0;41 }
2. 量子通讯工程,看完题目,就是写一个kruskal或者prim来求mst。 好久没写,发现都不会写了,刚好对dsu比较熟,就写了prim。
1 /* 2 ID: y1197771 3 PROG: test 4 LANG: C++ 5 */ 6 #include<bits/stdc++.h> 7 #define pb push_back 8 #define FOR(i, n) for (int i = 0; i < (int)n; ++i) 9 #define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl10 typedef long long ll;11 using namespace std;12 typedef pair<double, double> pii;13 const int maxn = 1e3 + 10;14 double d[110][110];15 int n;16 vector<pair<double, double>> a;17 double work(pii x, pii y) {18 return sqrt((x.first - y.first) * (x.first - y.first) + (x.second - y.second) * ((x.second - y.second)) );19 }20 bool vis[110];21 int f[maxn];22 int fd(int x) {23 if(x == f[x]) return f[x];24 return f[x] = fd(f[x]);25 }26 struct node {27 double d;28 int x, y;29 bool operator <(const node & t) const {30 return d < t.d;31 }32 } e[10000];33 void solve() {34 cin >> n;35 double x, y;36 for (int i = 0; i < n; i++) {37 cin >> x >> y;38 a.pb({x, y});39 f[i] = i;40 }41 int num = 0;42 for (int i = 0; i < n; i++) {43 for (int j = i + 1; j < n; j++) {44 double t = work(a[i], a[j]);45 e[num].d = t; e[num].x = i, e[num].y = j;46 num++;47 }48 }49 sort(e, e + num);50 double res = 0;51 for (int i = 0; i < num; i++) {52 int a1 = e[i].x, a2 = e[i].y;53 x = e[i].d;54 a1 = fd(a1); a2 = fd(a2);55 if(a1 != a2) {56 //cout << e[i].x << " " << e[i].y << " " << x << endl;57 f[a1] = a2;58 res += x;59 }60 }61 printf("%.2f\n", res);62 63 }64 int main() {65 //freopen("test.in", "r", stdin);66 //freopen("test.out", "w", stdout);67 solve();68 return 0;69 }
也是直接过。
3. 下载管理软件,读题,主要到:任何下载的时候带宽都是满的,但是并行度个数有限制,然后我就想:直接模型吧,按结束时间加入set进行模型,调了一个小时才过了33%。后来听师兄讲解,就是所有的任务加起来除以总带宽,那个并行度属于干扰项,我很惊讶,原来还可以这样!
写出来的有效代码不到5行,而我字节写的模拟,洋洋洒洒快到100行了。衰!
1 /* 2 ID: y1197771 3 PROG: test 4 LANG: C++ 5 */ 6 #include<bits/stdc++.h> 7 #define pb push_back 8 #define FOR(i, n) for (int i = 0; i < (int)n; ++i) 9 #define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl10 typedef long long ll;11 using namespace std;12 typedef pair<int, int> pii;13 const int maxn = 1e3 + 10;14 void solve() {15 int t, n, w;16 double s = 0;17 cin >> t >> n >> w;18 double task; int p;19 for (int i = 0; i < t; i++) {20 cin >> task >> p;21 s += task * (100 - p) / 100;22 }23 printf("%.2f\n", s / w);24 }25 int main() {26 freopen("test.in", "r", stdin);27 //freopen("test.out", "w", stdout);28 solve();29 return 0;30 }
http://ideone.com/ZqRTBn
vmware以及schlumberger题解