Znzryb's Blog
0%

Posted on Edited on

题目大意

维护一个长度为 n 的数组，支持两类操作：

1）对区间 [l,r] 所有元素加上一个值。

2）查询单点 a[x] 的当前值。

P3368 BIT2 区别在于区间加减和单点查询

P3374 【模板】树状数组 1

视频教程

https://www.bilibili.com/video/BV1pE41197Qj?spm_id_from=333.788.recommend_more_video.-1&vd_source=4350e5f2584d2f27c848b347ea11b675

tr实际上是一个差分数组，只不过用了树状数组维护，a[ ]即原始数组就是diff的前缀和，所以甚至不需要再建一个前缀和数组

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

和这题代码基本一样，还是比较适合我复训的。

我们来解释一下为什么可以这样pushup

1
2
3
4
5
6
inline void invert(ll s,ll e){
	pushup(s, 1);
	if(e<n){
		pushup(e+1, -1);
	}
}

众所周知，我们知道差分数组是给diff[s]+1，给diff[e+1]-1，那为什么可以直接pushup那？那是因为树状数组中遍历你上面的数组是必然遍历不到你的，这点你不用担心，所以不用担心差分连续加导致出错。

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
#include <iostream>
typedef long long ll;
using namespace std;
const int maxn=5e5+10;
ll n,m,tr[maxn],a[maxn],x,y,k,op; // tr[] is difference array
inline int lowbit(ll x){
	return (x&(-x));	// two's complementary (6)x=110  (two's..)x=001+1=010 
} 
inline void add(ll p,ll v){ 
	while(p<n+1){
		tr[p]+=v;
		p+=lowbit(p);
	}
}
ll search(ll p){
	if(p==0) return 0;
	return search(p-lowbit(p))+tr[p];
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	// 这是在建树
	for(int i=1;i<=n;i++){			// tr[] is the diff array's BIT 
		tr[i]=a[i]-a[i-lowbit(i)];  // lowbit(i)=1 is the value of diff array
	}
	for(int _=1;_<=m;_++){
		cin>>op;
		if(op==1){
			cin>>x>>y>>k;   
			// 执行了两遍add操作，模拟差分
			add(x,k);		// walk around. convert range plus v to diff[L]+v && diff[R+1]-v
			if(y+1<=n)
				add(y+1,-k);
			
		}else{
			cin>>x;
			int ans=search(x);
			cout<<ans<<endl;
		}
	}
	// cin>>n;
}
// 30pts https://www.luogu.com.cn/record/180207859  add(y+1,k)->add(y+1,-k)
// AC https://www.luogu.com.cn/record/180209186

Posted on Edited on

题目大意

维护一个长度为 n 的数组，支持两类操作：

1）单点加上一个值。

2）查询区间 [l,r] 的元素和。

P3369 【模板】普通平衡树

似乎这题也可以用树状数组解决

https://zh.wikipedia.org/wiki/二補數

lowbit()原理详见这里

视频教程

https://www.bilibili.com/video/BV1ce411u7qP/?spm_id_from=333.337.search-card.all.click&vd_source=4350e5f2584d2f27c848b347ea11b675

区间和我们实际上是用两前缀和相减得到的

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
#include <iostream>
using namespace std;
const int maxn=5e5+10;
int n,m,tr[maxn],sumTr[maxn],x,y,k,op;
inline int lowbit(int x){
	return (x&(-x));	// two's complementary (6)x=110  (two's..)x=001+1=010 
} 
inline void add(int p,int v){ 
	while(p<n+1){  // 这里要注意，别写成p<n了，会全WA
		tr[p]+=v;
		p+=lowbit(p);  
	}
}
int search(int p){
	if(p==0) return 0;
	return search(p-lowbit(p))+tr[p];
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>tr[i];
	}
	for(int i=1;i<=n;i++){
		sumTr[i]=tr[i]+sumTr[i-1];
	}
	for(int i=1;i<=n;i++){
		tr[i]=sumTr[i]-sumTr[i-lowbit(i)];
	}
	for(int _=1;_<=m;_++){
		cin>>op;
		if(op==1){
			cin>>x>>k;
			add(x,k);
		}else{
			cin>>x>>y;
			int ans=search(y)-search(x-1);  // 区间和我们实际上是用两前缀和相减得到的
			cout<<ans<<endl;
		}
	}
}
// AC https://www.luogu.com.cn/record/180138960

Posted on Edited on

题目大意

给定两个长度为 n 的 01 字符串 a、b，以及 m 次区间操作。每次操作可以选择是否交换区间 [l,r] 内 a 与 b 对应位置的字符。目标是经过若干选择后，使最终得到的 a 的字典序尽可能小，输出最小的结果字符串。

https://class.luogu.com.cn/classroom/LGR197

比赛的时候暴力法打了20分，record：

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

