蓝书 1.1 问题求解策略 习题题解

总表

刘汝佳，陈锋《算法竞赛入门经典训练指南》第 1 章——算法设计基础

更新中……

题号	题目名称（点击跳转题解）	备注
UVA 11636	Hello World!	递推
UVA 11039	Building Designing	贪心
UVA 1368	DNA Consensus String	贪心
UVA 10970	Big Chocolate	模拟，公式
UVA 10382	Watering Grass	贪心，区间覆盖
UVA 10905	Children’s Game	贪心
UVA 1422	Processor	二分答案，贪心
UVA 11627	*Slalom	暂缺
UVA 11100	The Trip, 2007	贪心
UVA 1450	Airport	二分答案
UVA 1467	*Installation	暂缺
UVA 1344	Tian Ji – The Horse Racing	贪心
UVA 11389	The Bus Driver Problem	贪心
UVA 1418	*WonderTeam	暂缺
UVA 1445	Cubist Artwork	模拟，贪心
UVA 1377	*Ruler	暂缺
LA 5704	*Yummy Triangular Pizza	暂缺
UVA 10825	*Anagram and Multiplication	暂缺
UVA 1508	Equipment	状压，搜索
UVA 1509	Leet	搜索，枚举
UVA 1346	*Songs	暂缺
LA 7607	*Power Supply	暂缺
CF Gym 101667A	*Broadcast Stations	暂缺
LA 6901	*String Transformation	暂缺
-	*Moving Building	暂缺
LA 7269	*Snake Carpet	暂缺
CF 1089M	*Minegraphed	暂缺
CF Gym 101630D	*Designing the Toy	暂缺
LA 7140	*Seat Arrangement	暂缺

Hello World!

简要题意

你希望输出 $n$ 条 Hello World! 信息。一开始你只有 $1$ 条。你希望通过复制粘贴来解决。至少需要复制粘贴几次，才能使语句的条数变为 $n$ ？（ $0<n<10001$ ）

解法

设 $f(n)$ 代表 $n$ 条语句需要复制粘贴几次。初始条件 $f(1)=0$ ，可以很方便的写出递推式 $f(n)=f(\lceil n/2 \rceil ) +1$ 。

即要 $n$ 条语句，先获得 $\lceil n/2 \rceil$ 条，然后复制其中的 $\lfloor n/2 \rfloor$ 条即可。（可以证明，这是最优的方案）

代码

#include<bits/stdc++.h>
using namespace std;

const int N = 10005;
int f[N];

int main(){
    for(int i=2;i<N;i++){
        f[i]=f[(i+1)/2]+1;
    }

    int x,kase=1;
    while(scanf("%d",&x)){
        if(x<0)break;
        printf("Case %d: %d\n",kase++,f[x]);
    }
    return 0;
}

Building Designing

简要题意

有 $n$ 个绝对值各不相同的非 $0$ 整数，选出尽量多的数，排成一个序列，使得正负交替，且绝对值递增（排成的序列可以重新排序，不用保持相对关系）。求最长序列长度 （ $n<5\times 10 ^ 5$ ）

题解

注意排序列可以重新排序。我们不妨先把原序列按照绝对值排序，然后贪心，能选的尽量选，如果这个数的符号和前面重复，就跳过它。

代码

#include <bits/stdc++.h>
using namespace std;

