1.21 learning summary

Today is also to make up the problem . Then what I want to review is that I have done a problem about greedy algorithm . At that time, this problem was not worked out for a long time . I haven't understood the topic . So I want to review again .

The title is as follows .

   When I was doing this problem , Just a confused face .  Mainly because I didn't understand , This is a line .  It is equivalent to marking a one-dimensional array , Where can I go ,  The most incomprehensible thing at that time was that k. Only later , So that can . It's a counter . From the beginning to n.  The title is not clear , I didn't understand it at that time .  Then understand the meaning of the topic , This topic is equivalent to marking yourself . Then some subscripts can go , Some subscripts don't go . Then walk a certain number of steps apart .  Under serious circumstances , The first time is to traverse directly . But obviously . This question . It can't be that simple .  Because the data he gave was very large . So we need to use a little greedy algorithm .  That is, a little mathematical induction .  Because every step of frog jumping is fixed . So if the Frog   You can reach a plank .  Then the position where he jumps out of the board is fixed .  Because he started from scratch .   And we have the position of the final point of the board .  That is, the edge of the board .  In this case . Through a formula .  Count the steps before the frog jumps out of the plank .  That is to say, the coordinates of this board   Divide by the number of steps and get the remainder .  In this case . This remainder . Subtract steps ,  Then add the edge of the board .  That's where he jumped out of the plank , If this position is smaller than the front of the second board   You can end the loop .  This is the idea of this topic .  It's easy to say ,  But we still need to think about .  Generally speaking , It is a test of your inductive thinking about mathematics .

The code is as follows ,

  #include<stdio.h>
 
 int main()
 {
 	long long n,d,m,l,ans,i;
  scanf("%lld%lld%lld%lld",&n,&d,&m,&l);
 	ans=0;
 	for(i=1;i<=n;i++) {
 		if(ans<((i-1)*m)) break;
 		while(ans<=(i-1)*m+l){  
 		ans=d-(((i-1)*m+l)%d)+(i-1)*m+l;
		 }
		 
 	}
  printf("%lld",ans);
 	return 0;
 }

The other topic I want to talk about is the topic of union search .  The interesting thing about this topic .  It is a knapsack and a parallel search set . Combined topics . 

The title is as follows . 

   On this one . The title says that to buy one, you should match it up and buy it all   And there is continuity . It's easy to think of and search sets .  Then he asked us what money we had . Get the most value .  This is very much like a backpack template .  So our idea is to solve the problem by combining search sets and knapsack .  The first is the union search .  We have their connections . So we can merge it into one .  Think of price as space .  It's like packing  . So I set up a one-dimensional array to record the ancestral relationship .  Then we set up a structure . To record prices and values separately .  One dimensional array .  It is still a normal merge and set lookup operation .  The only thing to add is   Every merger .  Before merging ancestors . The value of the items to be merged . Add the subscript represented by the ancestor In the structure array of ,  In other words, it is equivalent to packaging the price and value with the ancestors .

And then there's a for Recycle 01 The idea of backpacking .  The specific code is as follows ,

  #include<stdio.h>
 #include<iostream>
 using namespace std;
 int n,m,w,tot;
 int father[1000000],f[10000000];
 
 struct node {
     int p, v;
 };
 node s[1000000],s1[1000000];
 int find(int x) { 
 	if(father[x]==x) return x;
 	father[x]=find(father[x]); 
 	return father[x];
 }
 void hb(int x,int y) { 
 	int fx=find(x);
 	int fy=find(y);
 	if(fx!=fy) {
 		s1[fx].v+=s1[fy].v;
 		s1[fx].p+=s1[fy].p;
 		father[fy]=fx;
 	}
 }
 int main() {
 	cin>>n>>m>>w;
 	int c,d;
 	for(int i=1; i<=n; i++) {
 		cin>>c>>d;
 		s1[i].p=c;
 		s1[i].v=d;
 		father[i]=i;
 	}
 	for(int i=1; i<=m; i++) {
 		int x,y;
 		cin>>x>>y;
 		hb(x,y);
 	}
 	for(int i=1; i<=n; i++) if(father[i]==i)
	 {
	 	s[tot]=s1[i];
		 tot++; 
	 }
 
 		for(int i=1; i<=tot; i++){
	  		for(int j=w; j>=s[i].p; j--){ 
	  			f[j]=max(f[j],f[j-s[i].p]+s[i].v);}}
	  	cout<<f[w];
 return 0;
 }

The last one for A loop is a 01 Backpack template .  Here is a little introduction ,01 knapsack .  It is a relatively simple idea of dynamic programming .  Through a double loop  . Put all the items   Take them out one by one and go through them .  Put it where all this item can be put .  Then compare this position , The value of this item . Using a max function .  In order to get . The maximum value of items placed in each position .  So that's one 01 knapsack . Of course, backpacks have some more complicated situations .  This is a relatively simple one .