本次比赛题解:戳这里 ——> 题解

写在前面

T1 复读数组

题目传送门:复读数组

题目描述

复读数组

分析

计算每个位置对答案的贡献(相当于求包含一个点的区间的个数)。为了防止重算漏算,我们只计算区间中第一次出现这个值的位置的贡献,这需要我们预先求出每个数的前一个出现的位置。

对于重复的部分,完全被包含于原始数组的区间会重复k次,而跨了两个区间的长度小于n的区间会重复k-1次。

对于跨区间,且长度大于等于n的区间,答案是固定的,且对于区间起点的区间个数是等差数列,直接等差数列求和得到

我的代码保留了暴力程序

代码

/******************
User:fxyly
Language:c++
Problem:
Algorithm;
******************/
#include<bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;
const int inv2 = 5e8 + 4;

long long n,k,cnt;
long long a[maxn],tmp[maxn];
long long t[maxn],pre[maxn],pos[maxn],suc[maxn];
long long size[maxn];
bool vis[maxn];
long long ans = 0;

template<class T>inline void read(T &x){
    x = 0;char ch = getchar();bool flag = 0;
    while(!isdigit(ch)) flag |= ch == '-',ch = getchar();
    while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48),ch = getchar();
    if(flag) x = -x;
}

template<class T>void putch(const T x){if(x > 9) putch(x / 10);putchar(x % 10 | 48);}
template<class T>void put(const T x){if(x < 0) putchar('-'),putch(-x);else putch(x);}

void readdata(){
    read(n);read(k);
    for(int i = 1;i <= n; ++ i) read(a[i]),tmp[i] = a[i];
    sort(tmp + 1,tmp + n + 1);
    cnt = unique(tmp + 1,tmp + n + 1) - (tmp + 1);
    for(int i = 1;i <= n; ++ i){
        a[i] = lower_bound(tmp + 1,tmp + cnt + 1,a[i]) - tmp;
        a[i + n] = a[i];
    }
}

void work(){//n<=1000 暴力程序,我决定保留 
    memset(t,0,sizeof(t));memset(size,0,sizeof(size));
    //size是桶,t是答案 
    long long ans1 = 0;
    for(int i = 1;i <= n; ++ i){//计算一个区间内的情况,会重复k次 
        for(int j = i;j <= n; ++ j){
            if(!size[a[j]]) t[j] = t[j - 1] + 1;
            else t[j] = t[j - 1];
            size[a[j]]++;ans += t[j];
        }
        for(int j = i;j <= n; ++ j) t[j] = 0,size[a[j]] = 0;
    }
    if(k == 1) {
        put(ans);return;
    }
    memset(t,0,sizeof(t));memset(size,0,sizeof(size));
    for(int i = 1;i <= n; ++ i){//计算跨两个区间的情况,会重复k-1次 
        for(int j = i;j < n + i; ++ j){
            if(!size[a[j]]) t[j] = t[j - 1] + 1;
            else t[j] = t[j - 1];
            size[a[j]]++;
            if(j >= n + 1) ans1 += t[j];
        }
        for(int j = i;j < n + i; ++ j) t[j] = 0,size[a[j]] = 0;
    }

    ans1 = ans1 * (k - 1) % mod;
    ans = (ans * k % mod + ans1) % mod;
    //当区间长度大于n时,答案是固定的,直接算,区间个数等差数列 
    ans1 = cnt * (1 + k * n % mod - n + mod) % mod * (k * n % mod - n + mod) %mod * inv2%mod;
    ans = (ans + ans1) % mod;
    put(ans);
}

void work1(){//zhengjie ,计算每个数的贡献 

    for(int i = 1;i <= (n<<1); ++ i){pre[i] = pos[a[i]];pos[a[i]] = i;}

    for(int i = 1;i <= n; ++ i)//只有当这个数是区间里第一次出现的,才算它的贡献 
        ans = (ans + (i - pre[i]) * (n - i + 1) % mod) % mod;

    long long ans1 = 0;
    for(int i = 1;i <= n; ++ i) 
        ans1 = (ans1 + (pre[i] + i - 1) * (i - pre[i]) % mod * inv2 % mod) % mod;

    for(int i = n+1;i <= (n << 1); ++ i) {
        if(pre[i] <= n) ans1 = (ans1 + (n * 3 - 2 * i + pre[i] + 1) * (n - pre[i]) % mod * inv2 % mod) % mod;
    }

    ans1 = ans1 * (k - 1) % mod;
    ans = (ans * k % mod + ans1) % mod;
    //当区间长度大于n时,答案是固定的,直接算,区间个数等差数列 
    ans1 = cnt * (1 + k * n % mod - n + mod) % mod * (k * n % mod - n + mod) %mod * inv2%mod;
    ans = (ans + ans1) % mod;
    put(ans);
}

