题目描述#

给定 $n,k$ ，请选择 $1-n$ 的若干个整数，使得这些整数的和的子集都不等于 $k$ ，问最多能选出几个整数且分别是多少。

输入格式#

第一行是一个整数 $t(1≤t≤100)$ ，表示数据组数。

每组数据有两个整数 $n,k(1≤k≤n≤1000)$

输出格式#

对于每组数据

第一行输出一个整数 $m$ ，表示最多能选出的整数数量。

第二行输出这些选出的整数，顺序任意。

思路：#

1. 显然对 $i ∈[1,n]$ ， $i>k$ 时 $i$ 这个数肯定可以直接选

2. $i=k$ 显然不行

3. 考虑 $i<k$ 的情况：我们发现 选 $k-1$ 不选 $1$ ，选 $k-2$ 不选 $2$

如何证明其正确性？

如果选了大于 $k/2$ 的数，一定会有两个加起来等于 $k$ ，所以最多选 $k/2$ 个，那只需要选大的就可以了

代码：#

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1010;
int t, k, n;
int a[N], ans[N];
int cnt;
int main()
{
    ios::sync_with_stdio(0);
    cin >> t;
    while (t--)
    {
        cin >> n >> k;
        cnt = 0;
        memset(a, 0, sizeof(a));
        memset(ans, 0, sizeof(ans)); //初始化
        if (n > k)
        {
            for (int i = k + 1; i <= n; i++)
            {
                ans[++cnt] = i;
            }
        }
        for (int i = k - 1; i >= 1; i--)
        {
            if (!a[i])
            {
                ans[++cnt] = i;
                a[k - i] = 1;
            }
        }
        cout << cnt << endl;
        for (int i = 1; i <= cnt; i++)
        {
            cout << ans[i] << " ";
        }
        cout << endl;
    }
    return 0;
}

题目描述#

某行星上的时间一天有 $h$ 小时，一小时有 $m$ 分钟，它的时钟也是HH:MM的形式存在。

当某个点在镜子中显现的时间也是合法的时候，我们认为这个点是合法的。

给定一个时间点，求最近的合法点（如果它本来就是一个合法的时间点，那么就输出这个时间点）

输入格式#

第一行是一个整数 $t(1≤t≤100)$ ，表示数据组数。

每组数据有两行：

第一行输入$h,m$

第二行输入给定的那个时间点 $hh:mm$

输出格式#

对于每组数据

第一行输出一个整数 $m$ ，表示最多能选出的整数数量。

以 $hh:mm$ 的形式输出最近的合法时间点

思路#

显然，合法的 必要不充分条件 是 数字在屏幕上显示是正确的。即：1 2 5 8 0可以出现，3 4 6 7 9不能出现。

其次，必须满足对应的 分钟 和 小时 在该行星上时间范围内的条件。

那么就很容易判断一个时间是否合法，问题来到如何找到下一个合法的时间？

枚举即可！

注意前导零？——改用字符串来处理即可

代码：#

（比赛的时候写的太冗长了，这是一个需要改进的地方）

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1010;
int t, h, m;
int hh, mm;
char H[2], M[2];
char ansh[2], ansm[2];
int nh, nm;
int no[] = {3, 4, 6, 7, 9};
int solve(int x)
{
    int res = 0;
    char op[2];
    if (x == 1)
        op[0] = H[0], op[1] = H[1];
    else
        op[0] = M[0], op[1] = M[1];
    for (int j = 1; j >= 0; j--)
    {
        int num = op[j] - '0';
        res *= 10;
        if (num == 0)
            res += 0;
        else if (num == 1)
            res += 1;
        else if (num == 2)
            res += 5;
        else if (num == 5)
            res += 2;
        else if (num == 8)
            res += 8;
    }
    return res;
}
int check()
{
    for (int j = 0; j <= 1; j++)
    {
        int x = H[j] - '0';
        for (int i = 0; i < 5; i++)
            if (x == no[i])
                return 0;
    }
    for (int j = 0; j <= 1; j++)
    {
        int x = M[j] - '0';
        for (int i = 0; i < 5; i++)
            if (x == no[i])
                return 0;
    }
    nh = solve(0), nm = solve(1);

    if (nh < h and nm < m)
    {
        //cout<<hh<<" "<<mm<<endl;
        ansh[0] = hh / 10 + '0', ansh[1] = hh % 10 + '0';
        ansm[0] = mm / 10 + '0', ansm[1] = mm % 10 + '0';
        return 1;
    }
    return 0;
}
int main()
{
    cin >> t;
    while (t--)
    {
        cin >> h >> m;
        scanf("%d:%d", &hh, &mm);
        H[0] = hh / 10 + '0', H[1] = hh % 10 + '0';
        M[0] = mm / 10 + '0', M[1] = mm % 10 + '0';
        while (!check())
        {
            mm = (M[0] - '0') * 10 + M[1] - '0';
            hh = (H[0] - '0') * 10 + H[1] - '0';
            mm++;
            if (mm >= m)
            {
                mm = 0, hh++;
            }
            if (hh >= h)
                hh = 0;
            H[0] = hh / 10 + '0', H[1] = hh % 10 + '0';
            M[0] = mm / 10 + '0', M[1] = mm % 10 + '0';
        }
        cout << ansh[0] << ansh[1] << ":" << ansm[0] << ansm[1] << endl;
    }
    return 0;
}

题目描述#

一个字符串是 $k$ 美的定义：字符串中不同字符出现的总次数能整除 $k$

