2022牛客寒假算法基础集训营1

赛场上完成度：11/12

rank：33

https://ac.nowcoder.com/acm/contest/23106/A

和的数根=数根的和，因此每个人的权值等价于权值的数根。

设f[i][j]表示前i个人凑出j的方案数，直接根据意义转移即可。

代码：

#include
using namespace std;
const int mo=998244353;
int a[1000010],b[1000010],s[1000010];
int cal(int x)
{
	while (x>=10)
	{
		int y=x,z=0;
		while (y)
		{
			z=z+y%10;
			y=y/10;
		}
		x=z;
	}
	return x;
}
int main()
{
	int n;
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		a[i]=cal(x);
	}
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=9;j++) b[j]=0;
		b[a[i]]++;
		for (int j=1;j<=9;j++) b[cal(a[i]+j)]=(b[cal(a[i]+j)]+s[j])%mo;
		for (int j=1;j<=9;j++) s[j]=(s[j]+b[j])%mo;
	}
	for (int i=1;i<=9;i++) printf("%d ",s[i]);
}

https://ac.nowcoder.com/acm/contest/23106/B

不难发现，对于模3相同的初始分数，在经过相同的区间之后，分数的变化量相同。

因此可以考虑分块，预处理每一块对模3为0，1，2的初始分数的影响，对于每次询问，块前后的部分暴力，对于整块直接计算对答案的影响。

总复杂度O(n+qn^0.5)

代码：

