wordpress支付宝红包,sem和seo区别与联系,养生网站建设论文,搜狗竞价推广效果怎么样分考场传送门 分成互质数传送门 题目描述 n个人参加某项特殊考试。 为了公平#xff0c;要求任何两个认识的人不能分在同一个考场。 求最少需要分几个考场才能满足条件。 输入 第一行#xff0c;一个整数n(1n100)#xff0c;表示参加考试的人数。 第二行#xff0c…分考场传送门 分成互质数传送门 题目描述 n个人参加某项特殊考试。 为了公平要求任何两个认识的人不能分在同一个考场。 求最少需要分几个考场才能满足条件。 输入 第一行一个整数n(1n100)表示参加考试的人数。 第二行一个整数m表示接下来有m行数据 以下m行每行的格式为两个整数ab用空格分开 (1a,bn) 表示第a个人与第b个人认识编号从1开始。 输出 一行一个整数表示最少分几个考场。 样例输入 5 8 1 2 1 3 1 4 2 3 2 4 2 5 3 4 4 5 样例输出 4
大意就是要让互相认识的人不要在同一个考场然后求最小考场数这里可以用涂色法来确认两人在不在同意考场具体代码如下。
#includeiostream
#includecsttring
#includealgorithm
const int N110;
int a[N][N],rl[N],rp[N][N],n,ansN;//a数组是涂色数组rlroomlenth.是房间的当前人数rp,roompeople.是当前房间的人。
using namespace std;
bool judge(int pos,int room) {for(int i1;irl[room];i)//当前房子有没有认识的人if(a[pos][rp[room][i]])//互相涂色的表示认识返回false。return false;return true;//前面没有找到互相认识的人然会true。
}
void dfs(int pos,int total) {//pos是当前寻找的人total是当前答案。if(totalans) return ;//当前答案大于最优解剪枝。if(posn1) { ansmin(ans,total); return ; }//最优答案。for(int i1;itotal;i) {//遍历之前已近放置的房子看看有没有符合要求的if(judge(pos,i)) {/第pos个人在第i个房子是否合理rp[i][rl[i]]pos;dfs(pos1,total);rl[i]--;//回溯。}}rp[total1][rl[total1]]pos;//前面的房子全部不满住。重新开一个房子。dfs(pos1,total1);rl[total1]--;回溯。
}
int main() {int x,y,m;cinnm;for(int i0;im;i) {//读入加涂色。cinxy;a[x][y]1;a[y][x]1;}dfs(1,0);从第一个人开始搜索coutansendl;return 0;
}7834:分成互质组 总时间限制: 1000ms 内存限制: 65536kB 描述 给定n个正整数将它们分组使得每组中任意两个数互质。至少要分成多少个组
输入 第一行是一个正整数n。1 n 10。 第二行是n个不大于10000的正整数。 输出 一个正整数即最少需要的组数。 样例输入 6 14 20 33 117 143 175 样例输出 3 其实这两道题目都是差不都的方法上面的分考场是判断认识不认识这里的是判断他们两个的最大公因数是不是 1 做法都大致相同只要把上面的判断数组改成gcd函数就行直接给出代码吧。
#includeiostream
#includecstring
#includealgorithm
int n,a[20],rl[20],rp[20][20],ans;
using namespace std;
int gcd(int h,int j) {if(j0) return h;return gcd(j,h%j);
}
bool judge(int c,int j) {for(int i1;irl[j];i)if(gcd(c,rp[j][i])!1) return false;return true;
}
void dfs(int pos,int total) {if(totalans) return ;if(posn) {ansmin(ans,total);return ;}for(int i1;itotal;i) {if(judge(a[pos],i)) {rp[i][rl[i]]a[pos];dfs(pos1,total);rl[i]--;}}rp[total1][rl[total1]]a[pos];dfs(pos1,total1);rl[total1]--;
}
int main() {cinn;for(int i0;in;i)cina[i];ans130;memset(rl,0,sizeof(rl));dfs(0,0);coutansendl;return 0;
}
