Butteruni Blog
0%

2023.8.13练习总结

发表于 更新于 分类于

记录一下最近做的思维题

H-Insert 1, Insert 2, Insert 3, ..._2023牛客暑期多校训练营8 (nowcoder.com)

题意：给定序列 ，定义合法区间 满足对于任意 有 ，即区间内可以由若干个 的序列相互嵌合而成。求序列 中存在多少个合法区间。

思路：考虑如何会对答案造成贡献，假设我们现在已经有合法序列 ，此时若新加入点 能使合法区间向右延伸，必然对 有 ，于是我们对于一段区间需要维护区间内所有值的匹配情况，新加入点 对当前区间造成贡献仅当 。考虑对区间内所有值维护一个栈，栈中记录未匹配这个值的坐标，加入一个合法点 时弹出并压入相应的点即可，此时新点对答案的贡献为满足 的最小 与 的差值加一，为此我们还需要对整个区间维护一个栈，记录所有使得区间合法的 。每个点最多出入栈常数次，整体时间复杂度 

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
ll n, ans;
vector<ll>p[N], s;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int t = 1; //cin >> t;
	while(t --)
	{
        cin >> n;
        int cur,pre_id;
        for(int i = 1; i <= n; i ++)
        {
            cin >> cur; cur --;
            if(!cur) p[1].push_back(i), s.push_back(i), ans += s.size();
            else if(p[cur].empty()) 
            {
                s.clear();
            }
            else
            {
                pre_id = p[cur].back(), p[cur].pop_back(), p[cur + 1].push_back(pre_id);
                while(!s.empty() && s.back() > pre_id) 
                    s.pop_back();
                ans += s.size();
            }
        }
        cout << ans << '\n';
	}
}

Permutation and Primes

题目大意：构造一段长度为 的序列 ，要求 是一个质数且为奇数。

手玩一下发现可以通过构造 这样的序列完全覆盖 的区间同时把 作为下次构造的起点，这样就能构造出所有长度为 的序列。考虑如何覆盖到所有区间，如果在序列末尾添上缺少的 显然难以操作，因此不妨将上述构造方式的起点根据 移动到 ，这样处理方式固定且简单， 的构造方式打表即可

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        vector<int>ans;
        int x = n % 8;
        if(x == 0)
            x = 8;
        if(x == 1)
        {
            ans.push_back(1);
        }else if(x == 2)
        {
            ans.push_back(1);
            ans.push_back(2);
        }else if(x == 3)
        {
            ans.push_back(1);
            ans.push_back(2);
            ans.push_back(3);
        }else if(x == 4)
        {
            ans.push_back(3);
            ans.push_back(2);
            ans.push_back(1);
            ans.push_back(4);
        }else if(x == 5)
        {
            ans.push_back(1);
            ans.push_back(4);
            ans.push_back(3);
            ans.push_back(2);
            ans.push_back(5);
        }else if(x == 6)
        {
            ans.push_back(1);
            ans.push_back(4);
            ans.push_back(3);
            ans.push_back(2);
            ans.push_back(5);
            ans.push_back(6);           
        }else if(x == 7)
        {
            ans.push_back(1);
            ans.push_back(4);
            ans.push_back(3);
            ans.push_back(2);
            ans.push_back(5);
            ans.push_back(6); 
            ans.push_back(7);           
        }else if(n == 8 || x == 8)
        {
            ans.push_back(1);
            ans.push_back(2);
            ans.push_back(3);
            ans.push_back(4);
            ans.push_back(7);          
            ans.push_back(6); 
            ans.push_back(5); 
            ans.push_back(8); 
        }
        if(n == 8)
        {
            for(auto x:ans)
            {
                cout << x << " ";
            }
            cout << '\n';
            continue;
        }
        int cnt = n / 8;
        if(n % 8 == 0)
            cnt--;
        ll st = x;
        if(st == 0)
        {
            ans.push_back(1);
            st = 1;
        }
        for(int i = 1;i <= cnt;++i)
        {
            for(int j = 1;j <= 8;j++)
            {
                if(j % 3 != 0)
                {
                    ans.push_back(st + 3);
                    st += 3;
                }else 
                {
                    ans.push_back(st - 5);
                    st -= 5;
                }
            }
        }
        for(auto x:ans)
        {
            cout << x << " ";
        }
        cout << '\n';
    }
}