#include
using namespace std;
const int N=2e5+10;
int le[500],ri[500],g[500][5],fr[N];
int main()
{
	int n,q;
	scanf("%d%d",&n,&q);
	char s[200010];
	scanf("%s",s+1);
	int k=(int)sqrt(n);
	//printf("%d\n",k);
	int cc=n/k;
	for (int i=1;i<=cc;i++)
	{
		le[i]=(i-1)*k+1;
		ri[i]=i*k;
	}
	if (n%k) 
	{
		cc++;
		le[cc]=(cc-1)*k+1;
		ri[cc]=n;
	}
	for (int i=1;i<=cc;i++)
	{
		for (int p=0;p<=2;p++)
		{
			int x=p;
			for (int j=le[i];j<=ri[i];j++)
			{
				if (s[j]=='W') x++;
				if (s[j]=='L'&&x%3) x--;
				fr[j]=i;
			}
			g[i][p]=x-p;
		}
	}
	for (int i=1;i<=q;i++)
	{
		int l,r,x;
		scanf("%d%d%d",&l,&r,&x);
		int cl=fr[l],cr=fr[r];
		if (cl==cr)
		{
			for (int j=l;j<=r;j++)
			{
				if (s[j]=='W') x++;
				if (s[j]=='L'&&x%3) x--;
			}
			printf("%d\n",x);
			continue;
		}
		for (int j=l;j<=ri[cl];j++)
		{
			if (s[j]=='W') x++;
			if (s[j]=='L'&&x%3) x--;	
		}
		for (int j=cl+1;j



https://ac.nowcoder.com/acm/contest/23106/C
贪心地想，如果i和前面某个语句冲突，则在i前插入刚好能解决冲突的空指令。
这个贪心正确性显然。

#include
using namespace std;
int st[100000],rk[100000];;
int main()
{
	int n,tl=0,ans=0;
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		int p=-1;
		for (int j=1;j<4;j++)
		{
			int x;
			scanf("%d",&x);
			if (i-j<=0) continue;
			if (x==0) continue;
			if (p==-1) p=i-j;
		}
		if (p!=-1) 
        {
            while (tl-rk[p]<3) tl++,ans++;
        }
		st[++tl]=i;
		rk[i]=tl;
	}
	printf("%d\n",ans);
}




https://ac.nowcoder.com/acm/contest/23106/D
第一问，2*3*5*...一直到再乘超过n。
第二问，不大于n的最大质数。
证明略了，懒得打（之前打了一份，网站崩溃没保存，寄！

#include
using namespace std;
int zs[100];
int pd(int x)
{
	for (int i=2;i*i<=x;i++) if (x%i==0) return 0;
	return 1;	
}
int main()
{
	int k=0;
	for (int i=1;i<=23;i++) if (pd(i)) zs[++k]=i;
	int t;
	scanf("%d",&t);
	while (t)
	{
		t--;
		int n;
		scanf("%d",&n);
		if (n==1)
		{
			printf("-1\n");
			continue; 
		}
		int x=1,j=1;
		while (x*zs[j]<=n&&j<=k)
		{
			x=x*zs[j];
			j++;
		}
		printf("%d ",x);
		for (int i=n;i>=2;i--)
		{
			if (pd(i)) 
			{
				printf("%d\n",i);
				break;	
			}
		}
		//if (n==2) printf("%d\n",n);
	}
}




https://ac.nowcoder.com/acm/contest/23106/E
纯纯的签到，特判一下边界。
每次可以运出m-1个人，最后一轮最多运m个人。

#include
using namespace std;
int main()
{
	int t;
	scanf("%d",&t);
	while (t)
	{
		t--;
		int x,y;
		scanf("%d%d",&x,&y);
		if (y==1)
		{
			printf("-1\n");
			continue;
		}
		if (x<=y)
		{
			printf("1\n");
			continue;	
		}
		int ans=0;
		/*int z=x/(y-1);
		x=x%(y-1);
		ans=ans+(z-1)*2;
		ans=ans+1;
		if (y==2) ans=ans-2;
		printf("%d\n",ans);*/
		x=x-y;
		ans=ans+x/(y-1)*2;
		if (x%(y-1)) ans=ans+2;
		printf("%d\n",ans+1);
	}
}




https://ac.nowcoder.com/acm/contest/23106/F
大于等于m的数记为1，其他记为0，合法情况就是1的个数>0的个数，贪心地考虑切分，如果一段可以切成两份，则两份的1都要大于各种的0的数量，因此，扫一遍，能切就切。

#include
using namespace std;
int a[1000010];
int main()
{
	int t;
	scanf("%d",&t);
	while (t)
	{
		t--;
		int n,m,s1=0;
		scanf("%d%d",&n,&m);
		for (int i=1;i<=n;i++) 
		{
			scanf("%d",&a[i]); 
			if (a[i]>=m) a[i]=1,s1++;else a[i]=0;
		}
		if (s1=q2/2+1&&((n-i)/2+1<=s1)||(n-i)==0)
			{
				ans++;
				q1=0;
				q2=0;
			}
		}
		printf("%d\n",ans);
	}
}



https://ac.nowcoder.com/acm/contest/23106/G
不会。


https://ac.nowcoder.com/acm/contest/23106/H
树状数组优化一下暴力的过程即可。

#include
using namespace std;
int a[1000010],b[1000010];
long long tr1[1000010],tr2[1000010];
void p1(int x,int y)
{
	while (x<=1001)
	{
		tr1[x]+=y;
		x=x+(x&(-x));
	}
}
void p2(int x,int y)
{
	while (x<=1001)
	{
		tr2[x]+=y;
		x=x+(x&(-x));
	}
}
long long q1(int x)
{
	long long ret=0;
	while (x)
	{
		ret+=tr1[x];
		x=x-(x&(-x));	
	}
	return ret;
}
long long q2(int x)
{
	long long ret=0;
	while (x)
	{
		ret+=tr2[x];
		x=x-(x&(-x));	
	}
	return ret;
}
int main()
{
	//freopen("test.in","r",stdin);
	int n;
	scanf("%d",&n);
	for (int i=1;i<=n;i++) 
	{
		scanf("%d",&a[i]);
		b[a[i]]++;
	}
	long long ans1=0;
	//for (int i=1;i<=n;i++) for (int j=i;j<=n;j++) ans1=ans1+abs(a[i]+a[j]-1000);
	long long ans=0,ss=0;
	for (int i=n;i>=1;i--)
	{
		p1(a[i]+1,1);
		p2(a[i]+1,a[i]);
		ss=ss+a[i];
		long long x=q1(1000-a[i]+1),y=q2(1000-a[i]+1);
		ans=ans+x*1000-x*a[i]-y-(n-i+1-x)*1000+(n-i+1-x)*a[i]+ss-y;
	}
	printf("%lld\n",ans);
	//printf("%d\n",ans1);
	//for (int i=1;i<=n;i++) printf("%d\n",a[i]);
	//printf("%lld\n",ans-ans1);
}




https://ac.nowcoder.com/acm/contest/23106/I
m句歌词和1句歌词的区别，就是答案乘m。
每个人的策略应当相同，考虑每个人的策略是一个概率p，即有p的概率唱，那么这句歌词无效的概率就是p^n+(1-p)^n，要使得这个概率最小，可得p=0.5

#include
using namespace std;
const int mo=1e9+7;
int ksm(int x,int y)
{
	int ret=1;
	while (y)
	{
		if (y&1) ret=1ll*ret*x%mo;
		x=1ll*x*x%mo;
		y=y>>1;
	}
	return ret;
}
int main()
{
	int t;
	scanf("%d",&t);
	while (t)
	{
		t--;
		int n,m;
		scanf("%d%d",&n,&m);
		if (n==1) printf("0\n");
		else 
		{
			printf("%lld\n",1ll*m*(1-2*ksm(ksm(2,mo-2),n)%mo+mo)%mo);
		}
	}
}




https://ac.nowcoder.com/acm/contest/23106/J
每次考虑加入一个小朋友，要使得当前已经加入的小朋友的集合是合法的，贪心地考虑，每次选择权值最大的小朋友，如果小朋友是安静的，那加入后不会影响合法性，如果小朋友是闹腾的，就要判断加入后是否会由合法变为不合法。
最后看看集合大小是否能过达到n

#include
using namespace std;
int a[100010],b[100010];
int main()
{
	int t;
	scanf("%d",&t);
	while (t)
	{
		t--;
		int n,m,s;
		scanf("%d%d%d",&n,&m,&s);
		for (int i=1;i<=n;i++) scanf("%d",&a[i]);
		for (int i=1;i<=m;i++) scanf("%d",&b[i]);
		sort(a+1,a+n+1);
		reverse(a+1,a+n+1);
		sort(b+1,b+m+1);
		reverse(b+1,b+m+1);
		int i=1,j=1,k=0;
		long long ans=0;
		while (1)
		{
			if (k==s) break;
			if (i<=n&&a[i]>=b[j])
			{
				k++;
				ans=ans+a[i];
				i++;
				continue;
			}
			if (j<=m&&b[j]>=a[i]&&j*2<=k+1)
			{
				k++;
				ans=ans+b[j];
				j++;
				continue;
			}
			if (i<=n)
			{
				k++;
				ans=ans+a[i];
				i++;
				continue;	
			}
			if (j*2<=k+1)
			{
				k++;
				ans=ans+b[j];
				j++;
				continue;
			}
			break;
		}
		if (s==k) printf("%lld\n",ans);else printf("-1\n");
	}
}




https://ac.nowcoder.com/acm/contest/23106/K
设f[l][i][j][k]表示，前l个岛屿，后三个岛屿依次是i，j，k，所能拥有的最多的绿岛数量。
转移，每次枚举下一个岛屿的颜色，判断新的组合是否满足S中罗盘的预测，再开一个G数组记录某种状态是否存在合法的方案，新状态只能从合法的旧状态转移过来。

#include
using namespace std;
int g[100010][4][4][4],f[100010][4][4][4];
int main()
{
	int n;
	scanf("%d",&n);
	char s[100010];
	scanf("%s",s+1);
	for (int i=1;i<=3;i++) for (int j=1;j<=3;j++) for (int k=1;k<=3;k++)
	{
		int gs=0,rs=0,bs=0;
		if (i==1) gs++;
		if (j==1) gs++;
		if (k==1) gs++;
		if (i==2) rs++;
		if (j==2) rs++;
		if (k==2) rs++;
		if (i==3) bs++;
		if (j==3) bs++;
		if (k==3) bs++;
		g[3][i][j][k]=-1;
		if (s[3]=='G'&&gs>rs)
		{
			g[3][i][j][k]=1;
			f[3][i][j][k]=gs;	
		}
		if (s[3]=='R'&&rs>gs)
		{
			g[3][i][j][k]=1;
			f[3][i][j][k]=gs;	
		}
		if (s[3]=='B'&&rs==gs)
		{
			g[3][i][j][k]=1;
			f[3][i][j][k]=gs;
		}
	}
	for (int l=3;lrs)
				{
					g[l+1][j][k][t]=1;
					f[l+1][j][k][t]=max(f[l][i][j][k],f[l+1][j][k][t]);
				}
				if (s[l+1]=='R'&&gs




https://ac.nowcoder.com/acm/contest/23106/L
模拟一下即可。

#include
using namespace std;
int main()
{
	int t;
	scanf("%d",&t);
	while (t)
	{
		t--;
		int n;
		scanf("%d",&n);
		char s[100010];
		scanf("%s",s+1);
		int x=0,y=0;
		double ans=0;
		for (int i=1;i<=n;i++)
		{
			if (s[i]=='U') y++;
			if (s[i]=='D') y--;
			if (s[i]=='R') x++;
			if (s[i]=='L') x--;
			ans=max(ans,sqrt(x*x+y*y));
		}
		printf("%.8lf\n",ans);
	}
}