Znzryb's Blog
0%

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







Posted on Edited on

题目大意

这篇笔记对应的是「set 自定义 cmp 排序」：讲的是在 C++ 里如何为 set（以及类似容器）自定义比较器 cmp，从而改变元素的排序规则（例如从大到小排序），以及与默认比较方式的区别。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <set>
#include <iterator>
using namespace std;
int p[7]={0,4,3,2,1};
struct cmp{
	bool operator()(int a,int b){
		if(a!=b) return p[a]<p[b];
	}
};
set<int,cmp > g; // 一般来说像set，priority_queue都是传入cmp，less<int> 这样的结构体
int main(){
	g.insert(1);g.insert(2);g.insert(3);g.insert(4);
	for(set<int>::iterator it=g.begin();it!=g.end();it++)
		cout<<*it<<endl;
	set<int>::iterator it=g.end();
	advance(it,-1);
	cout<<"back: "<<*it<<endl;
	g.clear();
	cout<<g.empty()<<endl;
}
1
2
3
4
5
6
4
3
2
1
back: 1
1

优先队列的比较符号是反的，解释详情见

https://www.nowcoder.com/discuss/353157988535967744

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <queue>
using namespace std;
struct cmp {
	bool operator() (pair<int, int> a,  pair<int, int> b)  {
		// 如果第二个元素不同，则按照第二个元素比较
		if (a.second != b.second)
			return a.second > b.second;  // 如果想要最小堆，这里使用 >
	}
};
int a[]={1,2,4,1,492,412,3};

1
2
3
4
5
6
1 1
1 2
1 3
2 6
3 9
1 1 2 3 4 412 492

Posted on Edited on

Wine 如何打开devcpp
wine “/Users/zzy/.wine/drive_c/Program Files (x86)/Dev-Cpp/devcpp.exe”