雷火0924笔试 400/400
9646516
T4是近期做过的最难的笔试压轴题。
1.给球员得分记录找mvp，按照题意模拟即可，弄个map存下分数
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 0x3F3F3F3F;
const int maxn = 2e5 + 555;
const int MOD = 1e9 + 7;
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cout.precision(10);
cout << fixed;
int n;
cin >> n;
string ta, tb;
cin >> ta >> tb;
map<string, int> tm;
map<string, map<string, int>> pm;
int mvp_val = -1e9;
string mvp;
for (int i = 0; i < n; i++) {
string player, team;
int val;
cin >> player >> team >> val;
tm[team] += val;
pm[team][player] += val;
if (pm[team][player] > mvp_val) {
mvp_val = pm[team][player];
mvp = player;
}
}
if (tm[ta] == tm[tb]) {
cout << "ended in a draw" << endl;
} else if (tm[ta] > tm[tb]) {
cout << ta << endl;
} else {
cout << tb << endl;
}
cout << mvp << endl;
return 0;
}
2.给出隐身逻辑，有草丛隐身和buff隐身两种，判断A是否能看到B。先处理下每个人物i是否在草丛j中，查询的时候先看b是否开了buff，然后看ab是否是一伙的，之后再看b是否在草丛中，如果在再看ab在不在一个草丛中。我用了bitset优化，暴力应该也可以。注意B不在草丛的情况，没注意的话会卡56%
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 0x3F3F3F3F;
const int maxn = 2e5 + 555;
const int MOD = 1e9 + 7;
struct user {
double x, y;
int buff, cls;
bitset<200> st;
};
vector<user> V;
bool inside_circle(double cx, double cy, double cr, double x, double y) {
double ox = x - cx;
double oy = y - cy;
double d = ox * ox + oy * oy;
return d <= cr * cr;
}
bool inside_rect(double A, double B, double C) { return A <= B && B <= C; }
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cout.precision(10);
cout << fixed;
int n, m, q;
cin >> n >> m >> q;
for (int i = 0; i < n; i++) {
user s;
cin >> s.x >> s.y >> s.buff >> s.cls;
V.push_back(s);
}
for (int i = 0; i < m; i++) {
int t;
cin >> t;
if (t == 0) {
double cx, cy, cr;
cin >> cx >> cy >> cr;
for (auto &u : V) {
u.st[i] = inside_circle(cx, cy, cr, u.x, u.y);
}
} else {
set<double> sx, sy;
for (int j = 0; j < 4; j++) {
double x, y;
cin >> x >> y;
sx.insert(x);
sy.insert(y);
}
assert(sx.size() == 2);
assert(sy.size() == 2);
for (auto &u : V) {
u.st[i] = inside_rect(*sx.begin(), u.x, *next(sx.begin())) &&
inside_rect(*sy.begin(), u.y, *next(sy.begin()));
}
}
}
while (q--) {
int a, b;
cin >> a >> b;
a--;
b--;
if (V[b].buff) {
cout << 0 << endl;
} else if (V[a].cls != V[b].cls) {
if (!V[b].st.count()) {
cout << 1 << endl;
} else {
if (((V[a].st & V[b].st).count())) {
cout << 1 << endl;
} else {
cout << 0 << endl;
}
}
} else {
cout << 1 << endl;
}
}
return 0;
}
3.给一堆物品，每个物品有两个值a和b，求最多取出k个物品的条件下，取出a总和为y的物品，最小的b总和是多少。a和y有正有负，k<=5。
这题数据水了，暴力DP 100ms轻松过，正解可能需要折半搜索优化下。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 0x3F3F3F3F;
const int maxn = 2e5 + 555;
const int MOD = 1e9 + 7;
const char *FAIL_FLAG = "Cannot Make It!";
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cout.precision(10);
cout << fixed;
int n, k, x, y;
cin >> n >> k >> x >> y;
if (x == 1)
y = -y;
vector<pair<int, int>> V;
for (int i = 0; i < n; i++) {
int v, a, b;
cin >> v >> a >> b;
if (a == 1)
b = -b;
V.push_back({b, v});
}
vector<unordered_map<int, int>> F(6);
F[0][0] = 0;
for (auto [a2, b2] : V) {
for (int i = k; i >= 0; i--) {
for (auto [a, b] : F[i - 1]) {
if (!F[i].count(a2 + a)) {
F[i][a2 + a] = b + b2;
} else {
F[i][a2 + a] = min(b + b2, F[i][a2 + a]);
}
}
}
}
ll ans = 1e18;
for (int i = 0; i <= k; i++) {
if (F[i].count(y)) {
ans = min(ans, 1LL * F[i][y]);
}
}
if (ans < 1e18) {
cout << ans << endl;
} else {
cout << FAIL_FLAG << endl;
}
return 0;
}
4.给一个字符串矩阵(n*m~1e5)，每次移动可以上下左右走，也可以瞬移到相同字符处，代价都是1,给出1e5个询问，求两点最短路。这题出的真心不错，一眼就能看到思路，但是需要处理很多细节。
首先先加26个辅助点，代表a-z，每个辅助点连向对应字符位置，由于辅助点要一来一回，为了方便起见，将辅助点边权设为1，普通边边权为2，求出答案后除以2.
从a到b要么不使用传送，那么答案是曼哈顿距离，要么至少使用一次瞬移。此时A到B的答案为A->中间点X->辅助点->B。此时可以枚举辅助点的类型，这样辅助点->B这段距离可以预处理出来。中间点X->辅助点代价是1。A->中间点X代价是A到最近的这个类型的点的距离，这可以bfs预处理出来。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 0x3F3F3F3F;
const int maxn = 2e5 + 555;
const int MOD = 1e9 + 7;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
#define IDX(x, y) (((x) * (m)) + (y))
void dijk(int s, vector<int> &D, const vector<vector<pair<int, int>>> &G) {
set<pair<int, int>> st;
st.insert({0, s});
D[s] = 0;
while (!st.empty()) {
auto [dis, pos] = *st.begin();
st.erase(st.begin());
if (D[pos] < dis) {
continue;
}
for (auto [to, cost] : G[pos]) {
if (D[to] > cost + dis) {
D[to] = cost + dis;
st.insert({D[to], to});
}
}
}
}
vector<int> chr[26];
int n, m;
void bfs(int ch, vector<int> &dis, const vector<vector<pair<int, int>>> &G) {
queue<pair<int, int>> q;
for (int i : chr[ch]) {
q.push({0, i});
dis[i] = 0;
}
while (!q.empty()) {
auto [d, idx] = q.front();
int x = idx / m;
int y = idx - x * m;
q.pop();
for (int k = 0; k < 4; k++) {
int x2 = x + dx[k];
int y2 = y + dy[k];
if (x2 >= 0 && x2 < n && y2 >= 0 && y2 < m) {
if (dis[IDX(x2, y2)] > d + 1) {
dis[IDX(x2, y2)] = d + 1;
q.push({d + 1, IDX(x2, y2)});
}
}
}
}
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cout.precision(10);
cout << fixed;
cin >> n >> m;
vector<string> V(n);
for (int i = 0; i < n; i++) {
cin >> V[i];
}
vector<vector<pair<int, int>>> G(n * m + 100);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
chr[V[i][j] - 'a'].push_back(IDX(i, j));
for (int k = 0; k < 4; k++) {
int x = i + dx[k];
int y = j + dy[k];
if (x >= 0 && x < n && y >= 0 && y < m) {
G[IDX(i, j)].push_back({IDX(x, y), 2});
}
}
G[IDX(i, j)].push_back({n * m + V[i][j] - 'a', 1});
G[n * m + V[i][j] - 'a'].push_back({IDX(i, j), 1});
}
}
vector<vector<int>> dis(26, vector<int>(n * m + 30, INF));
for (int i = 0; i < 26; i++) {
dijk(n * m + i, dis[i], G);
}
vector<vector<int>> dis2(26, vector<int>(n * m + 30, INF));
for (int i = 0; i < 26; i++) {
bfs(i, dis2[i], G);
}
int q;
cin >> q;
while (q--) {
int x0, x1, y0, y1;
cin >> x0 >> y0 >> x1 >> y1;
x0--;
x1--;
y0--;
y1--;
int ch = V[x1][y1] - 'a';
ll ans = abs(x0 - x1) + abs(y0 - y1);
for (int i = 0; i < 26; i++) {
ll step1 = dis2[i][IDX(x1, y1)] * 2;
ll step2 = 1;
ll step3 = dis[i][IDX(x0, y0)];
ll now = step1 + step2 + step3;
ans = min(ans, now / 2);
}
cout << ans << endl;
}
return 0;
}
查看6道真题和解析