C语言

1.数字与字符的相互转换

将整型数字转换为字符：

char a;
int b=9;
a=b+'0';

将字符转换为整型数字：

int a;
a='x'-'0';

递归

斐波那契数列

#include<stdio.h>
int fibonacci(int n);
int main()
{
	int n,result;
	scanf("%d",&n);
	
	result=fibonacci(n);
	
	printf("%d",result);
	
	return 0;
}
int fibonacci(int n)
{
	if(n<0) return 0;
	if(n==1||n==2) return 1;
	
	else{
		return fibonacci(n-1)+fibonacci(n-2);
	}
}

n的阶层

/*使用递归求N的阶层*/ 
#include<stdio.h>
double dfs(int n);
int main()
{
	int n;
	scanf("%d",&n);
	
	double result=dfs(n);
	
	printf("%.0f",result);
	
	return 0;
}
double dfs(int n)
{
	if(n>0)  return n*dfs(n-1);
	
	else return 1;//注意使return 1，而不是return 0
}

全排列问题：

解释：

abc acb bac bca cab cba

第一次全排列时，在第一个位置每个元素都会出现一次，再对该位置后的元素重新全排列，这是一种全排列的思想

/*对N个数进行全排列,并打印出来*/

#include<stdio.h>
void dfs(char a[],int begin);//声明自定义函数，因为是打印，所以函数类型为void 

int main()
{
	char a[]="abc";
	dfs(a,0);
	
	return 0;
}

void dfs(char a[],int begin)
{
	int i,j;
	
	if(begin==2){
		for(j=0;j<3;j++){
		printf("%c ",a[j]);}
	printf("\n");
	}//当对最后一个元素交换时，就完成了一次全排列，就可以打印出结果 
	
	//begin:记录当前全排列的首位置 
	for(i=begin;i<3;i++)
	{
		int temp;
		//每个元素都可以出现在首位置一次 
		temp=a[begin];a[begin]=a[i];a[i]=temp;
		
		dfs(a,begin+1);//对首位置后的元素进行全排列 
		
		temp=a[begin];a[begin]=a[i];a[i]=temp;//回溯 
			
	}
}

递归实现随机取数

/*从 1～n这n个整数中随机选取任意多个，输出所有可能的选择方案*/
#include<stdio.h>
void dfs(int n,int begin);
int state[15];//记录整数的当前状态，state[]=0表示不取，state[]=1表示取
int main()
{
	int n;
	
	printf("Enter n:");
	scanf("%d",&n);
	
	dfs(n,1);
	
	return 0;
}
void dfs(int n,int begin)
{
	int i;
	
	if(begin>n){
		for(i=1;i<=n;i++){
			if(state[i]==1)printf("%d ",i);
		}
		printf("\n");
		return;
	}
	
	
	dfs(n,begin+1);//不取
	
	state[begin]=1;//取
	dfs(n,begin+1);
	state[begin]=0;//回溯
	
}

递归实现组合枚举2

//从1~n这n个数中选m个数，输出所有可能的方案
#include<stdio.h>
int n,m;//	n:所有数	m:要选取的数 
int way[30]; 
//way[100]:储存方案，start：当前所选的数，st:当前位置 
void dfs(int st,int start);
int main()
{
	scanf("%d%d",&n,&m);
	
	dfs(1,1);
	
	return 0;
}

void dfs(int st,int start)
{
	int i;
	if(n-start+st<m) return;
	if(st==m+1){
		for(i=1;i<=m;i++){
			printf("%d ",way[i]);
		}
		printf("\n");
		return;
	}
	for(i=start;i<=n;i++){
		way[st]=i;
		dfs(st+1,i+1);
		way[st]=0;//恢复现场 
	}
} 

bfs(宽松)：从初始状态变到目标状态

1.八数码

飞行员兄弟（开关问题）

题目描述：

“飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有 1616 个把手的冰箱。

已知每个把手可以处于以下两种状态之一：打开或关闭。

只有当所有把手都打开时，冰箱才会打开。

把手可以表示为一个 4×44×4 的矩阵，您可以改变任何一个位置 [i,j][�,�] 上把手的状态。

但是，这也会使得第 i� 行和第 j� 列上的所有把手的状态也随着改变。

