牛客CSP-S提高组赛前集训营4解题报告
本次比赛题解：戳这里 ——> 题解
写在前面
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 排列计数机
题目传送门：排列计数机
题目描述
分析
我……现在只会部分分，日后再来填坑
注意子序列不是子串
投递长鑫存储等公司10个岗位 >