Say something nonsense

The dog learning algorithm has also had a period of time, have to say, the algorithm of acwing class is very good, very to my appetite, there is a brief encounter, if you can meet in the university when! I must be a big shot now

Still can’t help but want to say 1: YXC cow force!!

Basic algorithm algorithm ideas and template code learning are seven seven eight eight, are basically knocked over (there are still dynamic return and greedy chapter did not finish learning)

Indeed, as Kong Ge (my college roommate) said, it is not enough to just watch the video class and write the questions by yourself. We still have to attend the weekly contest, which has a time limit and a more formal sense of ceremony. Therefore, this dog is going to start from this week, following the steps of Kong Ge, and start to participate in the algorithm week competition! And every week to digest the algorithm topic and sort out notes, so as to review and consolidate.

Participated in two weekly tournaments this week, Acwing and LeetCode. This is the notes of acwing’s weekly contest this week, as follows

The title

Acwing – 3770

Acwing-3770: Minimum consumption

You have n monsters to slay.

Monsters are divided into two forms, which can be represented by 0 and 1.

Killing a monster in form 0 costs a mana.

Killing a monster of form 1 costs b mana.

You can also use transformation magic to transform a 0 form monster into a 1 form or a 1 form monster into a 0 form.

It takes c mana to transform a monster.

What is the minimum mana required to destroy all monsters?

Answer key

Check in questions, do not examine any algorithm, direct simulation can be. 0 can either be destroyed directly (consuming a), or converted to 1 and then destroyed (consuming C +b). The minimum cost to destroy a 0 monster is min(a, C +b). Similarly, the minimum cost to destroy a 1 monster is min(b, C +a).

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

int get_min(int n, int a, int b, int c, string s) {
	int m_0 = min(a, c + b);
	int m_1 = min(b, c + a);
	int res = 0;
	for(int i = 0; i < s.size(); i++) {
		if(s[i] == '0') res += m_0;
		else res += m_1;
	}
	return res;
}

int main(a) {
	int m;
	scanf("%d", &m);
	while(m--) {
		int n, a, b, c;
		scanf("%d%d%d%d", &n, &a, &b, &c);
		string s;
		cin >> s;
		printf("%d\n", get_min(n, a, b, c, s));
	}
	return 0;
}
Copy the code

Acwing – 3771

Acwing-3771: Select stones

Given NNN stones, the numbers are 111 ~ NNN.

The value of the third pebble is aiA_iAI.

You need to pick any number of stones and place them in a row numbered from smallest to largest.

The selected stones must be sorted. For any two adjacent stones (for example, set their numbers as XXX and YYy), x−y= Ax − AYx-y = a_X-a_YX −y= AX − AY.

For example, when there is n = 8 n = n = 8 stones, stones value respectively,4,4,6,6,7,8,9 [3],4,4,6,6,7,8,9 [3],4,4,6,6,7,8,9 [3], some reasonable options are as follows:

  • Take stones 1, 2, 41, 2, 41, 2, and 4, and their values are 3,4,63,4,63,4,6. If stone No. 111 is adjacent to stone No. 222, 2−1=4−32-1=4-32−1=4−3 is true. If no. 222 stone is adjacent to No. 444 stone, 4−2=6−44-2=6-44−2=6−4 is true. So the plan is reasonable.
  • Choose pebble 777. If only one stone can be selected, any stone is a reasonable plan.

Not only do your choices need to be reasonable, but they also need to add up to the greatest possible value.

Calculate and output the maximum possible value for the sum of values.

Answer key

My solution: DFS bursts search

It seems that the correct answer will be found, but the Time Limit Exceeded will be reported

#include<iostream>
using namespace std;

typedef long long LL;

const int N = 1e6;

int a[N], n;
LL res = 0, ans = 0;

int path[N], ctn; // Store the points already included

// Each time we enumerate stones numbered x, we have two choices whether to include them or not
void dfs(int x) {
	if(x > n) return; // The search is over
	// Go to the next node
	dfs(x + 1);
	bool flag = false;
	// Try to include, check whether the inclusion is legal
	// There are already included stones
	if(ctn > 0) {
		int pre = path[ctn - 1]; // Get the current last pebble
		if(x - pre == a[x] - a[pre]) {
			// Meet the inclusion criteria
			path[ctn++] = x;
			res += a[x];
			flag = true;
		} else return; // Do not meet the inclusion criteria, direct pruning
	} else {
		// The current incorporated stones are 0, directly incorporated
		path[ctn++] = x;
		res += a[x];
		flag = true;
	}
	// Record the answers after inclusion
	ans = max(ans, res);

	dfs(x + 1); // Search for the next location

	// Resume the scene after the thorough search is completed
	if(flag) { ctn--; res -= a[x]; }}int main(a) {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	dfs(1);
	printf("%lld", ans);
	return 0;
}
Copy the code

