8.20

2024-03-25 17:56:04

P3388 【模板】割点（割顶）


void tarjan(int u,int fa){
    dfn[u]=low[u]=++chuo;
    int son=0;
    ee(i,u){
        int v=e[i].v;
        if(!dfn[v]){
            tarjan(v,fa),low[u]=min(low[u],low[v]);
            if(u==fa)son++;
            if(u==fa && son>=2)gd[u]=1;
            if(u!=fa && low[v]>=dfn[u])gd[u]=1;
        }
        else low[u]=min(low[u],dfn[v]);
    }
}

[POJ2762]Going from u to v or from v to u?

题意：
判断一个有向图是否弱连通。(从u->v 有一条道路或从v->u有一条道路)

SOL：

Tarjan缩点。然后判断原图是否是一条链。

因为如果缩点图有分叉，则分叉之间一定是不可达的，所以原图必然是一条链。

考虑链的特性：有且仅有一点入度为0，有且仅有一点出度为0。

因此缩点后直接判断入度为0和出度为0的点的个数是否均为1即可。

【1】：C-1 读题读太久又不会做……温得痛。

0x05 基本算法-排序

{lyd排序例题}动态中位数

用vector代替对顶堆

代码

货仓选址

假设选定的货仓左边有a个货仓，右边有b个货仓，若把选定货仓的坐标向右移一格，if(a<b)ans减小b-a的距离;
同理，向左移一格，if(a>b)ans减小a-b的距离;

若a==b，则ans达到最小值，所以选定的数应该是中位数。

若n为奇数，mid=(n+1)/2;
若n为偶数，选择mid=n/2和n/2+1之间任意一点都行，不如直接取mid=(n+1)/2;

代码

Ultra-QuickSort

冒泡排序要交换的次数其实就是逆序对的个数

八数码与逆序对的联系

八数码问题的有解无解的结论：

一个状态表示成一维的形式，求出除0之外所有数字的逆序对之和

若两个状态的逆序奇偶性相同，则可相互到达，否则不可相互到达。

由于原始状态的逆序为0（偶数），则逆序为偶数的状态有解。

也就是说，逆序的奇偶将所有的状态分为了两个等价类，同一个等价类中的状态都可相互到达。

1.当左右移动空格时，逆序不变。

2.当上下移动空格时，相当于将一个数字向前（或向后）移动两格（n* n的棋盘是n-1格，前提是n为奇数），跳过的这两个数字要么都比它大（小），逆序可能±2；要么一个较大一个较小，逆序不变。所以可得结论：只要是相互可达的两个状态，它们的逆序奇偶性相同。我想半天只能说明这个结论的必要性，详细的证明请参考后面的附件。

N×N的棋盘，N为奇数时，与八数码问题相同。

1.N为偶数时

空格每上下移动一次，奇偶性改变。称空格位置所在的行到目标空格所在的行步数为空格的距离（不计左右距离），若两个状态的可相互到达，则有，两个状态的逆序奇偶性相同且空格距离为偶数，或者，逆序奇偶性不同且空格距离为奇数。否则不能。

也就是说，当此表达式成立时，两个状态可相互到达：(状态1奇偶性==状态2奇偶性)==(空格距离%2==0)。

2.N为奇数时

同八数码问题

推广到三维N×N×N

其实，三维的结论和二维的结论是一样的。

考虑左右移动空格，逆序不变；同一层上下移动空格，跨过N-1个格子；上下层移动空格，跨过N^2-1个格子。

当N为奇数时，N-1和N^2-1均为偶数，也就是任意移动空格逆序奇偶性不变。那么逆序奇偶性相同的两个状态可相互到达。

当N为偶数时，N-1和N^2-1均为奇数，也就是令空格位置到目标状态空格位置的y z方向的距离之和，称为空格距离。若空格距离为偶数，两个逆序奇偶性相同的状态可相互到达；若空格距离为奇数，两个逆序奇偶性不同的状态可相互到达。

拼数

/*
translation:
    

设有n个正整数(n≤20)，将它们联接成一排，组成一个最大的多位整数。

例如：n=3时，3个整数13,312,343联接成的最大整数为：34331213

solution:
    sort对字符串排序只能是c++中string类型
    两种方法：
    1.bool cmp(const string &a,const string &b){
        return a+b>b+a;
    }
    2.自己手写
note:
    *字符串排序 
date:
    2019.07.10
    2019.08.20
*/

P1496 火烧赤壁

    rd(n);
    rep(i,1,n){
        rd(a[i]),rd(b[i]);
        de[++tot]=a[i];
        de[++tot]=b[i]; 
    }
    sort(de+1,de+tot+1);
    tot=unique(de+1,de+tot+1)-(de+1);
    rep(i,1,n){
        a[i]=lower_bound(de+1,de+tot+1,a[i])-de;
        b[i]=lower_bound(de+1,de+tot+1,b[i])-de;
        add[a[i]]++;
        add[b[i]]--;
    }
    int temp=0;
    rep(i,1,tot){
        temp+=add[i];
        if(temp){
            ans+=de[i+1]-de[i];
        }
    }
    printf("%d",ans);

P3871 [TJOI2010]中位数

vector水题……

学到了：
op为字符的时候，

char op[5];

scanf("%s",op);

if(op[0]=='你叉叉'){

}

else {

}

隐藏的逆序对：

P5149 会议座位

P1966 火柴排队

现在你有两个数组，从A数组变到B数组要变几次
我们可以开第三个数组：x[A[i]]=B[i];

求x[]的逆序对即可

码农公寓