一个原创好题

文章目录一个题一个题​题目描述给定一个长度为 n 的正整数数组以及一个正整数 k。 请你找出和最大的连续且长度至少为1子数组满足这个和能被 k 整除。 如果不存在这样的子数组请输出 -1。输入格式第一行两个整数 (n, k) 第二行 n 个正整数 (a_i)输出格式一行一个整数表示答案。 若无合法方案输出 -1输入样例5 71 2 3 4 5输出样例14输入样例3 71 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; vectorlong 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) { ansmax(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; cinnk; vectorll a(n1); for (int i1;in;i) cina[i]; vectorll b(n1); for (int i1;in;i) b[i]b[i-1]a[i]; unordered_mapll, ll ans; ans[0] 0; ll res 0; for (int i1; in; 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算法的变体以余数作为判断条件时间复杂度On*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; vectorll a(n 1); for (int i 1; i n; i) cin a[i]; unordered_mapll, ll dp; dp[0] 0; ll res -1; for (int i 1; i n; i) { ll x a[i]; unordered_mapll, 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]); } coutresendl; return 0; }备选样例样例①输入4 73 3 14 3输出14样例②输入5 52 3 4 1 2输出10样例③专卡暴力解输入100000 21 1 1 1 1 1 1 1 1 1 1…(一共10^5个1输出100000样例④输入4 71 1 1 1输出-1样例⑤专卡int类型不够爆掉输入3 10000000000001 999999999999 1输出1000000000000注此题改编自力扣523题代码样例数据类型全自己写自己敲定作为老师布置的任务就是壮大学校内部题库服了~~~大佬们有啥建议多提出本学生水平有限​