10.16模拟退火，归并排序，快速排序，洛谷题

模拟退火：

伪代码

eqs=1e-8;//终止温度，接近0，用于控制精度
T=100;//初始温度，应该是高温，以100为例
delta=0.98;//降温系数，控制退火的快慢，比1小
g(x);//状态下时的评价函数
now ,next;//当前状态与新状态
while(T>eps){
    g(next);g(now);//计算能量
    dE=g(next)-g(now);//能量差
    if(dE>=0)//新状态更优，接受新状态
        now = next;
    else if(exp(dE/T)>rand())//如果新状态更差，就在一定概率下接受它
        now = next;
    T*=delta;//降温
}

归并排序：

void Mergesort(int left,int right)
{
    if(left>=right)
        return;
 
    int mid=(left+right)/2;
 
    msort(left,mid);
    msort(mid+1,right);
 
    int i=left,j=mid+1,k=left;
    while(i<=mid&&j<=right)
    {
        if(a[i]>a[j])
        {
            b[k++]=a[j++];
            sum+=mid-i+1;
        }
        else
            b[k++]=a[i++];
    }
    while(i<=mid)
        b[k++]=a[i++];
    while(j<=right)
        b[k++]=a[j++];
    for(i=left;i<=right;i++)
        a[i]=b[i];
}

快速排序：

const int MAXN=100005;
int data[MAXN];
int partition(int left,int right){
    int i=left;
    int temp = data[right];
    for(int j = left;j<right;j++){
        if(data[j]<temp){
            swap(data[i],data[j]);
            i++;
        }
    }
    swap(data[i],data[right]);
    return i;
}
void quicksort(int left,int right){
    if(left<right){
        int i=partition(left,right);
        quicksort(left,i-1);
        quicksort(i+1,right);
    }
}

补题
Codeforces Round #748 (Div. 3) B题
思路：如果一个数被25整除，那么他的最后两位应该是 00 25 50 75.
所以我们可以从一个字符串的尾部查找删除，直到符合条件

#include <bits/stdc++.h>
using namespace std;
const int MAX=0x3f3f3f;
int a[MAX],b[MAX];
int ans;
set<int> s;
 
int main()
{
    int t;
    cin>>t;
    string str;
    while(t--){
        ans=MAX;
        cin>>str;
        int n=str.size();
        for(int i=n-1;i>0;i--)
            for(int j=i-1;j>=0;j--)
        if(((str[i]-'0'+(str[j]-'0')*10)%25==0)||(str[i]-'0'==0&&str[j]-'0'==0)){
            ans=min(ans, n-j-2);
        }
        cout<<ans<<endl;
    }
    return 0;
}

P1018 [NOIP2000 提高组] 乘积最大
今年是国际数学联盟确定的“ 2000 ――世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰 90 周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友 XZ 也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：

设有一个长度为 NN 的数字串，要求选手使用 KK 个乘号将它分成 K+1K+1 个部分，找出一种分法，使得这 K+1K+1 个部分的乘积能够为最大。

同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：

有一个数字串：312312， 当 N=3,K=1N=3,K=1 时会有以下两种分法：

3 \times 12=363×12=36
31 \times 2=6231×2=62
这时，符合题目要求的结果是: 31 \times 2 = 6231×2=62

现在，请你帮助你的好朋友 XZ 设计一个程序，求得正确的答案。

思路：自己用int long long 都是不行，所以这个是一个高精度+dp的题目，我们先让乘号都放在最左边，然后依次往右放，如果有更大的就更新。利用一个三重循环，第一重为从第1个数到第n个数，第二重为从1个乘号到第n个乘号，第三重是考虑最后一个乘号究竟放哪。初始化就是定义一个二维数组,dp[i][j]表示前i个数j个乘号时的最大值，利用substr函数即可；

代码：

#include<bits/stdc++.h>
using namespace std;
string str;
string dp[50][10];
string mul(string a,string b)//高精度乘法a,b,均为非负整数
{
    if(a=="0"||b=="0")return "0";
    string s;
    int na[20005]={0},nb[20005]={0},nc[40005]={0},La=a.size(),Lb=b.size();//na存储被乘数，nb存储乘数，nc存储积
    //fill(na,na+200,0);fill(nb,nb+200,0);fill(nc,nc+200,0);//将na,nb,nc都置为0
    for(int i=La-1;i>=0;i--) na[La-i]=a[i]-'0';//将字符串表示的大整形数转成i整形数组表示的大整形数
    for(int i=Lb-1;i>=0;i--) nb[Lb-i]=b[i]-'0';
    for(int i=1;i<=La;i++)
        for(int j=1;j<=Lb;j++)
        nc[i+j-1]+=na[i]*nb[j];//a的第i位乘以b的第j位为积的第i+j-1位（先不考虑进位）
    for(int i=1;i<=La+Lb;i++)
        nc[i+1]+=nc[i]/10,nc[i]%=10;//统一处理进位
    if(nc[La+Lb]) s+=nc[La+Lb]+'0';//判断第i+j位上的数字是不是0
    for(int i=La+Lb-1;i>=1;i--)s+=nc[i]+'0';//将整形数组转成字符串

    return s;
}

