Codeforces Round 705 (Div. 2)

似乎不是很难，但似乎又很难。

A

Description

有两个数 $n,k$，在 $1\sim n$ 中选择最多的数使得不存在两个和为 $k$ 的数。

Solution

显然比 $k$ 大的数全都要选，显然 $k$ 不能选，显然比 $k$ 小的数只能选一半。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using std::cin;
using std::endl;
using std::cout;

int T, n, k;

int main()
{
    cin >> T;
    while (T--)
    {
        cin >> n >> k;
        int ans = n - k + k / 2;
        if (ans <= 0)
        {
            cout << 0 << endl;
            continue;
        }
        cout << n - k + k / 2 << endl;
        for (int i = n; i > k; i--)
            cout << i << " ";
        for (int i = k - 1; i >= (k - 1) / 2 + 1; i--)
            cout << i << " ";
        cout << endl;
    }
}

B

Description

有一个每天有 $h$ 个小时，每个小时有 $m$ 分钟的星球，给出一个时间，求下一个能在镜子中照出合法时间的时间。

Solution

只有 $0,1,2,5,8$ 组成的时间是合法的，预处理一下然后模拟。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using std::cout;
using std::cin;
using std::endl;

const int maxn = 10010;
const int number[] = {0, 1, 2, 5, 8};

bool ok[maxn];
int n, m, x[10];

inline int hash(int a, int b, int c, int d) { return a * 1000 + b * 100 + c * 10 + d; }

void init()
{
    for (int a = 0; a < 5; a++)
        for (int b = 0; b < 5; b++)
            for (int c = 0; c < 5; c++)
                for (int d = 0; d < 5; d++)
                    ok[hash(number[a], number[b], number[c], number[d])] = 1;
    x[0] = 0, x[1] = 1, x[2] = 5, x[5] = 2, x[8] = 8;
}

inline int hash2(int a, int b) { return a * 100 + b; }

inline bool check(int a, int b)
{
    if (!ok[hash2(a, b)])
        return false;
    int p = x[a % 10] * 10 + x[a / 10], q = x[b % 10] * 10 + x[b / 10];
    return p < m && q < n;
}

void work(int a, int b)
{
    while (1)
    {
        if (check(a, b))
        {
            printf("%02d:%02d\n", a, b);
            return;
        }
        b++;
        if (b == m)
            b = 0, a++;
        if (a == n)
            a = 0;
    }
}

int main()
{
    int T;
    cin >> T;
    init();
    char ch;
    while (T--)
    {
        cin >> n >> m;
        int a, b;
        cin >> a >> ch >> b;
        work(a, b);
    }
}

C

Description

有一个长度为 $n$ 只含小写字母的字符串和一个数 $k$。求一个字符串，满足这个字符串字典序比原字符串大且每个字符出现的次数都能被 $k$ 整除，要求满足以上要求的字典序最小的字符串。$n\leq1000$。

Solution

发现和原字符串前缀相同的位数越多字典序就可能越小，于是从大到小枚举从哪一位开始不一样，然后枚举这一位填什么字符，看剩下的位置能不能满足要求。

具体判断能不能满足要求需要看把所有字符都填到恰好被 $k$ 整除需要几个，然后看这些的和是否不大于剩下的位数。

填的时候先把能随便填的都填上 a，剩下的地方从 a 到 z 依次填就行。

建议想好再写。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using std::cout;
using std::cin;
using std::endl;

const int maxn = 1e5 + 10;

char s[maxn];

int T, n, k;
int b[30];

void output(int x, int y)
{
    s[x] = y + 'a';
    for (int i = 1; i <= x; i++)
        cout << s[i];
    int res = n - x;
    for (int i = 0; i < 26; i++)
        res -= (k - b[i] % k) % k;
    for (int i = 0; i < res; i++)
        cout << 'a';
    for (int i = 0; i < 26; i++)
    {
        b[i] %= k;
        for (int j = 0; j < (k - b[i] % k) % k; j++)
            cout << char(i + 'a');
    }
    cout << endl;
}

