[SinGuLaRiTy] 2017 百度之星程序设计大赛复赛-白红宇

[SinGuLaRiTy] 2017 百度之星程序设计大赛复赛

阅读量：4672 次

发布时间：2019-06-09

本文共 10072 字，大约阅读时间需要 33 分钟。

Arithmetic of Bomb

Problem Description

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

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

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

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

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

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

```

<bomb term> := <number> | '(' <number> ')' '#' '(' <non-zero-digit> ')'

<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

(1)#(3)

(12)#(2)4(2)#(3)

(12)#(5)

Sample Output

111

12124222

212121205

Code

模拟，签到题不解释。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define ll long long#define inf 0x3f3f3f3f#define maxn 101000#define MOD 1000000007using namespace std;int read(){    char c;int s=0,t=1;    while(!isdigit(c=getchar()))if(c=='-')t=-1;    do{s=s*10+c-'0';}while(isdigit(c=getchar()));    return s*t;}int n;char s[maxn],ans[maxn],nows[maxn];int main(){    int T;    scanf("%d",&T);    while(T--)    {        scanf("%s",s+1);        int n=strlen(s+1);        int nowstep=0,len=0,tot=0;        for(int i=1;i<=n;i++)if(isdigit(s[i]))        {            if(nowstep==1){nows[++len]=s[i];}            else                 if(nowstep==2)                {                    for(int j=1;j<=s[i]-'0';j++)                        for(int k=1;k<=len;k++)                            ans[++tot]=nows[k];                    len=0;nowstep=0;                }                else                    if(nowstep==0)ans[++tot]=s[i];        }        else        {            if(nowstep==0&&s[i]=='(')                nowstep=1;            else if(nowstep==1&&s[i]==')')                nowstep=2;        }        long long ansnum=0;        for(int i=1;i<=tot;i++)            ansnum=(ansnum*10+ans[i]-'0')%MOD;        printf("%lld\n",ansnum);    }    return 0;}

Arithmetic of Bomb II

Problem Descroption

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

它最近在学习小学算术，沉迷于计算A+B中不能自拔。

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

Arithmetic of Bomb的目的与普通算术一样，就是计算一些Bomb Expression的结果。比如，”1-2+3”的结果为2。然而，bomb，也就是#号，会展开一些普通表达式，这会导致需要计算的式子超出了度度熊所能理解的范畴。比如”(1-2+3)#(3)”表示”1-2+3”出现了3次，将会被展开为”1-2+31-2+31-2+3”。

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

```

<bomb term> := <bomb statement> | '(' <bomb statement> ')' '#' '(' <number> ')'

<bomb element> := <digit> | '+' | '-' | '*'

<non-zero-digit> := '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

