一、分考场
题目链接：分考场 - 蓝桥云课 (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<bits/stdc++.h> 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<<num; return 0; }
二、四平方和
题目链接：四平方和 - 蓝桥云课 (lanqiao.cn)
题目要求：
四平方和定理，又称为拉格朗日定理：
每个正整数都可以表示为至多 4 个正整数的平方和。
如果把 0 包括进去，就正好可以表示为 4 个数的平方和。
比如：
5 = 0^2 + 0^2 + 1^2 + 2^2；
7 = 1^2 + 1^2 + 1^2 + 2^2；
对于一个给定的正整数，可能存在多种平方和的表示法。
要求你对 4 个数排序：
0≤a≤b≤c≤d
并对所有的可能表示法按a,b,c,d 为联合主键升序排列，最后输出第一个表示法。
解题思路：
暴力+稍微优化就可以AC了，如果用4层for循环直接暴力的话肯定G了，那么优化一下。最后一层for循环是没必要的，因为它可以通过前三次循环来计算出来的，再进行判断是否符合就可以了，并且用x*x<=n/k来控制循环的终止条件可以减少循环次数。因为a是四个数里最小的，它的最小值是0，最大值是500万除以4；b最小值也是0，因为b是bcd三个数中最小的，所以b的最大值是500万除以3 然后就可以推出c和d的最大值。
#include<bits/stdc++.h> 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<<i<<" "<<j<<" "<<z<<" "<<sum; return 0; } } } } return 0; }
三、最少砝码
题目链接：最少砝码 - 蓝桥云课 (lanqiao.cn)
题目要求：
你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意 小于等于 N 的正整数重量。
那么这套砝码最少需要包含多少个砝码？
注意砝码可以放在天平两边。
解题思路：
这道题可以用动态规划和找规律贪心来做，动态规划有点难了就不写了，这里写出来找规律的做法。
如果当n=1时，只用一个砝码就可以。
当n=2时候，我们要用两个砝码，两个重量为1的砝码即可，但是我们要贪心，我们可以选择更合适的1和3，因为3-1是2，这样范围就变成了1234。
当n=5的时候1 3就不行了，这个时候需要再加入一个砝码，能配合1 3表示5并且能满足贪心的砝码是9，最大的表示范围则是9+3+1=13。
此时我们就找到规律了，1*3=3，3*3=9，可能你觉得三个例子不够规律，那么如果要表达14，3*9=27，27-13=14，可以看得出规律了吧。
#include<bits/stdc++.h> 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<<ans; return 0; }
四、k倍区间
题目链接：k倍区间 - 蓝桥云课 (lanqiao.cn)
题目要求：
给定一个长度为 N 的数列，A1,A2,⋯AN，如果其中一段连续的子序列 Ai,Ai+1,⋯Aj(i
你能求出数列中总共有多少个 K 倍区间吗？
解题思路：
前缀和 每次相加 然后在数组加上这个k倍的余数
#include<bits/stdc++.h> 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; }
