M - Sum of 2050

题目描述：

A number is called 2050-number if it is 20502050, 2050020500, ..., (2050⋅10k2050⋅10k for integer k≥0k≥0).

Given a number nn, you are asked to represent nn as the sum of some (not necessarily distinct) 2050-numbers. Compute the minimum number of 2050-numbers required for that.

题意：

问一个数最少能用多少个形如$$2050*10^k,k>=0$$的数组成

思路：

先判断n能否除尽2050，如果不能就输出-1，能的话就可以将这个数看成2050进制，问题就类似于10问进制数n最少能用多少个形如$$10^k,k>=0$$的数构成，只需要用n/2050，再将每一位的数加起来即可

（没想到在这里让我碰见原题了？？看来做做CF还是挺好的

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ll t,n, m;
    cin>>t;
    while(t--){
        cin>>n;
        if(n % 2050 != 0){
            cout<<-1<<endl;
            continue;
        }
        else{
            m = n / 2050;
            ll sum = 0;
            while(m){
                sum += m % 10;
                m /= 10;
            }
            cout<<sum<<endl;
        }
    }
    return 0;


}

J - Let's go hiking

题目描述：

Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子

 1  2  3  4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。

思路：

就是简单的记忆化搜索

（又是原题……，不过第一遍的时候判断条件的时候没写好，就T了一发

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;

int n, m;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
bool judge(int x, int y){
    if(x > n ||x < 1 || y > m || y < 1)
    {
        return false;
    }
    else return true;

}


int dp[105][105];
int tr[105][105];
int cal(int x, int y){
    if(dp[x][y] != 1){//这里的条件要注意啊
        return dp[x][y];
    }
    for(int i = 0; i < 4; ++i){
        int xx = x + dx[i];
        int yy = y + dy[i];
        if(!judge(xx, yy))continue;
        if(tr[xx][yy] < tr[x][y]){
            dp[x][y] = max(dp[x][y], cal(xx, yy) + 1);
        }
    }
    return dp[x][y];

}

int main(){
    scanf("%d%d",&n,&m);
    int maxn = -1;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j)
        {
            scanf("%d", &tr[i][j]);
            dp[i][j] = 1;//所有点初始化都为1
        }
    }
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
        {
            maxn = max(maxn, cal(i, j));
        }
    }
    cout<<maxn<<endl;
    return 0;
}

L - Read it first?

题目描述：

You are given an array aa consisting of nn integers. Each aiai is one of the six following numbers: 4,8,15,16,23,424,8,15,16,23,42.

Your task is to remove the minimum number of elements to make this array good.

An array of length kk is called good if kk is divisible by 66 and it is possible to split it into k6k6 subsequences 4,8,15,16,23,424,8,15,16,23,42.

Examples of good arrays:

• [4,8,15,16,23,42][4,8,15,16,23,42] (the whole array is a required sequence);
• [4,8,4,15,16,8,23,15,16,42,23,42][4,8,4,15,16,8,23,15,16,42,23,42] (the first sequence is formed from first, second, fourth, fifth, seventh and tenth elements and the second one is formed from remaining elements);
• [][] (the empty array is good).

Examples of bad arrays:

• [4,8,15,16,42,23][4,8,15,16,42,23] (the order of elements should be exactly 4,8,15,16,23,424,8,15,16,23,42);
• [4,8,15,16,23,42,4][4,8,15,16,23,42,4] (the length of the array is not divisible by 66);
• [4,8,15,16,23,42,4,8,15,16,23,23][4,8,15,16,23,42,4,8,15,16,23,23] (the first sequence can be formed from first six elements but the remaining array cannot form the required sequence).

题意：

给你n个必为{4,8,15,16,23,42}的数，问你需要删去多少个才能分出若干个完全等于[4,8,15,16,23,42]的不同组

思路：

