JZTXT

《看了受制了》第二十七天，13道题，合计134道题

发布时间 2023-09-28 01:15:59作者: wxzcch

2023年9月26日
因为昨天没写总结，所以今天需要写两篇，补上来。昨天第一次注册cf，以后加油！

Acwing1137 最佳选择路线

题目理解

该题为多起点最短路模型，可以从公交站到多个公交站的最短路，那么只需要把多个起点赋值为0，然后求最短路就行了。
幸运的是因为前天，9月25号，de了很久的bug，导致板子一次就敲对了，可太好了。hhhh这怕是，底层算法孩子，最后的幸运了吧。

代码实现

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;

const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;

ll qmi(ll a, ll b){
    ll res = 1;
    while(b)
    {
        if(b & 1) res = res * a % Mod;
        a = a * a % Mod;
        b >>= 1;
    }
    return res;
}

ll inv(ll x){ return qmi(x, Mod - 2);}
ll mo(ll x){ return (x % Mod + Mod) % Mod;}
const int N = 1010, M = 200010;

int n, m, s;
int h[N], e[M], ne[M], w[M], idx;
int d[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

void dijksra()
{
    memset(d, INF, sizeof d);
    memset(st, 0, sizeof st);
    
    int T;
    cin >> T;

    priority_queue<PII, vector<PII>, greater<PII>> heap;

    for(int i = 1; i <= T; i++)
    {
        int k;
        cin >> k;

        d[k] = 0;
        heap.push({0, k});
    }

    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.y;
        if(st[ver]) continue;
        st[ver] = true;

        for(int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(d[j] > d[ver] + w[i])
            {
                d[j] = d[ver] + w[i];
                heap.push({d[j], j});
            }
        }
    }
}

int main() {


    while(cin >> n >> m >> s)
    {
        memset(h, -1, sizeof h);
        idx = 0;
        for(int i = 1; i <= m; i++)
        {
            int a, b, c;
            cin >> a >> b >> c;
            add(a, b, c);
        }
        
        dijksra();
        
        if(d[s] == INF) cout << -1 << endl;
        else cout << d[s] << endl;
    }

    return 0;
}

Div.4 Round898 A Short Sort

题目理解

任意交换两个字符，最后可否出现abc的字符序列，那么只需要模拟就好了。只能交换一次！

代码实现

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <map>
#include <set>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;

const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;

ll qmi(ll a, ll b){
    ll res = 1;
    while(b)
    {
        if(b & 1) res = res * a % Mod;
        a = a * a % Mod;
        b >>= 1;
    }
    return res;
}

ll inv(ll x){ return qmi(x, Mod - 2);}
ll mo(ll x){ return (x % Mod + Mod) % Mod;}


int main() {
    
    int n;
    string s;
    cin >> n;

    while(n -- )
    {
        cin >> s;

        if(s == "abc")
        {
            cout << "YES" << endl;
            continue;
        }

        swap(s[0], s[1]);
        if(s == "abc")
        {
            cout << "YES" << endl;
            continue;
        }

        swap(s[0], s[1]);
        swap(s[0], s[2]);
        if(s == "abc")
        {
            cout << "YES" << endl;
            continue;;
        }

        swap(s[0], s[2]);
        swap(s[1], s[2]);
        if(s == "abc")
        {
            cout << "YES" << endl;
            continue;
        }

        cout << "NO" << endl;
    }
    

    return 0;
}

Div.4 Round898 B Good Kid

题目理解

问的是，可以给任何一个数加一，然后把乘积变到最大！
我们把最小的值加一，然后累乘即可。

代码实现

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <map>
#include <set>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;

const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;

ll qmi(ll a, ll b)
{
    ll res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a % Mod;
        a = a * a % Mod;
        b >>= 1;
    }
    return res;
}

ll inv(ll x) { return qmi(x, Mod - 2); }
ll mo(ll x) { return (x % Mod + Mod) % Mod; }

const int N = 11;
int a[N], n;

int main()
{

    cin >> n;

    while (n--)
    {
        int k;
        cin >> k;

        int p = INF, flag = 1;
        for (int i = 1; i <= k; i++)
        {
            cin >> a[i];
            if (a[i] < p)
            {
                p = a[i];
                flag = i;
            }
        }

        a[flag]++;
        ll res = 1;

        for (int i = 1; i <= k; i++)
            res *= a[i];

        cout << res << endl;
    }

    return 0;
}

Div.4 Round898 C Target Practice

题目理解

该题目模拟即可，就是问最后的得分是多少，最外圈是1分，内一圈就加一分。

代码实现

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;

const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;

ll qmi(ll a, ll b){
    ll res = 1;
    while(b)
    {
        if(b & 1) res = res * a % Mod;
        a = a * a % Mod;
        b >>= 1;
    }
    return res;
}

ll inv(ll x){ return qmi(x, Mod - 2);}
ll mo(ll x){ return (x % Mod + Mod) % Mod;}

