// 20' 13min 90.91%
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
// 链表a从高到低存储二进制位
// 链表b从低到高存储二进制位
// 求异或值，最高位存储在头节点且无前导0
// 输入 {1,1,1},{1,0,1}
// 输出 {1，0}
// 输入 {1,0,1,1},{0,1}
// 输出 {1,0,0,1}
class Solution {
public:
ListNode* xorList(ListNode* a, ListNode* b) {
if(!b) return a;
int l1=0,l2=0;
string sa="",sb="";
while(a){
sa+=to_string(a->val);
a=a->next;
}
while(b){
sb+=to_string(b->val);
b=b->next;
}
reverse(sb.begin(),sb.end());
l1=sa.length(),l2=sb.length();
string ans;
int i=0,j=0;
if(l1>l2){
ans=sa.substr(0,l1-l2);
i=l1-l2;
}else if(l1<l2){
ans=sb.substr(0,l2-l1);
j=l2-l1;
}
while(i<sa.length()){
ans+=to_string((sa[i]-'0')^(sb[j]-'0'));
i++,j++;
}
ListNode* h=new ListNode(0),*r=h;
h->next=nullptr;
i=0;
while(i<ans.length()&&ans[i]=='0') i++;
for(;i<ans.length();i++){
r->next=new ListNode(ans[i]-'0');
r=r->next;
}
return h->next;
}
};
// 第2题
// 20' 11.5min 100%
// 给定数组a，执行k次操作，使得最后a的和最小
// 每次操作，选一个数ai，将ai变成ai的二进制中1的个数
// n<1e5, k<=100, ai<=1e9
// 输入 2 1(k) 8 7
// 输出 8
// 输入 3 2 8 7 1024
// 输出 9
// 输入 2 2 2 15
// 输出 3 （对15操作两次，变成[2,1]）
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
int n=0,k;
cin>>n>>k;
vector<int> a(n);
for(int i=0;i<n;i++)
cin>>a[i];
auto cmp = [&](const int& a,const int& b) {
int oa=__builtin_popcount(a),ob=__builtin_popcount(b);
return a-oa<b-ob;
};
priority_queue<int, vector<int>, decltype(cmp)> q{cmp};
for(auto& i:a)
q.push(i);
for(int i=0;i<k;i++){
int t=q.top();q.pop();
// cout<<t<<", ";
q.push(__builtin_popcount(t));
}
// cout<<"\n";
long long s=0;
while(q.size()){
// cout<<q.top()<<", ";
s+=q.top();
q.pop();
}
cout<<s;
return 0;
}
// 20' 100%!!!! 10.5min
// 不是博弈论！吓到了。
// 给定双向队列 q
// 奇数轮次，甲从队首或队尾选元素
// 偶数轮次，乙从队首或队尾选元素
// 第i轮选出的数为xi
// X = x1*10^{10^{n-1}} + x2*10^{10^{n-2}} + ... + xn*10^{10^0}
// 甲让X尽可能大，乙让X尽可能小
// 求最后的X (输出每轮选的数)
// 输入 3 1 2 3
// 输出 3 1 2
// input: 21
// 21 3 4 16 1 17 2 20 18 15 19 14 13 12 11 10 9 7 8 5 6
// output: 21 3 6 4 16 1 17 2 20 5 18 8 15 7 19 9 14 10 13 11 12
// 每个选出的数的权重递减，所以每次选两端最大的数就行...
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void t(vector<int>& b,int l,int r){
}
int main() {
int n=0;
cin>>n;
vector<int> a(n);
for(int i=0;i<n;i++)
cin>>a[i];
vector<int> b(n);
int i=0,j=n-1,c=0;
while(i<=j){
if(c&1){
if(a[i]<a[j])
b[c]=a[i++];
else b[c]=a[j--];
}else{
if(a[i]<a[j])
b[c]=a[j--];
else b[c]=a[i++];
}
c++;
}
for(auto& i:b)
cout<<i<<" ";
return 0;
}
// 第4题
// 20' 41min 71.43%
// 构造01串：
// 第一个字符是1
// 第二个字符是0，字符串为10
// 第3、4个字符是前两个字符的01翻转，得到 1001
// 第5-8个字符是1-4个字符的翻转，得到 10010110
// 第9-16个字符是第1-8个字符的反转，得到 1001011001101001
// 求第L到第R个字符之间有多少个1
// L<=R<=1e14
// 输入 4 7 输出 3
#include <iostream>
#include <vector>
#include <functional>
using namespace std;
#define ll long long
int main() {
ll l,r;cin>>l>>r;
vector<ll> a(50);
a[0]=1;
for(int i=1;i<50;i++){
a[i]=a[i-1]*2LL;
}
vector<ll> ones(50);
ones[0]=1;
for(int i=1;i<50;i++)
ones[i]=a[i]>>1;
function<ll(ll)> count = [&](ll d){
if(d==0) return d;
int i=0;
while(i<50){
if(a[i]<=d)
i++;
else break;
}
i--;
ll q=ones[i];
if(d&1){
if(__builtin_popcount(d)&1) // 找规律：二进制里1的个数是奇数，则第d个字符是1
q+=1;
d--;
}
q+=count(d-a[i]);
return q;
};
// cout<<count(l-1)<<", "<<count(r)<<"\n";
cout<<count(r)-count(l-1);
return 0;
}
// 第5题
// 忘了保存代码，过了3.33%，没超时
// 给定一个数组a，有n个数，和为sum
// 从自然数里找两个数 x，y，满足三个条件：
// 1. |x|+|y|==sum
// 2. 存在一个b数组，其中 bi=ai*x 或者 bi=ai*y，b数组的和为 0
// 3. x、y的绝对值的差的绝对值最小，||x|-|y||最小
// 如果有多个答案，任意输出一种，如果不存在x、y，输出-1（测试了-1没分）
// 1<=n<=100
// 1<=ai<=1000
// 第一行输出两个数 x 和 y
// 第二行输出一个长为n且仅包含'X'、'Y'的字符串
// 第 i 个字符是 'X'，表示 bi=x*ai
// 第 i 个字符是 'Y'，表示 bi=y*ai
// 输入 2 1 -1
// 输出 1 -1 XY
// 输入 5 248 537 207 611 771
// 输出 1148 -1226 XYXYX
// 实现了个暴力，示例都过了，但没超时也没超过空间。。。
int x=sum/2, y=sum/2-sum; // 初始化
sort(a);
for(int i=a.back();i<s;i++){ // 最大的元素为单独一组时和最小，i表示第一组的和
if(i*x==(-y)*(s-i)){ // if(x*i==(-y)*(sum-i) || x*(sum-i)==(-y)*i) // i 是某组和
vector<int> ma(n,0);
// cout<<"bin\n";
if(t(ma,0,0,i,a)){ // dfs 遍历看是否可以构造出和为i
cout<<x<<" "<<y<<"\n";
for(int k=0;k<n;k++)
if(ma[k])cout<<"X";
else cout<<"Y";
return 0;
}
}
if(i*(-y)==x*(s-i)){
vector<int> ma(n,0);
if(t(ma,0,0,s-i,a)){
cout<<x<<" "<<y<<"\n";
for(int k=0;k<n;k++)
if(ma[k])cout<<"X";
else cout<<"Y";
return 0;
}
}
}#腾讯##腾讯招聘##腾讯笔试##23届秋招笔面经#