先从头跑一遍，先删除顺序不合的数，什么样的数是顺序不合的呢？就是再此之前，比他小的数出现的次数如果小于等于它出现的次数，此时该数不可选，要删掉

跑循环的时候记录下每个数出现的次数（删掉的不算），然后找到最小的数，其他的数比这个最小值多出来也是得删掉的

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;

int n, m;
int tr[100];
int k[] = {4,8,15,16,23,42};

int main(){
    int sum = 0;
    scanf("%d",&n);
    for(int i = 1; i <= n; ++i){
        scanf("%d", &m);//输入的数为m
        for(int j = 0; j < 6; ++j)
        {
            if(m <= k[j]){//如果数大于等于m，就说明前面都符合，更新一下m的次数，然后跳出即可
                ++tr[m];
                break;
            }
            else//出现不合的情况，让sum++，跳出循环
            {
                if(tr[k[j]] <= tr[m])
                {
                    ++sum;
                    break;
                }
            }
        }

    }
    int minx = 1e9;
    for(int i = 0; i < 6; ++i){
        minx = min(minx, tr[k[i]]);
    }
    for(int i = 0; i < 6; ++i)
    {
        sum += tr[k[i]] - minx;
    }
    cout<<sum<<endl;
    return 0;
}

C - Play with bombs

题目描述：

The terrorists have planted some bombs in a building! Our hero, Little Horse, decides to rescue the people in the building. Unfortunately, there is more than one bomb, and Little Horse is unable to defuse all of them. To strive for more time for other people to escape, Little Horse decides to sacrifice himself.

There are nn bombs in the building, each of which has a countdown clock. In the beginning, the ii-th bomb's clock is set to aiai. Then:

1. Little Horse chooses one bomb, making its clock increase by 11.
2. Every bomb's clock decreases by 11.
3. If at least one clock becomes lower than 00, all the bombs will explode. Otherwise, go back to step 1.

Obviously, the explosion is not avoidable. What a sad story. But Little Horse doesn't care about his survival now. He just wants to strive for more time. So can you tell him how many times he can do step 1 at most before the explosion?

题意：

给出一个数组，每回合对数组进行三次操作：

1. 选一个数让其值加一
2. 数组内全体数减一
3. 如果数组内出现数值小于0的就结束

问你最多能进行几次操作1

思路：

二分！

因为我们不知道具体什么时候爆炸，所以可以用二分去枚举爆炸的时间，二分到最后，这就是我们要的。

众所周知，二分答案最重要的是check函数怎么写，本题判断的是每个数与爆炸时间的关系，具体是：对于数tr[i] ，如果他大于我们假定的爆炸时间x，就不要管他，因为我们不对他进行操作1，他也不会炸，而对于tr[1] < x的，我们就需要对其进行x - tr[i] 次操作1，我们就用sum记录差值之和，最后和我们的爆炸时间去比较，如果sum < x,说明我们假定的爆炸时间还是太长了，要往左缩一缩，反之，就往右缩缩

总的来说，我们的check函数其实是判断当前枚举的爆炸时间是不是恰好等于此时需要进行操作一的数量，如果爆炸时间短了，就让他变长点，如果长了就让他变短点

还有一点要注意的是，是第一个-1出现的时候结束，而我们这个check本质上是将能变成0的都变成了0，所以要让ans++，但是比较巧妙的是，每次check判断成功会让l = mid + 1，本来我们需要的是最后一次chekc成功时的mid，输出mid + 1，而此时这个 l 恰好就是mid+1，所以我们只需要输出 l 即可

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 100000 + 50
#define endl '\n'
#define seed 13331
#define mod 1000000007
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
//不开longlong见祖宗！
//inline __int128 read(){__int128 x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-'){f = -1;}ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
//inline void print(__int128 x){if(x < 0){putchar('-');x = -x;}if(x > 9){print(x / 10);}putchar(x % 10 + '0');}
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
inline void write(int x){if (x < 0) {x = ~x + 1; putchar('-');}if (x > 9){write(x / 10);}putchar(x % 10 + '0');}

