Cloud基特(Kit) 初探与教学 – 签到应用

查询

假诺本身想查询名字中含有 Dylan 的

    NSPredicate *predicate = [NSPredicate predicateWithFormat:@"name CONTAINS 'Dylan'"];
    CKQuery *query = [[CKQuery alloc] initWithRecordType:@"Place" predicate:predicate];

    [publicDB performQuery:query
              inZoneWithID:nil
         completionHandler:^(NSArray *results, NSError *error) {
             // ...
    }];

Sample Output

2
60
111
3
43
343

上面,新建一个职位音讯并蕴藏
因为 Cloud基特 在异步运行 saveRecord:completionHandler:
时会使用网络与服务器交互,网络情状是不定的,所以 一定 记得要在 block
中处理错误,一个好的运用应当有周到的错误处理机制。
您需要检讨 NSError
对象来规定正在处理哪一种错误。例如,无网络线连接的时候会触发CKErrorNetworkUnavailable
类型的失实,然后您需要做的就是没戏后重试。等等,那么要什么日期重试呢?顿时,依然十秒之后?别担心,CloudKit在 error 的 userInfo 字典中提供了一个提出的重试时间 CKErrorRetryAfterKey

Sample Input

3
1
2
3

更改一个已经存在的职位音信

Sample Input

2
24
96

#import <CloudKit/CloudKit.h>
// ...
CKDatabase *publicDB = [[CKContainer defaultContainer] publicCloudDatabase];

Valley Numer

订阅通告

    NSPredicate *predicate = [NSPredicate predicateWithFormat:@"description CONTAINS 'party'"];

    CKSubscription *subscription = [[CKSubscription alloc] initWithRecordType:@"Checkin" predicate:predicate options:CKSubscriptionOptionsFiresOnRecordCreation];

    CKNotificationInfo *info = [CKNotificationInfo new];
    info.alertLocalizationKey = @"NEW_PARTY_ALERT_KEY";
    info.soundName = @"NewAlert.aiff";
    info.shouldBadge = YES;

    subscription.notificationInfo = info;

    [publicDB saveSubscription:subscription
             completionHandler:^(CKSubscription *subscription, NSError *error) {
                 //...
             }];

收纳推送通告时,在 app delegate 中拍卖

- (void)application:(UIApplication *)application didReceiveRemoteNotification:(NSDictionary *)userInfo{
    CKNotification *ckNotification = [CKNotification notificationFromRemoteNotificationDictionary:userInfo];
    if (ckNotification.notificationType == CKNotificationTypeQuery) {
        CKQueryNotification *queryNotification = ckNotification;
        CKRecordID *recordID = [queryNotification recordID];
        // ...
    }
}

此时此刻苹果允许你利用 Cloud基特(Kit) 存储 10 GB 资源,100 M 数据库存储,每日 2 GB
流量;当您的用户数量扩大的时候,这么些免费额度也对应地追加到 1 PB 存储、10
TB 数据库存储,以及天天 200 TB 流量

WWDC 2015 中提到,CloudKit 已经 不仅 可以在 iOS 和 OS X
上运用,可以在您的网站上并轨CloudKit
JS
,以便
iCloud 用户可以在浏览器中也能应用相应的效果,或者是利用 CloudKit web
service

对 Cloud基特(Kit) 服务端直接进行 HTTP
请求。这意味着,现在此外活动或桌面平台都足以动用 Cloud基特(Kit) 了!

CopyRight@Dylan. Copy@NSHipster

Problem Description

大庭广众,度度熊以来沉迷于 Pokémon GO。

图片 1

前日它控制要吸引所有的精灵球!
为了不让度度熊失望,精灵球已经被优先停放在一个2*N的格子上,每一个格子上都有一个精灵球。度度熊可以选用随机一个格子起首游戏,抓捕格子上的精灵球,然后移动到一个紧邻的起码有一个公共点的格子上接轨通缉。例如,(2,
2) 的附近格子有(1, 1), (2, 1) 和 (1, 2) 等等。
现在度度熊希望通晓将持有精灵球都抓到并且步数最少的方案数目。多少个方案被认为是例外,当且仅当六个方案至少有一步所在的格子是见仁见智的。

    CKRecordID *greatID = [[CKRecordID alloc] initWithRecordName:@"GreatPlace"];

    [publicDB fetchRecordWithID:greatID completionHandler:^(CKRecord *fetchedPlace, NSError *error) {
         // handle errors here
    }];

Output