void solve()
{
    int sum = 0;
    for (int i = n; i >= 1; i--)
    {
        b[s[i] - 'a']--;
        for (int j = s[i] + 1 - 'a'; j < 26; j++)
        {
            b[j]++;
            sum = 0;
            for (int p = 0; p < 26; p++)
                sum += (k - b[p] % k) % k;
            if (sum <= n - i)
            {
                output(i, j);
                return;
            }
            b[j]--;
        }
    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin >> T;
    while (T--)
    {
        memset(b, 0, sizeof(b));
        cin >> n >> k >> (s + 1);
        for (int i = 1; i <= n; i++)
            b[s[i] - 'a']++;
        int ok = 1;
        for (int i = 0; i < 26; i++)
            if (b[i] % k)
            {
                ok = 0;
                break;
            }
        if (ok)
        {
            cout << (s + 1) << endl;
            continue;
        }
        else if (n % k)
        {
            cout << -1 << endl;
            continue;
        }
        solve();
    }
}

D

Description

有一个 $n$ 个数的正整数序列，$q$ 次操作，每次把一个数乘上 $x$，问每次操作后整个序列的 gcd 对 $10^9+7$ 取模的结果。

Solution

我们只需要求出所有质因子最低次数的幂即可。

对每个质因子维护一个 multiset，乘的时候把这个数增加的质因子加进去就行。

然后把答案乘一个 $p^x$ 即可，其中 $x$ 是增加的幂次。

乱维护即可。。。

注意质因数分解需要做到 $O(\log n)$，为此需要预处理每个数最小质因子。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>
#include <map>
using std::cin;
using std::cout;
using std::endl;
using std::cerr;

const int maxn = 2e5 + 10, mod = 1e9 + 7;
const int maxp = 18000;
typedef long long ll;

namespace IO
{
    const int mxsiz = 1 << 20;
    char inbuf[mxsiz], *p1, *p2;
    char outbuf[mxsiz], *op = outbuf;
    struct endio
    {
        endio(){};
        ~endio() { fwrite(outbuf, 1, op - outbuf, stdout); }
    } useless_var;
    inline char gc() { return p1 == p2 && (p2 = (p1 = inbuf) + fread(inbuf, 1, mxsiz, stdin), p1 == p2) ? EOF : *p1++; }
#define isdigit(x) (x >= '0' && x <= '9')
    inline int read()
    {
        int x = 0, f = 1;
        char ch = gc();
        for (; !isdigit(ch); ch = gc())
            if (ch == '-')
                f = -1;
        for (; isdigit(ch); ch = gc())
            x = x * 10 + ch - '0';
        return x * f;
    }
    template <typename T>
    inline void read(T &x)
    {
        x = 0;
        int f = 1;
        char ch = gc();
        for (; !isdigit(ch); ch = gc())
            if (ch == '-')
                f = -1;
        for (; isdigit(ch); ch = gc())
            x = x * 10 + ch - '0';
        x *= f;
    }
#undef isdigit
    inline bool ischar(char x)
    {
        return x >= 'A' && x <= 'z';
    }
    inline char readchar()
    {
        char ch = gc();
        while (!ischar(ch))
            ch = gc();
        return ch;
    }
    inline void push(char ch)
    {
        if (op - outbuf == mxsiz)
            fwrite(outbuf, 1, mxsiz, stdout), op = outbuf;
        *op++ = ch;
    }
    template <typename T>
    inline void work_wt(T x)
    {
        if (x > 9)
            work_wt(x / 10);
        push(x % 10 + '0');
    }
    template <typename T>
    inline void write(T x)
    {
        if (x < 0)
            x = -x, push('-');
        work_wt(x);
    }
    inline void writestr(char *s)
    {
        int n = strlen(s);
        for (int i = 0; i < n; i++)
            push(s[i]);
    }
    inline void endln() { push('\n'); }
    inline void space() { push(' '); }
    template <typename T>
    inline void writeln(T x) { write(x), endln(); }
}
using namespace IO;

int vis[maxn], p[maxp], tot, n, mi[maxn], q;
std::multiset<int> S[maxp];
std::map<int, int> mp[maxn], P;
ll ans = 1;

void init(int n)
{
    mi[1] = 2;
    for (int i = 2; i <= n; i++)
    {
        if (!vis[i])
            p[++tot] = i, P[i] = tot, mi[i] = i;
        for (int j = 1; j <= tot && p[j] * i <= n; j++)
        {
            vis[i * p[j]] = 1, mi[i * p[j]] = p[j];
            if (i % p[j] == 0)
                break;
        }
    }
}

ll qpow(ll a, int x)
{
    ll res = 1;
    for (; x; x >>= 1, a = a * a % mod)
        if (x & 1)
            res = res * a % mod;
    return res;
}

void modify(int x, int pos)
{
    if (x == 1)
        return;
    while (x > 1)
    {
        int i;
        i = P[mi[x]];
        int cnt = 0;
        while (x % p[i] == 0)
            x /= p[i], cnt++;
        if (cnt == 0)
            continue;        
        auto lst = *S[i].begin();
        int flag = S[i].size() == n - 1;
        if (mp[pos][i] != 0)
            S[i].erase(S[i].find(mp[pos][i])), S[i].insert(cnt + mp[pos][i]);
        else
            S[i].insert(cnt);
        mp[pos][i] += cnt;
        if (S[i].size() < n)
            continue;
        else
            ans = ans * qpow(p[i], flag ? *S[i].begin() : *S[i].begin() - lst) % mod;
    }
}

signed main()
{
    init(2e5);
    n = read(), q = read();
    int x;
    for (int i = 1; i <= n; i++)
    {
        x = read();
        modify(x, i);
    }
    while (q--)
    {
        int x, i;
        i = read(), x = read();
        modify(x, i);
        writeln(ans);
    }
}

E

Description

给定两个位数为 $n$ 的二进制数 $a,b$。$g(x,y)$ 为 $[x,y]$ 所有数异或起来的结果，$f(l,r)$ 为所有满足 $l\leq x\leq y\leq r$ 中 $g(x,y)$ 的最大值，求 $f(a,b)$。$n\leq10^6$。

Solution

不会？打表！

发现当 $a,b$ 位数不同时，答案是 $2^n-1$。

否则当 $a=b$ 或 $b=a+1$ 或 $b$ 是奇数时，答案是 $b$。

否则答案是 $b+1$。

证明？不会！

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
using std::cin;
using std::endl;
using std::cout;
using std::cerr;

std::string a, b;

std::string add(std::string x)
{
    int n = x.size();
    std::string res = x;
    int pos = n - 1;
    for (; pos >= 0; pos--)
        if (res[pos] == '1')
        {
            res[pos] = '0';
        }
        else
            break;
    res[pos] = '1';
    return res;
}

int main()
{
    int n;
    cin >> n >> a >> b;
    if (a[0] != b[0])
    {
        for (int i = 0; i < n; i++)
            cout << 1;
        cout << endl;
        return 0;
    }
    if (a == b || add(a) == b || b.back() == '1')
        cout << b << endl;
    else
        cout << add(b) << endl;
}

F

Description

这是一道交互题。

有一个 $n\times m$ 的矩阵，里面是正整数。（$n,m$ 给出）。

你可以询问两个长为 $w$，宽为 $h$ 的矩形是否完全相等。要求这两个矩形不能重叠也不能越界。

你需要求出所有 $(x,y)$ 的数目，满足整个矩形能用 $(1,1)-(x,y)$ 的子矩阵完全平铺出来。

询问次数最多 $3\times\log(n+m)$。

Solution

很显然可以对行和列分别求解，然后把答案乘起来。

实际上，我们只需要求出最小循环节——枚举 $n$ 的质因子，然后试一下它的最小质因子行不行，如果可以就除以这个最小质因子然后接着算直到 $n=1$。算完最小循环节之后就能知道最多能分成几段，那么这个段数的所有因数都是合法的。

也就是说我们需要在 $3$ 次询问以内判断一个串是否能被分成完全相同的若干个串。

我们把每个完全相同的串看成一个字符，问题就转化为询问一个字符串所有字符是否都相等。

设这个字符串长度为 $L$，当 $L=2$，直接问就行。

否则串长度一定为奇数（因为是质数）我们询问 $([1,\left\lfloor\dfrac{L}{2}\right\rfloor],[\left\lceil\dfrac{L}{2}\right\rceil,L-1])$，再询问 $([1,\left\lfloor\dfrac{L}{2}\right\rfloor],[\left\lceil\dfrac{L}{2}\right\rceil+1,L])$，如果两个都完全相等，那么这个串里的字符都相等（自己想想就懂了）。

于是就结束了。

Code

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>
using std::cin;
using std::cout;
using std::endl;

const int maxn = 1010;

int n, m;
int p[maxn * 2], vis[maxn * 2], tot, mi[maxn * 2];
int ansn, ansm;

void init(int n = 2000)
{
    mi[1] = 2;
    for (int i = 2; i <= n; i++)
    {
        if (!vis[i])
            p[++tot] = i, mi[i] = i;
        for (int j = 1; j <= tot && p[j] * i <= n; j++)
        {
            vis[i * p[j]] = 1, mi[i * p[j]] = p[j];
            if (i % p[j] == 0)
                break;
        }
    }
    std::ios::sync_with_stdio(false);
    cin >> ::n >> m;
}

bool ask(int l, int r, int len, bool d)
{
    if (d == 0)
        cout << "? " << n << " " << len << " " << 1 << " " << l << " " << 1 << " " << r << endl;
    else
        cout << "? " << len << " " << m << " " << l << " " << 1 << " " << r << " " << 1 << endl;
    int res;
    cin >> res;
    return res == 1 ? true : false;
}

bool queryn(int L, int len)
{
    if (L == 2)
        return ask(1, len + 1, len, 1);
    int mid = L / 2 * len;
    return ask(1, mid + 1, mid, 1) && ask(1, mid + 1 + len, mid, 1);
}

bool querym(int L, int len)
{
    if (L == 2)
        return ask(1, len + 1, len, 0);
    int mid = L / 2 * len;
    return ask(1, mid + 1, mid, 0) && ask(1, mid + 1 + len, mid, 0);
}

int work1()
{
    int res = n;
    for (int i = n; i > 1; i /= mi[i])
        if (queryn(mi[i], res / mi[i]))
            res /= mi[i];
    int times = n / res;
    int ans = 0;
    for (int i = 1; i <= times; i++)
        if (times % i == 0)
            ans++;
    return ans;
}

int work2()
{
    int res = m;
    for (int i = m; i > 1; i /= mi[i])
        if (querym(mi[i], res / mi[i]))
            res /= mi[i];
    int times = m / res;
    int ans = 0;
    for (int i = 1; i <= times; i++)
        if (times % i == 0)
            ans++;
    return ans;
}

int main()
{
    init();
    int ans = work1() * work2();
    cout << "! " << ans << endl;
}

A¶

Description¶

Solution¶

Code¶

B¶

Description¶

Solution¶

Code¶

C¶

Description¶

Solution¶

Code¶

D¶

Description¶

Solution¶

Code¶

E¶

Description¶

Solution¶

Code¶

F¶

Description¶

Solution¶

Code¶

A

Description

Solution

Code

B

Description

Solution

Code

C

Description

Solution

Code

D

Description

Solution

Code

E

Description

Solution

Code

F

Description

Solution

Code