比赛 20241021 评测结果 AAAAAAAAAA
题目名称 有机化学 最终得分 100
用户昵称 wdsjl 运行时间 0.051 s
代码语言 C++ 内存使用 3.59 MiB
提交时间 2024-10-21 10:22:53
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
#define For(i,l,r) for(register int i=l;i<=r;i++)
const int N = 300;
const int INF = 0x7f7f7f7f;
char s[N];

struct node{
	int idx;//记录点度数 
	int op;//点种类 
	int d;//记录最大度数 
}p[N];

vector <int> lnk[N];

int vis[N],d[N],n,ans,iok[N];

void dfs(int now){//深搜建图 
	if(now==n)return ;
	int to=now+1; 
	while(p[now].idx<p[now].d){
		while(iok[to])to++; 
		lnk[now].push_back(to);
		lnk[to].push_back(now);
		p[now].idx++; 
		p[to].idx++;
//		cout<<now<<" "<<to<<endl;
		dfs(to);
	} 
	if(p[now].d==p[now].idx)iok[now]=1;
	return ;
}

void init(){
	memset(iok,0,sizeof(iok));
	ans=0;
	n=strlen(s+1);
	memset(p,0,sizeof(p));
	memset(lnk,0,sizeof(lnk));
}

void bfs(int s){
	queue<int> q;
	memset(vis,0,sizeof(vis));
	For(i,1,n)d[i]=INF;
	d[s]=0;
	q.push(s);
	while(q.size()){
		int u=q.front();
		q.pop();
		if(vis[u])continue;
		vis[u]=true;
		for(auto v:lnk[u]){
			if(p[v].op==0)continue;
			if(d[v]>d[u]+1)d[v]=d[u]+1,q.push(v);
		}
	}
}

int main(){
	freopen("chemistryh.in","r",stdin);
	freopen("chemistryh.out","w",stdout); 
	while(cin>>(s+1)){
		init();
		For(i,1,n){
			p[i].op=s[i]=='C'?1:0;//1表示C
			p[i].d=s[i]=='C'?4:1;
		}
		dfs(1);
//		For(i,1,n)cout<<p[i].op;
//		cout<<"RRR"<<endl;
//		cout<<"------"<<endl; 
//		For(i,1,n){
//			for(auto v:lnk[i]){
//				cout<<v<<" ";
//			}
//			cout<<endl;
//		} 
		For(i,1,n){
			if(p[i].op){
				bfs(i);
//				cout<<i<<endl;
//				For(j,1,n)cout<<d[j]<<" ";
//				cout<<endl;
				For(j,1,n)if(d[j]!=0x7f7f7f7f)ans=max(ans,d[j]);	
			}
		}
		printf("%d\n",ans+1);
	}
	return 0;
}