AC手记

记录从暴力到最优的每一步

0%

Codeforces Round 1075 (Div.2)题解

发表于 分类于 6.1k 6 分钟

Codeforces Round 1075 (Div.2)题解

A

CF1075-A

题目大意：给定一个$h \times l$的表格和一个长度为$n$的序列，求从中最多能选出多少对坐标使坐标落在表格内。

先找出$\leq \min(h,l)$的元素个数$x$和$>min(h,l)$且$\leq max(h,l)$的元素个数$y$。因为选两个$x$中的元素必然合法，选一个$x$中的元素和一个$y$中的元素必然合法，选两个$y$中的元素必然不合法，所以最多的合法对数可以分类讨论：（1）$y \leq x$时，先用$y$个$x$中的元素凑成$y$对合法方案，剩下的$x-y$个$x$中的元素可以两两凑成一对，那么总对数为$y+ \frac{x-y}{2}=\frac{x+y}{2}$；（2）$y>x$时，只能凑出$x$对合法方案。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void moth()
{
    int n, h, l;
    cin >> n >> h >> l;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int x = 0, y = 0;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] <= min(h, l))
            x++;
        else if (a[i] <= max(h, l))
            y++;
    }
    if (y <= x)
        cout << (x + y) / 2 << '\n';
    else
        cout << x << '\n';
}

B

CF1075-B

题目大意：一只青蛙从$0$开始跳跃，总共有$n$种类型的跳跃方式，第$i$种跳跃方式每次可以跳跃$a_i$个单位长度，在$b_i$次跳跃后会回退$c_i$个单位长度。问是否可以达到$x$位置。

首先我们可以无需代价的进行$s=\sum_{i=1}^n a_i(b_i-1)$个单位长度而不会回退，如果该距离已经超过了$x$，直接输出$0$即可。如果不能达到$x$位置，就意味着我们需要回退。我们可以定义每种跳跃方式的“前进值”为$t_i=a_ib_i-c_i$，代表着每回退一次可以前进$t_i$个单位长度。显然，在“白嫖”之后如果不能到达$x$，我们会选择“前进值”最大的跳跃方式来尽可能减少回退次数。设最大“前进值”为$mx$，则如果$x-s$能够整除$mx$，那么回退次数就为$\frac{x-s}{mx}$，否则就需要再增加一次回退次数，即$\lfloor \frac{x-s}{mx} \rfloor + 1$。注意，如果“白嫖”后不能到达$x$位置且$mx \leq 0$，那么永远无法达到$x$位置，此时直接输出$-1$。

代码如下：

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
void moth()
{
    ll n, x;
    cin >> n >> x;
    vector<ll> a(n + 1), b(n + 1), c(n + 1);
    ll mx = 0, s = 0;
    bool tag = false;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i] >> b[i] >> c[i];
        mx = max(mx, a[i] * b[i] - c[i]);
        s += a[i] * (b[i] - 1);
        if (a[i] * b[i] - c[i] > 0)
            tag = true;
    }
    if (s >= x)
    {
        cout << 0 << '\n';
        return;
    }
    if (!tag)
    {
        cout << -1 << '\n';
        return;
    }
    if ((x - s) % mx)
        cout << (x - s) / mx + 1 << '\n';
    else
        cout << (x - s) / mx << '\n';
}

C1 & C2

CF1075-C1
CF1075-C2

题目大意：找到一个长度为$n$的排列$p$，使得对于每个$i$（在$C1$中$2 \leq i \leq n-1$，在$C2$中$1 \leq i \leq n-1$），都存在$j$($i \leq j \leq n$)使得$p_i=p_j \oplus i$，或者报告不存在这样的排列。

我们考虑当$i=n-1$的情况，此时$j=n-1$或者$j=n$，但是任何数异或上一个非$0$的数都不可能等于它本身，所以此时$j=n$，即$p_{n-1}=p_n \oplus (n-1)$。再考虑用$1$异或上一个数，结果必然是将这个数加$1$或者减$1$，那么如果我们令$p_n=1$，对于$2 \leq i \leq n-1$，我们都可以令$j=n$，此时所有奇数异或$1$都减$1$，所有偶数都加$1$，并且可以恰好错开并覆盖所有的数，最后把剩下一个没填的数填入$p_1$即可。

按照上面的构造，我们发现，当$n$为奇数时，$p_1=n-1$，否则$p_1=n$。那么在$C2$中，如果$n$为奇数，那么$p_1=n-1=n \oplus 1$，按$C1$的方法构造也正确。但是当$n$为偶数时，我们不能在$[1,n-1]$中找到一个数使得它异或$1$的结果为$n$，因为$(n+1) \oplus 1=n$，但是$n+1>n$。所以此时我们不能令$p_1=n$，那么我们需要在$i \in [2,n]$中找到一个位置可以使得$p_i=n$。

因为$p_i=n=p_j \oplus i$，则$n \oplus p_j=i$($i \leq j \leq n$)。那么我们可以从后往前赋值，每次赋值时标记$p_j \oplus n$，然后检查每个$i$之后是否有$j$已经满足$p_j \oplus n=i$，如果有就将该位设置为$n$，之后不再进行这步判断；否则就无解。

代码如下：
C1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void moth()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    set<int> st;
    for (int i = 2; i <= n; i++)
        st.insert(i);
    a[n] = 1;
    for (int i = n - 1; i >= 2; i--)
    {
        a[i] = a[n] ^ i;
        st.erase(a[i]);
    }
    a[1] = *st.begin();
    for (int i = 1; i <= n; i++)
        cout << a[i] << " \n"[i == n];
}

