幸运数字和推箱子
先讲点笑话
P11830 [省选联考 2025] 幸运数字
翻了翻题解区发现很多题解讲的都很好，借鉴借鉴
特殊性质 A
发现中位数的数量越多越优，那么把可能成为中位数的就全部令为中位数，并且数量尽可能多
这个结论不难证明：如果 \(x\) 已经是中位数，继续增加 \(x\) 的个数，答案肯定不会改变；如果 \(x\) 不是中位数，可以增加 \(x\) 个数的方式使得当前的中位数变成 \(x\)。
因为最多 \(n\) 个不同的数，考虑枚举中位数 \(x\)，发现给定的数的范围可能会把现在的 \(x\) 给覆盖掉，那么把所有的范围排个序，扔进优先队列里，边枚举 \(x\) 边更新这个优先队列就可以
复杂度 \(O(Tn \log n)\)
特殊性质 B
还是枚举中位数 \(x\)，判断 \(x\) 是否可以成为中位数，只需要知道小于 \(x\) 的数出现的次数范围以及大于 \(x\) 的数出现的次数范围就行
具体的，假设小于 \(x\) 的数出现的次数为 \([l,r]\) 次，大于 \(x\) 的数出现的次数为 \([l',r']\) 次，讨论一下：
如果 \([l,r]\) 和 \([l',r']\) 有交，说明 \(x\) 可以成为中位数，只需要控制小于 \(x\) 的个数等于大于 \(x\) 的个数即可
如果 \([l,r]\) 和 \([l',r']\) 无交，则需要取离最近的两个数，作为小于 \(x\) 的个数和大于 \(x\) 的个数，然后判断中位数是否在中间为 \(x\) 的那一部分即可
实现很简单，复杂度 \(O(Tn \log n)\)
正解 1
把性质 B 扩展一下，考虑求中位数的时候，维护 \(s,s1,s2,s3,s4\) 分别中位数可以取 \(x\) 的最大个数，表示小于 \(x\) 的最小个数，小于 \(x\) 的最大个数，大于 \(x\) 的最小个数，大于 \(x\) 的最大个数
判断的时候，首先必须要 \(s>0\)，接下来根据他们的定义，讨论 \(s1-s4\) 和 \(s2-s3\) 的符号是否相同，如果符号不用 \(x\) 一定可以成为中位数，很好理解
接下来还是粪陶
直接暴力拿 \(s1-s4,s4-s1,s2-s3,s3-s2\) 来讨论，显然一定要用正的那个，负的不用来讨论
若 \(\min(s1-s4,s4-s1-1,s2-s3,s3-s2-1)\le s-1\)，就可以钦定 \(x\) 为中位数
这是对于一个区间来的，若从一个区间端点到另一个区间端点时，\(s,s1,s2,s3,s4\) 可以 \(O(1)\) 全求出来
把所有的区间处理出来就可以了
复杂度 \(O(Tn \log n)\)
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
int s, s1, s2, s3, s4;
int c, T;
const int N = 1e6 + 5;
vector<int> l[N], r[N];
int l1[N], r1[N], l2[N], r2[N];
inline bool check()
{
if(!s)
return 0;
bool f1 = s1-s4<=0;
bool f2 = s2-s3<=0;
int mi = LONG_LONG_MAX;
if(f1+f2==1)
return 1;
if(f1)
mi = min(mi, s4 - s1 - 1);
if(!f1)
mi = min(mi, s1 - s4);
if(f2)
mi = min(mi, s3 - s2 - 1);
if(!f2)
mi = min(mi, s2 - s3);
return mi < s;
}
int S;
vector<int> v;
void work()
{
//二分处理区间
v.clear();
v.push_back(0);
int i;
for(i = 1; i <= n; i++)
v.push_back(l2[i]), v.push_back(r2[i]);
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for(i = 1; i <= n; i++)
{
int idx;
idx = lower_bound(v.begin(), v.end(), l2[i]) - v.begin();
l[idx].push_back(i);
idx = lower_bound(v.begin(), v.end(), r2[i]) - v.begin();
r[idx].push_back(i);
}
return;
}
void solve()
{
int i;
for(i = 0; i <= 2 * n; i++)
l[i].clear(), r[i].clear();
cin >> n;
s1 = s2 = s3 = s4 = s = 0;
S = 0;
for(i = 1; i <= n; i++)
{
cin >> l1[i] >> r1[i] >> l2[i] >> r2[i];
S += r1[i];
}
//算出s,s1,s2,s3,s4
for(i = 1; i <= n; i++)
{
if(l2[i] > 0)
{
s3 += l1[i],s4 += r1[i];
continue;
}
if(r2[i] < 0)
{
s1 += l1[i],s2 += r1[i];
continue;
}
s += r1[i];
}
work();
for(auto i : l[0])
s3 -= l1[i], s4 -= r1[i];
int ans = 0;
for(int i = 1; i < v.size(); i++)
{
bool f = 0;
if(check())
{
f = 1;
for(auto j : r[i - 1])
s1 += l1[j], s2 += r1[j];
s = S - s2 - s4;
if(check())
ans += v[i] - v[i - 1];
else
ans++;
}
for(auto j : l[i])
s3 -= l1[j], s4 -= r1[j];
if(!f)
{
for(auto j : r[i - 1])
s1 += l1[j], s2 += r1[j];
}
s = S - s2 - s4;
}
ans += check();
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> c >> T;
while(T--)
solve();
return 0;
}
考场思路
思路差不多，实现有所不同，由于某些原因重新敲了一遍就过了
扔个代码把
点击查看代码
#include <bits/stdc++.h>
#define fi first
#define se second
#define LL long long
#define MAXN 200005
#define All(x) x.begin(),x.end()
#define HH printf("\n");
using namespace std;
class Range
{
public:
int l1, r1;
int l2, r2;
bool operator < (const Range& x)const
{
if(l2 == x.l2)
return r2 < x.r2;
else
return l2 < x.l2;
}
} rg[MAXN];
int n;
int cid;
vector<int> X;
vector<int> add[MAXN * 4];
vector<int> rmv[MAXN * 4];
int N;
int p[MAXN * 4];
unordered_map<int, int> to;
bool check(LL lf_l, LL lf_r, LL mid, LL rf_l, LL rf_r)
{
if(mid == 0)
return false;
LL x = (lf_l + rf_l + mid + 1) / 2ll;
if(lf_l < x && x <= lf_l + mid)
return true;
if(x <= lf_l)
{
LL y = (lf_l + rf_r + mid + 1) / 2ll;
if(y <= lf_l)
return false;
return true;
}
else
{
LL y = (lf_r + rf_l + mid + 1) / 2ll;
if(y > lf_r + mid)
return false;
return true;
}
}
void solve()
{
cin >> n;
int i;
for(i = 1; i <= n; i++)
cin >> rg[i].l1 >> rg[i].r1 >> rg[i].l2 >> rg[i].r2;
sort(rg + 1, rg + 1 + n);
X.clear();
for(i = 1; i <= n; i++)
{
X.push_back(rg[i].l2);
X.push_back(rg[i].r2);
}
sort(All(X));
X.erase(unique(All(X)), X.end());
N = X.size();
to.clear();
for(i = 0; i < N; i++)
{
to[X[i]] = i + 1;
p[i + 1] = X[i];
}
for(i=0;i<=N;i++)
{
add[i].clear();
rmv[i].clear();
}
for(i=1;i<=n;i++)
{
add[to[rg[i].l2]].push_back(i);
rmv[to[rg[i].r2]].push_back(i);
}
int ans = 0;
LL lf_l = 0;
LL lf_r = 0;
LL in_l = 0;
LL in_r = 0;
LL rf_l = 0;
LL rf_r = 0;
for(i=1;i<=n;i++)
{
rf_l += rg[i].l1;
rf_r += rg[i].r1;
}
for(int o = 1; o <= N; o++)
{
for(auto i : add[o])
{
rf_r -= rg[i].r1;
rf_l -= rg[i].l1;
in_l += rg[i].l1;
in_r += rg[i].r1;
}
if(check(lf_l, lf_r, in_r, rf_l, rf_r))
{
ans++;
}
for(auto i : rmv[o])
{
in_l -= rg[i].l1;
in_r -= rg[i].r1;
lf_l += rg[i].l1;
lf_r += rg[i].r1;
}
if(o < N && p[o] + 1 != p[o + 1])
{
if(check(lf_l, lf_r, in_r, rf_l, rf_r))
ans += p[o + 1] - p[o] - 1;
}
}
cout<<ans<<endl;
}
int c,T;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>c>>T;
while(T--)
solve();
return 0;
}
P11833 [省选联考 2025] 推箱子
纯随机化和一些逆天的特判取得了 \(32\) 分的好成绩
n^2 暴力
按照 \(t\) 从小到大排序后，依次满足每个箱子的目标需求
若箱子移动的路线被其他箱子阻挡，此箱子会推着阻挡物前进
在此期间，任何一个箱子无法在规定时间内达到目标，将输出 No，否则为 Yes
线段树
和暴力一样，把 \(t\) 排序然后对于每个 \(i\) 从 \(a_i\) 移动到 \(b_i\) 的途中如果有挡道的箱子就一起往前移
观察移动后的序列，可以发现从原序列变成新序列只需要进行一个区间覆盖等差数列即可，直接使用线段树维护，二分查找受影响的最远的点，于是就有了双 log 的做法
先区间推平然后打等差数列起始位置的懒标记。
考虑优化成单 log，发现只需要将二分移到线段树即可，多维护区间左端点的值和右端点的值即可，需要 odt 实现，但是我不会/ng
代码实现略有不同，实现的很屎，可以去看题解区的线段树代码，比我实现的好
点击查看代码
#include <bits/stdc++.h>
#define fi first
#define se second
#define LL long long
#define MAXN 200005
using namespace std;
int n;
class Box
{
public:
int a, b;
LL t;
} a[MAXN];
int c,T;
pair<LL, int> ls[MAXN];
LL ust = 0;
namespace DS
{
class SegTree
{
public:
int l, r;
LL sm;
LL lf;
LL rf;
LL cv;
} tr[MAXN << 2];
inline int lc(int x)
{
return x << 1;
}
inline int rc(int x)
{
return x << 1 | 1;
}
void push_up(int p)
{
tr[p].sm = tr[lc(p)].sm + tr[rc(p)].sm;
tr[p].rf = tr[rc(p)].rf;
tr[p].lf = tr[lc(p)].lf;
}
void upd(int p, LL cv)
{
tr[p].cv = cv;
tr[p].sm = (LL)(cv + cv + tr[p].r - tr[p].l) * (LL)(tr[p].r - tr[p].l + 1) / 2ll;
tr[p].rf = cv + tr[p].r - tr[p].l;
tr[p].lf = cv;
}
void push_down(int p)
{
if(tr[p].cv == -1)
return ;
int mid = (tr[p].l + tr[p].r) >> 1;
upd(lc(p), tr[p].cv);
upd(rc(p), tr[p].cv + mid + 1 - tr[p].l);
tr[p].cv = -1;
}
void Build(int p, int l, int r)
{
tr[p].l = l, tr[p].r = r;
tr[p].cv = -1;
if(l == r)
{
tr[p].sm = a[l].a;
tr[p].lf = a[l].a;
tr[p].rf = a[l].a;
return ;
}
int mid = (l + r) >> 1;
Build(lc(p), l, mid);
Build(rc(p), mid + 1, r);
push_up(p);
}
void Modify(int p, int l, int r, LL cv)
{
if(l <= tr[p].l && tr[p].r <= r)
{
upd(p, cv + tr[p].l - l);
return ;
}
push_down(p);
int mid = (tr[p].l + tr[p].r) >> 1;
if(l <= mid)
Modify(lc(p), l, r, cv);
if(r > mid)
Modify(rc(p), l, r, cv);
push_up(p);
}
LL Query(int p, int l, int r)
{
if(l <= tr[p].l && tr[p].r <= r)
{
return tr[p].sm;
}
push_down(p);
int mid = (tr[p].l + tr[p].r) >> 1;
LL ret = 0;
if(l <= mid)
ret += Query(lc(p), l, r);
if(r > mid)
ret += Query(rc(p), l, r);
return ret;
}
inline LL qrySum(int l, int r)
{
return Query(1, l, r);
}
inline void setIncre(int l, int r, LL s)
{
Modify(1, l, r, s);
return ;
}
int BnqrR(int p, LL k)
{
if(tr[p].l == tr[p].r)
return tr[p].l;
push_down(p);
if(tr[rc(p)].lf < tr[rc(p)].l + k)
return BnqrR(rc(p), k);
if(tr[lc(p)].lf < tr[lc(p)].l + k)
return BnqrR(lc(p), k);
return -1;
}
int BnqrL(int p, LL k)
{
if(tr[p].l == tr[p].r)
return tr[p].l;
push_down(p);
if(tr[lc(p)].rf > tr[lc(p)].r + k)
return BnqrL(lc(p), k);
if(tr[rc(p)].rf > tr[rc(p)].r + k)
return BnqrL(rc(p), k);
return -1;
}
}
bool work(int p)
{
int apa = DS::qrySum(p, p);
if(a[p].b == apa)
{
return ust <= a[p].t;
}
if(a[p].b > apa)
{
LL us = 0;
int R = DS::BnqrR(1, a[p].b - p);
if(R == -1)
R = p;
if(!(R >= p))
{
R = p;
}
us = DS::qrySum(p, R);
us = (LL)(a[p].b + a[p].b + R - p) * (LL)(R - p + 1) / 2ll - us;
DS::setIncre(p, R, a[p].b);
ust += us;
if(ust > a[p].t)
return false;
return true;
}
else
{
LL us = 0;
int L = DS::BnqrL(1, a[p].b - p);
if(L == -1)
L = p;
if(!(L <= p))
{
L = p;
}
us = DS::qrySum(L, p);
us -= (LL)(a[p].b + a[p].b - (p - L)) * (LL)(p - L + 1) / 2ll;
DS::setIncre(L, p, a[p].b - (p - L));
ust += us;
if(ust > a[p].t)
return false;
return true;
}
}
bool check()
{
ust = 0;
int i;
for(i=1;i<=n;i++)
{
if(!work(ls[i].se))
return false;
}
return true;
}
void solve()
{
cin>>n;
int i;
for(i=1;i<=n;i++)
{
cin>>a[i].a>>a[i].b>>a[i].t;
ls[i] = {a[i].t, i};
}
DS::Build(1, 1, n);
sort(ls + 1, ls + 1 + n);
if(check())
printf("Yes\n");
else
printf("No\n");
}
int main()
{
cin>>c>>T;
while(T--)
solve();
return 0;
}
听说还有很厉害的分块做法，我不会/ng
是不是讲完了
浙公网安备 33010602011771号