Update

2021.8.2-2021.8.18 wrote this blog to commemorate the 2021 summer JC training
2021.9.3-2021.9.8 modification
2022.2.9 the part of bipartite graph is improved

2021.8.2(dp)

1. Milking

01 simple question of backpack

2.Gangsters

First sort the structure array from small to large according to the time point, and then d p dp dp, a special judgment needs to be added here. The state transition can be carried out only when the time difference is greater than or equal to the width difference.

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int ans=-1;
int n,K,T;
struct node{
 int t;//time 
 int p;//Weight  
 int s;//width 
}a[101];
bool cmp(node x,node y)
{
 return x.t<y.t;
}
int dp[1001];
int main()
{
 scanf("%d%d%d",&n,&K,&T);
 for(int i=1;i<=n;i++) scanf("%d",&a[i].t);
 for(int i=1;i<=n;i++) scanf("%d",&a[i].p);
 for(int i=1;i<=n;i++) scanf("%d",&a[i].s);
 sort(a+1,a+1+n,cmp);
 a[0].p=a[0].t=a[0].s=0;
 for(int i=1;i<=n;i++)
 	for(int j=i-1;j>=0;j--)
 		if(dp[j]>=a[j].p)
             if(abs(a[i].s-a[j].s)<=a[i].t-a[j].t)
                 dp[i]=max(dp[i],dp[j]+a[i].p);
 for(int i=0;i<=n;i++) ans=max(ans,dp[i]);
 printf("%d\n",ans);
 return 0;
}

3.Triangular Pastures

The meaning of the question has explained that each should be used, that is, the sum of the three sides of the triangle has been given, and the maximum area is calculated by Helen's formula. Get the mean inequality with BDFs (Baidu first search):
x y z ≤ ( x + y + z 3 ) 3 xyz≤(\frac{x+y+z}{3})^3 xyz≤(3x+y+z​)3
Substitute in p − a p-a p−a , p − b p-b p−b , p − c p-c p − c, it can be found that the closer the three sides are, the larger the area is.

Then do it on the backpack, and add the judgment that the sum of the two sides of the triangle is greater than the third side.

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n;
int sum;
int ans=-1;
int a[50];
bool f[50][1001][1001];
bool check(double x,double y,double z)
{
	if(!(x+y>z&&x+z>y&&y+z>x)) return 0;
	else return 1;
}
int S(int x,int y,int z)
{
	double p=(x+y+z)/2.0;
	return int(sqrt(p*(p-x)*(p-y)*(p-z))*100);
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		sum+=a[i];
	}
	f[0][0][0]=1;
	for(int i=1;i<=n;i++)
		for(int j=0;j<=sum/2;j++)
			for(int k=0;k<=sum/2;k++)
			{
				f[i][j][k]=f[i-1][j][k];
				if(j>=a[i]&&f[i-1][j-a[i]][k])
					f[i][j][k]=1;
				else if(k>=a[i]&&f[i-1][j][k-a[i]])
					f[i][j][k]=1;
			}
	for(int j=0;j<=sum/2;j++)
			for(int k=0;k<=sum/2;k++)
				if(f[n][j][k])
				{
					int aa=j,bb=k,cc=sum-j-k;
					if(!check(aa,bb,cc)) continue;
						ans=max(ans,S(aa,bb,cc));
				}
	printf("%d\n",ans);
	return 0;
}

4.Apple Catching

In general d p dp On the basis of dp, we need to add another dimension, that is, which tree is currently transferred, which is divided into 1 tree and 2 tree.

#include<iostream>
using namespace std;
const int inf=-1e9;
int ans;
int f[1005][35][3];
int a[2005];
int main(){
	int n,w;
	cin>>n>>w;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=0;i<=n;i++){
		for(int j=0;j<=w;j++){
			for(int k=1;k<=2;k++){
				f[i][j][k]=inf;
			}
		}
	}
	f[0][0][1]=0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=w;j++){
			for(int k=1;k<=2;k++){
				if(a[i]==k){
					f[i][j][k]=max(f[i][j][k],f[i-1][j][k]+1);
					if(j>0){
						f[i][j][k]=max(f[i][j][k],f[i-1][j-1][3-k]+1);
					}
				}
				else{
					f[i][j][k]=max(f[i][j][k],f[i-1][j][k]);
					if(j>0){
						f[i][j][k]=max(f[i][j][k],f[i-1][j-1][3-k]);
					}
				}
			}
			
		}
	}
	int ans=-1;
	for(int j=0;j<=w;j++){
		for(int k=1;k<=2;k++){
			ans=max(ans,f[n][j][k]);	
		}	
	
	}	cout<<ans;
}

5.Space Elevator

Set state d p [ j ] dp[j] dp[j] is j j j. whether the height is feasible. When the condition of [T.j] > is added, i.e. when the condition of [T.j] * break] is more than one;

#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
struct node{
	int h;
	int a;
	int c;
}sht[401];
int K;
bool cmp(node x,node y)
{
	return x.a<y.a;
}
bool dp[50001];
int main()
{
	scanf("%d",&K);
	for(int i=1;i<=K;i++) scanf("%d%d%d",&sht[i].h,&sht[i].a,&sht[i].c);
	sort(sht+1,sht+1+K,cmp);
	dp[0]=1;
	for(int i=1;i<=K;i++)
		for(int j=sht[i].a;j>=0;j--)
			for(int k=1;k<=sht[i].c;k++)
			{  
				if(j+k*sht[i].h>sht[i].a) break;
				if(dp[j]) dp[j+k*sht[i].h]=true;
			}
	for(int i=sht[K].a;i>=0;i--)
		if(dp[i])
		{
			cout<<i<<endl;
			return 0;
		}
	return 0;
}

6.Sum of Different Primes

01 backpack cost.

2021.8.3 (dp)

1. Divisibility

d p [ i ] [ j ] dp[i][j] dp[i][j] indicates front i i i number plus or minus the remainder is j j j whether it is established or not.

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,K;
int s[10001];
bool ht[10001][101];//Is it true that the plus minus remainder of the first i is j 
int main()
{
	scanf("%d%d",&n,&K);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&s[i]);
		s[i]=s[i]%K;
		if(s[i]<0) s[i]=-s[i];
	}
	ht[0][0]=1;
	ht[1][s[1]]=1;
	for(int i=2;i<=n;i++)
		for(int j=0;j<K;j++)
			ht[i][j]=ht[i-1][(j+s[i]+K)%K]|ht[i-1][(j+K-s[i])%K];
	if(ht[n][0]==1) printf("Divisible\n");
	else printf("Not divisible\n");
	return 0;
}

2.Washing Clothes

It's not difficult, but it's troublesome. First, color classification, and then a naked 01 backpack.

3.Problem Solving

I didn't write well at the beginning and didn't fully grasp it. Main ideas and judgments:

(1)down payments+Whether the previous balance is less than or equal to m 
(2)Whether the single payment balance is less than or equal to m

State transition if satisfied.

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int ans;
int m,p;
int s[301];
int h[301]; 
int t[301][301];
int main()
{
	memset(t,0x7f,sizeof(t));
	scanf("%d%d",&m,&p);
	for(int i=1;i<=p;i++) 
	{
		int a,b;
		scanf("%d%d",&a,&b); 
		s[i]=s[i-1]+a;
		h[i]=h[i-1]+b;
	}
	t[1][1]=1;
	t[0][0]=0;
	t[1][0]=2;
	for(int i=2;i<=p;i++)
	{
		for(int j=1;j<=i;j++)
			for(int k=0;k<=i-j;k++)
				if(s[i]-s[i-j]+h[i-j]-h[i-j-k]<=m)
					t[i][j]=min(t[i][j],t[i-j][k]+1);
		for(int j=1;j<=p;j++)
			if(h[i]-h[i-j]<=m) 
				t[i][0]=min(t[i][0],t[i][j]+1);
	}
	ans=t[p][0]+1;
	for(int i=1;i<=p;i++)
		if(h[p]-h[i-p]<=m) 
			ans=min(ans,t[p][i]+2);
    printf("%d\n",ans);
	return 0;
}

4.Milking Time

linear d p dp dp, sort the left endpoint before transfer, and then judge whether the current left endpoint is greater than the previous right endpoint + R before transfer.

#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
struct node{
	int l;
	int r;
	int v;
}a[1001];
bool cmp(node x,node y)
{
	return x.l<y.l;
}
int ans;
int n,m,R;
int dp[1001];
int main()
{
	scanf("%d%d%d",&n,&m,&R);
	for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].v);
	sort(a+1,a+1+m,cmp);
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<i;j++)
			if(a[j].r+R<=a[i].l)
				dp[i]=max(dp[i],dp[j]);
		dp[i]+=a[i].v;
	}
	for(int i=1;i<=m;i++) ans=max(ans,dp[i]);
	printf("%d",ans);	
	return 0;
}

2021.8.4 (dp)

1.Cow Exhibition

Consider the left column as m m m (mass), the right column is regarded as v v v (value), 01 backpack.

