Educational Codeforces Round 173 (Rated for Div. 2)

A 略

B

将ddd...d拆成111...1*d。能整除有两种情况，第一种d能整除1 3 5 7 9。第二种用111..11除以1 3 5 7 9发现k位能除尽，则阶乘n中包含因数k就成立。需要注意的一个点是有可能时d中的一个因数乘n的阶乘的因数能整除1 3 5 7 9

C

将这个数组段分成三部分，即仅包含特殊的数左，右，和包含特殊的数。前两部分的最大知道最小值中每个数都能取到，取并集。再将这个集合的左右边界和第三部分的左右边界比大小输出。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int T,n,a[N],pos,lmin,lmax,rmin,rmax,s,llmin,llmax,rrmin,rrmax,minn,maxx;
void init()
{
	pos=-1;
}
void solve()
{
	cin>>n;
	init();
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		if(a[i]!=1&&a[i]!=-1) pos=i;
	}
	if(pos==-1)
	{
		minn=maxx=0;s=0;
		for(int i=1;i<=n;i++)
		{
			s+=a[i];
			if(s<0) s=0;
			maxx=max(maxx,s);
		}
		s=0;
		for(int i=1;i<=n;i++)
		{
			s+=a[i];
			if(s>0) s=0;
			minn=min(minn,s);
		}
		cout<<maxx-minn+1<<endl;
		for(int i=minn;i<=maxx;i++)
		cout<<i<<" ";
		cout<<endl;
		return ;
	}
	if(pos==1)
	{
		lmin=lmax=0;
	}
	else
	{
		s=0;lmin=lmax=0;
        for(int i=1;i<=pos-1;i++)
		{
			s+=a[i];
			if(s<0) s=0;
			lmax=max(lmax,s);
		}
		s=0;
		for(int i=1;i<=pos-1;i++)
		{
			s+=a[i];
			if(s>0) s=0;
			lmin=min(lmin,s);
		}
	}
	if(pos==n)
	{
		rmin=rmax=0;
	}
	else
	{
		s=0;rmin=rmax=0;
        for(int i=pos+1;i<=n;i++)
		{
			s+=a[i];
			if(s<0) s=0;
			rmax=max(rmax,s);
		}
		s=0;
		for(int i=pos+1;i<=n;i++)
		{
			s+=a[i];
			if(s>0) s=0;
			rmin=min(rmin,s);
		}
	}
	lmin=min(lmin,rmin);
	lmax=max(lmax,rmax);
	if(pos==1) llmin=llmax=0;
	else
	{
		s=0;llmin=llmax=0;
		for(int i=pos-1;i>=1;i--)
		{
			s+=a[i];
			llmax=max(llmax,s);
			llmin=min(llmin,s);
		}
	}
	if(pos==n) rrmin=rrmax=0;
	else
	{
		s=0;rrmin=rrmax=0;
		for(int i=pos+1;i<=n;i++)
		{
			s+=a[i];
			rrmax=max(rrmax,s);
			rrmin=min(rrmin,s);
		}
	}
	llmin=llmin+rrmin+a[pos];
	llmax=llmax+rrmax+a[pos];
	if(llmax<lmin)
	{
		cout<<llmax-llmin+1+lmax-lmin+1<<endl;
		for(int i=llmin;i<=llmax;i++)
		cout<<i<<" ";
		for(int i=lmin;i<=lmax;i++)
		cout<<i<<" ";
		cout<<endl;
	}
	if(llmax>=lmin&&llmax<=lmax)
	{
		cout<<max(lmax,llmax)-min(lmin,llmin)+1<<endl;
		for(int i=min(lmin,llmin);i<=max(lmax,llmax);i++)
		cout<<i<<" ";
		cout<<endl;
	}
	if(llmax>lmax&&llmin<=lmax)
	{
		cout<<max(lmax,llmax)-min(lmin,llmin)+1<<endl;
		for(int i=min(lmin,llmin);i<=max(lmax,llmax);i++)
		cout<<i<<" ";
		cout<<endl;
	}
	if(llmin>lmax)
	{
		cout<<llmax-llmin+1+lmax-lmin+1<<endl;
		for(int i=lmin;i<=lmax;i++)
		cout<<i<<" ";
		for(int i=llmin;i<=llmax;i++)
		cout<<i<<" ";
		cout<<endl;
	}
}
signed main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--) solve();
}