cf 1102 B

题意：求字符串中任意相邻两位是否可以可以由前一个加上任意个x或y屏蔽十位与后一位相等，如果可以需要添加的最少数字是多少,x值为0-9，y值也为0-9，求出任意x,y对应情形下字符串需要添加的最少数字，不满足输出-1，字符串长度小于2e6

思路：初步算下复杂度，10*10*2e6，所以需要预处理所有情况，防止处理过程中TLE，具体预处理，按照floyd跑出最短路，如果最短路为inf则不可达。

代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=2e6+7;
 4 char a[maxn];
 5 const int inf=0x3f3f3f3f;
 6 int dis[15][15];
 7 int main()
 8 {
 9     scanf("%s",a);
10     for(int i=0; i<10; i++)
11     {
12         for(int j=0; j<10; j++)
13         {
14             for(int k=0; k<10; k++)
15             {
16                 for(int l=0; l<10; l++)
17                 {
18                     dis[k][l]=inf;
19                 }
20             }
21             for(int k=0;k<10;k++)
22             {
23                 dis[k][(k+i)%10]=1;
24                 dis[k][(k+j)%10]=1;
25             }
26             for(int k=0;k<10;k++)
27             {
28                 for(int l=0;l<10;l++)
29                 {
30                     for(int s=0;s<10;s++)
31                     {
32                         dis[l][s]=min(dis[l][k]+dis[k][s],dis[l][s]);
33                     }
34                 }
35             }
36             int ans=0;
37             int fi=0;
38             for(int k=0; k<strlen(a)-1; k++)
39             {
40                 if(dis[a[k]-'0'][a[k+1]-'0']==inf)
41                 {
42                     fi=1;
43                     break;
44                 }
45                 else
46                 {
47                     ans+=dis[a[k]-'0'][a[k+1]-'0']-1;
48                 }
49             }
50             if(fi==1)
51             {
52                 printf("-1");
53             }
54             else
55             {
56                 printf("%d",ans);
57             }
58             if(j==9)
59             {
60                 printf("
");
61             }
62             else
63             {
64                 printf(" ");
65             }
66         }
67     }
68 }

View Code

教训：写这道题时自己就不知道咋回事自己就设了个范围，想当然的以为跑到这个值就会将所有值跑出来，做题时不应该想当然，更应该分析题意，从题目入手。