情况

时间：2024年7月18日22:35
ABCpass

题解

A

题意

给一个nm矩阵，元素为1~nm，输出每个位置不一样元素的矩阵。如果不能，输出-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
void solve()
{
int n , m ;
cin >> n >> m ;
vector<int> a(n*m+1,0);
if(n*m == 1){
    cin >> n;
    cout << -1 << endl;
    return;
}
else{
    int nums = n * m;
    for (int i = 0; i < nums; ++i)
    {
        cin >> a[i];
}
a[nums] = a[0];
for (int j = 1; j <= nums; ++j)
{

    cout << a[j] << " ";
  
    if (j% m ==0)
    cout << endl;
}
}
return;
}

B

题意

Vova非常喜欢XOR运算（表示为 ⊕ ）。最近，当他要睡觉的时候，他想出了一个有趣的游戏。
在游戏开始时，Vova选择了两个长度为 n的二进制序列 s 和 t ，并将它们交给Vanya。二进制序列是仅由数字 0 和 1 组成的序列。Vanya可以选择整数 l,r ，使得 1≤l≤r≤n ，并且对于所有 l≤i≤r，同时用 si⊕si−l+1 替换 si ，其中 si𝑠𝑖 是序列 s𝑠 的第 i𝑖 个元素。
为了让游戏变得有趣，必须有获胜的可能性。如果Vanya能够通过无限次的动作从序列 s𝑠 中获得序列 t ，则他获胜。确定游戏对于序列 s 和 t 是否有趣。

思路

同时用 si⊕si−l+1 替换 si 。分析一下，1要变成0得有一个1跟他异或，0要变成1要一个1异或。而自己和自己异或肯定是0。所以主要看0变成1的情况。分析得，如果0变成1的位置，前面有1的话，那就可以让0变成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
31
32
33
34
35
36
37
38
39
void solve()
{
    int n;
    cin >> n;
    string s1, s2;
    cin >> s1;
    cin >> s2;
    if (s1[0] == '0' && s2[0] == '1')
    {
        cout << "NO\n";
        return;
    }
    else
    {
        bool flag = false;
        for (int i = 0; i < n; ++i)
        {

            if (s1[i] == '1' && flag == false)
                flag = true;

            if (s1[i] == '0' && s2[i] == '1')
            {
                if (flag == false)
                {
                    cout << "NO\n";
                    return;
                }
                else
                {
                    cout << "YES\n";
                    return;
                }
            }
        }
        cout << "YES\n";
    }
    return;
}

C

题意

雅罗斯拉夫正在玩一个电脑游戏，在其中一个关卡，他遇到了排成一排的 n 蘑菇。每种蘑菇都有自己的毒性水平;从一开始的第i 蘑菇的毒性水平为ai。雅罗斯拉夫可以选择两个整数 1≤l≤r≤n ，然后他的角色将从左到右轮流从这个子段一个接一个地吃蘑菇，即，数字为 l,l+1,l+2,…,r 的蘑菇。
该角色的毒性等级为 g ，初始值为 0 。计算机游戏由数字 x𝑥 定义-在任何给定时间的最大毒性水平。当食用毒性等级为 k 的蘑菇时，会发生以下情况：

  1. 角色的毒性等级增加 k 。
  2. 如果 g≤x ，则过程继续;否则， g 变为零并且过程继续。

雅罗斯拉夫开始感兴趣的是，有多少种方法可以选择 l 和 r 的值，使得 g 的最终值不为零。帮助雅罗斯拉夫找到这个号码！

思路

DP+前缀和。从后往前遍历。找到前缀和数组中不小于(lower_bound)当前前缀和+x的第一个下标。
如果下标：
为前缀和末尾。则说明以i开头的段有一个n-i个满足条件的子段。
前缀和+x正好等于前缀和J,则当前dp[i]+=dp[j+1]+j-i，因为正好等不满足等于0条件
如果不是正好等（大于），则dp[i]+=dp[j]+j-i-1
最终就是dp数组之和

代码

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
void solve()
{
    LL n, x;
    cin >> n >> x;
    LL arr[n], prarr[n + 1] = {0}, dp[n + 3] = {0};

    // Read elements array
    for (LL i = 0; i < n; ++i)
    {
        cin >> arr[i];
        prarr[i + 1] = prarr[i] + arr[i];
    }

    LL ans = 0;

    // Process subsegments in reverse order
    for (LL i = n - 1; i >= 0; --i)
    {
        LL temp = prarr[i] + x;

        // Find the lower bound of the target sum in the prefix sum array
        auto j = lower_bound(prarr, prarr + n + 1, temp) - prarr;

        // Calculate the number of valid subsegments
        if (j == n + 1)
            dp[i] += (n - i);
        else if (temp == prarr[j])
            dp[i] += (j - i) + dp[j + 1];
        else
            dp[i] += (j - i - 1) + dp[j];
    }

    // Calculate the total number of valid subsegments
    for (LL i = 0; i < n + 3; ++i)
    {
        ans += dp[i];
    }

    cout << ans << endl;
}

问题

dp还是牛