MYF

HDU 5063 Operation the Sequence

Posted on | In | | Visitors

题目链接

HDU 5063

解题方法：推导 + 反向模拟

题目分析

题目大意

先给出一个数字n，形成一个长度为n的数组，ai = i，现在有四种操作。第一种，取所有奇数位置的值，再取所有偶数位置的值。第二种，n个位置的元素关于中心对称，形成新的数列。第三种，将每一个位置的值平方。第四种，查询之前的操作全部完成之后某一位置的值。

解析

看题目很容易发现，最多执行五十次操作，所以每次查询的时候计算的话复杂度并不会很大。分析一下这个问题，看前三种操作，后两种还是挺容易的，对称的话直接找n+1-pos即可找到原来的位置，值平方的话只需要一直平方即可，因为二进制位只有一个1，所以快速幂在这种情况下完全没有优势，直接乘即可，最多也就50次。麻烦一点的是第一个问题，要分n为奇数和n为偶数两种情况考虑。当n为奇数时，对于这n个位置的奇数位，new = ( old + 1 ) / 2，对于偶数位 new = old / 2 + ( n - n / 2 )。再看n为偶数的情况，上面两个公式仍然成立，所以只需要倒推一下，找出来old关于new的位置变换公式即可。查询的时候直接跑那么多次的平方即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1)
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#define mp make_pair
#define pb push_back
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
const int maxn=100000+5;
const int mod=1000000007;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
/*
 fun1()     // 取所有奇数位置 再取所有偶数位置
 fun2() {    // 中心对称
 fun3() {    // 每个数乘方
 */
int op[maxn],stp=0,t,n,m;
int main(){
    int pos;
    char s[2];
    scanf("%d",&t);
    int mi=0;
    while (t--) {
        stp=0;
        mi=0;
        scanf("%d%d",&n,&m);
        for (int i=1; i<=m; i++) {
            scanf("%s%d",s,&pos);
            if (s[0]=='O'&&pos==1)
                op[stp++]=1;
            else if (s[0]=='O'&&pos==2)
                op[stp++]=0;
            else if (s[0]=='O'&&pos==3)
                mi++;
            else{
                ll tmp = pos;
                for (int i=stp-1; i>=0; i--)
                    if (op[i]==1&&tmp<=(n+1)/2)
                        tmp=2*tmp-1;
                    else if(op[i]==1)
                            tmp=tmp*2-2*(n-n/2);
                    else if(op[i]==0)
                        tmp=n+1-tmp;
                for (int i=1; i<=mi; i++)
                    tmp=tmp*tmp%mod;
                printf("%lld\n",tmp);
            }
        }
    }
    return 0;
}