题意:

给你一个每项系数都不超过2的多项式..

求每个数的取值使得整个多项式值最大

每个数只允许在[0,1]之间

做法:

模拟退火..

先看一发提交记录冷静下

Jun/18/2016 04:15  Wrong answer on test 9 → 18568836
Jun/18/2016 04:17  Wrong answer on test 9 → 18568861
Jun/18/2016 04:26  Wrong answer on test 9 → 18568934
Jun/18/2016 04:26  Wrong answer on test 5 → 18568935
Jun/18/2016 04:26  Wrong answer on test 8 → 18568939
Jun/18/2016 04:26  Wrong answer on test 7 → 18568942
Jun/18/2016 04:26  Wrong answer on test 7 → 18568946
Jun/18/2016 04:26  Wrong answer on test 8 → 18568950
Jun/18/2016 04:27  Wrong answer on test 9 → 18568952
Jun/18/2016 04:27  Wrong answer on test 9 → 18568957
Jun/18/2016 04:27  Wrong answer on test 9 → 18568958
Jun/18/2016 07:41  Time limit exceeded on test 1 → 18571278
Jun/18/2016 07:42  Time limit exceeded on test 1 → 18571289
Jun/18/2016 07:42  Wrong answer on test 7 → 18571296
Jun/18/2016 07:43  Wrong answer on test 7 → 18571302
Jun/18/2016 07:44  Wrong answer on test 9 → 18571314
Jun/18/2016 07:51  Wrong answer on test 9 → 18571398
Jun/18/2016 07:55  Time limit exceeded on test 5 → 18571456
Jun/18/2016 07:55  Wrong answer on test 9 → 18571461
Jun/18/2016 07:55  Wrong answer on test 9 → 18571467
Jun/18/2016 07:56  Wrong answer on test 9 → 18571473
Jun/18/2016 07:57  Wrong answer on test 9 → 18571488
Jun/18/2016 07:59  Wrong answer on test 9 → 18571505
Jun/18/2016 08:00  Wrong answer on test 9 → 18571531
Jun/18/2016 08:04  Wrong answer on test 7 → 18571574
Jun/18/2016 08:04  Wrong answer on test 7 → 18571576
Jun/18/2016 08:12  Time limit exceeded on test 7 → 18571677
Jun/18/2016 08:13  Time limit exceeded on test 9 → 18571684
Jun/18/2016 08:13  Time limit exceeded on test 9 → 18571693
Jun/18/2016 08:13  Time limit exceeded on test 9 → 18571696
Jun/18/2016 08:13  Time limit exceeded on test 9 → 18571698
Jun/18/2016 08:13  Wrong answer on test 9 → 18571702
Jun/18/2016 08:56  Wrong answer on test 7 → 18572318
Jun/18/2016 08:57  Wrong answer on test 7 → 18572324
Jun/18/2016 18:04  Wrong answer on test 9 → 18581926
Jun/18/2016 18:04  Wrong answer on test 9 → 18581938
Jun/18/2016 18:05  Time limit exceeded on test 1 → 18581942
Jun/18/2016 18:05  Time limit exceeded on test 1 → 18581948
Jun/18/2016 18:06  Wrong answer on test 9 → 18581971
Jun/18/2016 18:07  Wrong answer on test 9 → 18581985
Jun/18/2016 18:12  Wrong answer on test 9 → 18582075
Jun/18/2016 18:13  Wrong answer on test 9 → 18582093
Jun/18/2016 18:14  Wrong answer on test 7 → 18582106
Jun/18/2016 18:14  Time limit exceeded on test 7 → 18582115
Jun/18/2016 18:15  Wrong answer on test 9 → 18582128
Jun/18/2016 18:15  Wrong answer on test 9 → 18582138
Jun/18/2016 18:16  Wrong answer on test 7 → 18582157
Jun/18/2016 18:17  Wrong answer on test 1 → 18582169
Jun/18/2016 18:17  Wrong answer on test 7 → 18582179
Jun/18/2016 18:18  Wrong answer on test 7 → 18582187
Jun/18/2016 18:18  Wrong answer on test 9 → 18582193
Jun/18/2016 18:19  Wrong answer on test 9 → 18582205
Jun/18/2016 18:19  Wrong answer on test 9 → 18582218
Jun/18/2016 18:19  Wrong answer on test 9 → 18582227
Jun/18/2016 18:29  Wrong answer on test 9 → 18582404
Jun/18/2016 18:34  Wrong answer on test 9 → 18582511
Jun/18/2016 18:34  Wrong answer on test 9 → 18582519
Jun/18/2016 18:35  Wrong answer on test 9 → 18582547
Jun/18/2016 18:36  Wrong answer on test 9 → 18582564
Jun/18/2016 18:36  Wrong answer on test 9 → 18582573
Jun/18/2016 18:37  Wrong answer on test 9 → 18582581
Jun/19/2016 08:22  Wrong answer on test 9 → 18591248
Jun/19/2016 08:22  Wrong answer on test 9 → 18591250
Jun/19/2016 08:27  Time limit exceeded on test 5 → 18591302
Jun/19/2016 08:28  Wrong answer on test 9 → 18591305
Jun/19/2016 08:29  Wrong answer on test 9 → 18591323
Jun/19/2016 08:29  Wrong answer on test 9 → 18591328
Jun/19/2016 08:30  Wrong answer on test 9 → 18591330
Jun/19/2016 08:30  Wrong answer on test 9 → 18591335
Jun/19/2016 08:32  Wrong answer on test 9 → 18591351
Jun/19/2016 08:33  Wrong answer on test 9 → 18591366
Jun/19/2016 08:33  Wrong answer on test 9 → 18591372
Jun/19/2016 08:34  Wrong answer on test 9 → 18591380
Jun/19/2016 08:34  Wrong answer on test 9 → 18591383
Jun/19/2016 08:34  Wrong answer on test 9 → 18591390
Jun/19/2016 08:35  Wrong answer on test 9 → 18591392
Jun/19/2016 08:36  Wrong answer on test 9 → 18591410
Jun/19/2016 08:36  Wrong answer on test 9 → 18591413
Jun/19/2016 08:37  Time limit exceeded on test 1 → 18591418
Jun/19/2016 08:37  Wrong answer on test 9 → 18591426
Jun/19/2016 08:39  Wrong answer on test 9 → 18591449
Jun/19/2016 08:40  Wrong answer on test 9 → 18591454
Jun/19/2016 08:44  Wrong answer on test 7 → 18591491
Jun/19/2016 08:44  Time limit exceeded on test 1 → 18591493
Jun/19/2016 08:44  Wrong answer on test 7 → 18591499
Jun/19/2016 08:45  Time limit exceeded on test 1 → 18591506
Jun/19/2016 08:45  Time limit exceeded on test 1 → 18591510
Jun/19/2016 08:46  Wrong answer on test 9 → 18591515
Jun/19/2016 08:48  Wrong answer on test 9 → 18591543
Jun/19/2016 08:48  Wrong answer on test 7 → 18591549
Jun/19/2016 08:49  Time limit exceeded on test 1 → 18591555
Jun/19/2016 08:49  Wrong answer on test 9 → 18591562
Jun/19/2016 08:51  Wrong answer on test 9 → 18591578
Jun/19/2016 08:52  Time limit exceeded on test 5 → 18591592
Jun/19/2016 08:53  Time limit exceeded on test 5 → 18591599
Jun/19/2016 08:53  Wrong answer on test 8 → 18591607
Jun/19/2016 08:54  Wrong answer on test 8 → 18591612
Jun/19/2016 08:54  Wrong answer on test 8 → 18591614
Jun/19/2016 08:54  Wrong answer on test 9 → 18591617
Jun/19/2016 08:56  Wrong answer on test 9 → 18591632
Jun/19/2016 08:56  Wrong answer on test 9 → 18591639
Jun/19/2016 10:18  Compilation error → 18592774
Jun/19/2016 10:19  Wrong answer on test 9 → 18592786
Jun/19/2016 10:23  Wrong answer on test 9 → 18592860
Jun/19/2016 10:28  Wrong answer on test 9 → 18592924
Jun/19/2016 10:29  Wrong answer on test 9 → 18592947
Jun/19/2016 10:30  Wrong answer on test 9 → 18592961
Jun/19/2016 11:13  Wrong answer on test 9 → 18593607
Jun/19/2016 11:18  Compilation error → 18593671
Jun/19/2016 11:19  Compilation error → 18593680
Jun/19/2016 11:20  Wrong answer on test 9 → 18593693
Jun/19/2016 11:20  Compilation error → 18593700
Jun/19/2016 11:21  Accepted → 18593706
Jun/19/2016 11:23  Wrong answer on test 9 → 18593751
Jun/19/2016 11:24  Accepted → 18593759
Jun/19/2016 11:31  Wrong answer on test 1 → 18593892
Jun/19/2016 11:43  Wrong answer on test 3 → 18594112
Jun/19/2016 11:44  Wrong answer on test 9 → 18594142
Jun/19/2016 11:52  Wrong answer on test 9 → 18594259
Jun/19/2016 11:52  Wrong answer on test 9 → 18594265
Jun/19/2016 11:54  Wrong answer on test 9 → 18594298
Jun/19/2016 11:58  Wrong answer on test 9 → 18594367
Jun/19/2016 14:22  Wrong answer on test 9 → 18596711
Jun/19/2016 14:24  Compilation error → 18596745
Jun/19/2016 14:24  Wrong answer on test 1 → 18596755
Jun/19/2016 14:24  Accepted → 18596761
Jun/19/2016 14:30  Accepted → 18596849
Jun/19/2016 14:34  Wrong answer on test 9 → 18596914
Jun/19/2016 14:47  Wrong answer on test 9 → 18597084
Jun/19/2016 14:56  Wrong answer on test 9 → 18597204
Jun/19/2016 15:00  Wrong answer on test 9 → 18597249
Jun/19/2016 15:55  Wrong answer on test 9 → 18598101
Jun/19/2016 15:56  Wrong answer on test 9 → 18598110
Jun/19/2016 15:57  Wrong answer on test 9 → 18598134
Jun/19/2016 16:10  Wrong answer on test 1 → 18598342
Jun/19/2016 16:12  Wrong answer on test 9 → 18598369
Jun/19/2016 16:12  Accepted → 18598375
Jun/19/2016 16:16  Wrong answer on test 9 → 18598422
Jun/19/2016 16:20  Wrong answer on test 9 → 18598502
Jun/19/2016 16:24  Accepted → 18598565
Jun/19/2016 16:26  Wrong answer on test 9 → 18598594
Jun/19/2016 16:32  Wrong answer on test 9 → 18598695
Jun/19/2016 16:48  Wrong answer on test 9 → 18599381
Jun/19/2016 16:55  Wrong answer on test 9 → 18599506
Jun/19/2016 17:06  Wrong answer on test 9 → 18599719
Jun/19/2016 17:08  Accepted → 18599774
Jun/19/2016 17:10  Wrong answer on test 9 → 18599796
Jun/19/2016 17:14  Wrong answer on test 9 → 18599866
Jun/19/2016 17:15  Wrong answer on test 9 → 18599886
Jun/19/2016 17:16  Wrong answer on test 9 → 18599915
Jun/19/2016 17:17  Accepted → 18599923
Jun/19/2016 17:18  Accepted → 18599959
Jun/19/2016 17:18  Accepted → 18599960

