- \(\large\text{Floyed--最小环}\)
思路：枚举环上一条路径 \(i\) 至 \(j\)，那么该环一定由是一条 \(k\) 至 \(i\) 的边和该路径再加 \(j\) 至 \(k\) 的边。在取最小值时要判 \(i\not=j\)。
code：
点击查看代码
int n,m,ans=inf/10,e[107][107],dis[107][107];
void solve(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
e[i][j]=dis[i][j]=inf/10;
}
}
for(int i=1,u,v,w;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
e[u][v]=e[v][u]=dis[u][v]=dis[v][u]=w;
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i^j)ans=min(ans,dis[i][j]+e[k][i]+e[j][k]);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
if(ans==inf/10)printf("No solution.");
else printf("%d",ans);
}
- \(\large\text{埃筛--区间筛}\)
思路：若 \(n\) 为合数，那么他的最小质因子 \(\leq\sqrt n\)。筛出 \([1,\sqrt n]\) 中的所有质数，再对要求范围内的所有数进行埃筛即可。
code：
点击查看代码
int n,m,k,ans,pm[maxn];
bool vis[maxn];
void solve(){
const int mxn=1<<16;
for(int i=2;i<=mxn;i++){
if(!vis[i])pm[++k]=i;
for(int j=1;j<=k&&pm[j]<=mxn/i;j++){
vis[i*pm[j]]=true;
if(i%pm[j]==0)break;
}
}
scanf("%lld%lld",&n,&m);
mems(vis,false);
for(int i=1;pm[i]*pm[i]<=m;i++){
for(int j=(max(2ll,(n-1)/pm[i]+1))*pm[i];j<=m;j+=pm[i]){
vis[j-n+1]=true;
}
}
for(int i=1;i<=m-n+1;i++)ans+=!vis[i];
printf("%lld",n==1?ans-1:ans);
}
- \(\large\text{矩阵乘法+Floyed--倍增Floyed}\)
思路：\(i\) 到 \(j\) 经过 \(x+y\) 条边的最短路等于对于每个 \(k\) 点，\(i\) 到 \(k\) 的最短路加上 \(k\) 到 \(j\) 的最短路的最小值。
code：
点击查看代码
int n,m,s,t,tot,bk[1007];
struct matrix{
int e[maxn][maxn];
matrix operator*(const matrix x)const{
matrix res;
for(int i=1;i<=tot;i++){
for(int j=1;j<=tot;j++){
res.e[i][j]=inf/2;
for(int k=1;k<=tot;k++){
res.e[i][j]=min(res.e[i][j],e[i][k]+x.e[k][j]);
}
}
}
return res;
}
}st;
matrix qpow(matrix x,int y){
y--;matrix res=x;
while(y){
if(y&1)res=res*x;
x=x*x;
y>>=1;
}
return res;
}
void solve(){
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=1;i<=200;i++){
for(int j=1;j<=200;j++){
st.e[i][j]=inf/2;
}
}
while(m--){
int u,v,w;
scanf("%d%d%d",&w,&u,&v);
if(!bk[u])bk[u]=++tot;
if(!bk[v])bk[v]=++tot;
st.e[bk[u]][bk[v]]=st.e[bk[v]][bk[u]]=w;
}
matrix ans=qpow(st,n);
printf("%d",ans.e[bk[s]][bk[t]]);
}
- \(\large\text{树状数组——权值树状数组上倍增}\)
先咕着，等找到合适的例题再补上。
- \(\large\text{树状数组——离线处理}\)
思路：以右端点为关键字排序，通过记录已经出现过的种类实现去重，最后以前缀和的方式计算答案。
code：
点击查看代码
int n,m,d[maxn],lst[maxn],ans[maxn],e[maxn];
struct node{
int l,r,id;
bool operator<(const node &x)const{return r<x.r;}
}q[maxn];
inline int lowbit(int x){return x&(-x);}
void update(int x,int y){
while(x<=n){
e[x]+=y;
x+=lowbit(x);
}
}
int query(int x){
int ret=0;
while(x>0){
ret+=e[x];
x-=lowbit(x);
}
return ret;
signed main(){
read(n);
for(int i=1;i<=n;i++)read(d[i]);
read(m);
for(int i=1;i<=m;i++)read(q[i].l),read(q[i].r),q[i].id=i;
sort(q+1,q+m+1);
for(int i=1,now=1;i<=m;i++){
while(now<=q[i].r){
if(lst[d[now]])update(lst[d[now]],-1);
lst[d[now]]=now;
update(now++,1);
}
ans[q[i].id]=query(q[i].r)-query(q[i].l-1);
}
for(int i=1;i<=m;i++)write(ans[i]);
}