2023 ZZU ACM Recruitment Competition and Trial Supplementary Questions

Title

A.NANA and string

There are only two characters a and b in the string
Therefore, the substring with the same characters at the left and right ends must be the palindrome string defined in the title
Finding a palindrome string with an even length is equal to finding the number of substrings with the same characters at both ends but different parity
Finding a palindrome string with an odd length is equal to finding the number of strings with the same characters and parity at both ends
Count the different parities of different characters and then arrange and combine them
Note that a single character counts as a substring of odd length

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pb push_back

const int inf = 0x3f3f3f3f;
const long long llinf = (long long)0x3f3f3f3f3f3f3f3f;
const long long MOD = (long long)1e9 + 7LL;
const size_t N = (size_t)1e6 + 5;

#define IO \
    ios::sync_with_stdio(false); \
    std::cin. tie(0); \
    std::cout. tie(0)

#define debug(a) std::cerr << "\033[34m" << #a << ':' << a << "\033[0m" << std: :endl
#define testOut(a) std::cerr << "\033[32m" << a << "\033[0m" << std::endl

void solve() {<!-- -->
    string s;
    cin >> s;

    int a1 = 0, a2 = 0, b1 = 0, b2 = 0;
    for (int i = 0; i < s. size(); i ++ ) {<!-- -->
        a1 + = (s[i] == 'a' & amp; & amp; (i & amp; 1));
        a2 + = (s[i] == 'a' & amp; & amp; !(i & amp; 1));
        b1 + = (s[i] == 'b' & amp; & amp; (i & amp; 1));
        b2 + = (s[i] == 'b' & amp; & amp; !(i & amp; 1));
    }

    int ans = a1 * a2 + b1 * b2;
    cout << ans << ' ';

    ans = a1 * (a1 - 1) / 2 + a2 * (a2 - 1) / 2 + b1 * (b1 - 1) / 2 + b2 * (b2 - 1) / 2;
    cout << ans + s. size();
}

signed main() {<!-- -->
    IO;
    int T;
    T = 1;
    //cin >> T;
    while (T--) {<!-- -->
        solve();
    }
    return 0;
}

C.NANA goes to class

Think of the central core as 0, north as -1 to -5, and south as 1 to 5
Starting from 0, record the state after each walk
Calculate the distance to the next point
Finally add the absolute value of the state

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pb push_back

const int inf = 0x3f3f3f3f;
const long long llinf = (long long)0x3f3f3f3f3f3f3f3f;
const long long MOD = (long long)1e9 + 7LL;
const size_t N = (size_t)1e6 + 5;

#define IO \
    ios::sync_with_stdio(false); \
    std::cin. tie(0); \
    std::cout. tie(0)

#define debug(a) std::cerr << "\033[34m" << #a << ':' << a << "\033[0m" << std: :endl
#define testOut(a) std::cerr << "\033[32m" << a << "\033[0m" << std::endl

void solve() {<!-- -->
    int n;
    cin >> n;

    int st = 0, ans = 0;
    for (int i = 0; i < n; i ++ ) {<!-- -->
        char dir;
        int d;
        cin >> dir >> d;

        if (dir == 'N') {<!-- -->
            d = -d;
            ans + = abs(st - d);
            st = d;
        }
        else {<!-- -->
            ans + = abs(st - d);
            st = d;
        }
    }

    cout << ans + abs(st);
}

signed main() {<!-- -->
    IO;
    int T;
    T = 1;
    //cin >> T;
    while (T--) {<!-- -->
        solve();
    }
    return 0;
}

D.NANA at the night market

start bfs from end point
mark if reachable
Put the marked point into the queue
Judging whether the points around him can reach his position, and so on

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pb push_back

const int inf = 0x3f3f3f3f;
const long long llinf = (long long)0x3f3f3f3f3f3f3f3f;
const long long MOD = (long long)1e9 + 7LL;
const size_t N = (size_t)1e6 + 5;

#define IO \
    ios::sync_with_stdio(false); \
    std::cin. tie(0); \
    std::cout. tie(0)

#define debug(a) std::cerr << "\033[34m" << #a << ':' << a << "\033[0m" << std: :endl
#define testOut(a) std::cerr << "\033[32m" << a << "\033[0m" << std::endl

char mp[1010][1010];
bool f[1010][1010];
int dx[4] = {<!-- -->0, 0, 1, -1};
int dy[4] = {<!-- -->1, -1, 0, 0};

