Codeforces Round #746 (Div. 2)

发表于 更新于 分类于 本文字数： 871 阅读时长 ≈ 3 分钟

同样只过了A题

英文菜鸡，看样例才知道是不能连续使用同一weapon然后还**地分的情况

UPD:

B题和做的思路差亿点点，可惜自己多虑跑去干E
由题意得出在区间内的元素无法进行题中操作，所以只需对原数组进行排序，然后比对区间内与原数组位序是否相同

E题：

首先切入点是考虑每一位上的情况：对于第位到第位，如果在区间满足题设条件，那么比较强的要求是：在区间上第位的异或值为，按位与值为,而对于第位至最高位的异或值也为，那么显然要完成该要求就需要为偶数

而事实上如果遍历每一位的较强要求下的结果，就能覆盖到原题较弱要求下的解

然后上快读都被报TLE，最后map换成cc_hash_table才3166ms苟过测试点9

UPD: C如果所有节点异或和为，那么容易在任意节点间断开均可。否则的话k就必须大于。

而对于分割成三个部分以上的情况，可以合并成个部分，所以我们现在只需判断能否切成三部分。

A: 
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
const LL N = 1e3 + 86;

LL t, n, h, a[N], dp[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    f(sb, 1, t)
    {
        cin >> n >> h;
        f(i, 1, n) cin >> a[i - 1];
        sort(a, a + n);
        LL max1, max2;
        max1 = a[n - 1];
        max2 = a[n - 2];
        LL res = h / (max1 + max2) * 2;
        h %= (max1 + max2);
        while (h > 0)
        {
            if (res & 1)
                h -= max2;
            else
                h -= max1;
            res += 1;
        }
        cout << res << '\n';
    }
    return 0;
}
B 
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
onst LL N = 1e5 + 86;
LL t, n, x, a[N], b[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    f(sb, 1, t)
    {
        cin >> n >> x;
        bool vis = 1;
        f(i, 1, n)
        {
            cin >> a[i - 1];
            b[i - 1] = a[i - 1];
        }
        sort(a, a + n);
        for (int i = n - x; i <= x - 1; i++)
        {
            if (a[i] != b[i])
                vis = 0;
        }
        if (vis)
            cout << "YES\n";
        else
            cout << "NO\n";
    }
    return 0;
}
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
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>

onst LL N = 1e6 + 86;
LL n, a[N], ans, pref[N];

int main()
{
    //IN;
    //OUT;
    n = io.xint();
    f(i, 1, n) a[i] = io.xint();
    for (int k = 20; k >= 0; k--)
    {
         __gnu_pbds::cc_hash_table<LL, std::vector<LL> > vis[2];
        vis[0][0].pb(0);
        f(i, 1, n) pref[i] = (a[i] >> k) ^ pref[i - 1], vis[i & 1][pref[i]].pb(i);
        LL l = 0;
        for (LL r = 1; r <= n; r++)
        {
            if ((a[r] >> k) & 1)
            {
                std::vector<LL> &v = vis[r & 1][pref[r]];
                std::vector<LL>::iterator it = std::lower_bound(v.begin(), v.end(), l);
                if(it != v.end())
                    ans = ans < r - *it ? r - *it : ans;
            }
            else l=r;
        }
    }
    io.wll(ans);
    return 0;
}
C: 
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
const int N = 1e5 + 86;
int t, n, k, a[N], xo[N], x, c, b, flag;
vector<int> v[N];

int dfs(int now, int fa)
{
    xo[now] = a[now];
    for (auto it : v[now])
    {
        if (it == fa)
            continue;
        xo[now] ^= dfs(it, now);
    }
    return xo[now];
}

void fi(int now, int fa)
{
    for (auto it : v[now])
    {
        if (it == fa)
            continue;
        fi(it, now);
        if (xo[it] == x && flag == 0)
        {
            flag = 1;
            v[now].erase(find(v[now].begin(), v[now].end(), it));
            return;
        }
    }
}

int main()
{
    //IN;
    //OUT;
    ios::sync_with_stdio(false);
    cin.tie(0);
    t = io.xint();
    f(sb, 1, t)
    {
        x = 0;
        n = io.xint();
        k = io.xint();
        f(i, 1, n)
        {
            a[i] = io.xint();
            x ^= a[i];
            v[i].clear();
        }
        f(i, 1, n - 1)
        {
            c = io.xint();
            b = io.xint();
            v[c].pb(b);
            v[b].pb(c);
        }
        if (x == 0)
        {
            io.wstring("YES\n");
            continue;
        }
        else if (k == 2)
        {
            io.wstring("NO\n");
            continue;
        }
        flag = 0;
        dfs(1, 1);
        fi(1, 1);
        //io.wll(flag);
        if (flag == 1)
        {
            flag = 0;
            dfs(1, 1);
            fi(1, 1);
            if (flag == 1)
                io.wstring("YES\n");
            else
                io.wstring("NO\n");
            continue;
        }
        io.wstring("NO\n");
    }
    return 0;
}