一个原创好题

一个题

​
题目描述
给定一个长度为 n 的正整数数组，以及一个正整数 k。 请你找出和最大的连续且长度至少为1子数组，满足这个和能被 k 整除。 如果不存在这样的子数组，请输出 -1。

输入格式
第一行两个整数 (n, k) 第二行 n 个正整数 (a_i)

输出格式
一行一个整数，表示答案。 若无合法方案输出 -1

输入样例
5 7
1 2 3 4 5

输出样例
14

输入样例
3 7
1 2 3

输出样例
-1

解法：①暴力解（时间复杂度O(n^2),遇到数据量大的样例会超时，作为一个参考解法，不计入标准答案) #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); long long n, k; cin >> n >> k; vector<long long> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } long long ans = -1; for (int i = 0; i < n; ++i) { long long sum = 0; for (int j = i; j < n; ++j) { sum += a[j]; if (sum % k == 0) { ans=max(ans,sum); } } } cout << ans << endl; return 0; }

解法②（前缀和+同余原理）时间复杂度O(n)最优解，建议设为标准答案 #include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); ll n,k; cin>>n>>k; vector<ll> a(n+1); for (int i=1;i<=n;i++) cin>>a[i]; vector<ll> b(n+1); for (int i=1;i<=n;i++) b[i]=b[i-1]+a[i]; unordered_map<ll, ll> ans; ans[0] = 0; ll res = 0; for (int i=1; i<=n; i++) { ll num = b[i] % k; if (num < 0) num += k; if (ans.find(num) != ans.end()) { res = max(res, b[i] - ans[num]); } if (ans.find(num) == ans.end()) { ans[num] = b[i]; } else { ans[num] = min(ans[num], b[i]); } } cout << (res == 0 ? -1 : res) << endl; return 0; }

解法三(kadane算法的变体，以余数作为判断条件，时间复杂度O（n*k）,大数据可能会超时) #include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll n, k; cin >> n >> k; vector<ll> a(n + 1); for (int i = 1; i <= n; i++) cin >> a[i]; unordered_map<ll, ll> dp; dp[0] = 0; ll res = -1; for (int i = 1; i <= n; i++) { ll x = a[i]; unordered_map<ll, ll> ndp = dp; for (auto &p : dp) { ll m = p.first; ll s = p.second; ll num = (m + x % k + k) % k; if (ndp.count(num)) ndp[num] = max(ndp[num], s + x); else ndp[num] = s + x; } dp.swap(ndp); if (dp.count(0)&&dp[0]>0) res = max(res, dp[0]); } cout<<res<<endl; return 0; }

备选样例
样例①
输入：
4 7
3 3 14 3
输出：
14

样例②
输入
5 5
2 3 4 1 2
输出
10

样例③（专卡暴力解）
输入
100000 2
1 1 1 1 1 1 1 1 1 1 1…(一共10^5个1）
输出
100000

样例④
输入
4 7
1 1 1 1
输出
-1

样例⑤（专卡int类型不够爆掉）
输入
3 1000000000000
1 999999999999 1
输出
1000000000000
注：此题改编自力扣523题，代码，样例数据类型全自己写，自己敲定，作为老师布置的任务，就是壮大学校内部题库，服了~~~，大佬们有啥建议，多提出，本学生水平有限

​