Since the subscript may be negative, move the array backward uniformly. This step has been adjusted for a long time. If you are not careful, it is very easy to make mistakes. (for example, WRX sample output 10086)

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n;
int s[101];
int h[101];
int t[1000001];
const int N=100000;
int main()
{
	memset(t,-0x3f,sizeof(t));
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d",&s[i],&h[i]);
	t[N]=0;
	for(int i=1;i<=n;i++)
	{
		if(s[i]<0)
			for(int j=0;j<=100000+N+s[i];j++) 
				t[j]=max(t[j],t[j-s[i]]+h[i]);
		else for(int j=100000+N;j>=s[i];j--)
				t[j]=max(t[j],t[j-s[i]]+h[i]);
	}
	int ans=0;
	for(int i=N;i<=100000+N;i++)
		if(t[i]>=0)
			ans=max(ans,t[i]+i-N);
	printf("%d",ans);
	return 0;
}

2.Projects

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int m,n;
int salary;
int sh[101][101];
int t[101][10001];
int u[101],d[101];
int main()
{
	int q;
	scanf("%d",&q);
	while(q--)
	{
		memset(t,-0x7f,sizeof(t));
		scanf("%d%d%d",&m,&n,&salary);
		for(register int i=1;i<=m;i++)
		{
			sh[i][0]=0;
			for(register int j=1;j<=n;j++) scanf("%d",&sh[i][j]);
			scanf("%d%d",&u[i],&d[i]);
		}
		for(register int i=0;i<=n;i++)
			t[1][i]=sh[1][i]*(u[1]-i*salary)-(100-sh[1][i])*d[1];
		for(register int i=2;i<=m;i++)
			for(register int j=0;j<=n;j++)
				for(register int k=0;k<=j;k++)
					t[i][j]=max(t[i][j],t[i-1][j-k]+sh[i][k]*(u[i]-k*salary)-(100-sh[i][k])*d[i]);
		int ans=-0x7f7f7f7f;
		for(register int i=0;i<=n;i++)
			ans=max(ans,t[m][i]);
		printf("%d\n",ans);
		for(register int i=0;i<=n;i++)
			if(t[m][i]==ans)
				printf("%d ",i);
		printf("\n");
	}
	return 0;
}

3.Minimal Backgammon

Adjusted for one night + half a day to play "Minimal Backgammon" for the subject task. Calculate the probability, huoyanyan

Status: d p [ i ] [ j ] dp[i][j] dp[i][j] stands for the second i i Round i arrival j j Probability of j( d o u b l e double double type).

Transfer: discuss according to the situation to see if the position is L L L or B B B (divide the probability by six).

Boundary: d p [ 0 ] [ 0 ] = 1 ; dp[0][0]=1; dp[0][0]=1;

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,T,L,B;
bool s[101]; 
bool h[101];
double t[101][101];//Probability of arrival of round i at j 
int move(int x,int k)//Position after moving k grid from x 
{
	int x2=x+k;
	if(x2<=n) return x2;
	else return 2*n-x2;
}
int main()
{
	scanf("%d%d%d%d",&n,&T,&L,&B);
	while(n||T||L||B)
	{
		if(n==0&&T==0&&L==0&&B==0) break;
		memset(s,0,sizeof(s));
		memset(h,0,sizeof(h));
		memset(t,0,sizeof(t));
		for(register int i=1;i<=L;i++) 
		{
			int x;
			scanf("%d",&x);
			s[x]=1;
		}
		for(register int i=1;i<=B;i++)
		{
			int x;
			scanf("%d",&x);
			h[x]=1;
		} 
		if(h[0])
		{
			printf("0.000000");
			continue;
		}
		t[0][0]=1;
		for(register int i=0;i<T;i++)
		{
			for(register int j=n-1;j>=0;j--)
			{
				if(s[j])
					for(register int k=1;k<=6;k++) 
						t[i+2][move(j,k)]+=t[i][j]/6;
				else if(h[j])
					t[i][0]+=t[i][j];
				else for(register int k=1;k<=6;k++) 
						t[i+1][move(j,k)]+=t[i][j]/6;
			}
		}
		double ans=0;
		for(register int j=0;j<=T;j++) ans+=t[j][n];
		printf("%.6f\n",ans);
		scanf("%d%d%d%d",&n,&T,&L,&B);
	}
	return 0;
}

2021.8.5 (dp)

Ant Counting

Find the number of subsets of multiple sets that meet the requirements.

Key and difficult points: Combination number of multiple sets optimization d p dp dp, or TLE. (but not monotonous queue optimization dp)

In the original TLE code, the three-layer loop obviously timed out:

#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
int ans=0;
int T,A,S,B;
int cnt[1001];
int sht[1001]; 
const int mod=1000000;
int main()
{
	scanf("%d%d%d%d",&T,&A,&S,&B);
	for(int i=1;i<=A;i++)
	{
		int x;
		scanf("%d",&x);
		cnt[x]++;
	}
	sht[0]=1;
	for(int i=1;i<=T;i++)
	{
		for(int j=B;j>=1;j--)
			for(int k=1;k<=min(j,cnt[i]);k++)
				sht[j]=(sht[j]+sht[j-k])%mod;
	}
	for(int i=S;i<=B;i++) ans=(ans+sht[i])%mod;
	printf("%d\n",ans);
	return 0;
}

The combination number of multiple sets is optimized k k k cycle:

#include<iostream>
#include<cstdio>
using namespace std;
int ans=0;
int T,A,S,B;
int cnt[1001];
int sht[2][100001];
const int mod=1000000;
int main()
{
	scanf("%d%d%d%d",&T,&A,&S,&B);
	for(int i=1;i<=A;i++)
	{
		int x;
		scanf("%d",&x);
		cnt[x]++;
	}
	sht[0][0]=sht[1][0]=1;
	int c=0;
	for(int i=1;i<=T;i++)
	{
		c=1-c;
		for(int j=1;j<=B;j++)
		{
			if(j>cnt[i])
				sht[c][j]=(sht[c][j-1]+sht[1-c][j]-sht[1-c][j-1-cnt[i]]+mod)%mod;
			else
				sht[c][j]=(sht[c][j-1]+sht[1-c][j])%mod;
		}
	}
	for(int i=S;i<=B;i++) ans=(ans+sht[c][i])%mod;
	printf("%d\n",ans);
	return 0;
}

There's only one question today. How about efficiency?!

Cause analysis: failed math (azaz). The combination number of multiple sets is relatively rusty, so we should remember it again.

2021.8.6 (graph shortest circuit)

1.Chain forward star construction map

important h e a d head head array initialization:

	memset(hd,-1,sizeo(hd));

Structure, n x t nxt nxt save chain subscript:

	struct node{
		int v;
		int w;
		int nxt;
	}es[1000005];

Edge building function:

	void add(int x,int y,int c){
		es[cnt].v=y;
		es[cnt].w=c;
		es[cnt].nxt=hd[x];
		hd[x]=cnt++;
	}

2. Shortest path problem 1

D i j k s t r a Dijkstra Dijkstra template problem, but this problem can be built without chain forward star map, ordinary v e c t o r vector vector. Then use a priority queue, which is more convenient and has no difficulties.

void dijkstra(int s)
{
	memset(dis,0x3f,sizeof(dis)); 
	memset(vis,0,sizeof(vis));
	dis[s]=0;
	priority_queue<Edge> q;
	now.v=s; now.w=0;
	q.push(now);
	while(!q.empty())
	{
		now=q.top();
		q.pop();
		if(vis[now.v]==1) continue;
		vis[now.v]=1;
		int len=es[now.v].size();
		for(int i=0;i<len;i++)
		{
			tmp=es[now.v][i];
			if(dis[now.v]+tmp.w<dis[tmp.v])
			{
				dis[tmp.v]=dis[now.v]+tmp.w;
				et.v=tmp.v;
				et.w=dis[tmp.v];
				q.push(et); 
			}
		}	 
	} 
}

3. Unblocked works (Continued)

Data range: 1 ≤ n ≤ 200 1≤n≤200 1 ≤ n ≤ 200, use F l o y d Floyd Floyd does $O(n^3) $and won't exceed.

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,m;
int mp[1001][1001];
const int inf=0x3f3f3f3f;,
int main()
{
	while(scanf("%d",&n)!=EOF)
	{
		memset(mp,inf,sizeof(mp));
		for(register int i=1;i<=n;i++) mp[i][i]=0;
		
		for(register int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					scanf("%d",&mp[i][j]);
					
		for(register int k=1;k<=n;k++) 
			for(register int i=1;i<=n;i++)
				for(register int j=1;j<=n;j++)
					if(i!=j&&j!=k&&i!=k)
							mp[i][j]=min(mp[i][k]+mp[k][j],mp[i][j]);
		int q;
		scanf("%d",&q);
		while(q--)
		{
			int s,t;
			scanf("%d%d",&s,&t);
			printf("%d\n",mp[s][t]);
		}
	}
	return 0;
}

3.Cow Hurdles

F l o y d Floyd Floyd, and the difference is that the highest fence along the way should be the lowest, so the relaxation operation is changed to:

	mp[i][j]=min(mp[i][j],max(mp[i][k],mp[k][j]));

Others remain unchanged.

2021.8.7 (graph minimum spanning tree)

1.Buy or Build

The first choice in life / NOI - [moved]

Can be found 0 ≤ q ≤ 8 0≤q≤8 0 ≤ q ≤ 8, so each q [ i ] q[i] q[i] you can enumerate if you choose not to (dfs or adopt binary enumeration subset). After enumeration, add all the edges in the package first, and then K r u s k a l Kruskal Kruskal finds the minimum spanning tree.

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

struct node{
	int u,v,w;
}s[1000001],s2[1000001];
int h[10][1001];//Subnet
int t[10];//Cost per subnet
int p=0;

int ans;
int n,q,m;
int fa[1001];

bool cmp(node a,node b){ return  a.w<b.w;  }
int fd(int x){ return fa[x]= x==fa[x] ? fa[x] : fd(fa[x]); }

void init()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d",&h[i][0],&t[i]);//Quantity, cost
		for(int j=1;j<=h[i][0];j++) scanf("%d",&h[i][j]);
	}

	int x[1001],y[1001];
	for(int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);
	m=0;//Number of sides
	for(int i=1;i<=n;i++)
		for(int j=1;j<i;j++)
		{
			int dis=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
			m++;
            s[m].u=i;
            s[m].v=j;
            s[m].w=dis;
		}
	return;
}

