牛客练习赛125题解
A
答案即为：。
时间复杂度：。
B
设序列中非 质数的数量为
。那么：
为
时，输出
。
。
时间复杂度：，其中
为
。
C
设 为
位数，十进制下从高位到低位分别是：
。
那么 即为：
。
所以枚举 后可以依次求出
，最后检查
是否为
即可。
时间复杂度：，其中
为
。
D
对每种颜色独立考虑。
首先按照从左往右，从上至下的方式对所有坐标排序。
记 为走到第
行时的最大风车数。
依次扫描每个坐标，若当前位于第 行第
列，那么有
，最后的答案即为
。
上述 dp 可以通过树状数组维护，同样的，由于 数组必然需要保证不降的性质，也可以用 map 维护。
时间复杂度：。
E
若由起点和终点划定的矩形内部包含至少一家超市则答案即为起点到终点的曼哈顿距离。
否则答案即为曼哈顿距离加矩形最近超市的曼哈顿距离的两倍。
第一种情况可以通过二维前缀和维护。
第二种情况可以先预处理地图上每一点到最近的超市距离（多源 bfs），然后枚举矩形轮廓统计最小值即可（也可使用 st表 维护）。
时间复杂度：，其中
为
。
F
抽象出每个查询区间，那么若干个查询互相之间没有影响。
对于每个操作一，可以将操作区间理解成两个单点位置的颜色加减。
考虑扫描线，每个操作一转化至各自查询区间处的 和
操作（带时间戳，第
个操作时间戳为
），那么对于每个查询区间边界只需要依次处理每个操作标签（单点修改）即可。
树状数组和 set 维护，第 个位置的标签数，那么对于每个区间依次进行：将起始位置前的单点删除考虑（将时间戳从对应颜色 set 中删除），查询所有 set 中最小值小于当前查询时间戳的 set 的个数（树状数组维护每种颜色 set 的最小值），结束位置前（包含结束位置）的单点增加考虑（将时间戳加入对应颜色的 set）。
注意到查询区间不重复，可以直接维护已经考虑到的删除和添加的位置，然后依次向后考虑即可。
时间复杂度：。
标程
A
#include <bits/stdc++.h>
using namespace std;
#define _for(i, a, b) for(int i = a, IM = b; i <= IM; i ++)
#define endl '\n'
const int N = 3009;
int c[N << 1][N * 3];
void solved() {
int x; cin >> x;
int ans = 0;
for(int i = 1; i <= 4; i ++) {
int y; cin >> y;
ans += y > x;
}
cout << ans << endl;
}
int main() {
int ttx; cin >> ttx; while(ttx --)
solved();
return 0;
}
B
#include <bits/stdc++.h>
using namespace std;
#define _for(i, a, b) for(int i = a, IM = b; i <= IM; i ++)
#define endl '\n'
bool check(int x) {
if(x == 1 || x == 3) return false;
for(int i = 2; i * i <= x; i ++) {
if(x % i == 0) return false;
}
return true;
}
void solved() {
int n; cin >> n;
int ans = 0, x;
while(n --) {
cin >> x;
ans += check(x);
}
if(ans == 0) cout << -1;
else cout << (~ans & 1);
cout << endl;
}
int main() {
int ttx; cin >> ttx; while(ttx --)
solved();
return 0;
}
C
#include <bits/stdc++.h>
using namespace std;
#define _for(i, a, b) for(int i = a, IM = b; i <= IM; i ++)
#define endl '\n'
using ll = long long;
ll get(int a, ll y) {
ll ans = a, t = 10;
while(y > 0) {
int c = y % 10;
y /= 10;
a = c - a;
if(a < 0) {
a += 10;
y --;
}
ans += a * t;
t *= 10;
}
return ans;
}
ll ask(ll x) {
ll t = 1;
do {
x /= 10;
t *= 10;
} while(x);
return t / 10;
}
void solved() {
ll x, y;
cin >> y;
int sum = 0;
_for(i, 0, 9) {
x = get(i, y);
sum += x / 10 + x % ask(x) == y;
}
cout << sum << endl;
}
int main() {
int ttx; cin >> ttx; while(ttx --)
solved();
return 0;
}
D
#include <bits/stdc++.h>
using namespace std;
#define _for(i, a, b) for(int i = a, IM = b; i <= IM; i ++)
#define endl '\n'
using ll = long long;
const int N = 100009;
using int3 = array<int, 3>;
vector<int3> ve[N];
int col[N << 1];
ll ask(vector<int3> &ve) {
using pil = pair<int, ll>;
set<pil> se;
se.insert({0, 0});
for(int3 v: ve) {
int x = v[0], y = v[1], c = v[2];
set<pil>::iterator it = -- se.lower_bound({y, 1e18});
ll now = (*it).second + c;
it ++;
while(it != se.end()) {
if((*it).second > now) break;
se.erase(it ++);
}
se.insert({y, now});
}
return (*se.rbegin()).second;
}
void solved() {
int n, m; cin >> n >> m;
set<int> se;
int tot = 1;
_for(i, 1, n) _for(j, 1, m) {
cin >> col[tot ++];
se.insert(col[tot - 1]);
}
tot = 1;
_for(i, 1, n) _for(j, 1, m) {
int x; cin >> x;
ve[col[tot ++]].push_back({i, j, x});
}
ll ans = 0;
for(int c: se) {
ans = max(ans, ask(ve[c]));
ve[c].clear();
}
cout << ans << endl;
}
int main() {
int ttx; cin >> ttx; while(ttx --)
solved();
return 0;
}
E
#include <bits/stdc++.h>
using namespace std;
#define _for(i, a, b) for(int i = a, IM = b; i <= IM; i ++)
#define endl '\n'
using ll = long long;
using pii = pair<int, int>;
const int N = 1009;
int dis[N][N], sum[N][N];
queue<pii> qu;
int xx[] = {0, 1, 0, -1, 0};
void init() {
while(!qu.empty()) {
int x = qu.front().first, y = qu.front().second;
qu.pop();
_for(i, 1, 4) {
int fx = x + xx[i], fy = y + xx[i - 1];
if(fx < 1 || fx > 1000 || fy < 1 || fy > 1000) continue;
if(dis[fx][fy]) continue;
qu.push({fx, fy});
dis[fx][fy] = dis[x][y] + 1;
}
}
_for(i, 1, 1000) _for(j, 1, 1000)
sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
}
void solved() {
int x1, x2, y1, y2; cin >> x1 >> y1 >> x2 >> y2;
if(x1 > x2) swap(x1, x2);
if(y1 > y2) swap(y1, y2);
int cnt = sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1];
int ans = x2 - x1 + y2 - y1;
if(!cnt) {
int mn = 1e9;
_for(i, x1, x2) mn = min({mn, dis[i][y1], dis[i][y2]});
_for(j, y1, y2) mn = min({mn, dis[x1][j], dis[x2][j]});
ans += mn - 1 << 1;
}
cout << ans << endl;
}
int main() {
int ttx, n;
cin >> n >> ttx;
_for(i, 1, n) {
int x, y; cin >> x >> y;
dis[x][y] = sum[x][y] = 1;
qu.push({x, y});
}
init();
while(ttx --)
solved();
return 0;
}
F
#include <bits/stdc++.h>
using namespace std;
#define _for(i, a, b) for(int i = a, IM = b; i <= IM; i ++)
#define endl '\n'
using ll = long long;
using pii = pair<int, int>;
const int N = 500009;
using int3 = array<int, 3>;
int3 a[N];
vector<int3> ve[N];
multiset<int> mse[N];
int q[N];
int sum[N], n;
void add(int x, int p) {
while(x <= n) {
sum[x] += p;
x += x & -x;
}
}
int ask(int x) {
int ans = 0;
while(x) {
ans += sum[x];
x -= x & -x;
}
return ans;
}
int main() {
int m; cin >> n >> m;
_for(i, 1, m) {
int op; cin >> op;
if(op == 1) {
cin >> a[i][0] >> a[i][1] >> a[i][2];
} else {
cin >> a[i][0] >> a[i][1]; a[i][2] = -i;
}
q[i] = -1;
}
_for(i, 1, m) if(a[i][2] > 0) {
ve[a[i][0]].push_back({1, i, a[i][2]});
ve[a[i][1]].push_back({-1, i, a[i][2]});
}
sort(a + 1, a + 1 + m);
int ad = 1, de = 1;
_for(i, 1, m) if(a[i][2] < 0) {
int l = a[i][0], r = a[i][1];
while(ad <= r) {
for(int3 x: ve[ad]) if(x[0] == 1) {
int ti = x[1], col = x[2];
if(!mse[col].empty()) add(*mse[col].begin(), -1);
mse[col].insert(ti);
add(*mse[col].begin(), 1);
}
ad ++;
}
while(de < l) {
for(int3 x: ve[de]) if(x[0] == -1) {
int ti = x[1], col = x[2];
add(*mse[col].begin(), -1);
mse[col].erase(mse[col].find(ti));
if(!mse[col].empty()) add(*mse[col].begin(), 1);
}
de ++;
}
q[-a[i][2]] = ask(-a[i][2]);
}
_for(i, 1, m) if(q[i] != -1) cout << q[i] << endl;
return 0;
}
联想公司福利 618人发布
查看21道真题和解析
投递汇丰科技等公司7个岗位