对每组数据输出第一次回到已经渡过的岗位时的授命下标i (1≤i≤N)。
万一这种情形并未爆发,请输出 “Catch you”。

    CKRecordID *markID = [[CKRecordID alloc] initWithRecordName:@"mark"];

    CKRecord *place = [[CKRecord alloc] initWithRecordType:@"Place" recordID:markID];

    [publicDB saveRecord:place completionHandler:^(CKRecord *savedPlace, NSError *error) {

        if (!error) {

            NSLog(@"[success]\n keys: %@\n type: %@\n rName: %@", savedPlace.changedKeys, savedPlace.recordType, savedPlace.recordID.recordName);
        } else {

            NSLog(@"[error]\n info:%@", error.userInfo);

            double retryAfterValue = [error.userInfo[CKErrorRetryAfterKey] doubleValue];
            NSDate *retryAfterDate = [NSDate dateWithTimeIntervalSinceNow:retryAfterValue];

            NSLog(@"[retrydata]\n %@", retryAfterDate);
        }
    }];

Problem Description

一目掌握,度度熊相当喜爱数字。

它目前在求学小学算术,第一次发现这几个世界上仍旧存在两位数,三位数……甚至N位数!

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

图片 2

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
取模。

Convenience API 顾名思义是对 Cloud基特 操作的有益 API。利用 Convenience
API 就可以对 record 举行数据的二种基本操作:存储、读取、更改。
那么,继续完善我们的报到应用吧!起首前记得应用 Cloud基特框架并取得公开数据库的引用:

【SinGuLaRiTy-1038】 Copyright (c) SinGuLaRiTy 2017. All Rights
Reserved.

  • CKContainer
    Containers
    就像应用运行的沙盒一样,一个运用只可以访问自己沙盒中的内容而无法访问其他使用的。Containers
    就是最外层容器,每个应用有且仅有一个属于自己的
    container。(事实上,经过开发者授权配置 Cloud基特(Kit) Dashboard
    之后,一个使用也可以访问其他使用的 container。)
  • CKDatabase
    Database
    即数据库,私有数据库用来囤积敏感信息,比如说用户的性别年龄等,用户只可以访问自己的民用数据库。应用也有一个公开的数据库来囤积公共音信,例如你在构建一个依照地理地点签到的使用,那么地理地点信息就应该储存在公私数据库里以便所有用户都能访问到。
  • CKRecord
    即数据库中的一条数据记录。Cloud基特 使用 record 通过 k/v
    结构来囤积结构化数据。关于键值存储,目前值的架构协理NSString、NSNumber、NSData、NSDate、CLLocation,和
    CKReference、CKAsset(这五个下面大家会声明),以及存储以上数据类型的数组。
  • CKRecordZone
    Record 不是以零星的措施存在于 database 之中的,它们放在 record zones
    里。每个应用都有一个 default record zone,你也足以有自定义的 record
    zone。
  • CKRecordIdentifier
    是一条 record 的绝无仅有标识,用于确定该 record 在数据库中的唯一地点。
  • CKReference
    Reference 很像 RDBMS
    中的引用关系。依旧以地理地方签到应用为例,每个地理地方可以涵盖众多用户在该职务的登录,那么地点与签到之间就形成了这么一种含有式的依附关系。
  • CKAsset
    即资源文件,例如二进制文件。如故以签到使用为例,用户签到时或许还包含一张相片,那么这张照片就会以
    asset 格局储存起来。

Problem Description

强烈,度度熊异常欣赏图。
它如今发觉了图中也是足以出现 valley —— 山谷的,像下边这张图。

图片 3

为了形成山谷,首先要将一个图的巅峰标记为高点或者低点。标记完成后倘诺一个终极三元组<X,
Y,
Z>中,X和Y之间有边,Y与Z之间也有边,同时X和Z是高点,Y是低点,那么它们就结成一个valley。
度度熊想清楚一个无向图中最多能够整合多少个valley,一个极限最六只可以出现在一个valley中。

    CKRecordID *greatID = [[CKRecordID alloc] initWithRecordName:@"GreatPlace"];

    [publicDB fetchRecordWithID:greatID completionHandler:^(CKRecord *fetchedPlace, NSError *error) {
        if (fetchedPlace != nil) {
            NSString *name = fetchedPlace[@"name"];
            fetchedPlace[@"name"] = [name stringByAppendingString:@" Door A"];

            [publicDB saveRecord:fetchedPlace completionHandler:^(CKRecord *savedPlace, NSError *savedError) {
                //...
            }];
        } else {
            // handle errors here
        }
    }];

Arithmetic of Bomb

Cloud基特 的功底对象类型有 7
种。这一个目的类型或者和你在任何编程领域了然的切近对象类型稍有反差。

Code

如法炮制,签到题不解释。

#include<cstdio>
#include<cstring>
#include<cctype>
#include<cmath>
#include<algorithm>

#define ll long long
#define inf 0x3f3f3f3f
#define maxn 101000
#define MOD 1000000007

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

