非全对版本！！！

今天开始进阶国赛题目，发现国赛题目纯靠暴力好难拿分啊~还是得有那种思维才行>_>

第一题：0新型锁 - 蓝桥云课

这个题目一看就是用暴力dfs枚举，但是要枚举太多了个，所以肯定超时得不到答案

然后题目当中有个条件---lcm(a[i],a[i+1])=2025

又2025 = 3⁴ × 5²，设数 x = 3^p × 5^q，其中 0≤p≤4, 0≤q≤2。

条件 LCM(x, y) = 2025 等价于：

max(p_x, p_y) = 4
max(q_x, q_y) = 2

也就是说有四种状态

#include<iostream>
using namespace std;
const int MOD=1e9+7;
const int N=2025; 
typedef long long ll;

int main()
{
    ll a=1,b=2,c=4,d=8;
    for(int i=1;i<=2024;i++)
    {
        ll na=(a+b+c+d)%MOD;
        ll nb=(a+c)*2%MOD;
        ll nc=(a+b)*4%MOD;
        ll nd=a*8%MOD;
        a=na;
        b=nb;
        c=nc;
        d=nd;
    }
    ll ans=(a+b+c+d)%MOD;
    cout<<ans<<endl;
    return 0;
}

第二题：0互质藏卡 - 蓝桥云课

题目即从 1 到 17600 中选出 2025 个数，任意两个数不能有公共质因子

第三题：0数字轮盘 - 蓝桥云课

找规律的题目

#include<iostream> 

using namespace std;
#define ll long long

int main( )
{	
    ios::sync_with_stdio(0);
	cin.tie(0);
	
	int T,n,k;
	cin>>T;
	while(T--){
		cin>>n>>k;
		k = k%n;
		if(k==0)cout<<0<<endl;
		else if((n-k)%2==0) cout<<(n-k)/2<<endl;
		else if((n-k+n)%2==0)cout<<(n-k+n)/2<<endl;
		else cout<<-1<<"\n";
		
	}
    
    
    return 0;
}

第四题：0斐波那契字符串 - 蓝桥云课

我的做法就是先递归出所有的字符串，然后在计算逆序对数量（用了后缀和）--运行超时（~_~）

只拿到了一分

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=35,MOD=1e9+7;
int t;
int n;
string s[N];
int main()
{
	cin>>t;
	s[1]="0";
	s[2]="1";
	for(int i=3;i<N;i++)
	{
		s[i]=s[i-2]+s[i-1];
	} 
	while(t--)
	{
		cin>>n;
		string x;
		x=s[n];
		//后缀和
		long long m=x.length();
		int b[m+2]={0};
		for(int i=m-1;i>=0;i--)
		{
			int y=x[i]-'0';
			b[i]=b[i+1]+(y==0?1:0);
		} 
		long long cnt=0;
		for(int i=0;i<=m-1;i++)
		{
			if((x[i]-'0')==1)
			{
				cnt=(cnt+b[i])%MOD;
			}
		}
		cout<<cnt<<endl; 
	}
	return 0;
} 

正确满血做法（在递归的过程当中直接就统计了）

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N=100010,MOD=1e9+7;
typedef long long ll;

ll one[N],zero[N],inv[N];

void init()
{
	one[1]=0;zero[1]=1;inv[1]=0;
	one[2]=1;zero[2]=0;inv[2]=0;
	for(int i=3;i<N;i++)
	{
		one[i]=(one[i-2]+one[i-1])%MOD;
		zero[i]=(zero[i-2]+zero[i-1])%MOD;
		inv[i]=(inv[i-2]+inv[i-1]+(one[i-2]*zero[i-1])%MOD)%MOD;
	}
 } 
 
int main()
{
	init(); 
	int t;
	cin>>t;
	int n;
	while(t--)
	{
		cin>>n;
		cout<<inv[n]%MOD<<endl;
	}
	return 0;
}

第五题：0项链排列 - 蓝桥云课

我一开始用的暴力dfs枚举方式解决（只通过1个测试点omg国赛果然要求更严格了?_?），我的暴力啊，再爱我一次吧，多给点分吧~

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=2000010;
int a,b,c;
char path[N];
bool flag=false;
int n;

