A.Who is better?

题意：

给定组和，。两个人互相拿这个个数，先手第一次不能拿完，每次后手只能拿到前一次拿的数量之间的数量，不能拿时则输

题解：

可由中国剩余定理求出，算出前几个数可以猜测为斐波那契数列时先手必败

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 105;
ll b[maxn], a[maxn], f[maxn];
int n;
ll Ex_gcd(ll a, ll b, ll &x, ll &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    ll d = Ex_gcd(b, a % b, x, y);
    ll t = x;
    x = y;
    y = t - a / b * y;
    return d;
}
ll Ex_Crt()
{
    ll aa = b[1], rr = a[1], x, y;
    for (int i = 2; i <= n; ++i)
    {
        ll bb = b[i], c = a[i] - rr;
        ll d = Ex_gcd(aa, bb, x, y);
        if (c % d)
            return -1; //c不能整除d，不存在整数解
        c = c / d;
        bb = bb / d;
        x = (x * c % bb + bb) % bb;
        ll lcm = aa * bb;
        rr = (x * aa % lcm + rr) % lcm;
        aa = lcm;
    }
    if (rr == 0 || rr == 1)
        rr += aa;
    return rr;
}
int main()
{
    scanf("%d",&n);
    f[1] = f[2] = 1;
    for (int i = 3; i < 80; ++i)
        f[i] = f[i - 1] + f[i - 2];
    for (int i = 1; i <= n; ++i)
        scanf("%lld%lld",&b[i],&a[i]);
    ll x = Ex_Crt();
    if (x == -1)
        puts("Tankernb!");
    else
    {
        bool flag = false;
        for (int i = 3; i < 80; ++i)
        {
            if (f[i] == x)
            {
                flag = true;
                break;
            }
        }
        if (flag)
            puts("Lbnb!");
        else
            puts("Zgxnb!");
    }
    return 0;
}

B.so easy

题意：

给定一个的序列，给出次操作
1 将点标为不可用
2 询问从开始第一个可用的数
原先所有数均可用

题解：

用set把所有不可用的数存下来，每次都往后找第一个可用的数即可或者用并查集算出每个开始的第一个可用数

set

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
set<int> s;
int main()
{
    int n, q;
    scanf("%d%d", &n, &q);
    while (q--)
    {
        int op, x;
        scanf("%d%d", &op, &x);
        if (op == 1)
            s.insert(x);
        else
        {
            while (s.count(x))
                x++;
            printf("%d\n", x);
        }
    }
    return 0;
}

并查集

#include <bits/stdc++.h>
using namespace std;
unordered_map<int, int> mp;
int find(int x)
{
    return mp[x] ? mp[x] = find(mp[x]) : x;
}
int main()
{
    int n, q;
    scanf("%d%d", &n, &q);
    while (q--)
    {
        int op, x;
        scanf("%d%d", &op, &x);
        if (op == 1)
            mp[x] = find(x + 1);
        else
            printf("%lld\n", find(x));
    }
    return 0;
}

C.Buy Watermelon

题意：

判断一个西瓜能否均分为两份，并且每一份的重量至少是

题解：

为偶数，且不为即可

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int w;
    scanf("%d", &w);
    if (!(w & 1) && (w != 2))
        puts("YES");
    else
        puts("NO");
    return 0;
}

D.Carneginon

题意：

给定两个字符串和，判断和的长度关系和是否为字串

题解：

根据题意模拟即可，判断字串可以用strstr()函数也可以用算法
strstr()函数

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
char s1[100005],s2[100005];
int main(){
    cin >> s1;
    int len1=strlen(s1);
    int t;
    scanf("%d",&t);
    while(t--){
        cin >> s2;
        int len2=strlen(s2);
        if(len1==len2){
            if(strcmp(s1,s2)==0)printf("jntm!\n");
            else printf("friend!\n");    
        }
        else if(len1<len2){
            if(strstr(s2,s1)==NULL)printf("senior!\n");
            else printf("my teacher!\n");
        }
        else if(len1>len2){
            if(strstr(s1,s2)==NULL)printf("oh, child!\n");
            else printf("my child!\n");
        }
    }    
}  

