T1

给你两个链表，a是正序的，b是逆序的，将两个链表所表示的值进行异或，并输出不带前缀0的结果。

思路

将a链表逆序排列，然后和b末尾对齐，计算每个对应节点的异或值，并用头插法插入到新链表当中。然后删除前置0。

参考代码

/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 *    ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a ListNode类 
     * @param b ListNode类 
     * @return ListNode类
     */
    ListNode* reverse(ListNode* cur){
        ListNode* ret = nullptr;
        while(cur){
            auto tmp = cur->next;
            cur->next = ret;
            ret = cur;
            cur = tmp;
        }
        return ret;
    }
    ListNode* xorList(ListNode* a, ListNode* b) {
        // write code here
        a = reverse(a);
        ListNode* ret = nullptr;
        while(a != nullptr or b != nullptr){
            if(a != nullptr and b != nullptr){
                auto tmp = new ListNode((a->val) ^ (b->val));
                tmp->next = ret;
                ret = tmp;
                a = a->next;
                b = b->next;
            }else if(a != nullptr){
                auto tmp = new ListNode(a->val);
                tmp->next = ret;
                ret = tmp;
                a = a->next;
            }else{
                auto tmp = new ListNode((b->val));
                tmp->next = ret;
                ret = tmp;
                b = b->next;
            }
        }
        while(ret != nullptr and ret->val == 0){
            ret = ret->next;
        }
        if(ret == nullptr){
            return new ListNode(0);
        }else{
            return ret;
        }
    }
};

T2

思路

统计所有数字之和，然后将 {每个数字和他的1的个数之差，每个数的1的个数} 作为一组放到集合当中。然后从集合中取k次最大的元素，更新数字之和，并且将他的1的个数作为新的元素，统计 {每个数字和他的1的个数之差，每个数的1的个数}，并插入集合。

参考代码

#include <bits/stdc++.h>

using namespace std;

int main(){
    int n, k;
    cin >> n >> k;
    vector<long long> arr(n);
    for(auto& it: arr) cin >> it;
    long long ans = accumulate(arr.begin(), arr.end(), 0ll);
    priority_queue<pair<long long, long long>> q;
    for(int i = 0; i < n; ++i){
        long long tb = __builtin_popcountll(arr[i]);   
        q.push({arr[i] - tb, tb});
    }
    for(int i = 0; i < k; ++i){
        auto [delta, curv] = q.top();
        q.pop();
        ans -= delta;
        long long tb = __builtin_popcountll(curv);
        q.push({curv - tb, tb});
    }
    cout << ans << endl;
    return 0;
}

T3

思路

第一个人每次取双端队列的两端中的最大值，第二个人每次取双端队列中的两端中的较小值。

参考代码

#include <bits/stdc++.h>

using namespace std;

int main(){
    int n;
    cin >> n;
    deque<int> dq;
    vector<int> ans(n);
    for(int i = 0; i < n; ++i){
        int tv;
        cin >> tv;
        dq.push_back(tv);
    }
    for(int i = 0; i < n; ++i){
        if(i & 1){
            if(dq.front() < dq.back()){
                ans[i] = dq.front();
                dq.pop_front();
            }else{
                ans[i] = dq.back();
                dq.pop_back();
            }

        }else{
            if(dq.front() > dq.back()){
                ans[i] = dq.front();
                dq.pop_front();
            }else{
                ans[i] = dq.back();
                dq.pop_back();
            }
        }
    }
    for(int i = 0; i < n; ++i) cout << ans[i] << " "; cout << endl;
    return 0;
}

T4

思路

写个方法统计[1, pos]之间的1的数目。如果pos是偶数，那么1的个数就是pos/2。如果pos是奇数，可以发现前面pos - 1个数中是一半的1和一半的0，关键问题是pos位置是1还是0。可以观察到pos的二进制表示中1的数目和翻转次数之间的关系。得到如果pos的二进制表示中1的数目是奇数那么pos位置是1；如果pos的二进制表示中1的数目是偶数，那么pos的位置是0。

参考代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll query(ll pos){
    if(pos & 1) return (__builtin_popcountll(pos) & 1) + pos / 2;
    return pos / 2;
}
int main(){
    ll l, r;
    cin >> l >> r;
    cout << query(r) - query(l - 1) << endl;
    return 0;
}

T5

思路

因为x的绝对值和y的绝对值之和是sum，并且x乘以部分a中的元素加上y乘以a中的其他元素之和等于0，以及x的绝对值和y的绝对值之间的差值最小。
所以我们期望能够把a中的元素分成两个子集合a1和a2，a1的元素的和尽量接近sum的一半。 这样可以构造x等于a2的元素之和，y等于a1的元素之和的负数。这样就能保证满足前面的条件。
于是在代码实现上面，我们用了背包求得最接近一般的解法。

参考代码

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> PII;
const PII nil{-1, -1};
const PII st{0, 0};
int main(){
    int n;
    cin >> n;
    vector<int> arr(n + 1);
    for(int i = 1; i <= n; ++i){
        cin >> arr[i];
    }
    if(n == 1){
        cout << "0 " << arr[1] << endl;
        cout << "X" << endl;
        return 0;
    }
    int sum = accumulate(arr.begin(), arr.end(), 0ll);
    int avg = sum / 2;
    vector<vector<PII>> dp(n + 1, vector<PII>(avg + 1, nil));
    vector<int> vis(n + 1, 0);
    dp[0][0] = st;
    for(int i = 1; i <= n; ++i){
        for(int j = avg; j >= arr[i]; --j){
            if(dp[i - 1][j - arr[i]] != nil){
                dp[i][j] = {i, arr[i]};
            }
        }
        for(int j = 0; j <= avg; ++j){
            if(dp[i][j] == nil) dp[i][j] = dp[i - 1][j];
        }
    }
    int ta = 0;
    for(int i = 0; i <= avg; ++i){
        if(dp[n][i] != nil){
            ta = i;
        }
    }
    {
        int curv = ta, curd = n;
        while(dp[curd][curv] != st){
            vis[dp[curd][curv].first] = 1;
            int nexd = dp[curd][curv].first;
            int nexv = curv - dp[curd][curv].second;
            curv = nexv;
            curd = nexd - 1;
        }
    }
    int tb = sum - ta;
    cout << ta << " " << -tb << endl;
    for(int i = 1; i <= n; ++i){
        if(vis[i]) cout << "Y";
        else cout << "X";
    }
    cout << endl;
    return 0;
}