dfs解E题

1.对题目进行分析 可知数组中的每个数都满足大于1 而且在操作过程中a[i]大于等于2 所以不存在有0 的情况.

2.因为可以进行任意次操作 所以任意一组数据我们都可以 将他变为 n-1项都是1 最后一项为sum-(n-1) 根据此推导 我们可以证明答案只有两种情况 也就是n-1和n的情况

3.了解了第2点 我们就可以开始着手写代码了 我们只需要判断 sum是否能由n个有趣数组成 由于数据量小 我们可以采取搜索的模式 在限定的数据内有趣数不超过100 所以dfs能在1s内跑完 证毕

以下请见代码

/*￥￥￥￥CodePoet￥￥￥￥*/
#include<bits/stdc++.h>
using namespace std;


//判断该数是否有趣
bool check(int x)
{
    int s = 0, y;
    while (x) {
        y = x % 10;
        s += y;
        x /= 10;
    }
    int  t= sqrt(s);
    if (t * t == s)
        return true;
    return false;
}


vector<int> a;
int n;
//定义标识符
int flag = 0;
void dfs(int x, int cnt, int now)
{
  //如果能分配成n个数 就不用继续向下搜 
    if (cnt == n) {
      //刚好分完说明最多为n个
        if (x == 0) {
          //设计标识符剪枝
            flag = 1;
        }
        return;
    }
  	//用now 使得分成的数单调 不会搜重复
    for (int i = now;i < a.size();i++) {
      	  
      //如果x可以分配出a[i]这么大就搜
      if (x >= a[i] && flag == 0)
            dfs(x - a[i], cnt + 1, i);
 	//如果已经搜出答案也就是flag==1 那么提前结束搜索
      else break;
    }
}

signed main()
{
//ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

	//预处理好有趣数数组 数据不会超过20000
    for (int i = 1;i * i <= 20000;i++) {
        if (check(i * i)) {
            a.push_back(i * i);
            // cout << a[a.size() - 1] << ' ';
        }

    }
    int T;
    cin >> T;
    while (T--) {
      //初始化标识符
        flag = 0;
        cin >> n;
        vector<int> v(n + 1);
        int sum = 0;
      //统计和
        for (int i = 1;i <= n;i++) {
            cin >> v[i];
            sum += v[i];
        }
      //开搜
        dfs(sum, 0, 0);
        if (flag == 1)
            cout << n << '\n';
        else
            cout << n - 1 << '\n';
    }


}

以上就是我对思路 有任何疑问可以私信我 感谢观看