现在给你一个 $n,k$ ,和一个字符串，$n$ 为字符串的长度，让你求一个字符串满足 $k$ 美的定义并且这个字符串的字典序要尽可能的小（前提是大于等于原字符串）

并且长度和原串长度相同，如果答案字符串不存在，输出-1.

输入格式#

第一行是一个整数 $t(1≤t≤10000)$ ，表示数据组数。

每组数据有两行：

第一行输入两个整数 $n,k(1≤k≤n≤10^5)$ ，分别为字符串 $s$ 的长度和给定的数字 $k$

第二行输入只含小写字母的字符串 $s$

输出格式#

对于每一组测试数据，输出第一个字典序大于等于 $s$ 且满足 $k$ 美定义的字符串

思路：#

1. 因为要求的字符串要尽可能的小，还必须大于等于原串，那么我们可能的最优解就是原串本身满足k美，直接输出原串。

2. 如果一个串满足 $k$ 美，那么说明串的长度是由一组 $k$ 的倍数组成的，所以如果 $n$ 不能整除 $k$ ，那么找不到满足 $k$ 美的字符串，所以我们直接输出 $-1$ 。

   注意是 $k$ 的倍数，而不是每个出现次数都是 $k$ ，因此类似 $8=2+4+2=6+2(k=2)$ 这样的数据都是合法的。

3. 如何寻找满足 $k$ 美的最小字符串？我们可以这样 贪心 的想，构造一个最小的大于等于原串的k美字符串，那么我们应该对原串从后往前构造，因为越往前，构造出来的字符串就越大，所以尽可能在最后就构造好，这样满足字典序最小的性质。

4. 我们首先统计每个字符出现的次数，用一个cnt数组存储，然后统计将所有字符都变成k的倍数时所需增加的字符总数tot：即字符 $i$ 变成 $k$ 的倍数时需要增加的字符数为 $(k-cnt[i]\%k)\%k$ ;

5. 从后往前遍历，遍历到位置 $i$ 时，就判断一下从位置i开始之前的子串是否是一个不用修改的最长前缀子串（因为前面的串不改最优）

6. 然后得到位置 $i$ 上的字符 $c$ ，并逐个判断要放哪个字符

代码：#

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int cnt[30];
int n, t, k;
char s[100020];
void solve()
{
    memset(cnt, 0, sizeof(cnt));
    for (int i = 1; i <= n; i++)
    {
        cnt[s[i] - 'a']++; //对原串中出现的字母进行统计
    }
    int tot = 0;
    for (int i = 0; i <= 25; i++)
    {
        tot += (k - cnt[i] % k) % k; //表示将字符i变成 k的倍数 时所需要增加的字母数量
    }
    if (tot == 0)
    {
        for (int i = 1; i <= n; i++)
            cout << s[i];
        cout << endl;
    }
    else if (n % k != 0)
        cout << "-1" << endl;
    else
    {
        int ans = 0;
        for (int i = n; i >= 1 and ans == 0; i--) //从后往前遍历
        {
            tot -= (k - cnt[s[i] - 'a'] % k) % k;
            cnt[s[i] - 'a']--;
            tot += (k - cnt[s[i] - 'a'] % k) % k; //统计i位置之前的tot

            for (int j = s[i] - 'a' + 1; j <= 25; j++) //修改i
            {
                int last = tot;
                tot -= (k - cnt[j] % k) % k;
                cnt[j]++;
                tot += (k - cnt[j] % k) % k;
                if (i + tot <= n) //如果需要增加（修改）的字符数不超过i及其后面这一段的长度，那么就说明我们找到了最长的不用修改的前缀子串
                {
                    for (int x = 1; x < i; x++)
                    {
                        cout << s[x];
                    }
                    cout << char(j + 'a'); //输出i位置的字符
                    //因为i位被改大了，所以到现在，字典序已经变大了，后续的直接放最小的即可
                    for (int x = 1; x <= n - i - tot; x++)
                    {
                        cout << 'a'; //补a，因为i之前的字符经过补位后的修改后一定是k倍，所以剩下的位数一定是k倍，那么直接都补上a即可
                    }
                    for (int x = 0; x <= 25; x++) //从前往后，补充缺少的字符（补位）
                    {
                        int num = (k - cnt[x] % k) % k;
                        while (num > 0)
                        {
                            tot--, num--;
                            cout << char(x + 'a');
                        }
                    }
                    cout << endl;
                    ans = 1;
                    break;
                }

                tot = last;
                cnt[j]--;
            }
        }
    }
}
int main()
{
    cin >> t;
    while (t--)
    {
        cin >> n >> k;
        cin >> (s + 1);
        solve();
    }
    return 0;
}

题目描述#

一个长度为 $n$ 的数组 $a$ 。处理以下格式的 $q$ 个查询：给定整数 $i$ 和 $x$ ，将 $a_i$ 乘以 $x$。

在处理每个查询之后，您需要输出数组 $a$ 的所有元素的最大公约数（GCD）。

因为答案可能太大，所以要求以 $10^9+7$ 的模输出它。

输入格式#

第一行是两个整数 $n,q(1≤n,q≤2⋅10^5)$

第二行包括 $n$ 个整数 $a_1,a_2,\dots,a_n(1≤ai≤2⋅10^5)$

接下来 $q$ 行包括 $q$ 个查询，每行包括两个数字 $i，x (1≤i≤n, 1≤x≤2⋅10^5)$

输出格式#

输出 $q$ 行，每行为现在数组的 GCD 对 $1e9+7$ 的模数。