A-Rudolf and the Ticket

题意

左边口袋有一些面值为 $b_1,b_2,b_3,...,b_n$ 的硬币，右边有一些面值为 $c_1,c_2,c_3,...,c_m$ 的硬币，问有多少个 $(f,s)$ 可以使得 $b_f+c_s\le k$ 成立

数据范围

$t(1≤t≤100)$

$n,m(1≤n,m≤100)$

$k(1\le k\le 2000)$

$b_i,c_i(1\le b_i,c_i\le 1000)$

思路

双层循环遍历

参考代码

1
void solve() {
2
    ll n, m, k;cin >> n >> m >> k;
3
    vector<ll>b(n), c(m);
4
    for (ll i = 0; i < n; i++) cin >> b[i];
5
    for (ll i = 0; i < m; i++) cin >> c[i];
6
    ll ans = 0;
7
    sort(b.begin(), b.end());
8
    sort(c.begin(), c.end());
9
    for (ll i = 0;i < n;i++) {
10
        for (ll j = 0;j < m;j++) {
11
            if (b[i] + c[j] <= k) {
12
                ans++;
13
            }
14
            else { break; }
15
        }
16
    }
17
    cout<<ans<<endl;
18
}

B-Rudolf and 121

题意

可以对一个数组执行如下操作：

选中一个索引 $i(2\le i\le n-1)$ ：

$a_{i-1}=a_{i-1}-1$
$a_i=a_i-2$
$a_{i+1}=a_{i+1}-1$

询问是否可以通过这个运算使得所有元素变为0

数据范围

$t(1≤t≤10^4)$

$n(3≤n≤2\times 10^5)$

$a_i(0\leq a_i\le 10^9)$

思路

从左向右遍历，若有大于0的数则对其进行置零，且更新其后一位和两位的数值，直到出现负数或无法执行为止。检查操作后的 $a$ 数组是否符合要求

参考代码

1
void solve() {
2
    ll n;cin >> n;
3
    vector<ll>a(n);
4
    for (ll i = 0;i < n;i++) {
5
        cin >> a[i];
6
    }
7
    for (ll i = 0;i < n;i++) {
8
        if (a[i] < 0) {
9
            cout << "NO\n"; return;
10
        }
11
        if (a[i] > 0) {
12
            if(i+2<n){
13
                a[i + 1] -= 2 * a[i];
14
                a[i + 2] -= a[i];
15
                a[i] = 0;
16
            }
17
            else {
18
                cout << "NO\n";return;
19
            }
20
        }
21
    }
22
    cout << "YES\n";
23
}

C-Rudolf and the Ugly String

题意

对字符串 $s$ ，询问至少需要多少次删除字符的操作可以使得字符串中没有子段 $map$ 和 $pie$ 。

数据范围

$t(1≤t≤10^4)$

$n(1≤n≤10^6)$

思路

先查询子段 $mapie$ 的数量，并删去字符 $p$ ，再对剩下的字符串中存在的 $map$ 和 $pie$ 进行计数。

参考代码

1
void solve() {
2
    ll n;cin >> n;
3
    string s;cin >> s;
4
    int p = s.find("mapie");
5
    ll cnt = 0;
6
    while (p != -1) {
7
        s[p + 2] = 'x';
8
        p = s.find("mapie", p + 1);
9
        cnt++;
10
    }
11
    p = s.find("map");
12
    while (p != -1) {
13
        s[p + 2] = 'x';
14
        p = s.find("map", p + 1);
15
        cnt++;
16
    }
17
    p = s.find("pie");
18
    while (p != -1) {
19
        s[p] = 'x';
20
        p = s.find("pie", p + 1);
21
        cnt++;
22
    }
23
    cout << cnt << endl;
24
}

D-Rudolf and the Ball Game

题意

扔球游戏， $n$ 个人围成一圈，每次球可以选择顺时针或逆时针传球 $r_i(1\le r_i \le n-1)$ 个单位，已知起始球的位置和每次传递的距离，以及部分时刻传球的方向。询问最后球到了谁的手上。

数据范围

$t(1≤t≤10^4)$

$n,m(1≤n≤1000,1\le m\le 1000)$

$x(1\le x\le n)$

