题目1

题目链接
题目大意：
有n个球，序号分别是1、2、3、、、、n，每个球上面有一个数字a[1]、a[2]、a[3]、、、a[n]，这组数字是不递减的，即是 a[i]≤a[i+1]， 1≤i<𝑛；
现在需要给n个球染色，需要满足：
1、每个球只有一个颜色；
2、将某个颜色的球挑选出来，按照序号从小到大放好，上面的数字是严格递增；

问，最少需要几个颜色。

输入：
第一行是𝑡，表示样例数 (1≤𝑡≤100)
每个样例两行，第一行是整数𝑛 (1≤𝑛≤100)
第二行是n个整数 𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤𝑛)

输出：
每个样例一行，输出最少需要的颜色数量。

Examples
input
5
6
1 1 1 2 3 4
5
1 1 2 2 3
4
2 2 2 2
3
1 2 3
1
1

output
3
2
4
1
1

题目解析：
由于本身数字就是不递减，要满足严格递增，只需要关注数字相同的部分；
相同数字的最大连续长度，就是需要的颜色数量。

int a[N];

int main(int argc, const char * argv[]) {
    // insert code here...
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int ans = 1, cur = 1;
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            if (i > 0) {
                if (a[i] == a[i - 1]) {
                    ++cur;
                    ans = max(ans, cur);
                }
                else {
                    cur = 1;
                }
            }
        }
        cout << ans << endl;
    }   
    
    return 0;
}

题目2

题目链接
题目大意：
小明喜欢0到9中的一个数字d，如果某个整数的十进制表示中，数字d只出现一次则称这个整数是lucky数；
比如说d=7的时候，17就是lucky数，77就不是lucky数；
现在给出q个整数，问给出的整数是否都能拆分为若干个lucky数之和；

输入：
第一行是样例数𝑡 (1≤𝑡≤9)
每个样例两行，第一行𝑞 and 𝑑 (1≤𝑞≤1e4, 1≤𝑑≤9).
第二行是𝑞个整数 𝑎1,𝑎2,…,𝑎𝑞 (1≤𝑎𝑖≤1e9).
输出：
每个样例有q行，每一行对应a[i]是否可以拆分为若干个lucky数之和；

Examples
input
2
3 7
24 25 27
10 7
51 52 53 54 55 56 57 58 59 60

output
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO

题目解析：
以7为例，如果数字大于77，那么必然有解：可以拆分为7x+若干个7的组合；
比如说77=70+7，100=7+7+7+7+72；

那么小于100的数字可以枚举，更大的数字必然有解。

int a[100][10]; // a[i][j]表示数字为i，幸运数字是j，是否有解

int main(int argc, const char * argv[]) {
    // insert code here...

    for (int i = 1; i < 100; ++i) {
        for (int lucky = 1; lucky <= 9; ++lucky) {
            bool ok = 0;
            int tmp = i;
            while (tmp) {
                if (tmp % 10 == lucky) {
                    ok = 1;
                    break;
                }
                tmp /= 10;
            }
            a[i][lucky] = ok;
            for (int k = 1; k <= i; ++k) {
                if (a[k][lucky] && k + lucky < 100) {
                    a[k+lucky][lucky] = 1;
                }
            }
        }
    }
    
    int t;
    cin >> t;
    while (t--) {
        int q, d;
        cin >> q >> d;
        while (q--) {
            int k;
            cin >> k;
            if (k >= 100) {
                cout << "YES" << endl;
            }
            else {
                cout << (a[k][d] ? "YES" : "NO") << endl;
            }
        }
    }   
    
    return 0;
}

题目3

题目链接
题目大意：
n个数字的数组a，可以执行最多k次操作，每次操作是找两个数字，其中一个+1，另外一个-1；
想知道经过最多k次操作之后，数组最小的字典序是什么；

输入：
第一行是样例数𝑡 (1≤𝑡≤20)
每个样例两行，第一行是整数𝑛 and 𝑘 (2≤𝑛≤100, 1≤𝑘≤10000)
第二行是n个整数 𝑎1 , 𝑎2, …, 𝑎𝑛 (0≤𝑎𝑖≤100)
输出：
每个样例一行，要求所有数字非负，且 字典序最小；

Examples
input
2
3 1
3 1 4
2 10
1 0

output
2 1 5
0 1

题目解析：
容易知道，要让字典序最小，那么就是让前面的数字尽可能小；
所以从左到右开始选择数字，让前面的数字优先-1，收益最大；
同理，当我们需要+1的时候，为了字典序最小，全部加到最末尾的整数即可；

class Solution {
    static const int N = 100010;
public:
    int n, m;
    int a[N], b[N], c[N], ans[N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            cin >> n >> m;
            for (int i = 0; i < n; ++i) {
                cin >> a[i];
            }
            for (int i = 0; i < n - 1; ++i) {
                if (m >= a[i]) {
                    a[n - 1] += a[i];
                    m -= a[i];
                    a[i] = 0;
                }
                else {
                    a[n - 1] += m;
                    a[i] -= m;
                    m = 0;
                }
            }
            for (int i = 0; i < n; ++i) {
                cout << a[i] << " ";
            }
            cout << endl;
        }
    }
}
ac;

题目4

题目链接
题目大意：
有n个整数的数组a，现在将数组分成两个集合，如果两个集合内的整数之和相等，则是不美好的；
现在希望去掉若干个数字，要求n个数字无法拆成两个集合，这两个集合的和是相等的。

