大家好,又见面了,我是全栈君。
Operation the Sequence
Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 158 Accepted Submission(s): 74
a1=1,a2=2,a3=3,…,an=n
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];
}
T(1≤T≤20)
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.
1 3 5 O 1 O 2 Q 1 O 3 Q 1
2 4
注意到查询次数不超过50次。那么能够从查询位置逆回去操作,就能够发现它在最初序列的位置,再逆回去就可以
求得当前查询的值。对于一组数据复杂度约为O(50*n)。
//218ms #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn=100000+1000; int a[maxn];//奇偶排序操作 int q[maxn];//存储操作类型,1是奇偶排序。2是逆置 int c[maxn];//逆置 const int mod=1000000007; int solve(int cur,int x)//找到在刚開始的位置 { int ans=x; for(int i=cur-1;i>=0;i--) { if(q[i]==1) { ans=a[ans]; } else { ans=c[ans]; } } return ans; } int main() { int t,n,m; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); int index=1; for(int i=1; i<=n; i +=2) a[index++]=i; for(int i=2; i<=n; i +=2) a[index++]=i; for(int i=1;i<=n;i++) c[i]=n+1-i; char s[10]; int p; int cur=0; int cou=0; for(int i=0;i<m;i++) { scanf("%s%d",s,&p); if(s[0]=='O') { if(p==3) cou++; else q[cur++]=p; } else { long long ans=solve(cur,p); for(int i=0;i<cou;i++) { ans=ans*ans%mod; } printf("%I64d\n",ans); } } } return 0; }
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115774.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...