P171SUMB – ptit

Đề bài:

Thuật toán:

  • Gọi \(cnt[i]\) là số các số chia mod k = i trong tập \(S\).
  • Theo đề bài ta có: \(KQ = KQ + max(cnt[i], cnt[k-i])\) với \(i=1..k/2\).
    • Chú ý nếu n mod 2 = 0 thì ta không cộng \(cnt[n/2]\) vào KQ mà chỉ cộng 1 thôi.

Code:

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
int n, k, i, j, a[200004], cnt[500], ans;
int main() {
    cin >> n >> k;
    for (int i=1; i<=n; i++) cin >> a[i];
    for (int i=1; i<=n; i++) {
        a[i] = a[i] % k;
        ++cnt[a[i]];
    }
    for (int i=1; i<=k/2; i++) {
        ans = ans + max(cnt[i], cnt[k-i]);
    }
    if (k%2 == 0) {
        ans -= cnt[k/2];
        if (cnt[k/2]>0) ans++;
    }
    if (cnt[0] > 0) ans++;
    cout << ans;
	return 0;
}
Khuyên dùng

 

About Aida Nana

Nghề chính là chém gió, quăng bom và ném lựu đạn.
Nghề phụ là cắt cỏ, chém chuối, cưa cây......

Comments

  1. thasnk ad chia sẻ

Speak Your Mind

*