link

C-Linear Approximation

给出\(N\)个数\(A_1,A_2,...,A_N\) ，求一个数\(d\)，最小化\(\sum_{i=1}^N|A_i-(d+i)|\)

把\(A_i-i\)排个序，选取\(d=\)它们的中位数

#include<bits/stdc++.h>

#define ll long long

#define dbg1(x) cerr<<#x<<"="<<(x)<<" "

#define dbg2(x) cerr<<#x<<"="<<(x)<<"\n"

#define dbg3(x) cerr<<#x<<"\n"

using namespace std;

#define reg register

inline int read()

{

	int x=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

	return x*f;

}

int a[200005];

ll ans;

int main()

{

	int N=read();

	reg int i;

	for(i=1;i<=N;++i) a[i]=read()-i;

	std::sort(a+1,a+N+1);

	int mid=(N+1)/2;

	for(i=1;i<=N;++i) ans+=abs(a[i]-a[mid]);

	return 0*printf("%lld\n",ans);

}

D-Equal Cut

将数列分成\(4\)段，最小化“最大段的和-最小段的和”的绝对值

枚举第二个断点，然后第一个和第三个显然要满足两边的段和的差值最小

可以二分，但是发现选择的位置是单调的，可以\(O(N)\)完成

#include<bits/stdc++.h>

#define ll long long

#define dbg1(x) cerr<<#x<<"="<<(x)<<" "

#define dbg2(x) cerr<<#x<<"="<<(x)<<"\n"

#define dbg3(x) cerr<<#x<<"\n"

using namespace std;

#define reg register

inline ll read()

{

	ll x=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

	return x*f;

}

const int MN=2e5+5;

ll a[MN],N,t1,t2,t3,ans;

ll cal(ll x,ll y,ll z)

{

	ll _1=a[x],_2=a[y]-a[x],_3=a[z]-a[y],_4=a[N]-a[z];

	return abs(max(max(_1,_2),max(_3,_4))-min(min(_1,_2),min(_3,_4)));

}

int main()

{

	N=read();

	reg int i;

	for(i=1;i<=N;++i) a[i]=read()+a[i-1];

	t1=1;t2=2;t3=3;ans=cal(1,2,3);

	for(;t2<=N-2;++t2)

	{

		while(t1+1<t2&&abs(a[t2]-2*a[t1+1])<abs(a[t2]-2*a[t1]))++t1;

		while(t3+1<N&&abs(a[N]-2*a[t3+1]+a[t2])<abs(a[N]-2*a[t3]+a[t2]))++t3;

		ans=min(ans,cal(t1,t2,t3));

	}

	return 0*printf("%lld\n",ans);

}

E-Or Plus Max

给出\(2^N\)个数\(a_0,a_1,...a_{2^N-1}\)，对于\(k=1,2,...,2^N-1\)

求出\(Max(a_i+a_j)\)，其中\(0\le i<j\leq 2^N-1,i \ or \ j\leq k\)

用求子集和的方法（恰好能保证每个子集只出现了一次）求出子集内的最大和次大值

最后取当前缀最大值为当前集合的答案

/*8.20*/

#include<bits/stdc++.h>

#define ll long long

#define dbg1(x) cerr<<#x<<"="<<(x)<<" "

#define dbg2(x) cerr<<#x<<"="<<(x)<<"\n"

#define dbg3(x) cerr<<#x<<"\n"

using namespace std;

#define reg register

#define P pair<int,int>

#define mp make_pair

#define fi first

#define se second

inline int read()

{

	int x=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

	return x*f;

}

const int MN=262200;

int N,S,ans;

P a[MN];

P Merge(P a,P b){if(a.fi<b.fi)swap(a,b);return mp(a.fi,max(a.se,b.fi));}

int main()

{

	N=read();S=1<<N;

	reg int i,j;

	for(i=0;i<S;++i)a[i]=mp(read(),0);

	for(j=0;j<N;++j)for(i=0;i<S;++i)if(i>>j&1)

		a[i]=Merge(a[i],a[i^(1<<j)]);

	for(i=1;i<S;++i)ans=max(ans,a[i].fi+a[i].se),printf("%d\n",ans);

	return 0;

	return 0;

}

F-Colorful Sequences

题意：定义一个长度为\(N\)，字符集大小为\(K\)的序列是好的，当且仅当其中存在一个长度为\(K\)的子串满足\(1\)到\(K\)每个数恰好出现一次。给一个长度为\(M\)的序列\(A\)，问在所有长度为\(N\)的好的序列里，\(A\)作为子串的出现次数的和。

序列\(A\)在所有序列中的出现次数是\((N-M+1)K^{N-M}\)

现在只要减去\(A\)在不好的序列中的出现次数就行了

\(A\)本身就是好的，那么不存在\(A\)在不好的序列中出现的情况
好的序列的好的子段可以利用\(A\)中全部的数（换言之：\(A\)中出现的数各不相同）

长度为\(M\)的出现的数均不相同的序列一共为\(A_K^M=\frac{K!}{(K-M)!}\)，它们均等价

所以可以先求出所有上述序列的出现次数之和

