Educational Codeforces Round 173 (Rated for Div. 2) - Codeforces

Educational Codeforces Round 173 (Rated for Div. 2) - Codeforces

Problem - A - Codeforces

签到题目

Problem - B - Codeforces

数学

被小学奥数薄纱力…

给出一个由$n!$个$d$组成的整数，看他能否被十以内的奇数整除

$1$肯定是答案

一个数能被$3$整除，那么它的数位之和为一定可以被$3$整除,简单证明一下，设一个$k$位数，每个位数为$x_i$
$$\begin{gathered} n=x_k\ast 10^k+x_{k-1}\ast 10^{k-1}+...x2\ast 10+x_1 \\ (x_k+x_{k-1}+..x_2+x_1)\mathrm{mod}3=0 \\ n\mathrm{mod}3=\sum _{i=1}^k((x_i\mathrm{mod}3)\ast (10^i\mathrm{mod}3))=\sum _{i=1}^k(x_i\mathrm{mod}3)=0 \end{gathered}$$
同理可以得出，一个数能被$9$整除，那么它的数位之和一定能被$9$整除

一个数能被$5$整除，它的末尾一定是$0$或$5$

最后是$7$有点麻烦，得找找规律，发现题中$n=\mathrm{111..111}\ast d$,由$1$构成的$n$中最小的能被$7$整除的为$111111$

所以只要$n!\mathrm{mod}6==0$即$n>=3$，$n$一定可以表示为$111111\ast a+111111\ast b+...$

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
map<int,int>mp;
int n;int a[N];
int l[N],r[N];
long long gcd(long long a,long long b)
{
	return b? gcd(b,a%b):a;
}
void solve()
{
	int n,d;cin>>n>>d;
	cout<<"1 ";
	if(n>=3||d%3==0)cout<<"3 ";
	if(d==5)cout<<"5 ";
	if(n>=3||d==7)cout<<"7 ";
	if(n>=6||(n>=3&&d%3==0)||d==9)cout<<"9 ";
	cout<<endl;
}
int main()
{
	int t;cin>>t;
	while(t--)solve();
}

Problem - C - Codeforces

dp 数学

给出一个整数数组，数组最多有一个数$x$不是$-1,1$

问数组的一个连续段的和最多有几种不同结果，考虑空段

观察题目显然想到要把数组分为$x$左边和$x$右边，独立来看

对于一个只有$-1,1$的序列，假设它的连续段和最大为$x$，最小为$y$，可以证明它的连续段和肯定可以取满$[y,x]$内的值

证明：对于最大值$x$，由于它是由一个连续段相加得来，那么肯定可以将这个连续段分为若干个和为$1$的更小的段，从两端开始移去子段，得到的连续段和为$x-1,x-\mathrm{2...0}$，所以肯定可以取满$[0,x]$，同理可得取满$[y,0]$

对于求最大最小值就是简单的$dp$问题了

设已经求出的左边范围是$[a,b]$，右边为$[c,d]$，(由于肯定包含$0$，两者肯定有交集)将其合并为$[x,y]$,那么答案至少是$y-x+1$

再考虑$x$，设它的坐标是$ind$，只用求出$[ind+1,n]$的前缀和与$[1,ind-1]$的后缀和，将他们的范围（最大值大于等于$0$,最小值小于等于$0$）相加得到$[x_1,y_1]$

遍历这个区间加上$x$看看有没有新的值加入即可

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
map<int,int>mp;
int n;int a[N];
int l[N],r[N];
void solve()
{
	mp.clear();int ind=-1;int ans=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		l[i]=r[i]=0;
		scanf("%d",&a[i]);
		if(a[i]<-1||a[i]>1||a[i]==0)ind=i;
	}
	int aa=0,b=0,c=0,d=0;
	if(ind==-1)ind=n+1;
	for(int i=1;i<ind;i++)
	{
		l[i]=max(a[i],l[i-1]+a[i]);
		r[i]=min(a[i],r[i-1]+a[i]);
		aa=max(aa,l[i]);
		b=min(b,r[i]);
	}
	for(int i=ind+1;i<=n;i++)
	{
		l[i]=max(a[i],l[i-1]+a[i]);
		r[i]=min(a[i],r[i-1]+a[i]);
		c=max(c,l[i]);
		d=min(d,r[i]);
	}
	b=min(b,d);aa=max(aa,c);ans=aa-b+1;
	for(int i=b;i<=aa;i++)mp[i]++;
	if(ind!=n+1)
	{
		if(!mp[a[ind]])
		{
			mp[a[ind]]++;
			ans++;
		}
		int sum=0;
		int x1=0,x2=0,y1=0,y2=0;
		for(int i=ind+1;i<=n;i++)
		{
			sum+=a[i];x1=min(x1,sum);x2=max(x2,sum);
		}
		sum=0;
		for(int i=ind-1;i;i--)
		{
			sum+=a[i];y1=min(y1,sum);y2=max(y2,sum);
		}
		int ll=x1+y1,rr=x2+y2;
		for(int i=ll;i<=rr;i++)
		{
			if(!mp[a[ind]+i])
			{
				mp[a[ind]+i]++;ans++;
			}
		}
	}
	cout<<ans<<endl;
	for(auto x:mp)
	{
		cout<<x.first<<' ';
	}
	cout<<endl;
}
int main()
{
	int t;cin>>t;
	while(t--)solve();
}

Problem - D - Codeforces

质数 数学

给出$l,r,g$，求$l\le a\le b\le r,gcd(a,b)=g$的，满足$|a-b|$最大的$a,b$

模板题，需要一个转化，对于$x=g\ast a,y=g\ast b$,如果$gcd(x,y)=g$，那么一定有$gcd(a,b)=1$

那么题目就转化为了找到$[(l+g-1)/g,r/g]$之间的最大互质对

要根据质数的性质，在题目给的$10^{18}$的范围下，相邻质数的距离最大不会超过$1500$

其实，设$g_n$为在小于等于$n$的范围内相邻质数的最大距离，$g_{10^{18}}=1442$

考虑$l$的下一个质数为$q$,考虑$r$的上一个质数为$p$,两个不相等的质数一定互质，所以答案最坏也要是$(q,p)$

在最差的情况下要遍历$g_n^2\ast lg(r)$，时间是足够的

从大到小枚举长度即可，看似时间复杂度是$n^2$,，其实很快就可以在两端找到答案

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
map<int,int>mp;
int n;int a[N];
int l[N],r[N];
long long gcd(long long a,long long b)
{
	return b? gcd(b,a%b):a;
}
void solve()
{
	long long x,y,g;cin>>x>>y>>g;
	long long l=(x+g-1)/g,r=y/g;
	for(long long len=r-l;len>=0;len--)
	{
		for(long long i=l;i+len<=r;i++)
		{
			if(gcd(i,i+len)==1)
			{
				cout<<g*i<<' '<<g*(i+len)<<endl;return ;
			}
		}
	}
	cout<<"-1 -1"<<endl;
}
int main()
{
	int t;cin>>t;
	while(t--)solve();
}

可以得到求$[l,r]$内的最大互质对的模板

void getprime(long long a, long long b)
{
    for(long long len=r-l;len>=0;len--)
	{
		for(long long i=l;i+len<=r;i++)
		{
			if(gcd(i,i+len)==1)
			{
				cout<<i<<' '<<i+len<<endl;return ;
			}
		}
	}
}