int Case, n, t;
int tr[MAX];

bool check(ll x){
    ll sum = 0;
    for(int i = 1; i <= n; ++i){
        if(x >= tr[i])sum += (x - tr[i]);
    }
    if(sum <= x)return true;
    return false;
}

int main(){
    io;
    cin>>t;
    while (t--) {
        cin>>n;
        for(int i = 1; i <= n; ++i){
            cin>>tr[i];
        }
        ll l = 0, r = 2 * 1ll * inf;
        while (l <= r) {
            ll mid = (l + r) / 2;
            if(check(mid))l = mid + 1;
            else r = mid - 1;
        }
        printf("Case #%d: %lld\n",++Case,l);
    }
    return 0;
}

G - Color the fence

题目描述：

You are a rebel leader and you are planning to start a revolution in your country. But the evil Government found out about your plans and set your punishment in the form of correctional labor.

You must paint a fence which consists of 1010010100 planks in two colors in the following way (suppose planks are numbered from left to right from 00):

• if the index of the plank is divisible by rr (such planks have indices 00, rr, 2r2r and so on) then you must paint it red;
• if the index of the plank is divisible by bb (such planks have indices 00, bb, 2b2b and so on) then you must paint it blue;
• if the index is divisible both by rr and bb you can choose the color to paint the plank;
• otherwise, you don't need to paint the plank at all (and it is forbidden to spent paint on it).

Furthermore, the Government added one additional restriction to make your punishment worse. Let's list all painted planks of the fence in ascending order: if there are kk consecutive planks with the same color in this list, then the Government will state that you failed the labor and execute you immediately. If you don't paint the fence according to the four aforementioned conditions, you will also be executed.

The question is: will you be able to accomplish the labor (the time is not important) or the execution is unavoidable and you need to escape at all costs.

题意：

刷围栏。刷到第i个时，当i能被r整除时（0，r，2r），必须把围栏刷成红色。
当i能被b整除时（0，b，2b），必须把围栏刷成蓝色。
当i既能被r又能被b整除时，既可以刷成红色又可以刷成蓝色。
否则，不用涂色。
当涂相同颜色的围栏大于等于k个时，就失败了。当涂色操作不符合上面四个要求时，也会失败。
问：给你r，b，k三个数，问操作能否成功。

思路：

假设 r 小于 b

最多个相同颜色的肯定出现在 [y * b, (y + 1) * b]这里面，想让相同颜色尽可能多，就得让其使劲靠前，所以我们设在[y * b, (y + 1) * b]的区间内第一个能除尽 r 的数是该区间内的第 k + 1个数

则可以得到等式：y * b + k = x * r

移向得到：y * b - x * r = -k

根据裴蜀定理：

ax + by = t

其中 t 是gcd(a, b) 的倍数

所以最小的 k 为gcd(r, b)

在[y * b, (y + 1) * b] 里面有 b + 1个数，对于y * b,和 (y+1) * b，他们能除的尽b，也有可能除得尽 r， 但我们要让红色最多的情况下尽可能减少红色，所以对这俩个直接涂蓝，剩下的就只有 b - 1个数，再抛去前面gcd(r, b)个数，剩下的长度除以r 再加1得到的就是 红色最多的个数

即：

(b-1-gcd(r,b))/r+1

判断这个数与k的大小即可

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 100000 + 50
#define endl '\n'
#define seed 13331
#define mod 1000000007
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
//不开longlong见祖宗！
//inline __int128 read(){__int128 x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-'){f = -1;}ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
//inline void print(__int128 x){if(x < 0){putchar('-');x = -x;}if(x > 9){print(x / 10);}putchar(x % 10 + '0');}
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
inline void write(int x){if (x < 0) {x = ~x + 1; putchar('-');}if (x > 9){write(x / 10);}putchar(x % 10 + '0');}

ll t, r, b, k;

