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[]的逆序对即可