A.Orac and Factors

题意：

$f(n)$ 为 $n$ 的第二小因数，询问执行 $k$ 次 $n=f(n)+n$ 后的结果

题解：

如果 $n$ 为偶数接下来的数全为偶数，因此 $+2$ 即可。如果为奇数就去找第二小因数，一直找 $k$ 次或者 $n$ 为奇数即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 8e3 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
void solve()
{
    ll n, k;
    scanf("%lld%lld", &n, &k);
    while (k)
    {
        if (n % 2 == 0)
            break;
        for (ll i = 2; i <= n; i++)
            if (n % i == 0)
            {
                n += i;
                break;
            }
        k--;
    }
    n = n + k * 2;
    printf("%lld\n", n);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

B.Orac and Models

题意：

给定一个序列 $s_n$ ,找出一个最长的子串满足 $i_{j+1} \% i_j == 0 \&\& s_{i_j} < s_{i_{j+1}}$ ,其中 $i_j$ 为字串中第 $j$ 个元素在原序列中的下标，输出最长字串的长度

题解：

计算出每个数当因子的长度，用 $dp$ 维护，最后取最大值即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int a[maxn], dp[maxn];
void solve()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]), dp[i] = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 2; j * i <= n; j++)
            if (a[i * j] > a[i])
                dp[i * j] = max(dp[i * j], dp[i] + 1);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(ans, dp[i]);
    printf("%d\n", ans);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

C.Orac and LCM

题意：

给定一个序列 $a_n$ ，求出 $\gcd(\{\textrm{lcm}(\{a_i,a_j\})\ |\ i<j\})$ ,即所有 $lcm$ 的 $gcd$

题解：

根据两个整数的最大公因子和最小公倍数中的分配律： $lcm(a, gcd(b, c)) = gcd(lcm(a, b), lcm(a, c))$ 。可以求得 $\gcd(\{\textrm{lcm}(\{a_i,a_j\})\ |\ i<j\})=\gcd\limits_{i=1}^{n-1}{lcm(a_i,\gcd\limits_{j=i+1}^n a_j)}$ 。
gcd百度百科

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
ll a[maxn], t[maxn];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    t[n] = 0;
    for (int i = n - 1; i >= 1; i--)
        t[i] = __gcd(t[i + 1], a[i + 1]);
    ll ans = 0;
    for (int i = 1; i <= n; i++)
        ans = __gcd(ans, a[i] * t[i] / __gcd(a[i], t[i]));
    printf("%lld\n", ans);
    return 0;
}

D.Orac and Medians

题意：

给定一个序列 $a_n$ 和 $k$ ，每次操作可以选择一段区间 $s=\{a_l, a_{l + 1}, \ldots, a_r\}$ ，将 $a_l, a_{l + 1}, \ldots, a_r\$ 均变为 $a_{\lfloor \frac{|s|+1}{2}\rfloor}$ ，询问最终能否使得整个序列都变为 $k$

题解：

首先判断区间内是否有存在一个 $a_i==k$ ，再判断是否存在一段长度 $\leq3$ 的区间满足其中存在两个数 $\geq k$ 。当存在两个数 $=k$ 时，只需要每次取三个数组成的连续区间就能将区间的所有值变为 $k$ ；当存在两个数 $>k$ 时，可以将三个数组成的连续区间变为全 $>k$ ，那么只需要在区间中留一个 $k$ ，其他的全部变为 $>k$ ，那么每次取 $k$ 和一个 $>k$ 的值，就能将 $>k$ 的数变为 $k$
特判只有一个数的情况。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
ll a[maxn];
void solve()
{

    int n, k;
    scanf("%d%d", &n, &k);
    int f1 = 0, f2 = 0;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
        if (a[i] == k)
            f1 = 1;
    }
    int last = -10;
    for (int i = 0; i < n; i++)
    {
        if (a[i] >= k)
        {
            if (i - last <= 2)
                f2 = 1;
            last = i;
        }
    }
    if (f1 && (f2 || n == 1))
        puts("yes");
    else
        puts("no");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

E.Orac and Game of Life

题意：

给定一个 $n*m$ 的棋盘，棋盘一开始有两种颜色：白色(0)和黑色(1)。
有一种操作，每次操作：

若该格子有相邻格子的颜色与之相同，则颜色翻转
若该格子没有相邻格子的颜色与之相同，则颜色不变

图片说明
有 $t$ 次询问，每次询问都有 $i$ , $j$ , $p$ ，询问第 $i$ 行第 $j$ 列格子经过 $t$ 次操作后的颜色

题解：

先判断哪些格子一开始就会翻转，在通过这些点向四周一开始不会翻转的格子辐射。所以最终只要判断辐射到那个节点所需要的时间是否 $\geq t$ ，如果是再判断是否需要翻转即可。本质是道多源bfs

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e3 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
char c[maxn][maxn];
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
ll vis[maxn][maxn];
struct node
{
    int x, y;
    ll d;
};
bool check(int x, int y)
{
    for (int i = 0; i < 4; i++)
        if (c[x][y] == c[x + dir[i][0]][y + dir[i][1]])
            return true;
    return false;
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, m, t;
    cin >> n >> m >> t;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> c[i][j], vis[i][j] = -1;
    queue<node> q;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (check(i, j))
                q.push({i, j, 0ll}), vis[i][j] = 0;
    while (!q.empty())
    {
        node u = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int x = u.x + dir[i][0], y = u.y + dir[i][1];
            if (x >= 1 && y >= 1 && x <= n && y <= m && vis[x][y] == -1)
            {
                q.push(node{x, y, u.d + 1ll});
                vis[x][y] = u.d + 1ll;
            }
        }
    }
    while (t--)
    {
        ll i,j,p;
        cin >> i >> j >> p;
        ll ans = (c[i][j] - '0');
        if (vis[i][j] >= 0 && p > vis[i][j] && (p - vis[i][j]) & 1)
            ans ^= 1;
        cout << ans << "\n";
    }
    return 0;
}

Codeforces Round #641 (Div. 2)

A.Orac and Factors

题意：

题解：

B.Orac and Models

题意：

题解：

C.Orac and LCM

题意：

题解：

D.Orac and Medians

题意：

题解：

E.Orac and Game of Life

题意：

题解：