vmware以及schlumberger题解

先是vmare的：具体的题目我就不描述了。

1. 贪吃的小明。直接数个数，统计个数，就可以完成。使用map，应该输入implement这一类，我认为很简单，但是我只过了33%。

 /*

 ID: y1197771

 PROG: test

 LANG: C++

 */

 #include<bits/stdc++.h>

 #define pb push_back

 #define FOR(i, n) for (int i = 0; i < (int)n; ++i)

 #define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl

 typedef long long ll;

 using namespace std;

 typedef pair<int, int> pii;

 const int maxn = 1e3 + ;

 string s[] = {"ONE", "TWO", "THREE", "FOUR", "FIVE", "SIX" };

 void solve() {

     int n, a, b, c;

     string s1, s2;

     a = b = c = ;

     map<string, int> m;

     cin >> n;

     for (int i = ; i < ; i++) m[s[i] ] = i;

     for (int i = ; i < n; i++) {

         cin >> s1 >> s2;

         if(m[s1] > m[s2]) a++;

         else if(m[s1] < m[s2]) b++;

         else c++;

     }

     cout << a << " " << b << " " << c << endl;

     if(b < a) {

         cout << "MingMing Win" << endl;

     } else {

         cout << "LiangLiang Win" << endl;

     }

 }

 int main() {

     //freopen("test.in", "r", stdin);

     //freopen("test.out", "w", stdout);

     solve();

     return ;

 }

2. 贾昆的谍报计划，可以从任意点开始，最长下降路径，更leetcode https://leetcode.com/problems/longest-increasing-path-in-a-matrix/这道题一致吧，我认为是一样，因为上升和下降是完全一致的。这题我也没100%ac，但是我写的在leetcode可以ac啊，我不知道什么情况。我好想知道怎么回事了，set判重导致的错误，换priority_queue就可以。

 /*

 ID: y1197771

 PROG: test

 LANG: C++

 */

 #include<bits/stdc++.h>

 #define pb push_back

 #define FOR(i, n) for (int i = 0; i < (int)n; ++i)

 #define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl

 typedef long long ll;

 using namespace std;

 typedef pair<int, int> pii;

 const int maxn = 1e3 + ;

 int a[][];

 int cnt[][];

 struct node {

     int v, x, y;

     bool operator<(const node & t) const {

         return v < t.v;

     }

 };

 int dx[] = {, , , -};

 int dy[] = {, , -, };

 void solve() {

     set<node> se;

     int n, m, x, y; cin >> n >> m;

     for (int i = ; i < n; i++) {

         for (int j = ; j < m; j++) {

             cin >> x; a[i][j] = x;

             se.insert({x, i, j});

             cnt[i][j] = ;

         }

     }

     int res = ;

     while(!se.empty()) {

             int p = se.begin()->v;

         x = se.begin()->x; y = se.begin()->y;

         //cout << p << " " << x << " " << y << " " << res << endl;

         res = max(res, cnt[x][y]);

         se.erase(se.begin());

         for (int i = ; i < ; i++) {

             int cx = x + dx[i], cy = y + dy[i];

             if(cx <  || cx >= n || cy <  || cy >= m) continue;

             if(a[cx][cy] <= p) continue;

             cnt[cx][cy] =  max(cnt[x][y] + , cnt[cx][cy]);

         }

     }

     cout << res << endl;

 }

 int main() {

     freopen("test.in", "r", stdin);

     //freopen("test.out", "w", stdout);

     solve();

     return ;

 }

3.旗帜计数，这道题比较变态，很难，后来查了一下，是cf原题，转移方程+快速幂，转移方程不好搞，链接在这里http://codeforces.com/problemset/problem/93/D注意，这题是div1的第4道题，当时ac的不到100人左右。

schlimberger