我们要知道..在17:08之前的所有AC都是yjz的代码..

也就是说..我一共爆炸了146次才过的..总共提交超过150次已突破天际

模拟退火的做法:

每次设定一个初始的温度T(这一题我选的是[tex]T=10^{-2}[/tex],也就是说大概比氦的熔点还要低不少..)

每次随机一个相邻的节点,如果到达这个节点答案更优,也就是说在物化上叫做"势能减少",从激发态到达基态,我们就让它跃迁并放出能量,假设能量扩散对温度变化不大,也就是温度不增加(在我的做法中,这一步温度并不下降,因为这是个放热过程)

用OI的话,叫做更新答案..

如果这个节点答案不是更优,也就是说这是需要吸收能量,从基态到激发态,所以它就有概率跃迁并且吸收能量

说清楚点,是[tex]e^{-\frac{\Delta E}{TK}}[/tex]的概率跃迁并且吸收能量

这是根据化学反应平衡移动原理,温度升高,反应趋向于吸热移动;温度降低,反应趋向于放热移动,这时候我们考虑它吸收了能量,所以执行一次降温操作

那么这样下去

这题中,我的做法是这个转移的状态的delta在每次操作后*0.99,而每次吸热后温度*0.99

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
char a[10005];
double t;
map<char,int> ma;
double xy[15][15];
double xx[15];
double cst=0;
double ans[15];
double best_ans[15];
double best_val;
char mas[15];
int cnt=0;
const double e=2.7182818284590452353602874713527;
double cur_ans;
void try_best_ans(double delta)
{
    if (delta<1e-7) return;
    int i;
    static int val[25];
    int num=0;
    for (i=0;i<cnt;i++)
    {
        if (ans[i]+delta<=1)
        {
            val[num++]=i*2;
        }
        if (ans[i]-delta>=0)
        {
            val[num++]=i*2+1;
        }
    }
    int k=rand()%num;
    double new_ans=cur_ans;
    int chosen=val[k]/2;
    double newans=ans[chosen];
    if (val[k]%2==0) newans+=delta; else newans-=delta;
    for (i=0;i<cnt;i++)
    {
        new_ans-=xy[chosen][i]*ans[chosen]*ans[i];
        if (chosen==i)
        {
            new_ans+=xy[chosen][i]*newans*newans;
        }
        else
        {
            new_ans+=xy[chosen][i]*newans*ans[i];
        }
    }
    if (val[k]%2==0) new_ans+=delta*xx[chosen]; else new_ans-=delta*xx[chosen];
    if (new_ans>cur_ans)
    {
        if (val[k]%2==0) ans[chosen]+=delta; else ans[chosen]-=delta;
        cur_ans=new_ans;
        if (cur_ans>best_val)
        {
            best_val=cur_ans;
            for (i=0;i<cnt;i++)
            {
                best_ans[i]=ans[i];
            }
        }
        delta*=0.99;
    }
    else
    {
        if (pow(e,(new_ans-cur_ans)/t)*RAND_MAX>rand())
        {
            if (val[k]%2==0) ans[chosen]+=delta; else ans[chosen]-=delta;
            cur_ans=new_ans;
        }
        delta*=0.99;
        t*=0.99;
    }
    try_best_ans(delta);
}
int main()
{
    freopen("formula1.in","r",stdin);
    freopen("formula1.out","w",stdout);
    scanf("%s",a);
    int i;
    for (i=0;a[i]!='\0';i++)
    {
        if ((a[i]>='a')&&(a[i]<='z')&&(ma.find(a[i])==ma.end()))
        {
            ma[a[i]]=cnt++;
            mas[cnt-1]=a[i];
        }
    }
    if (ma.find('e')!=ma.end())
    {
        for (i='a';i<='z';i++)
        {
            if (ma.find(i)==ma.end())
            {
                int j;
                for (j=0;a[j]!='\0';j++)
                {
                    if (a[j]=='e') a[j]=i;
                }
                ma[i]=ma['e'];
                break;
            }
        }
    }
    int tag=1;
    i=0;
    if (a[0]=='-')
    {
        tag=-1;
        i=1;
    }
    for (;;)
    {
        double x=1;
        sscanf(a+i,"%lf",&x);
        x*=tag;
        for (;(a[i]=='.')||((a[i]>='0')&&(a[i]<='9'));i++) ;
        if ((a[i]>='a')&&(a[i]<='z'))
        {
            if (a[i+1]=='^')
            {
                xy[ma[a[i]]][ma[a[i]]]+=x;
                i+=3;
            }
            else if ((a[i+1]>='a')&&(a[i+1]<='z'))
            {
                xy[ma[a[i]]][ma[a[i+1]]]+=x;
                xy[ma[a[i+1]]][ma[a[i]]]+=x;
                i+=2;
            }
            else
            {
                xx[ma[a[i]]]+=x;
                i++;
            }
        }
        else
        {
            cst+=x;
        }
        if (a[i]=='+')
        {
            tag=1;
        }
        else if (a[i]=='-')
        {
            tag=-1;
        }
        else
        {
            break;
        }
        i++;
    }
    best_val=cst;
    int j;
    if (cnt==0)
    {
        printf("%.6lf\n",cst);
        return 0;
    }
    for (j=0;j<1000;j++)
    {
        for (i=0;i<cnt;i++)
        {
            ans[i]=0;
        }
        cur_ans=cst;
        t=0.01;
        try_best_ans(0.5);
    }
    printf("%.6lf\n",best_val);
    for (i=0;i<cnt;i++)
    {
        printf("%c=%.6lf\n",mas[i],best_ans[i]);
    }
    return 0;
}