请你求出打开冰箱所需的切换把手的次数最小值是多少。

输入格式

输入一共包含四行，每行包含四个把手的初始状态。

符号 + 表示把手处于闭合状态，而符号 - 表示把手处于打开状态。

至少一个手柄的初始状态是关闭的。

输出格式

第一行输出一个整数 N�，表示所需的最小切换把手次数。

接下来 N� 行描述切换顺序，每行输出两个整数，代表被切换状态的把手的行号和列号，数字之间用空格隔开。

注意：如果存在多种打开冰箱的方式，则按照优先级整体从上到下，同行从左到右打开。

数据范围

1≤i,j≤41≤�,�≤4

输入样例：

-+--
----
----
-+--

输出样例：

6
1 1
1 3
1 4
4 1
4 3
4 4

//一个把手改变，会使所在行列的所有把手全部反转
//特点：①在最优解里面每个把手只按一次，按两次没有区别，
//②按的顺序无关紧要，最终取决于这个把手按的次数！！！
//思考这个题可以递推出来吗？  答案是：很难
//可以想一想，前面的题都是通过某种顺序，每一次都是影响一个灯泡，但是这个题
//不能使用前面的办法，因为操作一次会影响好多灯泡。所以想一想朴素做法

//我们发现这个题的数据范围很小，所以尝试用暴力解决ac
//暴力思路：①16个开关，所有开关的状态数量想一想是多少？ 答案是2^16！这个我感觉
//我这么笨还是可以想出来的，往后怎么想呢？
//状态数量即最大操作次数2^16（65536）,既然也不大，那就①枚举所有的方案，
//然后按照这个方案来操作
//②如果可以实现把手全开，证明此方案合法
//③然后统计这个方案里面需要操作的把手数量
//④在所有能按的开关数量里取一个最小值
//ac
//输出方案注意:若两种方案步数相同，按字典序（先按横坐标排序，再按纵坐标排序）


#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>

//这个宏定义其实也就最后输出的时候应用了（如果我没猜错的话），但是y总的习惯就是好习惯！
#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;

const int N=5;

char g[N][N],backup[N][N];


//映射函数
int get(int x,int y)
{
    return x*4+y;//返回第x行第y列上的数是多少
}

void turn_one(int x,int y)
{
    if(g[x][y]=='+') g[x][y]='-';
    else g[x][y]='+';
}

void turn_all(int x,int y)
{
    for(int i=0;i<4;i++)
    {
        turn_one(x,i);
        turn_one(i,y);
    }
    turn_one(x,y);

}

int main()
{
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            cin>>g[i][j];

    vector<PII> res;//这是记录方案所需要的结构

    //枚举所有的方案
    for(int op=0;op<1<<16;op++)
    {
        vector<PII> temp;//temp里面存的是方案
        //先备份一下，为什么？因为这又不是最终方案，我们要把所有方案都试一遍，求最少的
        memcpy(backup,g,sizeof g);

        //枚举16个位置,进行操作
        for(int i=0;i<4;i++)
            for(int j=0;j<4;j++)
                if(op>>get(i,j)&1) //如果当前位置是1的话--get的作用就是返回二进制数中那一位是第几位，从而判断是否为1
                {
                    temp.push_back({i,j});
                    //按一下开关
                    turn_all(i,j);
                }


        //判断所有灯泡是否全亮
        bool has_closed=false;
        for(int i=0;i<4;i++)
            for(int j=0;j<4;j++)
                if(g[i][j]=='+') has_closed=true;

        if(has_closed==false)
        {
            //如果方案为空或者他的操作数大于我们刚存好的新的方案，那么就修改它
            if(res.empty()||res.size()>temp.size()) res=temp;
        }
        //还原回来，供下一个方案操作
        memcpy(g,backup,sizeof g);
    }
    //因为没说无解，所以可以猜想一下一定有解
    cout<<res.size()<<endl;
    //这里的迭代函数就是一种简便写法，不要误解
    //另外原题下标从1开始，所以下面加1了
    for(auto op:res) cout<<op.x+1<<" "<<op.y+1<<endl;

    return 0;
}

作者：山雾
链接：https://www.acwing.com/solution/content/80128/

