NE的俄罗斯方块

NC21787. NE的俄罗斯方块

描述

NE写了一个俄罗斯方块玩，而且和

一样，NE打算加入新机制
其中一个超级强力的道具就是，翻倍消除器，其特性如下：
初始有n列非空砖块，消除器内的计数器为K = 0，高度依次为h₁，h₂，... h_n，有效操作次数为t = 0
1.消除器可以多次使用，每次可以选择任意个h_i> = 2^k-的砖块列，使其高度减少2^k
2.每次使用后，无论选择多少列（包括0），计数器增加1，K = K + 1
3.若选取的个数cnt_j> = 1则记为一次有效操作次数，t = t + 1
4.若不再存在h_i> = 2^k-，结束
NE邀请了赤耳来玩，聪明的赤耳每次使用翻倍消除器的时候，都用最少的有效操作次数，将所有列的砖块数量之和尽可能的减少了
NE想知道，对于某一个局面Q，赤耳究竟进行了几次有效操作？

输入描述

第一行为正整数M表示使用的测试组数M <= 10
接下来M组游戏局面：
每组第一行输入一个正整数N表示含有砖块的列的数量N <= 100000
接下来一行为N个正整数h_i表示第i 个非零列的高度 h_i <= 2 ²⁰ $

输出描述

输出M行
每行一个整数,表示启动消除器后的有效操作次数

示例1

输入:

输出:

2
2

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 487ms, 内存消耗: 6008K, 提交时间: 2018-12-26 20:59:54

#include<iostream>
using namespace std;
int main() {
  int m, n;
  long long a, b;
  cin >> m;
  while(m--) {
    b = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
      cin >> a;
      b |= a;
    }
    cout << __builtin_popcount(b) << endl;
  }
}

C++14(g++5.4) 解法, 执行用时: 373ms, 内存消耗: 6120K, 提交时间: 2019-02-16 12:23:37

#include<iostream>
using namespace std;
int main() {
  int m, n;
  long long a, b;
  cin >> m;
  while(m--) {
    b = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
      cin >> a;
      b |= a;
    }
    cout << __builtin_popcount(b) << endl;
  }
}

上一题

下一题

详情