这场CF打得辣鸡的死，rating直线下掉，唉。。。 比赛链接：传送门

A A Compatible Pair

Solution

N^3暴力枚举所有情况即可

Code

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
#include <bits/stdc++.h>
#define LL long long

using namespace std;

int N, M;
int A[100], B[100];

int main()
{
#ifdef hk_cnyali
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    scanf("%d%d", &N, &M); 
    for (int i = 1; i <= N; ++i) scanf("%d", &A[i]);
    for (int i = 1; i <= M; ++i) scanf("%d", &B[i]);
    LL Ans = LLONG_MAX;
    for (int i = 1; i <= N; ++i)
    {
        LL Sum = LLONG_MIN, Summ = 1;
        for (int j = 1; j <= N; ++j)
            for (int k = 1; k <= M; ++k)
            {
                if (j != i)
                    Sum = max(Sum, (LL)A[j] * B[k]);
            }
        Ans = min(Ans, Sum);
    }
    cout<<Ans<<endl;
    return 0;
}

Summary

要注意Ans和Sum一定要开到最大/最小，考场上Sum赋的0x3f3f3f3f3f3f3f(少写了个3f)然后就悲催地FST了。。。 以后开inf都用INT_MAX和LLONG_MAX算了

B A Prosperous Lot

Solution

36则无解，否则用8凑2,0凑1即可

Code

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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
    #include <bits/stdc++.h>
    
    using namespace std;
    
    int N;
    
    int main()
    {
    #ifdef hk_cnyali
        freopen("B.in", "r", stdin);
        freopen("B.out", "w", stdout);
    #endif
        scanf("%d", &N);
        if (N == 1)
        {
            cout<<4<<endl;
            return 0;
        }
        if (N > 18 * 2){cout<<-1<<endl; return 0;}
        if (N & 1) 
        {
            for (int i = 1; i <= N / 2; ++i) cout<<"8";
            cout<<0<<endl;
        }
        else 
        {
            for (int i = 1; i <= N / 2; ++i)
                cout<<"8";
            cout<<endl;
        }
        return 0;
    }
   ``` 

### Summary

开始被hack了半天没找出错，后来才发现原来10^18是19位数，开始想成了不能超过17位数然后就gg了

C A Twisty Movement
-------------------

### Solution

设Dp\[i\]\[j\]表示区间i~j翻转的最大值，那么我们就可以用N^2的区间Dp把这个Dp数组处理出来（详见代码），然后在N^2枚举哪个区间翻转即可

### Code
```cpp
    #include <bits/stdc++.h>
    
    using namespace std;
    
    const int Maxn = 2000 + 10;
    
    int N, A[Maxn];
    int Dp[Maxn][Maxn];
    int Sum1[Maxn], Sum2[Maxn];
    
    int main()
    {
    #ifdef hk_cnyali
        freopen("C.in", "r", stdin);
        freopen("C.out", "w", stdout);
    #endif
        scanf("%d", &N);
        for (int i = 1; i <= N; ++i)
        {
            scanf("%d", &A[i]);
            Sum1[i] = Sum1[i - 1];
            Sum2[i] = Sum2[i - 1];
            if (A[i] == 1) Sum1[i] = Sum1[i - 1] + 1;
            else Sum2[i] = Sum2[i - 1] + 1;
        }
        for (int l = 1; l <= N; ++l)
            for (int i = 1; i + l - 1 <= N; ++i)
            {
                int j = i + l - 1;
                if (A[i] == 1)
                    Dp[i][j] = max(Dp[i + 1][j], Sum1[j] - Sum1[i - 1]);
                else Dp[i][j] = Dp[i + 1][j] + 1;
            }
        int Ans = 0;
        for (int i = 1; i <= N; ++i)
            for (int j = i; j <= N; ++j)
                Ans = max(Ans, Sum1[i - 1] + Sum2[N] - Sum2[j] + Dp[i][j]);
        cout<<Ans<<endl;
        return 0;
    }
   ``` 

### Summary

唉，Dp题还是做少了，这种简单的Dp考场上都没调出来，Dp方面还要加强

D A Determined Cleanup
----------------------

### Solution

自己找规律+看样例乱搞了一下搞出来了一种做法AC了，具体也不知道怎么证明之类的 
大概就是观察了下$(x+m)(k_3x^3 + k_2x^2 + k_1x + k_0)+n$这个式子
展开之后变成了$ax^4+(k_3m+k_2)x^3 + (k_2m+k_1)x^2 + (k_1m + k_0)x + dm + n$ 
然后就使得dm+n>=0且尽量小，cm+d>=0且尽量小。。。这样迭代地去算 
知道找到了一个$k_i$使得$k_i >= 0$且$k_i < m$就跳出循环 
大概就是这样 
然后C++里的ceil不知道为什么数字一大就有问题，于是就手写了一个和ceil功能一样的东西。。。

### Code
```cpp
    #include <bits/stdc++.h>
    #define LL long long
    
    using namespace std;
    
    const int Maxn = 1000000 + 100;
    
    LL N, M;
    LL A[Maxn];
    
    int main()
    {
    #ifdef hk_cnyali
        freopen("D.in", "r", stdin);
        freopen("D.out", "w", stdout);
    #endif
        scanf("%lld%lld", &N, &M);
    
        int Cnt = 0;
        while (1)
        {
            A[++Cnt] = (((LL)(ceil((long double)(-N) / M)) * M + N) % M + M) % M;
            if (N >= 0 && N < M)
                break;
            //N = (LL)ceil(((long double)(-N) / M));
            if (!(N % M))
                N = (-N) / M;
            else if (N > 0)
                N = (-N) / M;
            else N = (-N) / M + 1;
            //cout<<N<<endl;
        }
        cout<<Cnt<<endl;
        for (LL i = 1; i <= Cnt; ++i) cout<<A[i]<<" ";
        cout<<endl;
        return 0;
    }