2024CCPC深圳站组队赛题解

A:一道好题

Description

一道好题应该有一个简洁的题面。

有一个长度为 n，初始全为 0 的序列 a，另有一个长度为 n 的序列 b，你希望将 a 变成 b，你可以执行如下两种操作：

1 x：将 a 中所有值为 x 的数 +1。

2 x：将 a 中下标为 x 的数 +1。

你不需要最小化操作次数，但只能使用最多 20000 次操作。

Input

第一行一个正整数 n（1≤n≤1000）。

第二行 n 个非负整数 b1,⋯,bn（0≤bi≤n）描述序列 b。

Output

第一行一个整数 k 表示操作次数，你需要保证 0≤k≤20000。

之后 k 行每行两个整数 1 x 或 2 x，表示一次操作。对于 1 x 类型的操作，你需要保证 0≤x≤n，对于 2 x 类型的操作，你需要保证 1≤x≤n。

分析：

第一次做的时候 各种贪心，分块超次数了。

首先看到操作次数 $20000>=n*logn$ ，所以可以大约往出来算法运行次数为 $nlogn$ 级别的考虑。

考虑分治。在一段 $1-n$ 的区间中，把 $[(n+1)/2,n]$ 的先依次加一,这样整体就分成了不同两部分，在运用第一种操作整体加一。

具体细节看代码$merge$函数：

int n, a[N], c[N];
PII b[N];
vector<array<int, 2>> op;
void merge(int l, int r, int val)//val：此时整个区间的值
{
	if (b[r].f == val)
		return;
	int mid = l + r + 1 >> 1, now = val;
	if (b[mid].f > val)
	{
		for (int i = mid; i <= r; i++)
		{
			op.pb({2, b[i].s});
		}
		now++;
	}
	while (now < b[mid].f)//让整个右区间的值变成mid
		op.pb({1, now}), now++;
	if (b[r].f > now)
		merge(mid, r, now);
	merge(l, mid - 1, val);
}
void solve()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	cin >> a[i], b[i] = {a[i], i};

	sort(b + 1, b + 1 + n);
	merge(1, n, 0);

	cout << op.size() << "\n";
	for (auto &[x, y] : op)
	cout << x << " " << y << "\n";
}

F:见面礼

Description

给定一个 n 个点 n 条边的无向图，你需要求有多少种选择图上的一个点 p 和一条边 (x,y) 的方案，使得删去 (x,y) 后图变成一棵树，且这棵树以 p 为根时每个节点的儿子个数均不超过 3。保证至少存在一种这样的方案。

Input

输入的第一行一个整数 n（2≤n≤105） 表示节点数，接下来 n 行每行两个整数 x,y（1≤x,y≤n） 描述图上的一条边。保证图中没有重边自环。

Output

输出一行一个正整数表示答案。

分析：

队友写的，应该是个结论题。

粘一下官方题解：

由于保证存在一个方案，所以给出的图一定是一棵基环树。找到 基环树的环后，删去的边一定在环上。 枚举被删去的边（也就是环上的边），我们需要快速地确定选根 的方案数。 考虑一个点作为根的条件。注意到每个点的儿子个数不超过3的 充要条件是：根的度数不超过3，其余节点的度数不超过4。 于是维护每种度数的出现次数（注意到保证有解时，所有节点的 度数均不会超过5），删边时修改相邻的两个节点的度数。当不 存在度数为5的节点时，选根的方案数即为度数不超过3的节 点个数，否则不存在选根的方案。

int T, n, m;
vector<int>v[N];
int p[N], ff = 0, q[N], cnt = 0;
bool st[N];

void dfs(int u, int f)
{
    for(int it : v[u])
    {
        if(it == f) continue;
        if(ff) return;
        p[it] = u;
        // cout << it << '\n';
        if(st[it])
        {
            // cout << " ---" << it << '\n';
            int x = it;
            while(p[x] != it && p[x] != 0)
            {
                q[++ cnt] = p[x];
                x = p[x];
            }
            q[++ cnt] = p[x];
            // for(int i = 1; i <= cnt; i ++)
            // {
            //     cout << q[i] <<" \n"[i == cnt];
            // }
            ff = 1;
            return;
        }
        st[it] = true;
        dfs(it, u);
        if(ff) return;
    }
}
int num[N];