所以..两个WA点

1,Test 9有一种非常可怕的数据,里面有形如这样的东西

[tex]1.03e-3[/tex]

这东西讲道理的话我们可以这么理解:

[tex]1.03 * e - 3[/tex]

但是它不讲道理啊..所以它是这么理解的

[tex]1.03*10^{-3}[/tex]

所以我们要把所有e全换掉..

还有一个WA点是..

我把RAND_MAX打成INT_MAX了..

然后..

我就跟着yjz的代码改了好久..

解法和之前有些区别..比如delta固定化,精确答案而不是多次退火,温度取冰的熔点而不是比氦的熔点还低的温度等等..

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
char a[10005];
long double t;
map<char,int> ma;
double xy[15][15];
double xx[15];
double cst=0;
double ans[15];
double best_ans[15];
double best_val;
char mas[15];
int cnt=0;
const double e=2.7182818284590452353602874713527;
double cur_ans;
double deltas[25]={0.3,0.1,0.003,0.001,0.00003,0.00001,0.03,0.01,0.0003,0.0001,0.000003,0.000001};
const double eps=1e-10;
const int rand_max=100000007;
inline int random()
{
    static int now=2011719;
    now=(now*19+199903)%100000007;
    return now;
}
double calc()
{
    int i;
    double anses=cst;
    for (i=0;i<cnt;i++)
    {
        anses+=ans[i]*xx[i];
        int j;
        for (j=i;j<cnt;j++)
        {
            anses+=ans[i]*ans[j]*xy[i][j];
        }
    }
    return anses;
}
void try_best_ans(int counts)
{
    int flag=0;
    for (;;)
    {
        if (counts>500000) return;
        double delta=deltas[random()%6+flag];
        if (counts%1000==0) cur_ans=calc();
        if (random()%2) delta=-delta;
        flag^=6;
        int i;
        int k=random()%cnt;
        if ((ans[k]+delta>1+eps)||(ans[k]+delta<0-eps)) delta=-delta;
        double new_ans=cur_ans;
        int chosen=k;
        double newans=ans[chosen];
        newans+=delta;
        for (i=0;i<cnt;i++)
        {
            if (chosen==i)
            {
                new_ans+=xy[chosen][i]*ans[i]*delta*2;
                new_ans+=xy[chosen][i]*delta*delta;
            }
            else
            {
                new_ans+=xy[chosen][i]*ans[i]*delta;
            }
        }
        new_ans+=delta*xx[chosen];
        if (new_ans>cur_ans)
        {
            ans[chosen]+=delta;
            if (new_ans>best_val)
            {
                best_val=new_ans;
                for (i=0;i<cnt;i++)
                {
                    best_ans[i]=ans[i];
                }
            }
            cur_ans=new_ans;
            t*=0.9999;
        }
        else
        {
            if (exp((new_ans-cur_ans)/t)*rand_max>random())
            {
                ans[chosen]+=delta;
                cur_ans=new_ans;
            }
            counts++;
            t*=0.9999;
        }
    }
}
int main()
{
    freopen("formula1.in","r",stdin);
    freopen("formula1.out","w",stdout);
    srand(2011719);
    scanf("%s",a);
    int i;
    for (i=0;a[i]!='\0';i++)
    {
        if ((a[i]>='a')&&(a[i]<='z')&&(ma.find(a[i])==ma.end()))
        {
            ma[a[i]]=cnt++;
            mas[cnt-1]=a[i];
        }
    }
    if (ma.find('e')!=ma.end())
    {
        for (i='a';i<='z';i++)
        {
            if (ma.find(i)==ma.end())
            {
                int j;
                for (j=0;a[j]!='\0';j++)
                {
                    if (a[j]=='e') a[j]=i;
                }
                ma[i]=ma['e'];
                break;
            }
        }
    }
    int tag=1;
    i=0;
    if (a[0]=='-')
    {
        tag=-1;
        i=1;
    }
    for (;;)
    {
        double x=1;
        sscanf(a+i,"%lf",&x);
        x*=tag;
        for (;(a[i]=='.')||((a[i]>='0')&&(a[i]<='9'));i++) ;
        if ((a[i]>='a')&&(a[i]<='z'))
        {
            if (a[i+1]=='^')
            {
                xy[ma[a[i]]][ma[a[i]]]+=x;
                i+=3;
            }
            else if ((a[i+1]>='a')&&(a[i+1]<='z'))
            {
                xy[ma[a[i]]][ma[a[i+1]]]+=x;
                xy[ma[a[i+1]]][ma[a[i]]]+=x;
                i+=2;
            }
            else
            {
                xx[ma[a[i]]]+=x;
                i++;
            }
        }
        else
        {
            cst+=x;
        }
        for (;;)
        {
            if (a[i]=='+')
            {
                tag=1;
            }
            else if (a[i]=='-')
            {
                tag=-1;
            }
            else
            {
                break;
            }
            i++;
        }
        if (a[i]=='\0') break;
    }
    best_val=cst;
    int j;
    if (cnt==0)
    {
        printf("%.9lf\n",(double)cst);
        return 0;
    }
    for (j=0;j<5;j++)
    {
        for (i=0;i<cnt;i++)
        {
            ans[i]=0;
        }
        cur_ans=cst;
        t=273.15;
        try_best_ans(0);
    }
    printf("%.9lf\n",(double)best_val);
    for (i=0;i<cnt;i++)
    {
        printf("%c=%.9lf\n",mas[i],(double)best_ans[i]);
    }
    return 0;
}