Tenka1 Programmer Contest 2019

时间：2023-12-05 23:39:32

　　C：即要使前一部分为白色后一部分为黑色，枚举分割点前缀和计算答案取min即可。

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define N 200010

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

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

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

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

int n,a[N],s[N][2],ans=N;

char S[N];

signed main()

{

	n=read();

	scanf("%s",S+1);

	for (int i=1;i<=n;i++) if (S[i]=='#') a[i]=1;else a[i]=0;

	for (int i=1;i<=n;i++)

	{

		s[i][0]=s[i-1][0],s[i][1]=s[i-1][1];

		if (a[i]==1) s[i][1]++;else s[i][0]++;

	}

	for (int i=0;i<=n;i++) ans=min(ans,s[i][1]+s[n][0]-s[i][0]);

	cout<<ans;

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　D：即要求最大的一组和小于总和一半的方案数。容易想到设f[i][j]为前i个数最大一组（不是当前最大的一组，而是我们期望所有数分配完之后其成为最大的一组）和为j时的方案数。为保证第二维中的是最大的一组，做一个补集转化。dp时如果不将该数放进最大的一组就将方案数*2，因为剩下两组可以任选。最后有一个小问题就是如果总和是偶数，分成两组且每组恰好分得一半的方案数会被重复扣减，重新背包一下加回来即可。

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define N 310

#define P 998244353

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

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

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

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

int n,m,s,a[N],f[N*N],g[N*N];

signed main()

{

	n=read();

	for (int i=1;i<=n;i++) m+=a[i]=read();

	s=(m-1)/2;

	f[0]=1;

	for (int i=1;i<=n;i++)

	{

		for (int j=m;j>=a[i];j--)

		f[j]=(2ll*f[j]+f[j-a[i]])%P;

		for (int j=a[i]-1;j>=0;j--) f[j]=2ll*f[j]%P;

	}

	int ans=1;for (int i=1;i<=n;i++) ans=3ll*ans%P;

	for (int i=s+1;i<=m;i++) ans=(ans-3ll*f[i]%P+P)%P;

	if (m%2==0)

	{

		g[0]=1;

		for (int i=1;i<=n;i++)

		{

			for (int j=m;j>=a[i];j--)

			g[j]=(g[j]+g[j-a[i]])%P;

		}

		ans=(ans+3ll*g[m/2]%P+P)%P;

	}

	cout<<ans;

	return 0;

	//NOTICE LONG LONG!!!!!

}

//2max(a,b,c)<a+b+c

　　E、F：准备打猝死场，咕着先睡了。（woc闹钟没听见睡过了自闭了

　　E：完全无法理解为啥枚举a0的每个质因子p暴力将x=0~p-1代入都会wa。

　　F：小清新水题。首先枚举一下0的个数转化成只有1和2的情况。考虑找到第一个前缀和>x的位置i，这样区间[1,i]的和是x+1。容易发现此时1和i位置都必须是2，否则将区间缩小一点和就变为x。然后考虑第i+1位，可以发现也只能是2，否则区间[2,i+1]不合法。以此类推，[i,n]和[1,n-i+1]都必须是2。枚举i算算组合数即可。

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define N 3010

#define P 998244353

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

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

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

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

int n,m,C[N<<1][N<<1],ans;

void inc(int &x,int y){x+=y;if (x>=P) x-=P;}

signed main()

{

	freopen("b.in","r",stdin);

	freopen("b.out","w",stdout);

	n=read(),m=read();

	C[0][0]=1;

	for (int i=1;i<=max(n,m);i++)

	{

		C[i][0]=1;

		for (int j=1;j<=i;j++)

		C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;

	}

	for (int i=0;i<=n;i++)

	{

		int s=0;

		for (int j=0;j<=m-1-i;j++) inc(s,C[i][j]);

		for (int j=1;j<=i;j++) //j是第一个前缀和>m的位置 j~i均为2 1~i-j+1均为2

		if (j*2>m&&(i-j+1<j?(i-j+1)*2+(j-(i-j+1)+1):j*2)<=m+1)

			if (i-j+1<j) inc(s,C[j-(i-j+1)-1][m+1-((i-j+1)*2+(j-(i-j+1)+1))]);

			else if (j*2==m+1) inc(s,1);

		inc(ans,1ll*s*C[n][n-i]%P);

	}

	cout<<ans;

	return 0;

	//NOTICE LONG LONG!!!!!

}

//先把0去掉 则要考虑求长度为0~n的满足条件的序列数量

//找到第一个前缀和>x的位置 然后若当前不是后缀 下一位必须是2 首位也必须是2

//即第一个前缀和>x的位置及之后全都是2

　　result：rank 119 rating +42

相关文章