宝藏
题目描述
参与考古挖掘的小明得到了一份藏宝图，藏宝图上标出了 个深埋在地下的宝藏，第 个宝藏价值为 ，挖掘它需要时间 。
赞助商给小明的时间是有限的，他只有 的时间用来挖掘宝藏。也就是说他挖掘的宝藏消耗的总时间不得超过 。现在小明一共进行了 次开采活动，第 次开采正好开采 个宝藏（保证 为奇数），他想要您计算开采的宝藏的价值的中位数最大是多少。（这些开采活动是独立的，即不会实际对宝藏造成影响）
题解
发现当选取的宝藏越多时，答案单调减，所以先将宝藏按 排序，从最大值开始扫，同时维护从 和 的前 小的 的和，题解用的主席树，但是由于要查询的区间只有两种且有规律，用两棵线段树就好了
考试时由于没考虑清加入、删除和查询的先后顺序，挂成78了（还调了4个小时） /kk
// Tags:
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cstdio>
#include <cstring>
typedef long long ll;
template <typename T>
inline T &read(T &x) {
x = 0;
bool f = false;
short ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') f = true;
ch = getchar();
}
while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ '0'), ch = getchar();
if (f) x = -x;
return x;
}
const int N = 3e5 + 5, M = 1e6 + 5;
int n, q, maxt, ans[N];
ll t;
struct Obj {
int w, t;
inline bool operator<(const Obj &rhs) const { return w < rhs.w; }
} a[N];
struct SegmentTree {
struct Node {
int cnt;
ll sum;
} tr[M << 2];
inline void pushup(int x) {
tr[x].sum = tr[x << 1].sum + tr[x << 1 | 1].sum;
tr[x].cnt = tr[x << 1].cnt + tr[x << 1 | 1].cnt;
}
ll query(int x, int l, int r, int p) {
if (p == 0) return 0;
if (l == r) { return (ll)p * l; }
int mid = (l + r) >> 1;
if (p <= tr[x << 1].cnt) return query(x << 1, l, mid, p);
return tr[x << 1].sum + query(x << 1 | 1, mid + 1, r, p - tr[x << 1].cnt);
}
void modify(int x, int l, int r, int p, int v) {
if (l == r) { return tr[x].cnt += v, tr[x].sum += p * v, void(); }
int mid = (l + r) >> 1;
if (p <= mid) modify(x << 1, l, mid, p, v);
else
modify(x << 1 | 1, mid + 1, r, p, v);
pushup(x);
}
} pre, suf;
int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
freopen64("/tmp/CodeTmp/testdata.in", "r", stdin);
freopen64("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
freopen("treasure.in", "r", stdin);
freopen("treasure.out", "w", stdout);
#endif
#endif
read(n), read(t), read(q);
for (int i = 1; i <= n; ++i)
read(a[i].w), maxt = std::max(maxt, read(a[i].t));
std::sort(a + 1, a + n + 1);
for (int i = 1; i <= n; ++i) pre.modify(1, 0, maxt, a[i].t, 1);
memset(ans, -1, sizeof(ans));
for (int i = n, j = 1; i && j <= n; --i) {
pre.modify(1, 0, maxt, a[i].t, -1);
while (((j >> 1) <= i - 1) && ((j >> 1) <= n - i) &&
(suf.query(1, 0, maxt, j >> 1) + pre.query(1, 0, maxt, j >> 1) +
a[i].t <=
t)) {
ans[j] = a[i].w, j += 2;
}
suf.modify(1, 0, maxt, a[i].t, 1);
}
for (int i = 1, x; i <= q; ++i) { printf("%d\n", ans[read(x)]); }
return 0;
}寻找道路
题目描述
题解
#include <cctype>
#include <cstdio>
#include <vector>
typedef unsigned long long ull;
template <typename T>
inline T &read(T &x) {
x = 0;
bool f = false;
short ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') f = true;
ch = getchar();
}
while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ '0'), ch = getchar();
if (f) x = -x;
return x;
}
const int N = 1e6 + 5, mod = 1e9 + 7;
int n, dis[N], m;
ull dis2[N];
std::vector<int> G[2][N];
int q[N], tmp[N];
bool vis[N];
inline void add(int u, int v, int w) { G[w][u].push_back(v); }
int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
freopen64("/tmp/CodeTmp/testdata.in", "r", stdin);
freopen64("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
freopen("path.in", "r", stdin);
freopen("path.out", "w", stdout);
#endif
#endif
read(n), read(m);
for (int i = 1, u, v, w; i <= m; ++i) {
read(u), read(v), read(w);
add(u, v, w);
}
int l = 1, r = 1;
q[1] = 1, vis[1] = true;
while (l <= r) {
int u = q[l++];
for (int v : G[0][u])
if (!vis[v]) vis[v] = true, q[++r] = v;
}
l = 1, r = 0;
for (int i = 1; i <= n; ++i)
if (vis[i]) q[++r] = i;
while (l <= r) {
int tot = 0;
for (int i = l; i <= r && dis[q[i]] == dis[q[l]]; ++i) tmp[++tot] = q[i];
l += tot;
for (int i = 0; i < 2; ++i)
for (int j = 1; j <= tot; ++j) {
int u = tmp[j];
for (int v : G[i][u])
if (!vis[v]) {
vis[v] = true;
dis[v] = (((ull)dis[u] << 1) | i) % mod;
q[++r] = v;
}
}
}
for (int i = 2; i <= n; ++i) printf("%d ", vis[i] ? dis[i] : -1);
return 0;
}