1878(900div3)

A . How Much Does Daytona Cost?

我们将一个整数定义为子段中最常见的整数，如果它在该子段中出现的次数大于该子段中任何其他整数出现的次数。数组的子数段是数组 \(a\) 中元素的连续数段。

给定一个大小为 \(n\) 的数组 \(a\) 和一个整数 \(k\) ，判断 \(a\) 中是否存在一个非空子段，其中 \(k\) 是最常见的元素。

int a[110], num[110];
void solve()
{
    memset(a, 0, sizeof a);
    memset(num, 0, sizeof num);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i], num[a[i]]++;
    if (num[m])
        cout << "yes\n";
    else
        cout << "no\n";
}

B. Aleksa and Stack

给出 \(a\) 数组，构造一个数组满足：\(3\cdot a_{i+2}\) 不能被 \(a_{i}+a_{i+1}\) 整除。

Solution

方法很多。

\(\text{Solution 1:}\) 假设 \(a_{i},a_{i+1}，a_{i+2}\) 都相差 \(1\).

\[k=\frac{3\times a_{i+2}}{a_{i}+a_{i+1}}=\frac{3\times a_{i}+6}{2\times a_{i}+1}=1+\frac{a_{i}+5}{2\times a_{i}+1}\]

当 \(a_{i}+5<2\times a_{i}+1\) 时，可以保证后面的 \(k\) 都不可能为整数

\(\text{ Solution 2:}\) 序列全为奇数即可。

\[3\times a_{i+2}(odd),a_{i}+a_{i+1}(even) \cap\frac{odd}{even}\neq \text{integer}\]

int n;
void solve()
{
    cin >> n;
    int i = 5;
    while (n--)
        cout << i++ << " ";
    cout << '\n';
}

C. Vasilije in Cacak

给出 \(n,k,x\),判断能否在 \(1-n\) 之间选择 \(k\) 个不同的数，使得他们的和为 \(x\)

Solution

只需算出 \(1-n\) 中选择 \(k\) 个能构成的最大和最小值，看 \(x\) 是否在这个范围内即可。注意开 long long

最小：\(1,2,3\dots k\)
最大：\((n-k+1),(n-k+2)\dots n-1, n\)

long long n, k, x, cnt1, cnt2;
void solve()
{
    cin >> n >> k >> x;
    cnt1 = (k * (k + 1)) / 2;
    cnt2 = (k * (2 * n - k + 1)) / 2;
    if (x >= cnt1 && x <= cnt2)
        cout << "yes\n";
    else
	    cout << "no\n";
}

D. Reverse Madness

给你一个长度为 \(n\) 的字符串 \(s\) (小写字母),接下来会给你一个正整数 \(k\) 和两个长度为 \(k\) 的数组 \(l\) 和 \(r\) 。

保证这两个数组满足以下条件：

\(l_1 = 1\)
\(r_k = n\)
\(l_i \le r_i\)
\(l_i = r_{i-1}+1\)

现在给你一个正整数 \(q\) ，表示你需要对 \(s\) 进行修改的次数。

每个修改都用一个正整数 \(x\) 来定义：