下面,获取一个岗位新闻

Sample Input

图片 4图片 5

3
3 2 2
1 2
1 3
2 3
3 2 2
1 2
1 3
1 2
7 6 5
1 2
1 3
1 4
2 3
2 6
2 7
3 4 5 6 7

View Sample Input

谬误状况

Sample Output

1
0
2

Sample Input

6
1-2+3
(1-2+3)#(3)
(1)#(3)
(1+)#(2)1
(2*3+1)#(2)
(2)#(2)1+1(2)#(2)

Output

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

Valley Numer II

Arithmetic of Bomb II

Output

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

Sample Input

3
3
14
120

Problem Description

明明,度度熊以来沉迷于 Pokémon GO。

图片 6

鉴于太过沉迷,现在它不得不依据游戏内置的命令行走了:对,简直就像一个具体中的Pokémon!
游戏内置的吩咐实际上可以抽象成一种:保持现在的朝向前行X米,然后右转。度度熊相信,只要依据这多少个命令,它就必定可以抓到最难能可贵的精灵球。
但不幸的是,这些命令并不是很有可信度,有时会携带度度熊走回原来的职位。现在它想精通,在第几条指令时它首先次回到已经度过的岗位?假设这种气象并未生出,请输出
“Catch you”。

Code

状压DP

#include<cstdio>
#include<cstring>
#include<cctype>
#include<cmath>
#include<algorithm>

#define ll long long

using 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<<i)))
            {
                c|=(1<<i);
                dfs(dep+1,now,pre,cyc,x);
                c^=(1<<i);
            }
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        n=read();m=read();k=read();
        int u,v;
        memset(Map,0,sizeof(Map));
        for(int i=1;i<=m;i++)
        {
            u=read();v=read();
            Map[u][v]=Map[v][u]=1;
        }
        memset(high,0,sizeof(high));
        for(int i=1;i<=k;i++)
        {
            u=read();
            high[u]=1;
        }
        int nowk=0;
        for(int i=1;i<=n;i++)if(high[i])hi[++nowk]=i;
        k=nowk;
        memset(f,0,sizeof(f));
        int x=1;
        for(int i=1;i<=n;i++)if(!high[i])
        {
            x=1-x;
            memset(f[x],0,sizeof(f[x]));
            for(int j=0;j<(1<<k);j++)
            {
                f[x][j]=max(f[x][j],f[1-x][j]);
                c=j;
                dfs(1,x,1-x,j,i);
            }
        }
        int ans=0;
        for(int i=0;i<(1<<k);i++)ans=max(ans,f[x][i]);
        printf("%d\n",ans);
    }
    return 0;
}

 

Time: 2017-08-24

Pokémon GO

Output

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

Sample Output

1

111

12124222

212121205

Sample Input

3

14

119

Output

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

Output

对每组数据输出最多能构成的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

Input

先是行为T,表示输入数据组数。
每组数据包含一个数N。
●1≤T≤100
●1≤N≤10000

Code

自我还不会矩阵运算呀,只可以先在此间放一放大牛的代码了(能做出这道题的确佩服!)

【本题题解来自于:y5zsq

图片 7

Input

首先行为T,表示输入数据组数。
每组数据包含一个数N。
● 1≤T≤200
● 1≤length(N)≤100

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

Pokémon GO II

Problem Descroption

显明,度度熊相当欣赏数字。
它近期在上学小学算术,沉迷于总计A+B中腐败。
而是这回的算术题可并不简单,由于含有表示bomb的#号,度度熊称之为
Arithmetic of Bomb。

