BigHead
0%

01的时间

Posted on Edited on In , Views: Valine:

01的时间

题意

给你一个数x，让你找到x的倍数，同时这个倍数只能包含01数字(十进制)，输出最小的符合条件的

分析

1.这题本意是想让我们用搜索的，但写过数位dp后对这题第一反应就是可以dp啊。
dp[i][j][0]表示当前i长度余j并且第i位取0可不可达，同理dp[i][j][1]。

首先预处理出当第i位是1时对x取模的余数状态转移的话
*dp[i][j][0] |= dp[i-1][j][0] || dp[i-1][j][1];
dp[i][j][1] |= dp[i-1][(j-base[j]+x)%x][0] || dp[i-1][(j-base[j]+x)%x][1]; *

2.全部切记初始化0,dp[0][0][0] = 1;

思考

  • 1.这里刚开始我把dp所存的值弄混淆了，存了当前的最小值是多少，同时还开了一个辅助flag作为标记能不能可达。但是，后面想一想，完全没必要。因为当状态转移好之后，第一个首位是1并且取余是0的状态就是最小的(这个可以反向想一下)。找到最小的状态之后，剩下的就是往回找，看前一个是由谁转移来的。

  • 2.前面的转移式是最基本的转移，但实际转移中为了回溯更方便可以dp记录上一位的取值情况，不可到达初始为-1. 当有两种可选的状态的时候选较小的。

  • 3.我曾经错误以为：上述过程有一个性质就是，对于所找到的第一个符合条件首位是1的数字，他的之前所有状态都只有一个前述状态。为什么？

  • 4.假如他可以由两个状态转移y,z转移过来，那么(y-z)%x==0,那么就会出现一个比当前更小的符合条件的。但是后面想一想（y-z）可能不符合只含01这个条件。（但是如果没有这个限制的话，这就是一个可以利用的性质）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
/*************************************************************************
	> File Name: c.cpp
	> Author: liangxianfeng
	> Mail:   641587852@qq.com
	> Created Time: 2016年05月02日 星期一 22时07分26秒
 ************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<stack>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<string>
#include<cmath>
using namespace std;
#define ll long long
#define rep(i,n) for(int i =0; i < n; ++i)
#define CLR(x) memset(x,0,sizeof x)
#define MEM(a,b) memset(a,b,sizeof a)
#define pr(x) cout << #x << " = " << x << " ";
#define prln(x) cout << #x << " = " << x <<  endl; 
const int maxn = 4e5+100;
const int INF = 0x3f3f3f3f;
int num[maxn];
void get(int x) {
    num[0] = 1%x;
    for(int i = 1; i <= 250; ++i){
        num[i] = num[i-1]*10%x;
    }
}
int ans[maxn];

bool dfs(int pos, int x, int mod, bool ok) {
    if(mod == 0 && ok) {
        for(int i = pos-1; i >= 0; --i){
            printf("%d", ans[i]);
            return true;
        } 
    }

}
struct Node{
    int flag, last;
};
Node dp[512][10512][2];
int main(){
#ifdef LOCAL
	freopen("/home/zeroxf/桌面/in.txt","r",stdin);
    freopen("/home/zeroxf/桌面/out.txt","w",stdout);
#endif
    int n, kase;
    scanf("%d", &kase);
    while(kase--){
        scanf("%d", &n);
        get(n);
        
        memset(dp, -1 , sizeof dp);
        for(int i = 0; i <= 110; ++i){
            for(int j = 0; j <= n; ++j){
                dp[i][j][0].last = dp[i][j][1].last = -1;
                dp[i][j][1].flag = dp[i][j][0].flag = 0;
            }
        }
        dp[0][0][0].last = 0;
        dp[0][0][0].flag = false;
        for(int i = 0; i <= 100; ++i){
            for(int j = 0; j< n; ++j){
                if(dp[i][j][0].last != -1){
                    //pr(i);pr(j);pr(i+1);prln((j+num[i])%n);
                    //prln(dp[i][j][0].last);
                    if(dp[i][j][0].flag){
                        if(!dp[i+1][(j+num[i])%n][1].flag){
                            dp[i+1][(j+num[i])%n][1].flag = true;
                            dp[i+1][(j+num[i])%n][1].last = j*2;
                        }
                        if(!dp[i+1][(j)%n][0].flag){
                            dp[i+1][(j)%n][0].flag = true;
                            dp[i+1][(j)%n][0].last = j*2;
                        }
                    } else {
                        if(!dp[i+1][(j+num[i])%n][1].flag){
                            dp[i+1][(j+num[i])%n][1].flag = true;
                            dp[i+1][(j+num[i])%n][1].last = j*2;
                        }
                        if(!dp[i+1][(j)%n][0].flag){
                            dp[i+1][(j)%n][0].flag = false;
                            dp[i+1][(j)%n][0].last = j*2;
                        }
                        
                    }
                } 
                if(dp[i][j][1].last != -1){
                        //pr(i);pr(j);pr(i+1);prln((j+num[i])%n);
                       // prln(dp[i][j][1].last);
                        if(!dp[i+1][(j+num[i])%n][1].flag){
                            dp[i+1][(j+num[i])%n][1].flag = true;
                            dp[i+1][(j+num[i])%n][1].last = j*2+1;
                        }
                        if(!dp[i+1][(j)%n][0].flag){
                            dp[i+1][(j)%n][0].flag = true;
                            dp[i+1][(j)%n][0].last = j*2+1;
                        }
                } 
            }
        }
        int ans = -1, pos = 0;
        for(int i = 1; i <= 100; ++i){
            if(dp[i][0][1].flag){
                ans = 1;
                pos = i;
                break;
            }
        }
        while(pos != 0){
            if(ans%2) {
                printf("1");
            } else printf("0");
            ans = dp[pos][ans/2][ans%2].last;
            pos--;
        }
        printf("\n");
    }
	return 0;
}