bool check(int i, int j, int u)
{
    if(i == u + 1 && j >= 1 + u && j <= 10 - u || i == 10 - u && j >= 1 + u && j <= 10 - u)
        return true;
    
    if(j == u + 1 && i >= 1 + u && i <= 10 - u || j == 10 - u && i >= 1 + u && j <= 10 - u)
        return true;
    
    return false;
}

int val(int i, int j)
{
    int ans = 0;

    if(i == 1 || i == 10 || j == 1 || j == 10)
        return 1;
    else if(check(i, j, 1))
        return 2;
    else if(check(i, j, 2))
        return 3;
    else if(check(i, j , 3))
        return 4;
    else if(check(i, j , 4));
        return 5;
    
    return 0;
}

int main() {
    int n;
    cin >> n;

    while(n -- )
    {
        string s;
        int res = 0;
        int k = 1;
        for(int i = 1; i <= 10; i++)
        {
            cin >> s;
            for(int j = 0; j < 10; j++)
                if(s[j] == 'X')
                {
                    res += val(i, j + 1);
                }
            
        }
        cout << res << endl;
    }

    return 0;
}

Div.4 Round898 D Eraser

题目理解

问的是，每次可以把长度为k的区间里的B全变W，问最少多少次，可以把所有的字符都变成W。
那么我们只需要遇到B的时候用个标记，代表我们可以擦从这个B开始，最远多少的B即可。（双指针？）

代码实现

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <map>
#include <set>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;

const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;

ll qmi(ll a, ll b){
    ll res = 1;
    while(b)
    {
        if(b & 1) res = res * a % Mod;
        a = a * a % Mod;
        b >>= 1;
    }
    return res;
}

ll inv(ll x){ return qmi(x, Mod - 2);}
ll mo(ll x){ return (x % Mod + Mod) % Mod;}

int T;

int main() {
    cin >> T;

    while (T--)
    {
        int n, k;
        string s;
        cin >> n >> k >> s;
        int len = -1;
        int res = 0;
        for(int i = 0 ; i < n; i++)
            if(s[i] == 'B')
            {
                if(i > len)
                {
                    res ++;
                    len = i + k - 1;
                }
            }
        
        cout << res << endl;
    }
    

    return 0;
}

Div.4 Round898 E Building an Aquarium

题目理解

问我们把墙最少建多低，就可以灌水的体积为 >= k的体积。
这个题思路很好想，因为水只会填满高为墙的高度。

  • 所以我们可以按柱子高度排个序，然后用前缀和存一下前面的柱子的高度和。
  • 然后利用二分，查墙的高度。
  • 然后用lower_bound查，比这个墙高度低的有多少个
  • 然后 h * 个数 - 前面所有柱子的高度和就是可以填的体积

代码实现

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <map>
#include <set>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;

const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;

ll qmi(ll a, ll b)
{
    ll res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a % Mod;
        a = a * a % Mod;
        b >>= 1;
    }
    return res;
}

ll inv(ll x) { return qmi(x, Mod - 2); }
ll mo(ll x) { return (x % Mod + Mod) % Mod; }

ll T, n, k;
const int N = 2e5 + 10;
ll a[N], pre[N];

bool check(ll u)
{
    ll pos = lower_bound(a, a + n, u) - a;
    if (!pos)
    {
        return 1;
    }
    return (u * pos - pre[pos - 1]) <= k;
}

int main()
{

    cin >> T;

    while (T--)
    {
        cin >> n >> k;
        ll mx = 0;
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
            mx = max(mx, a[i]);
        }

        sort(a, a + n);

        for (int i = 0; i < n; i++)
            if (!i)
                pre[i] = a[i];
            else
                pre[i] = pre[i - 1] + a[i];

        ll l = 0, r = mx + k + 1;

        while (l < r)
        {
            ll mid = (l + r + 1) >> 1;
            if (check(mid))
                l = mid;
            else
                r = mid - 1;
        }

        cout << l << endl;
    }

    return 0;
}

Div.3 Round895 A Two Vessels

题目理解

经典倒水问题，直接做差向上取整就好了

代码实现

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;

const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;

ll qmi(ll a, ll b){
    ll res = 1;
    while(b)
    {
        if(b & 1) res = res * a % Mod;
        a = a * a % Mod;
        b >>= 1;
    }
    return res;
}

ll inv(ll x){ return qmi(x, Mod - 2);}
ll mo(ll x){ return (x % Mod + Mod) % Mod;}


int main() {

    int n;
    cin >> n;

    while(n -- )
    {
        int a, b, c;
        cin >> a >> b >> c;

        int div = abs(a - b);

        cout << ceil(1.0 * div / 2 / c) << endl;
    }

    return 0;
}

Div.3 Round895 B The Corridor or There and Back Again

题目理解