string max(string a,string b){
    int la=a.size(),lb=b.size();
    if(la!=lb)return la>lb?a:b;
    for(int i=0;i<la;i++)if(a[i]!=b[i])return a[i]>b[i]?a:b;
    return a;
}

int main()
{
    int n,k;
    cin>>n>>k;
    cin>>str;
    int len;
    memset(dp,0,sizeof(dp));
    for(int i=0;i<n;i++){
        dp[i][0]=str.substr(0,i+1);
    }
    for(int i=0;i<n;i++){
        for(int j=1;j<=k;j++)
            for(int f=j-1;f<i;f++){
                dp[i][j]=max(dp[i][j],mul(dp[f][j-1],str.substr(f+1,i-f)));

        }
    }
    /*for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++)
        cout<<dp[i][j]<<" ";
        cout<<endl;
    }*/

    cout<<dp[n-1][k]<<endl;
  	return 0;
}

P1300 城市街道交通费系统（DFS+剪枝）
城市街道交费系统最近创立了。一辆汽车左转一次需付费 11 ，右转一次需付费 55 。只有当前进、左转、右转都无路可走的时候，调头才是允许的，调头每次付费 1010 。

给出一张城市地图，要求你求出从起始点到达终止点的花费最少的路径。幸运的是，所有的道路都是正北、正南、正西或正东方向的。

思路：一看就是深搜，然后运行失败，然后想到如果从各个方向都能走到一个点上，那么花费高的那条路和后续操作就不用进行了，然后，这个有个小技巧，我把上下左右设置为0，1，2，3.然后进行向左向右向后运动时，得到的结果总是不同的，所以
int fx=cx+dis[f][0],fy=cy+dis[f][1];//直行
int lf=(f+1)%4,lx=cx+dis[lf][0],ly=cy+dis[lf][1];//右转
int bf=(f+2)%4,bx=cx+dis[bf][0],by=cy+dis[bf][1];//掉头
int rf=(f+3)%4,rx=cx+dis[rf][0],ry=cy+dis[rf][1];//左转
这样就可以避免繁琐的if else

代码：

#include<bits/stdc++.h>
using namespace std;
char a[51][51];
int dx,dy,f,cx,cy,n,m;
int val[50][50][4];
int ans=0x3f3f3f;
int dis[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
bool judge(int i,int j){
if(i<1||i>n||j<0||j>m)
    return false;
if(a[i][j]=='.')
    return false;
    return true;
}
void DFS(int cx,int cy,int f,int cost){
    if(cost>=val[cx][cy][f])
        return;
    val[cx][cy][f]=cost;
    //    cout<<cost<<" ";
    if(cx==dx&&cy==dy){
        ans=min(cost,ans);
        return;
    }
        bool flog=0;
        int fx=cx+dis[f][0],fy=cy+dis[f][1];//直行
    int lf=(f+1)%4,lx=cx+dis[lf][0],ly=cy+dis[lf][1];//左转
    int bf=(f+2)%4,bx=cx+dis[bf][0],by=cy+dis[bf][1];//掉头
    int rf=(f+3)%4,rx=cx+dis[rf][0],ry=cy+dis[rf][1];//右转
    if(judge(fx,fy)) flog=1,DFS(fx,fy,f,cost);//直行
    if(judge(lx,ly)) flog=1,DFS(lx,ly,lf,cost+1);//左转
    if(judge(rx,ry)) flog=1,DFS(rx,ry,rf,cost+5);//右转
    if(judge(bx,by)&&!flog) DFS(bx,by,bf,cost+10);//掉头
}
    /*while(cx!=dx&&cy!=dy){
            int flag=true;
        for(int i=0;i<4;i++){
            int fx=cx+dir[i][0];
            int fy=cy+dir[i][1];
            if(judge(fx,fy)){
                if(i==f){
                    DFS(fx,fy,i);
                    flag=false;
                }
                if(f==0&&i==1){
                    val[fx][fy]+=(val[cx][cy]+5);
                    DFS(fx,fy,i);
                    flag=false;
                }
                if(f==0&&i==3){
                    val[fx][fy]+=(val[cx][cy]+1);
                    flag=false;
                }
                if(f==1&&i==0){
                    val[fx][fy]+=(val[cx][cy]+1);
                    DFS(fx,fy,i);
                    flag=false;
                }
                if(f==1&&i==2){
                    val[fx][fy]+=(val[cx][cy]+5);
                    DFS(fx,fy,i);
                    flag=false;
                }
                if(f==2&&i==1){
                    val[fx][fy]+=(val[cx][cy]+1);
                    DFS(fx,fy,i);
                    flag=false;
                }
                if(f==2&&i==3){
                    val[fx][fy]+=(val[cx][cy]+5);
                    DFS(fx,fy,i);
                    flag=false;
                }
                if(f==3&&i==2){
                    val[fx][fy]+=(val[cx][cy]+1);
                    DFS(fx,fy,i);
                    flag=false;
                }
                if(f==3&&i==0){
                    val[fx][fy]+=(val[cx][cy]+5);
                    DFS(fx,fy,i);
                    flag=false;
                }
                if(flag){
                    val[fx][fy]+=(val[cx][cy]+10);
                    DFS(fx,fy,i);
                }
            }
        }
    }*/

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
        cin>>a[i][j];
        if(a[i][j]=='N'){
            f=0;
            cx=i;
            cy=j;
        }
        else if(a[i][j]=='S'){
            f=2;
            cx=i;
            cy=j;
        }
        else if(a[i][j]=='W'){
            f=1;
            cx=i;
            cy=j;
        }
        else if(a[i][j]=='E'){
            f=3;
            cx=i;
            cy=j;
        }
        if(a[i][j]=='F'){
            dx=i;
            dy=j;
        }
    }
    //cout<<cx<<" "<<cy<<endl;
    memset(val,0x3f,sizeof(val));
    DFS(cx,cy,f,0);
    cout<<ans;
	return 0;
}