1. mumuchacha的珍珠手链，求固定窗口内最大值，直接滑动窗口O（1）的转移，很简单，或者是前缀和，代码难度比较低。直接过。

 /*

 ID: y1197771

 PROG: test

 LANG: C++

 */

 #include<bits/stdc++.h>

 #define pb push_back

 #define FOR(i, n) for (int i = 0; i < (int)n; ++i)

 #define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl

 typedef long long ll;

 using namespace std;

 typedef pair<int, int> pii;

 const int maxn = 1e5 + ;

 int n, m;

 int a[maxn * ];

 void solve() {

     int cur = ;

     cin >> n >> m;

     for (int i = ; i <= n; i++) {

         cin >> a[i];

         a[i + n] = a[i];

         if(i < m) cur += a[i];

     }

     int res = a[];

     for (int i = m; i <= n + m; i++) {

         cur += a[i];

         if(i - m > ) cur -= a[i - m];

         res = max(res, cur);

     }

     cout << res << endl;

 }

 int main() {

     //freopen("test.in", "r", stdin);

     //freopen("test.out", "w", stdout);

     int i; cin >> i;

     while(i--)

     solve();

     return ;

 }

2. 量子通讯工程，看完题目，就是写一个kruskal或者prim来求mst。好久没写，发现都不会写了，刚好对dsu比较熟，就写了prim。

 /*

 ID: y1197771

 PROG: test

 LANG: C++

 */

 #include<bits/stdc++.h>

 #define pb push_back

 #define FOR(i, n) for (int i = 0; i < (int)n; ++i)

 #define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl

 typedef long long ll;

 using namespace std;

 typedef pair<double, double> pii;

 const int maxn = 1e3 + ;

 double d[][];

 int n;

 vector<pair<double, double>> a;

 double work(pii x, pii y) {

     return sqrt((x.first - y.first) * (x.first - y.first) + (x.second - y.second) * ((x.second - y.second)) );

 }

 bool vis[];

 int f[maxn];

 int fd(int x) {

     if(x == f[x]) return f[x];

     return f[x] = fd(f[x]);

 }

 struct node {

     double d;

     int x, y;

     bool operator <(const node & t) const {

         return d < t.d;

     }

 } e[];

 void solve() {

     cin >> n;

     double x, y;

     for (int i = ; i < n; i++) {

         cin >> x >> y;

         a.pb({x, y});

         f[i] = i;

     }

     int num = ;

     for (int i = ; i < n; i++) {

         for (int j = i + ; j < n; j++) {

             double t = work(a[i], a[j]);

             e[num].d = t; e[num].x = i, e[num].y = j;

             num++;

         }

     }

     sort(e, e + num);

     double res = ;

     for (int i = ; i < num; i++) {

         int a1 = e[i].x, a2 = e[i].y;

         x = e[i].d;

         a1 = fd(a1); a2 = fd(a2);

         if(a1 != a2) {

             //cout << e[i].x << " " << e[i].y << " " << x << endl;

             f[a1] = a2;

             res += x;

         }

     }

     printf("%.2f\n", res);

 }

 int main() {

     //freopen("test.in", "r", stdin);

     //freopen("test.out", "w", stdout);

     solve();

     return ;

 }

也是直接过。

3. 下载管理软件，读题，主要是：任何下载的时候带宽都是满的，但是并行度个数有限制，然后我就想：直接模拟吧，按结束时间加入set进行模型，调了一个小时才过了33%。后来听师兄讲解，就是所有的任务加起来除以总带宽，那个并行度属于干扰项，我很惊讶，原来还可以这样！

写出来的有效代码不到5行，而我字节写的模拟，洋洋洒洒快到100行了。衰！

 /*

 ID: y1197771

 PROG: test

 LANG: C++

 */

 #include<bits/stdc++.h>

 #define pb push_back

 #define FOR(i, n) for (int i = 0; i < (int)n; ++i)

 #define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl

 typedef long long ll;

 using namespace std;

 typedef pair<int, int> pii;

 const int maxn = 1e3 + ;

 void solve() {

     int t, n, w;

     double s = ;

     cin >> t >> n >> w;

     double task; int p;

     for (int i = ; i < t; i++) {

         cin >> task >> p;

         s += task * ( - p) / ;

     }

     printf("%.2f\n", s / w);

 }

 int main() {

     freopen("test.in", "r", stdin);

     //freopen("test.out", "w", stdout);

     solve();

     return ;

 }

http://ideone.com/ZqRTBn

巴特西

vmware以及schlumberger题解

最新文章

热门文章