[Offer收割]编程练习赛37

热门号码

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<vector>
#include<algorithm>
#include<iostream>
#include<map>
#include<queue>
using std::vector;
using std::queue;
using std::map;
using std::sort;
int cmp(const void * x, const void * y) {
//x < y
#define datatype int
return (*((datatype *)(x))) > (*((datatype *)(y))) ? 1 : -1;
#undef datatype
}
map<long long, int> mp;
char str[15];
const int num[26] = {2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 9, 9, 9, 9};
int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
int n, m, l;
    scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) {
        scanf("%s", str);
        l = strlen(str);
long long tmp = 0;
for (int j = 0; j < l; j++) {
            tmp = tmp * 10 + num[str[j] - 'A'];
        }
        mp[tmp]++;
    }
for (int i = 0; i < m; i++) {
long long tmp;
        scanf("%lld", &tmp);
        printf("%d\n", mp[tmp]);
    }
return 0;
}

三角形面积和

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<vector>
#include<algorithm>
#include<iostream>
#include<map>
#include<queue>
using std::vector;
using std::queue;
using std::map;
using std::sort;
#define read(x) scanf("%d",&x)
struct point {
int x, y;
};
int cmp(const void * x, const void * y) {
#define datatype point
    datatype dx = *((datatype *)(x)), dy = *((datatype *)(y));
//x < y
return dx.x - dx.y > dy.x - dy.y ? 1 : -1;
#undef datatype
}

point p[100005];
int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
int n;
    read(n);
for (int i = 0; i < n; i++) {
        read(p[i].x);
        read(p[i].y);
    }
    qsort(p, n, sizeof(point), cmp);
double ans = 0;
int ptr = 0;
while (ptr < n) {
double a = p[ptr].x + p[ptr].y;
int j;
bool find = false;
for (j = ptr + 1; j < n; j++) {
if (p[j].x + p[j].y <= a) continue;
if (p[j].x - p[j].y >= p[ptr].x + p[ptr].y) {
                ans += p[ptr].y * p[ptr].y;
                find = true;
break;
            }
double b = p[j].y - p[j].x;
            ans += p[ptr].y * p[ptr].y - (a + b) * (a + b) / 4;
            find = true;
break;
        }
if (!find) ans += p[ptr].y * p[ptr].y;
        ptr = j;
    }
    printf("%.2lf\n", ans);
return 0;
}

最少换乘

其实很简单，但是最多50w个站编号却是1-500w，这就是map牛逼的地方了呀。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<vector>
#include<algorithm>
#include<iostream>
#include<map>
#include<queue>
using std::vector;
using std::queue;
using std::map;
using std::sort;
#define read(x) scanf("%d",&x)
struct point {
int x, y;
};
int cmp(const void * x, const void * y) {
#define datatype point
    datatype dx = *((datatype *)(x)), dy = *((datatype *)(y));
//x < y
return dx.x - dx.y > dy.x - dy.y ? 1 : -1;
#undef datatype
}
map<int, int> mp;
vector<int> G[50005], H[500005];
int k[50005], d[50005];
bool fw[50005], fs[500005];
queue<int> q;
int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
int n, s, e, p, cnt = 0;
    read(n);
    read(s);
    read(e);
for (int i = 0; i < n; i++) {
        read(k[i]);
for (int j = 0; j < k[i]; j++) {
            read(p);
            G[i].push_back(p);
if (mp.find(p) == mp.end()) {
                mp[p] = cnt++;
            }
            H[mp[p]].push_back(i);
        }
    }
    memset(d, 0x3F, sizeof(d));
while (!q.empty()) q.pop();
    memset(fw, false, sizeof(fw));
    memset(fs, false, sizeof(fs));
int mps = mp[s];
for (int i = 0; i < H[mps].size(); i++) {
        d[H[mps][i]] = 0;
        q.push(H[mps][i]);
        fw[H[mps][i]] = true;
    }
while (!q.empty()) {
int x = q.front();
        q.pop();
for (int i = 0; i < G[x].size(); i++) {
int v = G[x][i];
int mpv = mp[v];
if (fs[mpv]) continue;
            fs[mpv] = true;
for (int j = 0; j < H[mpv].size(); j++) {
int w = H[mpv][j];
if (fw[w]) continue;
if (d[w] > d[x] + 1) {
                    d[w] = d[x] + 1;
                    fw[w] = true;
                    q.push(w);
                }
            }
        }
    }
int ans = 0x3FFFFFFF;
int mpe = mp[e];
for (int i = 0; i < H[mpe].size(); i++) {
if (d[H[mpe][i]] < ans) ans = d[H[mpe][i]];
    }
    printf("%d\n",ans);
return 0;
}

完美命名的烦恼

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<vector>
#include<algorithm>
#include<iostream>
#include<map>
#include<queue>
#include<string>
using std::vector;
using std::queue;
using std::map;
using std::sort;
using std::string;
#define read(x) scanf("%d",&x)
#define reads(x) scanf("%s",x)

int cmp(const void * x, const void * y) {
#define datatype int
    datatype dx = *((datatype *)(x)), dy = *((datatype *)(y));
//x < y
return dx > dy ? 1 : -1;
#undef datatype
}

char str[15];
map<string, int> mp;
vector<int> G[100005];
vector<bool> v[100005];
string sg[100005];
int din[100005], dout[100005], m = 0;
char ans[100005];
void dfs(int x) {
for (int i = 0; i < G[x].size(); i++) {
if (v[x][i]) continue;
        v[x][i] = true;
        dfs(G[x][i]);
    }
    ans[m++] = sg[x][sg[x].size() - 1];
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
int n, cnt = 0, s = -1, e = -1;
bool flag = false;
    read(n);
for (int i = 0; i < 2 * n; i++) G[i].clear();
for (int i = 0; i < n; i++) {
        reads(str);
int len = strlen(str);
if (len == 1) {
            printf("%s", str);
            flag = true;
continue;
        }
string s(str);
string sl = s.substr(0, len - 1);
string sr = s.substr(1, len);
if (mp.find(sl) == mp.end()) {
            mp[sl] = cnt;
            sg[cnt] = sl;
            cnt++;
        }
if (mp.find(sr) == mp.end()) {
            mp[sr] = cnt;
            sg[cnt] = sr;
            cnt++;
        }
int mpl = mp[sl], mpr = mp[sr];
        G[mpl].push_back(mpr);
        v[mpl].push_back(false);
        dout[mpl]++, din[mpr]++;
    }
if (flag) return 0;
for (int i = 0; i < cnt; i++) {
if (din[i] == dout[i]) continue;
if (din[i] - dout[i] > 1 || dout[i] - din[i] > 1) {
            printf("NO\n");
return 0;
        }
if (din[i] - dout[i] == 1) {
if (e == -1) e = i;
else {
                printf("NO\n");
return 0;
            }
        }
if (dout[i] - din[i] == 1) {
if (s == -1) s = i;
else {
                printf("NO\n");
return 0;
            }
        }
    }
if (s == -1) s = 0;
    dfs(s);
for (int i = sg[s].size() - 2; i >= 0; i--) ans[m++] = sg[s][i];
for (int i = m - 1; i >= 0; i--) printf("%c", ans[i]);
return 0;
}