题解
任务
3 条题解
-
0
#include <bits/stdc++.h> using namespace std; /* i 的含义:在这个程序中,i 不仅是开始匹配的位置,它其实代表了 “s 中不参与重叠的部分的长度”。 比如 ABC 和 CDE,n=3。当 i=2 时,s[2] 是 'C',t[0] 也是 'C',匹配成功。结果就是 n + i = 3 + 2 = 5。 */ int main() { int n; string s, t; cin >> n >> s >> t; // 尝试从 s 的第 i 个位置开始,看 s 的后缀能否匹配 t 的前缀 for (int i = 0; i < n; i++) { int flag = 1; // 假设从 i 开始可以匹配 int k = 0; // t 的下标,从头开始对比 for (int j = i; j < n; j++) { if (s[j] != t[k]) { flag = 0; // 只要有一个字符不同,匹配失败 break; } k++; } // 如果 flag 为 1,说明找到了最大的重叠部分 if (flag == 1) { // 最小长度 = s 的长度 + t 中不重叠部分的长度 // t 中不重叠部分的长度就是 n - (n - i) = i cout << n + i << endl; return 0; } } // 如果循环结束都没找到重叠,长度就是两个字符串直接拼接 cout << 2 * n << endl; return 0; } -
0
#include<bits/stdc++.h>//P1115 任务的最少完成时间 //这道题实际上求的是: //从序列中移除一个长度为k的连续子数组,使得剩余部分的和最小 //要最小化剩余和,就要最大化被减去的子数组和。 using namespace std; long long a[1000005];// 存储原始数据 long long s[1000005];// 存储前缀和 int main(){ int n,k; cin>>n>>k; for(int i=1;i<=n;i++){ cin>>a[i]; s[i]=s[i-1]+a[i];// 计算前缀和 s[i] 表示前 i 个元素的和 } long long ans=0; //求最大设最小 注意数据类型 for(int i=1;i<=n;i++){ if(i>=k){ //计算区间 [i-k+1, i] 的和,长度为 k if(s[i]-s[i-k]>ans){ //区间 [L, R] 的和 = s[R] - s[L-1] //这里 L = i-k+1,R = i //所以和 = s[i] - s[(i-k+1)-1] = s[i] - s[i-k] ans=s[i]-s[i-k]; } } } cout<<s[n]-ans; //s[n]:总和 ans:最大子数组和 }
- 1