Znzryb's Blog
0%

Posted on Edited on

思路讲解

来学习一下ST表（sparse table 稀疏表）

算了，我发现树状数组也不是不行，哈哈，我还是用我熟悉的树状数组

https://www.cnblogs.com/qdscwyy/p/9759220.html

我们来解释一些代码吧

1
2
3
4
// 1个大区间想要遍历下面的小区间需要这么写
for(int i=1;i<low;i<<=1){
	trd[x]=max(trd[x-i],trd[x]);
}

为什么需要这么写？

8→二进制100→维护区间8−lowbit(8)～88\xrightarrow{二进制}100\xrightarrow{维护区间}8-lowbit(8)～8

lowbit(8)=23=2二进制中第一个1在第几位lowbit(8)=2^3=2^{二进制中第一个1在第几位}

AC代码

AC

https://www.luogu.com.cn/record/199551454

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = b; i >= a; --i)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(5e4)+10;

ll N,T,H[MAXN],trx[MAXN],trd[MAXN];
inline ll lowbit(ll x){
	return x&(-x);
}
inline void updx(ll x,ll k){	// 更新小数数组
	// 将x位置替换为k
	while (x<=N) {
		trx[x]=k;
		ll low=lowbit(x);
		// 1个大区间想要遍历下面的小区间需要这么写
		for(int i=1;i<low;i<<=1){
			trx[x]=min(trx[x-i],trx[x]);
		}
		x+=lowbit(x);
	}
}
inline void updd(ll x,ll k){	// 更新大数数组
	// 将x位置替换为k
	while (x<=N) {
		trd[x]=k;
		ll low=lowbit(x);
		// 1个大区间想要遍历下面的小区间需要这么写
		for(int i=1;i<low;i<<=1){
			trd[x]=max(trd[x-i],trd[x]);
		}
		x+=lowbit(x);
	}
}
inline ll queryx(ll a,ll b){
	ll res=1e18;
	while (b>=a) {
		res=min(H[b],res);
		b-=1;
		for(;b-lowbit(b)>=a;b-=lowbit(b)){
			res=min(trx[b],res);
		}
	}
	return res;
}
inline ll queryd(ll a,ll b){
	ll res=0;
	while (b>=a) {
		res=max(H[b],res);
		b-=1;
		for(;b-lowbit(b)>=a;b-=lowbit(b)){
			res=max(trd[b],res);
		}
	}
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>T;
	FOR(i, 1, N){
		cin>>H[i];
	}
	memset(trx, 0x3f, sizeof(trx));
	FOR(i, 1, N){
		updd(i, H[i]);
		updx(i, H[i]);
	}
	while (T--) {
		ll l,r;
		cin>>l>>r;
		cout<<queryd(l, r)-queryx(l, r)<<'\n';
	}
	return 0;
}
/*
6 3
1
7
3
4
2
5
1 5
4 6
2 2
AC https://www.luogu.com.cn/record/199551454
*/

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

树状数组+二分

你可以理解为用树状数组的区间加减加速模拟法（模拟法最大的瓶颈不就是区间加减吗？）

image

然后分数是只增不减的，初始分数比别人低，经过N次比赛后也不会比别人高

所以我们就能够用二分法找到区间的L，和R

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
inline ll findl(ll x){
	ll l=1,r=MAXrange;
	while (l<r) {
		ll mid=l+r>>1;
		if(search(mid)>=x){
			r=mid;	// 太大了，小一点
		}else{
			l=mid+1;
		}
	}
	return l;
}
inline ll findr(ll x){
	ll l=1,r=MAXrange;
	while (l<r) {
		ll mid=l+r+1>>1;
		if(search(mid)<=x){
			l=mid;
		}else{
			r=mid-1;
		}
	}
	return l;
}

AC代码

AC

https://atcoder.jp/contests/abc389/submissions/61877078

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)
	

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(2e5)+10,MAXrange=7e5+10;

