題意：
? ? ? 剛開始的時候給你一個序列，長度為n,分別為a[1]=1,a[2]=2,a[3]=3,a[4]=4...a[n]=n,然后有4種操作如下：


Type1: O 1 call fun1();
Type2: O 2 call fun2();
Type3: O 3 call fun3();
Type4: Q i問當前a[i]的值,****** 詢問最多50次*******，輸出%1e9+7.
Global Variables: a[1…n],b[1…n];
fun1() {
index=1;
? for(i=1; i<=n; i +=2)?
? ? b[index++]=a[i];
? for(i=2; i<=n; i +=2)
? ? b[index++]=a[i];
? for(i=1; i<=n; ++i)
? ? a[i]=b[i];
}
fun2() {
? L = 1;R = n;
? while(L<R) {
? ? Swap(a[L], a[R]);?
? ? ++L;--R;
? }
}
fun3() {
? for(i=1; i<=n; ++i)?
? ? a[i]=a[i]*a[i];
}


思路：
? ? ? 感覺這個題目不錯，首先我們要從題目給的信息里面獲得重要的東西，比如這個題目最重要的是四種操作中詢問的的操作不會大于50，這個非常重要，操作數(shù)一共是100000，而這個是50,50/100000的比率，現(xiàn)在我們來分析這個題目，首先，直接模擬肯定是不行的，這個我用我解釋，其次就是我們怎么利用好這個50，我們對于每一次詢問，問的只是第i個位置的值，而所有的操作中對于每各位置的處理都是獨立的，就是我們變換的只是位置而已，對于每一位，我們不用管別的位數(shù)怎么變，只要知道自己該到那個位置就行了，那么這50次詢問也只是關(guān)心的一位，所以我們可以先把所有的操作存起來<也可以說是離線？>，然后對于每一個詢問，我們就把當前詢問的這個位置逆序變換到當初的位置，這樣的時間復雜度就是50*10W，完全可以接受，再就是怎么還原回去，這個雖然比較簡單，我還是說下吧，省著有學弟疑問，對于第一和第二種操作，我們每次還原到上一步就是先斷定他是奇數(shù)的第幾個還是偶數(shù)的第幾個，然后在算值<具體看代碼>，對于）O 3這個更好弄，只要開始變量記錄

下個數(shù)，最后乘回去就行了，<這個地方不是a^b是平方后再平方再平方...別弄錯了>，遇到詢問就直接跳過去，詢問不改變位置，大體就是這樣，具體看代碼吧，這個題目要好好做做，能從中學到不少有用的東西。

#include<stdio.h> #include<string.h> typedef struct {int k; }STAR;STAR Q[110000];int poww(int a ,int b) {__int64 c = a;for(int i = 2 ;i <= b ;i ++){c *= c;c %= 1000000007;}return (int)c; }int main () {int i ,j ,n ,m ,a ,t;char str[4];scanf("%d" ,&t);while(t --){scanf("%d %d" ,&n ,&m);for(i = 1 ;i <= m ;i ++){scanf("%s %d" ,str ,&a);if(str[0] == 'O') Q[i].k = a;else Q[i].k = a + 3;}for(i = 1 ;i <= m ;i ++){ if(Q[i].k > 3){int sp = 1 ,now = Q[i].k - 3;for(j = i - 1 ;j >= 1 ;j --){if(Q[j].k == 3) sp ++;else if(Q[j].k > 3) continue;else{if(Q[j].k == 1){if(now <= (n + 1) / 2) now = now * 2 - 1;else now = 2 * (now - (n + 1) / 2);}else now = n - now + 1;}}printf("%d\n" ,poww(now ,sp));}}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu 5063 不错的小想法题（逆向处理操作）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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