void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        int x, y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
        num[x] ++;
        num[y] ++;
    }
    dfs(1, 0);
    q[cnt + 1] = q[1];
    int cnt1 = 0, cnt2 = 0;
    for(int i = 1; i <= n; i ++)
    {
        if(num[i] == 5) cnt1 ++;
        if(num[i] == 4) cnt2 ++;
    }
    int ans = 0;
    for(int i = 1; i <= cnt; i ++)
    {
        int t1 = q[i], t2 = q[i + 1];
        int n1 = 0, n2 = 0;
        if(num[t1] == 5) n1 ++, n2 --;
        if(num[t1] == 4) n2 ++;
        if(num[t2] == 5) n1 ++, n2 --;
        if(num[t2] == 4) n2 ++;
        if(cnt1 - n1 != 0) continue;
        ans += n - (cnt2 - n2);
    }
    cout << ans << '\n';
}

G:相似基因序列问题

【题目描述】

已知一棵包含了 N 个生物的系统进化树，这些生物的 DNA 序列对应的对齐至 M 个片段的序列可以用仅含小写字母的字符串表示为 s1,…,sN。在这棵系统进化树上，如果两个生物对应的序列最多只有 K 处对应位置上的片段不相同（即对应字母不同），就称这两个生物的亲缘关系相近。

现有 Q 个尚未确定亲缘关系的生物，对齐得到序列分别为 t1,…,tQ。为了确定这些生物在系统进化树上的位置，请对 Q 个生物分别求出，原树中有多少个生物与其亲缘关系相近。

Input

输入的第一行包含四个正整数 N,Q,M,K，分别表示系统进化树上的生物数量、待确定亲缘关系的生物数量、对齐后的序列长度和比较序列时容许的最大差异数。保证 1≤N,Q≤300，1≤M≤60,000，1≤K≤10。

接下来 N 行，每行输入一个长度恰好为 M，仅包含小写字母的字符串 si，表示系统进化树上的每个生物对应的模板序列。

接下来 Q 行，每行输入一个长度恰好为 M，仅包含小写字母的字符串 tj，表示待确定亲缘关系的每个生物对应的查询序列。

保证输入的两个字符串均仅包含小写字母。

Output

输出共 Q 行，其中第 j 行输出一个非负整数，表示在系统进化树上与第 j 个待确定的生物亲缘关系相近的生物数量。

分析：

队友写的二分+hash。

中途我怕被卡hash跟他们说写双hash，mle了，改完单hash又tle一发 ，二分提前break过的。

int q, k, T, n, m;
string s[N], c[N];
const int mod = 1e9 + 13, mod2 = 1e9 + 17;
const int P = 131, P2 = 13331;
int h[N][M], hc[N][M], p[M];
// int h2[N][M], hc2[N][M], p2[M];


int check(int l, int r, int t1, int t2)
{
    int x1 = (hc[t1][r] - hc[t1][l - 1] * p[r - l + 1] % mod + mod) % mod;
    int x2 = (h[t2][r] - h[t2][l - 1] * p[r - l + 1] % mod + mod) % mod;

    // int y1 = (hc2[t1][r] - hc2[t1][l - 1] * p2[r - l + 1] % mod2 + mod2) % mod2;
    // int y2 = (h2[t2][r] - h2[t2][l - 1] * p2[r - l + 1] % mod2 + mod2) % mod2;
    
    if(x1 == x2) return true;
    return false;
}

void solve()
{
    cin >> n >> q >> m >> k;
    p[0] = 1;
    // p2[0] = 1;
    for(int i = 1; i <= m; i ++)
    {
        p[i] = p[i - 1] * P % mod;
        // p2[i] = p2[i - 1] * P2 % mod2;
    }
    for(int i = 1; i <= n; i ++)
    {
        cin >> s[i];
        int z = s[i].size();
        s[i] = ' ' + s[i];
        for(int j = 1; j <= z; j ++)
        {
            h[i][j] = (h[i][j - 1] * P % mod + s[i][j]) % mod;
            // h2[i][j] = (h2[i][j - 1] * P2 % mod2 + s[i][j]) % mod2;
        }
    }
    for(int i = 1; i <= q; i ++)
    {
        cin >> c[i];
        int z = c[i].size();
        c[i] = ' ' + c[i];
        for(int j = 1; j <= z; j ++)
        {
            hc[i][j] = (hc[i][j - 1] * P % mod + c[i][j]) % mod;
            // hc2[i][j] = (hc2[i][j - 1] * P2 % mod2 + c[i][j]) % mod2;
        }
        int ans = 0;
        for(int j = 1; j <= n; j ++)
        {
            int lr = 1, cnt = 0;
            while(lr <= m)
            {
                int l = lr, r = m;
                while(l < r)
                {
                    int mid = l + r >> 1;
                    if(check(l, mid, i, j)) l = mid + 1;
                    else r = mid; 
                }
                if(c[i][l] != s[j][l])
                {
                    cnt ++;
                }
                lr = l + 1;
                if(cnt > k) break;
            }
            if(cnt <= k) ans ++;
        }
        cout << ans << '\n';
    }
}