Standard solution: hash

The x – y = ax – ayx – y = a_x – a_yx – y = ax – ay to transform, to ax – x = ay – ya_x – x = a_y – yax – x = ay – y, since such, for I ∈ I \ [1, n] in [1, n] I ∈ (1, n), Each stone III can calculate an additional attribute ai− Ia_i-iAI − I, let’s say that this attribute is sis_isi, then all stones with the same sis_ISI can form a scheme. For each value of sis_ISI, calculate the total value of the stones contained therein.

#include<iostream>
#include<unordered_map>
using namespace std;

typedef long long LL;

const int N = 1e6;

int a[N];

int main(a) {
    unordered_map<int,LL> res;
    int n;
    scanf("%d", &n);
    LL ans = 0;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        res[a[i] - i] += a[i]; // For the stones in a[I] -i group, add the values
        ans = max(ans, res[a[i] - i]); // Save the total value of the group with the highest value in real time
    }
    printf("%lld", ans);
    return 0;
}
Copy the code

Acwing – 3772

Acwing-3772: Update the line

Given a strongly connected graph of NNN points MMM bar edges.

The points are numbered from 111 to NNN, and the edges are all 111 in length.

Given a simple path from point SSS to point TTT p1, P2… ,pkp_1,p_2,… ,p_kp1,p2,… ,pk, p1= SP_1 = SP1 =s, PK = TP_k = TPK =t.

Note that this path is not necessarily the shortest path from point SSS to point TTT.

Now Ming is going to follow this path from point SSS to point TTT.

During his journey, the navigation software on his phone will continue to guide him and advise him on the shortest route to take.

Of course, he will not necessarily follow these suggestions, as he will certainly follow the route given before.

Imagine how navigation software works on the move.

First, at point SSS, the navigation software will find and display a shortest path from point SSS to point TTT.

If Xiao Ming’s route is exactly the same as the software recommended route, the software recommended route will not change.

However, if Ming is at a point where the route diverges from the software’s recommended route, for example, the software recommended point VVV, Ming goes to point WWW.

Then, after he arrives at point WWW, the software updates the recommended route in real time, finding and displaying a shortest path from point WWW to point TTT.

The navigation software will work until Ming arrives at TTT, and during this process, the software supply circuit may be updated several times.

For example, given a strongly directed connected graph, as follows:

The simple path for [1, 2, 3, 4] (s = 1, t = 4) [1, 2, 3, 4] (s = 1, t = 4) [1, 2, 3, 4] (s = 1, t = 4)

So, Ming starts from point 111, and the navigation software finds and displays a shortest path from point 111 to point 444, with only one path [1,5,4][1,5,4][1,5,4].

Xiaoming did not follow the advice of the software and insisted on reaching point 222. At this time, the software recommended route was updated in real time and provided a shortest path from point 222 to point 444, such as [2,6,4][2,6,4][2,6,4]

Note that the shortest path provided by the software may also be [2,3,4][2,3,4][2,3,4].

Still ignoring the software’s advice, Ming insisted on reaching point 333, at which point the software recommended route was updated again, providing a shortest path from point 333 to point 444, namely [3,4][3,4][3,4].

Finally, Xiao Ming provides a route along the software and arrives at the destination location 444. The software completes the navigation.

Overall, there have been two updates to the software recommendation circuit.

It is worth noting that if the shortest path given by the software is [2,3,4][2,3,4][2,3,4] when the software updates the recommended route for the first time, xiao Ming will follow the recommended route to the destination, and the software will not need to update the recommended route again.

In other words, because the software has randomness when recommending the shortest path, the number of recommended routes updated by the software is not certain during the whole process.

Now, given the directed graph and the path, find the minimum and maximum possible times of recommended paths for software updates.

