Question A Ancient Civilization

There are \ (T(1\leq T \leq 100) \) groups of data.

Define \ (\ operatorname{d}(x,y) \) as the distance between the number of \ (x,y \), and the value is the sum of the number of different positions under binary. (for example \ (10010)_ 2 \) and \ (01011)_ 2 \), the distance between the two numbers is 3).

Now, we have the number of \ (n \), and the number of \ (I \) is recorded as \ (x_i \). Now try to find a number \ (Y \) to minimize \ (\ sum \ limits {I = 1} ^ n \ operatorname {D} (x_, I, y) \) and output \ (Y \).

\(n \ Leq 100,0 \ Leq x_i, y < 2 ^ l \), where \ (l \) is a constant given in the title, and \ (1\leq l \leq 30 \)

The contribution of each bit is calculated. Obviously, in order to minimize the distance, give priority to keeping the bit of \ (y \) consistent with most (for example, if the xx bit of a number is 1 and the xx bit of b number is 0, then the bit of \ (y \) should be determined according to the size relationship between a and b. This operation is performed on each bit with a total complexity of \ (O(Tln) \).

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n, l, x[N];
int solve() {
    cin >> n >> l;
    for (int i = 1; i <= n; ++i)
        cin >> x[i];

    int res = 0;
    for (int i = 0; i < 30; ++i) {
        int a = 0, b = 0;
        for (int k = 1; k <= n; ++k)
            if ((x[k] >> i) & 1) a++;
            else b++;
        if (a > b) res += 1 << i;
    }
    return res;
}

int main()
{
    int T;
    cin >> T;
    while (T--) cout << solve() << endl;
    return 0;
}

Question B Elementary Particles

There are \ (T(1\leq T \leq 100) \) groups of data.

Give A sequence \ (\ {a_n \} \) with A length of \ (n \). If there are two sub intervals \ ([l_1,r_1],[l_2,r_2] \), they are different from each other (i.e., it is impossible for \ (l_1=l_2 \) and \ (r_1=r_2 \)) to have the same length and one bit is the same (for example, \ ([4,3,2,1] \) and \ ([5,3,4,8] \), the two intervals are equal in length and the second bit is the same), then we say that the two intervals satisfy property A.

Q: what are the lengths of the two longest subintervals satisfying property A that we can find in this sequence? (output - 1 without solution)

\(2\leq n \leq 150000,1\leq a_i\leq 150000,\sum n\leq 3*10^5\)

It seems that as long as a certain bit is the same, a pair of intervals can be gathered, so scan it directly. If there is no same element, there is no solution.

If there are the same elements, you can expand this to see how long it can be extended at most. Assuming that the elements of position \ (i,j \) (\ (I < J \)) are the same, the longest interval length is \ ((n-j)+(i-1)+1=n-(j-i) \). (that is, this element is the \ (I \) th element of the whole interval. At this time, the interval length is the longest. The derivation process is to make \ (a_j \) the \ (1,2,\cdots,i \) of the interval in turn)

With a mathematical foundation, the problem changes to: find two identical elements with the shortest distance in the sequence. Limited by multiple groups of data and intellectual education, we might as well open a \ (map \) to maintain the previous position of each element, update it whenever a new element is scanned, and recalculate the shortest distance. The total complexity is \ (O(n\log n) \).

#include<bits/stdc++.h>
using namespace std;
const int N = 300010;
int n, a[N];
map<int, int> vis;
int solve() {
    vis.clear();

    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    int dis = n + 1;
    for (int i = 1; i <= n; ++i) {
        if (vis[a[i]]) dis = min(dis, i - vis[a[i]]);
        vis[a[i]] = i;
    }
    return n - dis;
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T--) printf("%d\n", solve());
    return 0;
}

Question C Road Optimization

The meaning of the title is brief.

For a DP, the first dimension record is currently going to the \ (i \) rod, and the second bit record has retained \ (j \) rods (instead of pulling out several).

After this, the state transition equation is relatively easy to write:

(Note: if you want to reach the \ (i \) pole, it means that it has not arrived yet, so this pole will not be pulled out for the time being. It will be transferred later

I won't elaborate on how to count the answers and output. Look at the code:

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 510;
int n, k;
LL len, d[N], a[N];
LL dp[N][N];
int main()
{
    //read
    cin >> n >> len >> k;
    for (int i = 1; i <= n; i++)
        cin >> d[i];
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    //solve
    d[n + 1] = len;
    memset(dp, 0x3f, sizeof(dp));
    dp[1][0] = 0;

    for (int i = 1; i <= n + 1; i++)
        for (int j = 1; j < i; j++)
            for (int x = 1; x <= j; x++)
                dp[i][x] = min(dp[i][x], dp[j][x - 1] + a[j] * (d[i] - d[j]));

    LL ans = 1e18;
    for (int i = 0; i <= k; i++)
        ans = min(ans, dp[n + 1][n - i]);
    cout << ans;
    return 0;
}