51nod 1421 最大取模值 奇怪的数学方法

2019-04-13 17:13发布

站内文章 / 模拟电子
14444 0 1503
这题确实经典.我旁边的一些神仙都用奇怪的方法A掉了,而我只能选择了贺题.
题目描述
给出一个数组a,求当a[i]>=a[j]时a[i]%a[j]最大的值.n<=10^5,a[i]<=10^6.
瞎搞过程
首先想到的当然是n2" role="presentation" style="position: relative;">n2的暴力.把暴力打上去有40" role="presentation" style="position: relative;">40分.
然后我们考虑一下,对于a[i]" role="presentation" style="position: relative;">a[i]最大的取模结果必然是小于a[i]" role="presentation" style="position: relative;">a[i]的.
我们从大到小枚举被取模数,当a[i]≤ans" role="presentation" style="position: relative;">a[i]≤ans直接跳出循环. #include /*省略快读快写*/ }using namespace chtholly; using namespace std; const int yuzu=2e5; int a[yuzu|10]; int main(){ int i,j,n=read(),llx=0; for (i=1;i<=n;++i) a[i]=read(); sort(a+1,a+n+1); for (i=n;i&&a[i]>llx;--i){ for (j=i+1;j<=n;++j){ llx=max(llx,a[j]%a[i]); } }write(llx); } 这样从40分变成60分.加了卡常头文件之后分数并没有变化.
那么只能考虑打复杂度正确的算法了.
一开始我想二分,但是挂了,后来我发现答案并没有可二分性.
好吧,我放弃了.
那么接下来我们看一个标算. /* 我们来看,对于某个被取模数x来讲,能够得到的最大的模数是小于x的某一个倍数的最大的那个数取模x的值. 可以看到数组是可以排序,去重的. 那么我们可以处理出一个2*数据范围的数组d,d[i]表示a数组中小于i的最大数字. 那么对于每一个去重后的a[i],我们都可以枚举它的每一个倍数a[i]*j,用d[a[i]*j]去模a[i],取最大值即可. */ #include /*快读快写省略*/ }using namespace chtholly; using namespace std; const int yuzu=2e5,mulu=2e6; int a[yuzu|10],d[mulu|10],n; map<int,int> mp; int main(){ int i,j,k=read(),llx=0; for (int x;k--;) if (!d[x=read()]++) a[++n]=x; memset(d,0,sizeof d); sort(a+1,a+n+1,greater<int>()); for (j=1,i=mulu;i;--i){ for (;j<=n&&a[j]>=i;) ++j; d[i]=a[j]; } for (i=1;i<=n;++i){ for (j=2;j*a[i]<=mulu;++j){ llx=max(llx,d[a[i]*j]%a[i]); } }write(llx); } 接下来是神犇styx的二分算法.我没看懂.
可惜这个代码无论如何总有这么一两个点tle" role="presentation" style="position: relative;">tle,我们都没救过来. #include #include #include #include using namespace std; int vis[4000010],sum[4000010],k,n,a[200010],cnt; int check(int x) { for(register int i=1;i<=cnt;++i) { for(register int j=a[i];j<=1e6;j+=a[i]) { if(sum[j+a[i]-1]-sum[j+x-1]>0) { return 1; } } } return 0; } int main() { scanf("%d",&n); int tmp; for(register int i=1;i<=n;++i) { scanf("%d",&tmp); if(!vis[tmp]) { vis[tmp]=1; } } for(register int i=1;i<=2e6;++i) { sum[i]=sum[i-1]+vis[i]; } for(int i=1;i<=1e6;i++) { if(vis[i]) { a[++cnt]=i; } } register int l=0,r=2e6,mid; while(lint mid=(l+r)>>1; if(check(mid)) { l=mid; } else { r=mid-1; } if(r-l<=1) { r=check(r)?r:l; break; } } printf("%d ",r); } 然后是神仙yzy的set瞎搞算法.反正我还是不懂. #include #include #include #include #define P pair #define mp make_pair #define fi first #define se second #define N 200100 using namespace std; int n,num[N],t,ans; P tmp; set

se; int main() { int i,j; cin>>n; for(i=1; i<=n; i++) { scanf("%d",&num[i]); } sort(num+1,num+n+1); se.insert(mp(num[2]/num[1]*num[1],num[1])); for(i=2; i<=n; i++) { for(;;) { tmp=(*se.begin()); if(num[i]/tmp.se != tmp.fi/tmp.se) { se.erase(tmp); se.insert(mp(num[i]/tmp.se*tmp.se,tmp.se)); } else { ans=max(ans,num[i]%tmp.se); break; } } se.insert(mp(num[i+1]/num[i]*num[i],num[i])); } cout< 好,谢谢大家.

热门文章