bool cmp(int a,int b){
    return abs(a)<abs(b);
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n;
        scanf("%d",&n);
        vector<int> a;
        for(int i=0;i<n;i++){
            int x;
            scanf("%d",&x);
            a.push_back(x);
        }
        sort(a.begin(), a.end(),cmp);
        int now = (a[0]>0)?0:1;
        int ans = 0;
        for(int i=0;i<n;i++){
            if(now==0 && a[i]>0){
                ans++;
                now=1;
            }
            else if(now==1 && a[i]<0){
                ans++;
                now=0;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

DNA Consensus String

简要题意

输入 $m$ 个长度均为 $n$ 的 $\text{DNA}$ 序列，求一个 $\text{DNA}$ 序列，到所有序列的总 Hamming 距离尽量小。两个等长字符串的 Hamming 距离等于字符不同的位置个数，如 $\texttt{ACGT}$ 和 $\texttt{GCGA}$ 的 Hamming 距离为 $2$ （左数第 $1$ 、 $4$ 个字符不同）。

输入整数 $m$ 和 $n$ （ $4\leq m \leq 50$ ， $4\leq n \leq 1000$ ），以及 $m$ 个长度为 $n$ 的 $\text{DNA}$ 序列，（只包含字母 $\texttt A$ 、 $\texttt C$ 、 $\texttt G$ 、 $\texttt T$ ），输出到 $m$ 个序列的 Hamming 距离和最小的 $\text{DNA}$ 序列和对应的距离。如有多解，要求字典序最小的解。

解法

考虑贪心。对于每一位，优先选出现次数多的字符，如果有多个出现次数相同的，优先选字典序较小的。（下面代码中用一个 pair<int,int> 的完成了两个关键字的排序）

代码

#include <bits/stdc++.h>
using namespace std;

char dat[55][1005];

char mp[]="TGCA";

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m;
        scanf("%d%d",&n,&m);
        memset(dat,0,sizeof(dat));
        for(int i=0;i<n;i++){
            scanf("%s",dat[i]);
        }
        int ans = 0;
        for(int i=0;i<m;i++){
            vector<pair<int,int>> v;
            for(int j=0;j<4;j++)v.push_back({0,j});
            for(int j=0;j<n;j++){
                if(dat[j][i]=='T')v[0].first++;
                if(dat[j][i]=='G')v[1].first++;
                if(dat[j][i]=='C')v[2].first++;
                if(dat[j][i]=='A')v[3].first++;
            }
            sort(v.begin(), v.end(),greater<pair<int,int>>());    
            putchar(mp[v[0].second]);
            ans += n-v[0].first;
        }        
        printf("\n%d\n",ans);
    }
    return 0;
}

Big Chocolate

简要题意

求把一块 $m \times n$ 的巧克力切成 $mn$ 块 $1 \times 1$ 的巧克力，最少需要几刀？（$1 \le m,n \le 300$）
每刀只能沿着直线把一块巧克力切成两部分。

解法

每切一刀一定增加且仅增加一块巧克力。一开始有 $1$ 块，最后有 $nm$ 块，所以总共要切 $(nm-1)$ 刀。

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    int x,y;
    while(scanf("%d%d",&x,&y)==2){
        printf("%d\n",x*y-1);
    }
    return 0;
}

Watering Grass

简要题意

长 $L$ 米，宽 $W$ 米的草坪里装有 $n$ 个浇灌喷头。每个喷头都装在草坪中心线上（离两边各 $\dfrac{W}{2}$ 米）。我们知道每个喷头的位置（离草坪中心线左端的距离），以及它能覆盖到的浇灌范围。请问：如果要同时浇灌整块草坪，最少需要打开多少个喷头？

解法

首先，一个喷头的有效区域是一个矩形，可看作一个区间。具体来说，对于一个位置在 $d$，半径为 $r$ 的喷头：

1. $r\le\dfrac{W}{2}$：此时该喷头无效。
2. $r>\dfrac{W}{2}$：此时该喷头的有效范围为

$$\left[d-\sqrt{r^2-\left(\dfrac{W}{2}\right)^2},d+\sqrt{r^2-\left(\dfrac{W}{2}\right)^2}\right]$$

然后对这个区间可以用贪心法，求出覆盖一个线段的最小区间数。先按区间起点排序，然后对于起点小于目前到达的位置的所有区间，选择终点最远的区间。可以证明这样就是最优取法。

代码

#include <bits/stdc++.h>
using namespace std;

int n, L, W;

bool solve() {
    vector<pair<double, double>> range;
    if(scanf("%d%d%d", &n, &L, &W)!=3)return 0;

    for (int i = 0; i < n; i++) {
        int a, r;
        scanf("%d%d", &a, &r);

        if ((double)r <= (double)W / 2)continue;

        double h = sqrt(pow(double(r), 2) - pow(W / 2., 2));
        range.push_back({fmax(0., a - h), a + h});
    }

    sort(range.begin(), range.end());
    n = range.size();

    if(n==0){
        puts("-1");
        return 1;
    }

    double now = 0;
    int i = 0;
    int ans = 0;

    while (now < L) {
        double to = -1;
        for (; range[i].first <= now && i < range.size(); i++) {
            to = max(to, range[i].second);
        }
        if (to == -1) {
            puts("-1");
            return 1;
        }
        now = to;
        ans++;
    }
    printf("%d\n", ans);
    return 1;
}

