社区讨论

关于退火为啥跑不过三分

P7913[CSP-S 2021] 廊桥分配参与者 10已保存回复 22

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
22 条
当前快照
1 份
快照标识符
@lobeya9x
此快照首次捕获于
2023/10/29 19:54
2 年前
此快照最后确认于
2023/11/04 01:29
2 年前
查看原帖
RT 听说三分可以直接日掉95pts 我内心:这我退火不是随便过?
写完之后:50 tle
有无神仙看看怎么优化优化退火过程或者帮忙调调参啥的/kel
CPP
#include<bits/stdc++.h>
using namespace std;
int n,m1,m2,ansx,nowans;
pair<int,int>a[2][100005];
double eps=1e-18;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>s;
inline int f(int x){//稳定的O((m1+m2)log(m1+m2))的统计答案
    if(x<0||x>n)return 0;
    int ans=0;
    for(int i=1;i<=m1;i++){
        while(s.size()&&s.top().first<a[0][i].first)s.pop();
        if(s.size()<x)s.push(make_pair(a[0][i].second,i)),ans++;
    }
    while(!s.empty())s.pop();
    for(int i=1;i<=m2;i++){
        while(s.size()&&s.top().first<a[1][i].first)s.pop();
        if(s.size()<n-x)s.push(make_pair(a[1][i].second,i)),ans++;
    }
    while(!s.empty())s.pop();
    return ans;
}
inline void mnth(){//退火过程
    double T=200;
    while(T>eps){
        int nx=(ansx+(int)((rand()*2-RAND_MAX)*T))%n;
        int qxe=f(ansx)-f(nx);
        T*=0.88;
        if(qxe<0){ansx=nx;continue;}
        if(exp(-qxe/T)*RAND_MAX>rand())ansx=nx;
    }
    cout<<max(max(f(ansx),f(0)),f(n));
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
    cin>>n>>m1>>m2;
    for(int i=1;i<=m1;i++)cin>>a[0][i].first>>a[0][i].second;
    for(int i=1;i<=m2;i++)cin>>a[1][i].first>>a[1][i].second;
    sort(a[0]+1,a[0]+m1+1);
    sort(a[1]+1,a[1]+m2+1);
    mnth();
    // cout<<f(1);
    return 0;
}
我自己进行的调参尝试包括0.88->0.7,对T在不同范围内按不同参数退火等,总之就是或者T或者WA
球球了,救救退火都写不对的孩子吧/kel

回复

22 条回复,欢迎继续交流。

正在加载回复...