Educational Codeforces Round 76 (E-G)

发表于 | 阅读数

E,F,G

E

给三个人的工作安排,通过调度后使三个人工作可以连续，求最小操作数。
将每个人的工作排序，为了保证最小操作数，一定使调度没有从小到大的元素。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
int a[N], dp[N], ans;
int n, k1, k2, k3;
int main()
{
    scanf("%d%d%d", &k1, &k2, &k3);
    n = k1 + k2 + k3;
    for (int i = 1; i <= k1 + k2 + k3; i++)
        scanf("%d", &a[i]);
    sort(1 + a, 1 + a + k1);
    sort(1 + a + k1, 1 + a + k1 + k2);
    sort(1 + a + k1 + k2, 1 + a + k1 + k2 + k3);

    dp[1] = a[1];
    ans = 1;
    for (int i = 2; i <= n; i++)
    {

        int k = a[i];

        if (k > dp[ans])
        {
            dp[++ans] = k;
            continue;
        }
        int l = 1;
        int r = ans;
        int pos = n;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            //cout<<l<<" "<<mid<<" "<<r<<endl;
            if (dp[mid] >= k)
            {
                pos = mid;
                r = mid - 1;
            }
            else
            {
                l = mid + 1;
            }
        }

        dp[pos] = k;
    }
    printf("%d\n", n - ans);
}

F

询问一个$x$,使得所有$a_1\bigoplus x,a_2\bigoplus x…a_n\bigoplus x$的二进制$1$的数量为相同。$(n<=100,a_i<=2^30-1)$

可以$meet-in-the-middle$,先处理前和后$15$为异或得到二进制得值，然后枚举二进制$1$的数量为$k$。

这时候可以用神奇的$map, int>$进行匹配。就好了


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
const int N = 1 << 15;
int f[N], n, l[N], r[N];
map<vector<int>, int> mp;
void init()
{
    for (int i = 0; i < N; i++)
    {
        int k = i;
        while (k)
        {
            f[i] += k % 2;
            k /= 2;
        }
    }
}
int main()
{
    init();
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        r[i] = x >> 15;
        l[i] = x & (N - 1);
    }
    for (int i = 0; i < N; i++)
    {
        vector<int> g;
        int k = f[l[1] ^ i];
        //cout<<l[1]<<endl;;
        for (int j = 2; j <= n; j++)
            g.push_back(f[l[j] ^ i] - k);
        //cout <<g[0]<<" "<<g[1]<<endl;
        mp[g] = i;
    }
    for (int i = 0; i < N; i++)
    {
        vector<int> g;
        int k = f[r[1] ^ i];
        for (int j = 2; j <= n; j++)
            g.push_back(-f[r[j] ^ i] + k);
        if (mp.count(g))
        {
            //cout<<mp[g]<<endl;
            printf("%d", mp[g] + (i << 15));
            return 0;
        }
    }
    printf("-1");
}

</details>

代码