Znzryb's Blog

P1242 新汉诺塔

Posted on 2024-10-04 Edited on 2026-04-06

题目大意

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

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

每次只能移动一个圆盘
不能把大盘放在小盘上

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

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

63pts, 期待以后的自己

#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

Compare函数/类的使用

Posted on 2024-10-04 Edited on 2026-04-06

题目大意

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

#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;
}

4
3
2
1
back: 1
1

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

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

#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 1
1 2
1 3
2 6
3 9
1 1 2 3 4 412 492

wine打开CPP命令

Posted on 2024-10-04 Edited on 2026-02-11

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

P3369 【模板】普通平衡树

Posted on 2024-10-04 Edited on 2026-04-06

题目大意

维护一个动态可重集合 M，需要支持以下操作：

插入一个数 x。
删除一个数 x（若有多个相同值，只删除一个）。
查询集合中严格小于 x 的元素个数，并将结果加 1 输出。
查询集合按从小到大排序后，第 x 小的数。
查询 x 的前驱：小于 x 且最大的数（不保证 x 在集合中，但保证答案存在）。
查询 x 的后继：大于 x 且最小的数（不保证 x 在集合中，但保证答案存在）。

P3224 [HNOI2012] 永无乡

主要是发现此题寻找第k大的连通块需要平衡二叉树，不学不行，故来学习。

参考博客

https://writings.sh/post/fhq-treap

其他OJ

https://loj.ac/p/104

参考视频

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

#include<bits/stdc++.h>

typedef long long ll;
using namespace std;
const ll MAXN=static_cast<ll>(1e5+10);
int cnt,root;

struct Node {
    int l,r;
    int val;
    int key;
    int size; // size
}fhq[MAXN];

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

inline int newnode(int val) {
    fhq[++cnt].val=val;
    fhq[cnt].key=rng();
    fhq[cnt].size=1;
    return cnt;
}

inline void update(int now) {
    fhq[now].size=fhq[fhq[now].l].size+fhq[fhq[now].r].size+1;
}

// 分裂之后左子树全部是比val值<=的，右子树全部是比y>=的
//                         左子树    右子树
void split(int now,int val,int &x,int &y) {
    if(!now) x=y=0;
    else {
        if(fhq[now].val<=val) {
            x=now;
            // 继续分裂右子树，因为左树<=val，无需再进行分裂，右树还需要继续分裂
            split(fhq[now].r,val,fhq[now].r,y);
        }else {
            y=now;
            split(fhq[now].l,val,x,fhq[now].l);
        }
        update(now);
    }
}

int merge(int x,int y) {
    if(!x||!y) return x+y;
    // 按照二叉堆的性质，y一定再x的下面（大根堆）
    if(fhq[x].key>fhq[y].key) {
        // 按照二叉搜索树，x<y,y在x的右边，综上，y在x的右下
        fhq[x].r=merge(fhq[x].r,y);
        update(x);
        return x;
    }else {
        // 按照二叉堆的性质，x一定在y的下面（大根堆）
        fhq[y].l=merge(x,fhq[y].l);
        update(y);
        return y;
    }
}

int x,y,z;

inline void ins(int val) {
    // 按值分裂，将树分为x，y
    split(root,val,x,y);
    // 合并树x，树y，新节点val
    root=merge(merge(x,newnode(val)),y);
}

inline void del(int val) {
    split(root,val,x,z);
    // 此时y树上所有值全部等于val
    split(x,val-1,x,y);
    // 不要y树的根节点，也就是把他的左子树和右子树合并
    y=merge(fhq[y].l,fhq[y].r);
    root=merge(merge(x,y),z);
}

inline void getrank(int val) {
    split(root,val-1,x,y);
    cout<<fhq[x].size+1<<endl;
    root=merge(x,y);
}

inline void getnum(int rank) {
    int now=root;
    while(now) {
        if(fhq[fhq[now].l].size+1==rank)
            break;
        // 当前节点rank比较大，要找的点在左子树上，令当前节点为左子树
        else if(fhq[fhq[now].l].size>=rank)
            now=fhq[now].l;
        else {
            rank-=fhq[fhq[now].l].size+1;
            now=fhq[now].r;
        }
    }
    cout<<fhq[now].val<<endl;
}

inline void pre(int val) {
    split(root,val-1,x,y);
    // 前驱就是分裂出来的x树上最右边的点
    int now=x;
    // 不断向右走直到没有点了
    while (fhq[now].r) {
        now=fhq[now].r;
    }
    cout<<fhq[now].val<<endl;
    root=merge(x,y);
}

inline void nxt(int val) {
    split(root,val,x,y);
    int now=y;
    while (fhq[now].l)
        now=fhq[now].l;
    cout<<fhq[now].val<<endl;
    root=merge(x,y);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int n;
    cin>>n;
    for(int i=1;i<=n;++i) {
        int opt,xopt;
        cin>>opt>>xopt;
        switch (opt) {
            case 1:
                ins(xopt);
                break;
            case 2:
                del(xopt);
                break;
            case 3:
                getrank(xopt);
                break;
            case 4:
                getnum(xopt);
                break;
            case 5:
                pre(xopt);
                break;
            case 6:
                nxt(xopt);
                break;
        }
    }
}
// AC https://www.luogu.com.cn/record/190721203

P3224 [HNOI2012] 永无乡

Posted on 2024-10-04 Edited on 2026-04-06

题目大意

有 $n$ 座岛（编号 $1sim n$ ），每座岛有一个“重要度排名” $p_i$ （是 $1\sim n$ 的一个排列，数值越小表示越重要）。初始有 m 座桥形成无向图，之后还会有 q 次操作：

B x y：在岛 x 与 y 之间新建一座桥。
Q x k：在当前与岛 x 连通的所有岛中，找出“重要度排名第 $k$ 小”的岛，输出该岛编号；若不存在则输出 $-1$ 。

思路讲解

这是此题的退化版（<10）

AC代码

源代码

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

40pts，TLE，不用平衡树stl的set合并太慢了。

源代码

//https://www.luogu.com.cn/problem/P3224
#include <iostream>
#include <vector>
#include <set>
#include <iterator>
using namespace std;
const int maxn=1e5+10;
int n,q,u,v,k,m,fa[maxn],p[maxn];  // fa is disjointed set to upd connected components
char op;
struct cmp{
    bool operator()(int a,int b){
        if(a!=b) return p[a]<p[b];
    }
};
set <int,cmp > g[maxn];
int find(int x){
    if(fa[x]!=x){
        fa[x]=find(fa[x]); // compress path
        return fa[x];
    }else{
        return x;
    }
}
void unionn(int i,int j){
    int i_fa=find(i);
    int j_fa=find(j);
    fa[j_fa]=i_fa;
    g[i_fa].insert(g[j_fa].begin(),g[j_fa].end());
    g[j_fa].clear();	
}
inline void query1(){
    unionn(u,v);
}
inline void query2(){
    int v_fa=find(v),cnt=0;
    set<int>::iterator it=g[v_fa].begin();
    if(g[v_fa].size()<k){
        cout<<-1<<endl;return;
    }
    advance(it,k-1);
    cout<<*it<<endl;	
}
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];
    }
    for(int i=1;i<=n;i++) fa[i]=i,g[i].insert(i);  //initialize disjointed set.
    for(int _=1;_<=m;_++){
        cin>>u>>v;query1();
    }
    cin>>q;
    for(int _=1;_<=q;_++){
        cin>>op;
        if(op=='B')
            cin>>u>>v,query1();
        else
            cin>>v>>k,query2();
    }
    cin>>n;
}
// 40pts https://www.luogu.com.cn/record/179949072