2024.5.17 【这个世界早已无法拯救，可我们还必须成为英雄。】
Friday 四月初十
继续水数据结构。。。
//2024.5.17
//by white_ice
//P3045 [USACO12FEB] Cow Coupons G
#include <bits/stdc++.h>
#include <typeindex>
using namespace std;
#define itn long long
#define int long long
constexpr int oo = 50004;
itn n,k,m;
itn sk[oo];
bool vis[oo];
struct nod{int k,id,typ;}st[oo<<1];
int top;
bool cmp(nod a,nod b){return a.k==b.k?sk[a.id]>sk[b.id]:a.k<b.k;}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin >> n >> k >> m;
int a,b;
for (itn i=1;i<=n;i++){
cin >> a >> b;
sk[i] = a;
st[++top].id = i;
st[top].k = a;
st[top].typ = 0;
st[++top].id = i;
st[top].k = b;
st[top].typ = 1;
}
sort(st+1,st+top+1,cmp);
int num = 0;
for (itn i=1;i<=top;i++){
if (st[i].k>m)
break;
if (vis[st[i].id])
continue;
if (st[i].typ&&!k)
continue;
vis[st[i].id] = 1;
if (st[i].typ) k--;
m -= st[i].k;
num++;
}
cout << num;
return 0;
}
以上是一个错误做法，
但是在这个题中可以获得原数据100分的好成绩
错误方法就不说了
两组hack数据：
20 3 9130
423 107
883 602
400 45
734 159
360 223
937 719
259 124
188 23
7 1
819 690
63 58
290 44
944 733
750 278
843 425
841 461
911 410
113 3
390 30
590 257
答案19
2 1 5
2 1
1000 3
答案为2
（原题hack数据）
正解：
//2024.5.17
//by white_ice
//P3045 [USACO12FEB] Cow Coupons G
#include <bits/stdc++.h>
#define pi pair<int,int>
using namespace std;
#define itn long long
#define int long long
constexpr int oo = 50004;
itn n,k,m;
itn sk[oo];
int p[oo],c[oo];
bool vis[oo];
priority_queue<pair<int ,int>,vector<pi>,greater<pi>>s1,s2;
priority_queue<int,vector<int>,greater<itn>> del;
signed main() {
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin >> n >> k >> m;
for (itn i=1;i<=n;i++){
cin >> p[i] >> c[i];
s1.push(make_pair(p[i],i));
s2.push(make_pair(c[i],i));
}
for (itn i=1;i<=k;i++)
del.push(0);
int num = 0;
while (!s1.empty()&&m>=0){
pi a = s1.top();
pi b = s2.top();
if (vis[a.second]){
s1.pop();
continue;
}
if (vis[b.second]){
s2.pop();
continue;
}
if (del.top()>a.first-b.first){
m-=a.first;
s1.pop();
vis[a.second] = 1;
}
else {
m-=b.first+del.top();
del.pop();
vis[b.second] = 1;
del.push(p[b.second]-c[b.second]);
}
if (m>=0)
num++;
}
cout << num ;
return 0;
}
维护两个小根堆，
分别是折前价格和折后价格。
每次决策前将两组的最小值取出比较，
判断使用这一次优惠券能带来的最大收益，
用del堆维护收益，
由此判断是否选择使用。
一道数据结构典题
我用了分块打但是hack点始终t掉。。。
//2024.5.17
//by white_ice
//P3870 [TJOI2009] 开关
#include <bits/stdc++.h>
using namespace std;
#define itn int
constexpr int oo = 50004;
int n,m;
int sq[oo];
bitset<oo> st[oo];
int blok,ktt;
__inline int read(){
char c = getchar();int x = 0,f = 1;
while (c<'0'||c>'9'){if (c=='-')f = -1;c=getchar();}
while (c>='0'&&c<='9'){x = (x<<1)+(x<<3)+c-'0';c = getchar();}
return f*x;
}
__inline void change(itn x){
if (x == blok+1)
sq[x] = ktt-sq[x];
else sq[x] = blok - sq[x];
st[x].flip();
}
signed main() {
n = read(),m = read();
blok = sqrt(n);
ktt = n-blok*blok;
int a,b,c;
for (itn i=1;i<=m;i++){
c = read(),a = read(),b = read();
if (!c){
int p = (a-1)/blok+1;
int k = (b-1)/blok+1;
if (p==k){
for (itn i=a-(p-1)*blok;i<=b-(k-1)*blok;i++){
st[p][i] = ~st[p][i];
if (st[p][i])
sq[p]++;
else sq[p]--;
}
}
else{
for (itn i=a-(p-1)*blok;i<=blok;i++){
st[p][i] = ~st[p][i];
if (st[p][i])
sq[p]++;
else sq[p]--;
}
for (itn i=p+1;i<k;i++)
change(i);
for (itn i=1;i<=b-(k-1)*blok;i++){
st[k][i] = ~st[k][i];
if (st[k][i])
sq[k]++;
else sq[k]--;
}
}
}
else {
int out = 0;
int p = (a-1)/blok+1;
int k = (b-1)/blok+1;
if (p==k){
for (itn i=a-(p-1)*blok;i<=b-(k-1)*blok;i++){
if (st[p][i])
out++;
}
}
else {
for (itn i=a-(p-1)*blok;i<=blok;i++){
if (st[p][i])
out++;
}
for (itn i=p+1;i<k;i++)
out += sq[i];
for (itn i=1;i<=b-(k-1)*blok;i++){
if (st[k][i])
out++;
}
}
cout << out << '\n';
}
}
return 0;
}
整体就是非常纯粹简单的分块，
注意小散块的处理。
还有用bitset，真的非常好用。
带权并查集题目，
题中并没有要求在线，
所以我们对问题排序，优化程序
其中siz记录每个节点下子孙节点的个数，
通过遍历排序后的问题对答案求解。
依照题意对值大于k的节点进行查找。
//2024.5.27
//by white_ice
//P4185 [USACO18JAN] MooTube G
#include<bits/stdc++.h>
using namespace std;
#define itn int
constexpr itn oo = 100005;
itn jntm(itn a,itn b){return a>b?a:b;}
itn ngm (itn a,itn b){return a<b?a:b;}
inline int read(){
char c = getchar();int x = 0,f = 1;
while (c<'0'||c>'9'){if (c=='-')f = -1;c=getchar();}
while (c>='0'&&c<='9'){x = (x<<1)+(x<<3)+c-'0';c = getchar();}
return f*x;
}
itn n,q;
struct ask{int k,v,id;}que[oo];
bool cmp2(const ask &a,const ask &b){return a.k>b.k;}
namespace Disjointset{
struct edg{itn u,v,w;}st[oo];
bool cmp(const edg &a,const edg &b){return a.w>b.w;}
itn f[oo];
int siz[oo];
itn find(itn x){if (x==f[x])return x;
f[x]=find(f[x]);
return f[x];}
void init(){for(int i=1;i<=n;i++){f[i] = i;siz[i] = 1;}}
}
itn top=1;
int out[oo];
itn main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
using namespace Disjointset;
cin >> n >> q;
for (itn i=1;i<n;i++)
cin >> st[i].u >> st[i].v >> st[i].w;
for (itn i=1;i<=q;i++){
cin >> que[i].k >> que[i].v;
que[i].id = i;
}
init();
sort(st+1,st+n+1,cmp);
sort(que+1,que+q+1,cmp2);
for (itn i=1;i<=q;i++){
while (que[i].k<=st[top].w){
itn x = find(st[top].v);
itn y = find(st[top].u);
siz[x]+=siz[y];
f[y] = x;
top ++;
}
out[que[i].id] = siz[find(que[i].v)];
}
for (itn i=1;i<=q;i++)
cout << out[i]-1<< '\n';
return 0;
}
类似题：
这里我们使用pb_ds大显身手
即时向红黑树中添加新元素实现查询。
编写非常简单
//2024.5.17
//by white_ice
//P1168 中位数
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_cxx;
using namespace __gnu_pbds;
using namespace std;
#define itn int
constexpr int oo = 100005;
int n;
int idx;
itn st[oo];
struct node{
int x,tim;
bool operator <(node o) const{
if(x != o.x) return x < o.x;
else return tim < o.tim;
}
};
tree<node,null_type,less<node>,rb_tree_tag,tree_order_statistics_node_update> tre;
void insert(int x){tre.insert({x,++idx});}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin >> n;
cin >> st[1];
insert(st[1]);
cout << st[1] << '\n';
for (itn i=3;i<=n;i+=2){
cin >> st[i-1] >> st[i];
insert(st[i-1]);
insert(st[i]);
cout << (tre.find_by_order(i/2)->x) << '\n';
}
if (!n%2)
cin >> st[n];
return 0;
}