9.9 京东笔试编程题

72 阅读 0 评论 48 点赞

我是靠谱客的博主悦耳野狼，最近开发中收集的这篇文章主要介绍9.9 京东笔试编程题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

这里写图片描述

思路: 结果就是补图的联通快都是团
但是数据有点水, 我用这种遍历方法也给过了

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <bitset>
// #include <unistd.h>
#include <unordered_map>
using namespace std;
#define LL long long
#define pb push_back
#define mk make_pair
#define pill pair<int, int>
#define fi first
#define se second
#define mst(a, b) memset(a, b, sizeof a)
#define lson (rt << 1)
#define rson ((rt << 1) | 1)
const int qq = 1e3 + 10;
const int INF = 1e9 + 10;
const int MOD = 1e9 + 7;
int n, m;
int mar[qq][qq];
int main() {
#ifdef ONLINE_JUDGE
#else
freopen("in.txt", "r", stdin);
#endif
int t;
scanf("%d", &t);
while (t--) {
scanf("%d%d", &n, &m);
for (int i = 1, a, b; i <= m; ++i) {
scanf("%d%d", &a, &b);
mar[a][b] = mar[b][a] = 1;
}
bool f = true;
for (int i = 1; i <= n && f; ++i) {
vector<int> node;
for (int j = 1; j <= n; ++j) {
if (i == j || mar[i][j])
continue;
node.pb(j);
}
for (int j = 1; j <= n && f; ++j) {
if (i == j || !mar[i][j])
continue;
for (int k = 0; k < node.size() && f; ++k) {
if (!mar[j][node[k]])
f = false;
}
}
}
if (f)
puts("Yes");
else
puts("No");
mst(mar, 0);
}
return 0;
}

这里写图片描述
思路: 类似三维偏序, 不过这里没这么复杂, 对a排序… 然后离散化b, 线段树维护c

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <bitset>
// #include <unistd.h>
#include <unordered_map>
using namespace std;
#define LL long long
#define pb push_back
#define mk make_pair
#define pill pair<int, int>
#define fi first
#define se second
#define mst(a, b) memset(a, b, sizeof a)
#define lson (rt << 1)
#define rson ((rt << 1) | 1)
const int qq = 5e5 + 10;
const int INF = 1e9 + 10;
const int MOD = 1e9 + 7;
struct Node {
int a, b, c;
bool operator < (const Node &d) const {
return a > d.a;
}
}p[qq];
int n;
int maxn[qq << 2];
int num[qq << 2];
int tmp[qq];
void updateMaxn(int l, int r, int rt, int x, int y, int val) {
if (l == r) {
maxn[rt] = max(maxn[rt], val);
return;
}
if (x <= l && r <= y) {
maxn[rt] = max(maxn[rt], val);
return ;
}
int mid =
(l + r) >> 1;
if (mid >= x)
updateMaxn(l, mid, lson, x, y, val);
if (mid < y)
updateMaxn(mid + 1, r, rson, x, y, val);
maxn[rt] = max(maxn[lson], maxn[rson]);
}
int getMaxn(int l, int r, int rt, int x, int y) {
if (l == r) {
return maxn[rt];
}
if (x <= l && r <= y) {
return maxn[rt];
}
int ans = 0;
int mid = (l + r) >> 1;
if (mid >= x)
ans = max(ans, getMaxn(l, mid, lson, x, y));
if (mid < y)
ans = max(ans, getMaxn(mid + 1, r, rson, x, y));
return ans;
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d%d%d", &p[i].a, &p[i].b, &p[i].c);
}
sort(p, p + n);
for (int i = 0; i < n; ++i) {
tmp[i] = p[i].b;
}
sort(tmp, tmp + n);
int k = unique(tmp, tmp + n) - tmp;
int id = lower_bound(tmp, tmp + k, p[0].b) - tmp;
id++;
updateMaxn(1, k, 1, id, id, p[0].c);
int ans = 0;
for (int i = 1; i < n; ++i) {
id = lower_bound(tmp, tmp + k, p[i].b) - tmp;
id++;
int x = 0;
if (id != k)
x = getMaxn(1, k, 1, id + 1, k);
if (x > p[i].c) {
ans++;
}
updateMaxn(1, k, 1, id, id, p[i].c);
}
printf("%dn", ans);
return 0;
}