徐州网络赛

B. so easy

离散然后并查集，赛后发现暴力也能过。。。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair < int , int > P;
const int N = 2e6 + 10;
const int inf = 0x3f3f3f3f;
struct node{
    int x,y;
}a[N];
int b[N],c[N],tot,q,n,fa[N];
int get(int x)
{
    if(x==fa[x]) return x;
    return fa[x]=get(fa[x]);
}
int main ()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d",&a[i].x,&a[i].y);
        c[i]=a[i].y;
    }
    sort(c+1,c+q+1);
    int m=unique(c+1,c+q+1)-c-1;
    b[++tot]=c[1];
    for(int i=2;i<=m;i++)
    {
        if(c[i]-c[i-1]>1){
            b[++tot]=c[i-1]+1;
        }
        b[++tot]=c[i];
    }
    if(c[m]+1<=n) b[++tot]=c[m]+1;
    for(int i=1;i<=tot;i++)
        fa[i]=i;
    for(int i=1;i<=q;i++)
    {
        a[i].y=lower_bound(b+1,b+tot+1,a[i].y)-b;
        if(a[i].x==1){
            int u=get(a[i].y);
            fa[u]=u+1;
        }
        else{
            printf("%d\n",b[get(a[i].y)]);
        }

    }
    return 0;
}

D. Carneginon

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair < int , int > P;
const int N = 1e5 + 10;
const int inf = 0x3f3f3f3f;
ull f[N],p[N];
ull f1[N];
char s[N],str[N];
int q;
void Hash()
{
    int len=strlen(s+1);
    p[0]=1;
    for(int i=1;i<=len;i++)
    {
        f[i]=f[i-1]*131+(s[i]-'a'+1);
        p[i]=p[i-1]*131;
    }
}
void hash1()
{
    int len=strlen(str+1);
    for(int i=1;i<=len;i++)
    {
        f1[i]=f1[i-1]*131+(str[i]-'a'+1);
    }
}
ull get(int l,int r)
{
    return f[r]-f[l-1]*p[r-l+1];
}
ull get1(int l,int r)
{
    return f1[r]-f1[l-1]*p[r-l+1];
}
int main ()
{
    int len,len1;
    scanf("%s",s+1);
    len1=strlen(s+1);
    Hash();
    scanf("%d",&q);
    while(q--)
    {
        scanf("%s",str+1);
        len=strlen(str+1);
        if(len==len1){
            bool f=true;
            for(int i=1;i<=len;i++){
                if(s[i]!=str[i]) {
                    f=false;
                    break;
                }
            }
            puts(f?"jntm!":"friend!");
        }
        else if(len<len1){
            hash1();
            bool f=false;
            for(int i=1;i+len-1<=len1;i++){
                if(get(i,i+len-1)==get1(1,len)){
                    f=true;
                    break;
                }
            }
            puts(f?"my child!":"oh, child!");
        }
        else{
            hash1();
            bool f=false;
            for(int i=1;i+len1-1<=len;i++){
                if(get(1,len1)==get1(i,i+len1-1)){
                    f=true;
                    break;
                }
            }
            puts(f?"my teacher!":"senior!");
        }
    }
    return 0;
}

E. XKC's basketball team

倒序遍历，维护一个值递增的数组，同时保存下标，因为如果a[i]比a[i+1]小，这个a[i]是无用的，所以维护一个值递增，下标递减的数组，每次二分即可，这样二分到的值一定是位置最大的

#include <cstdio>
#include <string>
#include <iostream>
using namespace std;

const int maxn = 1e6 + 5;

int w[maxn];
int st[maxn];
int ed[maxn],ans[maxn];

int main()
{
    int n, m;
    scanf("%d%d",&n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%d",&w[i]);
    st[1] = w[n];
    ed[1] = n;
    int ss= 1;
    ans[n]=-1;
    for(int i = n-1; i >= 1; i--)
    {
        if(w[i] > st[ss])
        {
            st[++ss] = w[i];
            ed[ss] = i;
        }
        int p=lower_bound (st+1,st+ss+1,w[i]+m)-st;
        if(p>ss) ans[i]=-1;
        else ans[i]= ed[p]-i-1;
    }
    for(int i=1;i<=n;i++){
        printf("%d",ans[i]);
        if(i!=n) putchar(' ');
    }
    puts("");
    return 0;
}

G. Colorful String

这题真是气死我了，马拉车板子抄错了，T成sb了，啊啊啊啊。

首先马拉车找到以当前位置为中心的回文串左端点，由于不能暴力算，所以我们可以计算每个字符对答案的贡献，ai记录距离i最近的j字符的位置，那么这个位置到以当前字符为中心的回文串最左端点贡献都是1，预处理一下即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
//typedef pair < int , int > P;
const int N = 6e5 + 10;
const int inf = 0x3f3f3f3f;
char s[N], tmp[N];
int p[N];
int aa[N], a[N][30];
void manacher() {
    int len = strlen(s + 1);
    int tot = 0;
    tmp[tot++] = '$';
    tmp[tot++] = '#';
    for (int i = 1; i <= len; i++) {
        tmp[tot++] = s[i];
        tmp[tot++] = '#';
    }
    len = tot;
    int mx = 0, id = 0;
    for (int i = 1; i < len; i++)
    {
        p[i] = mx > i ? min(mx - i, p[2 * id - i]) : 1;
        while (tmp[i + p[i]] == tmp[i - p[i]]) p[i] ++;
        if (i + p[i] > mx) {
            mx = p[i]+i;
            id = i;
        }
    }
    int st = 1;
    ll ans = 0;
    for (int i = 2; i < len-1; i++)
    {
        int L = i/2-p[i]/2 + 1;
        for (int j = 0; j < 26; j++)
        {
            if (a[st][j] >= L)
            {
                ans += a[st][j] - L + 1;
            }
        }
        if (tmp[i] == '#') st++;
    }
    printf("%lld\n", ans);
}

int main() {

    scanf("%s", s + 1);
    int len = strlen(s + 1);
    for (int i = 0; i < 26; i++)
        aa[i] = -1;
    for (int i = 1; i <= len; i++) {
        aa[s[i] - 'a'] = i;
        for (int j = 0; j < 26; j++)
            a[i][j] = aa[j];
    }
    manacher();
    return 0;
}

M. Longest subsequence

$a[i][j]$预处理$i$后面大于等于$j$字符最近的位置。
基于这样的一种贪心过程，选取$x$个字符与$t$串的前$x$字符相同，然后再选取一个字符大于$t$串的第$x+1$个字符，所以要贪心寻找的最近位置,还有就是最后要有个地方要注意，如果两个串前几个字符相同，退出时还要计算一次