Hướng dẫn giải của Bedao Regular Contest 02 - SISTER


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: bedao

Để tránh TLE đầu tiên ta sẽ dùng sàng nguyên tố để tìm tất cả các số nguyên tố từ thuộc khoảng ~[1, 10^6]~

Vì ~ 1 \leq n \leq 20~ nên ta có thể nghĩ đến thuật toán quay lui - nhánh cận hoặc duyệt nhị phân bằng bitmask, do duyệt bitmask có phần tiện hơn nên solution sẽ hướng dẫn theo hướng này

Mỗi lần duyệt, ta sẽ có ~2~ biến là ~S_1~ và ~S_2~, Nếu như bit thứ ~i~ là ~1~ thì ta cộng vào ~S_1~, ngược lại thì cộng vào ~S_2~ và sau mỗi lần duyệt ta sẽ tính chênh lệch của ~S_1~ và ~S_2~ là ~T = |S_1-S_2|~ và nếu ~T~ là nguyên tố thì thỏa mãn và ta sẽ lấy đáp án tốt nhất sau ~2^n~ lần duyệt.

Độ phức tạp: ~O(2^n)~

Code mẫu

#pragma GCC Optimize("O3")
#include<bits/stdc++.h>
#include<string>
#include<vector>
#define endl '\n'
#define alphaa "abcdefghijklmnopqrstuvwxyz"
#define ALPHAA "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define f(i,a,b) for(int i=a;i<=b;i++)
#define f1(i,n) for(int i=1;i<=n;i++)
#define f0(i,n) for(int i=0;i<n;i++)
#define ff(i,b,a) for(int i=b;i>=a;i--)
#define sp(x) cout<<x<<" "
#define en(x) cout<<x<<endl
#define el cout<<'\n'
#define fi first
#define se second
#define pb push_back
#define pk pop_back
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;
typedef long long ll;
const int N=1e6;
const int MOD=1e9+7;
int n,c[N];
ll a[30],ans=-1e18;
void sang()
{
   c[0]=c[1]=1;
   for(int i=2;i<=sqrt(N);i++)
   {
      if(!c[i])
      {
          for(int j=i*i;j<=N;j+=i) c[j]=1;
      }
   }
}
int main()
{
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  //freopen("BAIB.INP","r",stdin);
  //freopen("BAIB.OUT","w",stdout);
  sang();
  cin>>n;
  f0(i,n) cin>>a[i];
  f0(x,(1<<n))
  {
      ll s1=0,s2=0;
      f0(i,n)
      {
         if((x>>i)&1) s1+=a[i];
         else s2+=a[i];
      }
      ll t=abs(s1-s2);
      if(!c[t]) ans=max(ans,t);
  }
  if(ans<=0) cout<<-1;
  else cout<<ans;
}
//-----YEU CODE HON CRUSH-----//

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.