当前位置：首页 > news >正文

CSP-S模拟10

news 2025/10/19 21:40:30

🍄T1：二分图匹配(match)

🌅题目：

🌈【题目描述】

小明学了二分图匹配的算法。

现在小明想了一个问题：他有两种类型的点—— n 个红点、m 个蓝点，红点编号为 1∼n ,蓝点编号为 1∼m ,每个点都有一个属性值，用大写字母 A∼Z 表示，每次要将属性相同蓝点和红点进行匹配操作，由于是匹配，所以每个点只能匹配一次，另外小明希望匹配的情况尽可能简单，所以每次匹配的结点不能存在交叉的情况，即如果出现红点 i₁与蓝点 j₁匹配，红点 i₂与蓝点 j₂ 匹配，且满足i₁<i₂，那么一定有 j₁<j₂。现在小明想知道最多有多少组匹配。

🍅【输入格式】

第一行一个整数 n,m。
接下来一行,一个长度为 n 的字符串 S₁
，每个字符为 A∼Z 中一个，第 i 个字符表示红点 i 的属性。
接下来一行,一个长度为 m 的字符串 S₂，每个字符为 A∼Z 中一个，第 i 个字符表示蓝点 i 的属性。

🍍【输出格式】

一个整数，表示最多的匹配数

🍠【样例 1 输入】

2 5
AB
BAABB

🍒【样例 1 输出】

样例解释： S₁中的 A 可以与 S₂中第二个字符 A 匹配，S₁中的 B 可以与 S₂中的第四个字符 B 匹配

🍋【样例 2】

见下发文件

🍉【样例 3】

见下发文件

🍑【子任务】

对于30%的数据，1 ≤n,m≤ $ 10 ^ {3}$。

对于另外 20% 的数据，保证 S₁中字符都相同。

对于100%的数据，1≤n≤$10^3$,1≤m≤$10^6$。

🍭解析：

首先这个题一眼DP ~~（别问我为啥，我也不知道为啥）~~。既然这样，那么我们来考虑一下DP方程式吧！可以肯定的是至少有两维：i表示S1到第i位，j表示S2到第j位。再次思考，我们可以发现我们还需要一维来表明我们是否让这一组点匹配，即为dp[i][j][0/1]。再偷瞄一眼数据范围，丸辣，1e3×1e6×2，要boom了！莫慌，莫慌。让我们来思考一下解决方案。我们可以发现dp[i][j]仅与dp[i-1][j],dp[i][j-1]和dp[i-1][j-1]有关，因此我们可以利用滚动数组来节约空间。即转化为dp[j][d]，j表示S2到第j位，d则是我们滚动的i。因此真正的状态转移方程为dp[j][d]=max(dp[j][!d],max(dp[j-1][d],dp[j-1][!d]+1)).（换算一下就是dp[i][j]=max(dp[i-1][j],max(dp[i][j-1],dp[i-1][j-1]+1))）。然后我们再根据子任务提示特判一下S1中字符都相等的情况就大功告成啦！撒花~✿✿ヽ(°▽°)ノ✿

🍰最后，必不可少的一步，代码来啦~~

#include<iostream>
#include<cstring>
using namespace std;
int m,n,cnt,dp[1000005][2];char S[1005],T[1000005];bool t,d;
int main(){freopen("match.in","r",stdin);freopen("match.out","w",stdout);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>m;cin>>(S+1)>>(T+1);int same=S[1];for(int i=1;i<=n;i++){if(S[i]!=same){t=1;break;}}if(!t){for(int i=1;i<=m;i++) if(T[i]==same) cnt++;cnt=min(cnt,n);cout<<cnt<<'\n';return 0;}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) dp[j][d]=max(dp[j][!d],max(dp[j-1][d],dp[j-1][!d]+(S[i]==T[j])));//滚动数组优化 当前状态仅与i-1和j-1有关 d=!d;}cout<<dp[m][!d]<<'\n';return 0;
}

🌼T2：虚图（map）

🎂题目：

🍦【题目描述】

小明学了虚树，现在小明在想一个复杂的问题——虚图。

他觉得树太简单了，所以他把问题放在了一张 n 个点(编号依次为 1,2,3,...,n) m 条边的无向连通图上，虚树中有关键点的概念，故而他在图上设置了 TT 个关键点，小明现在想知道在这张图上怎么求任意两个关键点之间的距离的最小值。

🍤【输入格式】

第一行三个整数n,m,T

接下来 m 行,每行3个整数(u,v,w)，表示端点为 u,v，边权为 w 的无向边。

接下来一行 T 个整数，表示关键点的编号

🍷【输出格式】

一个整数，表示最小值。

🍵【样例 1 输入】

🎧【样例 1 输出】

🎨【样例 2 输入】

【样例 2 输出】

📖【样例 3】

见下发文件

🔮【子任务】

对于30%的数据，1≤n,m≤1000。

对于额外20%的数据，m=n-1

对于100%的数据，1≤n,m≤2×$10^5$,1≤u,v≤n,1≤w≤10^9。

解析：

看一眼题面，应该是最短路。事实证明最短路（dij或者SPFA）都有30pts，那我为什么保龄呢 ~~（我才不说是因为我把板子忘了）~~。据题解所说，显然求出所有的被标记的点出发的最短路。而且显然（也是题解说的，不是我说的！）每个被标记的点都有自己的管辖范围（在管辖范围中的点距离该点最近）。其他的倒是不太难,写一个堆优化的dij就好啦||ヽ(￣▽￣)ノミ|Ю

🎆嗯，上链接代码！

