接龙数列 、 子串简写 与 砍树

[蓝桥杯 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​​)因为当前这个数无法做出更多贡献。#includebits/stdc.h using namespace std; const int N1e55; 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].ls[0]-0; a[i].rs[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 ans0; for(int i1;in;i){ for(int j0;j9;j) coutdp[i][j] ; cout endl; } for(int i0;i10;i) ansmax(ans,dp[n][i]); cout n-ans; } }简化直接在原dp上进行更新不再记录历史数据。#includebits/stdc.h using namespace std; const int N1e55; 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 j0;j9;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简写成i18nKubernetes注意连字符不是字符串的一部分简写成K8sLanqiao简写成L5o等。在本题中我们规定长度大于等于 K 的字符串都可以采用这种简写方法(长度小于 K 的字符串不配使用这种简写)。给定一个字符串 S 和两个字符 c1​ 和 c2​请你计算 S 有多少个以 c1​ 开头 c2​ 结尾的子串可以采用这种简写输入格式第一行包含一个整数 K。第二行包含一个字符串 S 和两个字符 c1​ 和 c2​。输出格式一个整数代表答案。#includebits/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。输入格式输入共 nm 行第一行为两个正整数 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的路径会有重合要求找到一组边砍断后同时使ab、c d这两条路径都无法连接也就是重合路径中编号大的一条。我采用的方法是dfs暴力深搜会超时只能通过3/10#includebits/stdc.h #define int long long using namespace std; const int N 1e5 10; typedef pairint,int pii; vectorint edge[N];//图 int n,m; int w[N];//每一个边的计数 mappii,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(); }