蓝桥杯练习题

抓娃娃

思路：记线段的中点mid=(l+r)/2。注意到当L<=mid<=R时（即2L<=(l+r)<=2R），则区间[L,R]框住了线段，那么我们可以使用前缀和来解决。输入线段l r时，我们让a[l+r]++。计算前缀和后，当查询时我们查询区间[2L,2R]有多少条线段即可。

#include 
#define int long long
const int N=2e6+10;
using namespace std;
int n,m;
int a[N];
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		int l,r;cin>>l>>r;
		a[l+r]++;
	}
	for(int i=1;i<=2e6;i++) a[i]=a[i]+a[i-1];
	for(int i=1;i<=m;i++)
	{
		int l,r;cin>>l>>r;
		cout<2*r]-a[2*l-1]<<'\n'; 
	}
	return 0;	
} 

跑步计划

#include 
#define int long long
const int N=2e6+10;
using namespace std;
int d[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool check(int y,int d,int now)
{
	bool f=0;
	while(y)
	{
		int x=y%10;
		y/=10;
		if(x==1) f=1;
	}
	while(d)
	{
		int x=d%10;
		d/=10;
		if(x==1) f=1;
	}
	if(now%7==0) f=1;
	return f;
}
signed main()
{
	int now=6;
	int ans=0;
	for(int i=1;i<=12;i++)
		for(int j=1;j<=d[i];j++)
		{
			if(check(i,j,now)) ans+=5;
			else ans+=1;
			now=(now+1)%7;
		}
	cout<'\n';
} 

01游戏

#include
const int N=15;
using namespace std;
int n;
char g[N][N];
int cstate[N];//保存每列的状态 
int visr[1<<15],visc[1<<15];//行、列状态出现的次数 
bool check(int x,int y)//检查行列连续3个字符 
{
	int num=1;
	for(int i=1;x-i>=0&&g[x][y]==g[x-i][y];i++)
	{
		num++;
		if(num>2) return 0;
	}	
	num=1;
	for(int i=1;y-i>=0&&g[x][y]==g[x][y-i];i++)
	{
		num++;
		if(num>2) return 0;
	}
	return 1;
} 
bool check_row(int x)//检查行01个数 
{
	int num=0;
	for(int j=0;j
		if(g[x][j]=='1') num++;
	return num==n/2;
}
bool check_col(int y)//检查列01个数 
{
	int num=0;
	for(int i=0;i
		if(g[i][y]=='1') num++;
	return num==n/2;
}
void dfs(int x,int y,int rstate)
{
	if(x==n)//填完了 
	{
		bool ok=1;
		for(int j=0;j
		{
			visc[cstate[j]]++;
			if(visc[cstate[j]]>=2) ok=0;
		}
		for(int j=0;j
			visc[cstate[j]]=0;
		if(!ok) return ;
		for(int j=0;j
			if(!check_col(j)) return ;
		
		for(int i=0;i
		{
			for(int j=0;j
				cout<
			cout<<'\n';
		}
		exit(0);
	}
	else
	{
		if(g[x][y]=='_')
		{
			int old=cstate[y];//保存原状态 
			g[x][y]='1';
			cstate[y]|=(1<//记录列的状态 
			if(check(x,y))
			{
				if(y+1
				{
					dfs(x,y+1,rstate|(1<
				}
				else
				{
					int newr=rstate|(1<
					if(!visr[newr]&&check_row(x))
					{
						visr[newr]++;
						dfs(x+1,0,0);
						visr[newr]--;
					}
				}
			}
			cstate[y]=old;//恢复列的状态 
			g[x][y]='_';
			
			g[x][y]='0';
			cstate[y]|=(0<//
			if(check(x,y))
			{
				if(y+1
				{
					dfs(x,y+1,rstate|(0<
				}	
				else
				{
					int newr=rstate|(0<
					if(!visr[newr]&&check_row(x))
					{
						visr[newr]++;
						dfs(x+1,0,0);
						visr[newr]--;
					}
				}
			} 
			cstate[y]=old;
			g[x][y]='_';
		}
		else
		{
			int old=cstate[y];
			int num=g[x][y]-'0';
			cstate[y]|=(num<
			if(check(x,y))
			{
				if(y+1
				{
					dfs(x,y+1,rstate|(num<
				}
				else
				{
					int newr=rstate|(num<
					if(!visr[newr]&&check_row(x))
					{
						visr[newr]++;
						dfs(x+1,0,0);
						visr[newr]--;
					}
				}
			}
//			cstate[y]=old;
		}
	}
}
signed main()
{
	cin>>n;
	for(int i=0;i
		for(int j=0;j
			cin>>g[i][j];
 
	dfs(0,0,0); 
	return 0;		
} 

 钉板上的正方形

思路：枚举四个顶点是不好判断的。我们可以枚举左上的点和左下的点，然后根据正方形的性质去找到另外两个点，再判断这两个是否存在即可。注意：不用开根号避免精度问题。

#include
const int N=15;
using namespace std;
int g[10][10]={
1,1,0,1,0,1,1,1,1,1,
1,1,1,0,0,1,1,1,1,0,
1,1,0,0,1,0,1,1,1,1,
1,0,1,1,0,1,1,1,1,0,
1,0,1,0,1,1,1,1,0,0,
1,0,0,1,0,1,0,1,0,1,
1,1,1,1,1,1,1,1,1,0,
0,1,1,1,1,1,1,1,1,0,
0,1,1,0,1,0,1,1,1,1,
1,0,1,0,0,1,0,1,0,0
}; 
 
signed main()
{
	set<int>s;
	for(int i=0;i<10;i++)
		for(int j=0;j<10;j++)
			if(g[i][j])
			{
				for(int k=i+1;k<10;k++)
					for(int p=0;p<=j;p++)
						if(g[k][p])
						{
							if(i+j-p<10&&j+k-i<10&&k+j-p<10&&p+k-i<10&&g[i+j-p][j+k-i]&&g[k+j-p][p+k-i])
							{
								s.insert((k-i)*(k-i)+(j-p)*(j-p));								
							}
						}
			}
	cout<size()<<'\n';
	return 0;		
}