| A | B | C | D | Sum | Rank |
|---|---|---|---|---|---|
| 50 | 50 | 30 | 0 | 130 | 10/17 |
A. 二分图匹配
首先考虑一个朴素的 DP：设 \(f_{i,j}\) 表示 \(S_1[1\dots i]\) 和 \(S_2[1\dots j]\) 的最大匹配数量。发现空间开不下。注意到 \(f\) 数组的值最大为 \(\min(n,m)\)，考虑交换下标与值域，设 \(f_{i,j}\) 表示 \(S_1[1\dots i]\) 匹配了 \(j\) 位在 \(S_2\) 上的最短前缀。记 \(g_{i,j}\) 表示 \(S_2\) 中第 \(i\) 位之后第一次出现字符 \(j\) 的位置，于是有转移：\(f_{i,j}=\min(f_{i-1,j},g_{f_{i-1,j-1},{S_1}_i})\)。时间复杂度 \(O(26m+n^2)\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=1e3+5,maxm=1e6+5,inf=1e9;
int n,m,f[maxn][maxn],g[maxm][30],pos[30];
string s1,s2;
int main(){ios::sync_with_stdio(0),cin.tie(0);cin>>n>>m>>s1>>s2;s1=" "+s1,s2="A"+s2;memset(pos,0x3f,sizeof(pos));for(int i=m;~i;i--){for(int j=0;j<=25;j++){g[i][j]=pos[j];}pos[s2[i]-'A']=i;}memset(f,0x3f,sizeof(f));for(int i=0;i<=n;i++){f[i][0]=0;for(int j=1;j<=i;j++){f[i][j]=min(f[i-1][j],f[i-1][j-1]>=inf?inf:g[f[i-1][j-1]][s1[i]-'A']);}}for(int i=n;~i;i--){if(f[n][i]<=m){cout<<i;break;}}return 0;
}
}
int main(){return asbt::main();}
B. 虚图
考虑直接对这些关键点二进制分组，当前位为 \(1\) 的连一条 \(S\xrightarrow{0} a_i\)，否则连一条 \(a_i\xrightarrow{0} T\)，从 \(S\) 跑最短路，用 \(dis_T\) 更新答案即可。因为两个不同的点至少有一位不同，所以这样的分组方式遍历了所有组合。时间复杂度 \(O((n+m)\log^2n)\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pii pair<int,int>
#define fir first
#define sec second
#define mp make_pair
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=2e5+5;
const ll inf=1e18;
int n,m,kk,a[maxn];
ll dis[maxn];
bool vis[maxn];
vector<pii> e[maxn];
struct edge{int u,v,w;
}E[maxn];
priority_queue<pii> q;
il void dijkstra(int u){memset(dis,0x3f,sizeof(dis));memset(vis,0,sizeof(vis));dis[u]=0,q.push(mp(0,u));while(q.size()){int x=q.top().sec;q.pop();if(vis[x]){continue;}vis[x]=1;for(pii i:e[x]){int v=i.fir,w=i.sec;if(!vis[v]&&dis[v]>dis[x]+w){dis[v]=dis[x]+w;q.push(mp(-dis[v],v));}}}
}
int main(){ios::sync_with_stdio(0),cin.tie(0);cin>>n>>m>>kk;for(int i=1;i<=m;i++){cin>>E[i].u>>E[i].v>>E[i].w;}for(int i=1;i<=kk;i++){cin>>a[i];}int S=n+1,T=n=S+1;ll ans=inf;for(int i=0;i<=17;i++){for(int j=1;j<=m;j++){e[E[j].u].pb(mp(E[j].v,E[j].w));e[E[j].v].pb(mp(E[j].u,E[j].w));}for(int j=1;j<=kk;j++){if(j>>i&1){e[S].pb(mp(a[j],0));}else{e[a[j]].pb(mp(T,0));}}dijkstra(S),ans=min(ans,dis[T]);for(int j=1;j<=n;j++){e[j].clear();}}cout<<ans;return 0;
}
}
int main(){return asbt::main();}
C. 冒泡
考虑将答案差分，分为 \([1,r]\) 和 \([1,l]\) 两部分。
对于 \([1,x]\)，考虑枚举当前考虑的数有前端有多少与 \(x\) 相同。假设 \(x\) 为 \(\overline{a_1a_2a_3\dots}\)，如果当前枚举的为 \(\overline{a_1k}\;(k<a_2)\)，那么后面的位数都可以随意乱选。将此时的答案拆成已确定的部分、未确定的部分和二者之间。设未确定的还有 \(len\) 位，对于已确定的部分，求出其逆序对数 \(tot\)，这一部分答案为 \(tot\times10^{len}\)；对于未确定的部分，任选两个位置组成逆序对，其他位置乱选，答案为 \(\frac{len\times(len-1)}{2}\times45\times10^{len-2}\)；二者之间的部分，假设前面有一个 \(c\)，若希望构成逆序对则后面一个位置的取值有 \(0\dots c-1\) 共 \(c\) 种，贡献为 \(c\times len\times10^{len-1}\)。
注意这样无法算入 \(x\) 的贡献，需要另外求出来。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=5e5+5,mod=1e9+7;
int T,pw[maxn];
string l,r;
il int calc(string s){int x=s.size(),tot=0,sum=0,res=0,cnt[15]={0};for(char ch:s){int c=ch^48;x--;for(int i=0;i<c;i++){if(x>=2){(res+=x*(x-1)/2%mod*45%mod*pw[x-2])%=mod;}if(x>=1){(res+=(sum+i)*x%mod*pw[x-1])%=mod;}(res+=(tot+cnt[i+1])*pw[x])%=mod;}(tot+=cnt[c+1])%=mod,(sum+=c)%=mod;for(int i=0;i<=c;i++){cnt[i]++;}}return res;
}
il int nxd(string s){int cnt[15]={0},res=0;for(char ch:s){int c=ch^48;for(int i=c+1;i<=9;i++){(res+=cnt[i])%=mod;}cnt[c]++;}return res;
}
int main(){ios::sync_with_stdio(0),cin.tie(0);pw[0]=1;for(int i=1;i<=5e5;i++){pw[i]=pw[i-1]*10%mod;}cin>>T;while(T--){cin>>l>>r;cout<<(calc(r)-calc(l)+nxd(r)+mod)%mod<<"\n";}return 0;
}
}
signed main(){return asbt::main();}