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