a250 - NCPC2011 Problem H Special Subsequences
題目描述
題目給定一個整數序列和一個整數 k，要求找出序列中一個連續子序列，其總和可以被 k 整除。如果存在多個解，則輸出 i 最小的解，如果 i 相同，則輸出 j 最小的解。如果不存在解，則輸出 "no solutions."。
解題思路
本題的核心思想是利用前綴和和排序來高效地尋找滿足條件的子序列。首先，計算序列的前綴和，並將每個前綴和對 k 取模。然後，對前綴和的模值進行排序。排序後，如果相鄰兩個前綴和的模值相同，則說明它們之間的子序列總和可以被 k 整除。由於我們需要找到 i 最小且 j 最小的解，因此在排序後，我們只需要遍歷排序後的序列，找到第一個模值相等的相鄰元素，即可得到答案。
複雜度分析
- 時間複雜度: O(n log n)
- 計算前綴和需要 O(n) 時間。
- 排序前綴和需要 O(n log n) 時間。
- 尋找第一個滿足條件的子序列需要 O(n) 時間。
- 因此，總時間複雜度為 O(n log n)。
- 空間複雜度: O(n)
- 存儲前綴和需要 O(n) 空間。
- 存儲排序後的序列需要 O(n) 空間。
- 因此，總空間複雜度為 O(n)。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
struct so{
int num=0,it=0;
};
bool cmp(so x,so y){
if(x.num<y.num)return 1;
if(x.num==y.num&&x.it<y.it)return 1;
return 0;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int n;
while(cin >> n){
if(n==0)break;
int a[n],k,ans1=1000001,ans2=1000001;
so b[n+1];
bool ans=0;
for(int i=0;i<n;++i)cin >> a[i];
cin >> k;
for(int i=1;i<=n;++i){
b[i].num=a[i-1];
b[i].num+=b[i-1].num;
b[i].num%=k;
if(b[i].num<0)b[i].num+=k;
b[i].it=i;
}
sort(b,b+n+1,cmp);
for(int i=0;i<=n;++i){
if(b[i].num==b[i+1].num){
if(b[i].it+1<ans1){
ans1=b[i].it+1;
ans2=b[i+1].it;
ans=1;
}
}
}
if(ans==0)
cout << "no solutions.\n";
else
cout << ans1 << " " << ans2 << "\n";
}
}