描述

• Lostmonkey在地上沿著一條直線擺上n個(gè)裝置，每個(gè)裝置設(shè)定初始彈力系數(shù)ki，當(dāng)綿羊達(dá)到第i個(gè)裝置時(shí)，它會(huì)往后彈ki步，達(dá)到第i+ki個(gè)裝置，若不存在第i+ki個(gè)裝置，則綿羊被彈飛。綿羊想知道當(dāng)它從第i個(gè)裝置起步時(shí)，被彈幾次后會(huì)被彈飛。為了使得游戲更有趣，Lostmonkey可以修改某個(gè)彈力裝置的彈力系數(shù)，任何時(shí)候彈力系數(shù)均為正整數(shù)。

分析

• 分塊, 維護(hù) i 位置的綿羊經(jīng)過(guò)幾次彈出該塊(f[]), 以及彈出后落在哪個(gè)位置(arv[]). 這樣就可以在 n√n 的時(shí)間內(nèi)完成本題.

• 遇到查詢操作, 則每次 ans 加上 f[i], i 轉(zhuǎn)移到 arv[i], 直到 arv[i]?≥ n

• 遇到修改操作, 則只需維護(hù) 該塊的 f[] 數(shù)組和 arv[] 數(shù)組.

• 維護(hù)時(shí)不用一個(gè)點(diǎn)一個(gè)點(diǎn)的計(jì)算, 而是從后向前倒推.

• 我練習(xí)了一下對(duì)拍和生成數(shù)據(jù), 靠對(duì)拍發(fā)現(xiàn)了錯(cuò)誤.

#include #include using namespace std;const int maxn = 200000 + 10; const int maxb = 500 + 10;int A[maxn], f[maxn], arv[maxn]; int L[maxb], R[maxb];int main() {int n, m, size, block;scanf("%d", &n);for(int i = 0; i < n; i++) scanf("%d", &A[i]);size = (int)sqrt(n);block = n/size + (n%size != 0); //for(int b = 0; b < block; b++) {L[b] = b*size;R[b] = (b+1)*size-1;}R[block-1] = n-1;for(int b = 0; b < block; b++)for(int i = R[b]; i >= L[b]; i--) {int j = i + A[i];if(j > R[b]) f[i] = 1, arv[i] = j;else f[i] = f[j] + 1, arv[i] = arv[j];}scanf("%d", &m);while(m--) {int k, x, b;scanf("%d %d", &k, &x);b = x/size;if(k == 1) {int ans = 0;while(x < n) ans += f[x], x = arv[x];printf("%d\n", ans);} else {scanf("%d", &A[x]);for(int i = R[b]; i >= L[b]; i--) {int j = i + A[i];if(j > R[b]) f[i] = 1, arv[i] = j;else f[i] = f[j] + 1, arv[i] = arv[j];}}}return 0; } #include #include using namespace std;int main() {freopen("bzoj_2002.in", "w", stdout); // freopen("bzoj_2002.out", "r", stdin);srand(0);int n = 100, m = 100;printf("%d\n", n);for(int i = 1; i <= n; i++) printf("%d ", rand() % 9 + 1);printf("%d\n", m);for(int i = 1; i <= m; i++) {int k = rand() % 2 + 1;if(k == 1) {printf("%d %d\n", k, rand() % n);} else {printf("%d %d %d\n", k, rand() % n, rand() % 9 + 1);}}return 0; } #include #include using namespace std; const int maxn = 200000 + 10; const int maxb = 500 + 10; int A[maxn], f[maxn], arv[maxn]; int L[maxb], R[maxb]; int main() { freopen("bzoj_2002.in", "r", stdin); freopen("bzoj_2002_force.out", "w", stdout); int n, m, size, block; scanf("%d", &n); for(int i = 0; i < n; i++) scanf("%d", &A[i]); scanf("%d", &m); for(int i = 1; i <= m; i++) { int k, x, b; scanf("%d %d", &k, &x); b = x/size; if(k == 1) { int ans = 0; while(x < n) ans++, x += A[x]; printf("%d\n", ans); } else { scanf("%d", &A[x]); } } return 0; }

總結(jié)

以上是生活随笔為你收集整理的BZOJ-2002-Bounce弹飞绵羊-分块的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。