输入：
第一行是整数𝑛 (2≤𝑛≤100)
第二行是n个整数𝑎1 , 𝑎2, …, 𝑎𝑛 (1≤𝑎𝑖≤2000)
输出：
第一行是需要移除的整数个数m，第二行是m个需要移除整数的下标；

Examples
input
4
6 3 9 12
output
1
2

题目解析：
假设n个数字分成集合a[x]和b[y]，并且sum(a) = sum(b)，那么sum(a)=sum(n)/2。
最开始的想法是，如果sum(a)=sum(b)，那么只要去掉一个集合a或者b中的奇数，那么必然会出现sum(a)!=sum(b)； （因为奇数和偶数必定不相同）
问题就变成题目中是否存在一个解，使得sum(a)==sum(b) ：
如果有存在，则去掉n个数字中的奇数；
如果不存在，则不需要去掉任何数字；

注意，这里很容易产生误解：觉得去掉最小/最大的整数也是可行的。
例子： 4 4 6 6 8 8
去掉4之后可以拆分为 4 + 6 + 6 = 8 + 8
去掉8之后可以拆分为 4 + 4 + 6 = 6 + 8
直接找一个数字最小、最大都无法直接确定。

我们回到最初判断，我们会首先认为，如果sum(n)是奇数，则无解；
那么假如数组中存在一个奇数，我们只要去掉这个奇数即可。
那如果数组中一个奇数都没有呢？
假如数组都是偶数，假设最终分出来的两个集合a和b，我们对两边的集合除以2，不影响sum(a)=sum(b)；
如果还是没有奇数，我们可以继续这样操作。容易知道，这样是一定可以找到一个奇数。
根据上面的思路，我们把每一个数字看成二进制，最右边1出现之后，就是奇数了。那么即是寻找n个数字中，最右边1最早出现的位置。

如果要判断n个数字中，能不能凑出来sum(n)/2的数字，这个不就是背包嘛。

class Solution {
    static const int N = 101, M = 101*2000;
public:
    int n, m;
    int a[N], dp[M], ans[N];
    
    int bitpos(int n) {
        int pos = 0;
        while (n % 2 == 0) {
            n /= 2;
            pos++;
        }
        return pos;
    }
    
public:
    void solve() {
        cin >> n;
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            sum += a[i];
        }
        
        bool ok = 1;
        if (sum % 2) {
            ok = 0;
        }
        else {
            sum /= 2;
            dp[0] = 1;
            
            for (int i = 0; i < n; ++i) {
                for (int j = sum; j > 0; --j) {
                    if (j >= a[i]) {
                        dp[j] |= dp[j-a[i]];
                    }
                }
            }
            ok = dp[sum];
        }
                
        if (ok) {
            int minIndex = 0, minPos = bitpos(a[0]);
            for (int i = 1; i < n; ++i) {
                if (bitpos(a[i]) < minPos) {
                    minPos = bitpos(a[i]);
                    minIndex = i;
                }
            }
            cout << 1 << " " << minIndex + 1 << endl;
        }
        else {
            cout << 0 << endl;
        }
    }
    
}

题目5

题目链接
题目大意：
有n * k个整数分别为 1、2、3、4、、、n * k，现在需要将这些整数分成n行，并且对于每一行都满足：
任意选择区间[l, r]，区间的平均数是整数；
问，是否存在这样的分配方式；

输入：
第一行，整数𝑡 表示t个样例 (1≤𝑡≤500)
每个样例一行，整数𝑛 and 𝑘 (1≤𝑛,𝑘≤500)

输出：
每个样例，如果无解则输出NO；
如果有解则输出YES，接下来n行分别输出k个数字；

Examples
input
4
1 1
2 2
3 3
3 1

output
YES
1
YES
1 3
2 4
NO
YES
1
2
3

题目解析：
按照题目的要求，对于n行数字，每行数字的任意区间的平均数都是整数；
当区间长度为2时，（a[i][j] + a[i][j+1]）/ 2能够整除，那么必须是两个奇数或者两个偶数；
由此我们知道，当k>1的时候，肯定每一行数字都是奇数，或者都是偶数；（n=1或者k=1结果较为简单，这里不做讨论）

那么可以推断出， 如果nk是奇数，那么最终肯定会出现奇数个数字，无法满足要求；
当nk是偶数时，如果n是奇数，则k是偶数，那么在平均分配奇偶数的时候，必然会在第(n+1)/2行出现奇偶数混杂的情况，无法满足要求；
如果n是偶数，那么就可以按照1、3、5、7、、这样分配所有奇数，2、4、6、8这样分配所有偶数；
任意区间的平均数，都是中间两个数的平均值；

class Solution {
    static const int N = 201010;
    char str[N];
    int dp[N];

public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n, k;
            cin >> n >> k;
            if (k == 1) {
                cout << "YES" << endl;
                for (int i = 0; i < n; ++i) {
                    cout << i + 1 << endl;
                }
            }
            else if (n % 2) {
                cout << "NO" << endl;
            }
            else {
                cout << "YES" << endl;
                for (int i = 0; i < n / 2; ++i) {
                    int tmp = i * k * 2 + 1;
                    for (int j = 0; j < k; ++j) {
                        cout << tmp + j * 2 << " ";
                    }
                    cout << endl;
                    for (int j = 0; j < k; ++j) {
                        cout << tmp + 1 + j * 2 << " ";
                    }
                    cout << endl;
                }
            }
        }
    }
}