牛客暑期多校訓練營2020第3場

E Two Matchings

題意：

  給一個數組a，求排列p、q，滿足pi != qi。ppi=i，qqi=i。(n為偶數) 求 1 2 \frac{1}{2} 21​ ∑ i = 1 n \sum_{i=1}^{n} ∑i=1n​aI-api與 1 2 \frac{1}{2} 21​ ∑ i = 1 n \sum_{i=1}^{n} ∑i=1n​aI-aqi的和的最小值。

思路：

  pi != qi即是p中均為二進制環。

  n=4時，最小值為max-min；

  n=6時，最小值為max-min；

  n ≥ \ge ≥ 8時，整塊不會比切成4、6小塊考慮更優。

  然後動态規劃就可以了。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define LL long long
using namespace std;
const int N=2e5+10;
const LL inf=1e16;
LL a[N],f[N];
int cmp(LL a,LL b){return a>b;}
int main()
{
	int T,n;
	scanf("%d",&T);
	while(T)
	{
		T--;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)	scanf("%lld",&a[i]);
		sort(a+1,a+n+1,cmp);
		f[4]=a[1]-a[4];
		f[6]=a[1]-a[6];
		for(int i=8;i<=n;i+=2)
		{
			f[i]=f[i-4]+a[i-4+1]-a[i];
			if(i-6>=4)	f[i]=min(f[i],f[i-6]+a[i-6+1]-a[i]);
		}
		printf("%lld\n",f[n]*2);
	}
	return 0;
 } 
           

H Sort the Strings Revision

題意：

  給一個串s，一個排列p，一個數組d。第i次操作為：将si-1的第pi位換成di，求s0、s1、……sn的排名。

思路：

  對于原串的第i位，假設它是在第k次操作中被改變的，如果：

1. d[k] > s[i] ，那麼sk，……sn排在s0……sk-1後面
2. d[k] < s[i] ，那麼sk，……sn排在s0……sk-1前面
3. d[k] > s[i] ，那就當什麼都沒發生過

  是以我們可以從第一位開始考慮，看它是在什麼時候被改變的就可以了。但是，我們如何處理才能做到O(n)呢？按照笛卡爾樹dfs序！

笛卡爾樹

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define LL long long
#define int long long
using namespace std;
const int N = 2e6+10;
const LL base = 10000019;
const LL md = 1000000007;
LL p[N], d[N], c[N], ha[N];
int t[N], stk[N], l[N], r[N];
int num;
void init(int n)
{
	LL pseed, pa, pb, pmod;
	scanf("%lld%lld%lld%lld",&pseed,&pa,&pb,&pmod);
	for(int i = 0; i < n; i++)	p[i] = i;
	for(int i = 1; i < n; i++)
	{
		swap(p[pseed % (i + 1)], p[i]);
		pseed = (pseed * pa + pb) % pmod;
	}
	LL dseed, da, db, dmod;
	scanf("%lld%lld%lld%lld", &dseed, &da, &db, &dmod);
	for(int i = 0; i < n; i++)
	{
		d[i] = dseed % 10;
		dseed = (dseed * da + db) % dmod;
	}
}
void dfs(int x, int ll, int rr)
{
	if(ll>rr)	return;
	if(x==-1)
	{
		for(int i = ll; i <= rr; i++)	c[i] = num++;
		return;
	}
	if(d[x] > p[x] % 10)
	{
		dfs(l[x], ll, x);
		dfs(r[x], x+1, rr);
	} 
	else
	{
		dfs(r[x], x+1, rr);
		dfs(l[x], ll, x); 
	}
}
void solve(int n)
{
	int cnt=0, rt;
	for(int i = 0; i <= n; i++)	c[i] = 0;
	for(int i = 0; i < n; i++)
		if(d[i] != p[i] % 10)
			t[++cnt] = i;
	if(!cnt)	rt=-1;
	else
	{
		rt = t[1];
		stk[1] = t[1];
		int top = 1;
		l[t[1]] = r[t[1]] = -1;
		for(int i = 2; i <= cnt; i++)
		{
			l[t[i]] = r[t[i]] = -1;
			while(top && p[stk[top]] > p[t[i]])
			{
				l[t[i]] = stk[top];
				top--;
			} 
			if(top) r[stk[top]] = t[i];
			else rt = t[i];
			stk[++top] = t[i];
		}
	}
	num=0;
	dfs(rt, 0, n);
}
void print(int n)
{
	LL ans=0;
	for(int i = 0; i <= n; i++)	ans = (ans + c[i] * ha[i] % md) % md; 
	printf("%lld\n", ans);
}
signed main()
{
	int T, n;
	ha[0] = 1;
	for(int i = 1; i <= 2e6; i++)	ha[i] = ha[i-1] * base % md;
	scanf("%lld",&T);
	while(T)
	{
		T--;
		scanf("%lld",&n);
		init(n);
		solve(n);
		print(n);
	}
	return 0;
 }