[Contest on 2021.8.27] 开学的日期临近 —— 丧钟为我而鸣!

目录

\(\text{[USACO18OPEN] Out of Sorts P}\)

解法

考场上一直在想一次整体的操作,然后就凉了…

这题有个很重要的结论:对于 \(i\),在 \(i-1\) 和 \(i\) 都成为分割点之前都会对冒泡排序产生贡献。

于是我们只需要计算出每个分割点出现的时间 \(t_i\),答案就是 \(\sum_{i=0}^{n-1}\max\{t_i,t_{i+1}\}\)。

而在 \(i\) 位置出现分割点意味着从小到大排名在 \([1,i]\) 之内的数全都回到了区间 \([1,i]\)。在冒泡排序中,如果一个数前面有 \(k\) 个比它大的数,它会向前移动 \(k\) 次。所以从小到大排名在 \([1,i]\) 之内的数向前次数是足够它回到 \([1,i]\) 的(我好像又说了废话),由此,那个数回到 \([1,i]\) 需要的次数实际上就是它与 \(i\) 的距离。

然后就好啦。需要注意的是,题目给的是 do-while,你可以把它理解成每个数字都至少动一次。

代码

#include <cstdio>
#define print(x,y) write(x),putchar(y)

template <class T>
inline T read(const T sample) {
	T x=0; char s; bool f=0;
	while((s=getchar())>'9' or s<'0')
		f|=(s=='-');
	while(s>='0' and s<='9')
		x=(x<<1)+(x<<3)+(s^48),
		s=getchar();
	return f?-x:x;
}

template <class T>
inline void write(const T x) {
	if(x<0) {
		putchar('-');
		write(-x);
		return;
	}
	if(x>9) write(x/10);
	putchar(x%10^48);
}

#include <algorithm>
using namespace std;

const int maxn=1e5+5;

int n,a[maxn],b[maxn];

bool cmp(int x,int y) {
	return a[x]==a[y]?x<y:a[x]<a[y];
}

int main() {
	n=read(9);
	for(int i=1;i<=n;++i)
		a[i]=read(9),
		b[i]=i;
	sort(b+1,b+n+1,cmp); 
	long long ans=0,lst=0,t=0;
	for(int i=1;i<=n;++i) {
		t=max(t,0ll+b[i]);
		ans+=max(lst,max(t-i,1ll));
		lst=max(t-i,1ll);
	}
	print(ans,'\n');
	return 0;
} 

\(\text{Tree Tweaking}\)

或 \(\rm usOJ\) 的 \(30258\)。

解法

我们称呼在 \([L,R]\) 中的点是*的。

先按顺序插入点 \(x\),若此时离 \(x\) 最近的左边的点为 \(l\),右边的点为 \(r\),那么 \(x\) 将插入二者之间,而且深度是 \(l,r\) 中后插入那个点的深度加一。

考虑不在 \([L,R]\) 中的点:对于 \(i<L\),它们形成的树的形态已经固定;对于 \(i>R\),这个点一定接在前面一个固定的点 \(j\) 上(点 \(j\) 本身可以是不固定的)。所以对于 \(i\in [1,L)\cup (R,n]\) 可以预处理 \(dep_{a_i}=dep_{a_j}+1\),其中 \(a_j\) 是对于 \(a_i\) 的 \(l,r\) 中后插入那个点,并将其加入答案。当 \(a_i\) 的祖先有在 \([L,R]\) 之间的点,那么这表示的是 \(a_i\) 与那个祖先的距离。

这就变成了确定了某棵树的中序遍历,要使所有节点深度和最小的问题。具体而言,加入所有 \(i<L\) 的点后,树中两个权值相邻的节点之间有一段未确定先后顺序的节点。找出这些连通块有两种方法:找到第一个连通块内的点后,找出它的 \(l,r\),并将 \([l,r]\) 内所有*的点加入块内;或者考虑使用数组 \(pre\),找到第一个连通块内的点后,将它的 \(pre\) 赋成一个特定的值,由于后面在连通块内的点通过 \(l,r\) 可以传递,就可以加在一个连通块内(我词穷了,还是看代码吧)。

对于每个连通块,令 \(dp_{i,j}\) 为 \((i,j)\) 中点的最小深度和。转移过程相当于在 \((i,j)\) 中选一个点当根,所以最后还要加上 \(p_j-p_i-1\)(即又新加了一层,注意这里是包含 \(i>R\) 的点的)。

时间复杂度 \(\mathcal O(n+(r-l+1)^3)\)。感觉自己又水了一篇博客

代码

#include <cstdio>
#define print(x,y) write(x),putchar(y)

template <class T>
inline T read(const T sample) {
	T x=0; char s; bool f=0;
	while((s=getchar())>'9' or s<'0')
		f|=(s=='-');
	while(s>='0' and s<='9')
		x=(x<<1)+(x<<3)+(s^48),
		s=getchar();
	return f?-x:x;
}

template <class T>
inline void write(const T x) {
	if(x<0) {
		putchar('-'),write(-x);
		return;
	}
	if(x>9) write(x/10);
	putchar(x%10^48);
} 

#include <set>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

const int maxn=1e5+5;

int p[maxn],n,a[maxn],L,R;
int dep[maxn],pre[maxn];
long long ans,dp[205][205];
set <int> st;
set <int> :: iterator it;
vector <int> g[maxn];

int main() {
	n=read(9);
	for(int i=1;i<=n;++i)	
		a[i]=read(9),p[a[i]]=i;
	L=read(9),R=read(9);
	st.insert(0),st.insert(n+1);
	for(int i=1;i<=n;++i) {
		int x=a[i];
		it=st.lower_bound(x);
		int r=*it,l=*(--it);
		if(i<L) {
			dep[x]=(p[l]<p[r]?dep[r]:dep[l])+1;
			ans+=dep[x];
		}
		else if(i<=R) {
			if(max(p[l],p[r])<L) {
				pre[x]=l;
				g[l].push_back(l);
				g[l].push_back(r);
				ans+=1ll*(r-l-1)*(p[l]<p[r]?dep[r]:dep[l]);
			}
			else {
				pre[x]=(p[l]<p[r]?pre[r]:pre[l]);
			}
			g[pre[x]].push_back(x);
		}
		else {
			dep[x]=(p[l]<p[r]?dep[r]:dep[l])+1;
			ans+=dep[x];
		}
		st.insert(x);
	}
	for(int i=0;i<=n+1;++i) {
		if(g[i].empty()) continue;
		sort(g[i].begin(),g[i].end());
		int m=g[i].size()-1;
		for(int j=0;j<m;++j)
			dp[j][j+1]=0;
		for(int len=2;len<=m;++len) {
			for(int j=0;j+len<=m;++j) {
				dp[j][j+len]=1e15;
				for(int k=1;k<len;++k)
					dp[j][j+len]=min(dp[j][j+len],dp[j][j+k]+dp[j+k][j+len]);
				dp[j][j+len]+=g[i][j+len]-g[i][j]-1;
			}
		}
		ans+=dp[0][m];
	}
	print(ans,'\n');
	return 0;
}
上一篇:Educational DP Contest R - Walk(倍增floyd,矩阵快速幂)


下一篇:Codeforces Harbour.Space Scholarship Contest 2021-2022/1553E Permutation Shift