D - Count Bracket Sequences (atcoder.jp)

题意：给定长度为 的由 三种字符构成的字符串 ， 已知 可任意变成 或 ，求 能变成多少个不同的合法括号字符串，答案对 取模

思路：不出意外应该是个二维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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const int N = 3030;
ll dp[N][N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    string s;
    cin >> s;
    int n = s.length();
    dp[0][0] = 1;
    for(int i = 0;i < n;++i)
    {
        for(int j = 0;j < n;++j)
        {
            if(s[i] != ')')
                dp[i + 1][j + 1] = (dp[i][j] + dp[i + 1][j + 1]) % mod;
            if(j != 0 && s[i] != '(')
                dp[i + 1][j - 1] = (dp[i + 1][j - 1] + dp[i][j]) % mod;
        }
    }
    cout << dp[n][0];
}

E - Roulettes (atcoder.jp)

题意：有目标点数 ，现有 个转盘，转盘 上有 个 数，每次可花费 抽取转盘并随机获得转盘上数字对应数额的点数，保证每个转盘上数字之和大于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
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
double c[N];
int p[N];
int rp[N];
int s[N][N];
double dp[N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n,m;
    cin >> n >> m;
    for(int i = 1;i <= n;++i)
    {
        cin >> c[i];
        double sum = 0;
        cin >> p[i];
        int cnt = 0;
        for(int j = 1;j <= p[i];++j)
        {
            cin >> s[i][j];
            if(s[i][j] == 0)
                cnt++;
        }
        c[i] = p[i] * c[i] / (p[i] - cnt);
        // cout << sum / p[i] << " ";
        rp[i] = p[i] - cnt;
    }
    for(int i = 0;i <= m;++i)
    {
        dp[i] = INFINITY;
    }
    for(int i = m;i >= 0;--i)
    {
        for(int j = 1;j <= n;++j)
        {
            double tmp = 0;
            for(int k = 1;k <= p[j];++k)
            {
                if(s[j][k] == 0 || i + s[j][k] >= m)
                    continue;
                tmp += dp[i + s[j][k]];
            }
            dp[i] = min(dp[i],c[j] + 1.0 * tmp / rp[j]);
        }
    }
    printf("%.10lf\n",dp[0]);
}

Problem - D - Codeforces

题意：给 个不限使用次数的传送装置，装置 能使得 上的点传送到 ，且后者一定被前者包含，对于 组询问，每次询问回答从 开始传送能得到的最大坐标。

思路：第一反应是用离散化线段树暴力维护，但 被 包含的条件显然没发挥作用。不难发现装置 只对 上的点可能造成贡献， 上的点显然无法使用该传送机使坐标变大。于是合并所有相交区间的 后对于 输出 即可，此处 为左端点距离 最近区间的右端点。

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
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        vector<PII> tree;
        for(int i = 1;i <= n;++i)
        {
            int l,r,a,b;
            cin >> l >> r >> a >> b;
            tree.push_back({l,b});
        }
        sort(tree.begin(),tree.end());
        vector<PII>merge_tree;
        auto [l,r] = tree[0];
        for(auto[st,ed]:tree)
        {
            if(r >= st)
            {
                r = max(r,ed);
            }else 
            {
                merge_tree.push_back({l,r});
                l = st,r = ed;
            }
        }
        merge_tree.push_back({l,r});
        sort(merge_tree.begin(),merge_tree.end());
        int q;
        cin >> q;
        while(q--)
        {
            int x;
            cin >> x;
            int l = 0,r = merge_tree.size();
            while(l < r)
            {
                int mid = (l + r) >> 1;
                if(merge_tree[mid].first <= x)
                {
                    l = mid + 1;
                } else 
                {
                    r = mid;
                }
            }
            if(l != 0)
            {
                cout << max(merge_tree[l - 1].second,x) << " ";
            }else 
            {
                cout << x << " ";
            }
        }
        cout << '\n';
    }
}