【希冀OJ】考前刷一刷（一）

   众所周知，作为一名合格的程序员，算法 能力 是不可获缺的，并且在算法学习的过程中我们总是能感受到算法的✨魅力✨。
              ☀️短短几行代码，凝聚无数前人智慧；一个普通循环，即是解题之眼☀️
   二分，贪心，并查集，二叉树，图论，深度优先搜索(dfs)，宽度优先搜索（bfs），数论，动态规划等等， 路漫漫其修远兮，吾将上下而求索！ 希望在此集训中与大家共同进步，有所收获！！！

      8504. Sum of Digits

由于数字很大很大，所以只能转换为字符串，然后将每个字符加起来模拟题目要求即可，这里用递归实现（省事），当然也可以自己搞个while代替递归

#include
#include 
#include 
#include 
int sum;
void deal(char* dig) {
	int s=atoi(dig); if (0 <= s && s <= 9)return;
	s = 0;
	for (int i = 0; i < strlen(dig); i++) {
		s += dig[i] - '0';
	}	
	sprintf(dig, "%d", s);
	sum++;
	deal(dig);
	return;
}
int main()
{
	char str[1000000] = { 0 };
	scanf("%s", str);
	deal(str);
	printf("%d", sum);
	return 0;
}

      8578. 纸片抽取

暴力搜索提没得说，这里限制了搜索深度为4，所以一股脑写递归即可，记得回溯恢复现场哦

#include
#include 
#include 
#include 
int sum = 4;
int process(int num[], int n, int m) {
  if (sum<0||m < 0)return 0;
  if ((!sum) && (!m))return 1;
  for (int i = 0; i < n; i++) {
    sum--;
    int f = process(num, n, m - num[i]);
    sum++;
    if (f)return 1;
  }
  return 0;
}
int main()
{
  int num[50] = { 0 }, m, n;
  scanf("%d%d", &m, &n);
  for (int i = 0; i < n; i++)scanf("%d", &num[i]);
  if (process(num, n, m))printf("yes");
  else printf("no");
  return 0;
}

      8545. 括号匹配问题

括号匹配问题绝不是遍历字符串，分别统计左括号和右括号就可以的，而应该只统计左括号的多余数量，也就是如果遇到有括号，左括号数量减一，这样才能完美匹配（防止入坑）

#include
#include 
#include 
#include 

int main()
{
	char str[1024];
	scanf("%s", str); int a = 0;
	for (int i = 0; i < strlen(str); i++)
	{
		if (str[i] == '(')a++;
		else if (str[i] == ')')a--;
		if(a<0){
			printf("n");return 0;
		}
	}
	if (a == 0)
		printf("y");
	else
		printf("n");
	return 0;
}

      8532. 数字游戏

合法X的范围一定是2到sqrt(n)，那么就从最大开始递减，然后用个while循环去判断以及计算n为X的k次幂

#include
#include 
#include 
#include 
#include

int main()
{
	while (1)
	{
		int N; scanf("%d", &N);
		if (!N)break;
		int t = sqrt(N); int i; int sum = 0;
		for (i = t; i >= 2; i--) {
			int n = N;
			while (n != 1)
			{
				if (!(n % i)) { sum++; n /= i; }
				else  break;
			}
			if (n == 1)break;
		}
		if (i == 1)printf("0 0n");
		else printf("%d %dn", i, sum);
	}
	return 0;
}

下午考c语言程序设计，现在先练练手，找了几道简单的，但是也比较有意思，希望下午能满分，莫要出意外，我保证多测各种边界数据（这****的OI赛制）！

写在最后：
相信大家对今天的集训内容的理解与以往已经有很大不同了吧，或许也感受到了算法的魅力,当然这是一定的，路漫漫其修远兮，吾将上下而求索！伙伴们，明天见！