ll gcd(ll x, ll y){
    return y ? gcd(y, x % y) : x;
}

int main(){
    cin>>t;
    while (t--) {
        cin>>r>>b>>k;
        if(r > b)swap(r, b);
        ll x = gcd(r, b);
        if((b - 1 - x) / r + 1 >= k)cout<<"REBEL\n";
        else cout<<"OBEY\n";
    }
    return 0;
}

K - Play with sequences

题目描述：

Squirrel Liss is interested in sequences. She also has preferences of integers. She thinks n integers a1, a2, ..., a**n are good.

Now she is interested in good sequences. A sequence x1, x2, ..., x**k is called good if it satisfies the following three conditions:

• The sequence is strictly increasing, i.e. x**i < x**i + 1 for each i (1 ≤ i ≤ k - 1).
• No two adjacent elements are coprime, i.e. gcd(x**i, x**i + 1) > 1 for each i (1 ≤ i ≤ k - 1) (where gcd(p, q) denotes the greatest common divisor of the integers p and q).
• All elements of the sequence are good integers.

Find the length of the longest good sequence.

题意：

给你一个上升的序列，选出k个数，使其递增，同时使得每个数与其相邻的两个数的gcd > 1，问你最多选多少个

思路：

是一个很奇妙的dp

先进行预处理：用vector数组存2到1e5所有数的所有因子

dp[i] 表示到目前为止，以 i 为因子的最长序列的长度

然后对数组去跑循环，对每个数，让其每个因子的dp值加一，同时用maxn维护出来其中dp的最大值，等扫完了以后，就再扫一遍，这一遍，我们让该数的所有因子的dp值都等于maxn

最后从2到1e5扫一遍dp数组，找出最大值即可

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f3f3f3f3f
#define MAX 100000 + 50
#define endl '\n'
#define seed 13331
#define mod 1000000007
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
//不开longlong见祖宗！
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
inline void write(int x){if (x < 0) {x = ~x + 1; putchar('-');}if (x > 9){write(x / 10);}putchar(x % 10 + '0');}

vector<int>v[MAX];
int dp[MAX];
int n, maxn;
int tr[MAX];

void init(){//预处理
    for(int i = 0; i < MAX; ++i)v[i].clear();
    for(int i = 2; i < MAX; ++i){
        for(int j = i; j < MAX; j += i){
            v[j].push_back(i);
        }
    }
}

int main(){
    io;
    cin>>n;
    init();
    for(int i = 1; i <= n; ++i){
        cin>>tr[i];
    }
    for(int i = 1; i <= n; ++i){
        maxn = 0;
        for(int j = 0; j < v[tr[i]].size(); ++j){
            int u = v[tr[i]][j];
            ++dp[u];
            maxn = max(dp[u], maxn);//找最大值
        }
        for(int j = 0; j < v[tr[i]].size(); ++j){
            int u = v[tr[i]][j];
            dp[u] = maxn;//更新所有因子的dp
        }
    }
    maxn = 1;
    for(int i = 1; i < MAX; ++i)maxn = max(maxn, dp[i]);
    cout<<maxn<<endl;
    return 0;
}

D - An interesting game

题目描述：

On a weekend, Qingshan suggests that she and her friend Daniel go hiking. Unfortunately, they are busy high school students, so they can only go hiking on scratch paper.

A permutation pp is written from left to right on the paper. First Qingshan chooses an integer index xx (1≤x≤n1≤x≤n) and tells it to Daniel. After that, Daniel chooses another integer index yy (1≤y≤n1≤y≤n, y≠xy≠x).

The game progresses turn by turn and as usual, Qingshan moves first. The rules follow:

• If it is Qingshan's turn, Qingshan must change xx to such an index x′x′ that 1≤x′≤n1≤x′≤n, |x′−x|=1|x′−x|=1, x′≠yx′≠y, and px′<pxpx′<px at the same time.
• If it is Daniel's turn, Daniel must change yy to such an index y′y′ that 1≤y′≤n1≤y′≤n, |y′−y|=1|y′−y|=1, y′≠xy′≠x, and py′>pypy′>py at the same time.

