Lvat_s Blog

新知识get:模拟退火

设置一个温度T，T越小越不随机

然后做个几万遍就可以了。

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
 
double ans=2147483647,average=0;
int n,m,a[10005],sum[10005],zu[10005];
 
void Fire(){
double T=10000,nowans=0;
memset(sum,0,sizeof(sum));
for(int i=1;i<=n;i++){
    zu[i]=rand()%m+1;
    sum[zu[i]]+=a[i];
}
for(int i=1;i<=m;i++){
    nowans+=(sum[i]-average)*(sum[i]-average);
}
while(T>0.1){
    T*=0.9;
    int Nx,Ny,R=rand()%n+1;
    Nx=zu[R];
    if(T>500){
        int sa=2147483647,sb;
        for(int i=1;i<=m;i++){
            if(sa>sum[i]){
                sa=sum[i];
                sb=i;
            }
        }
        Ny=sb;
    }
    else Ny=rand()%m+1;
    if(Nx==Ny)continue;
    double lastans=nowans;
    nowans-=(sum[Nx]-average)*(sum[Nx]-average);
    nowans-=(sum[Ny]-average)*(sum[Ny]-average);
    sum[Nx]-=a[R];
    sum[Ny]+=a[R];
    nowans+=(sum[Nx]-average)*(sum[Nx]-average);
    nowans+=(sum[Ny]-average)*(sum[Ny]-average);
    if(nowans<=lastans){zu[R]=Ny;}
    else {
        if(rand()%10000>T){
            sum[Nx]+=a[R];
            sum[Ny]-=a[R];
            nowans=lastans;
        }
        else {
            zu[R]=Ny;
        }
    }
}
ans=min(nowans,ans);
}
 
int main(){
srand(19990720);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
    scanf("%d",&a[i]);
    average+=a[i];
}
average/=m;
for(int i=1;i<=10000;i++){
    Fire();
}
printf("%.2lf\n",sqrt(ans/m));
return 0;
}

公式: f[i]=3*f[i-1]-f[i-2]+2

我自己是用了三个变量滚动。需要写一个高精度。

#include<cstdio>
#include<cstring>
 
struct Num{
int n,s[100005];
}f1,f2,f3;
 
int n;
 
void Do(){
f3.n=f2.n;
memset(f3.s,0,sizeof(f3.s));
for(int i=0;i<f2.n;i++){
    f3.s[i]+=f2.s[i]*3;
    if(f3.s[i]>9){
        f3.s[i+1]+=f3.s[i]/10;
        f3.s[i]%=10;
    }
}
if(f3.s[f3.n]>0)f3.n++;
//printf("CTest2:%d%d\n",f2.s[0],f2.s[1]);
//printf("CTest3:%d%d\n",f3.s[0],f3.s[1]);
//printf("Test1:%d%d\n",f1.s[0],f1.s[1]);
f3.s[0]+=2-f1.s[0];
//printf("Test3:%d%d\n",f3.s[0],f3.s[1]);
if(f3.s[0]>9){
    f3.s[1]+=f3.s[0]/10;
    //printf("Test:%d%d\n",f3.s[0],f3.s[1]);
    f3.s[0]%=10;
}
else if(f3.s[0]<0){
    f3.s[1]--;
    f3.s[0]+=10;
}
for(int i=1;i<f1.n;i++){
    f3.s[i]-=f1.s[i];
    if(f3.s[i]<0){
        f3.s[i+1]--;
        f3.s[i]+=10;
    }
}
if(f3.s[f3.n-1]==0)f3.n--;
}
 
void Copy(){
f1.n=f2.n;
for(int i=0;i<f2.n;i++){f1.s[i]=f2.s[i];}
f2.n=f3.n;
for(int i=0;i<f3.n;i++){f2.s[i]=f3.s[i];}
}
 
int main(){
freopen("1002.in","r",stdin);
freopen("1002.out","w",stdout);
scanf("%d",&n);
if(n==1){printf("1\n");return 0;}
if(n==2){printf("5\n");return 0;}
f1.n=1;
f1.s[0]=1;
f2.n=1;
f2.s[0]=5;
n-=2;
while(n--){
    Do();
    Copy();
}
for(int i=f2.n-1;i>=0;i--){
    printf("%d",f2.s[i]);
}
putchar('\n');
return 0;
}

据说网络流写得好也能过……orz常数帝们

我自己是看了周冬的论文——他来自芜湖一中。膜拜前辈！orzzzz

S-T图直接最短路就行了，注意建图即可。

#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;

int n,m,en,h[2000005],D[2000005],f[2000005],S,T;

struct Edge{
int b,v,next;
}e[7000005];

struct Node{
int u,v;
bool operator< (const Node &x) const{
return v>x.v?1:0;
}
};

priority_queue<Node> Q;

void add(int sa,int sb,int sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}

void Dijkstra(){
memset(D,120,sizeof(D));
memset(f,0,sizeof(f));
while(!Q.empty())Q.pop();
Node tmp;
tmp.u=S;
D[S]=0;
tmp.v=0;
Q.push(tmp);
while(!Q.empty()){
    int u=Q.top().u;
    Q.pop();
    if(f[u])continue;
    if(u==T){printf("%d\n",D[T]);break;}
    f[u]=1;
    for(int i=h[u];i!=-1;i=e[i].next){
        int v=e[i].b;
        if(!f[v] && D[u]+e[i].v<D[v]){
            D[v]=D[u]+e[i].v;
            tmp.u=v;
            tmp.v=D[v];
            Q.push(tmp);
        }
    }
}
}

void Scanf(int &s){
char x;
while((x=getchar())<'0' || x>'9');
s=x-'0';
while((x=getchar())>='0' && x<='9')s=s*10+x-'0';
}

int main(){
freopen("1001.in","r",stdin);
freopen("1001.out","w",stdout);
Scanf(n);
Scanf(m);
S=0;
T=(n-1)*(m-1)*2+1;
memset(h,-1,sizeof(h));
en=0;
if(n==1 || m==1){
    n=max(n,m);
    int ans=2147483647,w;
    for(int i=1;i<n;i++){
        Scanf(w);
        ans=min(ans,w);
    }
    printf("%d\n",ans==2147483647?0:ans);
    return 0;
}
for(int i=0;i<=n-1;i++){
    for(int j=1;j<=m-1;j++){
        int sa,sb,sc;
        Scanf(sc);
        sa=((i-1)*(m-1)+j)*2-1;
        sb=(i*(m-1)+j)*2;
        if(i==0)sa=T;
        else if(i==n-1)sb=S;
        add(sa,sb,sc);
        add(sb,sa,sc);
    }
}
for(int i=1;i<=n-1;i++){
    for(int j=0;j<=m-1;j++){
        int sa,sb,sc;
        Scanf(sc);
        sa=((i-1)*(m-1)+j)*2;
        sb=((i-1)*(m-1)+j+1)*2-1;
        if(j==0)sa=S;
        else if(j==m-1)sb=T;
        add(sa,sb,sc);
        add(sb,sa,sc);
    }
}
for(int i=1;i<=n-1;i++){
    for(int j=1;j<=m-1;j++){
        int sa,sb,sc;
        Scanf(sc);
        sa=((i-1)*(m-1)+j)*2;
        sb=((i-1)*(m-1)+j)*2-1;
        add(sa,sb,sc);
        add(sb,sa,sc);
    }
}
Dijkstra();
return 0;
}