ll N,Q;
vector<pll> lr(MAXN);
ll tr[MAXrange];
inline ll lowbit(ll x){
	return x&(-x);
}
inline void add(ll x,ll l, ll r){
	while (l<=MAXrange) {
		tr[l]+=x;
		l+=lowbit(l);
	}
	r+=1;
	while(r<=MAXrange){
		tr[r]-=x;
		r+=lowbit(r);
	}
}
inline ll search(ll x){
	ll res=0;
	while (x>0) {
		res+=tr[x];
		x-=lowbit(x);
	}
	return res;
}
inline ll findl(ll x){
	ll l=1,r=MAXrange;
	while (l<r) {
		ll mid=l+r>>1;
		if(search(mid)>=x){
			r=mid;	// 太大了，小一点
		}else{
			l=mid+1;
		}
	}
	return l;
}
inline ll findr(ll x){
	ll l=1,r=MAXrange;
	while (l<r) {
		ll mid=l+r+1>>1;
		if(search(mid)<=x){
			l=mid;
		}else{
			r=mid-1;
		}
	}
	return l;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N;
	FOR(i, 1, N){
		cin>>lr[i].first>>lr[i].second;
	}
	// 	初始化dp
	FOR(i, 1, MAXrange){
		// 在i～i区间上区间加i（实际上就是我懒得建树）
		add(i, i, i);
	}
	FOR(i, 1, N){
		ll l=findl(lr[i].first);
		ll r=findr(lr[i].second);
		// 如果找到的r端点的值（现在的分数）连左端点都不满足，说明查找失败
		if(search(r)<lr[i].first){
			continue;
		//  如果找到的l端点的值（现在的分数）连右端点都不满足，也说明查找失败
		}else if(search(l)>lr[i].second){
			continue;
		}
		add(1,l,r);
	}
	cin>>Q;
	FOR(_, 1, Q){
		ll x;
		cin>>x;
		cout<<search(x)<<'\n';
	}
	return 0;
}
// AC https://atcoder.jp/contests/abc389/submissions/61877078

心路历程（WA，TLE，MLE……）

提交了好多次RE，发现可能是C++23不支持宏定义了

Posted on Edited on

思路讲解

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
using namespace std;

int parent[100002];
int order[100002];

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n + 1; i++) {
        parent[i] = i;
    }
    for (int i = 1; i <= n; i++) {
        order[i] = 0;
    }
    int current_order = 1;
    for (int i = 0; i < q; i++) {
        int op;
        cin >> op;
        if (op == 1) {
            int l, r;
            cin >> l >> r;
            int x = find(l);
            while (x <= r) {
                if (order[x] == 0) {
                    order[x] = current_order;
                    current_order++;
                    parent[x] = x + 1;
                }
                x = find(x);
            }
        } else if (op == 2) {
            int x;
            cin >> x;
            cout << order[x] << endl;
        }
    }
    return 0;
}

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

Ans(需要最大化)=k1+k2+⋯+knAns(需要最大化)=k_1+k_2+\cdots+k_n

k12∗p1+k22∗p2+⋯+kn2∗pn≤Mk_1^2*p_1+k_2^2*p_2+\cdots+k_n^2*p_n\leq M

购买第 i 种产品的第 j 个花费是

(j2−(j−1)2)∗pi→化简（2j−1）∗pi(j^2-(j-1)^2)*p_i\xrightarrow{化简}（2j-1）*p_i

那不难发现，我们有一个贪心策略，就是优先买便宜的东西，再买贵的东西。

当然，直接这样搞的话，肯定TLE，我们需要找一个价格阈值x，小于x的东西我们买，大于x的东西我们就不买了，最后看总花费是否 ≤ M

https://www.luogu.com.cn/article/imo508fb 然后你会发现WA了两个点，

hack数据：

1
2
3
4
5
6
7
2 25
1 1

应该输出：
7
错误输出：
6

同样起始价格为1，有时要买3个，有时要买4个，那怎么解决？

加了下面的小根堆就万无一失了，因为我们将刚刚超过价格阈值的全部记录下来，再跑一遍看看有没有遗失的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 下面就是把check(l)的过程再跑了一遍，只不过加了小根堆
ll cost=0;
for(int i=1;i<=N;++i){
	ll j=(l/P[i]+1)/2;
	cost+=j*j*P[i];
	pq.push((2*(j+1)-1)*P[i]);
}
while (!pq.empty()) {
	if(cost+pq.top()>M){
		break;
	}else{
		ans+=1;
		cost+=pq.top();
		pq.pop();
	}
}
cout<<ans<<'\n';

AC代码

AC https://atcoder.jp/contests/abc389/submissions/61888808

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>

using namespace std;

typedef unsigned long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(2e5)+10;

ll N,M,P[MAXN],ans;
// 小根堆
priority_queue<ll , vector<ll>, greater<ll>> pq;

