這題不是我自己想的,程式也是
程式源自 https://sites.google.com/site/silithusxoi/code/ks2014
如有違反著作權,煩請告知
這邊我單純分析他的想法和程式
首先,如果用暴力法算出每個區段, 必定 TLE ( 共有 n + (n-1) + (n-2) + ... + 1 個連續區段 )
他的想法是兩相同餘數間的美好度和,必定為 P/Q 的整數倍
以他的例子來說,1 4 6 有相同的餘數
所以 2~4 , 5~6 的美好度和,為 P/Q 的整數倍
為什麼呢?
因為加入 2 3 4 的美好度後,餘數不變
代表 2 3 4 的平均美好度必定餘 0 , 因此為 P/Q 的整數倍
至於 e 說的要考慮 0/0 的意思是
餘數為 0/0 代表從第一棵到該棵依舊是 P/Q 的整數倍
以他的例子來說就是 1~2 棵
所以共有 4 種可能 ( 1~2, 2~4, 5~6, 2~6 )
#include <cstdio>
#include <algorithm>
#define LL long long
using namespace std;
// pq 用來紀錄餘數
struct one_pq {
LL p;
int q;
bool operator< (const one_pq &v) {
return ( (q == v.q) ? (p < v.p) : (q < v.q) );
}
bool operator!= (const one_pq &v) {
return ( p!=v.p || q!=v.q );
}
};
one_pq pq[1000002];
int main()
{
int N,P,Q,i,c;
LL g,sum,ans;
scanf("%d %d %d", &N, &P, &Q);
// a. 化為最簡分數
c = __gcd(P,Q);
P /= c;
Q /= c;
// b. 計算餘數
for(i=1,sum=0ll; i<=N; i++) {
scanf("%d", &c);
sum += c;
g = i / Q; // 累計美好度的分母 (也就是棵數) 是 Q 的幾倍
if( P != 0ll ) // 如果 P == 0 ,則考慮分母的倍率即可, 但如果 P != 0 , 用分母的倍率可能會把 p 減成負的
g = min(g, sum/P); // 因此選 g 為分母或分子的最小倍率
pq[i].p = (sum - P*g);
pq[i].q = (int)(i - Q*g);
}
// 將餘數排序,一則讓相同餘數聚在一起,好計算有幾區,另一則是讓 0/0 出現在最前面方便計算
sort(pq+1, pq+1+N); // sort 是內建函數,比較方式會依照他上面定義的方式 (operator overloading)
pq[0].p = 0ll; pq[0].q = 0;
pq[N+1].p = -1ll; pq[N+1].q = -1;
// d. 計算區域數
ans = 0ll;
for(i=1,c=0; i<=N+1; i++) {
if( pq[i] != pq[c] ) {
g = i - c - 1; // 2/1 共有 3 個,所以有 2 區 (2~4 和 5~6) i = 6, c = 3
ans += (g+1) * g / 2; // g + (g-1) + ... + 1
c = i;
}
}
printf("%lld\n", ans);
return 0;
}
留言列表