Problem - 7341

题目大意：给出一个数组a，要将一个数修改成[1,300]内的任意一个数，问区间和是完全平方数的区间最多有多少个

1<=n<=300;1<=ai<=300

思路：因为n的范围是300，所以我们可以遍历每一个数，用前缀和维护区间和，统计对于每一个包含这个数的区间，将它修改成哪些数，能够使当前区间的区间和变成完全平方数，那么变成的这个数的贡献就+1，修改后区间和的范围即为[sum[r]-sum[l-1]-a[i]+1,sum[r]-sum[l-1]-s[i]+300]

对于不包含这个数的区间，其区间和如果是完全平方数就贡献+1，遍历完所有区间后，统计每个位置

#include<bits/stdc++.h>
//#include<__msvc_all_public_headers.hpp>
using namespace std;
typedef long long ll;
const int N = 305;
const ll MOD = 998244353;
int a[N];
int sum[N];
void solve()
{int n;cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];sum[i] = sum[i - 1] + a[i];//用前缀和维护区间和}int ans = 0;for (int i = 1; i <= n; i++){vector<int>cnt(305);int cnt2 = 0;for (int j = 1; j <= n; j++){for (int k = j; k <= n; k++){//遍历所有区间if (j <= i && k >= i){int su = sum[k] - sum[j - 1];int mi = su - a[i] + 1;//这个位置修改后能产生的区间和的最小值int ma = su - a[i] + 300;//这个位置修改后能产生的区间和的最大值int x = sqrtl(mi);if (x * x != mi){//找到最小的能被修改成的完全平方数x++;}int y = sqrtl(ma);//最大的能被修改成的完全平方数for (int l = x; l <= y; l++){cnt[l * l - mi+1]++;//修改成哪些数能使和变成完全平方数}}else{int su = sum[k] - sum[j - 1];int x = sqrtl(su);//对于其他区间，直接判断和是否唯完全平方数int flag = 0;for (int temp = x - 5; temp <= x + 5; temp++){//避免sqrt精度丢失if (temp * temp == su){flag = 1;break;}}cnt2 += flag;}                }}int cnt1 = 0;for (int j = 1; j <= 300; j++){//每个位置修改成哪个数贡献最大cnt1 = max(cnt1, cnt[j]);}ans = max(ans, cnt1 + cnt2);}cout << ans << endl;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin >> t;while (t--){solve();}return 0;
}

的贡献，维护答案的最大值