\(\text{find}\) \(i\) ，\(let\) \(l_i \le x \le r_i\) ( \(\text{In This Case:i is Unique}\)）。
\(\text{let}\) \(a=\min(x, r_i+l_i-x)\) \(\text{and}\) \(b=\max(x, r_i+l_i-x)\) 。
\(\text{reverse(s)[a,b]}\)

完成最后一次修改后，输出 \(s\) 。对于每个用例： \(\boxed{\begin{array}&n&k\\s&(string)\\l_{1}&l_{2}&\dots&l_{k}\\r_{1}&r_{2}&\dots&r_{k}\\q\\x_{1}&x_{2}&\dots&x_{q}\end{array}}\)

Solution

做法有：线段树，珂朵莉树, 平衡树，等等很多做法 \(\dots\) (我还没学 \(\dots\))

暴力做法肯定 \(TLE\dots\)

暴力

for (int i = 1; i <= q; i++){
    int x;
    cin >> x;
    for (int j = 1; j <= k; j++){
        if (x >= l[j] && x <= r[j]){
            int aa = min(x, r[j] + l[j] - x), bb = max(x,r[j] + l[j] - x);
            reverse(a.begin() + aa - 1, a.begin() + bb);
            break;
        }
    }
}

Jiangly 做法：

\(f\) 数组可以来判断查询某个数的奇偶，为偶数的话就置为 0 (因为偶数的话，就相当于在某个相同区间翻转了偶数次，即相当于没有翻转)，奇数置为 1 (相当于在该区间翻转了 1 次)

然后再遍历每一次的 \((l,r)\)，for (int j = l[i]; j <= l[i] + r[i] - j;j++) 相当于是每次只遍历前面一半即 for (int j = l[i]; j <= (l[i] + r[i])/2; j++)

在以 (l+r)/2 为对称轴两侧，如果 \(f[i]\) 与 \(f[\) 对称的相应的位置 \(]\) 相同(都为 \(0|1\)),则抵消，不交换.反之则交换.

Question: 如何证明 swap 的正确性？\({\text{迷迷糊糊}\dots}\)

void solve()
{
    int n, k, q;
    cin >> n >>k;
    string s;
    cin >> s;
    vector<int> l(k), r(k), f(n);
    for (int i = 0; i < k;i++)
        cin >> l[i], l[i]--;
    for (int i = 0; i < k;i++)
        cin >> r[i], r[i]--;
    cin >> q;
    while(q--)
    {
        int x;
        cin >> x;
        f[x - 1] ^= 1;
    }

    for (int i = 0; i < k;i++)
    {
        int rev = 0;
        for (int j = l[i]; j <= l[i] + r[i] - j;j++)//for (int j = l[i]; j <= (l[i] + r[i])/2; j++)
        {
			rev ^= f[j] ^ f[l[i] + r[i] - j];
            if(rev)
                swap(s[j], s[l[i] + r[i] - j]);
        }
    }
    cout << s << '\n';
}

E . Iva & Pav

定义 \(f(l,r)=a_{l}\&a_{l+1}\&\dots\&a_{r}(l\leq r)\).

给出 \(q\) 组查询：每组查询由 \(k,l\) 组成，求最大的索引 \(r(l\leq r\leq n)\to f(l,r)\geq k\)

输出这样的 \(r\)，若不存在，输出 -1

Solution

关键在于如何处理 &，没有看懂题解...

需要用到 ST 表或线段树(学了再说(待更 \(\dots\)))

官方题解：(前缀和加二分)

pref(i, j) 代表整数 i 的二进制表示中在位置 j 的比特位的前缀和

int a[200010], pre[200010][30];
void solve()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < 30; j++)
        {
            if (a[i] & (1 << j))
                pre[i + 1][j] = pre[i][j] + 1;
            else
                pre[i + 1][j] = pre[i][j];
        }
    }
    int q;
    cin >> q;
    while (q--)
    {
        int l, k;
        cin >> l >> k;
        if (a[l - 1] < k)
        {
            cout << "-1 ";
            continue;
        }
        int low = l, high = n, ans = l;
        while (low <= high)
        {
            int mid = (low + high) / 2, num = 0;
            for (int j = 0; j < 30; j++)
                if (pre[mid][j] - pre[l - 1][j] == mid - l + 1)
                    num += (1 << j);
            if (num >= k)
                low = mid + 1, ans = max(ans, mid);
            else
                high = mid - 1;
        }
        cout << ans << ' ';
    }
    cout << '\n';
}

Jiangly:(没看懂 \(\dots\))

nxt[i][j] 表示从位置 \(i\) 开始，第一个使得 \(a_i \ \& \ a_{i+1} \ \& \dots \& \ a_r\) 的结果为 \(0\) 的索引 \(r\)。