C2:

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
void moth()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    set<int> st;
    for (int i = 2; i <= n; i++)
        st.insert(i);
    a[n] = 1;
    if (n % 2)
    {
        for (int i = n - 1; i >= 2; i--)
        {
            a[i] = a[n] ^ i;
            st.erase(a[i]);
        }
        a[1] = *st.begin();
        for (int i = 1; i <= n; i++)
            cout << a[i] << " \n"[i == n];
    }
    else
    {
        vector<int> vis((n << 1) + 1);
        bool tag = false;
        for (int i = n - 1; i >= 2; i--)
        {
            if (!tag && vis[i])
            {
                a[i] = n;
                tag = true;
            }
            else
            {
                a[i] = a[n] ^ i;
                vis[a[i] ^ n] = 1;
            }
            st.erase(a[i]);
        }
        a[1] = *st.begin();
        if (!tag)
            cout << -1 << '\n';
        else
        {
            for (int i = 1; i <= n; i++)
                cout << a[i] << " \n"[i == n];
        }
    }
}

D1

CF1075-D1

题目大意：给一个长度为$n$的$01$串$s$和一个正整数$c$，对于一个长度为$n$的排列$p$($0 \leq p_i \leq n-1$)，如果满足下面的条件，就称其为好排列：

  • 若$s_i=1$，则存在一个区间$[l,r]$($1 \leq l \leq r \leq n$)，使得$mex_{i=l}^r p_i=i$ 。
  • 若$s_i=0$，则不存在一个区间$[l,r]$($1 \leq l \leq r \leq n$)，使得$mex_{i=l}^r p_i=i$ 。

如果好排列个数不是$c$的倍数，将其对$10^9+7$取模后输出，否则输出$-1$ 。

假设我们已经插入了$[0,k-1]$的所有数字，那么就会有$k+1$个空位来插入下一个数，我们发现，如果将$k$插入到最前面或者最后面的位置时，那么$k$与$[0,k-1]$的所有数字没有交集，则存在区间$[l,r]$使得$mex_{i=l}^r p_i=k$。如果插入的位置在中间，那么就不存在这样的区间。所以做法就是：定义两个答案$ans1,ans2$，$ans1$计算后对$10^9+7$取模，$ans2$对$c$取模，然后遍历字符串，如果$s_i=1$，就让答案乘以$2$，否则就让答案乘以$i-1$，并取模。注意$s_n=1$是必然的，因为排列只包含了$[0,n-1]$，那么整个排列的$mex$一定为$n$，则如果$s_n=0$，可以直接输出$-1$。最后，如果$ans1$的值为$0$，就直接输出$-1$，否则输出$ans2$ 。

代码如下：

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
void moth()
{
    int n, c;
    cin >> n >> c;
    string s;
    cin >> s;
    s = " " + s;
    if (s[n] == '0')
    {
        cout << -1 << '\n';
        return;
    }
    int ans1 = 1, ans2 = 1;
    for (int i = 1; i <= n - 1; i++)
    {
        if (s[i] == '1')
        {
            ans1 = ans1 * 2 % c;
            ans2 = ans2 * 2 % mod;
        }
        else
        {
            ans1 = ans1 * (i - 1) % c;
            ans2 = ans2 * (i - 1) % mod;
        }
    }
    if (ans1 == 0)
        cout << -1 << '\n';
    else
        cout << ans2 << '\n';
}

D2

CF1075-D2

题目大意同$D1$，但是给的是一个$01?$串，我们可以把"?"改为$0$或者$1$。令$f(w)$为好排列的个数，求在不为$c$的倍数的前提下$f(w)$的最小值对$10^9+7$取模，如果始终为$c$的倍数就输出$-1$。

首先字符串$s$的最后一位依然必须为$1$，否则直接输出$-1$结束。对于$s_i=1$，将答案乘以$2$，否则将答案乘以$i-1$。之后我们考虑"?"位置。对于奇数下标的位置，$i-1$为偶数，如果使贡献为$i-1$，不如使贡献为$2$(位置为$1$的地方也是如此，否则会导致最后结果为$-1$)；对于偶数下标的位置，如果下标为$2$，填"$0$"会导致答案乘以$1$，否则会导致答案乘以$2$，所以此处应该填$1$，至于其它位置，因为要最小化贡献，而越靠后的元素的$i-1$值越大，所以从后往前填"$1$"，让乘数从$i-1$变为$2$，如果$c=2^k$，那么最多可以填$k-1$个"$1$"，其余位置只能填"$0$"。代码的写法可以参照$D1$。

代码如下：

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
void moth()
{
    ll n, c;
    cin >> n >> c;
    string s;
    cin >> s;
    s = " " + s;
    if (s[n] == '0')
    {
        cout << -1 << '\n';
        return;
    }
    ll ans1 = 1, ans2 = 1;
    for (int i = 1; i <= n - 1; i++)
    {
        if (s[i] == '0')
        {
            ans1 = ans1 * (i - 1) % c;
            ans2 = ans2 * (i - 1) % mod;
        }
        else if (s[i] == '1')
        {
            ans1 = ans1 * 2 % c;
            ans2 = ans2 * 2 % mod;
        }
    }
    for (int i = n - 1; i >= 1; i--)
    {
        if (s[i] == '?' && (i % 2))
        {
            ans1 = ans1 * 2 % c;
            ans2 = ans2 * 2 % mod;
        }
    }
    for (int i = n - 1; i >= 3; i--)
    {
        if (s[i] == '?' && (i % 2 == 0))
        {
            if (ans1 * 2 % c != 0)
            {
                ans1 = ans1 * 2 % c;
                ans2 = ans2 * 2 % mod;
            }
            else
            {
                ans1 = ans1 * (i - 1) % c;
                ans2 = ans2 * (i - 1) % mod;
            }
        }
    }
    if (ans1 == 0)
        cout << -1 << '\n';
    else
        cout << ans2 << '\n';
}