思路：使用暴力枚举的方法，将所有的方案以二进制的形式枚举出来，然后对每个方案进行操作并判断，最后得出最优方案

递归与递推

AcWing 92. 递归实现指数型枚举

题目：

从 1∼n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。

输入格式
输入一个整数 n。

输出格式
每行输出一种方案。

同一行内的数必须升序排列，相邻两个数用恰好 1 个空格隔开。

对于没有选任何数的方案，输出空行。

本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。

数据范围
1≤n≤15
输入样例：
3
输出样例：

3
2
2 3
1
1 3
1 2
1 2 3

代码实现：

//递归实现指数型枚举
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 16;
bool state[N];//false表示不选，true表示选 
int n;

void dfs(int u){
	//找到出口，输出方案 
	if(u>n){
		for(int i=1;i<=n;i++){
			if(state[i]) cout << i << ' ';
		}
		puts("");
		return;
	}
	
	//分支行动，选或者不选 
	
		//不选 
		dfs(u+1);
		//选 
		state[u]=true;
		dfs(u+1);
		state[u]=false;//返回现场 
		
}
int main()
{
	cin >> n;
	
	dfs(1);
	
	return 0;
} 

AcWing 94. 递归实现排列型枚举

题目：

题目描述

把 1~n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。

输入格式

一个整数n。

输出格式

按照从小到大的顺序输出所有方案，每行1个。

首先，同一行相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。

数据范围

1≤n≤9

输入样例

3

输出样例

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

代码实现：

//递归实现排列型枚举
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 15;
int n;
int way[N];//记录方案 
bool state[N];//判重数组，false表示没用过，true表示用过 

void dfs(int u){
	
	//找边界，输出方案 
	if(u>n){
		for(int i=1;i<=n;i++)
			cout << way[i] << ' ';
			
	puts("");
	return;
	}
		//遍历1~n,没有用过则将该数存入方案 
		for(int i=1;i<=n;i++){
			if(!state[i]) {
			way[u]=i;
			state[i]=true;
		
			dfs(u+1);//深度搜索 
			
			//还原现场 
			way[u]=0;
			state[i]=false;
			}
		}
		
}

int main()
{
	cin >> n;
	
	dfs(1);
	
	return 0;
}

AcWing 93.递归实现组合型枚举

题目：

从 1∼n1∼� 这 n� 个整数中随机选出 m� 个，输出所有可能的选择方案。

输入格式

两个整数 n,m�,� ,在同一行用空格隔开。

输出格式

按照从小到大的顺序输出所有方案，每行 11 个。

首先，同一行内的数升序排列，相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 1 3 5 7 排在 1 3 6 8 前面）。

数据范围

n>0 ,
0≤m≤n ，
n+(n−m)≤25

输入样例：

5 3

输出样例：

1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5 

代码实现

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 30; 
int way[N];
int n,m;
//u:当前位置	start:当前位置头一个数 
void dfs(int u,int start){
	
	if(u>m){
	for(int i=1;i<=m;i++) cout << way[i] << " ";
	puts("");
	return;
	}
	
	for(int i=start;i<=n;i++){
		way[u]=i;
		dfs(u+1,i+1);
		way[i]=0;//恢复现场 
	}
}

int main()
{
	cin >> n >> m;
	
	dfs(1,1);
	
	return 0;
}

AcWing1209. 带分数

题目内容
100可以表示为带分数的形式：100=3+69258714

还可以表示为：100=82+3546197

注意特征：带分数中，数字 1∼9分别出现且只出现一次（不包含 0）。

类似这样的带分数，100有 11种表示法。

输入格式

一个正整数。

输出格式

输出输入数字用数码 1∼9不重复不遗漏地组成带分数表示的全部种数。

数据范围
1 ≤ N < 106 1≤N<1061≤N<106

样例
输入样例1

100

输出样例1

11

输入样例2

105

输出样例2

6

代码实现：

Acwing95. 费解开关

题目：

你玩过“拉灯”游戏吗？

25盏灯排成一个 5×5 的方形。

每一个灯都有一个开关，游戏者可以改变它的状态。

每一步，游戏者可以改变某一个灯的状态。

游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字 1表示一盏开着的灯，用数字 0表示关着的灯。