然后，对于每个查询用例，我们找到最大的索引 \(r\)，使得 \(a_l \ \& \ a_{l+1} \ \& \dots \& \ a_r \ge k\)。我们可以从最高位开始，逐位地检查 \(k\)，如果某一位是 \(1\)，那么我们只需要找到满足 \(a_l \ \& \ a_{l+1} \ \& \dots \& \ a_r \ge k\) 的最小的 \(r\)，然后更新答案为这个最小的 \(r\)。如果某一位是 \(0\)，那么我们只需要找到满足 \(a_l \ \& \ a_{l+1} \ \& \dots \& \ a_r \ge k\) 的最大的 \(r\)，然后更新答案为这个最大的 \(r\)。

最后，如果答案的索引 \(r\) 小于等于 \(l\)，那么将答案更新为 \(-1\)。

void solve() {
    int n;
    std::cin >> n;
    
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    
    std::vector nxt(n + 1, std::vector<int>(30, n));
    for (int i = n - 1; i >= 0; i--) {
        nxt[i] = nxt[i + 1];
        for (int j = 0; j < 30; j++) {
            if (~a[i] >> j & 1) {
                nxt[i][j] = i;
            }
        }
    }
    
    int q;
    std::cin >> q;
    
    while (q--) {
        int l, k;
        std::cin >> l >> k;
        l--;
        int ans = l,res = n;
        for (int i = 29; i >= 0; i--) {
            if (k >> i & 1) {
                res = std::min(res, nxt[l][i]);
            } else {
                ans = std::max(ans, min(res, nxt[l][i]));
            }
        }
        ans = std::max(ans, res);
        if (ans <= l) {
            ans = -1;
        }
        std::cout << ans << " ";
    }
}

F. Vasilije Loves Number Theory

设 \(d(n)\) 为 \(n\) 的正整数除数，有两个选择：

1 x：将 \(n\) 设置为 \(n\cdot x\)，然后回答是否存在一个正整数 \(a\) 使得 \(\gcd(a,n)=1\cap d(n\cdot a)=n\)
2：将 \(n\) 设置为初始值

Solution

\(d(n)\) 为因子个数函数, 由唯一分解定理有 \(n=p_{1}^{a_{1}}+p_{2}^{a_{2}}+\dots+p_{r}^{a_{r}}\to d(n)=(a_{1}+1)(a_{2}+1)\dots(a_{r}+1)\)

[!abstract]- \(胡言乱语\dots\) \(d(12)=6\{1,2,3,4,6,12\},\not\to d(12)=d(1)\times d(2)\times\dots \times d(12)\) \(d(1)=1,d(2)=2,d(3)=2,d(4)=3,d(6)=4,d(12)=6\)

如果 \(m,n\) 互质，则 \(d(m\times n)=d(m)\times d(n)\)

则题目中的 \(gcd(a,n)=1\to d(n\cdot a)=d(n)\times d(a)?=n\)

如果 \(n\) 是一个奇数，且 \(n\) 可以表示为两个不同素数的乘积（\(n = p*q\)，\(p\) 和 \(q\) 为素数），那么 \(d (n) = 4\)（例如，\(n = 21，d (21) = 4\)）。

设 \(d\) 数组为因子个数数组，则 \(\text{find a}\to d(n)\times d(a)\equiv n\cap gcd(a,n)\equiv1\to d(a)=\frac{n}{d(n)}\to d(a) \text{ is integer}\to'YES' .or'NO'\)

[!NOTE]- 用线性筛求 \(d(i)\) \(p[i]\)：\(i\) 的最小质因数，用于判断 \(i\) 是否为质数 \(pr[]\)：存储质数的数组 \(d[i]\)：\(i\) 的约数个数，即积性函数值 \(a[i]\)：\(i\) 与 \(p[i\)]的幂指数关系 \(cnt\)：质数计数器，记录质数的个数