int main() {
    while(solve());
}

Children’s Game

简要题意

给定 $n$ 个数字，求将他们一个一个接起来后形成的整数的最大值。

解法

考虑贪心。显然最高位应该放比较大的位，首先会想到按字典序排序，但这是不对的。

举例：$321$ 和 $3$ 的字典序 $321 > 3$，按字典序排序得到的是 $3213$，但正确的是 $3321$。

为此，我们可以直接比较两个字符串前后拼接的字典序大小作为排序关键字。

代码

#include <bits/stdc++.h>
using namespace std;

bool cmp(string a, string b) {
    return a + b > b + a;
}

int main() {
    while(1){
        vector<string> v;
        string s;
        int n;
        cin >> n;
        if(n==0)break;
        int i;
        for (i = 0; i < n; i++) {
            cin >> s;
            v.push_back(s);
        }
        sort(v.begin(), v.end(), cmp);
        for (i = 0; i < n; i++) {
            cout << v[i];
        }
        puts("");
    }
    return 0;
}

Processor

简要题意

这个处理器需要执行一系列的程序。对于每一个程序 $P_i$ 都有三个正整数参数：开始时间 $r_i$ ,最后完成期限 $d_i$ 以及 工作量 $w_i$。处理器在处理程序时，每个程序的所有工作量都必须在时间段 $[ri,di]$ 内完成。同时，处理器也不必在连续时间内处理统一项程序，也就是说，处理器可以随时打断正在处理的程序或者从被打断的地方继续处理一项之前被打断的程序，但是不能同时处理两个或者更多程序。由于处理器的处理速度是可变化的，所以如果它以速度 $s$ 处理一项工作量为 $w_i$ 的程序 $P_i$，那么要花费时间 $w_i/s$ 就可以处理完程序 $P_i$. 在这里，处理的速度 $s$ 无论在何时都是一个整数。求处理器速度完成全部任务的最大值的最小值。

解法

考虑二分答案。接下来就是考虑贪心策略。正确的策略是：优先做截止时间比较靠前的任务。为此，我们建立一个堆，维护当前所有能做的任务，在每一秒都不断从堆中取出任务，直到这一秒的工作量达到处理速度 $s$。

代码

#include <bits/stdc++.h>
using namespace std;


struct Node{
    int l,r,w;
    bool operator<(const Node& rhs)const{
        return r>rhs.r; // 堆里面优先选右端点小的任务
    }
};

Node a[10005];
int n;

bool cmp(const Node& a,const Node& b){
    return a.l<b.l; // 按照左端点排序
}

bool check(int v){
    priority_queue<Node> q;
    int now=0;
    for(int i=1;i<20000;i++){
        while(now<n && a[now].l <= i){ // 这个任务开始了
            q.push({a[now].l,a[now].r,a[now].w});
            now++;
        }

        if(q.empty())continue;

        int left = v; // 这个时间里面还能做 left 的工作量
        while(q.size() && left>0){
            if(q.top().r<=i)return 0; // 这个任务已经来不及了，失败

            auto work = q.top();q.pop();
            if(work.w > left){
                work.w-=left;left=0;
                q.push(work);
            }
            else left-=work.w;
        }
    }
    return q.empty(); // 如果还有任务剩下来，那么失败
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].w);
        }
        sort(a,a+n,cmp);
        
        int l = 1,r=1e9;
        while(l<r){
            int mid = (l+r)>>1;
            if(check(mid))r=mid;
            else l=mid+1;
        }
        printf("%d\n",l);
    }
    return 0;
}

The Trip, 2007

简要题意

给出 $n\ (1\le n\le 10\ 000)$ 个正整数，把它们划分成尽量少的严格递增序列 （顺序可以改变），在保证序列数最小的前提下，要求序列长度的最大值最小。输出序列个数的最小值 $k$ 和这些序列。

解法

不难发现需要的严格递增序列数量就是同一正整数的最多出现次数。对于不同的正整数，一定可以从小到大把它们全部放在一个序列里面。而一样的正整数一个序列只能出现一次。