void solve() {<!-- -->
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) {<!-- -->
        cin >> mp[i];
    }

    queue<pair<int, int>> q;
    q.push({<!-- -->n - 1, m - 1});
    f[n - 1][m - 1] = true;
    int ans = 1;

    while (q. size()) {<!-- -->
        int x = q.front().first;
        int y = q.front().second;
        q. pop();

        for (int i = 0; i < 4; i ++ ) {<!-- -->
            int ax = x + dx[i];
            int ay = y + dy[i];
            if (ax < 0 || ax > n || ay < 0 || ay > m || f[ax][ay]) {<!-- -->
                continue;
            }
            if ((i == 0 & amp; & amp; mp[ax][ay] == 'L') || (i == 1 & amp; & amp; mp[ax][ay] == 'R') || (i == 2 & amp; & amp; mp[ax][ay] == 'U') ||(i == 3 & amp; & amp; mp[ax ][ay] == 'D')) {<!-- -->
                q.push({<!-- -->ax, ay});
                f[ax][ay] = true;
                ans + + ;
            }
        }
    }

    cout << ans;
}

signed main() {<!-- -->
    IO;
    int T;
    T = 1;
    //cin >> T;
    while (T--) {<!-- -->
        solve();
    }
    return 0;
}

Ranking of F.NANA

Find the lowest score of each person and store it in the corresponding position of the cnt array
Record the number of people for each score
Then use the suffix and query to get the ranking by the number of people whose scores are greater than v[i] + r[i]

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pb push_back

const int inf = 0x3f3f3f3f;
const long long llinf = (long long)0x3f3f3f3f3f3f3f3f;
const long long MOD = (long long)1e9 + 7LL;
const size_t N = (size_t)1e6 + 5;

#define IO \
    ios::sync_with_stdio(false); \
    std::cin. tie(0); \
    std::cout. tie(0)

#define debug(a) std::cerr << "\033[34m" << #a << ':' << a << "\033[0m" << std: :endl
#define testOut(a) std::cerr << "\033[32m" << a << "\033[0m" << std::endl

int l[N], r[N], v[N], cnt[610];

void solve() {<!-- -->
    int n;
    cin >> n;

    for (int i = 1; i <= n; i ++ ) {<!-- -->
        cin >> l[i] >> r[i];
v[i] = 0;

        for (int j = 0; j < 5; j ++ ) {<!-- -->
            int x;
            cin >> x;
            v[i] + = x;
        }

        cnt[v[i] + l[i]] + + ;
    }

    for (int i = 600; i >= 1; i--) {<!-- -->
        cnt[i] + = cnt[i + 1];
    }

    for (int i = 1; i <= n; i ++ ) {<!-- -->
        cout << cnt[v[i] + r[i] + 1] + 1 << endl;
    }
}

signed main() {<!-- -->
    IO;
    int T;
    T = 1;
    //cin >> T;
    while (T--) {<!-- -->
        solve();
    }
    return 0;
}

G.NANA watching the swan dance

Take the smaller value of black and white swans to form black and white pairs
Divide the rest by 2 times B
Subtract C if the number of geese is odd

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pb push_back

const int inf = 0x3f3f3f3f;
const long long llinf = (long long)0x3f3f3f3f3f3f3f3f;
const long long MOD = (long long)1e9 + 7LL;
const size_t N = (size_t)1e6 + 5;

#define IO \
    ios::sync_with_stdio(false); \
    std::cin. tie(0); \
    std::cout. tie(0)

#define debug(a) std::cerr << "\033[34m" << #a << ':' << a << "\033[0m" << std: :endl
#define testOut(a) std::cerr << "\033[32m" << a << "\033[0m" << std::endl

void solve() {<!-- -->
    int w, b, A, B, C;
    cin >> w >> b >> A >> B >> C;

    int ans = min(w, b) * A;
    ans + = (abs(w - b) / 2 * B);
    ans -= ((abs(w - b) & 1) * C);

    cout << ans;
}

signed main() {<!-- -->
    IO;
    int T;
    T = 1;
    //cin >> T;
    while (T--) {<!-- -->
        solve();
    }
    return 0;
}

I.NANA makes spicy soup

sliding window
Calculate the sum of unprocessed ingredients in the interval of length k each time
Update ans

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pb push_back

const int inf = 0x3f3f3f3f;
const long long llinf = (long long)0x3f3f3f3f3f3f3f3f;
const long long MOD = (long long)1e9 + 7LL;
const size_t N = (size_t)1e6 + 5;

#define IO \
    ios::sync_with_stdio(false); \
    std::cin. tie(0); \
    std::cout. tie(0)