void Kruskal()
{
	p=0;
	int k=0,tot=0;
	sort(s+1,s+1+m,cmp);
	for(int i=1;i<=n;i++) fa[i]=i;

	for(int i=1;i<=m;i++)
	{
		int fx=fd(s[i].u);
		int fy=fd(s[i].v);
		if(fx!=fy)
		{
			fa[fy]=fx;
			tot+=s[i].w;

			p++;
			s2[p].u=s[i].u;
			s2[p].v=s[i].v;
			s2[p].w=s[i].w;

			k++;
			if(k==n-1) break;
        }
 	}
 	ans=tot;
	return;
}

void enumerate()
{
	int ii=1<<q;
	for(int i=1;i<ii;i++)
	{
		int tot=0;
		for(int j=1;j<=n;j++) fa[j]=j;

		int jj=1;
		for(int j=1;j<=q;j++)
		{
			if(i & jj)
			{
				tot+=t[j];
				for(int k=1;k<=h[j][0];k++)
				{
					int fx=fd(h[j][k]);
					int fy=fd(h[j][1]);
					if(fx!=fy) fa[fy]=fx;
				}
			}
			jj*=2;
		}

		for(int j=1;j<=p;j++)
		{
			int fx=fd(s2[j].u);
			int fy=fd(s2[j].v);
			if(fx!=fy)
			{
				fa[fy]=fx;
				tot+=s2[j].w;
        	}
		}
		ans=min(ans,tot);
	}
	return;
}

int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		init();
		Kruskal();
		enumerate();
		printf("%d\n",ans);
		if(T!=0) printf("\n");
	}
	return 0;
}

2.Slim Span

It is much simpler than the previous question

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<vector>
#include<cstdio>
using namespace std;

struct node{
	int u,v,w;
}sht[100001];

int mx; 
int cnt;
int n,m;
int ans;
bool flag;
int f[100001];

bool cmp(node x,node y){  return x.w<y.w;  }
int fd(int x){ return f[x]=f[x]==x?f[x]:fd(f[x]);  }

bool Kruskal(int l)
{
	cnt=0;
	mx=-1; 
	for(int i=1;i<=n;i++) f[i]=i;
	for(int i=l;i<=m;i++)
	{
		int fx=fd(sht[i].u);
		int fy=fd(sht[i].v);
		if(fx!=fy)
		{
			f[fy]=fx;
			mx=max(sht[i].w,mx);
			cnt++;
			if(cnt==n-1) return 1;
		}
	}
	return 0;
}
int main()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		if(n==0&&m==0) break;
		ans=0x3f3f3f3f;
		for(int i=1;i<=n;i++) f[i]=i;
		for(int i=1;i<=m;i++)
			scanf("%d%d%d",&sht[i].u,&sht[i].v,&sht[i].w);
		sort(sht+1,sht+1+m,cmp);
		for(int i=1;i<=m;i++)
			if(Kruskal(i))
				ans=min(ans,mx-sht[i].w);
		if(ans==0x3f3f3f3f) printf("-1\n");
		else printf("%d\n",ans);
	}
	return 0;
}

3.Kerry's cable network

Board questions.

2021.8.9 (bipartite drawing)

1.COURSES

Hungarian algorithm template for maximum matching of bipartite graphs.

//Bi-partite graph 
//Title Reference: POJ1469 
//Hungarian algorithm, time complexity O(mn) 
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

int mp[305][305];//Adjacency matrix is generally used to store graphs  
bool flag[305];//Match 
int res[305];//Record the final result. If result (result) = = 0, it means that the current point has not been used, res= 0 indicates that it has been used, and this result is the result of the estoppel side 
int n1,n2;
int ans;
int T;

bool find(int st)
{
	for(int i=1;i<=n2;i++)//Enumerate each point on the right 
		if(mp[st][i]&&flag[i]==0)//If there are connected edges and no matching points have been determined 
		{
			flag[i]=1;
			if(res[i]==0||res!=0&&find(res[i]))//There is no result at present, so it can be matched directly; Otherwise, let's see if there's any space on the side of its repentance  
			{
				res[i]=st;
				return 1;
			}
		}
	return 0;
}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		memset(mp,0,sizeof(mp));
		memset(res,0,sizeof(res));
		scanf("%d%d",&n1,&n2);
		for(int i=1;i<=n1;i++)
		{
			int x;
			scanf("%d",&x);
			for(int j=1;j<=x;j++)
			{
				int y;
				scanf("%d",&y);
				mp[i][y]=1;
			}
		}
		bool ff=1;
		for(int i=1;i<=n1;i++)//Enumerate each point on the left 
		{
			memset(flag,0,sizeof(flag));//Mark of right point 
			if(!find(i))
			{
				printf("NO\n");
				ff=0;
				break;
			}
		}
		for(int i=1;i<=n1;i++) cout<<res[i]<<' ';
		cout<<endl;
		if(ff) printf("YES\n");
	}
	return 0;
}

2.Air Raid

Read the picture in and build a left n n n nodes, right n n Bipartite graph with n nodes.

KM algorithm template (not necessarily correct, because I was dizzy):

//KM algorithm, the premise is the perfect matching of bipartite graph, and the maximum weight matching is solved. 
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int mp[105][105];
int match[105];
bool v_a[105];//Pruning array 
bool v_b[105];//Pruning array
int sk[105]; 
int a[105];//Demand on the left 
int b[105];//Supply on the right
int n;
bool dfs(int st)
{
	v_a[st]=1;
	for(int i=1;i<=n;i++)
	{
		if(v_b[st]) continue;
		int g=a[st]+b[i]-mp[st][i];
		if(g==0)//Meet wishes and needs 
		{
			v_b[st]=1;
			if(match[i]==0||match[i]==1&&dfs(match[i]))
			{
				match[i]=st;
				return 1;
			}
		}
		else sk[st]=min(sk[st],g);//Find the smallest edge of g 
	}
	return 0;
}
void KM()
{
	//Initialize demand and supply 
	for(int i=1;i<=n;i++)
	{
		a[i]=mp[i][1];
		for(int j=2;j<=n;j++)
			a[i]=max(mp[i][j],a[i]);
		b[i]=0; 
	}
	for(int i=1;i<=n;i++)
		while(1)
		{
			memset(v_a,0,sizeof(v_a));
			memset(v_b,0,sizeof(v_b));
			if(dfs(i)) break;
			int d=0x3f3f3f3f;
			for(int j=1;j<=n;j++)
				if(v_b[j]) 
					d=min(d,sk[j]);//Reduce demand 
			for(int j=1;j<=n;j++)
			{
				if(v_a[j]) a[j]-=d;
				if(v_b[j]) b[j]+=d;
				else sk[j]-=d;
			} 
		}
}
int main()
{
	return 0;
}

3.Going Home(WA changed or not)

4.Asteroids

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
bool mp[505][505];//Adjacency matrix is generally used to store graphs  
bool flag[505];//Pruning array, if used, directly jump out 
int res[505];//If result (result) = = 0, it means that the current point has not been used, result= 0 indicates that it has been used, and this result is the result of the estoppel side 
int n1,n2;
int n,k;
int ans;
int T;
bool find(int st)
{
	for(int i=1;i<=n2;i++)//Enumerate each point on the right 
		if(mp[st][i]&&flag[i]==0)
		{
			flag[i]=1;
			if(res[i]==0||res!=0&&find(res[i]))//There is no result at present, so it can be matched directly; Otherwise, let's see if there's any space on the side of its repentance  
			{
				res[i]=st;
				return 1;
			}
		}
	return 0;
}
int main()
{
	scanf("%d%d",&n,&k);
	n1=n2=n;
	for(int i=1;i<=k;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		mp[x][y]=1;
	}
	for(int i=1;i<=n1;i++)//Enumerate each point on the left 
	{
		memset(flag,0,sizeof(flag));
		if(find(i))
			ans++;
	}
	printf("%d\n",ans);
	return 0;
}

Later today K M KM KM algorithm is confused. I'd better change it again when I understand it

2021.8.10 (dp)

1. Mine excavation

2.Palindrome

Classic palindrome string problem.

