catalogue

A. Square sequence

B. Prime number splitting

D. Evaluation

E. Path count

F. Optimal inclusion

G. Permutation number

H. Puzzle game

1. The eighth miracle

A. Square sequence

Topic analysis:

Y < y, y < y, y < y -  ==  - (judgment condition of arithmetic sequence) then record x+y = minimum value, and finally output the value

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    int x = 0, y = 0;
    int sum = 0x3f3f3f3f;
    for(int i = 2019 + 1; i <= 10000 ; i ++)
        for(int j = i + 1; j <= 10000; j ++)
        {
            if(i * i - 2019 * 2019 == j * j - i * i)
                sum = min(i + j, sum);
        }
    
    cout << sum << endl;
    return 0;
}

Answer: 7020

B. Prime number splitting

Topic analysis:

Meaning: find the number of schemes divided into the sum of several different prime numbers

Analysis: we can first find all prime numbers from 1-2019 and convert the problem into all schemes with a sum of 2019 from the prime numbers from 1-2019. Is it like 01 backpack at this time.

01 backpack dynamic planning:

State representation: the number of sets selected from the previous i prime numbers and the sum is j (quantity is the attribute of state representation)

State calculation: for f [i, j], its transfer scheme is transferred from f [i - 1, j] (the ith prime is not selected) and f [i - 1, j - prime[i]] (the ith prime is selected), so f [i, j] = f [i - 1, j] + f[i - 1, j - prime[i]]

#include <iostream>
#include <cstring>

using namespace std;

const int N = 5000;

typedef long long LL;

int prime[N];
int idx = 1;
LL f[N][N];
bool st[N];

void get_primes(int x) //Linear sieve prime number
{
    for(int i = 2; i <= x; i ++)
    {
        if(!st[i])  prime[idx ++] = i;
        for(int j = 1; prime[j] <= x / i; j ++)
        {
            st[prime[j] * i] = true;
            if(i % prime[j] == 0)   break;
        }
    }
}

int main()
{
    get_primes(2019);
    f[0][0] = 1;
    for(int i = 1; i < idx; i ++)
        for(int j = 0; j <= 2019; j ++)
        {
            f[i][j] = f[i - 1][j];
            if(prime[i] <= j)   f[i][j] += f[i - 1][j - prime[i]]; //It can also be converted to one dimension, but it is not necessary in this problem.
        }
    
    cout << f[idx - 1][2019] << endl;
    return 0;
}

Answer: 55965365465060

D. evaluation

Topic analysis:

We can enumerate from 1 to the first number that satisfies the divisor of 100, and then output the number.

#include <iostream>
#include <cstring>

using namespace std;

int main()
{
    for(int i = 100; i; i ++)
    {
        int cnt = 0;
        int temp = i;
        for(int j = 1; j <= temp / j; j ++)
        {
            if(temp % j == 0)
            {
                if(j == temp / j) //Pay attention to the special judgment j == temp / j. at this time, the approximate number will only be + 1
                    cnt ++;
                else
                    cnt += 2;
            }
        }
        if(cnt == 100)
        {
            cout << i << endl;
            return 0;
        }
    }
}

Answer: 45360

E. Path count

Topic analysis:

Meaning of the question: the number of schemes starting from (1,1) and ending at (1,1) in the 5X5 square matrix, and the number of each scheme should meet the meaning of the question

Considering that the side length is 5, we can consider dfs violent search

Select the value we want to record according to each condition:

1. The total length is no more than 12. Use step to record our steps

2. Return to the lower left corner: judge x==1? y==1?

3. Route non self intersection: use st array to record whether the line segment has been passed before this search (Note: restore the original state to ensure the correctness of the next search)

4. No crossing: add judgment conditions

#include <iostream>
#include <cstring>

using namespace std;

const int N = 10;

bool st[N][N];
int ans;
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

void dfs(int x, int y, int step)
{
    if(step <= 12 && step > 2 && st[x][y])
    {
        if(x == 1 && y == 1)
        {
            ans ++;
        }
    }
    if(step > 12)
        return ;
    for(int i = 0; i < 4; i ++)
    {
        int nx = x + dx[i], ny = y + dy[i];
        if(nx < 1 || nx > 6 || ny < 1 || ny > 6)
            continue;
        if(st[nx][ny])
            continue;
        st[nx][ny] = true;
        dfs(nx, ny, step + 1);
        st[nx][ny] = false; //State recovery process
    }
}

int main()
{
    dfs(1, 1, 0);
    cout << ans << endl;
}

Answer: 206

F. Optimal inclusion

Topic analysis:

Given two strings S and T, find at least how many strings in s can be modified and then become t by extracting several characters

Analysis: this topic is a simplified version of the classic topic "editing distance"

We can think of it as follows: for the S character, we have two operations, delete Si and modify Si. The costs are 0 and 1 respectively. Find the minimum cost of matching S with T

Dynamic planning:

Status representation: f [i, J]: the first i characters of S are equal to the minimum operand of the first j characters of T

Considering all states that can be transferred to f[i, j], f[i, j] can only be transferred from deleting the ith character of S, modifying the ith character of S and doing nothing

For deleting the ith character of S, the transferred f [i, j]: F [i, j] = f [i - 1, j] + 0 (the cost of deleting is 0)

For modifying the ith character of S, f [i, j]: F [i, j] = f [i - 1, j - 1] + 1 (the cost of modification operation is 1)

For f[i, j] transferred without any operation: f[i, j] = f[i - 1, j - 1]

We can combine modification and no operation into one category. The code is as follows

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010;

int n, m;
int f[N][N];
char a[N];
char b[N];

int main()
{
    cin >> a + 1 >> b + 1;
    n = strlen(a + 1);
    m = strlen(b + 1);
    memset(f, 0x3f, sizeof f); //The attribute in the state representation is the minimum value, so we need to initialize to positive infinity
    for(int i = 1; i <= n; i ++)    f[i][0] = 0; //Indicates the cost of matching the first i - 1 character from Si to T before deletion
    f[0][0] = 0; //Matching operands not started
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
        {
            int temp = 0;
            if(a[i] == b[j])    temp = 0; //If temp is 0, the state of no operation is transferred
            else    temp = 1; //Cost of modification operation
            f[i][j] = min(f[i - 1][j], f[i - 1][j - 1] + temp);
        }
    cout << f[n][m] << endl;
    return 0;
}

G. Permutation number

Topic analysis:

Given n, k, let's find the number of k - 1 peaks or valleys (peaks: the number is larger than the next two numbers, valleys: the number is smaller than the next two numbers) in the full arrangement with the number of elements n, 1 - n

analysis:

I didn't write this question out, so I can refer to it AcWing 2554. Permutation number $o (n ^ 2K) $DP (may be better understood) - acwing Solution to the problem

Dynamic planning:

Let f [i, j, k, 0 / 1] represent all sets in which the last two numbers of the k-monotone sequence with the first i - 1 number arranged and the last number j are increasing or decreasing

Considering the transfer from f[i - 1][r][k][0 / 1], r is divided into the following cases:

If R < Jr < J
Then, after we fill j in the arrangement, the last two numbers increase. Then consider whether the last two numbers in the original arrangement increase.
1. If it increases, the number of folding points will not increase after j is put in, then there is f[i][j][k][1] += f[i - 1][r][k][1]
2. If it decreases, the number of folding points will increase after j is put in, then f[i][j][k][1] += f[i - 1][r][k - 1][0]
If r ≥ jr ≥ j
Then, after we fill j in the permutation, the last two numbers decrease. Then consider whether the last two numbers in the original arrangement increase.
1. If it increases, the number of folding points will increase after j is put in, then f[i][j][k][0] += f[i - 1][r][k - 1][1]
2. If it decreases, the number of fold points will not increase after j is put in, then there is f[i][j][k][0] += f[i - 1][r][k][0]

Finally, maintain f[i][r][k][0/1] with prefix and array S

#include <cstdio>
#include <cstring>

const int N = 505;
const int mod = 123456;

int n, m;
int f[2][N][N][2];
int s[2][N][N][2];

int main()
{
    scanf("%d%d", &n, &m);

    f[1][1][1][0] = 1;
    f[0][1][1][0] = f[0][2][1][1] = 1;
    s[0][1][1][0] = s[0][2][1][0] = s[0][2][1][1] = 1;
    for (int i = 3; i <= n; i ++ )
    {
        memset(f[i & 1], 0, sizeof f[0]);
        memset(s[i & 1], 0, sizeof s[0]);
        for (int j = 1; j <= i; j ++ )
            for (int k = 1; k <= i && k <= m; k ++ )
            {
                (f[i & 1][j][k][1] += s[i - 1 & 1][j - 1][k][1] + s[i - 1 & 1][j - 1][k - 1][0]) %= mod;
                (f[i & 1][j][k][0] += s[i - 1 & 1][i - 1][k][0] - s[i - 1 & 1][j - 1][k][0]) %= mod;
                (f[i & 1][j][k][0] += s[i - 1 & 1][i - 1][k - 1][1] - s[i - 1 & 1][j - 1][k - 1][1]) %= mod;
                s[i & 1][j][k][0] = (s[i & 1][j - 1][k][0] + f[i & 1][j][k][0]) % mod;
                s[i & 1][j][k][1] = (s[i & 1][j - 1][k][1] + f[i & 1][j][k][1]) % mod;
            }
    }

    printf("%d\n", ((s[n & 1][n][m][0] + s[n & 1][n][m][1]) % mod + mod) % mod);

    return 0;
}

