Educational Codeforces Round 70 (Rated for Div. 2)

A.You Are Given Two Binary Strings

乘2^k次，其实就是把二进制左移了k位

加法就是对应位加就好了，然后再把字符反转一下

如果想要得到的字符串字典序最小，那么第一个1出现的位置要尽可能靠后

那么就是x 的长度大于等于 y 最右边的1要用y最右边的1消去

需要左移几位k就是多少

D.Print a 1337-string

题目思路：

要求你输出一个串，里面有N个子序列”1337”

设有 n 个1，m个3，k个7

那么种类数就是 $n * k * C {^2}_m​$

三个变量比较多，我们假设只输出一个7，那么就是$n * C {^2}_m​$

那么我们预处理出来组合数C（$i * (i-1) / 2​$）的值，找一个N能整除的Ci，输出就行，但是题中要求输出字符串的长度最长只能是1e5，一个质数只能整除C2，显然不行

那么我们能不能找一个$n_1 * C {^2}{m_1} + n_1 * C {^2}{m_2} + n_2 * C {^2}_{m_3} * ……=N ​$

显然可以，C2 = 1,一定可以造出来

但是一个串中后面的3中也是可以给前面用的，所以m一定是递减的,”13311337”前面俩个三也可以结合后面的，m1 = 4,n1 = 1,m2 = 2,n2 = 2

因为字符串不能大于1e5，所以我们选择Ci要小于 5e4（i < 400）,n也要小于 1e4（这个范围可以浮动，保证算出来nj + i不大于1e5就行）（5e4 * 1e4 * 2 > 1e9 此时字符串长度才（400 + 20000）

然后枚举Ci，二分找一个范围内最大的n，n*Ci小于剩下的N，直到N = 0;

题目代码：

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
int T,N,M,K;
/*-------------------------------------------------------------------------------------------*/
vector<LL> b;
/* ------------------------------------------------------------------------------------------*/
 
 
int main()
{
    //std::ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //freopen("input.in","r",stdin);
    //freopen("output.out","w",stdout);
/* -----------------------------------------------------------------------------------------*/
    LL a;
    for(int i = 2;i < MAX;i++)
    {
        a = (i * (i-1)) / (LL)2;
        b.push_back(a);
        if(a > 50000) break;
    }
    scanf("%d",&T);
    while(T--)
    {
        vector<int> ansn;
        vector<int> ansm;
        scanf("%d",&N);
        for(int i = b.size()-1;i >= 0;i--)
        {
            if(b[i] > N) continue;
            else
            {
                int l = 1;
                int r = 10000;
                while(r > l)
                {
                    int mid = (l+r) / 2;
                    if(N / mid > 0) l = mid+1;
                    else r = mid - 1;
                }
                for(int j = (l+r) / 2;j >= 1;j--)
                {
                    if(b[i] * j <= N)
                    {
                        N -= b[i]*j;
                        ansm.push_back(j);
                        ansn.push_back(i+2);
                        break;
                    }
                }
            }
            if(N == 0) break;
        }
        for(int i = 0;i < ansn.size();i++)
        {
            for(int j = 1;j <= ansm[i];j++)
            {
                printf("1");
            }
 
            int n;
            if(i != ansn.size()-1) n = ansn[i] - ansn[i+1];
            else n = ansn[i];
 
            for(int j = 1;j <= n ;j++)
            {
                printf("3");
            }
        }
       printf("7\n");
    }
    return 0;
}