$r_i(1\le r_i\le n-1)$

思路

按题意模拟即可，每次记录球的所有可能位置，并更新。

参考代码

1
void solve() {
2
    ll n, m, x;cin >> n >> m >> x;
3
    set<ll>xi;
4
    xi.insert(x);
5
    for (ll i = 0;i < m;i++) {
6
        ll r;string c;cin >> r >> c;
7
        if (c == "?") {
8
            set<ll>yi;
9
            for (auto j : xi) {
10
                ll b1 = (j + r) % n, b2 = (j - r + n) % n;
11
                if (b1 == 0) b1 = n;
12
                if (b2 == 0) b2 = n;
13
                yi.insert(b1);yi.insert(b2);
14
            }
15
            xi = yi;
16
        }
17
        else if (c == "1") {
18
            set<ll>yi;
19
            for (auto j : xi) {
20
                ll b1 = (j - r + n) % n;
21
                if (b1 == 0) b1 = n;
22
                yi.insert(b1);
23
            }
24
            xi = yi;
25
        }
26
        else {
27
            set<ll>yi;
28
            for (auto j : xi) {
29
                ll b2 = (j + r) % n;
30
                if (b2 == 0) b2 = n;
31
                yi.insert(b2);
32
            }
33
            xi = yi;
34
        }
35
    }
36
    cout << xi.size() << endl;
37
    for (auto i : xi) {
38
        cout << i << " ";
39
    }cout << '\n';
40
}

E-Rudolf and k Bridges

题意

需要在一条河上建桥，每个位置建立桥墩的花费是 $a_{i,j}+1$ ， $a_{i+j}$ 是到水面的深度。桥要求宽为 $k$ ，任意两个桥墩的距离不能超过 $d$ ，桥的首尾都需要有支架。

数据范围

$t(1≤t≤1000)$

$n,k(1≤k\le n≤100)$

$m(3\le m\le 2\times 10^5)$

思路

对每一行进行DP，可以获得每一行建桥的最小花费。再对其求前缀和，找到总花费最小的连续 $k$ 段。

进行DP状态转移时，需要优先选中距离不大于 $d$ 的桥墩点中，花费最小的桥墩。

参考代码

1
void solve() {
2
    ll n, m, k, d;
3
    cin >> n >> m >> k >> d;
4
    vector<vector<ll>>a(n, vector<ll>(m));
5
    for (ll i = 0;i < n;i++) {
6
        for (ll j = 0;j < m;j++) {
7
            cin >> a[i][j];
8
            a[i][j] += 1;
9
        }
10
    }
11
    // 每行dp
12
    vector<ll>spd(n, 0);
13
    for (ll ni = 0;ni < n;ni++) {
14
        vector<ll>dp(m, 0);
15
        for (ll i = 0;i < m;i++) {
16
            dp[i] = a[ni][i];
17
        }
18
        // 维护前d个值中的最小值
19
        queue<ll>q1;
20
        deque<ll>qmin;
21
        q1.push(dp[0]);
22
        qmin.push_back(dp[0]);
23

24
        for (ll i = 1;i < m;i++) {
25
            if (i == 1)
26
                dp[i] += dp[0];
27
            else {
28
                ll mn = qmin.front();
29
                dp[i] = mn + dp[i];
30
            }
31

32
            if (q1.size() == d + 1) {
33
                if (q1.front() == qmin.front()) {
34
                    qmin.pop_front();
35
                }
36
                q1.pop();
37
            }
38
            q1.push(dp[i]);
39
            while (!qmin.empty() && dp[i] < qmin.back()) {
40
                qmin.pop_back();
41
            }
42
            qmin.push_back(dp[i]);
43
        }
44
        spd[ni] = dp[m - 1];
45
    }
46

47
    vector<ll>sum(n + 1, 0);
48
    sum[0] = 0;
49
    for (ll i = 1;i <= n;i++) {
50
        sum[i] = sum[i - 1] + spd[i - 1];
51
    }
52
    ll ans = sum[k];
53
    for (ll i = k;i <= n;i++) {
54
        ans = min(ans, sum[i] - sum[i - k]);
55
    }
56
    cout << ans << endl;
57
}