2017"百度之星"程序设计大赛

Arithmetic of Bomb

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Problem Description

众所周知，度度熊非常喜欢数字。

它最近在学习小学算术，第一次发现这个世界上居然存在两位数，三位数……甚至N位数！

但是这回的算术题可并不简单，由于含有表示bomb的#号，度度熊称之为 Arithmetic of Bomb。

![](../../../data/images/C777-1001-1.jpg)

Bomb Number中的bomb，也就是#号，会展开一些数字，这会导致最终展开的数字超出了度度熊所能理解的范畴。比如”(1)#(3)”表示”1”出现了3次，将会被展开为”111”，

同理，”(12)#(2)4(2)#(3)”将会被展开为”12124222”。

为了方便理解，下面给出了Bomb Number的BNF表示。

```
<bomb number> := <bomb term> | <bomb number> <bomb term>
<bomb term> := <number> | '(' <number> ')' '#' '(' <non-zero-digit> ')'
<number> := <digit> | <digit> <number>
<digit> := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
<non-zero-digit> := '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
```

请将Bomb Number中所有的#号展开，由于数字可能很长，结果对 1 000 000 007 取模。

Input

第一行为T，表示输入数据组数。

每组数据包含一个Bomb Expression。

- 1≤T≤100

- 1≤length(Bomb Number)≤1000

Output

对每组数据输出表达式的结果，结果对 1 000 000 007 取模。

Sample Input

4
1
(1)#(3)
(12)#(2)4(2)#(3)
(12)#(5)

Sample Output

Source

2017"百度之星"程序设计大赛 - 复赛

思路：模拟；根据BNF得到重复个数小于10；

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<queue>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#include<list>
#include<set>
#include<map>
using namespace std;
#define LL __int64
#define pi (4*atan(1.0))
#define eps 1e-8
#define bug(x)  cout<<"bug"<<x<<endl;
const int N=2e3+10,M=2e6+10,inf=1e9+10;
const LL INF=1e18+10,mod=1e9+7;

char a[N];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",a);
        int n=strlen(a);
        LL ans=0;
        for(int i=0;i<n;i++)
        {
            if(a[i]=='(')
            {
                int pos;
                for(int j=i;;j++)
                if(a[j]==')')
                {
                    pos=j;
                    break;
                }
                int num=a[pos+3]-'0';
                for(int k=0;k<num;k++)
                {
                    for(int l=i+1;l<pos;l++)
                    {
                        ans=(ans*10+a[l]-'0')%mod;
                    }
                }
                i=pos+4;
            }
            else ans=(ans*10+a[i]-'0')%mod;
        }
        printf("%lld
",ans);
    }
    return 0;
}

Pokémon GO

Accepts: 738

Submissions: 1725

Time Limit: 3000/1500 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

众所周知，度度熊最近沉迷于 Pokémon GO。

今天它决定要抓住所有的精灵球！

为了不让度度熊失望，精灵球已经被事先放置在一个2*N的格子上，每一个格子上都有一个精灵球。度度熊可以选择任意一个格子开始游戏，抓捕格子上的精灵球，然后移动到一个相邻的至少有一个公共点的格子上继续抓捕。例如，(2, 2) 的相邻格子有(1, 1), (2, 1) 和 (1, 2) 等等。

现在度度熊希望知道将所有精灵球都抓到并且步数最少的方案数目。两个方案被认为是不同，当且仅当两个方案至少有一步所在的格子是不同的。

思路：原题；http://blog.csdn.net/yanghui07216/article/details/50490089

Valley Numer

Accepts: 548

Submissions: 1125

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

众所周知，度度熊非常喜欢数字。

它最近发明了一种新的数字：Valley Number，像山谷一样的数字。

当一个数字，从左到右依次看过去数字没有出现先递增接着递减的“山峰”现象，就被称作 Valley Number。它可以递增，也可以递减，还可以先递减再递增。在递增或递减的过程中可以出现相等的情况。

比如，1，10，12，212，32122都是 Valley Number。

121，12331，21212则不是。

度度熊想知道不大于N的Valley Number数有多少。

注意，前导0是不合法的。

思路：数位dp，dp[i][j][k]表示第i位前一位为j的方案数，k==0表示前面没有递增的情况，k==1表示有递增的情况；

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<queue>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#include<list>
#include<set>
#include<map>
using namespace std;
#define LL __int64
#define pi (4*atan(1.0))
#define eps 1e-8
#define bug(x)  cout<<"bug"<<x<<endl;
const int N=2e3+10,M=2e6+10,inf=1e9+10;
const LL INF=1e18+10,mod=1e9+7;

LL f[110][12][3],bit[N];
LL dp(int pos,int pre,int now,int flag,int p)
{
    if(pos==0)return 1;
    if(p&&flag&&f[pos][pre][now]!=-1)return f[pos][pre][now];
    int x=flag?9:bit[pos];
    LL ans=0;
    for(int i=0;i<=x;i++)
    {
        if(!p)
            ans+=dp(pos-1,i,0,flag||i<x,p||i);
        else
        {
            if(now)
            {
                if(i>=pre)ans+=dp(pos-1,i,now,flag||i<x,p||i);
            }
            else
            ans+=dp(pos-1,i,now||i>pre,flag||i<x,p||i);
        }
    }
    ans%=mod;
    if(p&&flag)f[pos][pre][now]=ans;
    return ans;
}
char a[N];
LL getans()
{

    scanf("%s",a);
    int len=0,n=strlen(a);
    for(int i=n-1;i>=0;i--)
        bit[++len]=a[i]-'0';
    return dp(len,0,0,0,0);
}
int main()
{
    memset(f,-1,sizeof(f));
    int T;
    scanf("%d",&T);
    while(T--)
    {
        LL out=getans();
        out=(out+mod-1)%mod;
        printf("%lld
",out);
    }
    return 0;
}