牛客周赛 Round 59

A

只需要进行普通模拟即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int double
void solve(){
    int n,m;
    cin>>n>>m;
    printf("%.7lf",n/m);
    return ;
}
 
signed main(){
    // int t=1;
//    cin>>t;
    solve();
}

B

判断4个子串即可。

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int N = 2e5 + 5, M = 5e2 + 5, base = 131;
const int inf = 0x3f3f3f3f3f3f3f3f, MOD = 1e9 + 7;
string s;
void solve()
{
    cin >> s;
    if ((s.find("https://www.nowcoder.com") == 0) || (s.find("www.nowcoder.com") == 0))
    {
        cout << "Nowcoder" << endl;
        return;
    }
    if ((s.find("https://ac.nowcoder.com") == 0) || (s.find("ac.nowcoder.com") == 0))
    {
        cout << "Ac" << endl;
        return;
    }
    cout << "No" << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
    for (int i = 1; i <= T; i++)
    {
        solve();
    }
    return 0;
}

C

算出所有的顺序对和逆序对数，然后减去k即可。

1
2
3
4
5
6
7
8
9
10
#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL n,k;
int main(){
    cin>>n>>k;
    cout<<n*(n-1)/2-k;
      
    return 0;
}

D

构造时候有一些技巧：

  1. 用一个前缀和记录一定要弄的数字。
  2. 注意特判0的情况。
  3. 注意用0凑数字是最简单的。
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
#include <bits/stdc++.h>
#define N 200005
using namespace std;
long long t, s, n, k;
vector<long long> a(100005, 0);
int main()
{
    cin >> t;
    for (int i = 1; i < 100000; i++)
    {
        a[i] = a[i - 1] + i;
    }
    while (t--)
    {
        cin >> s >> n >> k;
 
        if (k == 0)
        {
            if (n > s)
            {
                cout << "NO" << endl;
            }
            else
            {
                cout << "YES" << endl;
                for (int i = 0; i < n - 1; i++)
                    cout << 1 << " ";
                cout << s - n + 1 << endl;
            }
            continue;
        }
        if (k > n || a[k - 1] > s)
        {
            cout << "NO" << endl;
            continue;
        }
        vector<int> ans(n);
        for (int i = 0; i < k; i++)
            ans[i] = i;
        s -= a[k - 1];
        for (int i = k; i < n; i++)
        {
            if (s != k)
                ans[i] = s, s = 0;
            else
            {
                ans[i] = s - 1;
                s = 1;
            }
        }
        if (s == 0)
        {
            cout << "YES" << endl;
            for (int i = 0; i < n; i++)
                cout << ans[i] << ' ';
            cout << endl;
        }
        else
            cout << "NO" << endl;
    }
    return 0;
}

F

在这个动态规划（DP）问题中，dp[l][r][x] 表示在区间 [l, r] 内的不同类型子序列的回文值之和。具体的 4 个状态分别是：

1. dp[l][r][0]：不包含左右端点 [0, 0] 的子序列

  • 含义：这表示区间 [l, r] 中所有不包含左右端点 l 和 r 的子序列的回文值之和。
  • 由于不包含端点，实际上是在考虑 [l + 1, r - 1] 内的子序列。因此，这个状态可以直接从 dp[l + 1][r - 1][4] 继承下来，因为状态 4 包含了所有类型子序列的总和。

2. dp[l][r][1]：包含左端点但不包含右端点 [1, 0] 的子序列

  • 含义：这表示区间 [l, r] 中所有包含左端点 l 但不包含右端点 r 的子序列的回文值之和。
  • 这类子序列可以通过扩展右端点前面的子序列来得到，因此 dp[l][r][1] 可以从状态 dp[l][r-1][1] 和 dp[l][r-1][3] 推导出来。即，首先考虑原先已经包含左端点的子序列，然后再加上同时包含左右端点的子序列的贡献。

3. dp[l][r][2]：不包含左端点但包含右端点 [0, 1] 的子序列

  • 含义：这表示区间 [l, r] 中所有不包含左端点 l 但包含右端点 r 的子序列的回文值之和。
  • 这类子序列可以通过扩展左端点前面的子序列来得到，因此 dp[l][r][2] 可以从状态 dp[l+1][r][2] 和 dp[l+1][r][3] 推导出来。即，首先考虑原先已经包含右端点的子序列，然后再加上同时包含左右端点的子序列的贡献。

4. dp[l][r][3]：包含左右端点 [1, 1] 的子序列

  • 含义：这表示区间 [l, r] 中所有同时包含左右端点 l 和 r 的子序列的回文值之和。
  • 这里需要判断 a[l] 和 a[r] 是否相等：
    • 如果相等，则左右端点不需要修改；
    • 如果不相等，则需要修改一端，使它们相等。
  • 因此，该状态的值由 dp[l+1][r-1][4]（即区间内部的子序列）加上修改端点的代价来计算，后者由 power(2, r - l - 1) * (a[l] != a[r]) 决定。

5. dp[l][r][4]：区间 [l, r] 内所有子序列的回文值之和

  • 含义：这是一个综合状态，表示区间 [l, r] 内所有类型子序列的回文值总和，包括 [0, 0]、[1, 0]、[0, 1] 和 [1, 1] 的子序列。
  • 这个状态是由前面四个状态相加得到的，因此 dp[l][r][4] 是所有子序列的回文值之和： $ dp[l][r][4] = dp[l][r][0] + dp[l][r][1] + dp[l][r][2] + dp[l][r][3] $

总结：

  • dp[l][r][0]：不包含两端的子序列的回文值和。
  • dp[l][r][1]：包含左端点但不包含右端点的子序列的回文值和。
  • dp[l][r][2]：不包含左端点但包含右端点的子序列的回文值和。
  • dp[l][r][3]：同时包含左右端点的子序列的回文值和。
  • dp[l][r][4]：综合状态，表示区间内所有子序列的回文值总和。
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
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
constexpr int P = 1E9 + 7;

int power(i64 a, i64 b)
{
    i64 res = 1;
    while (b)
    {
        if (b % 2)
        {
            res = res * a % P;
        }
        a = a * a % P;
        b /= 2;
    }
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }

    vector dp(n + 1, vector<vector<int>>(n + 1, vector<int>(5)));
    for (int len = 2; len <= n; len++)
    {
        for (int l = 1; l + len - 1 <= n; l++)
        {
            int r = l + len - 1;
            dp[l][r][0] = ((i64)dp[l + 1][r - 1][4]) % P;
            dp[l][r][1] = ((i64)dp[l][r - 1][1] + dp[l][r - 1][3]) % P;
            dp[l][r][2] = ((i64)dp[l + 1][r][2] + dp[l + 1][r][3]) % P;
            dp[l][r][3] = ((i64)dp[l + 1][r - 1][4] + power(2, r - l - 1) * (a[l] != a[r])) % P;
            for (int i = 0; i < 4; i++)
            {
                dp[l][r][4] = ((i64)dp[l][r][4] + dp[l][r][i]) % P;
            }
        }
    }

    cout << dp[1][n][4] << "\n";

    return 0;
}