Recent answers - column

Preface

Because there is not much time to make up questions at ordinary times , You may understand a problem for half an hour ,

However , Sometimes there are other things at hand , Just forget the reality ac& Blogging , So I googled out a question ,

For my current level , Figure out how to do （ Difficulty in thinking ） How to achieve ac It is more important , However, the latter is more time-consuming

So I'm going to open a hi column , It's like the transition state of filling a question ,

Write down the problem that you understand and solve here , Follow up whether or not to make up , There can also be a place to review

Collection of recent topics

Codeforces Round #808 (Div. 1)

This one came out of Changsha No.1 Middle School cf, The quality is still very high

A. Doremy's IQ（ greedy ）

n(n<=1e5) game , The first i Day difficulty ai(1<=ai<=1e9), Your initial IQ is q(1<=q<=1e9)

If your current IQ >0 You have the right to participate in the competition , Every day you can choose whether to participate in the competition ,

1. If you don't participate , Nothing happened

2. If you take part in , And ai>q, Then the current IQ q reduce 1,ai<=q Then nothing happens

It is required to participate in the largest number of competitions , Output this n God, your choice 01 strand

practice 1： If q>=n Obviously take all , Otherwise, the final IQ must be 0, and { The first i Less days 1, Later, it is reduced to 0, Some of the last ones are not selected } Obviously, it is not as good as { The first i Less days 1 The opportunity to move back , In this way, there may be more choices }, therefore , It can be divided into two days x, from x Choose every day from day one .

practice 2： If q>=n Obviously take all , Otherwise, the final IQ must be 0, Obviously, it's better for the chance of falling to happen later . Look at this process in reverse order , Think of the descending order as ascending in reverse order , Sequential no operation is considered as reverse order no operation , You can be greedy directly , Because the smaller the number of days, the higher the IQ .

B. Difference Array（ Property problem - violence ）

Long for n(n<=1e5) Non descending sequence of , The first i The values are ai, Construct a new array b,,

take b After array sorting , Record as new a Array , You can find a The length of 1, Repeat the process , until a There's only one element left

Finally a How many is this element , Specially ,

practice 1： Because the number of elements in the difference group is at the root level （ Consider the Fibonacci sequence ）, therefore , It can be used map Defend violently , At present (key,value) Show elements key There are several values for .key A difference element will be added adjacent to the value range , Make a difference with the same element , Only new 0 Elements .

practice 2： The order of violence , Only right and wrong 0 The elements are in descending order , When sorting, at most one 0, Same effect .

Proof of complexity ：

C. DFS Trees（ Property problem - The difference in the tree ）

n(n<=1e5) A little bit ,m(m<=2e5) Undirected graph of strip and edge , The first i The edge weight of a strip is i,

For each point , Execute the given function findMST(i), The output of the minimum spanning tree edge set can be obtained 1, Otherwise output 0,

vis := an array of length n
s := a set of edges

function dfs(u):
    vis[u] := true
    iterate through each edge (u, v) in the order from smallest to largest edge weight
        if vis[v] = false
            add edge (u, v) into the set (s)
            dfs(v)

function findMST(u):
    reset all elements of (vis) to false
    reset the edge set (s) to empty
    dfs(u)
    return the edge set (s)

The final output length is n String of

practice ： Because the border weights are different , therefore MST only , Consider building MST.

Conclusion ： if dfs There is no cross edge in the process , What we find out in this way is MST.

This problem is used here in undirected graph , It's a good property problem .

Tarjan review - poozhai - Blog Garden

By the tree ： The edge you want to keep .

Forward edge ： I found my son again .

Back to my ancestors ： I found my father again .

Cross edge ： I found my brother again .

Consider the figure given by the official solution ：

according to MST nature ,u-v Not taken , explain u-v Is the side with the largest weight on this ring ,

If from t/u/o/v Start searching ,u-v It's all atavism , Not taken ;

And from a/b/c/d/e/f Start searching ,u-v Are the first to be found side , Cause other edges on the ring to become cross edges , It doesn't fit the question

This shows that , For non MST On each side (u,v) Come on , Only two cases meet the meaning of the question ：

1. When v When it is root ,u This subtree

2. When u Root ,v This subtree

Other points are not in line with the meaning of the topic , Need to make a differential mark ：

1. if u and v It's the ancestral relationship , Need to be right u To v This chain and all the dot marks beside this chain

2. if u and v Not ancestral , Need right and wrong u subtree 、 Not v All point markers outside the subtree

	for(int i=1;i<=tp;++i){
		int u=es[i].v,v=es[i].nt;
		if(dp[u]>dp[v])u^=v^=u^=v;
		int w=lca(u,v);
		if(u==w){
			--vis[v];
			++vis[jump(v,dp[v]-dp[u]-1)];
		}
		else{
			++vis[root];
			--vis[u];
			--vis[v];
		}
	}

The problem solution is marked with subtrees , It's still good to write

AtCoder Beginner Contest 259

Ex. Yet Another Path Counting（ violence ）

n(n<=400) That's ok n The two-dimensional matrix of a column , The first i Xing di j There is a number listed aij(1<=aij<=n*n),

You can start from a grid , You can only go down one space or right one space at a time ,

Find the number of schemes with the same starting and ending numbers , The answer is right 998244353 modulus

practice ： Elegant violence

practice 1： Enumerate the same number pairs (x1,y1) and (x2,y2), Then calculate with combinatorial numbers （ Similar to Cartland number ,x Step by step y Step for right ）, The logarithm square of points is O(n^4)

practice 2： direct dp,dp[i][j] The starting point is (i,j) And left / upper , Now go to (i,j) Number of alternatives , Enumerate colors , Only mark with this color each time 1, Other color marks 0, Sum of final statistical schemes , The worst color is n^2 Level , Every time I traverse n^2,, by O(n^4)

Consider elegant violence , Same color number >n Current practice 2,<=n Current practice 1, It's down to O(n^3), It's really wonderful

AtCoder Beginner Contest 258

Ex. Odd Steps（ Matrix fast power optimization dp）

Find the sequence that satisfies the following conditions X Number of alternatives , The answer is right 998244353 modulus ：

1. Sequence X Every element in is an odd number

2. Sequence X The sum of the elements is exactly the given S

3. Given n Number a1,...,an,X This... Cannot appear in the prefix and sequence of n The number that has appeared in the number

The topic satisfies n<=1e5,1<=a1<...<an<S<=1e18

practice ： Matrix fast power optimization dp

Consider prefixes and sequences Y Only mapping out a sequence X, Consider plain prefixes and sequential dp Transfer ,

dp[i]=dp[i-1]+dp[i-3]+dp[i-5]+..., because dp[i-2]=dp[i-3]+dp[i-5]+...,, therefore dp[i]=dp[i-1]+dp[i-2],

Consider matrix fast power to maintain this value , But there are some values in the middle to ban Dropped , here dp[i] by 0, Does not conform to the formula ,

If dp[i] By ban 了 , Make it manually dp[i+1] and dp[i+2] Then continue to transfer , It feels difficult to write （ If dp[i+1] Also by ban What about it ）

therefore , Consider using dp Value and prefix and sum Two values , To maintain matrix fast power transfer ,

So even now dp The value is 0,sum Can also continue to transfer , Pair two adjacent elements at a time ai and ai+1 Fast exponentiation of matrices

Complexity O(k^3*n*log1e18),k take 2 or 3