( i i i cycle in reverse order, j j j cycle (reverse order) if s [i] = = s [j], DP [i] [j] = DP [i + 1] [j-1], otherwise dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1

Because the array is two-dimensional, the array of this question should be defined as s h o r t short short type, otherwise MLE will be.

3.Chocolate

It was originally a simple probability dp, but the problem has a big hole. That is to say, its probability is required by the accuracy. The accuracy is three decimal places. When it is calculated to a certain number of times, the change value of probability becomes very small within the accuracy range. From this point of view, when n > 1000 n>1000 n> At 1000, n=1000+n%2, which reduces the amount of calculation (otherwise TLE will occur).

I don't know why I started rolling on a whim

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int c,n,m;
double sht[2][1001];
int main()
{
	while(scanf("%d",&c),c!=0)
	{
		scanf("%d%d",&n,&m);
		if(m>n||m>c||(m+n)%2)
		{
			printf("0.000\n");
			continue;
		}
		if(n>1000) n=1000+n%2;
		memset(sht,0,sizeof(sht)); 
		sht[0][0]=1.0;
		for(int i=1;i<=n;i++)
			for(int j=0;j<=i&&j<=c;j++)
			{
				sht[i%2][j]=0;
				if((i+j)%2) continue;
               else sht[i%2][j]=sht[1-i%2][j-1]*(c-(j-1.0))/c+sht[1-i%2][j+1]*(j+1.0)/c;
			}	
		printf("%.3lf\n",sht[n%2][m]);
	}
	return 0;
} 

4.BUY LOW, BUY LOWER

Status: d p [ i ] dp[i] dp[i] indicates i i i is the maximum length of the end point.

Transfer: d p [ i ] = m a x d p [ j ] + 1 ( a [ i ] < a [ j ] ) dp[i]=max{dp[j]+1(a[i]<a[j])} dp[i]=maxdp[j]+1(a[i]<a[j])

Another scheme of the array can be added c [ ] c[] c [], assignment or accumulation during transfer.

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n;
int ans;
int c[5001];
int a[5001];
int dp[5001];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) c[i]=dp[i]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=i-1;j>0;j--)
		{
			if(a[j]>a[i])
			{
				if(dp[i]<dp[j]+1)
				{
					dp[i]=dp[j]+1;
					c[i]=c[j];
				}
				else if(dp[i]==dp[j]+1)
					c[i]+=c[j];
			}
			else if(a[i]==a[j])
			{
				if(dp[i]==1) c[i]=0;
				break;
			}
		}
	}
	int mx=-1;
	for(int i=1;i<=n;i++)
		mx=max(mx,dp[i]);
	for(int i=1;i<=n;i++)
		if(mx==dp[i])
			ans+=c[i];
	printf("%d %d\n",mx,ans);
	return 0;
}

5.Cowties

Since it is to form a circle, it is necessary to raise the position of No. 1 cow.

Status: d p [ i ] [ j ] dp[i][j] dp[i][j] stands for the second i i i cow in j j The shortest distance to position j

Transfer: dp[i][k]=min(dp[i][k],dp[i-1][j]+dis);

Initial value: dp[1] [...] = 0;

Final value: max{dp[n] [...] + dis(n,1)};

6.Jumping Cows

Status: d p [ i ] [ 0 ] dp[i][0] dp[i][0] indicates that the i-th odd number is taken, d p [ i ] [ 1 ] dp[i][1] dp[i][1] stands for the second i i i even numbers are taken. Then compress the first dimension.

for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
{
	sht[0]=mx1+a[i];
	sht[1]=mx0-a[i];
	mx1=max(mx1,sht[1]);
	mx0=max(mx0,sht[0]);
}
printf("%d",max(mx1,mx0));

7.Zipper

Status: d p [ i ] [ j ] dp[i][j] dp[i][j] indicates the front of string A i i i, before string B j j Whether j can form a C-string prefix.

Transfer:

if(i>0&&dp[i-1][j]&&A[i-1]==C[i+j-1]||j>0&&dp[i][j-1]&&B[j-1]==C[i+j-1]) 

	dp[i][j]=1;
   

Initial value:

d p [ 0 ] [ i ] = 1 dp[0][i]=1 dp[0][i]=1 when the first character of a string and c string is the same;

d p [ i ] [ 0 ] = 1 dp[i][0]=1 dp[i][0]=1 when the first character of b string and c string is the same;

#include<iostream>
#include<cstring> 
#include<cstdio>
#include<string>
using namespace std;
int T;
string A,B,C;
bool sht[201][201];
int main()
{
	scanf("%d",&T);
	for(int t=1;t<=T;t++)
	{
		memset(sht,0,sizeof(sht));
		cin>>A>>B>>C;
		sht[0][0]=1; 
		for(int i=0;i<=A.size();i++)
		{
			for(int j=0;j<=B.size();j++)
			{
				if(i>0&&sht[i-1][j]&&A[i-1]==C[i+j-1]||j>0&&sht[i][j-1]&&B[j-1]==C[i+j-1])
					sht[i][j]=1;
			}
		}
		if(sht[A.size()][B.size()]) printf("Data set %d: yes\n",t);
		else printf("Data set %d: no\n",t);
	}
	return 0;
}

8.Ministry

Similar to CSP2020 grid access (if you remember correctly)

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int m,n;
int ans_i;
int r[101][501];
int a[101][501];
int sht[101][501];//Reach the minimum sum of row i and column j
void print(int n,int j)
{
	if(n==1) return;
	if(r[n][j]==j)
	{
		print(n-1,j);
		printf("%d\n",j);
	}
	if(r[n][j]==j-1)
	{
		print(n,j-1);
		printf("%d\n",j-1);
	}
	if(r[n][j]==j+1)
	{
		print(n,j+1);
		printf("%d\n",j+1);
	}
}
int main()
{
	memset(sht,0x7f,sizeof(sht));
	scanf("%d%d",&m,&n);
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&a[i][j]);
	for(int i=1;i<=n;i++)
	{
		sht[1][i]=a[1][i];
		r[1][i]=i;
	}
	for(int i=2;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(sht[i][j]>sht[i-1][j]+a[i][j])
			{
				sht[i][j]=sht[i-1][j]+a[i][j];
				r[i][j]=j;
			}
			if(j>1&&sht[i][j]>sht[i][j-1]+a[i][j])
			{
				sht[i][j]=sht[i][j-1]+a[i][j];
				r[i][j]=j-1;
			}
		}
		for(int j=n;j>=1;j--)
		{
			if(sht[i][j]>sht[i-1][j]+a[i][j])
			{
				sht[i][j]=sht[i-1][j]+a[i][j];
				r[i][j]=j;
			}
			if(j<n&&sht[i][j]>sht[i][j+1]+a[i][j])
			{
				sht[i][j]=sht[i][j+1]+a[i][j];
				r[i][j]=j+1;
			}
		}
	}
	ans_i=1;
	for(int i=1;i<=n;i++)
		if(sht[m][i]<sht[m][ans_i])
			ans_i=i;
	print(m,ans_i);
	printf("%d",ans_i);
	return 0;
}

2021.8.11 (dp)

1.Brackets Sequence

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

int n; 
char s[101];
int p[101][101];//Describe the solution to achieve sht[i][j] 
int sht[101][101];//Represents the minimum amount of addition that makes the parenthesis sequence of i to j legal 
const int inf=1e9;

void print(int i,int j)
{
	if(i>j) return;
	else if(i==j)
	{
		if(s[i]=='('||s[i]==')') printf("()");
		else printf("[]");
	}
	else if(p[i][j]==-1)
	{
		printf("%c",s[i]);
		print(i+1,j-1);
		printf("%c",s[j]);
	}
	else{
		print(i,p[i][j]);
		print(p[i][j]+1,j);
	}
}
int main()
{
	scanf("%s",s+1);
	int n=strlen(s+1);
	for(int i=1;i<=n;i++) sht[i][i]=1;
	for(int len=2;len<=n;len++)
		for(int i=1;i<=n-len+1;i++)
		{
			int j=i+len-1;
			sht[i][j]=inf;
			if(s[i]=='('&&s[j]==')'||s[i]=='['&&s[j]==']')
				if(sht[i][j]>sht[i+1][j-1])
				{
					p[i][j]=-1;
					sht[i][j]=sht[i+1][j-1];
				}
			for(int k=i;k<j;k++)
				if(sht[i][j]>sht[i][k]+sht[k+1][j])
				{
					sht[i][j]=sht[i][k]+sht[k+1][j];
					p[i][j]=k;
				}
		}
	print(1,n);
	printf("\n");
	return 0;
}

2.Multiplication Puzzle

Classic interval dp, Luogu P1063 weakened version.

d p [ i ] [ j ] dp[i][j] dp[i][j] indicates i i i to j j The minimum score of j.

Initial value, d p [ i ] [ i ] = d p [ i ] [ i + 1 ] = 0 dp[i][i]=dp[i][i+1]=0 dp[i][i]=dp[i][i+1]=0.

State transition: d p [ i ] [ j ] = m i n ( d p [ i ] [ j ] , d p [ i ] [ k ] + d p [ k ] [ j ] + a [ i ] ∗ a [ j ] ∗ a [ k ] ) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[j]*a[k]) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+a[i]∗a[j]∗a[k]) ;

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n;
int a[101];
int sht[101][101];
int main()
{
	memset(sht,0x7f,sizeof(sht));
	scanf("%d",&n);
	for(int i=1;i<=n;i++) 
	{
		scanf("%d",&a[i]);
		sht[i][i]=sht[i][i+1]=0;
	}
	for(int len=3;len<=n;len++)//Enumeration length
		for(int i=1;i+len-1<=n;i++)//Enumerate left endpoints
		{
			int j=i+len-1;//Calculate right endpoint based on length
			for(int k=i+1;k<j;k++)
				sht[i][j]=min(sht[i][j],sht[i][k]+sht[k][j]+a[i]*a[j]*a[k]);
		}
	printf("%d\n",sht[1][n]);
	return 0;
}