下面这种状态

10111
01101
10111
10000
11011
在改变了最左上角的灯的状态后将变成：

01111
11101
10111
10000
11011
再改变它正中间的灯后状态将变成：

01111
11001
11001
10100
11011
给定一些游戏的初始状态，编写程序判断游戏者是否可能在 6 步以内使所有的灯都变亮。

输入格式

第一行输入正整数 n，代表数据中共有 n 个待解决的游戏初始状态。

以下若干行数据分为 n组，每组数据有 5行，每行 5 个字符。

每组数据描述了一个游戏的初始状态。

各组数据间用一个空行分隔。

输出格式

一共输出 n行数据，每行有一个小于等于 6的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。

对于某一个游戏初始状态，若 6步以内无法使所有灯变亮，则输出 −1。

数据范围

0<n≤5000

输入样例：

3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111
输出样例：

3
2
-1

代码实现

#include <bits/stdc++.h>
using namespace std;

char g[6][6],backup[6][6];
//数据偏移量，左、右、上、下、本身 
int dx[5]={-1,1,0,0,0}; int dy[5]={0,0,1,-1,0}; 

void turn(int x,int y){
	for(int i=0;i<5;i++){
		int a=x+dx[i]; int b=y+dy[i];
		//if(g[a][b]=='0') g[a][b]='1';
		//else g[a][b]='0';
		if(a<0||a>4||b<0||b>4) continue; //边界外，跳出循环 
		g[a][b]^=1;//异或操作，将（a,b)取反 
	}
}

int main(){
	int n;
	scanf("%d",&n);
	
	while(n--){
		for(int i=0;i<5;i++) cin >> g[i];//输入初始状态的二维数组
		int res=7;
		//对第一行进行二进制枚举,每一个op的二进制数代表一个方案 
		for(int op=0;op<32;op++){
			
			int step=0;//按灯的步骤数 
			memcpy(backup,g,sizeof g);//备份 
			
			//对第一行进行操作，遍历op二进制的各个位数 
			for(int i=0;i<5;i++){
				if(op>>i&1){//判断op右移i位的那个数是否是1，是就按灯 
					step++;
					turn(0,4-i); 
				}
			}
			
			//对前4行字符进行操作 
			for(int i=0;i<4;i++){
				for(int j=0;j<5;j++){
					if(g[i][j]=='0'){
						step++;
						turn(i+1,j);
					}
				}
			}
			
			//判断最后一行每盏灯的状态 
			bool dark=false; 
			for(int i=0;i<5;i++){
				if(g[4][i]=='0'){
					dark=true;
					break;
				}
			}
			if(!dark) res=min(res,step);
			memcpy(g,backup,sizeof backup);//还原 
		}
		
		if(res>6) res=-1;
		
		cout << res << endl;
	}
	
	return 0;
}

详解见https://blog.csdn.net/weixin_45662399/article/details/123607593

二分与前缀和

二分和模板

AcWing789.数的范围

题目描述
给定一个按照升序排列的长度为 n
的整数数组，以及 q
个查询。

对于每个查询，返回一个元素 k
的起始位置和终止位置（位置从 0
开始计数）。

如果数组中不存在该元素，则返回 -1 -1。

输入格式
第一行包含整数 n
和 q
，表示数组长度和询问个数。

第二行包含 n
个整数（均在 1∼10000
范围内），表示完整数组。

接下来 q
行，每行包含一个整数 k
，表示一个询问元素。

输出格式
共 q
行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回 -1 -1。

数据范围
1≤n≤100000

1≤q≤10000

1≤k≤10000

样例
输入样例：
6 3
1 2 2 3 3 4
3
4
5
输出样例：
3 4
5 5
-1 -1

#include<bits/stdc++.h>
using namespace std;
int a[100010];
int main(){
	int n,q;
	scanf("%d %d",&n,&q);
	for(int i=0;i<n;i++) scanf("%d",&a[i]);
	
		while(q--){
		int k;
		scanf("%d",&k);
		//二分左端点 
		int l=0,r=n-1;
		while(l<r){
			int mid=(l+r)/2;
			if(a[mid]>=k) r=mid;
			else l=mid+1;
		}
		
		
		if(a[l]!=k){
		printf("-1 -1\n");
		continue;
		}
		else printf("%d ",l);
			
		l=0,r=n-1;
		//二分右端点 
		while(l<r){
			int mid=(l+r+1)/2;
			if(a[mid]<=k) l=mid;
			else r=mid-1;
		}
		printf("%d\n",l);
		
	}
	
	return 0;	
}