此时序列长度的最大值就是 $\lceil n/k \rceil$。接下来考虑构造这个序列。我们用优先队列维护还剩下的数和其出现次数。对于每个序列，从出现次数最大的开始选 $\lceil n/k \rceil$ 个数，不断重复 $k$ 次得到的就是一个合法的序列。

比如有 $3$ 个 $1$，$4$ 个 $6$，$1$ 个 $8$。则需要 $4$ 个序列。
分别为 $\{1,6\}$，$\{1,6\}$，$\{1,6\}$，$\{6,8\}$。

复杂度 $O(n \log n)$。（使用了优先队列和 set）

代码

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+4;
int cnt[N];

struct Node{
    int x,cnt;
    bool operator<(const Node& a)const{
        return cnt<a.cnt;
    }
};

int main(){
    int n;bool ok=0;
    while(scanf("%d",&n)){
        if(n==0)break;
        if(ok)puts("");ok=1;

        memset(cnt,0,sizeof(cnt));

        int ans = 0;
        for(int i=0;i<n;i++){
            int x;scanf("%d",&x);
            ans=max(ans,++cnt[x]);
        }
        printf("%d\n",ans);

        int max_cnt = (n/ans) + (n%ans==0?0:1);
        
        priority_queue<Node> q;
        for(int i=0;i<N;i++){
            if(cnt[i])q.push({i,cnt[i]});
        }

        for(int i=0;i<ans;i++){
            set<int> seq; // 答案，用 set 自动排序
            vector<Node> back; // 要放回优先队列里的 Node

            for(int j=0;j<max_cnt;j++){
                if(q.empty())break;
                auto x=q.top();q.pop();
                x.cnt--;
                seq.insert(x.x);
                if(x.cnt)back.push_back(x);
            }

            for(auto nd:back)q.push(nd);

            for(auto it=seq.begin();it!=seq.end();it++){
                if(it!=seq.begin())putchar(' ');
                printf("%d",*it);
            }
            puts("");
        }
    }
    return 0;
}

Airport

简要题意

有一个飞机场，它有两个飞机通道 ( $W$ 和 $E$ )，但只有一个起飞跑道。

每个时刻都有一些飞机到达 $W$ 或者 $E$ 通道中，开始等待起飞。任意时刻，飞机的编号为它前面等待起飞的飞机数（$0,1,2,……$）。每个时刻，只能有一架飞机起飞。

你的任务是在每个时刻从 $W$ 或者 $E$ 中选择一架飞机起飞，使得任意时刻飞机的最大编号最小。

解法

显然二分答案。

然后考虑贪心策略，对于每个时刻，我们不好判断这时候应该飞的是哪一边的飞机。那我们不妨把这一次飞飞机的机会留着，直到两边的飞机有一边超过了上限，再考虑能不能把这个飞机飞走。

我们维护目前可以飞的次数，以及两边目前最多可以飞几架飞机，然后在超过的时候进行判断能不能把飞机飞到小于上限。如果做不到，就说明无法达到这个结果。

代码

#include<bits/stdc++.h>
using namespace std;


const int N = 5005;

int a[N],b[N];
int n;

bool check(int x){ // x 代表任何时刻最多有 x 架飞机（不是答案！答案要减一）
    int cnta=0,cntb=0; // 两边的飞机数量
    
    int flyChance=0; // 总共有几次飞飞机的机会
    int maxa=0,maxb=0; // a,b最多可以飞几架
    int tmpa=0,tmpb=0;

    for(int i=0;i<n;i++){
        cnta+=a[i],cntb+=b[i];
        tmpa+=a[i],tmpb+=b[i];
        
        if(!cnta && !cntb)goto cont;

        if(!cnta){
            if(cntb>x)return 0;
            cntb--,maxb--;
        }
        else if(!cntb){
            if(cnta>x)return 0;
            cnta--,maxa--;
        }
        else{
            if(cnta<=x&&cntb<=x){
                flyChance++; // 这次的机会留着以后用
                if(flyChance==cnta+cntb){ // 能清完了
                    flyChance=cnta=cntb=0; // 要直接清零，不然flyChance会多统计
                    maxa=maxb=0;
                }
                goto cont;
            }
            int need = max(cnta-x,0)+max(cntb-x,0);
            
            if(flyChance<need)return 0;
            if(maxa<max(cnta-x,0))return 0; // 如果a飞不出这么多飞机
            if(maxb<max(cntb-x,0))return 0;
            
            cnta=min(cnta,x);
            cntb=min(cntb,x);

            flyChance-=need;flyChance++;
            maxa-=max(cnta-x,0),maxb-=max(cntb-x,0);
        }

        cont:;
        if(tmpa)maxa++,tmpa--; // 统计 a,b 两边最多能飞几架
        if(tmpb)maxb++,tmpb--;
    }
    return 1;
}