3.Maximum sum

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int dp1[50001];
int dp2[50001];
int dp3[50001];
int a[50001];
int n,T;
int ans;
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		memset(dp2,-0x7f,sizeof(dp2));
		memset(dp3,-0x7f,sizeof(dp3));
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		dp1[1]=a[1];
		dp2[n]=a[n];
		for(int i=2;i<=n;i++)
			dp1[i]=max(dp1[i-1]+a[i],a[i]);
		for(int i=n-1;i>=1;i--)
			dp2[i]=max(dp2[i+1]+a[i],a[i]);
		dp3[n]=dp2[n];
		for(int i=n-1;i>=1;i--)
			dp3[i]=max(dp3[i+1],dp2[i]);
		ans=-0x7f;
		for(int i=2;i<=n;i++)
			ans=max(ans,dp1[i-1]+dp3[i]);
		printf("%d\n",ans);
	}
	return 0;
}

4.Martian Mining

Status: d p [ i ] [ j ] dp[i][j] dp[i][j] denotes by ( i , j ) (i,j) (i,j) is the maximum energy transfer value of the matrix in the lower right corner.

d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] + s u m a [ i ] [ j ] , d p [ i ] [ j − 1 ] + s u m b [ i ] [ j ] ) ; dp[i][j]=max(dp[i-1][j]+suma[i][j],dp[i][j-1]+sumb[i][j]); dp[i][j]=max(dp[i−1][j]+suma[i][j],dp[i][j−1]+sumb[i][j]);

( s u m a [ i ] [ j ] suma[i][j] suma[i][j] stands for ( i , j ) (i,j) (i,j) is the right end line prefix and, s u m b [ i ] [ j ] sumb[i][j] sumb[i][j] stands for ( i , j ) (i,j) Prefix (I) and (J) are vertical lines.

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,m;
int sht[501][501]; 
int a[501][501],b[501][501];
int suma[501][501],sumb[501][501];
void init()
{
	memset(sht,0,sizeof(sht));
	memset(suma,0,sizeof(suma));
	memset(sumb,0,sizeof(sumb));
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&a[i][j]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&b[i][j]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			suma[i][j]=suma[i][j-1]+a[i][j];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			sumb[i][j]=sumb[i-1][j]+b[i][j];
}
int main()
{
	while(scanf("%d%d",&n,&m))
	{
		if(n==0&&m==0) break;
		init();
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				sht[i][j]=max(sht[i-1][j]+suma[i][j],sht[i][j-1]+sumb[i][j]);
		printf("%d\n",sht[n][m]);
	}
	return 0;
}

5.Honeycomb Walk

d p [ k ] [ i ] [ j ] dp[k][i][j] dp[k][i][j] stands for the second k k Step k, arrival ( i , j ) (i,j) (i,j) number of options.

d p [ k ] [ i ] [ j ] + = d p [ k − 1 ] [ x ] [ y ] ; dp[k][i][j]+=dp[k-1][x][y]; dp[k][i][j]+=dp[k−1][x][y]; ( x = i + d x [ ] , y = j + d y [ ] x=i+dx[],y=j+dy[] x=i+dx[],y=j+dy[]).

Initial value: d p [ 0 ] [ 7 ] [ 7 ] = 1 ; dp[0][7][7]=1; dp[0][7][7]=1;

final value: d p [ n ] [ 7 ] [ 7 ] ; dp[n][7][7]; dp[n][7][7];

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int T,n;
int dx[8]={1,0,-1,-1,0,1};
int dy[8]={0,1,1,0,-1,-1};
int sht[26][26][26];
int main()
{
	sht[0][7][7]=1;
	for(int k=1;k<=15;k++)
		for(int i=0;i<15;i++)
			for(int j=0;j<15;j++)
				for(int d=0;d<6;d++)
				{
					int tx=i+dx[d];
					int ty=j+dy[d];
					if(tx>=0&&tx<15&&ty>=0&&ty<15)
						sht[k][i][j]+=sht[k-1][tx][ty];
				}
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		printf("%d\n",sht[n][7][7]);
	}
	return 0;
}

6.Grazing on the Run

d p [ i ] [ j ] [ 0 ] dp[i][j][0] dp[i][j][0] and d p [ i ] [ j ] [ 1 ] dp[i][j][1] dp[i][j][1] adds a dimension: eat from the left or right, and then there's nothing to say.

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int inf=1e9;
int sh[1001][1001][2];
int t[1001];
int n,v;
int main()
{
	scanf("%d%d",&n,&v);
	for(int i=1;i<=n;i++) scanf("%d",&t[i]);
	t[++n]=v;
	sort(t+1,t+1+n);		
	for(int i=1;i<=n;i++)
	{
		if(t[i]==v)
			sh[i][i][0]=0;
		else sh[i][i][0]=sh[i][i][1]=inf;
	}
	
	for(int len=2;len<=n;len++)
	    for(int i=1;i<=n-len+1;i++)
		{
			int j=i+len-1;
			sh[i][j][0]=sh[i][j][1]=inf;
			sh[i][j][0]=min(sh[i+1][j][1]+(t[j]-t[i])*(n-j+i),sh[i+1][j][0]+(t[i+1]-t[i])*(n-j+i));
			sh[i][j][1]=min(sh[i][j-1][1]+(t[j]-t[j-1])*(n-j+i),sh[i][j-1][0]+(t[j]-t[i])*(n-j+i));
		}
	printf("%d\n",min(sh[1][n][0],sh[1][n][1]));
	return 0;
}

7.Treats for the Cows

similar.

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n;
int v[2001];
int sht[2001][2001];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) 
	{
		scanf("%d",&v[i]);
		sht[i][i]=v[i]*n;
	}
	for(int len=2;len<=n;len++)
		for(int i=1;i+len-1<=n;i++)
		{
			int j=i+len-1;
			sht[i][j]=max(sht[i+1][j]+v[i]*(n-j+i),sht[i][j-1]+v[j]*(n-j+i));
		}
	printf("%d\n",sht[1][n]);
	return 0;
}

8.Travel

linear d p dp dp , d p [ i ] [ j ] dp[i][j] dp[i][j] stands for the second i i Day i arrival j j j cities have achieved the greatest gains (possibly negative).

Transfer: d p [ i ] [ j ] = m a x ( d p [ i ] [ j ] , d p [ i − 1 ] [ k ] − a [ k ] [ j ] + b [ i ] [ j ] ) ; dp[i][j]=max(dp[i][j],dp[i-1][k]-a[k][j]+b[i][j]); dp[i][j]=max(dp[i][j],dp[i−1][k]−a[k][j]+b[i][j]);

Initial value: d p [ 0 ] [ 1 ] ； dp[0][1]； dp[0][1]；

Final value: max{ d p [ m ] [ 1... n ] dp[m][1...n] dp[m][1...n] };

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,m;
int sht[101][101]; 
int a[101][101],b[101][101];
int main()
{
	while(scanf("%d%d",&n,&m))
	{
		if(n==0&&m==0) break;
		memset(sht,-0x7f,sizeof(sht));
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				scanf("%d",&a[i][j]);
		for(int i=1;i<=m;i++)
			for(int j=1;j<=n;j++)
				scanf("%d",&b[i][j]);
		sht[0][1]=0;
		for(int i=1;i<=m;i++)
			for(int j=1;j<=n;j++)
				for(int k=1;k<=n;k++)
					sht[i][j]=max(sht[i][j],sht[i-1][k]-a[k][j]+b[i][j]);
		int ans=-0x7f7f7f7f;
		for(int i=1;i<=n;i++)
			ans=max(ans,sht[m][i]);
		printf("%d\n",ans);
	}
	return 0;
}

2021.8.12 (multiplication)

emmm... Improve group content and digestibility ≤ 80 ≤80 ≤ 80% of a class.

1. [template] nearest common ancestor (LCA)

Multiplication for LCA + single point addition

//Luogu P3379 
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int cnt=0;
int n,U,T;
int p[500001][25];
int head[500001],to[1000001],nxt[1000001],deep[500001];
void add(int x,int y)
{
	to[cnt]=y;
	nxt[cnt]=head[x];
	head[x]=cnt++;
}
inline void dfs(int u,int fa)//DFS preprocesses the depth and parent nodes of all nodes 
{
	deep[u]=deep[fa]+1;
	p[u][0]=fa;
	for(int i=1;(1<<i)<=deep[u];i++)
		p[u][i]=p[p[u][i-1]][i-1];
	for(int i=head[u];i!=-1;i=nxt[i])
		if(to[i]!=fa)
			dfs(to[i],u);
}
int lca(int a,int b)//Rise from the node with large depth to the node with small depth, and use the multiplication method to find the minimum depth 
{
	int i,j;
	if(deep[a]<deep[b]) swap(a,b);
	for(i=0;(1<<i)<=deep[a];i++);
	i--;
	for(j=i;j>=0;j--)//Make the depth of a and B the same 
		if(deep[a]-(1<<j)>=deep[b])
			a=p[a][j];
	if(a==b) return a;
	for(j=i;j>=0;j--)//Jump to the point where there is no merge
	 	if(p[a][j]!=-1&&p[a][j]!=p[b][j])
		{
			a=p[a][j];
			b=p[b][j];
		}
	return p[a][0];
} 
void addNode(int x,int fa)//Single point addition 
{
	deep[x]=deep[fa]+1;
	p[x][0]=fa;
	for(int j=1;j<=20;j++)
		if(p[x][j-1]!=-1)
			p[x][j]=p[p[x][j-1]][j-1];
}
int main()
{
	memset(head,-1,sizeof(head));
	scanf("%d%d%d",&n,&T,&U);
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
	dfs(U,0);
	while(T--)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		int ans=lca(u,v);
		printf("%d\n",ans);
	}
	return 0;
} 

