请问的网站开发培训 有知道的吗,分答网站,网络营销是什么的产物,最近新闻热点国家大事前言
45pts 4500 rnk 34 写了200分#xff0c;挂了155分 好哇#xff01;
考场
这次状态还真是挺不错的。 开考#xff0c;先看题。 T1期望#xff0c;乍一看看不出来啥#xff0c;似乎挺难的。 T2乍一看特别可做。 T3脑子里只有模拟退火
先去看T2。 被这种类似的题惯…前言
45pts 4500 rnk 34 写了200分挂了155分 好哇
考场
这次状态还真是挺不错的。 开考先看题。 T1期望乍一看看不出来啥似乎挺难的。 T2乍一看特别可做。 T3脑子里只有模拟退火
先去看T2。 被这种类似的题惯性一带第一眼首先离散化一下 l,rl,rl,r 就变成 O(n)O(n)O(n) 了。 … 开考30min这人已经死了。
发现50或者70分似乎比较好写后面就完全没有头绪。 莫名想到杨表 由于几乎没有优化的入手点很快转了T1 T1确实是一个不太难的题按照 fff 升序转移就行了。 30 min 敲完过了样例信心。
但我也明白做出来这个题的人应该不会太少还是去T2。 想到如果把dp的下标都变成弱限制似乎 n2n^2n2 可以把 log\loglog 去掉。 然后再仔细看看这个 dp 发现转移有很多好的性质直接平衡树维护就可以 O(nlogn)O(n\log n)O(nlogn)。 感觉这个题A了的话还是挺值钱的。 就肝它了 然后就开始写 splay。 我的这个做法细节非常多又容易RE又容易WA。 但好在在暴力对拍的帮助下1100左右总于是拍不出锅了。 值域调大调小都稳健如老狗。 当然啦写暴力对拍的时候直接把离散化复制过去了 信心。
然后还有半个小时左右看了眼T3决定把模拟退火写了。 模拟退火真好写10min就完事了。 但是由于是完全的瞎退效果奇差无比样例都过不去调参都不好使。 想到了一种优化退火的方法但是时间来不及了。 中点白给那10分我愣是没看见 然后就交了。
题目解析
T1
一个地方把 double 开成 int 了。 吐血。 改过来就过了。
T2
很神奇这个题我的做法包括dp定义其实和题解完全不一样但是代码却长的几乎一模一样。 都是前面加一个后面删一个中间区间加一。 导致今天下午补题极其轻松改几个变量删一个离散化就过了。 我这个做法是立足于 l,rl,rl,r 是 O(n)O(n)O(n) 的基础上的。 不然似乎还是做不了。 题解的 dp 设计我其实中间想到过但是觉得没啥卵用。
T3
主要扑在 T2 上分配给这题的时间确实太少了。 稍微深度思考一下就能发现最小圆覆盖呀。 不过我自己恐怕切不掉这个题。对于当限制点少于 m1m1m1 个点时候如何求超圆圆心我没有办法。 题解的高斯消元可以说是很神奇了在给出点与最后一个点作差向量组成的基底表示下得到的圆唯一且最小。 然而并不会证
总结
感觉屡次挂大分的原因还是心太浮吧。 想到做法 ≠\ne 做法是真的 ≠\ne 能写出来 ≠\ne 能A题。 考试还是需要谨小慎微一些多想想为什么别被惯性思维带跑。 不奢求了就希望明天得的分能比挂的分少吧。 支愣起来啊windwhisper
代码
T1
#includebits/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 cgetchar();while(!isdigit(c)){if(c-) f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}
const int N3050;
const int M2e4100;
const double inf2e9;
const double eps1e-10;int n,m,tot;double f[N],a[N][N],p[N],sum[N];
bool vis[N];signed main(){freopen(trip.in,r,stdin);freopen(trip.out,w,stdout);nread();for(int i1;in;i){for(int j1;jn;j) scanf(%lf,a[i][j]);}for(int i1;in;i) p[i]sum[i]1;f[n]0;vis[n]1;int nown;while(!vis[1]){int id(0);double mninf1;for(int i1;in;i){if(vis[i]) continue;sum[i]p[i]*a[i][now]*f[now];p[i]*(1-a[i][now]);f[i]abs(p[i]-1)eps?sum[i]/(1-p[i]):inf;if(f[i]mn){idi;mnf[i];}//printf( i%d sum%lf p%lf\n,i,sum[i],p[i]);}vis[id]1;nowid;//printf(id%d f%lf\n,id,f[id]);}printf(%.8lf\n,f[1]);return 0;
}
/*
1
1 2
1 1
*/
T2
#includebits/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 cgetchar();while(!isdigit(c)){if(c-) f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}
const int N3050;
const int M2e4100;
const double inf2e9;
const double eps1e-10;int n,m,tot;double f[N],a[N][N],p[N],sum[N];
bool vis[N];signed main(){freopen(trip.in,r,stdin);freopen(trip.out,w,stdout);nread();for(int i1;in;i){for(int j1;jn;j) scanf(%lf,a[i][j]);}for(int i1;in;i) p[i]sum[i]1;f[n]0;vis[n]1;int nown;while(!vis[1]){int id(0);double mninf1;for(int i1;in;i){if(vis[i]) continue;sum[i]p[i]*a[i][now]*f[now];p[i]*(1-a[i][now]);f[i]abs(p[i]-1)eps?sum[i]/(1-p[i]):inf;if(f[i]mn){idi;mnf[i];}//printf( i%d f%lf id%d mn%lf\n,i,f[i],id,mn);}vis[id]1;nowid;//for(int i1;in;i) printf(%lf ,f[i]);//puts();//printf(id%d f%lf\n\n,id,f[id]);}printf(%.8lf\n,f[1]);return 0;
}
/*
1
1 2
1 1
*/
T3
#includebits/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 cgetchar();while(!isdigit(c)){if(c-) f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}
const int N2e5100;
const int M2e4100;
const double inf2e9;
const double eps1e-10;int n,m,tot;double a[20][20],ans[20];
void Gauss(int n){for(int i1;in;i){int xi;for(int ji1;jn;j){if(a[j][i]a[x][i]) xj;}if(x!i) swap(a[x],a[i]);for(int ji1;jn;j){for(int ki1;kn1;k){a[j][k]-a[i][k]/a[i][i]*a[j][i];} }}for(int in;i1;i--){ans[i]a[i][n1]/a[i][i];for(int j1;ji;j) a[j][n1]-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 i1;im;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 i1;im;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 i1;im;i) res.p[i]k*x.p[i];return res;
}
inline double len(const point x){double res(0);for(int i1;im;i) resx.p[i]*x.p[i];return sqrt(res);
}
void print(point o,int op1){printf(( );for(int i1;im;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 i1;in;i) print(p[i],in);for(int i1;in;i) t[i]p[i]-p[n];memset(a,0,sizeof(a));for(int x1;xn;x){for(int k1;km;k){for(int i1;in;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 i1;in;i){
// for(int j1;jn;j) printf(%lf ,a[i][j]);
// puts();
// }Gauss(n-1);point resp[n];for(int i1;in;i) resres(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(km1) return;for(int i1;itp;i){double dlen(o-x[i]);if(dreps){pt[k]x[i];ocircle(pt,k);rlen(o-x[i]);solve(k1,i);}}
}signed main(){freopen(dimension.in,r,stdin);freopen(dimension.out,w,stdout);nread();mread();for(int i1;in;i){for(int j1;jm;j) scanf(%lf,x[i].p[j]);}solve(1,n1);//printf(%.10lf\n,r);for(int i1;im;i) printf(%.10lf ,o.p[i]);return 0;
}
/*
2 5
3 5 8 4 10
10 5 7 6 9
*/
