2021.12.16 eleveni的刷题记录

2021.12.16 eleveni的刷题记录

1. 数论

https://www.luogu.com.cn/problem/P2532

1.1卡特兰数

https://www.luogu.com.cn/blog/syksykCCC/solution-p2532

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

const int N=1e4+10;

int n;

struct node{

	int len,num[N];

	node(){

		memset(num,0,sizeof(num));

		len=1;num[1]=1;

	}

	node operator *(const int &k)const{

		node fin;

		for(int i=1;i<=len;i++)fin.num[i]=num[i]*k;

		fin.len=len;

		for(int i=2;i<=fin.len;i++){

			fin.num[i]+=fin.num[i-1]/10;

			fin.num[i-1]%=10;

		}

		while(fin.num[fin.len]>10){

			fin.num[fin.len+1]+=fin.num[fin.len]/10;

			fin.num[fin.len]%=10;

			++fin.len;

		}

		return fin;

	}

	node operator /(const int &k)const{

		node fin;

		int t=0;

		for(int i=len;i>=1;i--){

			t=t*10+num[i];

			fin.num[i]=t/k;

			t=t%k;

		}

		fin.len=len;

		while(!fin.num[fin.len])--fin.len;

		return fin;

	}

}ans;

int main(){

	IOS;

	cin>>n;

	for(int i=n+2;i<=2*n;i++)ans=ans*i;

	for(int i=2;i<=n;i++)ans=ans/i;

	for(int i=ans.len;i>=1;i--)cout<<ans.num[i];

	return 0;

}

1.2 同余

https://www.luogu.com.cn/problem/P4296

set的应用！

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<set>

#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

typedef long long ll;

ll n;

set<ll>s;

int main(){

	cin>>n;

	ll m=sqrt(n);

	if(n==1)return puts("None"),0;

	s.insert(1);

	for(ll i=1;i<=m;i++)if(n%i==0){

		ll j=n/i;

		for(ll k=j+1;k<=n;k+=j)if((k+1)%i==0)s.insert(k);

		for(ll k=j-1;k<=n;k+=j)if((k-1)%i==0)s.insert(k);

	}

	if(!s.size())return puts("None"),0;

	for(set<ll>::iterator it=s.begin();it!=s.end();it++)cout<<*it<<endl;

	return 0;

}

1.3 矩阵

https://www.luogu.com.cn/problem/P3873

矩阵快速幂：一直不变的那个矩阵是basic

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<stack>

#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

const int N=110;

const int mod=4147;

int n,m;

struct Matrix{

	int num[N][N];

	Matrix(){

		memset(num,0,sizeof(num));

	}

	Matrix operator *(const Matrix &b)const{

		Matrix c;

		for(int i=1;i<=100;i++)

		for(int j=1;j<=100;j++)

		for(int k=1;k<=100;k++)

		c.num[i][j]=(c.num[i][j]+num[i][k]*b.num[k][j])%mod;

		return c;

	}

}ans,basic;

inline Matrix operator ^(Matrix x,int y){

	Matrix fin=x;--y;

	while(y){

		if(y&1)fin=fin*x;

		x=x*x;

		y>>=1;

	}

	return fin;

}

int main(){

	IOS;

	cin>>n>>m;

	for(int i=n;i>=1;i--)cin>>ans.num[i][1];

	for(int i=n;i>=1;i--)cin>>basic.num[n][i];

	for(int i=2;i<=n;i++)basic.num[i-1][i]=1;

	/*cout<<"ans "<<endl;

	for(int i=1;i<=n;i++)cout<<ans.num[i][1]<<endl;

	cout<<"basic "<<endl;

	for(int i=1;i<=n;i++){

		for(int j=1;j<=n;j++)cout<<basic.num[i][j]<<" ";

		cout<<endl;

	}

	cout<<endl;*/

	m-=n;

	basic=basic^m;

	ans=basic*ans;

	//cout<<"change ans"<<endl;

	//for(int i=1;i<=n;i++)cout<<ans.num[i][1]<<endl;

	cout<<ans.num[n][1];

	return 0;

}

2. 动态规划

动态规划是算好了拿来直接用？/疑惑

2.1 普通DP

https://www.luogu.com.cn/problem/P2530

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

const int N=11;

const int inf=0x3f3f3f3f;

int n,f[N*N][N][N][N];

char a[N*N];

int main(){

	cin>>n;

	for(int i=1;i<=n;i++)cin>>a[i];

	memset(f,inf,sizeof(f));

	f[0][0][0][0]=0;

	for(int i=1;i<=n;i++)

	for(int j=0;j<=10;j++)

	for(int k=0;k<=10-j;k++)

	for(int l=0;l<=10-j-k;l++){

		if(+k+l>10)continue;

		if(a[i]=='A'&&j)f[i][j][k][l]=f[i-1][j-1][k][l];

		if(a[i]=='B'&&k)f[i][j][k][l]=f[i-1][j][k-1][l];

		if(a[i]=='C'&&l)f[i][j][k][l]=f[i-1][j][k][l-1];

		f[i][0][k][l]=min(f[i][0][k][l],f[i][j][k][l]+1);

		f[i][j][0][l]=min(f[i][j][0][l],f[i][j][k][l]+1);

		f[i][j][k][0]=min(f[i][j][k][0],f[i][j][k][l]+1);

	}

	cout<<f[n][0][0][0];

	return 0;

}

https://www.luogu.com.cn/problem/P4398

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

const int N=55;

int n,a[N][N],b[N][N],f[N][N][N][N];

inline int read(){

	int s=0,w=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){

		if(ch=='-')w=-1;

		ch=getchar();

	}

	while(ch<='9'&&ch>='0'){

		s=s*10+ch-'0';

		ch=getchar();

	}

	return s*w;

}

int main(){

	n=read();

	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=read();

	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)b[i][j]=read();

	int ans=0;

	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)

	for(int k=1;k<=n;k++)for(int l=1;l<=n;l++){

		if(a[i][j]==b[k][l])

		f[i][j][k][l]=min(f[i-1][j-1][k-1][l-1],min(f[i][j-1][k][l-1],f[i-1][j][k-1][l]))+1;

		ans=max(ans,f[i][j][k][l]);

	}

	cout<<ans;

	return 0;

}

https://www.luogu.com.cn/problem/P2592

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

const int mod=12345678;

int n,m,k,f[155][155][25][25];

inline int read(){

	int s=0,w=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){

		if(ch=='-')w=-1;

		ch=getchar();

	}

	while(ch<='9'&&ch>='0'){

		s=s*10+ch-'0';

		ch=getchar();

	}

	return s*w;

}

int main(){

	n=read();m=read();k=read();

	f[0][0][0][0]=1;

	for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)

	for(int u=0;u<=k;u++)for(int v=0;v<=k;v++){

		int x=f[i][j][u][v];

		f[i+1][j][max(u-1,0)][v+1]=(f[i+1][j][max(u-1,0)][v+1]+x)%mod;

		f[i][j+1][u+1][max(v-1,0)]=(f[i][j+1][u+1][max(v-1,0)]+x)%mod;

	}

	int ans=0;

	for(int i=0;i<=k;i++)for(int j=0;j<=k;j++)

	ans=(ans+f[n][m][i][j])%mod;

	cout<<ans;

	return 0;

}

2.2 树形DP

https://www.luogu.com.cn/problem/P3698

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

const int N=110;

int n,m,cnt,head[N],f[2][N][N],fa[N];

struct node{

	int to,next;

}a[N*2];

inline int read(){

	int s=0,w=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){

		if(ch=='-')w=-1;

		ch=getchar();

	}

	while(ch<='9'&&ch>='0'){

		s=s*10+ch-'0';

		ch=getchar();

	}

	return s*w;

}

inline void add(int u,int v){

	++cnt;

	a[cnt].to=v;

	a[cnt].next=head[u];

	head[u]=cnt;

}

inline void pre(int x,int fai){

	fa[x]=fai;

	for(int i=head[x];i;i=a[i].next){

		int v=a[i].to;

		if(v==fai)continue;

		pre(v,x);

	}

}

inline void dfs(int x){

	f[0][x][0]=f[1][x][0]=1;

	for(int i=head[x];i;i=a[i].next){

		int v=a[i].to;

		if(v==fa[x])continue;

		dfs(v);

		for(int j=n;j>=1;j--)

		for(int k=0;k<j;k++){

			if(j-k>=2)

			f[1][x][j]=max(f[1][x][j],f[1][v][k]+f[1][x][j-k-2]),

			f[0][x][j]=max(f[0][x][j],f[1][v][k]+f[0][x][j-k-2]);

			f[0][x][j]=max(f[0][x][j],f[0][v][k]+f[1][x][j-k-1]);

		}

	}

	for(int i=1;i<=n;i++)

	f[0][x][i]=max(f[0][x][i],f[0][x][i-1]),

	f[1][x][i]=max(f[1][x][i],f[1][x][i-1]);

}

int main(){

	m=read();n=read();

	for(int i=1;i<m;i++){

		int u,v;

		u=read()+1;v=read()+1;

		add(u,v);add(v,u);

	}

	pre(1,0);

	//for(int i=1;i<=n;i++)cout<<fa[i]<<" ";cout<<endl;

	dfs(1);

	cout<<f[0][1][n];

	return 0;

}

https://www.luogu.com.cn/problem/P4438

处理树二选一减小空间可以编号处理，每次处理一条链，这样最多需要的编号个数就是链的长度

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

#define int long long

const int N=4e4+10;

const int inf=0x3f3f3f3f;

int n,son[N][2],dfsx[N],f[200][50][50];

struct Satin{

	int a,b,c;

}rural[N];

inline int read(){

	int s=0,w=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){

		if(ch=='-')w=-1;

		ch=getchar();

	}

	while(ch<='9'&&ch>='0'){

		s=s*10+ch-'0';

		ch=getchar();

	}

	return s*w;

}

inline void dfs(int x,int id,int L,int R){

	dfsx[x]=id;

	if(x>=n){

		for(int i=0;i<=L;i++)

		for(int j=0;j<=R;j++)

		f[dfsx[x]][i][j]=1ll*rural[x-n+1].c*1ll*(rural[x-n+1].a+i)*1ll*(rural[x-n+1].b+j);

		return ;

	}

	dfs(son[x][0],id+1,L+1,R);dfs(son[x][1],id+2,L,R+1);

	for(int i=0;i<=L;i++)

	for(int j=0;j<=R;j++)

	f[dfsx[x]][i][j]=min(1ll*f[dfsx[son[x][0]]][i][j]+f[dfsx[son[x][1]]][i][j+1],

				1ll*f[dfsx[son[x][0]]][i+1][j]+f[dfsx[son[x][1]]][i][j]);

}

signed main(){

	//memset(f,inf,sizeof(f));

	n=read();

	for(int i=1;i<n;i++){

		int u,v;

		u=read();v=read();

		if(u<0)u=-u+n-1;

		if(v<0)v=-v+n-1;

		son[i][0]=u;son[i][1]=v;

	}

	for(int i=1;i<=n;i++)rural[i].a=read(),rural[i].b=read(),rural[i].c=read();

	dfs(1,1,0,0);

	cout<<f[dfsx[1]][0][0];

	return 0;

}

2.3 区间DP

https://www.luogu.com.cn/problem/P4302

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<stack>

#include<queue>

#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

const int N=110;

const int inf=0x3f3f3f3f;

int f[N][N],len[N];

string s;

inline int check(int L,int R,int lenth){

	for(int i=L;i<=R;i++)if(s[i]!=s[L+(i-L)%lenth])return 0;

	return 1;

}

int main(){

	cin>>s;

	for(int i=1;i<=100;i++){

		if(i<10)len[i]=1;

		else if(i<100)len[i]=2;

		else len[i]=3;

	}

	int n=s.length();

	s=' '+s;

	memset(f,inf,sizeof(f));

	for(int i=1;i<=n;i++)f[i][i]=1;

	for(int l=2;l<=n;l++)

	for(int i=1;i+l-1<=n;i++){

		int j=i+l-1;

		for(int k=i;k<j;k++)f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);

		for(int k=1;k<l;k++)if(l%k==0)

		if(check(i,j,k))f[i][j]=min(f[i][j],f[i][i+k-1]+2+len[l/k]);

	}

	cout<<f[1][n];

	return 0;

}

https://www.luogu.com.cn/problem/P3847

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<set>

#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

const int N=3010;

int n,a[N],f[N][N];

int main(){

	IOS;

	cin>>n;

	for(int i=1;i<=n;i++)cin>>a[i];

	for(int l=2;l<=n;l++)

	for(int i=1;i+l-1<=n;i++){

		int j=i+l-1;

		if(a[i]==a[j])f[i][j]=f[i+1][j-1];

		else f[i][j]=min(f[i+1][j-1],min(f[i][j-1],f[i+1][j]))+1;

	}

	cout<<f[1][n];

	return 0;

}

2.4 概率DP

https://www.luogu.com.cn/problem/P2059

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cmath>

#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

const int N=55;

int n,m,a[N];

double f[N][N];

int main(){

	cin>>n>>m;

	f[1][1]=1.0;

	for(int i=1;i<=m;i++)cin>>a[i];

	for(int i=2;i<=n;i++){

		for(int k=1;k<=m;k++){

			int aim=a[k]%i?a[k]%i:i;

			for(int j=1;j<i;j++){

				aim=aim+1>i?1:aim+1;

				f[i][aim]+=f[i-1][j]/(double)m;

			}

		}

	}

	for(int i=1;i<=n;i++)printf("%.2lf%% ",f[n][i]*100);

	return 0;

}

2.5 二进制优化

https://www.luogu.com.cn/problem/P4095

完全背包

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cmath>

#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

#define int long long

const int N=1010;

int n,m,cnt,pre[N*10][N],suf[N*10][N],L[N*10],R[N*10];

struct node{

	int cost,val,id;

}a[N*N];

signed main(){

	IOS;

	cin>>n;

	for(int i=1;i<=n;i++){

		int cost,val,num;

		cin>>cost>>val>>num;

		L[i]=cnt;

		for(int j=1;j<=num;j*=2){

			++cnt;

			a[cnt].cost=cost*j;a[cnt].val=val*j;

			a[cnt].id=i;

			num-=j;

		}

		if(num)

		a[++cnt].cost=cost*num,a[cnt].val=val*num,a[cnt].id=i;

		R[i]=cnt+1;

	}

	for(int i=1;i<=cnt;i++){

		memcpy(pre[i],pre[i-1],sizeof(pre[i-1]));

		for(int j=1000;j>=a[i].cost;j--)

		pre[i][j]=max(pre[i][j],pre[i-1][j-a[i].cost]+a[i].val);

	}

	for(int i=cnt;i>=1;i--){

		memcpy(suf[i],suf[i+1],sizeof(suf[i+1]));

		for(int j=1000;j>=a[i].cost;j--)

		suf[i][j]=max(suf[i][j],suf[i+1][j-a[i].cost]+a[i].val);

	}

	cin>>m;

	for(int i=1;i<=m;i++){

		int limit,maxn;

		cin>>limit>>maxn;

		++limit;

		int ans=0;

		for(int j=0;j<=maxn;j++)

		ans=max(ans,pre[L[limit]][j]+suf[R[limit]][maxn-j]);

		cout<<ans<<endl;

	}

	return 0;

}

3. 基础算法

3.1 贪心

https://www.luogu.com.cn/problem/UVA1344

田忌告诉我说他不想赛马！

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

const int N=1024;

int n,a[N],b[N],ans=0;

inline int read(){

	int s=0,w=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){

		if(ch=='-')w=-1;

		ch=getchar();

	}

	while(ch<='9'&&ch>='0'){

		s=s*10+ch-'0';

		ch=getchar();

	}

	return s*w;

}

int main(){

	freopen("uva1344.out","w",stdout);

	while(~scanf("%d",&n)&&n){

		for(int i=1;i<=n;i++)a[i]=read();

		for(int j=1;j<=n;j++)b[j]=read();

		sort(a+1,a+n+1);

		sort(b+1,b+n+1);

		ans=0;

		int aL=1,bL=1,aR=n,bR=n;

		for(int i=1;i<=n;i++){

			if(a[aR]>b[bR])ans+=200,--aR,--bR;

			else if(a[aR]<b[bR])ans-=200,++aL,--bR;

			else if(a[aL]>b[bL])ans+=200,++aL,++bL;

			else{

				if(a[aL]<b[bR])ans-=200;

				++aL,--bR;

			}

		}

		cout<<ans<<endl;

	}

	return 0;

}

https://www.luogu.com.cn/problem/P3963

那啥，实际上咱可以用单调队列水的……

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<queue>

#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

#define int long long

const int N=2e5+10;

typedef long long ll;

int n,m,W,ai[N];

ll summaxn,summinn,maxn[N],minn[N];

struct node{

	int score,val;

	bool operator <(const node &b)const{

		return score<b.score;

	}

}a[N];

priority_queue<int>qmaxn;

priority_queue<int>qminn;

signed main(){

	IOS;

	cin>>m>>n>>W;

	for(int i=1;i<=n;i++)cin>>a[i].score>>a[i].val,ai[i]=a[i].score;

	sort(ai+1,ai+n+1);

	int len=unique(ai+1,ai+n+1)-ai-1;

	for(int i=1;i<=n;i++)a[i].score=lower_bound(ai+1,ai+len+1,a[i].score)-ai;

	sort(a+1,a+n+1);

	//cout<<"sort "<<endl;

	//for(int i=1;i<=n;i++)cout<<a[i].score<<" "<<a[i].val<<endl;

	int ans=-1;

	for(int i=1;i<=n;i++){

		while(qminn.size()>m/2)summinn-=qminn.top(),qminn.pop();

		minn[i]=summinn;

		summinn+=a[i].val,qminn.push(a[i].val);

	}

	for(int i=n;i>=1;i--){

		while(qmaxn.size()>m/2)summaxn-=qmaxn.top(),qmaxn.pop();

		maxn[i]=summaxn;

		summaxn+=a[i].val,qmaxn.push(a[i].val);

	}

	/*cout<<"minn"<<endl;

	for(int i=1;i<=n;i++)cout<<minn[i]<<" ";cout<<endl;

	cout<<"maxn"<<endl;

	for(int i=1;i<=n;i++)cout<<maxn[i]<<" ";cout<<endl;*/

	for(int i=m/2+1;i<=n-m/2;i++)if(minn[i]+a[i].val+maxn[i]<=W)ans=ai[a[i].score];

	cout<<ans;

	return 0;

}

https://www.luogu.com.cn/problem/P3845

又是奶牛挤奶，但我依旧48pts，望天，心好累，心好塞~

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cmath>

#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

const int N=1010;

int t,n,top;

struct node{

	int x,y;

	bool operator <(const  node &b)const{

		return y==b.y?x<b.x:y<b.y;

	}

}a[N],endi[N];

int main(){

	IOS;

	cin>>t;

	while(t--){

		memset(&endi,0,sizeof(endi));

		top=0;

		cin>>n;

		for(int i=1;i<=n;i++){

			cin>>a[i].x>>a[i].y;

			a[i].y*=-1;

			if(a[i].x>a[i].y)swap(a[i].x,a[i].y);

		}

		sort(a+1,a+n+1);

		//cout<<"sort "<<endl;

		//for(int i=1;i<=n;i++)cout<<a[i].x<<" "<<a[i].y<<endl;

		top=1;

		endi[1]=a[1];

		for(int i=2;i<=n;i++){

			int flag=0;

			for(int j=1;j<=top;j++){

				if(a[i].x>=endi[j].x){

					endi[j]=a[i];

					flag=1;

					break;

				}

			}

			if(!flag)endi[++top]=a[i];

		}

		cout<<top<<endl;

	}

	return 0;

}

3.2 递推

https://www.luogu.com.cn/problem/P3856

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cmath>

#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

#define int long long

const int N=110;

int f[N][N][N],lastia[N],lastib[N],lastic[N];

char a[N],b[N],c[N];

signed main(){

	scanf("%s",a+1);scanf("%s",b+1);scanf("%s",c+1);

	int lena=strlen(a+1),lenb=strlen(b+1),lenc=strlen(c+1);

	for(int i=1;i<=lena;i++){

		lastia[a[i]-'a'+1]=i;

		memset(lastib,0,sizeof(lastib));

		for(int j=1;j<=lenb;j++){

			lastib[b[j]-'a'+1]=j;

			memset(lastic,0,sizeof(lastic));

			for(int k=1;k<=lenc;k++){

				lastic[c[k]-'a'+1]=k;

				for(int d=1;d<=26;d++){

					int ai=lastia[d],bi=lastib[d],ci=lastic[d];

					if(!ai||!bi||!ci)continue;

					f[i][j][k]+=f[ai-1][bi-1][ci-1]+1;

					//利用容斥原理，反正就是把各种情况分别揪出来

					//一共有26种，也就是分别以26种英文字母结尾

					//而且没揪出来一种就额外多增加一种子串——原来重复的字母+1

					//并且以前被更新过的数组不会被重复更新

					//这是递推

				}

			}

		}

	}

	cout<<f[lena][lenb][lenc];

	return 0;

}

4.图论

4.1 Tarjan（强连通分量）

https://www.luogu.com.cn/problem/P4306

注意：

最后计算总数的时候要给点边计算边染色，否则会出现有两个点都连接到同一个

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<stack>

#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

const int N=2010;

int n,cnt,tot,head[N],sizei[N],belong[N],vis[N],low[N],dfn[N],ind;

int cnti,headi[N],ru[N],fin[N];

struct node{

	int from,to,next;

}a[N*N],ai[N*N];

stack<int>stacki;

inline int read(){

	int s=0,w=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){

		if(ch=='-')w=-1;

		ch=getchar();

	}

	while(ch<='9'&&ch>='0'){

		s=s*10+ch-'0';

		ch=getchar();

	}

	return s*w;

}

inline void add(int u,int v){

	++cnt;

	a[cnt].from=u;

	a[cnt].to=v;

	a[cnt].next=head[u];

	head[u]=cnt;

}

inline void addi(int u,int v){

	++cnti;

	ai[cnti].from=u;

	ai[cnti].to=v;

	ai[cnti].next=headi[u];

	headi[u]=cnti;

}

inline void Tarjan(int x){

	low[x]=dfn[x]=++ind;

	stacki.push(x);

	vis[x]=1;

	for(int i=head[x];i;i=a[i].next){

		int v=a[i].to;

		if(!dfn[v]){

			Tarjan(v);

			low[x]=min(low[x],low[v]);

		}else if(vis[v])low[x]=min(low[x],dfn[v]);

	}

	int k=0;

	if(low[x]==dfn[x]){

		++tot;

		do{

			k=stacki.top();stacki.pop();

			vis[k]=0;

			belong[k]=tot;

			++sizei[tot];

		}while(k!=x);

	}

}

inline void dfs(int x,int fa){

	fin[x]=sizei[x];

	for(int i=headi[x];i;i=ai[i].next){

		int v=ai[i].to;

		if(v==fa)continue;

		if(vis[v])continue;

		vis[v]=1;

		dfs(v,x);

		fin[x]+=fin[v];

	}

}

int main(){

	n=read();

	for(int i=1;i<=n;i++){

		string s;cin>>s;

		for(int j=1;j<=n;j++)if(s[j-1]=='1')add(i,j);

	}

	for(int i=1;i<=n;i++)if(!dfn[i])Tarjan(i);

	/*cout<<"belong "<<endl;

	for(int i=1;i<=n;i++)cout<<belong[i]<<" ";cout<<endl;

	cout<<"sizei "<<endl;

	for(int i=1;i<=tot;i++)cout<<sizei[i]<<" ";cout<<endl;

	cout<<"addi "<<endl;*/

	for(int i=1;i<=cnt;i++)

	if(belong[a[i].from]!=belong[a[i].to])

	addi(belong[a[i].from],belong[a[i].to]),++ru[belong[a[i].to]];//,cout<<belong[a[i].from]<<" "<<belong[a[i].to]<<endl;

	//if(cnti==0)return cout<<n*n,0;

	//cout<<"ru "<<endl;

	//for(int i=1;i<=tot;i++)cout<<ru[i]<<" ";cout<<endl;

	memset(vis,0,sizeof(vis));

	for(int i=1;i<=tot;i++)if(!ru[i])dfs(i,i);

	int ans=0;

	//cout<<"fin "<<endl;

	for(int i=1;i<=tot;i++)ans+=fin[i]*sizei[i];//,cout<<fin[i]<<" ";cout<<endl;

	cout<<ans;

	return 0;

}

/*

5

01000

00110

10000

00000

00010

ans 15

*/

4.2 DFS

https://www.luogu.com.cn/problem/P3848

对于暴搜，我选择把它转化成图再暴搜/斜眼笑/手动狗头

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cmath>

#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

const int N=1e4+10;

int n,start,endi,cnt,top,head[N],id[110][110],mapi[110][110],vis[N];

long long ans;

struct node{

	int to,next,val;

}a[N*200];

inline int read(){

	int s=0,w=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){

		if(ch=='-')w=-1;

		ch=getchar();

	}

	while(ch<='9'&&ch>='0'){

		s=s*10+ch-'0';

		ch=getchar();

	}

	return s*w;

}

inline void add(int u,int v,int w){

	++cnt;

	a[cnt].to=v;

	a[cnt].val=w;

	a[cnt].next=head[u];

	head[u]=cnt;

}

inline void dfs(int x,long long tot){

	ans=max(ans,tot);

	for(int i=head[x];i;i=a[i].next){

		int v=a[i].to;

		if(vis[v])continue;

		vis[v]=1;

		dfs(v,tot+a[i].val);

		vis[v]=0;

	}

}

int main(){

	n=read();start=read();endi=read();

	//cout<<"add "<<endl;

	for(int i=1;i<=n;i++){

		int lasti=0,x=0,y=0;

		for(int j=1;j<=n;j++){

			mapi[i][j]=read();

			if(!mapi[i][j])id[i][j]=++top;

			if(!mapi[i][j]&&!lasti)lasti=id[i][j],x=i,y=j;

			else if(!mapi[i][j]&&lasti){

				int val=abs(x-i)+abs(y-j);

				if(val<=1)goto aa;

				add(lasti,top,val);add(top,lasti,val);

				//cout<<lasti<<" "<<top<<" "<<val<<endl;

				aa:

				lasti=top,x=i,y=j;

			}

		}

	}

	for(int j=1;j<=n;j++){

		int lasti=0,x=0,y=0;

		for(int i=1;i<=n;i++){

			if(id[i][j]&&!lasti)lasti=id[i][j],x=i,y=j;

			else if(id[i][j]&&lasti){

				int val=abs(x-i)+abs(y-j);

				if(val<=1)goto bb;

				add(lasti,id[i][j],val);add(id[i][j],lasti,val);

				//cout<<lasti<<" "<<id[i][j]<<" "<<val<<endl;

				bb:

				lasti=id[i][j],x=i,y=j;

			}

		}

	}

	/*cout<<"id "<<endl;

	for(int i=1;i<=n;i++){

		for(int j=1;j<=n;j++)cout<<id[i][j]<<" ";

		cout<<endl;

	}

	cout<<endl;*/

	vis[id[start][endi]]=1;

	dfs(id[start][endi],0);

	cout<<ans;

	return 0;

}

2021.12.16 eleveni的刷题记录的相关教程结束。