算法

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int s[N], p[N], ne[N];
int n, m, sum, ans;
void getNext(const char P[], int ne[])
{
    int i = 0, j;
    j = ne[0] = -1;
    while (i < m)
    {
        while (-1 != j && P[i] != P[j])
            j = ne[j];
        ne[++i] = ++j;
    }
}

void kmp(const char S[], const char P[], int ne[])
{
    int i, j;
    getNext(P, ne);
    i = j = 0;
    while (i < n)
    {
        while (-1 != j && S[i] != P[j])
            j = ne[j];
        i++;
        j++;
        if (j >= m)
        {
            if (ans == -1)
                ans = i - m + 1;
            j = ne[j];
        }
    }
}
char T[N], S[N];
int main()
{
    int t;
    scanf("%s%d", T, &t);
    while (t--)
    {
        getchar();
        scanf("%s", S);
        int lent = strlen(T), lens = strlen(S);
        if (lent == lens)
        {
            if (strcmp(S, T) == 0)
                puts("jntm!");
            else
                puts("friend!");
        }
        else if (lent > lens)
        {
            ans = -1;
            memset(ne, 0, sizeof(ne));
            n = lent, m = lens;
            kmp(T, S, ne);
            if (ans != -1)
                puts("my child!");
            else
                puts("oh, child!");
        }
        else
        {
            ans = -1;
            memset(ne, 0, sizeof(ne));
            n = lens, m = lent;
            kmp(S, T, ne);
            if (ans != -1)
                puts("my teacher!");
            else
                puts("senior!");
        }
    }
    return 0;
}

E.XKC's basketball team

题意：

给定个数和一个数，对每个求出最大的，满足，输出两者之间间隔多少数

题解：

可以用单调队列从后往前记录，对于每个都对单调队列进行一次二分即可。
也可以用线段树维护区间最大值，每次只要找最大、最靠右的那个数即可，这个可以在query()函数中，先判断右结点再判断左结点来实现。

单调队列+二分

#include<bits/stdc++.h>
using namespace std;
int a[N], q[N], pos[N];
const int N = 5e5 + 5;
int main()
{
    int n, m, top = 0;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = n; i; i--)
    {
        if (q[top] < a[i])
            q[++top] = a[i], pos[top] = i;
    }
    for (int i = 1; i <= n; i++)
    {
        int index = lower_bound(q + 1, q + top + 1, a[i] + m) - q;
        printf("%d%c", (pos[index] - i - 1 >= 0) ? pos[index] - i - 1 : -1, i == n ? '\n' : ' ');
    }
}

线段树

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 5;
int n, m, a[maxn], ans[maxn], MAX[maxn << 2];
void build(int l, int r, int x)
{
    if (l == r)
    {
        MAX[x] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, x << 1);
    build(mid + 1, r, x << 1 | 1);
    MAX[x] = max(MAX[x << 1], MAX[x << 1 | 1]);
}
void query(int l, int r, int L, int R, int x, int val, int &ans)
{
    if (l > R || r < L || ans != -1)
        return;
    if (l == r)
    {
        ans = l;
        return;
    }
    int mid = (l + r) >> 1;
    if (MAX[x << 1 | 1] >= val)
        query(mid + 1, r, L, R, x << 1 | 1, val, ans);
    if (MAX[x << 1] >= val)
        query(l, mid, L, R, x << 1, val, ans);
}
int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%d", a + i);
    build(1, n, 1);
    for (int i = 1; i <= n; ++i)
    {
        ans[i] = -1;
        query(1, n, i + 1, n, 1, a[i] + m, ans[i]);
        if (ans[i] != -1)
            ans[i] = ans[i] - i - 1;
    }
    for (int i = 1; i <= n; i++)
        printf("%d%c", ans[i], i == n ? '\n' : ' ');
    return 0;
}

G.Colorful String

题意：

给定一个字符串，求所有回文子串中不同字符种数之和

题解：