int main(){
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d%d",a+i,b+i);
        }

        int l=1,r=1e9;
        while(l<r){
            int m = (l+r)>>1;
            if(check(m))r=m;
            else l=m+1;
        }
        printf("%d\n",l-1);
    }
    return 0;
}

Tian Ji – The Horse Racing

简要题意

田忌和齐王赛马，两人各有 $n$ 匹马，赢一场比赛获得 200 元，输一场比赛失去 200 元，平局不赚不赔。求最大钱数。

解法

考虑排序之后贪心。

正确策略如下：

1. 田忌最强的马可以打赢齐王最强的马，那么用这两匹马对战即可；
2. 田忌最弱的马可以打赢齐王最弱的马，那么用这两匹马对战即可；
3. 否则，用田忌最弱的马消耗掉齐王最强的马。

代码

#include<bits/stdc++.h>
using namespace std;

const int N = 5000;
int a[N],b[N];

int main(){
    int n;
    while(scanf("%d",&n)){
        if(n==0)return 0;

        for(int i=0;i<n;i++)scanf("%d",a+i);
        for(int i=0;i<n;i++)scanf("%d",b+i);

        sort(a,a+n);
        sort(b,b+n);

        int la=0,lb=0, ra=n-1,rb=n-1;
        int ans=0;
        for(int i=0;i<n;i++){
            if(a[ra]>b[rb]){
                ans+=200;
                ra--,rb--;
            }else if(a[la]>b[lb]){
                ans+=200;
                la++,lb++;
            }else{
                if(a[la]<b[rb])ans-=200;
                la++,rb--;
            }
        }

        printf("%d\n",ans);
    }
    return 0;
}

The Bus Driver Problem

简要题意

有 $n$ 个司机，$n$ 个下午路线和 $n$ 个夜间路线。分配路线，使总加班费最少。若一个司机的行驶时间未超过 $d$，则没有加班费，否则加班费按超出部分每小时 $r$ 元计算。

解法

显然让下午路线最长的配夜间路线最长的即可。分别降序和增序排序两个路线，让一个最大的配另一个最小的。

代码

#include<bits/stdc++.h>
using namespace std;

const int N = 105;
int a[N],b[N];

int main(){
    int n,d,r;
    while(scanf("%d%d%d",&n,&d,&r)){
        if(n==0)return 0;
        for(int i=0;i<n;i++)scanf("%d",a+i);
        for(int i=0;i<n;i++)scanf("%d",b+i);

        sort(a,a+n);
        sort(b,b+n,greater<int>());

        int ans=0;
        for(int i=0;i<n;i++){
            int k=a[i]+b[i];
            if(k>d)ans+=(k-d)*r;
        }
        printf("%d\n",ans);
    }
    return 0;
}

Cubist Artwork

简要题意

用一些等大的立方体搭积木，每个立方体或者直接放在地面的网格上，或者放在另一个立方体的上面，给出正视图和侧视图，判断最少要用多少个立方体。

解法

考虑一个 $m$ 行 $n$ 列的矩阵，现在已经知道了每一行每一列的最大值，求最小元素和。
不妨先从列开始考虑。每一列都要放一个最大值，那么放在哪里呢？应该放在一个不会影响行最大值的地方，并且最好能够恰好满足行的最大值。
然后再考虑行，如果这一行已经被满足了，那么跳过，否则，答案还要增加这一行的最大值。

代码

#include<bits/stdc++.h>
using namespace std;

int h1[15],h2[15];
bool satisfied[15];

int main(){
    int m,n;
    while(scanf("%d%d",&m,&n)){
        if(m==0)return 0;

        memset(satisfied,0,sizeof(satisfied));
        for(int i=1;i<=m;i++)scanf("%d",h1+i);
        for(int i=1;i<=n;i++)scanf("%d",h2+i);

        int ans = 0;
        for(int i=1;i<=m;i++){
            ans+=h1[i];
            for(int j=1;j<=n;j++){
                if(!satisfied[j] && h2[j]==h1[i]){
                    satisfied[j]=1;
                    break;
                }
            }
        }
        for(int i=1;i<=n;i++){
            if(!satisfied[i])ans+=h2[i];
        }

        printf("%d\n",ans);
    }
    return 0;
}

