histcat

Morning Basic Algorithms#

Search#

Introduction#

DFS BFS Iterative Deepening Bidirectional Search A*

Example Problem: K Shortest Paths Problem#

todo

Divide and Conquer#

Example Problem: Closest Pair of Points in a Plane#

todo

Greedy#

Example Problems#

1. [AHOI2018 Middle School Group] Grouping#

After sorting, consider where and how each number $i$ should be placed from front to back.

2. Deletion Problem#

Consider in reverse. Determine what digit can be filled in the $i$-th position of the answer sequentially.

3. [NOIP2012 Advanced Group] King's Game#

Assuming $S$ people are already arranged in front, consider how to arrange the next two people, extending to all.

Afternoon Simulation Contest#

T1 Beautiful Sequence#

Problem Statement#

Given a sequence $a$ of length $n$ and a positive integer $k$.

Little A thinks a sequence $a$ of length $m$ is beautiful if and only if the sum of every two adjacent numbers in this sequence is a multiple of $k$, that is, for all $i \in [1,m)$, it must satisfy $k\ |\ (a_i+a_{i+1})$.

Little A has a sequence $a$ of length $n$, and he wants to delete as few numbers as possible to make the remaining sequence beautiful.

You need to help him calculate the minimum number of numbers that need to be deleted.

Points to Consider#

Think in reverse, how many can be kept. Start from the conclusion to derive the properties of the conclusion.

Process#

First, it is easy to think that we can take each input number modulo $k$, which will not affect the result.

Then consider the properties of the result. If the first number is $x$, then the second number must be $k-x$, the third number must be $x$, and so on.

Thus, we scan the modulo array, considering each number (the number itself) $i$, the previous number must be $k-i$. Since we are looking for the length of the result, we use a map $f[x]$ (the value range is too large) to store the lengths of the subsequences that end with $k-x$ and satisfy the result properties (to put it simply, $i$ can be placed after this). Therefore, for $i$, its previous number is $k - i$, so $f[i] = f[k - i] + 1$, and we also check if we can update the answer $ans$.

The code is as follows:

#include<bits/stdc++.h>

using namespace std;

map<int, int> a;
int q[100010];

int main()
{
	int ans = 0;
	int n, k;
	cin >> n >> k;

	for(int i = 1;i <= n;i++)
	{
		cin >> q[i];
		q[i] %= k;
		ans = max(ans, ad = a[(k - q[i]) % k] + 1);
	}

	cout << n - ans;
	return 0;
}

T2 Simple Math Problem#

Problem Statement#

Little B loves math. One day, a friend of Little B told him two numbers $n,p$ and asked him how many pairs $(i,j)$ satisfy $1≤i,j≤n$ and $i \mod j ≤ p$.

Little B immediately understood, so he wanted to ask if you know this problem.

Points to Consider#

Avoid using long long, number theory block (todo).

Process#

todo

T3 Strange Stack#

Problem Statement#

Little C has a strange stack containing $n$ elements, each with three attributes $a_i,b_i,c_i$.

Each time, Little C will choose one element from the first and third elements at the top of the stack. Except for the first time, Little C will ensure that at least one of the $a_i$ or $b_i$ of the element taken out is the same as the last one taken out.

Little C wants to know how to take elements to maximize the sum of $c_i$ of the elements taken out.

Points to Consider#

todo

Process#

TODO

T4 Magical String#

Problem Statement#

Little B has a string $S$ of length $n$.

Little B thinks that a substring of this string $S$ is "magical" if and only if:

• The occurrence counts of all characters that appear in the substring are the same.

Little B wants to know how many substrings of $S$ are "magical".

In this problem, a substring of a string is defined as a continuous segment of that string.

Points to Consider#

todo

Process#

todo

Others#

Two sets of lecture notes, one assignment.