2.Design the city

Similar, omitted.

3.Minimal Segment Cover

Although LCA is not required, the idea is the same. "Doubling" means doubling each time, such as from 1 1 1 to 20 20 20 k k k cycle.

#include<iostream>
using namespace std;
const int N=5e5+10,inf=0x3f3f3f3f;
int dp[N][20];
int n,m;
int main()
{
	scanf("%d%d",&n,&m);
	while(n--)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		dp[l][0]=max(dp[l][0],r);//The left end point is certain, and the right end point is the optimal de duplication 
	}
	for(int i=1;i<N;i++) dp[i][0]=max(dp[i][0],dp[i-1][0]);
	for(int k=1;k<20;++k)
		for(int i=0;i<N;++i)
			dp[i][k]=dp[dp[i][k-1]][k-1];
	while(m--)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		int ans=0;
		for(int k=19;k>=0;--k)
			if(dp[l][k]<r)
			{
				ans+=(1<<k); 
				l=dp[l][k];
			}
		if(dp[l][0]<r) printf("-1\n");
		else printf("%d\n",ans+1);
	}
	return 0;
}

4.Balanced Lineup

(although AC has passed, it has not heard through...)

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int n,q;
int a[50001];
int dp_max[50001][25],dp_min[50001][25];
void initRMQ()
{
	for(int j=1;(1<<j)<=n;j++)
		for(int i=1;i+(1<<j)-1<=n;i++)
		{
			dp_max[i][j]=max(dp_max[i][j-1],dp_max[i+(1<<(j-1))][j-1]);
			dp_min[i][j]=min(dp_min[i][j-1],dp_min[i+(1<<(j-1))][j-1]);
		}
}
int getRMQ(int l,int r)
{
	int k=(int)(log((double)r-l+1)/log(2.0));
	return max(dp_max[l][k],dp_max[r-(1<<k)+1][k])-min(dp_min[l][k],dp_min[r-(1<<k)+1][k]);
}
int main()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++) 
	{
		scanf("%d",&a[i]);
		dp_max[i][0]=dp_min[i][0]=a[i];
	}
	initRMQ();
	while(q--)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%d\n",getRMQ(l,r));
	}
	return 0;
}

5. [ZJOI2012] disaster

20 points WA.

6.Connections between cities

I haven't written much. I can't write any more:

//Code that can't be written 
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=10001;

int tot;
int n,m,c;
int d[2*N];//depth 
int dis[N];//Distance to root 
bool vis[N];//dfs traversal tag array
int head[N];
int ver[2*N];//dfs traversal sequence
int first[N];//Where each node first appears in ver
int t[2*N][25];//Recording scheme 
int dp[2*N][25];

struct edge{
	int v,w;
	int nxt;
}e[2*N];

void dfs(int u,int dep)
{
	vis[u]=1;
	tot++;
	ver[tot]=u; d[tot]=dep; first[u]=tot;
	for(int k=head[u];k!=-1;k=e[k].nxt)
		if(!vis[e[k].v])
		{
			dis[e[k].v]=dis[u]+e[k].w;
			dfs(e[k].v,dep+1);
			tot++;
			ver[tot]=u; d[tot]=dep;
		}
}

void initRMQ()
{
	for(int i=1;i<=n;i++)
	{
		dp[i][0]=d[i];
		t[i][0]=i;
	}
	for(int j=1;(1<<j)<=n;j++)
		for(int i=1;i+(1<<j)-1<=n;i++)
		{
			if(dp[i][j-1]<dp[i+(1<<(j-1))][j-1])
			{
				dp[i][j]=dp[i][j-1];
				t[i][j]=t[i][j-1];
			}
			else 
			{
				dp[i][j]=dp[i+(1<<(j-1))][j-1];
				t[i][j]=t[i+(1<<(j-1))][j-1];
			}
		}
}

int RMQ(int x,int y)
{
	int k=(int)(log((double)y-x+1)/log(2.0));
	return min(t[x][k],t[y-(1<<k)+1][k]);
}
int main()
{
	while(1==scanf("%d%d%d",&n,&m,&c))
	{
		memset(d,0,sizeof(d));
		memset(t,0,sizeof(t));
		memset(dp,0,sizeof(dp));
		memset(vis,0,sizeof(vis));
		memset(dis,0,sizeof(dis));
		memset(ver,0,sizeof(ver));
		memset(head,0,sizeof(head));
		memset(first,0,sizeof(first));
	}
	return 0;
}

2021.8.13 (tree diameter and center of gravity)

Once again, the digestibility is? A class of.

1. Hospital setting

#include<iostream>
#include<cstring> 
#include<cstdio>
using namespace std;
const int N=206;
struct node{
	int v,nxt;
}e[N];
int n;
int cnt;
int w[N];
int head[N],sum[N];
long long ans=0x3f3f3f3f,f[N];
void add(int x,int y)
{
	cnt++;
	e[cnt].v=y;
	e[cnt].nxt=head[x];
	head[x]=cnt;
}
void dfs(int x,int fa,int dep)
{
	sum[x]=w[x];
	for(int i=head[x];i!=-1;i=e[i].nxt)
		if(e[i].v!=fa)
		{
			dfs(e[i].v,x,dep+1);
			sum[x]+=sum[e[i].v];
		}
	f[1]+=w[x]*dep;
}
void dp(int x,int fa)
{
	for(int i=head[x];i!=-1;i=e[i].nxt)
		if(e[i].v!=fa)
		{
			f[e[i].v]=f[x]+sum[1]-sum[e[i].v]*2;
			dp(e[i].v,x);
		}
	ans=min(ans,f[x]);
}
int main()
{
	scanf("%d",&n);
	memset(head,-1,sizeof(head));
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&w[i]);
		int u,v;
		scanf("%d%d",&u,&v);
		if(u) add(i,u), add(u,i);
       	if(v) add(i,v), add(v,i);
	}
	dfs(1,0,0);
	dp(1,0);
	printf("%d\n",ans);
	return 0;
} 

2.Cow Marathon

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=100000;
struct node{
	int v,next,c;
}e[N*2];
int n,m;
int p[N];//Distance from the current point to the root node 
int head[N],cnt;
void add(int x,int y,int z)
{
	cnt++;
	e[cnt].v=y;
	e[cnt].c=z;
	e[cnt].next=head[x];
	head[x]=cnt;
}
void dfs(int x,int fa)
{
	for(int i=head[x];i!=-1;i=e[i].next)
	{
		int u=e[i].v;
		if(u==fa) continue;
		p[u]=p[x]+e[i].c;
		dfs(u,x);
	}
}
int main()
{
	cnt=0;
	memset(head,-1,sizeof(head));
	
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		char c;
		scanf("%d%d%d",&u,&v,&w);
		cin>>c;
		add(u,v,w);  add(v,u,w);
	}
	
	memset(p,0,sizeof(p));
	dfs(1,0);
	p[0]=-1;
	int t1=0;
	for(int i=1;i<=n;i++) 
		if(p[i]>p[t1])
			t1=i;
	int ans=p[t1];
	
	memset(p,0,sizeof(p));
	dfs(t1,0);
	p[0]=-1;
	int t2=0;
	for(int i=1;i<=n;i++) 
		if(p[i]>p[t2])
			t2=i;
	
	printf("%d\n",p[t2]);
	return 0;
} 

3.Balancing Act

//I haven't 
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int T,n;
const int N=51000;
struct node{
	int v,nxt;
}e[N*2];
int head[N],cnt;
int ans,ans_it;
int sum[N],dp[N];
void add(int x,int y)
{
	cnt++;
	e[cnt].v=y;
	e[cnt].nxt=head[x];
	head[x]=cnt;
}
void dfs(int x,int fa)
{
	sum[x]=1;
	dp[x]=0;
	for(int i=head[x];i!=-1;i=e[i].nxt)
	{
		int u=e[i].v;
		if(u==fa) continue;
		dfs(u,x);
		sum[x]+=sum[u];
		dp[x]=max(dp[x],sum[u]);
	}
	dp[x]=max(dp[x],n-sum[x]);
	if(ans>dp[x])
	{
		ans=dp[x];
		ans_it=x;
	}
}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		ans=1e9;
		cnt=0;
		memset(head,-1,sizeof(head)); 
		scanf("%d",&n);
		for(int i=1;i<n;i++)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			add(x,y); add(y,x);
		}
		dfs(1,0);
		printf("%d %d\n",ans_it,ans);
	}
	return 0;
}

A question without AC:

4.Social Network I haven't

There are also questions about the center of gravity of the tree, which can't even be written at all. If you don't understand much in class, you can only... Make up after you understand it.