Equipment

简要题意

给出 $n$ 个 5 元组，从中选出 $k$ 组，$1\le k \le n \le 10^4$，使得这些组中 5 个位置，每个位置上最大数之和最大，求这个和。

解法

不难发现，当 $k\ge 5$ 时，答案就是所有 $n$ 组里面 5 位每一个的最大值之和。

我们只需要考虑 $k<5$ 的情况。
一个朴素想法是枚举 $C_n^k \approx 10^{17}$，我们考虑怎么优化这个问题。
我们选的 $k$ 个五元组，每个都给答案贡献了某几位。则总共有 $2^5-1=31$ 种贡献的情况。不难发现，贡献某几位的方案是可以贪心选出最大的。
下一步就是找到 $k$ 个贡献方案，它们的并集为全集。为此，可以枚举全集的子集然后搜索。

代码

#include<bits/stdc++.h>
using namespace std;

int maxn[40]; // 这个贡献方案的最大值
int a[10];
int n,k;
int ans;

void dfs(int S,int cnt,int val){
    if(cnt==k){
        ans=max(ans,val);
        return;
    }
    for(int S0=S;S0;S0=(S0-1)&S){
        dfs(S^S0,cnt+1,val+maxn[S0]);
    }
}

int main(){
    int T;scanf("%d",&T);
    while(T--){
        memset(maxn,0,sizeof(maxn));

        scanf("%d%d",&n,&k);
        for(int i=0;i<n;i++){
            for(int i=0;i<5;i++)scanf("%d",a+i);
            
            for(int s=0;s<=31;s++){
                int val = 0;
                for(int j=0;j<5;j++){
                    if(s & (1<<j))val+=a[j];
                }
                maxn[s]=max(maxn[s],val);
            }
        }

        if(k>=5){
            printf("%d\n",maxn[16]+maxn[8]+maxn[4]+maxn[2]+maxn[1]);
            continue;
        }

        ans=0;
        dfs(31,0,0);
        printf("%d\n",ans);
    }
    return 0;
}

Leet

简要题意

有一种网络用语，每个英文字母都可能被唯一替换成长度不超过 k 的串。给出一个小写英文串 A 以及另一个网络用语串 B，询问 B 是否由 A 按照上述规则替换而来的。
$1 \le k \le 3$， $1 \le |A| \le 15$。

解法

根据题意，暴力枚举每个字符可能映射的所有可能组合。复杂度 $O(|A|^k)$。

代码

#include<bits/stdc++.h>
using namespace std;

struct Node{
    int l;
    char s[5];
}mp[50];
char a[100],b[100];

int k;
int la,lb;
bool ok;

void dfs(int ia,int ib){
    if(ia==la && ib==lb){
        ok=1;return;
    }
    if(ia==la)return;

    if(mp[a[ia]-'a'].l!=0){
        if(ib+mp[a[ia]-'a'].l>lb)return;
        for(int i=0;i<mp[a[ia]-'a'].l;i++){
            if(b[ib+i]!=mp[a[ia]-'a'].s[i])return;
        }
        dfs(ia+1,ib+mp[a[ia]-'a'].l);
        return;
    }

    for(int i=1;i<=k;i++){
        if(ib+i>lb)return;

        mp[a[ia]-'a'].l=i;
        for(int j=0;j<i;j++){
            mp[a[ia]-'a'].s[j]=b[ib+j];
        }
        dfs(ia+1,ib+i);
        mp[a[ia]-'a'].l=0;
    }
}

int main(){
    int T;scanf("%d",&T);
    while(T--){
        memset(mp,0,sizeof(mp));

        scanf("%d%s%s",&k,a,b);
        la=strlen(a);
        lb=strlen(b);

        ok=0;
        dfs(0,0);

        printf("%d\n",ok);
    }
    return 0;
}

简要题意

解法

代码

简要题意

解法

代码

简要题意

解法

代码

简要题意

解法

代码

简要题意

解法

代码

简要题意

解法

代码

简要题意

解法

代码