一些不知怎么分类的算法。
huffman树：https://www.luogu.org/problemnew/show/P2168
#include<bits/stdc++.h> #define ll long long using namespace std; const int N=1e5+99; struct node{ll v;int h;}; int n,num,k; ll ans; priority_queue<node>q; bool operator<(node a,node b){return (a.v!=b.v)?a.v>b.v:a.h>b.h;} int main() { scanf("%d%d",&n,&k); ll x; for(int i=1;i<=n;i++) {scanf("%lld",&x);q.push((node){x,0});} num=n; while((num-1)%(k-1))num++,q.push((node){0,0}); while(num>1) { int maxh=0;ll sum=0; for(int i=1;i<=k;i++) { node p=q.top();q.pop(); sum+=p.v;maxh=max(maxh,p.h); } num-=k-1;ans+=sum; q.push((node){sum,maxh+1}); } node p=q.top(); printf("%lld %d",ans,p.h); }
矩阵树定理：https://www.luogu.org/problemnew/show/P4111
#include<cstdio> #include<algorithm> using namespace std; typedef long long ll; const int mod=1e9; const int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1}; int n,m,tot,id[107][107]; ll a[107][107]; char str[107]; ll Gauss() { ll ret=1; for(int i=2;i<=tot;i++) { for(int j=i+1;j<=tot;j++) while(a[j][i]) { ll t=a[i][i]/a[j][i]; for(int k=i;k<=tot;k++)a[i][k]=(a[i][k]-a[j][k]*t)%mod; for(int k=i;k<=tot;k++)swap(a[i][k],a[j][k]); ret=-ret; } if(!a[i][i])return 0; ret=ret*a[i][i]%mod; } return (ret+mod)%mod; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%s",str+1); for(int j=1;j<=m;j++)if(str[j]=='.')id[i][j]=++tot; } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=0;k<4;k++) { int x=i+dx[k],y=j+dy[k]; if(id[x][y])a[id[x][y]][id[i][j]]--,a[id[i][j]][id[i][j]]++; } printf("%lld",Gauss()); }
分数规划：https://www.luogu.org/problemnew/show/P3199
#include<bits/stdc++.h> using namespace std; const int N=11100; int n,m,ecnt,hd[N],v[N],nxt[N],vis[N],used[N],tim[N]; double w[N],d[N]; bool spfa(int S,double k) { queue<int>q;q.push(S); for(int i=1;i<=n;i++)vis[i]=0,tim[i]=0,d[i]=1e18; d[S]=0,tim[S]=1; while(!q.empty()) { int u=q.front();q.pop();vis[u]=0,used[u]=1; for(int i=hd[u];i;i=nxt[i]) if(d[v[i]]>d[u]+w[i]-k) { d[v[i]]=d[u]+w[i]-k; if(!vis[v[i]])q.push(v[i]),vis[v[i]]=1,tim[v[i]]++; if(tim[v[i]]>50)return 1; } } return 0; } bool check(double val) { memset(used,0,sizeof used); for(int i=1;i<=n;i++)if(!used[i]&&spfa(i,val))return 1; return 0; } int main() { scanf("%d%d",&n,&m); for(int i=1,x,y;i<=m;i++) { double z;scanf("%d%d%lf",&x,&y,&z); v[++ecnt]=y,nxt[ecnt]=hd[x],w[ecnt]=z,hd[x]=ecnt; } double l=-1e7-100,r=1e7+100; while(r-l>1e-9) { double mid=(l+r)/2; if(check(mid))r=mid;else l=mid; } printf("%.8lf",l); }
模拟退火：https://www.luogu.org/problemnew/show/P2503
注：可能要多交几发才能过
#include<bits/stdc++.h> using namespace std; int n,m,a[50],bel[50],sum[50]; double ans,ave; void fire() { double tot=0; memset(sum,0,sizeof sum); for(int i=1;i<=n;i++)bel[i]=rand()%m+1,sum[bel[i]]+=a[i]; for(int i=1;i<=m;i++)tot+=(sum[i]-ave)*(sum[i]-ave); ans=min(ans,tot); double T=200; while(T>1e-16) { int x=rand()%n+1,mn=1; for(int i=2;i<=m;i++)if(sum[i]<sum[mn])mn=i; double now=tot-(sum[bel[x]]-ave)*(sum[bel[x]]-ave)-(sum[mn]-ave)*(sum[mn]-ave); sum[bel[x]]-=a[x],sum[mn]+=a[x]; now+=(sum[bel[x]]-ave)*(sum[bel[x]]-ave)+(sum[mn]-ave)*(sum[mn]-ave); double delta=now-tot; if(delta<0)tot=now,bel[x]=mn; else if(exp(-delta/T)*RAND_MAX>=rand())tot=now,bel[x]=mn; else sum[bel[x]]+=a[x],sum[mn]-=a[x]; ans=min(ans,tot); T*=0.996; } } int main() { srand(time(NULL)); scanf("%d%d",&n,&m); if(m==1){puts("0.00");return 0;} for(int i=1;i<=n;i++)scanf("%d",&a[i]),ave+=a[i]; ave/=m; ans=1e18; for(int i=1;i<=100;i++)fire(); ans=sqrt(ans/m); printf("%0.2f",ans); }
不清楚还有没有