首页 > 代码库 > 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 }
View Code

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 }
View Code

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 }
View Code

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 }
View Code

也是直接过。

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 }
View Code

http://ideone.com/ZqRTBn

vmware以及schlumberger题解