Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1000 Accepted Submission(s): 341
You have an array consisting of n integers: a1=1,a2=2,a3=3,…,an=n . Then give you m operators, you should process all the operators in order. Each operator is one of four types: Type1: O 1 call fun1(); Type2: O 2 call fun2(); Type3: O 3 call fun3(); Type4: Q i query current value of a[i], this operator will have at most 50. 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]; }
The first line in the input file is an integer T(1≤T≤20) , indicating the number of test cases. The first line of each test case contains two integer n(0<n≤100000) , m(0<m≤100000) . Then m lines follow, each line represent an operator above.
For each test case, output the query values, the values may be so large, you just output the values mod 1000000007(1e9+7).
Sample Output
2 4
注意到“this operator will have at most 50”（Q），所以可优化下后用暴力，复杂度由O（m*n）降至O（50*m）。
#include <bits/stdc++.h> using namespace std; #define mst(a,b) memset((a),(b),sizeof(a)) #define f(i,a,b) for(int i=(a);i<=(b);++i) const int maxn =100005; const int mod = 1e9+7; const int INF = 1e9; #define ll long long #define rush() int T;scanf("%d",&T);while(T--) int m,n,op[maxn]; char s[2]; int cnt; ll pos; ll query() //从查询位置逆回去操作，就可以发现它在最初序列的位置，再逆回去即可求得当前查询的值 { int b=0; for(int i=cnt-1; i>=0; --i) { if(op[i]==1) { if(pos<=(n+1)/2) { pos=2*pos-1; } else { pos=2*(pos-(n+1)/2); } } else if(op[i]==2) { pos=n-pos+1; } else if(op[i]==3) { b++; } } while(b--) { pos=pos*pos%mod; } return pos; } int main() { rush() { scanf("%d%d",&n,&m); cnt=0; while(m--) { scanf("%s%I64d",s,&pos); if(s[0]=='O') { op[cnt++]=pos; } else if(s[0]=='Q') { printf("%I64d\n",query()); } } } return 0; }
