morning

Playing the game is basically crazy. myd violence AT1, wj two points + greed (misinterpretation) AT3, I pushed T2 formula for 2h, then hit the wrong ± sign and% less at the same time, and successfully exploded to 57.5
wjRank2 235，mydRank10 165
I'm dead

noon

Play a game of chess with myd and wj and lose decisively (I should play chess. Who is serious to play Chinese chess
It seems that there are no horses in military chess, Gobang and go. There are up to 20 horses in chess???
Lose to doubt life, then read the Tao Te Ching and Zhuangzi for 20mins, and the state of mind suddenly coordinated
I'm out of breath and my legs are not sour. I can climb 8 floors in one breath
However, there are many secluded characters in the Tao Te Ching. Zhuangzi is better. Classical Chinese is as good as vernacular

afternoon

It's all about cancer. 80% of T4's data are produced by the author with Yin Shou. Otherwise, how can it be the Yin problem?
Maximum flow + black and white dyeing + cet-7 = playing with wool
But there is a saying, I changed these questions quickly, and I have finished changing them
At dinner, I invited the first party of kidnapping junior high school to stroll and brush the streets. As a result
wj: you won't get lost again, will you?
Me: that's why I call you
wj: sooner or later you will lead us astray
emmmmm......
But I'm not lost
Current street brushing progress: 20% - > 60%

night

Write problem solving and travel notes. It is estimated that there will be several problems A after writing

T1

It is found that this range can be AC within O(nm) under the normal methods such as fast card reading
Personal data self-test can be A, if not, it has nothing to do with me
Guaranteed to pass in GMOJ
So let's be violent
It's actually a violent jump on new nodes
code:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
int n=4,m,a[333000],c[333000],b[333000],wj[333000],fa[333000],ans=3;
inline int read()
{
    int ret,c,f=1;
    while (((c=getchar())> '9'||c< '0')&&c!='-');
    if (c=='-') f=-1,ret=0;
    else ret=c-'0';
    while ((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0';
    return ret*f;
}
int max(int x,int y)
{
	return x>y?x:y;
}
int main()
{
	m=read();
	a[1]=b[1]=c[1]=1;
	fa[2]=fa[3]=fa[4]=1;
	wj[2]=1,wj[3]=2,wj[4]=3;
	while (m--)
	{
		int x=read();
		fa[n+1]=fa[n+2]=x;
		a[x]=b[x]=1;
		wj[n+1]=1,wj[n+2]=2;
		while (fa[x]!=1)
		{
			if (wj[x]==1) a[fa[x]]=max(a[fa[x]],max(a[x],b[x])+1);
			if (wj[x]==2) b[fa[x]]=max(b[fa[x]],max(a[x],b[x])+1);
			x=fa[x];
			ans=max(ans,b[x]+a[x]);
		}
		if (wj[x]==1) a[fa[x]]=max(a[fa[x]],max(a[x],b[x])+1);
		if (wj[x]==2) b[fa[x]]=max(b[fa[x]],max(a[x],b[x])+1);
		if (wj[x]==3) c[fa[x]]=max(c[fa[x]],max(a[x],b[x])+1);
		x=1;
		ans=max(max(ans,b[x]+c[x]),max(a[x]+b[x],a[x]+c[x]));
		printf("%d\n",ans);
		n+=2;
	}
	return 0;
}

T2

Thank whx teacher for teaching this question in advance
The problem can be divided into several subproblems, i.e. the ith known point (high) h i h_i hi, position w i w_i wi) the number of schemes to the i+1 known point, and then multiply it
Abstract subproblem: from( i , h i i,h_i i. HI) point start, no breakdown of x-axis, arrival( i + 1 , h i + 1 i+1,h_{i+1} i+1,hi+1)
(x,y) to (x+1,y+1),(x+1,y),(x+1,y-1)
dp + card can often AC
But here we talk about mathematical methods. The worst time complexity is O (n * metaphysics)
But very, very fast!!!
The formula of a single subproblem is (set) ∣ h i − h i + 1 ∣ = m , w i + 1 − w i = n |h_i-h_{i+1}|=m,w_{i+1}-w_i=n ∣hi​−hi+1​∣=m,wi+1​−wi​=n):
∑ k = 0 n − m ( ( n − k + m )   m o d   2 + 1 )   m o d   2 ∗ C ( n , k ) ∗ ( C ( n − k , n − k + m 2 ) − C ( n − k , n − k + h i + h i + 1 + 2 2 ) ) \sum_{k=0}^{n-m}((n-k+m)\bmod2+1)\bmod2*C(n,k)*(C(n-k,{n-k+m\over2})-C(n-k,{n-k+h_i+h_{i+1}+2\over2})) k=0∑n−m​((n−k+m)mod2+1)mod2∗C(n,k)∗(C(n−k,2n−k+m​)−C(n−k,2n−k+hi​+hi+1​+2​))
Is it long and smelly??
Explain that n is the total number of steps, m is the number of steps to rise, k is the number of steps taken in enumeration (x+1,y), and C(n,k) is the number of schemes for selecting k steps in N steps.
Obviously if ( n − k + m )   m o d   2 = 1 (n-k+m)\bmod2=1 (n − k+m)mod2=1 cannot be reached, and whether it is legal or not should be considered.
Legal total = all - illegal
We can find that in the remaining n-k steps, there must be (n-k-m)/2 steps down, so we choose so many steps down in the remaining n-k steps, that is, all the schemes
Next, let's transform the following conditions:
Not breaking through the x-axis means not touching the line y=-1
Then, for each illegal walking method, we turn down all the walking methods after the point after touching the straight line with y=-1 for the first time (it is suggested to understand it by looking at the picture). It is easy to prove that all illegal walking methods must converge at one point after turning (reserved for exercises, which can be understood perceptually), and it has a double shot relationship with the illegal scheme, that is, a one-to-one corresponding relationship, without repetition and omission.
Therefore, the number of illegal schemes = the number of schemes to this new point, i.e C ( n − k , n − k + h i + h i + 1 + 2 2 ) C(n-k,{n-k+h_i+h_{i+1}+2\over2}) C(n−k,2n−k+hi​+hi+1​+2​)
code:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
long long n,myd=1000000007,fst[40002],e[40002],o[40002],lst=1;
long long ins[40002];
long long ksm(long long x,int y)
{
	long long ans=1;
	while (y)
	{
		if (y&1) ans=ans*x%myd;
		x=x*x%myd;
		y>>=1;
	}
	return ans;
}
long long inv(long long x)
{
	return ksm(x,1000000005);
}
long long Del(long long x,long long y)
{
	return x<y?(x-y+myd)%myd:x-y;
}
long long C(long long x,long long y)
{
	if (y>x) return 0;
	return fst[x]%myd*ins[y]%myd*ins[x-y]%myd;
}
int main()
{
	freopen("brick.in","r",stdin);
	freopen("brick.out","w",stdout);
	scanf("%lld",&n);
	lst=1;
	fst[0]=1;
	ins[0]=inv(1)%myd;
	for (long long i=1;i<=2*n;i++)
	{
		fst[i]=fst[i-1]*i%myd;
		ins[i]=inv(fst[i])%myd;
	}
	for (long long i=1;i<=n;i++)
	{
		scanf("%lld",&e[i]);
	}
	if (e[1]>0||e[n]>0)
	{
		cout<<0;
		fclose(stdin);
		fclose(stdout);
		return 0;
	}
	e[1]=e[n]=0;
	o[1]=1;
	for (int i=2;i<=n;i++)
	{
		if (e[i]<0) continue;
		int wj=abs(e[i]-e[lst]);
		for (int j=0;j<=i-lst-wj;j++)
		{
			int kyx=(i-j-lst);
			if ((kyx+wj)%2==0)
			{
				o[i]+=Del(C(kyx,(kyx+wj)>>1),C(kyx,(kyx+e[i]+e[lst]+2)>>1))*C(i-lst,j)%myd;
				o[i]%=myd;
			}
		}
		o[i]=o[i]*o[lst]%myd;
		lst=i;
	}
	cout<<o[n];
	fclose(stdin);
	fclose(stdout);
	return 0;
}
//This question is quite short. At the same time, I have made a weakened version

T3

Two point answer + dp
dp is that the first i person can also do several No. 2 tasks when doing j sub tasks No. 1
See the code for the equation
code:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
int x[101][101],n,m,a[101][2];
int max(int x,int y)
{
	return x>y?x:y;
}
bool check(int mid)
{
	memset(x,-0x3f,sizeof(x));
	x[0][0]=0;
	for (int k=1;k<=n;k++)
	{
		for (int j=0;j<=m;j++)
		{
			for (int i=0;i<=j&&mid>=i*a[k][0];i++)
			{
				x[k][j]=max(x[k-1][j-i]+(mid-i*a[k][0])/a[k][1],x[k][j]);
			}
		}
	}
	return x[n][m]>=m;
}
int main()
{
	freopen("company.in","r",stdin);
	freopen("company.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%d%d",&a[i][0],&a[i][1]);
	int l=0,ans,r=100000,mid;
	while (l<=r)
	{
		mid=l+r>>1;
		if (check(mid)) r=mid-1,ans=mid;
		else l=mid+1;
	}
	cout<<ans;
	fclose(stdin);
	fclose(stdout);
	return 0;
}

T4

First of all, cet-7 can be dyed in black and white, and you will get a bipartite map
Next is a minimum cut
According to the famous minimum cut maximum tumor theorem, the network flow of the underworld is obtained and the maximum flow is obtained
In order to ensure the maximum number of points, we need to build edges like this (we preset the left side of the bipartite graph as D 1 D_1 D1 set, right D 2 D_2 D2 set, inf > inf, inf > all point weights, and both are much larger):
S company all D 1 D_1 D1 ， point, T with all D 2 D_2 For the point of D2 ， the edge weight is inf + the weight of the point
Set all original edges to D 1 D_1 D1​-> D 2 D_2 D2 ， form, parallel edge, edge weight INF
Then the residual network is used to find the solution
code:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<cmath>
#include<queue>
#include<deque>
using namespace std;
long long n,m,s,t,tot=2,tot2=2,head[4101],head2[4101],dep[4101],l,r,u[4101],r2,wj[4101];
long long w,ans,x[90001],y[90001];
bool vis[4101],myd[4101];
long long mn(long long x,long long y)
{
	return (x>y?y:x);
}
struct f{
	long long to,net;
	long long w;
} a[100011],a2[100011];
void add(long long x,long long y,long long w)
{
	a[tot].to=y,a[tot].w=w,a[tot].net=head[x],head[x]=tot++;
	return;
}
void add2(long long x,long long y)
{
	a2[tot2].to=y,a2[tot2].net=head2[x],head2[x]=tot2++;
	return;
}
bool bfs()
{
	memset(dep,0,sizeof(dep));
	l=0,r=0;
	u[r++]=s;
	dep[s]=1;
	while (l<r)
	{
		r2=r;
		for (long long i=l;i<r;i++)
		{
			for (long long j=head[u[i]];j;j=a[j].net)
			{
				if (a[j].w!=0&&dep[a[j].to]==0)
				{
					u[r2++]=a[j].to;
					dep[a[j].to]=dep[u[i]]+1;
				}
			}
		}
		l=r,r=r2;
	}
	return dep[t];
}
long long dfs(long long d,long long in)
{
	if (d==t)
	{
		return in;
	}
	long long out=0;
	long long uw=dep[d]+1;
	for (long long j=head[d];j&&in;j=a[j].net)
	{
		if (a[j].w==0||dep[a[j].to]!=uw) continue;
		long long s=dfs(a[j].to,mn(in,a[j].w));
		out+=s,in-=s;
		a[j].w-=s,a[j^1].w+=s;
	}
	if (out==0)
	{
		dep[d]=0;
	}
	return out;
}
void dft(int x,int fa,int wjj)
{
	if (vis[x]) return;
	vis[x]=1;
	if (wjj==1)
	{
		add(s,x,wj[x]+1e9),add(x,s,0);
	}
	else
	{
		myd[x]=1;
		add(x,t,wj[x]+1e9),add(t,x,0);
	}
	for (int i=head2[x];i;i=a2[i].net)
	{
		if (a2[i].to!=fa) dft(a2[i].to,x,wjj^1);
	}
	return;
}
void gjy(int x)
{
	vis[x]=1;
	for (int i=head[x];i;i=a[i].net)
	{
		if (!vis[a[i].to]&&a[i].w>0) gjy(a[i].to);
	}
	return;
}
int main()
{
	freopen("graph.in","r",stdin);
	freopen("graph.out","w",stdout);
	scanf("%d%d",&n,&m);
	t=n+1,s=t+1;
	for (int i=1;i<=n;i++) scanf("%d",&wj[i]);
	for (int i=1;i<=m;i++)
	{
		scanf("%d%d",&x[i],&y[i]);
		add2(x[i],y[i]),add2(y[i],x[i]);
	}
	for (int i=1;i<=n;i++) dft(i,0,1);
	for (int i=1;i<=m;i++)
	{
		if (myd[x[i]]) swap(x[i],y[i]);
		add(x[i],y[i],1e15),add(y[i],x[i],0);
	}
	memset(vis,0,sizeof(vis));
	while (bfs())
	{
		ans+=dfs(s,1e20);
	}
	gjy(s);
	int we=0,we2=0;
	for (int i=1;i<=n;i++) if (myd[i]^vis[i]) we++,we2+=wj[i];
	cout<<we<<' '<<we2<<endl;
	for (int i=1;i<=n;i++) printf("%d",myd[i]^vis[i]);
	fclose(stdin);
	fclose(stdout);
    return 0;
}