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();
}