Блог пользователя Myshyk

Автор Myshyk, история, 6 лет назад, По-русски

Пожалуйста помогите Link

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Где можно сдать?

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

log2(10^12)<=40, можно использовать meet-in-the-middle.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    можно подробней?

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится

      cnt[x][bit] — количество чисел в которых х-ый бит равен bit(0 или 1).

      Давайте обозначим функцию f(x) как сумму , где 1 ≤ i ≤ n

      Как найти f(x) за log :

      Перебераем бит, j, от 1 до 40 (240 > 1012). И добавляем ответу где b, j-ый бит числа x.

      Медленное решение: Перебераем маску x(0 ≤ x ≤ 240), если f(x) равен S тогда выводим x.

      Оптимизируем с помощью meet-in-the-middle. Считаем первую половину, т.e. сохраняем значения. Для второй половины ищем ответ из сохраненных значений.

      Код

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Более понятная реализация, где delta[b][i] сразу же обозначает разницу которую сделает установление i-того бита x-а на b:

using ll = long long;
const int BITS = 40;
const int HALF = BITS / 2;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    ll total;
    cin >> n >> total;
    vector<vector<ll>> delta(2, vector<ll>(BITS));
    for (ll x; n--;) {
        cin >> x;
        for (int b : {0, 1})
            for (int i = 0; i < BITS; i++) {
                ll bit = ((x >> i) & 1);
                bit ^= b;
                delta[b][i] += (bit << i);
            }
    }
    map<ll, int> owner;
    for (int mask = 0; mask < (1 << HALF); mask++) {
        ll sum = 0;
        for (int i = 0; i < HALF; i++)
            sum += delta[(mask >> i) & 1][i];
        owner[sum] = mask;
    }
    for (ll submask = 0; submask < (1 << HALF); submask++) {
        ll mask = (submask << HALF);    
        ll sum = 0;
        for (int i = HALF; i < BITS; i++)
            sum += delta[(mask >> i) & 1][i];
        if (owner.find(total - sum) != owner.end())
            cout << (mask | owner[total - sum]), exit(0);                           
    }
    cout << -1;
    return false;
}