问题变为：求出所有长度为\(N\)的不好序列中长度为\(M\)的“出现的数各不相同”的子串的总数量

这可以\(DP\)。

\(f_{i,j}\)表示所有长度为\(i\)的序列中，满足末尾最长长度为\(j\)的子串中元素各不相同的方案数

\(g_{i,j}\)表示\(f_{i,j}\)所表示的序列中，无重\(M\)长的子串一共又多少个

\[f_{i,j}=(K-j+1)f_{i-1,j-1}+\sum_{h=j}^{K-1}f_{i-1,h}
\\
g_{i,j}=(K-j+1)g_{i-1,j-1}+\sum_{h=j}^{K-1}g_{i-1,h}+[j\geq M]f_{i,j}
\]

需要前缀和优化，复杂度\(O(N\times K)\)
好的序列的好的子段只能\(A\)的前缀/后缀的部分（换言之：\(A\)中存在相同的数）

分别对最长无重复前缀和最长无重复后缀进行\(Dp\)

然后枚举\(A\)串出现的位置进行计数

#include<bits/stdc++.h>

#define ll long long

#define dbg1(x) cerr<<#x<<"="<<(x)<<" "

#define dbg2(x) cerr<<#x<<"="<<(x)<<"\n"

#define dbg3(x) cerr<<#x<<"\n"

using namespace std;

#define reg register

inline int read()

{

	int x=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

	return x*f;

}

const int MN=25005,MK=405,P=1e9+7;

int Mul(int x,int y){return 1ll*x*y%P;}

int Add(int x,int y){return (x+y)%P;}

int fp(int x,int y){int r=1;for(;y;y>>=1,x=Mul(x,x))if(y&1)r=Mul(r,x);return r;}

int N,K,M,ans,a[MN],fac[MN],inv[MN],fi[MN];

int sf[MN][MK],f[MN][MK],sg[MN][MK],g[MN][MK];

bool chk1()

{

	static int ton[MK],num;

	reg int i;

	if(M<=K)return false;

	num=0;

	for(i=1;i<=K;++i)num+=!ton[a[i]]++;

	if(num==K) return true;

	for(i=K+1;i<=M;++i)

	{

		num-=!--ton[a[i-K]];

		num+=!ton[a[i]]++;

		if(num==K) return true;

	}

	return false;

}

int chk2()

{

	static int ton[MK],num;

	memset(ton,0,sizeof ton);

	reg int i;num=0;

	for(i=1;!ton[a[i]]&&i<=M;++i)num+=!ton[a[i]]++;

	return num;

}

int main()

{

	N=read(),K=read(),M=read();

	reg int i,j,Z=max(N,K);

	for(fac[0]=i=1;i<=Z;++i)fac[i]=Mul(fac[i-1],i);

	for(inv[0]=inv[1]=1,i=2;i<=Z;++i)inv[i]=Mul(inv[P%i],(P-P/i));

	for(fi[0]=i=1;i<=Z;++i)fi[i]=Mul(fi[i-1],inv[i]);

	for(i=1;i<=M;++i) a[i]=read();

	ans=Mul(N-M+1,fp(K,N-M));

	if(chk1()){return 0*printf("%d\n",ans);}

	f[0][0]=1;

	for(i=1;i<=N;++i)for(j=1;j<K;++j)

	{

		f[i][j]=Add(Mul(f[i-1][j-1],K-j+1),Add(sf[i-1][K-1],P-sf[i-1][j-1]));

		g[i][j]=Add(Mul(g[i-1][j-1],K-j+1),Add(sg[i-1][K-1],P-sg[i-1][j-1]));

		if(j>=M)g[i][j]=Add(g[i][j],f[i][j]);

		sf[i][j]=Add(sf[i][j-1],f[i][j]);

		sg[i][j]=Add(sg[i][j-1],g[i][j]);

	}

	if(chk2()==M)

	{

		int tmp=Mul(sg[N][K-1],Mul(fac[K-M],fi[K]));

		ans=Add(ans,P-tmp);

		printf("%d\n",ans);

		return 0;

	}

	else

	{

		int tmp=0,Mi,Ma,lm=chk2(),rm;

		reverse(a+1,a+M+1);rm=chk2();

		for(i=1;i<=N-M+1;++i)

		{

			int ii=i+lm-1,jj=N-i-M+1+rm,_1=0,_2=0;bool fl=ii==lm;

			for(j=lm;j<K;++j) _1=Add(_1,Mul(Mul(f[ii][j],Mul(fac[K-j],fi[K])),Mul(fac[K-lm],fi[K-j])));

			for(j=rm;j<K;++j) _2=Add(_2,Mul(Mul(f[jj][j],Mul(fac[K-j],fi[K])),Mul(fac[K-rm],fi[K-j])));

			tmp=Add(tmp,Mul(_1,_2));

		}

		ans=Add(ans,P-tmp);

		printf("%d\n",ans);

		return 0;

	}

}

Blog来自PaperCloud，未经允许，请勿转载，TKS！

巴特西

【AtCoder】 ARC 100

link

C-Linear Approximation

D-Equal Cut

E-Or Plus Max

F-Colorful Sequences

最新文章

热门文章