个人积分赛7

D.Make Them Odd

题面如下：

There are n positive integers a1,a2,…,an. For the one move you 
can choose any even value c and divide by two all elements thatequal c.
For example, if a=[6,8,12,6,3,12]and you choose c=6,and a is transformed into a=[3,8,12,3,3,12]after the move.
You need to find the minimal number of moves for transforming a
to an array of only odd integers (each element shouldn't be 
divisible by 2).
Input:The first line of the input contains one integer t(1≤t≤104) —
the number of test cases in the input. 
Then t test cases follow.
The first line of a test case contains n(1≤n≤2⋅105) — 
the number of integers in the sequence a. 
The second line contains positive integers a1,a2,…,an(1≤ai≤109).
The sum of n for all test cases in the input doesn't exceed 2⋅105.
Output:For t test cases print the answers in the order of test cases
in the input. The answer for the test case is the minimal number 
of moves needed to make all numbers in the test case odd 
(i.e. not divisible by 2).
ExampleInput:4640 6 40 3 20 11102442 4 8 1633 1 7Output:41040

本题的大致题意为:一共t组查询，每组n个数，每一次可将该数组里相同的偶数同时除以2，直到该数组里所有的数都为奇数。
核心思路为我们需要用一个数组将偶数的变化过程标记下来，如果循环到某偶数且当前数字未被标记就开始当前循环，若被标记或当前为奇数，则循环结束，每次循环记录一共除的总次数即可。
代码实现：

#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define hhh 3000005
int cmp(int x,int y){return x>y;
}
int a[hhh];
int main(){int t,n,ans;scanf("%d",&t);while(t--){                                 //多组 ans=0;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}	sort(a+1,a+n+1,cmp);                    //快排 使从大到小选择偶数 进行运算  map<int,int>flag;                       //a[i]最大为10的9次，用普通数组定义装不下 for(int i=1;i<=n;i++){if(a[i]%2==0){                      //若为偶数，则进行下列运算 while(a[i]%2==0&&flag[a[i]]==0){//当该数是偶数，且未被标记过，则标记，并将其除2 flag[a[i]]=1;               //标记的作用是使与其相同的数不会被重复除 a[i]=a[i]/2;ans++;                      //记录除的次数 }}}printf("%d\n",ans);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！