【2021】360编程题-神枪手

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int n,a[50005],s[30];
ll ans,sum,pw[30];
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int i,j;
    pw[0]=1;
    for(i=1;i<=20;i++) /**< 预处理2的i次幂 */
        pw[i]=pw[i-1]*2;
    cin>>n;
    for(i=1;i<=n;i++) /**< 一发命中直接求和 */
        cin>>a[i],ans+=a[i];
    for(i=1;i<=n;i++)
    {
        ans+=sum;/**< 任意两数或的值如何求？首先两数或不会比任意一数小，
        所以a[i]和a[1]到a[i-1]做或运算首先加上a[1]到a[i-1]的总和*/
        sum+=a[i];
        j=0;
        while(a[i])
        { /**< a[i]的二进制位中某一位为1时，与前面所有数字中这一位没有1的或运算，属于额外所得。 */
            if(a[i]%2==1) /**< s[]数组存储前i-1个数字，各位二进制中1的个数 */
                ans+=pw[j]*(i-1-s[j]),s[j]++;
            j++;
            a[i]/=2;
        }
    }
    cout<<ans;
    return 0;
}

import math
bits=[0]*32 #32Bits
for num in nums:
    num_b_str = list(bin(num)[2:])[::-1]
    for i in range(len(num_b_str)):
        if num_b_str[i]=='1':
            bits[i]+=1
res=sum(nums)
for i in range(len(bits)):
    bit=bits[i]
    cns = math.comb(bit,1)*math.comb(N-bit,1)
    cns+=math.comb(bit,2)
    res+=pow(2,i)*cns
print(res)

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
#define ll long long


int main() {
    int n, temp;
    cin >> n;
    ll sum=0;
    vector<int> vec;
    for (int i = 0; i < n; i++) {
        cin >> temp;
        vec.push_back(temp);
    }
    for(int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            sum += vec[i] | vec[j];
        }
    }
    cout << sum << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, a;
    cin >> n;
    //统计每个二进制位上0和1各有多少
    vector<vector<int>> b(31,vector<int>(2,0));
    long long sum = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a;
        for (int i = 0; i < 31; ++i) {
            b[i][(a >> i) & 1] += 1;
        }
        sum += a;
    }
    long long inc = 0;
    for (int i = 0; i < 31; ++i) {
        //0与任意1异或得1 算清楚了0和1之间异或的情况
        //1和1异或 单方向 不要重复计算
        int n = b[i][1];
        //累加的两部分分别表示0和1异或的和、1和1异或的和
        inc += 1LL * b[i][0] * b[i][1] * (1 << i) + 1LL * (n*(n-1)/2)* (1<<i);
    }
    //加上有一枪没种的情况
    inc += sum;
    cout<<inc<<endl;
    return 0;
}

显然答案为：

(1). 打破一个气球
(2). 所有数对进行或运算后的结果之和

二者之和。

(1) 的结果显然就是所有气球分值之和 sum。

所以关键在于如何计算所有数对进行或运算后的结果和。

或运算 a | b 的结果不会减少 b 的值，而只是会在 b 的基础上，加上二进制表示中某位上 a 为 1 而 b 为 0 的该位的权重。

即

其中 。

所以计算出每位上为 0 的数量和为 1 的数量，然后相乘的结果乘以位权就是或运算增加的值 inc。

过程中因为每个位置的数重复计算了一次，所以结果为 (inc + sum * n - sum)/2。

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int n, a;
    cin >> n;
    vector<array<int, 2>> b(31);
    long long sum = 0;
    for (int _ = 0; _ < n; ++_) {
        cin >> a;
        for (int i = 0; i < 31; ++i) {
            b[i][a >> i & 1] += 1;
        }
        sum += a;
    }
    long long inc = 0;
    for (int i = 0; i < 31; ++i) {
        inc += 1LL * b[i][0] * b[i][1] * (1 << i);
    }
    cout << (inc + sum * n - sum) / 2 + sum << '\n';
    return 0;
}

package test4;

import java.util.Scanner;

/**
 * @author xq
 * @create 2021-05-07-21:10
 */
public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int M = scanner.nextInt();
        int K = scanner.nextInt();
        int[][] ints = new int[N][2];
        int sum = 0;
        for (int i = 0; i < N; i++) {
            ints[i][0] = scanner.nextInt();
            ints[i][1] = scanner.nextInt();
            sum+=ints[i][1];
        }
        if (K>=N){
            System.out.println(sum);
            System.exit(0);
        }
        int[][] dp = new int[N][K+1];
        dp[0][0] = ints[0][1];
        int max = 0;
        for (int i = 1; i <= K; i++) {
            for (int j = 0; j < N; j++) {
                if (dp[j][i-1]>0){
                    for (int k = j+1; k < N; k++) {
                        if (ints[k][0]-ints[j][0]<=M){
                            dp[k][i] = Math.max(dp[k][i],dp[j][i-1]+ints[k][1]);
                            max = Math.max(dp[k][i],max);
                        }
                    }
                }
            }
        }
        System.out.println(max);
    }
//    public static void main(String[] args) {
//        long sum = 0;
//        Scanner scanner = new Scanner(System.in);
//        while (scanner.hasNext()){
//            int nextInt = scanner.nextInt();
//            int[] ints = new int[nextInt];
//            for (int i = 0; i < nextInt; i++) {
//                ints[i] = scanner.nextInt();
//                sum+=ints[i];
//            }
//            for (int i = 0; i < nextInt; i++) {
//                for (int j = i+1; j < nextInt; j++) {
//                    int temp = ints[i]|ints[j];
//                    sum+=temp;
//                }
//            }
//        }
//        System.out.println(sum);
//    }
}