Codeworks round 797 (Div. 3, cf1690)

It seems that such a set of water problems is meaningless to the gods , The notes of Underachievers

Portal

author ：hans774882968 as well as hans774882968

this paper CSDN link

this paper juejin link

A

Estimate the lower bound of the maximum n/3+1, Directly enumerating the maximum value can pass ：

        read (n);
        int v1, v2, v3;
        rep (i, n / 3 + 1, n) {
    
            if ( (n - i) % 2) v1 = (n - i) / 2, v2 = v1 + 1;
            else v1 = (n - i) / 2 - 1, v2 = v1 + 2;
            if (v1 < v2 && v2 < i) {
    
                v3 = i;
                break;
            }
        }
        printf ("%d %d %d\n", v2, v3, v1);

But enter n = 6 7 8 9 ... It can be found that the maximum value is a formula that can be written directly (n - 1) / 3 + 2, So we can further optimize ：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)

const int N = 2e5 + 5;

int n;

void dbg() {
    
    puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {
    
    cout << f << " ";
    dbg (r...);
}
template<typename Type>inline void read (Type &xx) {
    
    Type f = 1;
    char ch;
    xx = 0;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
    xx *= f;
}
void read() {
    }
template<typename T, typename ...R>void read (T &x, R &...r) {
    
    read (x);
    read (r...);
}

int main() {
    
    int T;
    read (T);
    while (T--) {
    
        read (n);
        int v1, v2, v3 = (n - 1) / 3 + 2;
        if ( (n - v3) % 2) v1 = (n - v3) / 2, v2 = v1 + 1;
        else v1 = (n - v3) / 2 - 1, v2 = v1 + 2;
        printf ("%d %d %d\n", v2, v3, v1);
    }
    return 0;
}

B

branch b[i] Equal to and not equal to 0 Discuss .

• about b[i]≠0 Of i, requirement a[i]-b[i] identical , Set to x.
• For others i, requirement max(a[i]) <= x.

use set It is most convenient to realize .

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)

const int N = 2e5 + 5;

int n, a[N], b[N];

void dbg() {
    
    puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {
    
    cout << f << " ";
    dbg (r...);
}
template<typename Type>inline void read (Type &xx) {
    
    Type f = 1;
    char ch;
    xx = 0;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
    xx *= f;
}
void read() {
    }
template<typename T, typename ...R>void read (T &x, R &...r) {
    
    read (x);
    read (r...);
}

bool jdg() {
    
    set<int> s1, s2;
    rep (i, 1, n) {
    
        if (b[i]) s1.insert (a[i] - b[i]);
        else s2.insert (a[i]);
    }
    if (s1.size() > 1) return false;
    if (s1.size() == 1 && *s1.begin() < 0) return false;
    if (s1.size() == 1 && s2.size() && *s1.begin() < *s2.rbegin() ) return false;
    return true;
}

int main() {
    
    int T;
    read (T);
    while (T--) {
    
        read (n);
        rep (i, 1, n) read (a[i]);
        rep (i, 1, n) read (b[i]);
        puts (jdg() ? "YES" : "NO");
    }
    return 0;
}

C

Just ask for the actual start time , The expression is easy to write from the sample .

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)

const int N = 2e5 + 5;

int n, a[N], b[N];

void dbg() {
    
    puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {
    
    cout << f << " ";
    dbg (r...);
}
template<typename Type>inline void read (Type &xx) {
    
    Type f = 1;
    char ch;
    xx = 0;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
    xx *= f;
}
void read() {
    }
template<typename T, typename ...R>void read (T &x, R &...r) {
    
    read (x);
    read (r...);
}

int main() {
    
    int T;
    read (T);
    while (T--) {
    
        read (n);
        rep (i, 1, n) read (a[i]);
        rep (i, 1, n) read (b[i]);
        rep (i, 1, n) printf ("%d%c", b[i] - max (b[i - 1], a[i]), " \n"[i == n]);
    }
    return 0;
}

D

Directly enumerate a k The range of , Look how many are inside W that will do . Use prefixes and statistics W Number .

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)

const int N = 2e5 + 5;

int n, a[N], k;
char s[N];

void dbg() {
    
    puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {
    
    cout << f << " ";
    dbg (r...);
}
template<typename Type>inline void read (Type &xx) {
    
    Type f = 1;
    char ch;
    xx = 0;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
    xx *= f;
}
void read() {
    }
template<typename T, typename ...R>void read (T &x, R &...r) {
    
    read (x);
    read (r...);
}

int main() {
    
    int T;
    read (T);
    while (T--) {
    
        read (n, k);
        scanf ("%s", s + 1);
        rep (i, 1, n) a[i] = a[i - 1] + (s[i] == 'W');
        int ans = n;
        rep (i, k, n) ans = min (ans, a[i] - a[i - k]);
        printf ("%d\n", ans);
    }
    return 0;
}

E

For the formula with fixed value doping , It is always recommended to try to extract the constant value first , Further analysis .—— Fertile · Zigishoud

(a + b) / k = a / k + b / k + (a % k + b % k) / k, This is the fixed value a / k and b / k It's extracted , We only need to consider a % k + b % k >= k Is it true .

This is a classic greedy problem , It seems to be against the background of crossing the river ？ Greedy strategy ： Prioritize , Then try to set the current minimum value a[i] Match a minimum value that satisfies the condition . If the match fails, discard a[i], Success leads to a pair of . use multiset To match .

Another way is to sort + Double pointer , That is, directly take the existing maximum value to match the current minimum value . This practice can also AC, But I don't know its correctness .

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)

const int N = 2e5 + 5;

int n, k, a[N];

