衔尾蛇

NC214948. 衔尾蛇

描述

光、对立和小红三个人在玩捉蛇游戏。
已知蛇有三种：红蛇、蓝蛇和绿蛇。蛇可以咬住自己的尾巴，形成衔尾蛇。每条蛇可以咬住自己的尾巴，也可以咬住别的蛇的尾巴。
一共有 $a\$ 条红蛇， $b\$ 条蓝蛇， $c\$ 条绿蛇。她们想知道一共可以形成多少种不同的衔尾蛇的环？

注：蛇可以不用全部用完。

输入描述

一行三个非负整数：、和

输出描述

一个整数，为方案的数量。

示例1

输入:

1 1 1

输出:

说明:

一条红蛇咬自己，一种方案。
一条蓝蛇咬自己，一种方案。
一条绿蛇咬自己，一种方案。
一条红蛇和一条蓝蛇互相咬对方的尾巴，一种方案。
一条红蛇和一条绿蛇互相咬对方的尾巴，一种方案。
一条绿蛇和一条蓝蛇互相咬对方的尾巴，一种方案。
三条蛇互相咬，红咬绿，绿咬蓝，蓝咬红，一种方案。
三条蛇互相咬，红咬蓝，蓝咬绿，绿咬红，一种方案。
一共8种方案。

示例2

输入:

1 0 0

输出:

说明:

一条红蛇咬自己，显然只有这一种方案。

示例3

输入:

3 0 0

输出:

说明:

一条红蛇咬自己，一种方案。

两条红蛇互相咬对方的尾巴，为一种方案。

三条红色互相咬，也是一种方案（1咬2的尾巴,2咬3的尾巴,3咬1的尾巴）

上次编辑到这里，代码来自缓存点击恢复默认模板

Python3 解法, 执行用时: 704ms, 内存消耗: 8856K, 提交时间: 2022-10-09 13:04:18


mp={}
ans=0
# a=b=c=0
def dfs(s):
    global ans
    global a
    global b
    global c
    t=""
    t=t+s+s
    flag=True
    for i in range(len(s)):
        q=t[i:i+len(s)]
        if mp.get(q,None):flag=False
    if flag==True:
        mp[s]=True
        ans+=1
    if a:
        a-=1
        dfs(s+"a")
        a+=1
    if b:
        b-=1
        dfs(s+"b")
        b+=1
    if c:
        c-=1
        dfs(s+"c")
        c+=1

data=list(map(int,input().strip().split()))
a,b,c=data
dfs("")
print(ans-1)

C++(clang++11) 解法, 执行用时: 182ms, 内存消耗: 8252K, 提交时间: 2021-04-08 15:34:04

#include<bits/stdc++.h>
using namespace std;
unordered_map<string,bool>mp;
int a,b,c,ans=0;
void dfs (string s){
	string t ="";
	t=t+s+s;
	bool flag=true;
	for(int i=0;i<s.length();++i){
		string q=t.substr(i,s.length());
		if(mp[q]==true)	flag=false;
	}
	if(flag==true){
		mp[s]=true;
        ans++;
	}
	if(a){
		a--;
		dfs(s+"a");
		a++;
	}
	if(b){
		b--;
		dfs(s+"b");
		b++;
	}
	if(c){
		c--;
		dfs(s+"c");
		c++;
	}
}
int main(){
	cin>>a>>b>>c;
	dfs("");
	cout<<ans-1<<"\n";
	return 0;
}