AcWing790.数的三次方根

#include<bits/stdc++.h>

using namespace std;

int main(){
	double n;
	scanf("%lf",&n);
	
	double l=-100,r=100;
	while((r-l)> 1e-8 ){
		double mid=(l+r)/2;
		if(mid*mid*mid>n) r=mid;
		else l=mid;
	}
	
	printf("%lf",l);
	
	return 0;
}

tip:cbrt()计算立方根

数学与简单DP

dp——蓝桥杯算法印章

https://codeleading.com/article/98736171731/

https://www.yii666.com/blog/397106.html

枚举、模拟与排列

代码模板

基础算法 —— 代码模板链接 常用代码模板1——基础算法

排序
二分
高精度
前缀和与差分
双指针算法
位运算
离散化
区间合并

数据结构 —— 代码模板链接 常用代码模板2——数据结构

链表与邻接表：树与图的存储
栈与队列：单调队列、单调栈
kmp
Trie
并查集
堆
Hash表
搜索与图论 —— 代码模板链接 常用代码模板3——搜索与图论

DFS与BFS
树与图的遍历：拓扑排序
最短路
最小生成树
二分图：染色法、匈牙利算法
数学知识 —— 代码模板链接 常用代码模板4——数学知识

质数
约数
欧拉函数
快速幂
扩展欧几里得算法
中国剩余定理
高斯消元
组合计数
容斥原理
简单博弈论

拓展知识：

sort函数的使用：

sort(begin,end);默认升序排序

sort(begin,end,compare);可以选择降序排序

bool compare(int a,int b){
	return a<b;
	//return a>b则是降序排序
}

详解：https://blog.csdn.net/m0_53176241/article/details/127931860

pow()函数

返回值是double类型，使用时注意类型转换

strlen()函数

获取字符串函数

字符串输入

char a[110];

scanf("%s",a);
或者
char a[110];
cin>>a;		//遇空格、tab、回车就结束

reverse()函数

一、反转数组

1翻转数组

//头文件
#include <algorithm>
//使用方法
reverse(a, a+n);//n为数组中的元素个数

2翻转字符串

//用法为
reverse(str.begin(), str.end());

abs()函数

对整数int long long long 取绝对值

strcpy()函数

strcpy(str1,str2):将数组str2复制到数组str1中

可以利用到数组交换中

char str1,str2,str_[110];
		strcpy(str_,str1);
		strcpy(str1,str2);
		strcpy(str2,str_);

问题描述