#define debug(a) std::cerr << "\033[34m" << #a << ':' << a << "\033[0m" << std: :endl
#define testOut(a) std::cerr << "\033[32m" << a << "\033[0m" << std::endl

int a[N], f[N];

void solve() {<!-- -->
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i ++ ) {<!-- -->
        cin >> a[i];
    }
    for (int i = 0; i < n; i ++ ) {<!-- -->
        cin >> f[i];
    }

    int sum = 0;
    for (int i = 0; i < n; i ++ ) {<!-- -->
        if (f[i]) {<!-- -->
            sum + = a[i];
        }
    }
    for (int i = 0; i < k; i ++ ) {<!-- -->
        if (!f[i]) {<!-- -->
            sum + = a[i];
        }
    }

    int ans = sum;
    for (int i = k; i < n; i ++ ) {<!-- -->
        if (!f[i - k]) {<!-- -->
            sum -= a[i - k];
        }
        if(!f[i]) {<!-- -->
            sum + = a[i];
        }

        ans = max(sum, ans);
    }

    cout << ans;
}

signed main() {<!-- -->
    IO;
    int T;
    T = 1;
    //cin >> T;
    while (T--) {<!-- -->
        solve();
    }
    return 0;
}

J.NANA and her friends

double pointer
Sort the worth of n friends
Define l, r to point to the head and tail respectively
For the pointer l, if k is enough to do the addition so that the minimum value becomes the next value of the value pointed to by the pointer l, the value pointed to by l and all the previous values become the next value
The same is true for the pointer r
If k is not enough to reduce, reduce the difference between the maximum value and the minimum value as much as possible

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pb push_back

const int inf = 0x3f3f3f3f;
const long long llinf = (long long)0x3f3f3f3f3f3f3f3f;
const long long MOD = (long long)1e9 + 7LL;
const size_t N = (size_t)1e6 + 5;

#define IO \
    ios::sync_with_stdio(false); \
    std::cin. tie(0); \
    std::cout. tie(0)

#define debug(a) std::cerr << "\033[34m" << #a << ':' << a << "\033[0m" << std: :endl
#define testOut(a) std::cerr << "\033[32m" << a << "\033[0m" << std::endl

int a[N];

void solve() {<!-- -->
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i ++ ) {<!-- -->
        cin >> a[i];
    }

    sort(a, a + n);

    int l = 0, r = n - 1;
    while (l <= r) {<!-- -->
        if ((a[l + 1] - a[l]) * (l + 1) <= k) {<!-- -->
            k -= ((a[l + 1] - a[l]) * (l + 1));
            a[0] = a[l + 1];
            l + + ;
        }
        else {<!-- -->
            break;
        }
        if ((a[r] - a[r - 1]) * (n - r) <= k) {<!-- -->
            k -= ((a[r] - a[r - 1]) * (n - r));
            a[n - 1] = a[r - 1];
            r--;
        }
        else {<!-- -->
            break;
        }
    }
    int ans = a[n - 1] - a[0];

    if (l <= r) {<!-- -->
        ans -= (k / (n - r));
    }

    cout << ans;
}

signed main() {<!-- -->
    IO;
    int T;
    T = 1;
    //cin >> T;
    while (T--) {<!-- -->
        solve();
    }
    return 0;
}

K.NANA is in Zhengzhou

By meter

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pb push_back

const int inf = 0x3f3f3f3f;
const long long llinf = (long long)0x3f3f3f3f3f3f3f3f;
const long long MOD = (long long)1e9 + 7LL;
const size_t N = (size_t)1e6 + 5;

#define IO \
    ios::sync_with_stdio(false); \
    std::cin. tie(0); \
    std::cout. tie(0)

#define debug(a) std::cerr << "\033[34m" << #a << ':' << a << "\033[0m" << std: :endl
#define testOut(a) std::cerr << "\033[32m" << a << "\033[0m" << std::endl

int v[] = {<!-- -->1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 4 , 1, 2, 3, 1, 2, 3, 4};

void solve() {<!-- -->
    int n;
    cin >> n;

    int sum = 0;
    for (int i = 0; i < n; i ++ ) {<!-- -->
        string s;
        cin >> s;

        for (int j = 0; j < s. size(); j ++ ) {<!-- -->
            sum + = (v[s[j] - 'a']);
        }
    }

    cout << sum + n - 1;
}

signed main() {<!-- -->
    IO;
    int T;
    T = 1;
    //cin >> T;
    while (T--) {<!-- -->
        solve();
    }
    return 0;
}