當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

2.6模拟总结

發布時間：2023/12/3 编程问答 31 豆豆

生活随笔收集整理的這篇文章主要介紹了 2.6模拟总结小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

前言

45pts
45+0+0
rnk 34
寫了200分，掛了155分
好哇！

考場

這次狀態還真是挺不錯的。
開考，先看題。
T1期望，乍一看看不出來啥，似乎挺難的。
T2乍一看特別可做。
T3腦子里只有模擬退火

先去看T2。
被這種類似的題慣性一帶，第一眼：首先離散化一下 $l, r$ 就變成 $O (n)$ 了。
…
開考30min，這人已經死了。

發現50或者70分似乎比較好寫，后面就完全沒有頭緒。
莫名想到楊表
由于幾乎沒有優化的入手點，很快轉了T1
T1確實是一個不太難的題，按照 $f$ 升序轉移就行了。
30 min 敲完，過了樣例，信心++。

但我也明白做出來這個題的人應該不會太少，還是去T2。
想到如果把dp的下標都變成弱限制，似乎 $n^2$ 可以把 $log?\log$ 去掉。
然后再仔細看看這個 dp ，發現轉移有很多好的性質，直接平衡樹維護就可以 $O(nlog?n)O(n\log n)$ 。
感覺這個題A了的話還是挺值錢的。
就肝它了！
然后就開始寫 splay。
我的這個做法細節非常多，又容易RE又容易WA。
但好在在暴力對拍的幫助下，11：00左右總于是拍不出鍋了。
值域調大調小都穩健如老狗。
當然啦，寫暴力對拍的時候直接把離散化復制過去了
信心++。

然后還有半個小時左右，看了眼T3，決定把模擬退火寫了。
模擬退火真好寫，10min就完事了。
但是由于是完全的瞎退，效果奇差無比，樣例都過不去，調參都不好使。
想到了一種優化退火的方法，但是時間來不及了。
中點白給那10分我愣是沒看見
然后就交了。

題目解析

T1

一個地方把 double 開成 int 了。
吐血。
改過來就過了。

T2

很神奇，這個題我的做法包括dp定義其實和題解完全不一樣，但是代碼卻長的幾乎一模一樣。
都是前面加一個，后面刪一個，中間區間加一。
導致今天下午補題極其輕松，改幾個變量，刪一個離散化就過了。
我這個做法是立足于 $l, r$ 是 $O (n)$ 的基礎上的。
不然似乎還是做不了。
題解的 dp 設計我其實中間想到過，但是覺得沒啥卵用。

T3

主要撲在 T2 上，分配給這題的時間確實太少了。
稍微深度思考一下就能發現最小圓覆蓋呀。
不過我自己恐怕切不掉這個題。對于當限制點少于 $m + 1$ 個點時候如何求超圓圓心我沒有辦法。
題解的高斯消元可以說是很神奇了，在給出點與最后一個點作差向量組成的基底表示下得到的圓唯一且最小。
然而并不會證

總結

感覺屢次掛大分的原因還是心太浮吧。
想到做法 $≠\ne$ 做法是真的 $≠\ne$ 能寫出來 $≠\ne$ 能A題。
考試還是需要謹小慎微一些，多想想為什么，別被慣性思維帶跑。
不奢求了，就希望明天得的分能比掛的分少吧。
支愣起來啊，windwhisper！

代碼

T1

T2

T3

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) #define ok debug("OK\n") inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; } const int N=2e5+100; const int M=2e4+100; const double inf=2e9; const double eps=1e-10;int n,m,tot;double a[20][20],ans[20]; void Gauss(int n){for(int i=1;i<=n;i++){int x=i;for(int j=i+1;j<=n;j++){if(a[j][i]>a[x][i]) x=j;}if(x!=i) swap(a[x],a[i]);for(int j=i+1;j<=n;j++){for(int k=i+1;k<=n+1;k++){a[j][k]-=a[i][k]/a[i][i]*a[j][i];} }}for(int i=n;i>=1;i--){ans[i]=a[i][n+1]/a[i][i];for(int j=1;j<i;j++) a[j][n+1]-=a[j][i]*ans[i];}return; } struct point{double p[20];point(){memset(p,0,sizeof(p));} }; inline point operator - (const point &x,const point &y){point res;for(int i=1;i<=m;i++) res.p[i]=x.p[i]-y.p[i];return res; } inline point operator + (const point &x,const point &y){point res;for(int i=1;i<=m;i++) res.p[i]=x.p[i]+y.p[i];return res; } inline point operator * (const double k,const point &x){point res;for(int i=1;i<=m;i++) res.p[i]=k*x.p[i];return res; } inline double len(const point &x){double res(0);for(int i=1;i<=m;i++) res+=x.p[i]*x.p[i];return sqrt(res); } void print(point o,int op=1){printf("( ");for(int i=1;i<=m;i++) printf("%lf ",o.p[i]);printf(")");if(op) puts(""); } point t[20]; inline point circle(point *p,int n){ // printf("circle: n=%d\n",n); // for(int i=1;i<=n;i++) print(p[i],i==n);for(int i=1;i<n;i++) t[i]=p[i]-p[n];memset(a,0,sizeof(a));for(int x=1;x<n;x++){for(int k=1;k<=m;k++){for(int i=1;i<n;i++) a[x][i]+=2*t[i].p[k]*t[x].p[k];a[x][n]+=t[x].p[k]*t[x].p[k];}} // for(int i=1;i<n;i++){ // for(int j=1;j<=n;j++) printf("%lf ",a[i][j]); // puts(""); // }Gauss(n-1);point res=p[n];for(int i=1;i<n;i++) res=res+(ans[i]*t[i]); // print(res); // puts("");return res; } point x[N]; point o; double r; point pt[20]; void solve(int k,int tp){if(k>m+1) return;for(int i=1;i<tp;i++){double d=len(o-x[i]);if(d>r+eps){pt[k]=x[i];o=circle(pt,k);r=len(o-x[i]);solve(k+1,i);}} }signed main(){freopen("dimension.in","r",stdin);freopen("dimension.out","w",stdout);n=read();m=read();for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) scanf("%lf",&x[i].p[j]);}solve(1,n+1);//printf("%.10lf\n",r);for(int i=1;i<=m;i++) printf("%.10lf ",o.p[i]);return 0; } /* 2 5 3 5 8 4 10 10 5 7 6 9 */

總結

以上是生活随笔為你收集整理的2.6模拟总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。