　　对于一个 n 行 m 列的矩阵，它的一个 k 行 k 列的子矩阵是指由矩阵中的连续 k 行、连续 k 列组成的矩阵。
　　子矩阵的和是指子矩阵中所有元素的和。现在，小蓝对于一个矩阵中的子矩阵中最大的子矩阵的和很感兴趣。
　　例如，对于如下 3 行 4 列的矩阵，2 行 2 列的子矩阵的和的最大值是 8，对应的子矩阵为由最后两行最后两列组成的子矩阵。
　　2 0 2 3
　　1 1 0 1
　　1 2 3 4
　　现在，小蓝有一个 30 行 20 列的大矩阵，如下所示，请问它的 5 行 5 列的子矩阵的和的最大值是多少？
　　9719 7515 5916 6467 7157 9614 8560 9075 2099 2838 1403 7652 6238 1699 8907 1804 5384 7942 7546 1978
　　8785 1944 8108 6040 2010 6646 2750 5410 4516 8757 5624 9257 9030 9290 6833 4646 9749 5304 5633 1573
　　8525 8244 8514 7474 7896 9731 8402 9036 1869 2688 2085 1667 7753 8466 4911 3812 8585 8319 4020 7350
　　1949 9120 4424 4057 8277 4511 6333 1533 7624 8932 1053 8682 9284 4134 1466 3607 8753 5310 3728 4163
　　9420 9185 7055 2342 4143 4499 2036 5374 7026 8638 8866 8364 1706 8767 1601 8309 5695 8179 4142 8489
　　5876 5660 4658 8307 2582 7544 8793 8207 3979 1692 1400 1893 4500 6389 7198 4836 4761 6603 2859 1312
　　6367 4174 9956 6668 6771 4795 6492 3937 7096 8041 8644 9379 8071 8667 5810 5794 8147 3823 7877 4822
　　4809 3297 8518 4972 9754 6854 3271 7891 8882 1052 3197 6035 5628 7674 7931 8085 8970 7733 4745 8785
　　7536 1511 6964 4763 5409 7032 8963 8576 3411 5853 3316 1267 7851 2735 6953 2970 1810 6830 5576 6903
　　2241 1575 2379 4679 9519 9290 4802 1562 3509 8365 6777 5143 5610 1061 7880 1935 5793 7023 5629 9571
　　2480 5937 4612 8890 1964 8532 3309 9737 8507 1849 8544 1500 9282 6288 2137 4730 4239 3473 4643 6377
　　7341 2881 3430 5815 1972 6629 3817 4547 7561 4779 6578 6114 4972 5505 7515 1800 4784 2272 4502 7541
　　7665 8607 2022 8192 2605 1346 4155 8725 8167 7022 6136 3615 6057 6329 8671 2033 3151 2249 5981 6412
　　9046 3353 8650 6965 4179 1248 5659 5219 8083 5615 3821 4436 9217 7356 3914 5717 3734 3765 4435 7210
　　8951 5013 2951 7401 2329 5686 6530 9581 6539 6881 8634 2663 2916 3019 8529 5645 8201 9270 1939 7275
　　6429 1531 6322 9586 2793 7968 4001 9665 7624 4369 6245 5146 9567 6801 6064 6199 3210 6753 2586 7795
　　5771 8507 7973 1470 1475 6896 6781 6572 8412 8557 8255 5268 8960 7251 9214 2489 6920 9917 3810 4605
　　9116 7950 3715 1697 4703 2868 8673 3106 2579 1074 3992 3547 4279 3149 3396 6081 6221 1125 9358 2471
　　8360 1526 4116 9278 6325 5175 5533 4107 7522 7599 7711 9211 1752 2431 8321 3844 3579 1047 3987 8487
　　7600 2401 8748 8945 2078 1519 4614 4576 5706 4040 9358 1928 1327 6699 5258 2846 3418 8310 1249 3866
　　7796 8668 4087 4258 8992 8996 4617 5997 2527 8204 8927 1456 9340 2088 1605 2299 9878 8347 7789 2122
　　8372 1102 4243 4208 1651 7861 4947 7802 4704 6204 4455 6012 8494 9060 3747 2786 2136 1830 7424 8309
　　6919 4420 2031 5399 2652 7219 4048 7013 5094 5276 4225 5976 4157 6722 8765 4679 1604 4986 5033 2623
　　4015 2297 3067 6261 6623 4577 4589 4747 6659 7667 7853 4040 6393 9606 7219 9334 1316 3430 9963 5187
　　4998 3735 9884 2990 1374 8436 6674 3018 5714 9352 8708 8789 7879 2965 1444 4671 4743 9817 6066 8057
　　6996 9609 2884 4601 7287 3432 4145 8858 6857 8624 4531 6579 1615 2894 4521 3274 5237 1093 3317 9289
　　7117 1850 3210 8010 2512 1394 4718 9332 5593 4118 4995 3994 5063 9426 1709 5128 4997 9287 1907 9068
　　4258 7328 6490 2603 5333 5093 8070 2116 8489 1994 7098 7409 1463 4268 9509 2358 1192 2460 5031 6292
　　4911 1192 1012 2494 5276 8981 3540 3306 8869 6678 7879 7526 8847 6270 7653 3109 6955 9760 8520 8673
　　6328 7277 7818 3285 9398 4929 4639 1617 4023 1051 9320 4955 6580 6481 3824 9611 2863 6492 6281 6203

答案提交

　　这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

问题描述

　　小蓝要上一个楼梯，楼梯共有 n 级台阶（即小蓝总共要走 n 级）。小蓝每一步可以走 1 级、2 级或 3 级台阶。
　　请问小蓝至少要多少步才能上到楼梯顶端？

