倍增基础练习题

syoj 806. 序列翻转

P6148 [USACO20FEB] Swapity Swapity Swap S

\(n\) 个进行 \(m\) 次操作，每次操作将所给的 \(l\) 到 \(r\) 区间进行翻转。一共会重复 \(k\) 次上述操作。 \(k<=1e9\)。

倍增 \(k\)，设 \(f[i][j]\) 表示总操作重复 \(2^i\) 次后的序列。

预处理时，转移方程为 \(f[i][j]=f[i-1][f[i-1][j]]\)，即从上一次答案两次操作后转移过来。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,k;
int f[32][N],ans[N];
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++) f[0][i]=i;
	for(int i=1;i<=m;i++){
		int l,r;
		scanf("%d%d",&l,&r);
		reverse(f[0]+l,f[0]+r+1);
	}
	for(int i=1;i<32;i++)
		for(int j=1;j<=n;j++) f[i][j]=f[i-1][f[i-1][j]];
	for(int i=1;i<=n;i++) ans[i]=i;
	int cnt=0;
	while(k){
		if(k&1) for(int i=1;i<=n;i++) ans[i]=f[cnt][ans[i]];
		k>>=1;
		cnt++;
	}
	for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
	return 0;
} 

syoj 877. 飞行的小鸟

P3509 [POI2010] ZAB-Frog

经典题目。单调队列优化 dp + 倍增。

\(n\) 个点进行 \(m\) 次操作。对于每个点，每次会移动到离自己距离第 \(k\) 远的位置上。\(m\) 次操作后，求原序列各点的现坐标。

\(nxt_i\) 表示距第 \(i\) 个点第 \(k\) 小的位置。该过程用单调队列维护，即让 \(head\) 和 \(tail\) 相差 \(k\)。（因为序列升序）

然后用倍增重复操作。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1000010;
int n, k;
ll m;
ll a[N];
int nex[N], tmp[N], ans[N];
int main()
{
	scanf("%d%d%lld", &n, &k, &m);
	for(int i = 1; i <= n; i ++ ) scanf("%lld", &a[i]);
	nex[1] = k + 1;
	int head = 1, tail = k + 1;
	
	for(int i = 2; i <= n; i ++ )
	{
		while(tail + 1 <= n && a[i] - a[head] > a[tail + 1] - a[i]) head ++, tail ++;
		if(a[i] - a[head] >= a[tail] - a[i]) nex[i] = head;
		else nex[i] = tail;
	}
	
	for(int i = 1; i <= n; i ++ ) ans[i] = i;
	
	while(m)
	{
		if(m & 1) for(int i = 1; i <= n; i ++ ) ans[i] = nex[ans[i]];	
		memcpy(tmp, nex, sizeof(tmp));
		for(int i = 1; i <= n; i ++ ) nex[i] = tmp[tmp[i]];
		m >>= 1;
	}
	
	for(int i = 1; i <= n; i ++ ) printf("%d ", ans[i]);
	return 0;
}

syoj 878. 巡逻

P4155 [SCOI2015] 国旗计划

鸽。

syoj 807. 蚂蚁爬树

P1967 [NOIP2013 提高组] 货车运输

鸽。

CF1175E Minimal Segment Cover

鸽。