先用Manacher预处理一波，然后找出每一个位置的26个字母下一个位置，存在一个vector里面，然后最后找的时候就是差值对应的个数。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 5;
const int INF = 0x3f3f3f3f;
char S[N], T[N << 1];
int Len[N << 1];
int nxt[N][27];
vector<int> V[N];
void Manacher(char *s)
{
    int L = strlen(s);
    int po = 0, mx = 0;
    for (int i = 1; i <= L * 2; i++)
        T[i] = i & 1 ? '#' : s[i / 2 - 1];
    T[0] = '@';
    T[2 * L + 1] = '#';
    T[2 * L + 2] = '\0';
    ll tmp = 0;
    for (int i = 1; i <= 2 * L; i++)
    {
        if (i < mx)
            Len[i] = min(mx - i, Len[2 * po - i]);
        else
            Len[i] = 1;
        while (T[i + Len[i]] == T[i - Len[i]])
            Len[i]++;
        if (i + Len[i] > mx)
        {
            po = i;
            mx = i + Len[i];
        }
    }
}
int main()
{
    scanf("%s", S);
    Manacher(S);
    int len1 = strlen(S);
    int len2 = strlen(T);
    for (int j = 0; j < 26; j++)
    {
        int pos = INT_MAX;
        for (int i = len1 - 1; i >= 0; i--)
        {
            if (S[i] == j + 'a')
                pos = i;
            nxt[i][j] = pos;
        }
    }
    for (int i = 0; i < len1; i++)
    {
        for (int j = 0; j < 26; j++)
            V[i].push_back(nxt[i][j]);
        sort(V[i].begin(), V[i].end());
    }
    ll ans = 0;
    for (int i = 2; i < len2; i++)
    {
        int L = Len[i] / 2;
        if (L == 0)
            continue;
        int pos = i / 2 - 1;
        if (i & 1)
            pos++;
        int R = pos + L - 1;
        int Last = V[pos][0];
        int cnt = 0;
        for (auto x : V[pos])
        {
            if (x > R)
                break;
            int r = x - 1;
            ans = ans + (ll)(cnt++) * (ll)(r - Last + 1);
            Last = x;
        }
        if (R >= Last)
            ans = ans + (ll)cnt * (ll)(R - Last + 1);
    }
    printf("%lld\n", ans);
    return 0;
}

I.query

题意：

给定一个长度为的排列，给出组询问，每种询问给定，求中询问多少组满足

题解：

就是倍数关系，因此对于每个数将它的倍数都作为一对数记录下来，那么问题就是求之间对数的个数，每次都去查找肯定会超时，发现这是道二位偏序问题。因此将每个问题都离线处理，将从打到小排序，那么对于每个问题，肯定满足，那么只需要用树状数组维护，每次调用即可

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
#define lowbit(x) x &(-x)
struct Query
{
    int l, r, k, f;
    Query(){};
    Query(int l0, int r0, int k0, int f0) : l(l0), r(r0), k(k0), f(f0){};
    bool operator<(const Query &C) const
    {
        if (l != C.l)
            return l > C.l;
        return f > C.f;
    }
} q[maxn << 6];
int n, m;
int pos[maxn], cnt;
int a[maxn], bit[maxn], ans[maxn];
void update(int x, int ad)
{
    for (; x <= n; x += lowbit(x))
        bit[x] += ad;
}
int query(int x)
{
    int res = 0;
    for (; x; x -= lowbit(x))
        res += bit[x];
    return res;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        pos[a[i]] = i;
    }
    for (int i = 1; i <= m; i++)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        q[cnt++] = Query(l, r, i, 0);
    }
    for (int i = 1; i <= n; i++)
        for (int j = a[i] * 2; j <= n; j += a[i])
            q[cnt++] = Query(min(i, pos[j]), max(i, pos[j]), 0, 1);
    sort(q, q + cnt);
    for (int i = 0; i < cnt; i++)
    {
        if (q[i].f)
            update(q[i].r, 1);
        else
            ans[q[i].k] = query(q[i].r);
    }
    for (int i = 1; i <= m; i++)
        printf("%d\n", ans[i]);
}

J.Random Access Iterator

题意：

给定一棵以号节点为根节点的树，从根节点出发，在节点有次等概率进入儿子节点，求能够到达最深深度的概率。