输入格式

　　输入一行包含一个整数 n 。

输出格式

　　输出一行包含一个整数，表示答案。

样例输入

9

样例输出

3

样例输入

10

样例输出

4

评测用例规模与约定

　　对于所有评测用例，1 <= n <= 10000 。

问题描述

　　给定一个仅包含数字字符的字符串，请统计一下这个字符串中出现了多少个值为奇数的数位。

输入格式

　　输入一行包含一个字符串，仅由数字字符组成。

输出格式

　　输出一行包含一个整数，表示答案。

样例输入

123455

样例输出

4

样例输入

111222333111222333111222333

样例输出

18

评测用例规模与约定

　　对于所有评测用例，1 <= 字符数量 <= 10000 。

问题描述

　　对于一个序列 a[1], a[2], …, a[n]，如果 a[i] 满足 a[i]<a[i-1] 且 a[i]<a[i+1]，则称 a[i] 是一个极小值，如果如果 a[i] 满足 a[i]>a[i-1] 且 a[i]>a[i+1]，则称 a[i] 是一个极大值。
　　给定一个序列，请找到极小值中最大的和极大值中最小的。

输入格式

　　输入的第一行包含一个整数 n ，表示序列的长度。
　　第二行包含 n 个整数，相邻的整数之间使用一个空格分隔，表示给定的序列。

输出格式

　　输出一行包含两个整数，用一个空格分隔，分别表示极小值中最大的和极大值中最小的。输入保证至少存在一个极小值，至少存在一个极大值。

样例输入

8
1 8 2 4 4 3 5 3

样例输出

3 5

评测用例规模与约定

　　对于所有评测用例，1 <= n <= 1000，0 <= a[i] <= 10000。

问题描述

　　对于一个字符矩阵，其中的一些字符构成字母 Y 是指存在一个中间字符，从这个中间字符向下、向左上（45度）、向右上（45度）的字符都与中间的字符相同。
　　字母 Y 的长度指同时向 3 个方向的相同字母延伸的最大距离。
　　例如，下图中所有的 1 组成一个字母 Y，长度为 3。
　　又如，下图中以第 5 行第 6 列为中心也构成一个字母 Y （由字符 A 构成），长度为 1 。
　　再如，下图中以第 4 行第 3 列为中心也构成一个字母 Y （由字符 0 构成），长度为 2 。
　　1000001
　　0100010
　　0010100
　　0001AAA
　　00010A0
　　00010A0
　　00010A0
　　给定一个字符矩阵，请找出能构成字母 Y 的最大长度，如果无法构成字母 Y，请输出 0 。

输入格式

　　输入的第一行包含两个整数 n, m ，用一个空格分隔，表示字符矩阵的行数和列数。
　　接下来 n 行，每行包含 m 个字符，表示字符矩阵。

输出格式

　　输出一行包含一个整数，表示答案。

样例输入

7 7
1000001
0100010
0010100
0001AAA
00010A0
00010A0
00010A0

样例输出

3

评测用例规模与约定

　　对于50%的评测用例，1 <= n, m <= 100。
　　对于所有评测用例，1 <= n, m <= 1000，字符矩阵中仅包含数字字符和大写英文字母。

请选择编程语言

问题描述

　　小蓝要上一个楼梯，楼梯共有 n 级台阶（即小蓝总共要走 n 级）。小蓝每一步可以走 a 级、b 级或 c 级台阶。
　　请问小蓝总共有多少种方案能正好走到楼梯顶端？

输入格式

　　输入的第一行包含一个整数 n 。
　　第二行包含三个整数 a, b, c 。

输出格式

　　输出一行包含一个整数，表示答案。答案可能很大，请输出答案除以 1000000007 后的余数。

样例输入

4
1 2 3

样例输出

7

样例输入

7
2 4 6

样例输出

0

评测用例规模与约定

　　对于 30% 评测用例，1 <= a < b < c <= n <= 50。
　　对于 60% 评测用例，1 <= a < b < c <= n <= 1000。
　　对于所有评测用例，1 <= a < b < c <= n <= 1000000。

请选择编程语言