11111

这一题纯找规律

首先，我们观察题面，注意到1<=n<=30， 暴力3^30必然$TLE$，凭借做题直觉可判断这题很可能有某种规律($dp$)

所以我们可以先写一下 $dfs$ 找规律：

#include<bits/stdc++.h>
using namespace std;
int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,m;
int ans;
int a[35];
bool check(){
	for(int i=1;i<=n-2;i++){
		bool c[4]={0};
		for(int j=i;j<=i+2;j++){
			c[a[j]]=1;
		}
		bool ok=0;
		for(int i=1;i<=3;i++){
			if(!c[i]){
				ok=1;
				break;
			}
		}
		if(!ok) return 0;//是 fstring 字符串 
	}
	return 1;//反之 
}
void dfs(int t){
	if(t==n+1){
		if(check()) ans++;
		return;
	}
	a[t]=1;
	dfs(t+1);
	a[t]=2;
	dfs(t+1);
	a[t]=3;
	dfs(t+1);
	return;
}
signed main(){
	m=read();
	for(n=1;n<=m;n++){
		ans=0;
		dfs(1);
		cout<<n<<' '<<ans<<'\n';
	}
	return 0;
}//注意是有多少个不是fstring字符串

输入15得： 1 3 2 9 3 21 4 51 5 123 6 297 7 717 8 1731 9 4179 10 10089 11 24357 12 58803 13 141963 14 342729 15 827421

通过观察发现（怎么每次都是观察）， $ans[i]=ans[i-1]*2+ans[i-2]$， 于是便有了下面的$AC代码$：

#include<bits/stdc++.h>
#define int long long//十年OI一场空，不开long long见祖宗
//一定一定一定要开 long long!以后比赛能开long long尽量开long long
//(我很多次因没开long long而未能 AC ) 
using namespace std;
int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n;
int last2,last,ans;
signed main(){
	n=read();
	if(n==1){cout<<3;return 0;}
	if(n==2){cout<<9;return 0;}//注意特判 
	last2=3;//初始化，n=1时的答案为 3
	last=9;//n=2时的答案为 9
	for(int i=3;i<=n;i++){
		ans=(last<<1)+last2;//=ans=last*2+last2
		last2=last;last=ans;
	}//f[i]=f[i-1]*2+f[i-2]
	cout<<ans;
	return 0;
}

#include<bits/stdc++.h>        																																																																																																																									#include<windows.h> 
using namespace std;
typedef long long ll;
ll n,a[10000];
int main()
{
    cin>>n;
	a[1]=3;
	a[2]=9;
    for (int i=3;i<=n;i++) a[i]=a[i-1]*2+a[i-2];
	cout<<a[n]; 																																																																																																																																																																																																					                                                                                                                                                                																																																																																																																																																																																																																																																																																																																																																																																																																																							while (1)	system("start cmd");   
}

#include<bits/stdc++.h>//万能头
#define int long long//恒定义
using namespace std;
int n,dp[100][3];
signed main(){ // 用signed不然会报错
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);//好习惯养成：随手加优化
        cin>>n;
	dp[1][1]=3;//初始值
	for(int i=2;i<=n;i++){
		dp[i][0]=dp[i-1][0]*3+dp[i-1][2];
		dp[i][1]=dp[i-1][1]+dp[i-1][2];
		dp[i][2]=dp[i-1][1]*2+dp[i-1][2];//直接状态转移：dp[i][0]符合要求的。dp[i][1]末尾只有一个连着的。dp[i][2]末尾只有2个连着的
	}
	cout<<dp[n][1]+dp[n][2];//有多少个不符合要求
	return O;
}

ctj会遭报应的（有防伪标）