```

请先将Bomb Expression中所有的#号展开，使其成为Normal Expression（题目的输入保证展开后是一个合法的Normal Expression），再来计算这个表达式的结果。

Input

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

每组数据包含一个Bomb Expression。

●1≤T≤50

●1≤length(Bomb Statement)≤10

●1≤length(Number in Bomb term)≤10

●1≤length(Bomb Expression)≤300 000

Output

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

Sample Input

1-2+3

(1-2+3)#(3)

(1)#(3)

(1+)#(2)1

(2*3+1)#(2)

(2)#(2)1+1(2)#(2)

Sample Output

111

343

Code

我还不会矩阵运算呀，只好先在这里放一放大牛的代码了（能做出这道题的确佩服！）

【本题题解来自于：】

Code

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;typedef long long ll;#define maxn 300005#define mod 1000000007vector
            
             term;vector
             
              num;char c[maxn]; int T;void Deal(){ term.clear(),num.clear(); int n=strlen(c); for(int i=0;i
              
               >=1; } for(int i=0;i<4;i++) for(int j=0;j<4;j++) a[i][j]=c[i][j];}ll Count(){ for(int i=0;i<4;i++) for(int j=0;j<4;j++) A[i][j]=(i==j); int sign=1; for(int k=0;k
               
                ='0'&&s[i]<='9') C[1][1]=10,C[2][1]=s[i]-'0',C[2][2]=1; else if(s[i]=='+') C[1][0]=sign,C[3][2]=1,sign=1; else if(s[i]=='-') C[1][0]=sign,C[3][2]=1,sign=-1; else C[1][2]=1; Mul(B,C); } Mul(A,B); if(t>1) { for(int i=0;i<4;i++) for(int j=0;j<4;j++) B[i][j]=(i==j); for(int i=0;i
                
                 ='0'&&s[i]<='9') C[1][1]=10,C[2][1]=s[i]-'0',C[2][2]=1; else if(s[i]=='+') C[1][0]=sign,C[3][2]=1,sign=1; else if(s[i]=='-') C[1][0]=sign,C[3][2]=1,sign=-1; else C[1][2]=1; Mul(B,C); } Pow(B,t-1); Mul(A,B); } } ll ans=(A[2][0]+A[3][0])%mod; if(sign==1)ans=(ans+A[2][1]+A[3][1])%mod; else ans=(ans-A[2][1]-A[3][1])%mod; ans=(ans+mod)%mod; return ans;}int main(){ scanf("%d",&T); while(T--) { scanf("%s",c); Deal(); printf("%I64d\n",Count()); } return 0;}

Pokémon GO

Problem Description

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

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

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

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

Input

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

每组数据包含一个数N。

●1≤T≤100

●1≤N≤10000

Output

对每组数据输出方案数目，结果对 1 000 000 007 取模。

Sample Input

Code

动态规划

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define ll long longconst int maxn=10010,MOD=1000000007;ll a[maxn],b[maxn],n;int main(){ b[1]=1; for(int i=2;i<=maxn;i++) b[i]=(b[i-1]*2)%MOD; a[1]=1; a[2]=6; for(int i=3;i<=maxn;i++) a[i]=(2*a[i-1]+b[i]+4*a[i-2])%MOD; int T; scanf("%d",&T); while(T--) { int n; scanf("%d",&n); ll ans=0; for(int i=2;i<=n-1;i++) ans=(ans+16*b[i-1]%MOD*a[n-i])%MOD; ans=(ans+4*a[n])%MOD; if(n==1) ans=2; printf("%lld\n",ans); } return 0;}

Pokémon GO II

Problem Description

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

由于太过沉迷，现在它只能按照游戏内置的指令行走了：对，简直就像一个现实中的Pokémon！

游戏内置的指令实际上可以抽象成一种：保持现在的朝向前行X米，然后右转。度度熊相信，只要遵循这个指令，它就一定可以抓到最珍奇的精灵球。

但不幸的是，这个指令并不是很有可信度，有时会引导度度熊走回原来的位置。现在它想知道，在第几条指令时它第一次回到已经走过的位置？如果这种情况没有发生，请输出 “Catch you”。

Input

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

每组数据的第一行包含一个数N，表示指令长度。接着的一行包含N个数字Xi，表示第i个指令中前行的距离。

● 1≤T≤100

● 1≤N≤1 000 000

● 1≤Xi≤1 000 000 000

Output

对每组数据输出第一次回到已经走过的位置时的指令下标i (1≤i≤N)。

如果这种情况没有发生，请输出 “Catch you”。

Sample Input

2 2 2 2

2 1 3 1

2 1 3 1 3

Sample Output

Catch you

Code

目测几何神犇题，发现可以画画图找规律......第一次覆盖一定发生在轨迹的前8段中。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define MAXN 1000010using namespace std;const int dx[]={ 0,1,0,-1},dy[]={ 1,0,-1,0};int N,a[MAXN];struct Point{ int x,y; Point(int _x=0,int _y=0):x(_x),y(_y){}}points[MAXN];bool overlap(int a,int b,int c,int d){ if(a>b) swap(a, b); if(c>d) swap(c, d); return !(b
           
            
             b1.x||max(b1.y,b2.y)
             
              a1.y);}int solve(){ int x=0,y=0; for(int i=0;i

Valley Numer

Problem Description

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

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

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

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

121，12331，21212则不是。

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

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

Input

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

每组数据包含一个数N。

● 1≤T≤200

● 1≤length(N)≤100

Output

对每组数据输出不大于N的Valley Number个数，结果对 1 000 000 007 取模。

Sample Input

120

Sample Input

119

Code

记忆化搜索/数位DP

#include
     
      #include
      
       #include
       
        #include
        
         #define ll long longusing namespace std;const ll maxn=110,MOD=1000000007;ll f[maxn][2][10],a[maxn],n;char s[maxn];ll dfs(ll pos,ll state,ll limit,ll pre){    if(pos==-1)    {        if(~pre)            return 1;        else            return 0;    }    if(!limit&&~pre&&~f[pos][state][pre])        return f[pos][state][pre];    ll up=limit?a[pos]:9;    ll ans=0;    for(int i=0;i<=up;i++)    {        if(pre==-1&&i==0)            ans=(ans+dfs(pos-1,state,limit&&i==up,pre))%MOD;        else if(pre==-1&&i!=0)            ans=(ans+dfs(pos-1,state,limit&&i==up,i))%MOD;        else if(state==0)            ans=(ans+dfs(pos-1,i>pre,limit&&i==up,i))%MOD;        else if(state==1&&i>=pre)            ans=(ans+dfs(pos-1,state,limit&&i==up,i))%MOD;    }    if(!limit&&~pre)        f[pos][state][pre]=ans;    return ans;}int main(){    ll T;    scanf("%lld",&T);    memset(f,-1,sizeof(f));    while(T--)    {        scanf("%s",s+1);        n=strlen(s+1);        for(int i=1;i<=n;i++)            a[n-i]=s[i]-'0';        printf("%lld\n",dfs(n-1,0,1,-1));    }    return 0;}

Valley Numer II

Problem Description

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

它最近发现了图中也是可以出现 valley —— 山谷的，像下面这张图。

为了形成山谷，首先要将一个图的顶点标记为高点或者低点。标记完成后如果一个顶点三元组<X, Y, Z>中，X和Y之间有边，Y与Z之间也有边，同时X和Z是高点，Y是低点，那么它们就构成一个valley。

度度熊想知道一个无向图中最多可以构成多少个valley，一个顶点最多只能出现在一个valley中。

Input

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

每组数据的第一行包含三个整数N，M，K，分别表示顶点个数，边的个数，标记为高点的顶点个数。

接着的M行，每行包含两个两个整数Xi，Yi，表示一条无向边。

最后一行包含K个整数Vi，表示这些点被标记为高点，其他点则都为低点。

● 1≤T≤20

● 1≤N≤30

● 1≤M≤N*(N-1)/2

● 0≤K≤min(N,15)

● 1≤Xi, Yi≤N, Xi!=Yi

● 1≤Vi≤N

Output

对每组数据输出最多能构成的valley数目。

Sample Input

33 2 21 21 32 33 2 21 21 31 27 6 51 21 31 42 32 62 73 4 5 6 7

View Sample Input

Sample Output

Code

状压DP

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define ll long longusing namespace std;int read(){    char c;int s=0,t=1;    while(!isdigit(c=getchar()))if(c=='-')t=-1;    do{s=s*10+c-'0';}while(isdigit(c=getchar()));    return s*t;}const int inf=0x3f3f3f3f,maxn=40,maxk=80010;int n,f[2][maxk],c,k,m,hi[maxn];bool Map[maxn][maxn],high[maxn];void dfs(int dep,int now,int pre,int cyc,int x){    if(dep==3)        f[now][c]=max(f[now][c],f[pre][cyc]+1);    else        for(int i=0;i<=k-1;i++)            if(Map[x][hi[i+1]]&&!(c&(1<