bool check()
{
	int cnt=0;
	for(int i=1;i<n;i++)
	{
		if(path[i]!=path[i+1])
		{
			cnt++;
		}
	}
	if(cnt==c)flag=true;
	return cnt==c;
}

void dfs(int x)
{
	if(x>n)
	{
		if(check())
		{
			for(int i=1;i<=n;i++)
			{
				cout<<path[i];
			}
			exit(0); 
		} 
		return;
	}
	
	//位置放l还是q
	//放L
	if(a>0)
	{
		a--;
		path[x]='L';
		dfs(x+1);
		a++;
	} 
	if(b>0)
	{
		b--;
		path[x]='Q';
		dfs(x+1);
		b++;
	}
}

int main()
{
	cin>>a>>b>>c;
	n=a+b;
	dfs(1);
	if(!flag)
	{
		cout<<-1<<endl;
	}
	return 0;
} 

第六题：0蓝桥星数字 - 蓝桥云课

4分版：直接模拟

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100010;
typedef long long ll;

bool check(ll x)
{
	if(x<10)return false;
	int last=x%2;
	x/=10;
	while(x>0)
	{
		int cur=x%2;
		if(cur==last)return false;
		last=cur;
		x/=10;
	}
	return true;
}

int main()
{
	ll n;
	cin>>n;
	ll cnt=0;
	ll num=9;
	while(cnt<n)
	{
		num++;
		if(check(num))
		{
			cnt++;
		}
	}
	cout<<num<<endl;
} 

第七题：0翻倍 - 蓝桥云课

14分版：同样也是直接模拟，按照顺序然后依次翻倍直到大于前一个

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=200010;
int n;
ll a[N];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	
	ll cnt=0;
	ll cur_min=a[1];
	for(int i=2;i<=n;i++)
	{
		if(a[i]<cur_min)
		{
			ll need=cur_min;
			ll val=a[i];
			int k=0;
			while(val<need)
			{
				val*=2;
				k++;
			}
			cnt+=k;
			cur_min=val;
		}
		else
		{
			cur_min=a[i];
		}
	} 
	cout<<cnt<<endl;
	return 0;
	
}
 

第八题：0近似回文字符串 - 蓝桥云课

暴力dfs只对了一个样例，其他都超时了

这个题目即长度为 n 的字符串 S，满足：

1. S 不是回文
2. 删掉一个字符后，存在一种删法使其变成回文

即先构造一个回文字符串在破环它，即先构造长度为n-1的回文字符串-》长度为n-1的回文字符串数量为26^⌈(n-1)/2⌉

再插入一个字符使其不为回文--》n-1的字符串，可以插入（n-1）+1个位置，每个位置可插入26中的一个--》共26*n种方法

然后再减去插入后仍为回文的字符串

故=回文串数×(总插入−保持回文) =26^⌈(n-1)/2⌉*（26*n-n）;

第九题：0子串去重 - 蓝桥云课

直接模拟通过了2/3的样例

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=100010;
string s;
int m;
int x_1,y_1,x_2,y_2;
string s1,s2;
int b[26]; 
int ans=0;
int main()
{
	cin>>s;
	cin>>m;
	while(m--)
	{
		ans=0;
		cin>>x_1>>y_1>>x_2>>y_2;
		s1.clear();
		memset(b,0,sizeof b);
		for(int i=x_1-1;i<=y_1-1;i++)
		{
			if(b[s[i]-'a']>=1)continue;
			else
			{
				s1.push_back(s[i]);
				b[s[i]-'a']++;
			}
		}
		s2.clear();
		memset(b,0,sizeof b);
		for(int i=x_2-1;i<=y_2-1;i++)
		{
			if(b[s[i]-'a']>=1)continue;
			else
			{
				s2.push_back(s[i]);
				b[s[i]-'a']++;
			}
		}
		int k=s1.length();
		int t=s2.length();
		ans=abs(k-t);
		for(int i=0;i<min(k,t);i++)
		{
			if(s1[i]!=s2[i])ans++;
		}
		cout<<ans<<endl;
	}
	return 0;
} 

第十题：0涂格子 - 蓝桥云课