房间里面有陷阱，进去会触发，过s秒后，这个房间就不能进去了。我们需要从1号房间出发，再回到一号房间，给出了陷阱的位置和触发的时间。
我是用的二分，但是大佬好像可以直接枚举。。我二分的条件是，那个房间过s秒后，我是否可以回来，比如我走到了t位置，那么我从1到t，再从t到陷阱的房间，是否是在陷阱触发之前。

  • 如果在触发之前就过去了就没事
  • 如果出发了，还没过去就有事

代码实现

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;

const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;

ll qmi(ll a, ll b){
    ll res = 1;
    while(b)
    {
        if(b & 1) res = res * a % Mod;
        a = a * a % Mod;
        b >>= 1;
    }
    return res;
}

ll inv(ll x){ return qmi(x, Mod - 2);}
ll mo(ll x){ return (x % Mod + Mod) % Mod;}

const int N = 110;
int a[N], s[N];
int n, T;

bool check(int u)
{
    // 遍历n个陷阱
    for(int i = 1;  i <= n; i++)
        if(2 * u - a[i] >= a[i] + s[i])
            return false;

    return true;
}

void solve()
{
    cin >> n;
    int mx = INF, ms = INF;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i] >> s[i];
        if(a[i] <= mx)
        {
            mx = i;
            ms = s[i];
        }
    }

    int l = 1, r = 1e6;

    while(l < r)
    {
        int mid = (l + r + 1) >> 1;
        if(check(mid)) l = mid;
        else r = mid - 1;
    }

    cout << l << endl;
}

int main() {

    cin >> T;
    while(T--)
        solve();

    return 0;
}

Div.3 Round895 C Non-coprime Split

题目理解

找到两个数a和b，让

\[l <= a + b <= r \]

并且，gcd(a, b) != 1
所以我们在区间内，枚举i，然后枚举b，且一定是b * b <= i，不然会出现超界的情况。

代码实现

void solve()
{
    int l, r;
    cin >> l >> r;
    int a, b = -1;
    for(int i = l; i <= r; i++)
    {
        for(int j = 2; j * j <= i; j++)
        {
            if(i % j == 0)
            {
                b = j;
                a = i - b;
                break;
            }
        }
        if(b != -1) break;
    }

    if(b == -1 || a == 1 || b == 1) cout << -1 << endl;
    else cout << a << " " << b << endl;
}

Div.3 Round895 D Plus Minus Permutation

题目理解

  • 让x 的倍数位置放大数即n, n - 1, n - 2 ...
  • 让y 的倍数位置放小数即1, 2, 3 ...
  • 因为当x和y的最小公倍数，的倍数位置上是又要加又要减，等于没变。所以我们加的数量和减的数量，都减去最小公倍数的数量即可。

代码实现

ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

void solve()
{
    ll n, a, b;
    cin >> n >> a >> b;

    ll sum = 0;
    ll c = n / lcm(a, b);
    a = n / a - c;
    b = n / b - c;

    cout << ((n + n - a + 1) * a / 2) - ((1 + b) * b) / 2 << endl;

    return;
}

Div.3 Round900 A How Much Does Daytona Cost?

题目理解

说的是众数，其实只要出现过即可。因为是子段，自己也是自己的子段

代码实现

void solve()
{
    int n,m;
    cin >> n >> m;
    int flag = 0;
    for(int i = 1; i <= n; i++)
    {
        int b;
        cin >> b;
        if(b == m && flag == 0)
        {
            cout << "YES" << endl;
            flag = 1;
        }
    }

    if(!flag)
        cout << "NO" << endl;
    return;
}

Div.3 Round900 B Aleksa and Stack

题目理解

预处理出来符合条件的数组即可。

代码实现

void solve()
{
    int n;
    cin >> n;

    for(int i = 1; i <= n; i++)
        cout << a[i] << " ";
    
    cout << endl;


    return;
}

int main() {

    int T;
    cin >> T;
    a[1] = 2, a[2] = 3;
    int t = 4;
    for(int i = 3; i <= 2e5 + 4; i++)
    {
        if(t * 3 % (a[i - 1] + a[i - 2]) != 0)
        {
            a[i] = t;
            t++;
        }else{
            while(t * 3 % (a[i - 1] + a[i - 2]) == 0)
                t++;
            a[i] = t;
            t++;
        }
    }

    while(T--)
        solve();

    return 0;
}

Div.3 Round900 C Vasilije in Cacak

题目理解

问：在1 - n中选k个数可否组成m。
那么基础数论，前k个数求和是最小值，最后k个数求和是最大值。所以我们只需要：

  • 求和公式，求下上下界
  • 判断m是否在范围内即可

代码实现

void solve()
{

    ll n, m, k;
    cin >> n >> m >> k;

    ll l = (1 + m) * m / 2, r = (2 * n - m + 1) * m / 2;

    if(k >= l && k <= r)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;

    return;
}