P1301 魔鬼之城
在一个被分割为N*M个正方形房间的矩形魔鬼之城中，一个探险者必须遵循下列规则才能跳跃行动。他必须从(1, 1)进入，从(N, M)走出；在每一房间的墙壁上都写了一个魔法数字，是1～13之内的自然数；探险者可以想像出8个方向中的任何一个(水平或垂直或对角线方向)，随后他就可以作一次空间跳跃穿过这一方向上的连续的X个房间，其中X是他原来所在房间的魔法数字。但如果在这一方向上的房间数小于X，则他不作任何跳跃，而必须想像另一个方向。同时，探险者不能作连续两次相同方向的跳跃。

例如在上图的5*4的魔鬼之城中，如果探险者现在所在的位置是(3, 3)，那么通过依次空间跳跃他可以到达下列房间中的一个：(1, 1)，(3, 1)，(1, 3)，(5, 1)，或(5, 3)。另外，如果他要用两次跳跃从(5, 4)到达(3, 2)，则他不能首先跳到(4, 3)(因为这样他第二次跳跃的方向将和第一次相同，而这是不允许的)。所以他必须先跳跃到(2, 1)。

请你写一个程序，对给定的地图，算出探险者至少需要跳跃多少步才能离开魔鬼之城。

思路：和上题相似，只不过多了四个方向，然后用BFS做的，利用的BFS模板

#include<bits/stdc++.h>
using namespace std;
int a[120][120];
int n,m;
int f[100000][9];
int ans[120][120];
int mv1[8]={1,1,-1,-1,1,-1,0,0};
int mv2[8]={0,1,-1,0,-1,1,-1,1};
bool use[1000][1000][9];
int dir[8][2]={{-1,0},{0,-1},{1,0},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};
void BFS(){
     int x=1,y=1;
     f[x][0]=1;
     f[x][1]=1;
     f[x][3]=-1;
    while(x<=y){
        for(int i=0;i<8;i++){
            if(i!=f[x][3]){
            int nowx=f[x][0]+dir[i][0]*a[f[x][0]][f[x][1]];
            int nowy=f[x][1]+dir[i][1]*a[f[x][0]][f[x][1]];
            if(nowx<1||nowx>m||nowy<1||nowy>n) continue;
            if(!use[nowx][nowy][i]){
                use[nowx][nowy][i]=1;
                ans[nowx][nowy]=f[x][2]+1;
                y++;
                f[y][0]=nowx;
                f[y][1]=nowy;
                f[y][2]=ans[nowx][nowy];
                f[y][3]=i;
                }
            }
            if(ans[m][n]>0)
                return;
        }
        x++;
    }
    return;
}
int main()
{
    //memset(ans,-1,sizeof(ans));
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
        cin>>a[i][j];
    //ans[1][1]=0;
    BFS();
    if(ans[m][n]>0)
        cout<<ans[m][n];
    else
        cout<<"NEVER";
	return 0;
}

这几天也在思考，以后准备按照自己的进度学习，刷专题，然后有空就去div3提高代码能力。