首页 > 代码库 > HDU 5063 Operation the Sequence（仔细审题）
HDU 5063 Operation the Sequence（仔细审题）
http://acm.hdu.edu.cn/showproblem.php?pid=5063
题目大意：
题目意思还是比较简单。所以就不多少了。注意这句话，对解题有帮助。
Type4: Q i query current value of a[i], this operator will have at most
50.
解题思路：
因为给定n和m都是100000，我们每一步都做具体的操作，时间将是O（n*m），肯定超时。最开始的时候
我怎么想都不知道怎么解决。以为是线段树。比赛完了以后，看了解题报告（http://bestcoder.hdu.edu.cn/）
我吓到了，原来是自己没有仔细分析题目的给的条件。Q i query current value of a[i], this operator will
have at most 50.询问Q i最多50次。
所以我们把每部的操作都记下来，每次Q i的时候，就反推回去。自己可以推推。
假设当前位置为x，我们要求操作之前的位置。
fun1：
n = (n + 1) / 2;
x = x <= n / 2 ? (2 * x - 1) : ((x - n) * 2);
fun2:
x = n + 1 - x;
fun3:
我们用flag记录平方次数。
这样处理的时间复杂度O（50*n）
AC代码：
1 #include<cstdio> 2 3 #define MAXN 100000+10 4 #define MOD 1000000007 5 6 int op[MAXN], count; 7 8 int fun_1(int x, int n){ 9 n = (n + 1) >> 1;10 if(x <= n){11 return (x << 1) - 1;12 }13 return (x - n) << 1;14 }15 16 int fun_2(int x, int n){17 return n + 1 - x;18 }19 20 void solve(int x, int n){21 int flag = 0;//记录平方次数22 23 for(int i = count - 1; i >= 0; --i){//逆推回去 找出初始位置24 if(op[i] == 1){25 x = fun_1(x, n);26 }else if(op[i] == 2){27 x = fun_2(x, n);28 }else{29 flag++;30 }31 }32 33 __int64 num = x;34 for( ; flag > 0; --flag){35 num = num * num % MOD;36 }37 printf("%I64d\n", num);38 }39 40 int main(){41 char str[5];42 int t, n, m, i, num;43 44 scanf("%d", &t);45 while(t--){46 scanf("%d%d", &n, &m);47 for(count = i = 0; i < m; ++i){48 49 scanf("%s%d", str, &num);50 if(str[0] == ‘O‘){51 op[count++] = num;//记录执行fun1、fun2、fun352 }else{53 solve(num, n);54 }55 }56 }57 return 0;58 }
HDU 5063 Operation the Sequence（仔细审题）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。