The person who can't make her or his move loses, and the other wins. You, as Qingshan's fan, are asked to calculate the number of possible xx to make Qingshan win in the case both players play optimally.

题意：

一个排列，A,B两个人，A先手走到一个点，且下次只能走到相邻且值比当前点小的点，同时不能与B相遇。B下次只能走到相邻且值比当前点大的点，同时不能与A相遇。问多少个起点使得A必胜。

思路：

总的来说：仅存在一个点，其往左和往右都是单调递减的，且左右单调序列的长度相同（设为m）并且都为整个排列中最长的单调序列（增或减），当m为偶数时输出1，其他情况输出0

• 最长单调序列只有一个时，无论a下在这个序列的哪里，都会被b视情况而定来下其左或右地无情卡死（仔细想想
• 最长单调序列出现三个及以上时，无论a下在哪里，b都可以从一个完好的谷底往一个a碰不到的山顶走去，由于a是先手，所以a必死
• 当最长单调序列出现俩个时，长度为m，若m为奇数，你手动模拟一下，就会发现a因为其先手而必死，若m为偶数，则会赢
• 还有可能山峰的左右子峰不相同时，假设子峰的长度为x 、y，且x < y，若x为偶数，则b只要走到y峰x+1的位置，就能卡死a；若xwei奇数，则b只要走到y峰x的位置，就能卡死a

代码就不贴了，写不出来(╥﹏╥)

A - Prefix Flip (Easy Version)

题目描述：

This is the easy version of the problem. The difference between the versions is the constraint on nn and the required number of operations. You can make hacks only if all versions of the problem are solved.

There are two binary strings aa and bb of length nn (a binary string is a string consisting of symbols 0 and 1). In an operation, you select a prefix of aa, and simultaneously invert the bits in the prefix (0 changes to 1 and 1 changes to 0) and reverse the order of the bits in the prefix.

For example, if a=001011 and you select the prefix of length 3, it becomes 011011. Then if you select the entire string, it becomes 001001.

Your task is to transform the string aa into bb in at most 3n operations. It can be proved that it is always possible.

题意：

给出两个二进制串a,b，可以对他们进行一种操作：对串的前 i 个元素取反，并将[1, i]的串反转一下，你需要通过操作将a变成b，输出每次操作选择的 i

思路：

将第 i 个字符取反需要三次操作，三次分别是 i，1，i

进行第一个 i，就将第 i 个字符取反并拿到了第一位

1，就将原来的第 i 个字符再次取反

第二个 i ，又将原来的第 i 个字符取反，并变回了原来的顺序

位置 i 的字符取反了三次，就相当于取反了1次

其他的位置的字符取反了两次，就相当于不变

所以只需要比较a 和 b哪个不一样，然后 i 1 i 即可

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f3f3f3f3f
#define MAX 100000 + 50
#define endl '\n'
#define seed 13331
#define mod 1000000007
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
//不开longlong见祖宗！
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
inline void write(int x){if (x < 0) {x = ~x + 1; putchar('-');}if (x > 9){write(x / 10);}putchar(x % 10 + '0');}


int t, n;
string a, b;
vector<int>tr;

int main(){
    t = IntRead();
    while (t--) {
        int sum = 0;
        tr.clear();
        n = IntRead();
        cin>>a>>b;
        for(int i = 0; i < a.size(); ++i){
            if(a[i] == b[i])continue;
            else{
                sum += 3;
                tr.push_back(i + 1);
                tr.push_back(1);
                tr.push_back(i + 1);
            }
        }
        cout<<sum;
        for(int i = 0; i < tr.size(); ++i)cout<<' '<<tr[i];
        cout<<endl;
    }
    return 0;
}