oToToT的code收藏區

題目連結: https://zerojudge.tw/ShowProblem?problemid=b591 今天去打ISSC時的題目，最後沒寫出來，賽後想兩下就知道哪邊爛了，囧。一開始看到題目時，直覺是對y二分搜，後來寫一寫後發現那東東好像不是很好做(雖然大為學長他們後來也還是做了出來...)，想了一段時間後就發現其實將所有的x跟那個x所對應到最小且合法的y畫在平面上，其實他是會是一個凹向下的圖形(類似二次函數)，所以其實可以三分搜(不過那時不知為何我寫了個爬山，囧)，發現這件事後就直接對x三分搜即可。 #include <bits/stdc++.h> using namespace std; #define PB push_back typedef pair<int,int> PII; #define FF first #define SS second const double eps = 1e-7; vector<PII> con; double getY(double); int main(){ int n; while(scanf("%d",&n), n){ con.clear(); for(int i=0;i<n;i++){ PII x; scanf("%d%d",&x.FF,&x.SS); con.PB(x); } double l=0, r=1e9; for(int _=0;_<500;++_){ if(r-l < eps) break; double ll=l+(r-l)/3, rr=l+2*(r-l)/3; if(getY(rr) < getY(ll)) l=ll; else r=rr; ...

題目連結: http://tioj.infor.org/problems/1882 本題是要求一堆二次函數取min疊加起來後的最大值，因為二次函數疊加起來後其實斜率還是有單調性，因此可以三分搜出答案，不過我不太喜歡寫三分搜，因此就寫了個模擬退火(當初是培訓時有人提了這鬼東東ww)，研究了一下發現滿有趣的，簡單來說就是隨邊挑個起點，走走看如果比較好就走，如果比較差就用$e^{\Delta y \times t}$ 來判斷是否要走下去(這裡的t指的是步數，原本是用溫度)，不過因為本題的斜率有單調性，所以不需要往下(這好像又叫爬山法)。此外我裡面還用了C++的random，發現可調的參數真的變多了，但相對的用起來也沒那麼無腦了XD #include <bits/stdc++.h> using namespace std; #define endl '\n' struct wow{ double a,b,c; }; vector<wow> func; inline double getY(double x); int main(){ cin.tie(NULL);ios_base::sync_with_stdio(); default_random_engine rGen; uniform_real_distribution<double> rForm(-1,1); auto random = bind(rForm,rGen); int n; cin>>n; func.resize(n); for(int i=0;i<n;i++) cin>>func[i].a>>func[i].b>>func[i].c; uniform_real_distribution<double> inipos(0,90); double x=inipos(rGen); double y=getY(x); doubl...