#include<iostream>
#include<queue>
#include<cstring>
#define ll long long
using namespace std;
const int N=800800,inf=1e9;
struct node{int to,nxt,val;}e[N<<1];
int n,m,T,cnt,head[N],id[N],ans=inf;ll dis[N];bool flag[N];
inline void add(int x,int y,int z){e[++cnt].to=y;e[cnt].val=z;e[cnt].nxt=head[x];head[x]=cnt;
}//建边 
struct nd{int t;ll v;friend bool operator <(const nd &a,const nd &b){return a.v>b.v;}
};
priority_queue<nd> q;
inline void dij(int s){dis[s]=0;q.push({s,0ll});while(!q.empty()){nd x=q.top();q.pop();if(ans<=x.v) continue;//无影响 if(x.t!=s&&flag[x.t]){//除s以外的关键点 ans=x.v;continue;}int u=x.t;ll w=x.v;for(int i=head[u];i;i=e[i].nxt){int v=e[i].to;if(dis[v]>w+e[i].val){dis[v]=w+e[i].val;q.push({v,dis[v]});}}}
} 
int main(){
//	freopen("map.in","r",stdin);
//	freopen("map.out","w",stdout);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>m>>T;while(m--){int a,b,c;cin>>a>>b>>c;if(a==b) continue;//自环 add(a,b,c);add(b,a,c);//建边 }memset(dis,0x3f,sizeof(dis));for(int i=1;i<=T;i++){cin>>id[i];flag[id[i]]=1;//标记关键点编号 }for(int i=1;i<T;i++) dij(id[i]);cout<<ans<<'\n';return 0; 
}

🍓T3：冒泡 (bubble)

🌹题目：

🐉【题目描述】

小明学习了冒泡排序。
大致代码如下：

for(int i=1;i<=n;++i) {for(int j=1;j<=n-i;++j) {if(a[j]>a[j+1]) {swap(a[j],a[j+1]);}}
}

为了检验小明的学习成果，老师准备出一些题目考考小明。

由于冒泡排序可以稍微进行一些优化，所以老师准备考考小明关于冒泡排序交换次数的问题。

为了确保小明是理解而不是模拟，老师准备用多组数据考察小明，在这儿为了方便数据的生成，老师划定了一个区间 [L,R] ，对于 $x=\overline{a_1a_2\cdots a_n} \in [L,R]$,将 x 在十进制下数位分离后即可得到一个数列 a₁,a₂,...,a_n，比如对于数13579，我们可以看成数列1,3,5,7,9。

现在为了方便比较答案，老师希望知道区间 [L,R] 中所有数对应的序列冒泡排序交换次数之和在模$10^9$+7下的答案。

🐇【输入格式】

第一行一个整数 T 表示老师考察的次数

多组数据，对于每组数据，第一行两个整数 L,R。

❄️【输出格式】

一共 T 行，每行一个整数，表示答案

☀️【样例 1 输入】

✨【样例 1 输出】

2
67
393

样例解释：对于区间[10,20],只有10对应的序列1,0和20对应的序列2，0冒泡排序时需要进行一次交换，故而交换总次数为2

💖【样例 2 输入】

1
100 2000

🎵【样例 2 输出】

🔥【样例 3 】

见下发文件

☔【数据范围】

对于 20% 的数据，1≤L≤R≤$10^6$。

对于额外 10% 的数据，L=R。

对于额外 30% 的数据，保证 T=1。

对于100%的数据1≤L≤R≤$10^{500000}$
,1≤T≤5。

🌺解析：

暂时没有……略略略

🌻代码少不了滴（嘿嘿从QED那偷偷贺过来的希望跪求QED不要生气🙏）

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define ll long long
using namespace std;
const int N = 5e5 + 10, mod = 1e9 + 7;
const ll inf = 1e18;
ll g[N], sum[N], p10[N];
void Pre(){for (ll i = 2; i < N; i++)for (ll j = 9; j >= 0; j--)(g[i] += g[i - 1] + (9 - j) * p10[i - 2] * (i - 1)) %= mod;
}
int calc(string s){int len = s.size();ll res = 0, pre = 0;for (ll i = 1; i <= len; i++){int d = s[i - 1] - '0';ll base = 0;for (ll j = 0; j < 10; j++) base += sum[j] * j * (len - i) % mod * p10[len - i - 1];base %= mod;ll tmp = 0;for (int i = 9; i >= d; i--) tmp += sum[i];for (ll j = d - 1; j >= 0; j--){res += pre * p10[len - i] + g[len - i] + base + tmp * p10[len - i] + j * (len - i) * p10[len - i - 1];tmp += sum[j];}res %= mod;for (int j = d + 1; j < 10; j++) pre += sum[j];pre %= mod;sum[d]++;}memset(sum, 0, sizeof(sum));return (res + pre) % mod;
}
string cutDown(string s){string news = s;for (int i = (int)news.size(); i >= 1; i--){if (news[i - 1] != '0'){news[i - 1]--;break;}news[i - 1] = '9';}if (news[0] == '0'){string newnews;for (int i = 1; i < (int)news.size(); i++) newnews.push_back(news[i]);return newnews;}return news;
}
signed main(){//freopen("bubble.in", "r", stdin); freopen("bubble.out", "w", stdout);ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0);int T; cin >> T;p10[0] = 1;for (int i = 1; i < N; i++) p10[i] = p10[i - 1] * 10 % mod;Pre();while (T--){string l, r; cin >> l >> r;cout << (calc(r) - calc(cutDown(l)) + mod) % mod << '\n';}return 0;
}

查看全文

http://www.hskmm.com/?act=detail&tid=34544