1.找出数组中的 K-or 值

按题意模拟

int findKOr(vector<int>& p, int k) {
    //位运算枚举32位
    int res=0;
    for(int i=0;i<31;i++){
        int cnt=0;
        for(auto x:p) cnt+=(x>>i)&1;
        if(cnt>=k)  res+=(1<<i);
    }
    return res;
}

2.数组的最小相等和

定义题

long long minSum(vector<int>& q1, vector<int>& q2) {
    long long sum1=0;int cnt1=0;
    long long sum2=0;int cnt2=0;
    for(auto x1:q1) sum1+=x1,cnt1+=x1==0;
    for(auto x2:q2) sum2+=x2,cnt2+=x2==0;
    if(cnt1==0&&sum1<sum2+cnt2||cnt2==0&&sum2<sum1+cnt1)    return -1;
    return max(sum1+cnt1,sum2+cnt2);
}

3.使数组变美的最小增量运算数

贪心

大于或等于 3 的子数组，其 最大 元素都大于或等于 k等价于长度等于3的子数组......

dfs

设dfs(i,j)表示前0-i位，右侧有j个没有增量的数所对应的最小增量数，则

​dfs(i,j)=min\left\{\begin{matrix} dfs(i-1,0)+max(k-p[i],0), &决策q[i]增大到k\\ dfs(i-1,j+1), &j<2\end{matrix}\right.

long long minIncrementOperations(vector<int>& p, int k) {
    int n=p.size();
    vector<vector<long long>> memo(n,vector<long long>(3,-1));
    function<long long(int,int)> dfs=[&](int i,int j)->long long{
        if(i<0) return 0;
        auto &sts=memo[i][j];
        if(sts==-1){
            //若做出修改i位置
            sts=dfs(i-1,0)+max(k-p[i],0);
            //若j<2，可以不做修改
            if(j<2)
            sts=min(sts,dfs(i-1,j+1));
        }
        return sts;
    };
    return dfs(n-1,0);
}

4.收集所有金币可获得的最大积分

按题意遍历到一个节点有两种选择，我们设dfs(i,j)表示第i个节点，前i-1个节点右移了j次，在该节点能获得的最大积分。

两种决策​res1=(q[i]>>j)-k , ​res2=q[i]>>(j+1)

​dfs(i,j)=max\left\{\begin{matrix} res1+\sum\limits_{ch\in g[i]}^{ch!=fa}dfs(ch,j), &决策1\\ res2+\sum\limits_{ch\in g[i]}^{ch!=fa}dfs(ch,j+1), &ceil(\frac{10^4}{2^j})\geq1\end{matrix}\right.

int maximumPoints(vector<vector<int>>& l, vector<int>& q, int k) {
    int n=q.size();
    vector<vector<int>> g(n);
    for(auto &t:l){
        int x=t[0],y=t[1];
        g[x].push_back(y);
        g[y].push_back(x);
    }
    vector<vector<int>> f(n,vector<int>(14,-1));
    function<int(int,int,int)> dfs=[&](int i,int j,int fa)->int{
        auto &res=f[i][j];
        if(res==-1){
            int res1=(q[i]>>j)-k;
            int res2= q[i]>>(j+1);
            for(auto ch:g[i]){
                if(ch==fa)  continue;
                            res1+=dfs(ch,j,i);
                if(j<13)    res2+=dfs(ch,j+1,i);
            }
            res=max(res1,res2);
        }
        return res;
    };
    return dfs(0,0,-1);
}