蓝桥杯2018年第九届真题-倍数问题(模运算)

解题思路:
首先对输入排序，枚举两个余数，可以算出第三个余数，由于三个余数和在0到3(k-1),故合法的只为0,k,2k,算出这三个可能的情况，判断是否存在即可。
注意事项:
对n,k枚举可能超时，复杂度O(k^2)，选择一个余数时选择最大的数字，所以要先排序。
参考代码:

#include<bits/stdc++.h>

using namespace std;

#define maxx 1100

int n,ans,w;

unordered_map<int,int> M;

vector<int> allx[maxx];

int all[maxx*1000];

int pd(int i,int j,int k)

{

  if(i<0||j<0||k<0||i>=w||j>=w||k>=w) return 0;

M.clear();

++M[i];++M[j];++M[k];

if(M.size()==1)

{

  if(allx[i].size()>=3) return allx[i][0]+allx[i][1]+allx[i][2];

  else return 0;

}

else if(M.size()==2)

{

  if(i==j)

  {if(allx[i].size()>=2&&allx[k].size()>=1) return allx[i][0]+allx[i][1]+allx[k][0];

  else return 0;}

  else if(i==k)

   {if(allx[i].size()>=2&&allx[j].size()>=1) return allx[i][0]+allx[i][1]+allx[j][0];

  else return 0;}

  else

   {if(allx[j].size()>=2&&allx[i].size()>=1) return allx[j][0]+allx[j][1]+allx[i][0];

    else return 0;}

}

else

{

  if(allx[i].size()>0&&allx[j].size()>0&&allx[k].size()>0) return allx[i][0]+allx[j][0]+allx[k][0];

  return 0;

}

}

int main()

{

  cin>>n>>w;

  for(int i=1;i<=n;++i) cin>>all[i];sort(all+1,all+1+n);

  for(int i=n;i>=1;--i) allx[all[i]%w].push_back(all[i]);

  for(int i=0;i<w;++i)

   for(int j=0;j<w;++j)

   {

     int k=-(i+j);

     ans=max(ans,pd(i,j,k));

     k=w-(i+j);

     ans=max(ans,pd(i,j,k));

     k=2*w-(i+j);

     ans=max(ans,pd(i,j,k));

   }

   cout<<ans;

}