int main(){
//    freopen("a.in","r",stdin);
    readdata();
    if(n <= 1000) work1();
    else work1();
    return 0;
}

T2 路径计数机

题目传送门:路径计数机

题目描述

图片说明

分析

链条不相交的路径的条件:对于其中的一条,另一条的lca与之不等且两条路径都不经过另一条路径的lca与fa[lca]的边。

用树形DP维护以点i为LCA的路径数,经过i及fa[i]这条边的路径数(乘法原理)

代码

/******************
User:fxyly
Language:c++
Problem:
Algorithm: 
******************/

#include<bits/stdc++.h>

using namespace std;

const int maxn = 3005;

int p,q,n,size,first[maxn];
int ind[maxn],vis[maxn];
long long fp[maxn],fq[maxn],gp[maxn],gq[maxn];
long long f[maxn][maxn],g[maxn][maxn];
//f[i][j] - i的子树中与i距离为j的路径的个数 ,g[i][j] -  不在i的子树中与i距离为j的路径的个数
//fp[i]/fq[i] - i的子树以i为lca的长为p/q的路径的条数 
//gp[i]/gq[i] - 经过i与其父亲的连边的长为p/q的路径的条数 
bool judge = 1;
struct Edge{
    int v,nt;
}edge[maxn << 1];

template<class T>inline void read(T &x){
    x = 0;char ch = getchar();bool flag = 0;
    while(!isdigit(ch)) flag |= ch == '-',ch = getchar();
    while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48),ch = getchar();
    if(flag) x = -x;
}

template<class T>void putch(const T x){if(x > 9) putch(x / 10);putchar(x % 10 | 48);}
template<class T>void put(const T x){if(x < 0) putchar('-'),putch(-x);else putch(x);}

void eadd(int u,int v){edge[ ++ size].v = v;edge[size].nt = first[u];first[u] = size;}

void readdata(){
    read(n);read(p);read(q);
    for(int i = 1;i < n; ++ i){
        int u,v;read(u);read(v);
        eadd(u,v);eadd(v,u);ind[u]++,ind[v]++;
        if(ind[u] > 2 || ind[v] > 2) judge = 0;
    }
}

void work(){//lian
    int root = 0;
    long long ans = 0;
    for(int i = 1;i <= n; ++ i){
        int j = i + p + 1;
        if(j <= n - q) ans = ans + (n - q - j + 1);
        else break;
    }
    for(int i = 1;i <= n; ++ i){
        int j = i + q + 1;
        if(j <= n - p) ans = ans + (n - p - j + 1);
        else break;
    }
    ans = ans * 4;
    put(ans);
}

void dfs1(int u,int fa){
    f[u][0] = 1;
    for(int i = first[u];i;i = edge[i].nt){
        int v = edge[i].v;if(v == fa) continue;
        dfs1(v,u);
        for(int j = 0;j < p; ++ j) fp[u] += f[u][j] * f[v][p - j - 1];
        for(int j = 0;j < q; ++ j) fq[u] += f[u][j] * f[v][q - j - 1];
        for(int j = 1;j <= max(p,q); ++ j) f[u][j] += f[v][j - 1];
    }
}

void dfs2(int u,int fa){
    for(int i = 0;i <= p; ++ i) gp[u] += f[u][i] * g[u][p - i];
    for(int i = 0;i <= q; ++ i) gq[u] += f[u][i] * g[u][q - i];
    for(int i = first[u];i;i = edge[i].nt){
        int v = edge[i].v;if(v == fa) continue;
        g[v][1] = 1;
        for(int j = 2;j <= max(p,q); ++ j) g[v][j] += f[u][j - 1] - f[v][j - 2] + g[u][j - 1];
        dfs2(v,u);
    }
}

void work2(){

    dfs1(1,0);dfs2(1,0);

    long long ans = 0,ansp = 0,ansq = 0;

    for(int i = 1;i <= n; ++ i)
        ansp += fp[i],ansq += fq[i];

    ans = ansp * ansq;

    for(int i = 1;i <= n; ++ i)
        ans -= (fp[i] * gq[i] + fq[i] * gp[i] + fp[i] * fq[i]);

    put(ans << 2);
}

int main(){
//    freopen("b.in","r",stdin);
    readdata();
    if(judge) work();
    else work2();
    return 0;
}

T3 排列计数机

题目传送门:排列计数机

题目描述

图片说明

分析

我……现在只会部分分,日后再来填坑
注意子序列不是子串