Description

【题目描述】

出生于魔王家族的 Mary，从小便与同龄的普通人类有所不同。比如说，Mary 的头两侧长有一对犄角，可以捕捉到远处细微的变化；比如说，Mary 身上的魔力会吸引神秘的生物，这些友善的来客自在地游曳在魔王城中，将其点缀成了一座坐落于偏僻孤岛上的水族馆；再比如，Mary 有一棵与生俱来的有根树。

Mary 有棵有根树。

在 Mary 出生时，这棵有根树也一同降临在了世界上。照料好自己的有根树是魔王家族世世代代的传承，但让有根树生长的方法却因人而异。Mary 不知道如何让这棵只有一个结点的有根树生长，而她的父母也不得而知。虽然 Mary 的有根树从未生长，但是 Mary 像普通人类一样不断成长，她所能驾驭的魔力也随之越来越强。Mary 的成长获得了父母的认可，他们将魔王家族中象征着力量成熟的魔法——闪耀魔法传授给了 Mary。当 Mary 第一次成功施展了闪耀魔法时，她的有根树终于产生了变化：从原来的根结点上，长出了 M 个新的结点。原来，每当 Mary 施展一次闪耀魔法时，她的有根树都会有一个叶结点恰好长出 M 个可以区分的子结点。每次进行生长的叶结点是在所有尚未生长的叶结点中等概率随机产生的，而已经拥有 M 个子结点的非叶结点不会再次生长。

Mary 想知道：在她总共使用了 K 次闪耀魔法之后，她的有根树上各个结点的深度总和的期望。最初没有使用闪耀魔法时，只有一个结点的有根树的深度定义为 0。

Input

输入仅一行，包括两个由单个空格隔开的正整数 M，K，表示从一个结点上可以长出的子结点的数量，以及使用闪耀魔法的次数。保证 1≤M≤100，1≤K≤107。

Output

输出一个数，表示 Mary 的有根树的结点深度和的期望。假设期望深度和化为最简分式后的形式为 p/q（即其中 p,q 互质），请输出非负整数 x 使得 qx≡p(mod1,000,000,009)，且 0≤x<1,000,000,009。可以证明，在本题数据范围下，x 存在且唯一。

分析：

设$f_1$表示叶子节点深度的全部期望，$f_2$表示非叶子节点深度的全部期望。

在进行一次闪耀魔法时：

全部叶子的节点数量:$sz_i=sz_{i-1}+m-1$

一个叶子节点的期望深度:d=$\frac{f_1}{sz_i}$

显然会有一个叶子节点变为非叶子节点：$f_2+=d$

新的叶子节点一定是上一次的叶子节点期望深度+1：$f_1+=(d+1)*m-d$

那么对于最终的答案就是$f_1+f_2$.

int f1[N],f2[N];
int qmi(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=res*a%P;
        a=a*a%P;
        b>>=1;
    }
    return res;
}
void solve(){
    int m,k;cin>>m>>k;
    for(int i=1,sum=1;i<=k;i++,sum+=m-1,sum%=P){
        int ver=f1[i-1]*qmi(sum,P-2)%P;
        f2[i]=f2[i-1]+ver;
        f2[i]%=P;
        f1[i]=(f1[i-1]+(ver+1)*m%P-ver+P)%P;
    }
    cout<<(f1[k]+f2[k])%P<<"\n";
}

I：不定方程

Description

给定正整数 n,k，求不定方程 $a^k−b^k=n$ 的正整数解数量。

Input

输入第一行一个整数 T（1≤T≤20） 表示询问数量。之后 T 行，每一行两个整数 n,k 表示一次询问。保证 1≤n≤1018，3≤k≤64。

Output

对于每一组询问，输出一行一个非负整数表示答案。

分析：

正解：

偏解：

$a^k-b^k=(a-b)(a^{k-1}+a^{k-2}b+...b^{k-1}=n$

设$c=(a-b),a=b+c$ 带入原式：$(b+c)^k-b^k$

首先通过第一行可以看出（a-b）是n的质因子，其次$(b+c)^k-b^k$ 显然单调递增

所以我们可以枚举n的因子，然后二分答案寻找b

由于n很大我们可以用$Pollard-Rho$在$n^{\frac{1}{4}}$枚举单个因子 ，带回除掉再找其他的因子。