2集合間距離
有两种方法,我选择了更劣的做法,呜呜呜!我是暴力枚举每个点,然后对与另一个集合里的点枚举横坐标,用二分找到纵坐标上距离最小的点, \(xhr\) 写的是直接多源广搜,我的时间复杂度为 \(O(n * 1000)\),他的时间复杂度为 \(O(n)\),在线膜拜
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5, M = 1e3 + 5;
int n, x[N], y[N], m, ans = 1e18, l[M][M], r[M][M];
vector<int> v[N];
signed main() {
for (int i = 0; i <= 1000; i++) {
v[i].push_back(-1e18);
v[i].push_back(1e18);
}
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> x[i] >> y[i];
}
cin >> m;
for (int i = 1, _x, _y; i <= m; i++) {
cin >> _x >> _y;
v[_x].push_back(_y);
}
for (int i = 0; i <= 1000; i++) {
sort(v[i].begin(), v[i].end());
for (int j = 0; j <= 1000; j++) {
auto tmp = upper_bound(v[i].begin(), v[i].end(), j) - v[i].begin() - 1;
l[i][j] = v[i][tmp];
tmp = lower_bound(v[i].begin(), v[i].end(), j) - v[i].begin();
r[i][j] = v[i][tmp];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= 1000; j++) {
ans = min(ans, abs(x[i] - j) + min(y[i] - l[j][y[i]], r[j][y[i]] - y[i]));
}
}
cout << ans;
return 0;
}
Star Divine
两种做法,一种是随机化,我们可以随机红色的点选哪些,然后对于每一个蓝色的点看与他相连的红点有多少,奇数个就选,这个做法由于红色的点每个有二分之一的概率会选到,蓝色也一样,所以期望的随机次数就是一次.还有一种正解做法,考虑如果当前的蓝点选或不选,如果选的话会产生多少贡献,不选的话会产生多少贡献,如果一样的话随便哪个,由于每次选的都一定大于等于二分之一,所以最终选出的点数也一定大于等于二分之一
#include <bits/stdc++.h>
using namespace std;
using Pii = pair<long long, long long>;
#define int long long
mt19937_64 rnd(time(0));
const int N = 1e5 + 5;
int t, x, y, m, vis[N];
set<Pii> s;
vector<int> g[N];
void Solve() {
cin >> x >> y >> m;
for (int i = 1; i <= x; i++) {
g[i].clear();
}
for (int i = 1, u, v; i <= m; i++) {
cin >> u >> v;
s.insert({u, v});
}
while (!s.empty()) {
auto cur = *s.begin();
s.erase(s.begin());
g[cur.first].push_back(cur.second);
}
while (true) {
int cnt = 0;
for (int i = 1; i <= y; i++) {
vis[i] = rnd() % 2;
cnt += vis[i];
}
for (int i = 1; i <= x; i++) {
int tmp = 0;
for (auto v : g[i]) {
tmp += vis[v];
}
if (tmp % 2 == 1) {
cnt++;
}
}
if (cnt >= (x + y + 1) / 2) {
break;
}
}
vector<int> ans1, ans2;
for (int i = 1; i <= y; i++) {
if (vis[i] == true) {
ans2.push_back(i);
}
}
for (int i = 1; i <= x; i++) {
int tmp = 0;
for (auto v : g[i]) {
tmp += vis[v];
}
if (tmp % 2 == 1) {
ans1.push_back(i);
}
}
cout << ans1.size() << " " << ans2.size() << "\n";
for (auto cur : ans1) {
cout << cur << " ";
}
cout << "\n";
for (auto cur : ans2) {
cout << cur << " ";
}
cout << "\n";
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> t;
while (t--) {
Solve();
}
return 0;
}
Logical Sum of Substring
这题我们考虑直接暴力线段树,那么我们可以维护当前的答案,在二进制位上的第 \(i\)位为一是的最小出现位置与最大出现位置即可
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5, M = 17, INF = 1e18;
int n, k, a[N], q;
struct node {
int ans, maxi[M], mini[M];
void clean() {
ans = INF;
for (int i = 0; i <= k; i++) {
maxi[i] = -INF;
mini[i] = INF;
}
}
}tr[N * 4], CANT, tmp;
node Merge(node l, node r) {
node m;
m.clean();
m.ans = min(l.ans, r.ans);
vector<int> v;
for (int i = 0; i <= k; i++) {
m.maxi[i] = max(l.maxi[i], r.maxi[i]);
m.mini[i] = min(l.mini[i], r.mini[i]);
if (l.maxi[i] != -INF) {
v.push_back(l.maxi[i]);
}
if (r.mini[i] != INF) {
v.push_back(r.mini[i]);
}
}
if (m.ans == 1) {
return m;
}
sort(v.begin(), v.end());
for (int i = 0; i < v.size(); i++) {
int tot = 0;
for (int j = i; j < v.size(); j++) {
tot |= a[v[j]];
if (tot == ((1 << k) - 1)) {
m.ans = min(m.ans, v[j] - v[i] + 1);
break;
}
}
}
return m;
}
void build(int i, int l, int r) {
if (l == r) {
tr[i].clean();
if (a[l] == ((1 << k) - 1)) {
tr[i].ans = 1;
}
for (int j = 0; j <= k; j++) {
if ((a[l] & (1 << j))) {
tr[i].maxi[j] = l, tr[i].mini[j] = l;
}
}
return ;
}
int mid = (l + r) >> 1;
build(i * 2, l, mid);
build(i * 2 + 1, mid + 1, r);
tr[i] = Merge(tr[i * 2], tr[i * 2 + 1]);
}
void change(int i, int l, int r, int p, int x) {
if (l == r) {
a[l] = x;
tr[i].clean();
if (a[l] == ((1 << k) - 1)) {
tr[i].ans = 1;
}
for (int j = 0; j <= k; j++) {
if ((a[l] & (1 << j))) {
tr[i].maxi[j] = l, tr[i].mini[j] = l;
}
}
return ;
}
int mid = (l + r) >> 1;
if (mid >= p) {
change(i * 2, l, mid, p, x);
}
else change(i * 2 + 1, mid + 1, r, p, x);
tr[i] = Merge(tr[i * 2], tr[i * 2 + 1]);
}
void query(int i, int l, int r, int x, int y) {
if (l > y || r < x) {
return ;
}
if (l >= x && r <= y) {
tmp = Merge(tmp, tr[i]);
return ;
}
int mid = (l + r) >> 1;
query(i * 2, l, mid, x, y);
query(i * 2 + 1, mid + 1, r, x, y);
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
CANT.clean();
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
build(1, 1, n);
cin >> q;
while (q--) {
int opt, x, y;
cin >> opt >> x >> y;
if (opt == 1) {
change(1, 1, n, x, y);
}
else {
tmp.clean();
query(1, 1, n, x, y);
if (tmp.ans == INF) {
cout << "-1\n";
}
else cout << tmp.ans << "\n";
}
}
return 0;
}
标签:int,tr,mid,long,cin,20240925,query
From: https://www.cnblogs.com/libohan/p/18432976