本来想偷懒的，回头来还是写了。

A. Ancient Civilization

题意

给出含有n个数的数组，和数组中的数的二进制位大小。
定义距离d(x,y)为x和y不同二进制位的个数，输出一个数，使得这个数到数组中所有数的距离之和最小。

题解

因为是到数组中所有的数，考虑贪心。我们把每一位是1的出现次数统计出来，如果大于总数一半，输出值的这一位就置1，否则置0。

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <deque>
#include <iostream>
#include <map>
#include <deque>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <bitset>
#include <tuple>
#define ll long long
#define pi acos(-1)
#define hu(x) x*pi/180.0
#define mod 998244353
#define linf 0x7fffffffffffff
using namespace std;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll T;
    cin >> T;
    while (T--) {
        int n, l ,s;
        cin >> n >> l;
        int num[35];
        memset(num, 0, sizeof(num));
        for (int i = 0; i < n; i++) {
            cin >> s;
            bitset<35> bit(s);
            for (int j = 0; j < 34; j++) {
                if (bit[j] == 1) num[j]++;
            }
        }
        int re = 0;
        for (int i = 0; i < 34; i++) {
            if (num[i] > n / 2) re += (1 << i);
        }
        cout << re << endl;
    }
    return 0;
}

B. Elementary Particles

题意

给出含有n个数的数组，找出两个长度相同且起始点和终点不同的区间，使得这两个区间中的某个相同位数相同，求这个区间最大长度。

题解

我们发现，对于任意两个相同的数，最大区间长度=（左边的数的左边的数的个数+右边的数右边的数的个数+1）。
例如，对于
1 2 3 4 2 7 5 6
中的两个2，两个最长区间为1 2 3 4 2和4 2 7 5 6。长度又左边的2的左边的数的个数和右边的2右边的数的个数决定。
而使得这两个数的和尽可能大，易知两个数越近越好。
所有我们排序后遍历一遍即可。

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <deque>
#include <iostream>
#include <map>
#include <deque>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <bitset>
#include <tuple>
#define ll long long
#define pi acos(-1)
#define hu(x) x*pi/180.0
#define mod 998244353
#define linf 0x7fffffffffffff
using namespace std;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        pair<int,int>* num = new pair<int, int>[n];
        for (int i = 0; i < n; i++) {
            cin >> num[i].first;
            num[i].second = i;
        }
        sort(num, num + n);
        int re = 0;
        int last = num[0].first;
        int lastw = num[0].second;
        for (int i = 1; i < n; i++) {
            if (num[i].first == last) {
                re = max(re, lastw + n - num[i].second);
            }
            last = num[i].first;
            lastw = num[i].second;
        }
        if (re == 0) cout << -1 << endl;
        else cout << re << endl;
    }
    return 0;
}

C. Road Optimization

给出一条从路，同时给出每一段限速的倒数和所在位置，我们可以去掉最多k个限速，求最少的时间。

题解

参考了tourist的做法。
考虑dp，我们用dp[i][j]表示从i开始去掉i前面不大于k个限速的时间，p每循环一次就列出所有拆除j个的情况，状态转移方程为dp[i][j] = min(dp[i][j], dp[p][old] + (a[i] – a[p]) * b[p])。然后我们可以在dp[n]中找出拆除从0-k个的最小时间。

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <deque>
#include <iostream>
#include <map>
#include <deque>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <bitset>
#include <tuple>
#define ll long long
#define pi acos(-1)
#define hu(x) x*pi/180.0
#define mod 998244353
#define linf 0x7fffffffffffff
#define inf 0x7f7f7f7f
using namespace std;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, l, k;
    cin >> n >> l >> k;
    int* a = new int[n+1];
    int* b = new int[n+1];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    a[n] = l;
    b[n] = 0;
    ll dp[505][505];
    memset(dp, 0x7f, sizeof(dp));
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            for (int p = i - 1; p >= 0; p--) {
                int old = j - (i - p - 1);
                if (old >= 0) {
                    dp[i][j] = min(dp[i][j], dp[p][old] + (a[i] - a[p]) * b[p]);
                }
            }
        }
    }
    cout << *min_element(dp[n], dp[n] + k + 1) << endl;
    return 0;
}