bc13&&hdoj5062&&hdoj5063 Beautiful Palindrome Number Operation the Sequence

46 阅读 0 评论 31 点赞

我是靠谱客的博主斯文芹菜，最近开发中收集的这篇文章主要介绍bc13&&hdoj5062&&hdoj5063 Beautiful Palindrome Number Operation the Sequence，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Beautiful Palindrome Number

Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 951 Accepted Submission(s): 626

Problem Description

A positive integer x can represent as

(a1a2…akak…a2a1)10 or

(a1a2…ak−1akak−1…a2a1)10 of a 10-based notational system, we always call x is a Palindrome Number. If it satisfies

0<a1<a2<…<ak≤9 , we call x is a Beautiful Palindrome Number.
Now, we want to know how many Beautiful Palindrome Numbers are between 1 and

10N .

Input

The first line in the input file is an integer

T(1≤T≤7) , indicating the number of test cases.
Then T lines follow, each line represent an integer

N(0≤N≤6) .

Output

For each test case, output the number of Beautiful Palindrome Number.

Sample Input


2
1
6

Sample Output


9
258

Source

BestCoder Round #13

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<list>
#include<vector>
using namespace std;
const int maxn=1000010;
int num[maxn];
char str[10];
void dabiao(){
int i,j;
for(i=1;i<maxn;++i){
sprintf(str,"%d",i);
int len=strlen(str);
for(j=0;j<(len+1)/2;++j){
if(str[j]==str[len-j-1]){
if(j==((len+1)/2-1)||str[j]<str[j+1]);
else break;
}
else break;
}
if(j<(len+1)/2)num[i]=num[i-1];
else num[i]=num[i-1]+1;
}
}
int cnt[10]={1,10,100,1000,10000,100000,1000000,10000000};
int main()
{
dabiao();
int n,t;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
printf("%dn",num[cnt[n]]);
}
return 0;
}

Operation the Sequence

Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 779 Accepted Submission(s): 265

Problem Description

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];
}

Input

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.

Output

For each test case, output the query values, the values may be so large, you just output the values mod 1000000007(1e9+7).

Sample Input

Sample Output

2
4

Source

BestCoder Round #13

注意到查询次数不超过50次，那么可以从查询位置逆回去操作，就可以发现它在最初序列的位置，再逆回去即可求得当前查询的值，对于一组数据复杂度约为O(50*n)

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<list>
#include<vector>
#define MOD 1000000007LL
using namespace std;
const int maxn=100010;
long long oper[maxn],n;
long long cnt,pos;
long long query(){
long long b=0,i;
for(i=cnt-1;i>=0;--i){
if(oper[i]==1){
if(pos<=(n+1)/2){
pos=2*pos-1;
}
else {
pos=2*(pos-(n+1)/2);
}
}
else if(oper[i]==2){
pos=n-pos+1;
}
else if(oper[i]==3){
b++;
}
}
while(b--){
pos=pos*pos%MOD;
}
return pos;
}
int main()
{
int t,m;
scanf("%d",&t);
while(t--){
scanf("%lld%d",&n,&m);
char str[5];cnt=0;
while(m--){
scanf("%s%lld",str,&pos);
if(str[0]=='O'){
oper[cnt++]=pos;
}
else {
printf("%lldn",query());
}
}
}
return 0;
}