2021.8.14 (monotone Stack & monotone queue)

1. Smart code OI #216

2. Smart code OI #821

The first two questions are simple and omitted.

3.Largest Rectangle in a Histogram

Find the largest rectangular area, find the first one on the left and right that is smaller than the current one, and use the current value × The number is the area. Take the maximum of each current value (i.e. the minimum value in the rectangle) in the enumeration.

Maintain monotonicity with monotone stack.

#include<algorithm>
#include<iostream>
#include<cstdio> 
using namespace std;
int n;
int top;
long long ans=0;
long long a[100010];
long long sht[100010];
int main()
{
	while(~scanf("%d",&n))
	{
		if(n==0) break; 
		for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
		a[n+1]=0;
		top=0;
		ans=0;
		for(int i=1;i<=n+1;i++)
		{
			if(top==0||a[i]>=a[sht[top-1]]) sht[top++]=i;
			else{
				while(top>=1&&a[i]<a[sht[top-1]])
				{
					int r=i;
					int l=(top==1)?(0):(sht[top-2]);
					ans=max(ans,a[sht[top-1]]*(r-l-1));
					top--;
				}
				sht[top++]=i;
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}

4. Sliding window / [template] monotonic queue

Find the maximum / minimum value in the interval, and use the monotone queue to maintain monotonic increasing / decreasing monotonicity.

#include<iostream>
#include<cstdio>
using namespace std;
int a[10000005];
int que[10000005];
int main()
{
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	int head,tail;
	head=tail=0;
	for(int i=1;i<=n;i++)
	{
		while(head<tail&&i-que[head]>=k) head++;
		if(head>=tail||a[i]>=a[que[tail-1]])
			que[tail++]=i;
		else
		{
			while(head<tail&&a[que[tail-1]]>a[i]) 
				tail--;	
			que[tail++]=i;
		}
		if(i>=k) printf("%d ",a[que[head]]);
	}
	printf("\n");
	head=tail=0;
	for(int i=1;i<=n;i++)
	{
		while(head<tail&&i-que[head]>=k) head++;
		if(head>=tail||a[i]<=a[que[tail-1]])
			que[tail++]=i;
		else
		{
			while(head<tail&&a[que[tail-1]]<a[i]) 
				tail--;	
			que[tail++]=i;
		}
		if(i>=k) printf("%d ",a[que[head]]);
	}
	return 0;
} 

5. [NOIP2017 popularization group] jump house

Blue topic + +;

It can be said that the most disgusting use of monotonous queue -- optimized dynamic gauge

That is, when encountered (linear?) When using dynamic rules, we need to use the transfer of the maximum value in a certain section of the dp [] array. According to the monotonicity of monotonic increase / decrease, we can use the monotonic queue to find the maximum value of a certain section in the dp array (similar to the previous question), so as to save a layer of cycle.

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,d,k;
struct node{
	int pos;
	int sco;
}a[500001];
long long sht[500001];//To the i-th place, the i-th grid can get the maximum score 
bool check(int g)
{
	a[0].pos=0;
	a[0].sco=0;
	sht[0]=0;
	for(int i=1;i<=n;i++) sht[i]=-50000000002LL;
	
	int j=0;
	int que[500001];
	int head,tail;
	long long left,right;
	head=tail=0;
	
	for(int i=1;i<=n;i++)
	{
		while(a[i].pos-a[j].pos>=max(d-g,1)&&j<i)
		{
			while(head<tail&&sht[que[tail-1]]<sht[j])
					tail--;
			que[tail++]=j++;
		}
		while(head<tail&&a[que[head]].pos<a[i].pos-(g+d)) 
			head++;
		if(head<tail&&sht[que[head]]!=-50000000002LL)
		{
			sht[i]=sht[que[head]]+a[i].sco;
			if(sht[i]>=k) return 1;
		}
	}
	return 0;
}
int main()
{
	scanf("%d%d%d",&n,&d,&k);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&a[i].pos,&a[i].sco);
	int l=0,r=a[n].pos;
	int ans=-1;
	while(l<r)
	{
		int mid=(l+r)>>1;
		if(check(mid)) 
		{
			r=mid;
			ans=mid;
		}
		else l=mid+1;
	}
	printf("%d",ans);
	return 0;
}

6.Feel Good

Compared with the previous calculation of conscience! Monotone stack.

#include<iostream>
#include<cstdio>
using namespace std;
int top;
long long n,L,R;
long long sum[100005];
int a[100005],sht[100005],lt[100005];
int main()
{
	scanf("%lld",&n);
	long long ans=-1,tmp;
	for(int i=1;i<=n;i++) 
	{
		scanf("%lld",&a[i]);
		sum[i]=sum[i-1]+a[i];
	}
	a[++n]=-1;
	top=0;
	for(int i=1;i<=n;i++)
	{
		if(top==0||a[i]>a[sht[top-1]]) 
		{
			sht[top++]=i;
			lt[i]=i;
			continue;
		}
		if(a[i]==a[sht[top-1]]) continue;
		while(top>=1&&a[i]<a[sht[top-1]])
		{
			--top;
			tmp=1LL*a[sht[top]]*(sum[i-1]-sum[lt[sht[top]]-1]);
			if(tmp>ans)
			{
				L=lt[sht[top]];  
				R=i-1;
				ans=tmp;
			}
		}
		lt[i]=lt[sht[top]];
		sht[top++]=i;
	}
	printf("%lld\n%lld %lld\n",ans,L,R);
	return 0;
}

8.14 summary:

Monotone stack: find the first one on the left / right that is larger / smaller than the current number.

Monotone queue: find the maximum / minimum value in the interval.

2021.8.15(STL)

1.Glass Carving

Used a binary search lower that comes with STL_ bound() . In fact, I've always been able to do it, but I've always been handwritten (mainly handwritten or wrong). Remember to use it in the examination room.

#include<iostream>
#include<cstdio>
#include<set>
using namespace std;
int w,h,n;
set<int> h1,v1;
multiset<int> h2,v2;
int main()
{
	scanf("%d%d%d",&w,&h,&n);
	
	h1.insert(0);
	h1.insert(h);
	v1.insert(0);
	v1.insert(w);
	
	h2.insert(h);
	v2.insert(w);
	for(int i=1;i<=n;i++)
	{
		char c;
		int x;
		scanf("%s%d",&c,&x);
		if(c=='V')
		{
			multiset<int>::iterator it,it2,it3;
			it2=it=v1.lower_bound(x);
			if(it!=v1.begin()) it--;
			v1.insert(x);
			it3=v2.lower_bound(*it2-*it);
			
			v2.erase(it3);
			v2.insert(*it2-x);
			v2.insert(x-*it);
		}
		else
		{
			multiset<int>::iterator it,it2,it3;
			it2=it=h1.lower_bound(x);
			if(it!=h1.begin()) it--;
			h1.insert(x);
			it3=h2.lower_bound(*it2-*it);
			
			h2.erase(it3);
			h2.insert(*it2-x);
			h2.insert(x-*it);
		}
		int R=*(--h2.end()),C=*(--v2.end());
		printf("%lld\n",(1LL)*R*C);
	}
	return 0;
}

2.Yet Another Yet Another Task

I said it was STL. I used recursion for no reason (how concise it is, it's still a problem with difficulty of 2000).

#include<iostream>
#include<cstdio>
using namespace std;
int n;
int ans,res;
int a[100001];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<32;i++)
	{
		res=0;
		for(int j=1;j<=n;j++)
		{
			res+=a[j];
			if(a[j]>i) res=0;
			res=max(res,0);
			ans=max(ans,res-i);
		}
	}
	printf("%d",ans);
	return 0;
}

3. Produce champion

Map, map (or understood as an array with subscripts of any type).

#include<iostream>
#include<cstdio>
#include<string>
#include<map>
using namespace std;
int n,c;
int main()
{
	cin>>n; 
    while(n)
    {
        c=0;
        map<string,int> mp;
        string s1,s2;
        for(int i=1;i<=n;i++)
        {
            cin>>s1>>s2;
            mp[s2]+=1;
            mp[s1]+=0;
        }
        map<string,int>::iterator it;
        for(it=mp.begin();it!=mp.end();it++)
            if(it->second==0)
                c++;
        if(c==1) printf("Yes\n");
        else printf("No\n");
        cin>>n;
    }
    return 0;
}

2021.8.17(Tarjan)

Every time I talk about improving the content of the group, I cover the circle

Put a Tarjan template with WA and record the following revisions:

Going from u to v or from v to u?

//POJ2762 WA
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int NN=10001;

struct node{
	int v,nxt;
}e[NN];

int T;
int sht[NN],h;
int belong[NN],b;
int head[NN],cnt=0;
int DFN[NN],Low[NN],Indax,fg[NN];

void add(int x,int y)
{
	e[cnt].v=y;
	e[cnt].nxt=head[x];
	head[x]=cnt++;
}
void tarjan(int u)
{
	DFN[u]=Low[u]=++Indax;
	fg[u]=1;
	sht[++h]=u;
	for(int i=head[u];i!=-1;i=e[i].nxt)
	{
		int v=e[i].v;
		if(DFN[v]==0)
		{
			tarjan(v);
			Low[u]=min(Low[v],Low[u]);
		}
		else if(fg[v])
			Low[u]=min(DFN[v],Low[u]);
	}
	if(DFN[u]==Low[u])
	{
		b++;
		int p;
		do{
			p=sht[h];
			fg[p]=0;
			belong[p]=b;
			h--;	
		}while(h!=0&&u!=p);
	}
}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		h=0;
		b=0;
		cnt=0;
		Indax=0;
		memset(belong,0,sizeof(belong));
		memset(head,-1,sizeof(head));
		memset(DFN,0,sizeof(DFN));
		memset(Low,0,sizeof(Low));
		memset(sht,0,sizeof(sht));
		memset(fg,0,sizeof(fg));
		int n,m;
		scanf("%d%d",&n,&m);
		while(m--)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			add(u,v);
		}
		for(int i=1;i<=n;i++)
			if(DFN[i]==0)
				tarjan(i);
		if(b) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
} 