inline bool check(ll x){
	ll cost=0,res=0;
	for(int i=1;i<=N;++i){
		ll j=(x/P[i]+1)/2;
		if(j==0)	// 防除零
			continue;
		// 防溢出
		if(j*P[i] > (M-cost)/j){
			return false;
		}
		cost+=j*j*P[i];
		res+=j;
		if(cost>M){
			return false;
		}
	}
	ans=max(ans,res);
	return true;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>M;
	for(int i=1;i<=N;++i){
		cin>>P[i];
	}
	sort(&P[1],&P[N+1]);
	ll l=0,r=M;
	while (l<r) {
		ll mid=l+r+1>>1;
		if(check(mid)){
			l=mid;
		}else{
			r=mid-1;
		}
	}
	// 下面就是把check(l)的过程再跑了一遍，只不过加了小根堆
	ll cost=0;
	for(int i=1;i<=N;++i){
		ll j=(l/P[i]+1)/2;
		cost+=j*j*P[i];
		pq.push((2*(j+1)-1)*P[i]);
	}
	while (!pq.empty()) {
		if(cost+pq.top()>M){
			break;
		}else{
			ans+=1;
			cost+=pq.top();
			pq.pop();
		}
	}
	cout<<ans<<'\n';
	return 0;
}
/*
2 25
1 1
AC https://atcoder.jp/contests/abc389/submissions/61888808
*/

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

参考题解

https://ac.nowcoder.com/discuss/1452143

1
2
3
// 以陪第i只猪猪为结束需要多少消耗
// 注意，这里的第i只猪猪是按照a排序过的顺序的第i个（cmp顺序）
ll dp[MAXN];

直接记忆化会导致TLE，所以我进行了一些小小的优化，具体见图

那一大段被注释掉的就是搜索程序

image

当然，改动之后dp里装的就是以前1～i位为末尾的最优的情况（最少的消耗）。

1
2
3
4
for(int i=1;i<=N;++i){
	if(i!=1) dp[i]=min(dfs(i),dp[i-1]);
	else dp[i]=dfs(i);
}

所以这个程序其实是个伪装成记忆化搜索的递推！

那为什么不直接写递推那？还不是不太直接想的出来。。。

AC代码

AC

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=74795179

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(1e5)+10;
struct abVal{
	ll a;ll b;ll val;
	bool operator<(const abVal &other) const{
		return  a<other.a;
	}
};
vector<abVal> info(MAXN);	// 存储全部题目给出的信息
       // 所有猪猪都不陪伴消耗的总金钱
ll N,M,sumVal;
// 以陪第i只猪猪为结束需要多少消耗
// 注意，这里的第i只猪猪是按照a排序过的顺序的第i个（cmp顺序）
ll dp[MAXN];
bool cmp(abVal a,abVal b){
	return a.a<b.a;
}
ll dfs(int x){
	if(x==0) return sumVal; // 搜索的终点
	if(dp[x]!=-1) return dp[x];	 // 记忆化搜索	
	//                                   我们需要它找到比a-M刚好大一个或者等于的
	ll st=lower_bound(info.begin()+1, info.begin()+x, abVal{info[x].a-M,9999999,9999999})-info.begin()-1;	// start
	if(st==0){	// 没找到
		// 直接用通式计算    陪的代价              不陪的代价
		dp[x]=min(sumVal-info[x].val+info[x].b,sumVal);
		return dp[x];
	}
	//                   陪的代价            不陪的代价
	dp[x]=min(dfs(st)-info[x].val+info[x].b,dfs(st));
//	for(int i=st;i>=1;--i){
//		if(dp[x]==-1){
//			// 第一次我们就直接赋值  陪的代价            不陪的代价
//			dp[x]=min(dfs(i)-info[x].val+info[x].b,dfs(i));
//		}else{ //          陪的代价                        不陪的代价
//			dp[x]=min({dfs(i)-info[x].val+info[x].b,dp[x],dfs(i)});
//		}
//	}
	return dp[x];
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N>>M;
	for(int i=1;i<=N;++i){
		cin>>info[i].a;
	}
	for(int i=1;i<=N;++i){
		cin>>info[i].b>>info[i].val;
		sumVal+=info[i].val;
	}
	sort(&info[1],&info[N+1],cmp);
	memset(dp, -1, sizeof(dp));
	for(int i=1;i<=N;++i){
		if(i!=1) dp[i]=min(dfs(i),dp[i-1]);
		else dp[i]=dfs(i);
	}
	ll ans=sumVal;
	for(int i=1;i<=N;++i){
		ans=min(ans,dp[i]);
	}
	cout<<ans<<'\n';
	return 0;
}

心路历程（WA，TLE，MLE……）

直接记忆化会喜提TLE

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=74794988