H. Puzzle game

Topic analysis

Given an outer ring, middle ring and inner ring, we can rotate the outer, middle and inner rings clockwise and counterclockwise at the same time. We can also make a circular movement in the inner and outer directions of the lamp tube with the position of 0 in the three circles. Ask whether we can make all green move to the outer ring, all red move to the middle ring and all yellow move to the inner ring.

Analysis: we can find that no matter how we rotate, the points we exchange will be the points with the same value of the subscript% 4 of the circle, so we can judge that for the points composed of these subscripts, green = = 3? Red = = 2? Yellow = = 1? If satisfied, we can make all green move to the outer circle, all red move to the middle circle and yellow move to the inner circle in a limited number of rotation and exchange operations

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int t;
string a, b, c;

int cnt[4][3];

void add(string a)
{
    for(int i = 0; i < a.size(); i ++)
    {
        if(a[i] == 'G')
            cnt[i % 4][0] ++;
        else if(a[i] == 'R')
            cnt[i % 4][1] ++;
        else
            cnt[i % 4][2] ++;
    }
}

int main()
{
    cin >> t;
    while(t --)
    {
        cin >> a >> b >> c;
        bool is_total = true;
        memset(cnt, 0, sizeof cnt);
        add(a), add(b), add(c);
        for(int i = 0; i < 4; i ++)
        {
            //Green moves to the outer ring, all red moves to the middle ring, and all yellow moves to the inner ring
            if(cnt[i][0] != 3 || cnt[i][1] != 2 || cnt[i][2] != 1)
            {
                is_total = false;
                break;
            }
        }
        if(is_total)    cout << "YES" << endl;
        else    cout << "NO" << endl;
    }
    return 0;
}

1. The eighth miracle

Topic analysis:

(I've been learning line segment tree recently, so I can practice with this problem)

analysis:

For this single point modification, the problem of interval query is easy to associate with tree array and line segment tree. We can easily find that tree array is difficult to maintain our query operation.

So we use segment tree to solve this problem

For the segment tree, we need to consider what values need to be maintained to ensure the correctness of the answer.

l. r is positive. We also need to maintain an array with a length of 8 to store the eighth largest number in the interval

Moreover, for this problem, we can find that we do not need to use lazy tags to update the value of the parent node to the value of the child node, but only need to push up the value of the child node to update the parent node.

The code is as follows

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int N = 100010;

struct Node
{
    int l, r;
    int v[8];
}tr[4 * N];

int n, m;

void build(int u, int l, int r)
{
    if(l == r)  tr[u] = {l, r};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    }
}

void pushup(Node &t, Node &l, Node &r)
{
    int i = 0, j = 0, k = 0;
    while(i < 8 && j < 8 && k < 8)
    {
        if(l.v[i] < r.v[j]) t.v[k ++] = r.v[j ++];
        else    t.v[k ++] = l.v[i ++];
    }
    if(k < 8 && j < 8)  t.v[k ++] = r.v[j ++];
    if(k < 8 && i < 8)  t.v[k ++] = l.v[i ++];
}

void modify(int u, int x, int c)
{
    if(tr[u].l == x && tr[u].r == x)    tr[u].v[0] = c;
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if(mid >= x)    modify(u << 1, x, c);
        else    modify(u << 1 | 1, x, c);
        pushup(tr[u], tr[u << 1], tr[u << 1 | 1]); 
    }
}

Node query(int u, int l, int r)
{
    if(tr[u].l >= l && tr[u].r <= r)    return tr[u];
    int mid = tr[u].l + tr[u].r >> 1;
    if(mid >= r)    return query(u << 1, l, r);
    else if(mid < l)   return query(u << 1 | 1, l, r); 
    else
    {
        Node ans;
        auto left = query(u << 1, l, r);
        auto right = query(u << 1 | 1, l, r);
        pushup(ans, left, right);
        return ans;
    }
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    build(1, 1, n);
    while(m --)
    {
        char op[2];
        int l, r;
        cin >> op >> l >> r;
        if(*op == 'C')
        {
            modify(1, l, r);
        }
        else
        {
            cout << query(1, l, r).v[7] << endl;
        }
    }
    return 0;

}

Finally, share the draft of analysis: