比赛 |
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;
}