题解：

第一次求出每个点的深度，和最深的深度
树形,定义为从开始能到达最深节点的概率，每次不能到达最深节点的概率为，那么，因此最终结果为，这个过程再跑一次即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e6 + 5;
const int mod = 1e9 + 7;
int head[maxn], nxt[maxn << 1], to[maxn << 1], cnt;
int dep[maxn], siz[maxn], mxd[maxn];
ll dp[maxn];
ll ksm(ll a, ll b, ll mod)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
void init()
{
    memset(head, -1, sizeof(head));
    cnt = 0;
}
void addedge(int u, int v)
{
    to[cnt] = v;
    nxt[cnt] = head[u];
    head[u] = cnt++;
}
void dfs(int u, int fa)
{
    mxd[u] = dep[u];
    for (int i = head[u]; ~i; i = nxt[i])
    {
        int v = to[i];
        if (v == fa)
            continue;
        dep[v] = dep[u] + 1;
        siz[u]++;
        dfs(v, u);
        mxd[u] = max(mxd[u], mxd[v]);
    }
}
void dfs1(int u, int fa)
{
    ll sum = 0;
    for (int i = head[u]; ~i; i = nxt[i])
    {
        int v = to[i];
        if (v == fa)
            continue;
        if (mxd[v] == mxd[1])
        {
            dfs1(v, u);
            sum = (sum + dp[v]) % mod;
        }
    }
    if (siz[u] == 0)
        dp[u] = 1;
    else
    {
        ll p = sum * ksm(siz[u], mod - 2, mod) % mod;
        p = (1 - p + mod) % mod;
        dp[u] = (1 - ksm(p, siz[u], mod) + mod) % mod;
    }
}
int main()
{
    init();
    int n;
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        addedge(u, v);
        addedge(v, u);
    }
    dfs(1, 0);
    dfs1(1, 0);
    printf("%lld\n", dp[1]);
    return 0;
}

K.Center

题意：

给定个点，要求添加尽可能少的点使得存在一个点，满足对每个点都能找到一个点以该点为中心

题解：

记录下每个点与这个点的中心，统计每个点出现的次数，次数最多的那个就作为中心，要添加的点数量就是减去这个最大值

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int maxn = 1005;
pii p[maxn];
map<pii, int> mp;
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d%d", &p[i].first, &p[i].second);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            mp[{p[i].first + p[j].first, p[i].second + p[j].second}]++;
    int ans = 0;
    for (auto i : mp)
        ans = max(ans, i.second);
    printf("%d\n", n - ans);
    return 0;
}

M.Longest subsequence

题意：

给定一个长度为的字符串和一个长度为的字符串，要求在中找到一个最长的字典序大于的字序列

题解：

字典序大于只有两种情况，当前位置和相等和当前位置，当前位置和相等那么只需要每次都选取尽可能靠前的那个位置，再对考虑两种情况，对当前位置那么也只需要取尽可能靠前那个，从当前位置开始后面的都可以取过来使得长度尽可能长。模拟即可，只需要考虑到前面几位都与都相同，那么可以把后面的所有字符都取过来，单独判断一下即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
char s[maxn], t[maxn];
int dp[maxn][30];
int main()
{
    int n, m;
    cin >> n >> m;
    scanf("%s%s", s + 1, t + 1);
    for (int i = n - 1; i >= 0; i--)
        for (int j = 0; j < 26; j++)
        {
            if (s[i + 1] - 'a' == j)
                dp[i][j] = i + 1;
            else
                dp[i][j] = dp[i + 1][j];
        }
    int ans = 0, pos = 0, flag = 1;
    for (int i = 1; i <= m; i++)
    {
        for (int j = t[i] - 'a' + 1; j < 26; j++)
            if (dp[pos][j] > 0)
                ans = max(ans, i + n - dp[pos][j]);
        pos = dp[pos][t[i] - 'a'];
        if (pos == 0)
        {
            flag = 0;
            break;
        }
    }
    if (flag && pos != n)
        ans = max(ans, m + n - pos);
    printf("%d\n", ans ? ans : -1);
    return 0;
}