題干：

小a有n個數，他想把他們劃分為連續的權值相等的k段，但他不知道這是否可行。

每個數都必須被劃分

這個問題對他來說太難了，于是他把這個問題丟給了你。

輸入描述:

第一行為兩個整數n,q，分別表示序列長度和詢問個數。 第二行有n個數，表示序列中的每個數。 接下來的q行，每行包含一個數k，含義如題所示。

輸出描述:

輸出q行，每行對應一個數Yes或者No，分別表示可行/不可行

?

示例1

輸入

復制

5 3 2 1 3 -1 4 3 2 1

輸出

復制

Yes No Yes

備注:

?

對于的數據，

對于的數據，

對于的數據，

設ai表示數列中的第i個數，保證

保證數據完全隨機

?

解題報告：

? ?剛開始以為二分復雜度是正確的，寫了一個就AC了，但是后來一想發現不對啊復雜度成了O(q^2logn)、、、大概是數據水了吧

? ?而且我這種解法根本不適合有負數存在的情況、、因為sum數組就不單調了呀。

AC代碼：

#include<bits/stdc++.h> #define ll long long using namespace std; const int MAX = 100000 + 5 ; ll a[MAX]; ll sum[MAX]; int main() {int n,q,k;cin>>n>>q;for(int i = 1; i<=n; i++) scanf("%lld",a+i),sum[i] = sum[i-1] + a[i];while(q--) {scanf("%d",&k);if(sum[n] % k != 0) {puts("No");continue;}int every = sum[n] / k;int cur = 0,flag = 1;for(int i = 1; i<=k; i++) {int pos = lower_bound(sum+1,sum+n+1,cur + every) - sum;if(sum[pos] != cur+every) {flag=0;break;}cur += every;}if(flag == 1) puts("Yes");else puts("No");}// 2 3 6 5 9return 0 ;}

標程：（其實也差不多啦復雜度o(因子個數*N + q)）

? ? 其實就是打表算的，對于這題其實打表比較合適，因為q比n大，且題干中說了數據保證隨機，所以最好是打表然后o(1)查詢

#include<cstdio> #include<cstring> #include<algorithm> #define LL long long using namespace std; const int MAXN = 2 * 1e6 + 10, INF = 1e9 + 10; inline int read() {char c = getchar(); int x = 0, f = 1;while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x * f; } int a[MAXN]; bool ans[MAXN]; int main() {int N = read(), Q = read();LL sum = 0;for(int i = 1; i <= N; i++) a[i] = read(), sum += a[i];for(int i = 1; i <= N; i++) {if(sum % i != 0) {ans[i] = 0; continue;}LL cur = 0, k = 0;for(int j = 1; j <= N; j++) {cur += a[j];if(cur == sum / i) cur = 0, k++;}ans[i] = (cur == 0 && k == i);}while(Q--) {int x = read();puts(!ans[x] ? "No" : "Yes");} }

數據保證隨機的意思是 sum 的因子不會太多（構造數據可以達到1e5級別）
另外可能有一個坑點：因為有負數的存在，如果當前數大于了 sum/k 了，是不能直接跳出的（這是針對標程的解法的，用前綴和就不存在這個問題）

還是要注意一下負數啊！！各種題中，尤其是那種，說 int范圍的。比如這題

---

不對啊，我那種方法其實修改一下也是正確的，用set維護一個pair<前綴，當前下標>，然后每次二分查找pair<那個值，上一次查找的下標>，這樣找到的就是pair<那個值，那個下標后面的值>或者pair<大于那個值，下標無所謂>，我們在if判斷一下是否是第一種，就可以了。

總結

以上是生活随笔為你收集整理的【牛客 - 181C】序列（前缀和，二分，可用set维护）（有坑）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。