蓝桥杯倒数七天冲刺国一之每日复习第二天

距离蓝桥杯还有六天！！各位加油！！！不要忘了打印准考证测试环境！

目录

一丶分考场

二丶四平方和

三丶最少砝码

四丶k倍区间

题目链接：分考场 - 蓝桥云课 (lanqiao.cn)

题目要求：

n 个人参加某项特殊考试。

为了公平，要求任何两个认识的人不能分在同一个考场。

求是少需要分几个考场才能满足条件。

解题思路：

一道dfs题目，首先我们要考虑

直接每个学生去安排，第一个学生分一个考场，然后看第二个 如果认识就开一个新的考场，不认识就放进去，然后我们判断 第i个考场如果满足就把学生放进去，否则就判断下一个考场 如果都认识并且没空考场就一定要开新的考场

我们定义一个g数组 维护考生之间认识与否 g[a][b]=g[b][a]=1代表俩人认识

p数组是用来判断考场第i个考场j位置有没有人

while(p[j][k] && !g[x][p[j][k]])
{
    k++;
}

在一个for里

如果一开始p[j][k]==0,直接退出while，那么说明这个考场还没有人，考生可以坐在这个考场

一开始是p[j][k]==1，然后看g[x][p[j][k]]也就是看j考场中k座位的学生是否与x认识，如果认识那么退出

后边判断 如果P[j][k]为0 把x安排进去 然后回溯

最后当我们for语句执行完了，也就是说所有考场中都有x认识的人，必须为x开辟一个新考场才行

然后就是我们的代码

#include
using namespace std;
int g[101][101],p[101][101];				
int n,m,a,b,num=101;
void dfs(int x,int y)
{ 
	if(y>=num)
	{
		return;					
	}
	if(x>n)
	{
		num = min(num,y);
		return;
	}
	for(int j=1;j<=y;j++)
	{						
		int k=0;
		while(p[j][k] && !g[x][p[j][k]])
		{
			k++;
		}
		if(p[j][k]==0)
		{
			p[j][k]=x;
			dfs(x+1,y);
			p[j][k]=0;
		}
	}                                  		 	  
	p[y+1][0]=x;				
	dfs(x+1,y+1);							
	p[y+1][0]=0;									
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{ 
		cin>>a>>b;
		g[a][b]=g[b][a]=1; 			
	}
	dfs(1,1);
	cout<

#include
using namespace std;
int main()
{
	int n;
	cin>>n;
	for(int i=0;i<=n/4;i++)
	{
		for(int j=i;j<=n/3;j++)
		{
			for(int z=j;z<=n/2;z++)
			{
				double num = sqrt(n-i*i-j*j-z*z);
				int sum = sqrt(n-i*i-j*j-z*z);
				if(num==sum)
				{
					cout<

#include
using namespace std;
int main()
{             
    int n;
    cin>>n;
    int ans = 1,num = 1,sum = 1; //ans是保存用了几个砝码 num是新的砝码的重量 sum是砝码最高可以表示的值，因为如果n=1只有一种方法我们就初始化为1.
    while(1)
    {
    	if(sum>=n)//如果最高表示的值大于等于n
		{
			break;//跳出循环
		}
		ans++;//砝码+1
		num *= 3;//砝码重量遵循上面的规律
		sum += num;//sum加上新的砝码重量
    }      
    cout<

#include
using namespace std;
const int N =100010;
int n,k;
long long s[N],cnt[N];
long long res;
int main()
{
	cnt[0] = 1;
	cin >> n >> k;
	for(int i = 1; i <= n; i ++ )
	{
		cin >> s[i];
		s[i] += s[i - 1];
		res += cnt[s[i] % k];
    	cnt[s[i] % k]++ ;
	}
	cout << res;
	return 0;
}