本文共 5804 字，大约阅读时间需要 19 分钟。
热门号码
#include #include #include #include #include #include #include #include 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 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 #include #include #include #include #include #include #include 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 #include #include #include #include #include #include #include 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 mp;vector G[50005], H[500005];int k[50005], d[50005];bool fw[50005], fs[500005];queue 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 #include #include #include #include #include #include #include #include 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 mp;vector G[100005];vector 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;}
转载于:https://www.cnblogs.com/dramstadt/p/7902603.html