利用线性筛法求解积性函数 \(d[]\)的值，同时利用数组 \(p[]\)和 \(pr[]\)存储最小质因数和质数，以及数组 \(a[]\)记录指数关系。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
p[1] = d[1] = ans[1] = 1;//积性函数的定义：f[1]=1
for (int i = 2; i <= n; i ++) {
    if (!p[i]) p[i] = i, pr[++ cnt] = i, d[i] = 2, a[i] = 1;
    for (int j = 1; j <= cnt && pr[j] * i <= n; j ++) {
        p[i * pr[j]] = pr[j];
        if (p[i] == pr[j]) {
            d[i * pr[j]] = d[i] / (a[i] + 1) * (a[i] + 2);
            a[i * pr[j]] = a[i] + 1;
            break;
        }
        else {
            d[i * pr[j]] = d[i] * d[pr[j]];
            a[i * pr[j]] = 1;
        }
    }
}
Eg：abc172_d

\(\Huge{\text{if }d(n)|n\leftrightarrow YES}\)

首先，预先计算每个小于 \(10^6\) 的正整数的最小质因数。这样，我们就能在对数时间内对所有小于或等于 \(10^6\) 的数字进行因式分解。我们还利用上述公式对 \(n\) 进行因式分解并找出其除数个数，然后为每个质因数存储其仍能整除 \(n\) 的最高幂次。我们可以使用数组或映射来完成这项工作，无论哪种方法，我们都把这个结构称为 \(power\) 。

现在我们需要处理查询：

对于第一个查询，我们在 \(\mathcal{O}(\log{x})\) 运算中对 \(x\) 进行因式分解，并让 \(x = r_1^{\beta_1} \cdot r_2^{\beta_2} \cdots r_\ell^{\beta_\ell}\) 成为数字 \(x\) 的因式分解。我们通过以下操作更新 \(d(n)\) ：对于 \(x\) 中的每个素数 \(r_i\) ，用 \(d(n)\) 除以 \(power[r_i]+1\) ，然后将 \(\beta_i\) 加到 \(power[r_i]\) ，再用 \(d(n)\) 乘以 \(power[r_i]+1\) 。计算出 \(d(n)\) 后，我们应该检查 \(n\) 是否能被它整除。我们可以用两种方法来做这件事：

我们将之前所有类型 \(1\) 查询的值（在最后一个类型 \(2\) 查询之后）与起始值 \(n\) 的值相乘，再乘以模数 \(d(n)\) ，因为 \(n\) 的值可能非常大，我们无法将其存储在 64 位整数中。如果 mod \(d(n)\) 的值是 \(0\) ，那么它可以被整除，我们的查询答案就是 "YES"，否则就是 "NO"。

时间复杂度 \(\mathcal{O}(Q \cdot (Q + \log{x}) + \log{n})\) 。

关键是如何处理(没有看懂)

Jiangly

std::vector<int> minp, primes;
 
constexpr int V = 1E6;
 
int cnt[V + 1];
 
void sieve(int n) {//预处理，n=1e6
    minp.assign(n + 1, 0);
    primes.clear();
    
    for (int i = 2; i <= n; i++) {
        if (minp[i] == 0) {
            minp[i] = i;
            primes.push_back(i);
        }
        
        for (auto p : primes) {
            if (i * p > n) {
                break;
            }
            minp[i * p] = p;
            if (p == minp[i]) {
                break;
            }
        }
    }
}
 
void solve() {
    int n, q;
    std::cin >> n >> q;
    
    std::vector<int> s;
    int d = 1;
    auto add = [&](int x, int t = 1) {
        while (x > 1) {
            int p = minp[x];
            x /= p;
            d /= cnt[p] + 1;
            cnt[p] += t;
            d *= cnt[p] + 1;
        }
    };
    s.push_back(n);
    add(n);
    while (q--) {
        int o;
        std::cin >> o;
        
        if (o == 1) {
            int x;
            std::cin >> x;
            s.push_back(x);
            add(x);
            int v = 1;
            for (auto x : s) {
                v = 1LL * v * x % d;
            }
            if (v == 0) {
                std::cout << "YES\n";
            } else {
                std::cout << "NO\n";
            }
        } else {
            while (s.size() > 1) {
                add(s.back(), -1);
                s.pop_back();
            }
        }
    }
    while (s.size() > 0) {
        add(s.back(), -1);
        s.pop_back();
    }
    std::cout << "\n";
}

G. wxhtzdy ORO Tree

(待更...)