[蓝桥杯 2023 省 B]接龙数列 

对于一个长度为 K 的整数数列：A1​,A2​,…,AK​，我们称之为接龙数列当且仅当 Ai​ 的首位数字恰好等于 Ai−1​ 的末位数字（2≤i≤K）。

例如 12,23,35,56,61,11 是接龙数列；12,23,34,56 不是接龙数列，因为 56 的首位数字不等于 34 的末位数字。所有长度为 1 的整数数列都是接龙数列。

现在给定一个长度为 N 的数列 A1​,A2​,…,AN​，请你计算最少从中删除多少 个数，可以使剩下的序列是接龙序列？

输入格式

第一行包含一个整数 N。

第二行包含 N 个整数 A1​,A2​,…,AN​。

输出格式

一个整数代表答案。

解：

容易想到，本题可以使用 dp 解决。

我们可以发现，一个数字是什么并不重要，重要的是头尾两个数字。我们可以先将每个数字的头尾记录下来，记为 li​,ri​。

接着设 dpi,j​ 表示到第 i 个数以 j 结尾的接龙数列的最大长度。

当 li​=ri−1​ 时，意味着当前的数字可以和前一个数字接起来，此时 dpi,ri​​=max(dpi,ri​​,dpi−1,li​​)。

否则 dpi,ri​​=max(dpi,ri​​,dpi−1,ri​​)，因为当前这个数无法做出更多贡献。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,dp[N][20];
struct Node{
	int l,r;
}a[N];

int main(){
    cin >> n;
    if(n == 1) cout << 0 << endl;
    else{
        string s;
        for(int i = 1;i <= n;i++){
            cin >> s;
            a[i].l=s[0]-'0';
    		a[i].r=s[s.length()-1]-'0';
        }
        for(int i = 1;i <= n;i++){
            dp[i][a[i].r] = max(dp[i-1][a[i].r],dp[i-1][a[i].l] + 1);
            for(int j = 0;j <= 9;j++){
    			if(j != a[i].r) dp[i][j]=dp[i-1][j];
    		}
        }
        int ans=0;
    	
    	for(int i=1;i<=n;i++){
    		for(int j=0;j<=9;j++) cout<<dp[i][j]<<" ";
    		cout << endl;
    	}
    	
    	for(int i=0;i<=10;i++) ans=max(ans,dp[n][i]);
    	cout << n-ans;
    }
}

简化：直接在原dp上进行更新，不再记录历史数据。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,dp[20];
struct Node{
	int l,r;
}a[N];

int main(){
    cin >> n;
    for(int i = 1;i <= n;i++){
        string s;
        cin >> s;
        a[i].l = s[0] - '0';
        a[i].r = s[s.length() - 1] - '0';
        dp[a[i].r] = max(dp[a[i].r],dp[a[i].l] + 1);
        // cout << dp[a[i].r] << endl;
    }
    // for(int j=0;j<=9;j++) cout << dp[j] << " ";
    // cout << endl;
    int ans = 0;
    for(int j = 0;j <= 9;j++) ans = max(dp[j],ans);
    cout << n - ans;
}

[蓝桥杯 2023 省 B] 子串简写

题目描述

程序猿圈子里正在流行一种很新的简写方法：对于一个字符串，只保留首尾字符，将首尾字符之间的所有字符用这部分的长度代替。例如 internationalization 简写成 i18n，Kubernetes（注意连字符不是字符串的一部分）简写成 K8s，Lanqiao 简写成 L5o 等。

在本题中，我们规定长度大于等于 K 的字符串都可以采用这种简写方法(长度小于 K 的字符串不配使用这种简写)。

给定一个字符串 S 和两个字符 c1​ 和 c2​，请你计算 S 有多少个以 c1​ 开头 c2​ 结尾的子串可以采用这种简写？

输入格式

第一行包含一个整数 K。

第二行包含一个字符串 S 和两个字符 c1​ 和 c2​。

输出格式

一个整数代表答案。

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long k,cnt = 0,ans = 0;
    cin >> k;
    string s;
    char c1,c2;
    cin >> s >> c1 >> c2;
    int l = 0,r = k - 1;
    while(r <= s.length()){
        if(s[l] == c1) cnt ++;//如果第一个指针所指向的字符是第一个字符，那么计数器加一
        if(s[r] == c2) ans += cnt;//如果第二个指针所指向的字符是第二个字符，那么答案加上计数器的值
        l++,r++;//两个指针每次加一
    }
    cout << ans;
}

[蓝桥杯 2023 省 B] 砍树

题目描述

给定一棵由 n 个结点组成的树以及 m 个不重复的无序数对 (a1​,b1​),(a2​,b2​),…,(am​,bm​)，其中 ai​ 互不相同，bi​ 互不相同，ai​=bj​(1≤i,j≤m)。

小明想知道是否能够选择一条树上的边砍断，使得对于每个 (ai​,bi​) 满足 ai​ 和 bi​ 不连通，如果可以则输出应该断掉的边的编号 (编号按输入顺序从 1 开始)，否则输出 -1。

输入格式

输入共 n+m 行，第一行为两个正整数 n,m。

后面 n−1 行，每行两个正整数 xi​,yi​ 表示第 i 条边的两个端点。

后面 m 行，每行两个正整数 ai​,bi​。

输出格式

一行一个整数，表示答案，如有多个答案，输出编号最大的一个。

解：

给n个节点，n-1行边，m行目标对。以n个节点组成无向图G，假设有2个目标对，a, b 与 c, d。在图G中，a到b的路径与c到d的路径会有重合，要求找到一组边，砍断后同时使a，b、c， d这两条路径都无法连接，也就是重合路径中编号大的一条。

我采用的方法是dfs暴力深搜，会超时，只能通过3/10

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

const int N = 1e5 + 10;
typedef pair<int,int> pii;
vector<int> edge[N];//图
int n,m;
int w[N];//每一个边的计数
map<pii,int> id;//存边的编号

/*      目标节点  当前节点  父节点（前一个节点）  */
bool dfs(int to, int now, int father)
{
    if(now == to) return true;
    for(int i = 0; i< edge[now].size(); i ++)
    {
        int son = edge[now][i];
        if(son == father) continue;
        
        if(dfs(to, son, now))
        {
            int ID = id[{now,son}];
            w[ID] ++;//计数加一
            return true;
        }
    }
    return false;
}

void solve()
{
    cin >> n >> m;
    for(int i = 0;i < n-1;i ++)
    {
        int x, y; cin >> x >> y;
        
        edge[x].push_back(y);//记录路径
        edge[y].push_back(x);
        
        id[{x,y}] = id[{y,x}] = i;//记录边号
    }
    for(int i = 0;i < m;i ++)//记录目标起点终点
    {
        int x, y; cin >> x >> y;
        dfs(y, x, -1);//dfs深搜
    }
    int ans = -1;
    for(int i = n - 1;i >= 0;i --)//从大到小枚举，输出编号最大的一个边
    {
        if(w[i] == m)
        {
            ans = i + 1;
            break;
        }
    }
    cout << ans << endl;
}

signed main()
{
    solve();
}