图片 8

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 expression> := <bomb term> | <bomb expression>
<bomb term>
<bomb term> := <bomb statement> | ‘(‘ <bomb statement>
‘)’ ‘#’ ‘(‘ <number> ‘)’
<bomb statement> := <bomb element> | <bomb statement>
<bomb element>
<bomb element> := <digit> | ‘+’ | ‘-‘ | ‘*’
<normal expression> := <norm term> | <normal
expression> ‘+’ <norm term> | <normal expression> ‘-‘
<norm term>
<norm term> := <number> | <norm term> ‘*’
<number>
<number> := <digit> | <non-zero-digit>
<number>
<digit> := ‘0’ | <non-zero-digit>
<non-zero-digit> := ‘1’ | ‘2’ | ‘3’ | ‘4’ | ‘5’ | ‘6’ | ‘7’ | ‘8’
| ‘9’
“`
请先将Bomb Expression中负有的#号举行,使其变为Normal
Expression(题目标输入保证展开后是一个合法的诺玛(Norma)l
Expression),再来总括这些表明式的结果。

Problem Description

众目睽睽,度度熊至极喜欢数字。
它目前表明了一种新的数字:Valley Number,像山谷一样的数字。

图片 9

当一个数字,从左到右依次看过去数字没有出现先递增接着递减的“山峰”现象,就被称作
Valley
Number。它可以递增,也得以递减,仍可以先递减再递增。在递增或递减的进程中得以现身相等的动静。
比如,1,10,12,212,32122都是 Valley Number。
121,12331,21212则不是。
度度熊想精通不领先N的Valley Number数有稍许。
专注,前导0是不合法的。

Code

动态规划

#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<cstring>

#define ll long long
const 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;
}

Sample Input

4

1

(1)#(3)

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

(12)#(5)

Code

目测几何神犇题,发现可以描绘图找规律……第一次覆盖一定发生在轨道的前8段中。

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<cstdlib>

#define MAXN 1000010

using 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<c||d<a);
}

bool intersect(Point a1,Point a2,Point b1,Point b2)
{
    bool is_vertical_a=(a1.x==a2.x),is_vertical_b=(b1.x==b2.x);
    if(is_vertical_a && is_vertical_b)
        return a1.x==b1.x&&overlap(a1.y,a2.y,b1.y,b2.y);
    if(!is_vertical_a && !is_vertical_b)
        return a1.y==b1.y&&overlap(a1.x,a2.x,b1.x,b2.x);
    if(is_vertical_a)
    {
        swap(a1,b1);
        swap(a2,b2);
    }
    return !(max(a1.x,a2.x)<b1.x||min(a1.x,a2.x)>b1.x||max(b1.y,b2.y)<a1.y||min(b1.y,b2.y)>a1.y);
}

int solve()
{
    int x=0,y=0;
    for(int i=0;i<N;++i)
    {
        x+=dx[i&3]*a[i];
        y+=dy[i&3]*a[i];
        points[i+1].x=x;
        points[i+1].y=y;
        for(int j=max(0,i-8);j<i-2;++j)
            if(intersect(points[j],points[j+1],points[i],points[i+1]))
                return i;
    }
    return -1;
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d",&N);
        for(int i=0;i<N;++i)
            scanf("%d",a+i);
        int result=solve();
        if(result==-1)
            printf("Catch you\n");
        else
            printf("%d\n", result+1);
    }
    return 0;
}

Input

首先行为T,表示输入数据组数。

每组数据包含一个Bomb Expression。

– 1≤T≤100

– 1≤length(Bomb Number)≤1000

Input

首先行为T,表示输入数据组数。
每组数据的率先行包含一个数N,表示指令长度。接着的一行包含N个数字Xi,表示第i个指令中提升的距离。
● 1≤T≤100
● 1≤N≤1 000 000
● 1≤Xi≤1 000 000 000

Sample Input

3
4
2 2 2 2
4
2 1 3 1
5
2 1 3 1 3

Code

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
#define maxn 300005
#define mod 1000000007
vector<string>term;
vector<ll>num;
char c[maxn]; 
int T;
void Deal()
{
    term.clear(),num.clear();
    int n=strlen(c);
    for(int i=0;i<n;)
    {
        string s;
        if(c[i]=='(')
        {
            i++;
            while(c[i]!=')')s.push_back(c[i++]);
            i+=3;
            ll t=0;
            while(c[i]!=')')t=t*10+c[i++]-'0';
            if(t)term.push_back(s),num.push_back(t);
            i++;
        }
        else
        {
            while(i<n&&c[i]!='(')s.push_back(c[i++]);
            term.push_back(s),num.push_back(1);
        }
    }
}
typedef ll Mat[4][4];
Mat A,B,C;
void Mul(Mat &a,Mat b)
{
    Mat c;
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
        {
            c[i][j]=0;
            for(int k=0;k<4;k++)
                c[i][j]+=a[i][k]*b[k][j];
        }
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            a[i][j]=(c[i][j]%mod+mod)%mod;
}
void Pow(Mat &a,ll b)
{
    if(b==1)return ;
    Mat c;
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            c[i][j]=(i==j);
    while(b)
    {
        if(b&1)Mul(c,a);
        Mul(a,a);
        b>>=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<term.size();k++)
    {
        string s=term[k];
        ll t=num[k];
        int n=s.size();
        for(int i=0;i<4;i++)
            for(int j=0;j<4;j++)
                B[i][j]=(i==j);
        for(int i=0;i<n;i++)
        {
            memset(C,0,sizeof(C));
            C[0][0]=C[3][3]=1;
            if(s[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); 
        }
        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<n;i++)
            {
                memset(C,0,sizeof(C));
                C[0][0]=C[3][3]=1;
                if(s[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;
}

Code

记忆化搜索/数位DP

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cctype>
#define ll long long
using 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;
}

Sample Output

4
Catch you
5