2021.8.18 (tree dp)

1.Tree

Status:

• d p [ i ] [ 0 ] dp[i][0] dp[i][0] is represented by i i A subtree with i as the root has and has only one ring.
• d p [ i ] [ 1 ] dp[i][1] dp[i][1] is expressed in i i i is the root of the subtree, the root does not match the meaning of the title, and the rest meet the requirements
• d p [ i ] [ 2 ] dp[i][2] dp[i][2] denotes by i i A subtree with i as the root has a chain (≥ two points) that is not in the ring.

Transfer:

• d p [ i ] [ 1 ] dp[i][1] dp[i][1]: sum all subtrees, s u m sum sum KaTeX parse error: Expected '}', got 'EOF' at end of input: { d p [ s o n ] [ 0 ] dp[son][0] dp[son][0] KaTeX parse error: Expected 'EOF', got '}' at position 1: }̲ ;

• d p [ i ] [ 2 ] dp[i][2] dp[i][2]: son node [ 1 ] [1] [1] And [ 2 ] [2] [2] Minimum value of + the rest plus [ 0 ] [0] [0]， m i n ( d p [ x ] [ 2 ] , d p [ x ] [ 1 ] ) min(dp[x][2],dp[x][1]) min(dp[x][2],dp[x][1]) + + + s u m sum sum { d p [ s o n ] [ 0 ] dp[son][0] dp[son][0] } ;

• d p [ i ] [ 0 ] dp[i][0] dp[i][0] :

t m p 1 = d p [ x ] [ 2 ] + s u m tmp1=dp[x][2]+sum tmp1=dp[x][2]+sum { d p [ s o n ] [ 0 ] dp[son][0] dp[son][0] } + 1 +1 +1 ;

Connected with one of the chains, the number of sides + 1, plus the sum of other subtrees.

t m p 2 = m i n tmp2=min tmp2=min { d p [ x 1 ] [ 1 ] , d p [ x 1 ] [ 2 ] dp[x1][1],dp[x1][2] dp[x1][1],dp[x1][2] } + m i n +min +min { d p [ x 2 ] [ 1 ] , d p [ x 2 ] [ 2 ] dp[x2][1],dp[x2][2] dp[x2][1],dp[x2][2] } + 1 + s u m +1+sum +1+sum { d p [ s o n ] [ 0 ] dp[son][0] dp[son][0] } ;

Connect the two subtrees.

d p [ i ] [ 0 ] = m a x dp[i][0]=max dp[i][0]=max { t m p 1 , t m p 2 tmp1,tmp2 tmp1,tmp2 } ；

#include<iostream>
#include<vector>
#include<cstdio>
using namespace std;
struct node{
	int to,nxt;
}edge[205];
int n;
int sht[105][105];
const int inf=1e4;
int head[105],cnt=0;
void add(int x,int y)
{
	edge[cnt].to=y;
	edge[cnt].nxt=head[x];
	head[x]=cnt++;
}
void dfs(int fa,int u)
{
	int sum=0;
	vector<int> a;
	for(register int i=head[u];i!=-1;i=edge[i].nxt)
	{
		int v=edge[i].to;
		if(v==fa) continue;
		a.push_back(v);
		dfs(u,v);
		sum+=sht[v][0];
	}
	sht[u][1]=sht[u][0]=sht[u][2]=inf;
	sht[u][1]=min(sht[u][1],sum);
	int len=a.size();
	for(register int i=0;i<len;i++)
	{
		int v=a[i];
		sht[u][2]=min(sht[u][2],min(sht[v][1],sht[v][2])+(sum-sht[v][0]));
		sht[u][0]=min(sht[u][0],sht[v][2]+(sum-sht[v][0])+1);
	}
	for(register int i=0;i<len;i++)
		for(register int j=i+1;j<len;j++)
		{
			int v1=a[i],v2=a[j];
			sht[u][0]=min(sht[u][0],min(sht[v1][2],sht[v1][1])+min(sht[v2][2],sht[v2][1])+(sum-sht[v1][0]-sht[v2][0])+1);
		}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) head[i]=-1;
	for(register int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v); add(v,u); 
	}
	dfs(0,1);
	if(sht[1][0]==inf) printf("-1\n");
	else printf("%d\n",sht[1][0]);
	return 0;
}

2.Special Experiment

Connect the nodes that cannot be taken at the same time and build a tree.

Status:

• d p [ i ] [ 0 ] dp[i][0] dp[i][0] is represented by i i i node is the root node, and the root node is not selected.

• d p [ i ] [ 1 ] dp[i][1] dp[i][1] is expressed in i i i node is the root, and the root node is selected.

Transfer:

• d p [ i ] [ 1 ] = s u m dp[i][1]=sum dp[i][1]=sum { d p [ s o n ] [ 0 ] dp[son][0] dp[son][0] } + a [ i ] +a[i] +a[i] ;

• d p [ i ] [ 0 ] = s u m dp[i][0]=sum dp[i][0]=sum { m a x max max { d p [ s o n ] [ 0 ] , d p [ s o n ] [ 1 ] dp[son][0],dp[son][1] dp[son][0],dp[son][1] } } ;

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
struct node{
	int to,nxt;
}edge[80001];
int n,m;
int sht[260][3];
int a[260],b[260];
int head[260],num=0;
void add(int x,int y)
{
	edge[num].to=y;
	edge[num].nxt=head[x];
	head[x]=num++;
}
void dfs(int fa,int u)
{
	sht[u][0]=0;
	sht[u][1]=a[u];
	for(register int i=head[u];i!=-1;i=edge[i].nxt)
	{
		int v=edge[i].to;
		if(v==fa) continue;
		dfs(u,v);
		sht[u][1]+=sht[v][0];
		sht[u][0]+=max(sht[v][0],sht[v][1]);
	}
}
int main()
{
	while(~scanf("%d%d",&n,&m))
	{
		if(n==0&&m==0) break;
		num=0;
		memset(head,-1,sizeof(head));
		memset(sht,0,sizeof(sht));
		for(register int i=1;i<=n;i++) scanf("%d",&a[i]);
		for(register int i=1;i<=m;i++) scanf("%d",&b[i]);
		for(register int i=1;i<=n-1;i++)
			for(register int j=i+1;j<=n;j++)
				for(register int k=1;k<=m;k++)
					if(a[j]-a[i]==b[k])
						add(i,j),add(j,i);
		dfs(0,1);
		printf("%d\n",max(sht[1][0],sht[1][1]));
	}
	return 0;
}

3.Party at Hali-Bula

I don't know why, RE:

#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<map>
using namespace std;
struct node{
	string to;
	int nxt;
}edge[80001];
int n;
int num;
int sht[260][3];
bool only[260][3];
vector<int> a[205];
map<string,int> mp;
void dfs(int fa,int u)
{
	sht[u][0]=0;
	sht[u][1]=1;
	for(register int i=0;i<a[u].size();i++)
	{
		int v=a[u][i];
		if(v==fa) continue;
		dfs(u,v);
		sht[u][1]+=sht[v][0];
		sht[u][0]+=max(sht[v][0],sht[v][1]);
		if(only[v][0]==0) only[u][1]=0;
		if(sht[v][0]==sht[v][1]||sht[v][0]>sht[v][1]&&only[v][0]==0||sht[v][0]<sht[v][1]&&only[v][1]==0) only[u][0]=0;
	}
}
int main()
{
	while(1==scanf("%d",&n))
	{
		if(n==0) break;
		num=0;
		for(int i=1;i<=n;i++)
		{
			a[i].clear();
			sht[i][0]=0;
			sht[i][1]=1;
			only[i][0]=only[i][1]=1;//Default unique 
		}
		string u,v;
		cin>>u;
		mp[u]=++num;
		for(register int i=1;i<n;i++)
		{
			cin>>u>>v;
			if(mp[u]==0) mp[u]=++num;
			if(mp[v]==0) mp[v]=++num;
			a[mp[u]].push_back(mp[v]);
			a[mp[v]].push_back(mp[u]);
		}
		dfs(0,1);
		if(sht[1][0]==sht[1][1]) printf("%d No\n",sht[1][0]);
		else if(sht[1][0]>sht[1][1]) printf("%d %s\n",sht[1][0],(only[1][0]==1)?"Yes":"No");
		else printf("%d %s\n",sht[1][1],(only[1][1]==1)?"Yes":"No");
	}
	return 0;
}

At the end of the training, we will finish with RE!

Looking back on so many days, I still have a lot to gain (especially dp), but there are still 100 million graph theories that I don't understand. (it's also very happy to be with the computer all day ~)

End