love_yyc @ 2022-10-26 09:02:14
在模拟退火的题单里看到了他，但是不会，求助这道题怎么退火啊 qwq
by Demeanor_Roy @ 2022-10-26 09:14:27
@love_yyc
这应该是退火经典题型了吧！
你可以初始得到一个随机值，计算A+B与其的差，每次在当前解的基础上扰动，如果新值与A+B的差更小就接受它，否则以一定概率接受它，多退火几次就行了。
其实这道题还有扩展，你可以证明它是单谷函数，用三分解决！
by Buried_Dream @ 2022-10-26 09:14:34
/*
work by: TLE_Automation
Time: O(TLE)
knowledge: SA
*/
#include<bits/stdc++.h>
#define TLE std
#define int long long
#define Min(x, y) (x > y ? y : x);
#define Max(x, y) (x > y ? x : y);
using namespace TLE;
const int maxn = 3e6;
const int MAXN = 3e3;
const double down = 0.996;
const double limit = 1e-10;
inline int read() {
int s = 0, w = 1;
char ch = getchar();
while (!isdigit(ch)) {if(ch == '-') {w = -1;}ch = getchar();}
while (isdigit(ch)) {s = (s << 1) + (s << 3) + (ch ^ 48);ch = getchar();}
return s * w;
}
inline void print(int x) {
if (x < 0 ) putchar('-'), x = -x;
if (x > 9 ) print(x / 10);
putchar(x % 10 + '0');
}
int a, b, ans, num;
int calc(int x) {
return abs(a + b - x) - abs(a + b - ans);
}
int js = 0;
void SA() {
double T = 10;
while(T > limit) {
int x = num + ((rand() << 1) - RAND_MAX) * T;
int del = calc(x);
if(del < 0) {
ans = x;
num = x;
}
else if(exp(-del / T) > (double) rand() / RAND_MAX) num = x;
T *= down;
}
}
signed main() {
a = read(), b = read();
for(int i = 1; i <= 7; i++) SA();
printf("%lld\n", ans);
return 0;
}by love_yyc @ 2022-10-26 09:16:40
感谢各位巨佬
虽然不明白为什么都算出 a+b 了还要用退火
by freedom_wang @ 2022-10-26 09:26:51
大家其实都在魔怔
by eight8 @ 2022-10-26 09:29:24
@love_yyc 万一你不会加法只会减法可以把calc改掉，不用加法（雾
int calc(int x)
{
return abs(x-a-b)-abs(ans-a-b);
} by love_yyc @ 2022-10-26 09:46:03
@eight8
by a2lyaXNhbWUgbWFyaXNh @ 2022-10-26 12:46:12
@love_yyc 如果退火掌握的没有图论好，可以试试 Floyd 做法，也是可以通过滴！
#include<cstdio>
#define INT_MAX 2147483647
template<typename __T>//使用了 C++ 的泛型编程的“模板”
__T min(const __T __NumA,const __T __NumB){
return __NumA>__NumB?__NumB:__NumA;
}
long long f[11][11],a,b,n=3;
int main(){
scanf("%lld%lld",&a,&b);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
f[i][j]=(i!=j)*INT_MAX;//建边
f[1][2]=a,f[2][3]=b;
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);//Floyd 本体
printf("%lld",f[1][3]);
return 0;
}by diqiuyi @ 2022-10-28 17:10:15
最小生成树也可
#include <bits/stdc++.h>
using namespace std;
inline int read(){
int x=0;bool f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=0;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return f?x:-x;
}
struct edge{
int u,v,w;
bool operator<(edge x) const{
return w<x.w;
}
}a[10];
int A,B,f[114514],n=3,m=2,ans;
int fa(int x){return (f[x]^x)?f[x]=fa(f[x]):x;}
int main(){
A=read(),B=read();
a[1]={1,2,A},a[2]={2,3,B};
sort(a+1,a+m+1);
for(int i=1;i<=n;i++)
f[i]=i;
for(int i=1;i<=m;i++)
if(fa(a[i].u)^fa(a[i].v))
ans+=a[i].w,f[fa(a[i].u)]=fa(a[i].v);
printf("%d\n",ans);
return 0;
}by creation_hy @ 2022-11-01 17:44:39
@S__B 我的评价是不如用树套树，只用了218行就解决了问题！
别问为啥不是红黑树，我不会
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e4 + 5;
const int MAXM = 1e7 + 5;
const int INF = 2147483647;
int n, m, a[MAXN];
inline int read()
{
int s = 0, f = 1;
char ch = getchar();
while (ch < 48 || ch > 57)
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= 48 && ch <= 57)
{
s = (s << 3) + (s << 1) + (ch ^ 48);
ch = getchar();
}
return s * f;
}
namespace FHQ
{
int ch[MAXM][2], pri[MAXM], sz[MAXM], val[MAXM], tot = 0;
// --- bottom ---
inline int Add(int x)
{
val[++tot] = x;
pri[tot] = rand();
sz[tot] = 1;
return tot;
}
inline void push_up(int x)
{
sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1;
}
inline int Merge(int x, int y)
{
if (!x || !y)
return x + y;
if (pri[x] < pri[y])
{
ch[x][1] = Merge(ch[x][1], y);
push_up(x);
return x;
}
else
{
ch[y][0] = Merge(x, ch[y][0]);
push_up(y);
return y;
}
}
inline void Split(int cur, int k, int &x, int &y)
{
if (!cur)
{
x = y = 0;
return;
}
if (val[cur] <= k)
{
x = cur;
Split(ch[cur][1], k, ch[cur][1], y);
}
else
{
y = cur;
Split(ch[cur][0], k, x, ch[cur][0]);
}
push_up(cur);
}
inline int Find(int cur, int k)
{
while (true)
if (sz[ch[cur][0]] >= k)
cur = ch[cur][0];
else if (sz[ch[cur][0]] + 1 == k)
return cur;
else
{
k -= sz[ch[cur][0]] + 1;
cur = ch[cur][1];
}
}
// --- application ---
inline void Insert(int &root, int k)
{
int x, y;
Split(root, k, x, y);
root = Merge(x, Merge(Add(k), y));
}
inline void Delete(int &root, int k)
{
int x, y, z;
Split(root, k, x, z);
Split(x, k - 1, x, y);
y = Merge(ch[y][0], ch[y][1]);
root = Merge(x, Merge(y, z));
}
inline int Rank(int root, int k)
{
int x, y;
Split(root, k - 1, x, y);
int ans = sz[x] + 1;
root = Merge(x, y);
return ans;
}
inline int Last(int root, int k)
{
int x, y;
Split(root, k - 1, x, y);
int ans = sz[x] ? val[Find(x, sz[x])] : -INF;
root = Merge(x, y);
return ans;
}
inline int Next(int root, int k)
{
int x, y;
Split(root, k, x, y);
int ans = sz[y] ? val[Find(y, 1)] : INF;
root = Merge(x, y);
return ans;
}
// --- level 2 application ---
inline void build(int &root, int l, int r)
{
for (int i = l; i <= r; i++)
Insert(root, a[i]);
}
}
namespace SegTree
{
int t[MAXN << 2], root[MAXN << 2];
inline int ls(int p)
{
return p << 1;
}
inline int rs(int p)
{
return p << 1 | 1;
}
inline void build(int p, int l, int r)
{
FHQ::build(root[p], l, r);
if (l == r)
return;
int mid = l + r >> 1;
build(ls(p), l, mid);
build(rs(p), mid + 1, r);
}
inline void update(int p, int l, int r, int pre, int k)
{
FHQ::Delete(root[p], a[pre]);
FHQ::Insert(root[p], k);
if (l == r)
return;
int mid = l + r >> 1;
if (pre <= mid)
update(ls(p), l, mid, pre, k);
else
update(rs(p), mid + 1, r, pre, k);
}
inline int Rank(int p, int qx, int qy, int l, int r, int k)
{
if (qx > r || qy < l)
return 0;
if (qx <= l && r <= qy)
return FHQ::Rank(root[p], k) - 1;
int mid = l + r >> 1;
return Rank(ls(p), qx, qy, l, mid, k) + Rank(rs(p), qx, qy, mid + 1, r, k);
}
inline int Find(int l, int r, int k)
{
int x = 0, y = 1e8;
while (x <= y)
{
int mid = x + y >> 1;
if (Rank(1, l, r, 1, n, mid) + 1 <= k)
x = mid + 1;
else
y = mid - 1;
}
return x - 1;
}
inline int Last(int p, int qx, int qy, int l, int r, int k)
{
if (qx > r || qy < l)
return -INF;
if (qx <= l && r <= qy)
return FHQ::Last(root[p], k);
int mid = l + r >> 1;
return max(Last(ls(p), qx, qy, l, mid, k), Last(rs(p), qx, qy, mid + 1, r, k));
}
inline int Next(int p, int qx, int qy, int l, int r, int k)
{
if (qx > r || qy < l)
return INF;
if (qx <= l && r <= qy)
return FHQ::Next(root[p], k);
int mid = l + r >> 1;
return min(Next(ls(p), qx, qy, l, mid, k), Next(rs(p), qx, qy, mid + 1, r, k));
}
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// freopen("t.in", "r", stdin);
a[1] = read();
a[2] = read();
SegTree::build(1, 1, 2);
long long ans = SegTree::Last(1, 1, 2, 1, 2, a[2]) + SegTree::Next(1, 1, 2, 1, 2, a[1]);
cout << ans;
return 0;
}by a2lyaXNhbWUgbWFyaXNh @ 2022-11-01 18:56:01
@creation_hy Orz，蒟蒻只会Floyd