前面暴力没搞对是发现是有个双重循环写错了

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
#include <iostream>
#include <bitset>
using namespace std;
const int maxn=2e5+10;
int n,m,l[maxn],r[maxn];
char a[maxn],b[maxn],c[maxn];
// bool vis[maxn];
void out() {
    for(int i=1;i<=n;i++) {
        cout<<c[i];
    }
    cout<<endl;
}
inline void compare(){
    for(int i=1;i<=n;i++) {
        if(c[i]>a[i])
            break;
        if(a[i]>c[i]) {
            for(int j=1;j<=n;j++) {
                c[j]=a[j];       // 双重循环一定要小心，前面WA是因为c[i]=a[i]
            }
            break;
        }
    }
}
void dfs(int x) {
    // out();
    // compare();
    if(x>m)
        return;
    for(int i=l[x];i<=r[x];i++) {
        swap(a[i],b[i]);
    }
    compare();
    dfs(x+1);
    for(int i=l[x];i<=r[x];i++) {
        swap(a[i],b[i]);
    }
    // compare();
    dfs(x+1);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++) {
        cin>>b[i];
    }
    for(int _=1;_<=m;_++) {
        cin>>l[_]>>r[_]; 
    }
    for(int i=1;i<=n;i++)
        c[i]=a[i];
    dfs(1);
    for(int i=1;i<=n;i++) {
        cout<<c[i];
    }
    cout<<endl;
    return 0;
}

Posted on Edited on 
1
2
3
4
5
6
#include <iostream>
#include <cstdlib>
using namespace std;
int main(){
	cout<<rand()<<endl;
}
1
41

Posted on Edited on

题目大意

有 nn 个大小不同的圆盘（编号 1simn1sim n，编号越大盘越大），初始时它们以任意方式套叠在三根柱子 A,B,CA,B,C 上（输入给出每根柱子从上到下的圆盘编号；用 0 表示空）。

同样给出一个目标状态。要求在满足：

  • 每次只能移动一个圆盘

  • 不能把大盘放在小盘上

的前提下，用最少步数把初始状态变到目标状态。

输出每一步操作 move I from P to Q，最后输出最少步数。

63pts, 期待以后的自己

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
#include <iostream>
#include <vector> 
#include <algorithm>
using namespace std;
const int maxn=50;
int n,n1,a1,now[maxn],ob[maxn]; //ob is abbreviation of object;
vector<int> hanoi[5],cache;
long long ans;
char ForOut[4]={'0','A','B','C'};
// bool vis[maxn];
//void debug(){
//	for(int i=1;i<=3;i++){
//		for(int j=0;j<hanoi[i].size();j++)
//			cout<<hanoi[i][j]<<" ";
//		cout<<endl;
//	}
//		
//}
inline void out(int st,int ed,int x){
	ans+=1;
	cout<<"move "<<x<<" from "<<ForOut[st]<<" to "<<ForOut[ed]<<endl;
}
inline bool check(int x){
	for(int i=1;i<=3;i++)
		if(!hanoi[i].empty() && x==hanoi[i].back() /*&& x<hanoi[c].back()*/ /*&& !vis[x]*/)
			return true;
	return false;
}
inline void upd(int x,int c){
	hanoi[now[x]].pop_back();
	hanoi[c].push_back(x);
	swap(now[x],c);
}
void solve(int a,int b,int c,int x){
	if(check(x)){
		if(!hanoi[c].empty() && x>hanoi[c].back()){
			solve(c,a,b,hanoi[c].back());
		}
		out(now[x],c,x);
		upd(x,c);
		return;
	}
	for(int i=x-1;i>=1;i--){
		if(now[i]==b) continue;  // If big plates on b(tool column) just ignore it 
		solve(now[i],6-now[i]-b,b,i);
	}
	out(a,c,x);
	upd(x,c);
}
bool cmp(int a,int b){
	if(a!=b) return a>b;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=3;i++){
		cin>>n1;
		for(int _=1;_<=n1;_++){
			cin>>a1;
			now[a1]=i;
			cache.push_back(a1);
		}
		sort(cache.begin(),cache.end(),cmp);
		for(int j=0;j<cache.size();j++)
			hanoi[i].push_back(cache[j]);
		cache.clear();
	}
	for(int i=1;i<=3;i++){
		cin>>n1;
		for(int _=1;_<=n1;_++){
			cin>>a1;
			ob[a1]=i;
		}
	}
	// debug();
	for(int i=n;i>=1;i--){
		if(now[i]!=ob[i])
			/*vis[i]=true,*/solve(now[i],6-now[i]-ob[i],ob[i],i);
	}
	cout<<ans<<endl;
	cin>>n;
}
// https://www.luogu.com.cn/problem/P1242
// It is clear from the above: to move K from X to Y, part of the minimum number 
// of operations must be performed so that the disc with a number less than K 
// must be moved to Z.
// 45pts https://www.luogu.com.cn/record/179798145 error because of put 6 on 5
// I add a bool vis && cache.
// the inputs are not necessary to be sorted
// 63pts https://www.luogu.com.cn/record/179814530