ABC273 F
- 简要题意
一个人要沿数轴从 \(0\) 处走到 \(x\) 处，数轴上有一些障碍，每个障碍有一把对应的锤子可以将其销毁，给定障碍和锤子的坐标及 \(x\) ，求最短路长。
- 简要题解
区间 \(DP\) 的思想，设 \(dp[l][r][0]\) 为遍历完 \([l,r]\) 的坐标，并且位于 \(l\) 位置，的到达 \(x\) 的最短路长；\(dp[l][r][1]\) 为位于 \(r\) 处，直接记搜转移即可。
ABC272 F
- 简要题意
给定两个长度为 \(n\) 的字符串 \(S,T\)，定义 \(f(S,i)\) 为将 \(S\) 的前 \(i\) 个字符依次拼到末尾形成的字符串。
问有多少二元组 \((i,j)\) 满足 \(f(S,i)\) 的字典序小于 \(f(T,j)\) 。
- 简要题解
将两个字符串都拉两倍后拼在一起跑 \(SA\) ，那么此时已经按照字典序排好序了，维护一个后缀和统计答案即可。
ABC 270 F
- 简要题意
\(n\) 个初始互不联通的岛屿，你有如下方法让其联通。
- 对于每个点 \(i\) ，你可以花费 \(a_i\) 在该点修机场。两点如果都有机场，那这两点可以互相到达。
- 对于每个点 \(i\) ，你可以花费 \(b_i\) 在该点修港口。两点如果都有港口，那这两点可以互相到达。
- 有 \(m\) 条道路，第 \(i\) 条道路连接 \(u_i,v_i\) ，你可以花费 \(w-i\) 让开通这条道路，开通后，道路的两个端点可以互相到达。
- 简要题解
看着就很像一个最小生成树的题目，对于在点上有代价的，我们可以通过新建点再向该点连边的方式来实现。
具体的，对于机场，我们连边 \(i->n+1\) ，边权为 \(a_i\) ；对于港口，我们连边 \(i->n+2\) ，边权为 \(b_i\) ；对于道路正常连边，然后跑最小生成树即可。
点击查看代码
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=2e5+5;
const LL inf=0x3f3f3f3f3f3f3f3f;
inline int read() {
int x=0,w=0; char ch=getchar();
while(!isdigit(ch)) w|=(ch=='-'), ch=getchar();
while(isdigit(ch)) x=x*10+(ch^48), ch=getchar();
return w?-x:x;
}
struct edge { int x,y,z; bool friend operator<(edge x,edge y) { return x.z<y.z; } }e[N<<2];
int n,m,idx,a[N],b[N],u[N],v[N],w[N],fa[N];
LL ans=inf;
inline int Get(int x) { return fa[x]==x?x:fa[x]=Get(fa[x]); }
inline LL Kruskal(int n) {
for(int i=1;i<=n;i++) fa[i]=i;
sort(e+1,e+1+idx);
LL res=0,cnt=0;
for(int i=1,fx,fy;i<=idx && cnt<n-1;i++) {
fx=Get(e[i].x); fy=Get(e[i].y);
if(fx^fy) fa[fx]=fy, ++cnt, res+=e[i].z;
}
return cnt==n-1?res:inf;
}
int main() {
n=read(); m=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++) b[i]=read();
for(int i=1;i<=m;i++) u[i]=read(), v[i]=read(), w[i]=read();
for(int k=0,node;k<4;k++) {
node=n; idx=0;
if(k&1) { ++node; for(int i=1;i<=n;i++) e[++idx]=edge{i,node,a[i]}; }
if(k&2) { ++node; for(int i=1;i<=n;i++) e[++idx]=edge{i,node,b[i]}; }
for(int i=1;i<=m;i++) e[++idx]=edge{u[i],v[i],w[i]};
ans=min(ans,Kruskal(node));
}
cout<<ans<<endl;
return 0;
}
ABC243 F
- 简要题意：
共 \(n\) 个物品，可以随机抽 \(k\) 轮，每轮相互独立且抽中物品 \(i\) 的概率为 \(p_i\) ，问最终恰好抽到 \(m\) 个不同的物品的概率。
\(m\) 个 物品，每个物品可以重复选，最终选择恰好 \(n\) 个物品的概率（无标号） \(P=\frac{n!}{\prod_{i=1}^mc_i!}\) 。
- 简要题解
设考虑完 \(x\) 个物品，共选择了 \(y\) 个不同的物品，已经选择了 \(z\) 次的概率为 \(f[x][y][z]\) ，那么每次转移枚举第 \(x+1\) 个物品选择多少个即可。转移方程：
\[\frac{p_{x+1}^c}{c!}f[x][y][z]->f[x+1][y+[c!=1]][z+c]) \] 标签：ATcoder,简要,题意,记录,int,题解,ch,物品 From： https://www.cnblogs.com/oscaryangzj/p/16849229.html