void dbg() {
    
    puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {
    
    cout << f << " ";
    dbg (r...);
}
template<typename Type>inline void read (Type &xx) {
    
    Type f = 1;
    char ch;
    xx = 0;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
    xx *= f;
}
void read() {
    }
template<typename T, typename ...R>void read (T &x, R &...r) {
    
    read (x);
    read (r...);
}

int main() {
    
    int T;
    read (T);
    while (T--) {
    
        read (n, k);
        rep (i, 1, n) read (a[i]);
        LL ans = 0;
        rep (i, 1, n) ans += a[i] / k, a[i] %= k;
        sort (a + 1, a + n + 1);
        multiset<int> st;
        rep (i, 1, n) st.insert (a[i]);
        rep (i, 1, n) {
    
            if (!st.size() ) break;
            if (!st.count (a[i]) ) continue;
            st.erase (st.find (a[i]) );
            auto it = st.lower_bound (k - a[i]);
            if (it == st.end() ) continue;
            st.erase (it);
            ++ans;
        }
        printf ("%lld\n", ans);
    }
    return 0;
}

F

Pre cheese ： A permutation can be written as the product of several cycles . Such as input data 8 6 1 7 5 2 9 3 10 4 It's written in (1 8 3) (2 6) (4 7 9 10) (5). The order of a permutation is equal to the order of all its cycles lcm, It's intuitive and easy to understand .

For cycles (a[1] a[2] ... a[x]), Take out the string t = s[a[1]]s[a[2]]...s[a[x]], Then one transformation means moving the first character to the end . So we construct a t + t,t The number of times to change back to the original string is equal to (t + t).find(t, 1), among find yes cpp Of string Function of , The second parameter indicates the subscript from which to start the matching substring .

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)

const int N = 2e2 + 5;

int n, p[N];
bool vis[N];

void dbg() {
    
    puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {
    
    cout << f << " ";
    dbg (r...);
}
template<typename Type>inline void read (Type &xx) {
    
    Type f = 1;
    char ch;
    xx = 0;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
    xx *= f;
}
void read() {
    }
template<typename T, typename ...R>void read (T &x, R &...r) {
    
    read (x);
    read (r...);
}

LL gcd (LL a, LL b) {
    
    return b ? gcd (b, a % b) : a;
}

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

int main() {
    
    int T;
    read (T);
    while (T--) {
    
        memset (vis, 0, sizeof vis);
        read (n);
        string s;
        cin >> s;
        re_ (i, 0, n) read (p[i]), p[i]--;
        LL ans = 1;
        re_ (i, 0, n) {
    
            if (vis[i]) continue;
            vis[i] = true;
            int u = p[i];
            string t = string (1, s[i]);
            while (u != i) {
    
                vis[u] = true;
                t += s[u];
                u = p[u];
            }
            int cnt = (t + t).find (t, 1);
            ans = lcm (ans, cnt);
        }
        printf ("%lld\n", ans);
    }
    return 0;
}

G

Take an example 10 13 5 2 6 For example . First, find out all the formed intervals [1, 2] [3, 3] [4, 5]. if a[2] -= 3, Because it is greater than or equal to the value of this interval , So there is no interval splitting . if a[2] -= 8, Because it is smaller than the value of this interval , Therefore, interval splitting is required , namely idx = 2 Become the new left end point of the interval , Then we need to find the right endpoint of the new interval , That is, perform interval consolidation ,[3, 3] Was merged into . If a[2] Smaller , become a[2] <= 2, be [3, 3] [4, 5] Will be merged .

From the above example, it is found that , It is necessary to split and merge intervals . When merging, you should traverse until the value of the candidate interval is strictly less than the value of the newly generated interval . Because there is no gap between the sections , So we just need a value to represent , For example, the above example is 1 3 4. At this point, we can sort out the operations we need ：

• Interval splitting , Insert a value .
• Interval merging , That is, delete several values .
• Find the maximum less than or equal to k Value .

These operations only need set.

Time complexity ：O((n + m)logn).

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define rep(i,a,b) for(int i = (a);i <= (b);++i)
#define re_(i,a,b) for(int i = (a);i < (b);++i)
#define dwn(i,a,b) for(int i = (a);i >= (b);--i)

const int N = 2e5 + 5;

int n, m, a[N];

void dbg() {
    
    puts ("");
}
template<typename T, typename... R>void dbg (const T &f, const R &... r) {
    
    cout << f << " ";
    dbg (r...);
}
template<typename Type>inline void read (Type &xx) {
    
    Type f = 1;
    char ch;
    xx = 0;
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar() ) if (ch == '-') f = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar() ) xx = xx * 10 + ch - '0';
    xx *= f;
}
void read() {
    }
template<typename T, typename ...R>void read (T &x, R &...r) {
    
    read (x);
    read (r...);
}

int main() {
    
    int T;
    read (T);
    while (T--) {
    
        read (n, m);
        rep (i, 1, n) read (a[i]);
        set<int> s;
        for (int mn = INT_MAX, i = 1; i <= n; ++i) {
    
            if (mn > a[i]) s.insert (i);
            mn = min (mn, a[i]);
        }
        while (m--) {
    
            int k, d;
            read (k, d);
            a[k] -= d;
            auto it = --s.upper_bound (k);
            auto it_tmp = it;
            for (++it; it != s.end() && a[*it] >= a[k]; it = s.erase (it) );
            if (a[*it_tmp] > a[k]) s.insert (k);
            // for (int v : s) cout << v << ",";
            // puts (""); //
            printf ("%d%c", s.size(), " \n"[m == 0]);
        }
    }
    return 0;
}