According to the title, Xiao Ming will follow the given route p1, P2… ,pkp_1,p_2,… ,p_kp1,p2,… , the key is to solve each point along the way (P1, P2… , pk – 1 p_1, p_2,… ,p_{k-1}p1,p2,… , PK −1), to the end pkp_KPK, how many shortest. We consider whether the navigation route needs to be updated when Xiaoming takes a step from PIp_ipi to PI +1p_{I +1} PI +1.

  • When the edge from PIp_IPi to PI +1p_{I +1} PI +1 is not on a shortest path from PIp_IPi to pkp_kpk

    When Xiao Ming reaches PI +1p_{I +1} PI +1, the navigation route will be updated, so the minimum and maximum possible times of updating the route will be increased by 1.

    That is, all possible routes recommended by navigation must not contain the edge from PIp_IPi to PI +1p_{I +1} PI +1, so when Xiaoming goes to PI +1p_{I +1} PI +1, the route must be updated.

  • When pip_IPi goes to PI +1p_{I +1} PI +1, it is on a shortest path from PIp_IPi to pkp_kpK

    • When there is only one shortest path from PIp_IPi to PKp_kpk

      The shortest path must go through PI +1p_{I +1} PI +1. That is, when Xiaoming is located in PIp_IPi, there is only one shortest route recommended by navigation, that is, the route through PI +1p_{I +1} PI +1, so xiaoming will not be updated when he reaches PI +1p_{I +1} PI +1.

    • If there is more than one shortest path from PIp_IPi to PKp_kpK

      When Xiaoming is located at PIP_IPi, if the navigation recommended route happens to pass PI +1p_{I +1} PI +1, no update is required. If the recommended route does not go through PI +1p_{I +1} PI +1, you need to update it. That is, the minimum possible number is the same, and the maximum possible number is increased by 1.

From the discussion above, we know that the key is, for a point piP_IPI, we need to maintain the shortest number of piP_IPI to PKP_KPK.

Consider using BFS, but if we build a forward graph that starts with BFS at point P1p_1P1, then when extended to PIP_IPi, we can only get the shortest path from P1p_1P1 to PIP_IPi, and the shortest path from p1p_1P1 to PIp_IPi.

In the shortest path problem, we update the distance array according to the triangle inequality: DJ >di+1d_j \gt d_i + 1dj>di+1. Iii is the point PIp_IPi with the shortest distance from the starting point, and PJP_JPJ is the adjacent point of PIP_IPI. If djd_jdj ≥di+1d_j \ge d_i+1dj≥di+1 is used, then djd_jdj ≥di+1d_j \ge d_i+ 1DJ ≥di+1 needs to be updated. We think we found the shortest path from p1p_1P1 to PJP_JPJ. For the same JJJ, if the condition of DJ ≥di+1d_j \ge d_I + 1DJ ≥ DI +1 is encountered for many times, it indicates that there are multiple shortest circuits between point P1p_1P1 and point PJP_JPJ.

So we can count JJJ every time DJ ≥di+1d_j \ge d_I + 1DJ ≥di+1. The count represents the number of shortest paths from p1p_1P1 to PJP_JPJ. (My own code takes into account the case of heavy edges, which should not be counted twice when there are heavy edges.)

If you start BFS at p1p_1P1, you can only get the number of shortest paths from pJP_JPj to p1p_1P1. So in this case, we’re going to need the number of shortest paths from pJP_JPJ to pkp_kpk. So we consider building a reverse graph (which means we create an edge b→ab \rightarrow ab→a when the input data indicates that there is an edge a→ba \rightarrow ba→b) to facilitate BFS from the endpoint PKp_kpk.

The triangle inequality di≥ DJ +1d_i \ge d_j+ 1DI ≥ DJ +1 must be satisfied for every point PIp_IPi and point Pjp_JPj (assuming piP_IPi is in front of PJP_JPJ) on the shortest path after BFS is executed

So for xiaoming’s step from pip_IPi to PI +1p_{I +1} PI +1, we can use the triangle inequality to determine whether pip_ipi to PI +1p_{I +1} PI +1 is the shortest path

So, we have a clear idea, and the key point is that

  • To build a reverse figure
  • BFS starts at the destination, pkP_kpk, and additionally maintains the number of shortest paths from a point to PKP_kpk
  • Every time Xiaoming walks from PIp_ipi to PI +1p_{I +1} PI +1, we can determine whether this step is on the shortest path according to the triangle inequality

My solution:

#include<iostream>
#include<cstring>
using namespace std;

const int N = 2e5 + 10, M = N;

const int INF = 0x3f3f3f3f;

int h[N], e[N], ne[N], idx; // Graph adjacency list storage

int ctn[N]; // Store the number of shortest paths from a point I to k

int n, m, k;

int path[N]; // The given route

int d[N];

int q[N]; / / the queue

bool st[N]; // Used to prevent multiple counts of CTN in case of multiple edges

bool stt[N]; // Check whether a node is in queue Q

void add(int a, int b) {
	// adjacency list, head plug method
	e[idx] = b;
	ne[idx] = h[a];
	h[a] = idx++;
}

void bfs(a) {
	memset(d, 0x3f.sizeof d);
	d[path[k]] = 0;
	stt[path[k]] = true; // STT indicates whether to add to the queue
	int hh = 0, tt = - 1;
	q[++tt] = path[k]; / / team
	while(tt >= hh) {
		// When the queue is not empty
		int t = q[hh++]; / / out of the team
		stt[t] = false;
		memset(st, false.sizeof st); // To prevent double edges, add multiple CTNS
		// Iterate over all outgoing edges
		for(inti = h[t]; i ! =- 1; i = ne[i]) {
			int j = e[i];
			if(d[j] >= d[t] + 1) {
				// An update occurred
				d[j] = d[t] + 1;
				if(! st[j]) {// Add CTN when j point is not passed (prevent multiple CTN additions for multiple edges)
					ctn[j]++;
					st[j] = true;
				}
				if(! stt[j]) { q[++tt] = j;/ / team
					stt[j] = true;
				}
			}
		}
	}
}

int main(a) {
	memset(h, - 1.sizeof h);
	scanf("%d%d", &n, &m);
	while(m--) {
		int a, b;
		scanf("%d%d", &a, &b);
		add(b, a); // build the reverse edge
	}
	scanf("%d", &k);
	for(int i = 1; i <= k; i++) scanf("%d", &path[i]);
	bfs(); // Set up the database
	int min_c = 0, max_c = 0; // The minimum and maximum possible times to update the route
	// process
	for(int i = 1; i < k; i++) {
		int a = path[i], b = path[i + 1];
		// Check whether the line from I to I + 1 is shortest
		// BFS starts at k, so the point I + 1 is searched before I
		if(d[a] < d[b] + 1) {
			// The path from I to I + 1 is not on the shortest path
			min_c++;
			max_c++;
		} else {
			// I to I + 1 on the shortest path, let's see how many shortest paths there are
			if(ctn[a] > 1) {
				// The shortest path from I to k is greater than 1, i.e., not only from I to I + 1max_c++; }}}printf("%d %d\n", min_c, max_c);
	return 0;
}
Copy the code

Yxc standard solution:

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

using namespace std;

const int N = 200010, M = N;

int n, m;
int h[N], e[M], ne[M], idx;
int dist[N], cnt[N], q[N];
int path[N];

void add(int a, int b)  // Add an edge a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void bfs(int start)
{
    int hh = 0, tt = 0;
    memset(dist, 0x3f.sizeof dist);
    dist[start] = 0;
    q[0] = start;

    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + 1)
            {
                dist[j] = dist[t] + 1;
                cnt[j] = 1;
                q[ ++ tt] = j;
            }
            else if (dist[j] == dist[t] + 1) cnt[j] ++ ; }}}int main(a)
{
    scanf("%d%d", &n, &m);
    memset(h, - 1.sizeof h);
    while (m -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(b, a);
    }

    int k;
    scanf("%d", &k);
    for (int i = 1; i <= k; i ++ ) scanf("%d", &path[i]);
    bfs(path[k]);

    int minc = 0, maxc = 0;
    for (int i = 1; i < k; i ++ )
    {
        int a = path[i], b = path[i + 1];
        if (dist[a] < dist[b] + 1) minc ++, maxc ++ ;
        else if (cnt[a] > 1) maxc ++ ;
    }

    printf("%d %d\n", minc, maxc);
    return 0;
}
Copy the code

This week is the first time to participate in the weekly tournament, the situation is not very ideal. Acwing has 3 questions, only the first one, the second one did not think of using hash.

There are 4 leetcodes in total, only the first 2 have been made, and the last two leetcodes have not been digested, notes are still being sorted out….

(after)