定位賽 Time Limit: 1000 ms???Case Time Limit: 1000 ms???Memory Limit: 64 MB
Description LOLS4.1賽季正式開始，排位分又重置了，上賽季是最強王者的DoubleLee，JCBOSS迫不及待地打開LOL
納尼？！！
定位賽換成ACM題了？！
定位賽題目如下：
給你n個整數(依次編號為1~n)，請輸出具備以下條件的長度的【L，R】區間
1.(a[L] + a[L + 1] + ....a[R]) % n == 0
2.如果有多個可行的區間，請輸出L最小的
3.滿足以上條件的仍然有多個，則輸出R最小的
4.如果沒有符合條件的區間，則輸出“Error”（不包括引號）

PS:提交超過10次無法AC的，直接青銅5。。。

Input 單組數據測試
第一行一個整數n（1<=n<=10^5)
接下來一行n個整數（每個整數0<=n<=2^30）
Output 輸出滿足要求的區間L,R（格式參照sample）
沒有則輸出“Error”（不包括引號）
Sample Input

Original

Transformed

5 1 2 3 4 5
Sample Output

Original

Transformed

1 4
Source "訊飛輸入法杯"安徽大學第六屆程序設計競賽
————————————————————憂桑的分割線———————————————————— 思路：這道題考兩個東西：1.模運算的性質 2.前綴和 此題是否一定有解？首先考慮數列中存在某一項的前綴和（前 i 項和）Mod n == 0，此時它就是可行解。 其次考慮數列中每一項的前綴和 Mod n != 0，這個時候重點來了，我們知道鴿巢原理：有n-1個籠子，放進n只鴿子，那么一定有一個籠子里面有兩只鴿子。 同理，此時余數最多只有n-1種，而數列中有n個元素，這意味著一定會有重復的余數出現。 重復的余數出現意味著什么？ 沒反應過來？那么繼續看：前綴和是不減的。越來越大。 某兩個位置的前綴和 Mod n 結果相同。 沒錯，這就意味著出現了可行解。余數相同意味著這個區間內前綴和的變化量正好是k*n(k為正整數)。 但是可行解并不意味著全部，要找到最優解，需要判斷在什么時候更新當前解。 最后，考慮模運算的性質： (a + b) % n == (a % n + b % n) % n; 如此一來，便可以優化vis[ ]的空間。直接用sum%n代替sum算了。 代碼如下： #include <stdio.h> #include <string.h> #include <stdlib.h> #include <math.h> int f[100010]; int vis[100010]; int main() {int n, l, r;int ans_l = 101000, ans_r;//最優解scanf("%d", &n);int sumod = 0;for(int i = 1; i <= n; i++)scanf("%d", f+i);memset(vis, -1, sizeof(vis));vis[0] = 0;//這是隱含解，從還未開始計算前綴和0，一直到某一項的前綴和 Mod n == 0是優先考慮的最優解for(int i = 1; i <= n; i++) {sumod = (sumod + f[i]) % n;if(vis[sumod] == -1) vis[sumod] = i;//該“前綴mod和”并未出現過，儲存一下該值的位置else { //該“前綴mod和”第二次出現了！可行解出現。l = vis[sumod] + 1;//可行解出現正是因為從某sumod第一次出現之后到第二次出現增加了k個nr = i;//因此l = vis[] + 1, r = i;if(l < ans_l){ans_l = l; ans_r = r;//是否更新最優解}}}printf("%d %d\n", ans_l, ans_r);return 0; }

總結

以上是生活随笔為你收集整理的AOJ-AHU-OJ-675 定位赛的全部內容，希望文章能夠幫你解決所遇到的問題。

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