四、 根能抵达的点（树的遍历）

南京大学考研机试题任意门
题意:建立一个带边权树，起初所有的节点都能从根节点出发遍历到，然后我们删除边权比x小的点，使根节点能够抵达的节点数目（包括自己）不超过 Y。求x。
这里我们可以用二分来做，二分一定是有序的，但有序的不一定能用二分。
树的遍历—dfs，bfs，并查集

#include 
#include 
#include using namespace std;const int N = 20010, M = N * 2;int n, m;
int h[N], e[M], w[M], ne[M], idx;void add(int a, int b, int c)
{e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}int dfs(int u, int mid, int fa)
{int res = 1;for (int i = h[u]; ~i; i = ne[i]){int j = e[i];if (j == fa || w[i] < mid) continue;res += dfs(j, mid, u);}return res;
}int main()
{int T;scanf("%d", &T);while (T -- ){scanf("%d%d", &n, &m);memset(h, -1, sizeof h);idx = 0;for (int i = 0; i < n - 1; i ++ ){int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c);add(b, a, c);}int l = 0, r = 1e8;while (l < r){int mid = (l + r) >> 1;if (dfs(0, mid, -1) <= m) r = mid;else l = mid + 1;}printf("%d\n", r);}return 0;
}

五、平方因子（试除法、枚举）

任意门
题意：给定一个数 n，判定它是否有一个不为 1 的完全平方数因子。
也就是说，是否存在某个 k，k>1，使得 k2 能够整除 n。

#includeusing namespace std;int main()
{int n;while(cin>>n){bool res=false;for(int i =2;i*i<=n;i++){if(n%(i*i)==0){res=true;break;}}if(res)puts("Yes");else puts("No");}return 0;
}

六、数字根（同余）

北京大学机试题任意门
题意：一个正整数的数字根是通过对该整数的各位数字求和得到的。
如果得到的结果是一个一位数字，则该这个数字就是所求的正整数的数字根。

注意这道题目的数据范围很大，所以要用string来处理。

性质：一个数除余 9 的余数 和 其各位数字之和除余 9 的余数相同，即同余。

写法一：同余

#include using namespace std;int main()
{string str;while (cin >> str, str != "0"){int sum = 0;for (auto c: str)sum += c - '0';sum %= 9;if (!sum) sum = 9;cout << sum << endl;}return 0;
}

写法二：

#include 
#include 
#include using namespace std;string s;int main()
{while (cin >> s, s != "0") //如果是0的话就直接跳过{int res = 0; //数字根。while (res == 0 || res > 9)  //如果是第一个，或者是当前的数字根不是一位{   res = 0;   //每次初始化数字根for (char t : s)  //那么累加当前数的每一位数res += t - '0';if (res > 9) s = to_string(res); //如果当前的数字根不是一位数，将res转成字符串赋值给s}cout << res << endl; //最后输出数字根}return 0;
}

七、素数（筛质数）

北京航空航天大学机试题任意门
题意：给定一个数，让你筛出1到这个数中所有以1结尾的素数。

#include
using namespace std;
bool prime(int x)
{for(int i=2;i<=x/i;i++)if(x%i==0)return 0;return 1;
}
int main()      
{int n,i;while(cin>>n){bool ok=0;for(int i=2;i<=n-1;i++)if(prime(i)&&i%10==1)cout<