无法在这个位置找到: head2.htm
当前位置: 建站首页 > 新闻动态 > 行业新闻 >

2020牛客多校第二场小结+思考+题解(BCDFJ)

时间:2021-03-27 18:53来源:未知 作者:jianzhan 点击:
题型连接:2020牛客暑假多校风校训练营(第二场)题解B题Boundary题意让你n个点,考虑到这选一个历经原点的圆,而且这一圆历经这n个点的数量数最多,求这一数最多的等级。题解这一
题型连接:

2020牛客暑假多校风校训练营(第二场)

题解B题Boundary

题意

让你n个点,考虑到这选一个历经原点的圆,而且这一圆历经这n个点的数量数最多,求这一数最多的等级。

题解

这一题的作法挺多的,能够枚举类型圆心或是半径,还可以枚举类型圆周角(题解的作法)。

時间繁杂度:O(n^2logn)

最先大家必须了解一个定理:三个点能够明确一个圆。

作法一:枚举类型圆心或是半径

如今大家己知一个原点(0,0),随后大家能够枚举类型2个点,随后求出三个点产生的圆的圆心,并纪录圆心的较大出現频次,

最终大家枚举类型i个点,假如这i个点里边随意选择2个点和原点产生的圆的数量(即C(i,2))相当于圆心的较大出現频次,那麼i便是回答,由于从i个点随意选择2个点就确保了全部随意选择的2个点和原点所产生的圆心全是同样的。

这类方式较为恰当,也较为难想。枚举类型半径的方式相近。

trick1:必须考虑到n个点里边出現原点的状况,及其全部点都共线的状况。

trick2:用map维护保养较大圆心出現频次会请求超时,因此只有暴力行为枚举类型来求。

编码完成:

#include bits/stdc++.h using namespace std;const double eps = 1e-10;struct Point{ double x,y; Point(){} Point(double _x,double _y):x(_x),y(_y){}}p[2005];double cx,cy;int flag;void solve(Point a, Point b, Point c) //三点共圆求圆心公式计算{ double fm1=2 * (a.y - c.y) * (a.x - b.x) - 2 * (a.y - b.y) * (a.x - c.x); double fm2=2 * (a.y - b.y) * (a.x - c.x) - 2 * (a.y - c.y) * (a.x - b.x); if (fm1 == 0 || fm2 == 0){ flag=1; return; } double fz1=a.x * a.x - b.x * b.x + a.y * a.y - b.y * b.y; double fz2=a.x * a.x - c.x * c.x + a.y * a.y - c.y * c.y; cx = (fz1 * (a.y - c.y) - fz2 * (a.y - b.y)) / fm1; cy = (fz1 * (a.x - c.x) - fz2 * (a.x - b.x)) / fm2;}vector pair double,double int main(){ int n;scanf("%d", for(int i=1;i i++) scanf("%lf%lf", p[i].x, p[i].y); for(int i=1;i i++){ for(int j=i+1;j j++){ flag=0; solve(Point{0.0,0.0},p[i],p[j]); if(flag) continue; v.push_back(make_pair(cx,cy)); } } if(v.size()==0){ cout 1 endl; return 0; } sort(v.begin(),v.end()); int MAX=1; int num=1; pair double,double cur=v[0]; int len=v.size(); for(int i=1;i i++){ if(v[i]==cur) num++; else{ MAX=max(num,MAX); num=1; cur=v[i]; } MAX=max(num,MAX); } for(int i=1;i i++){ if(i*(i-1)==MAX*2){ cout i endl; break; } } return 0;}

作法二:枚举类型圆周角

一样大家能够枚举类型2个点,随后求出这2个点和原点产生的圆周角,随后求出圆周角的众数就可以了了。

trick:角相同(即弧相同)可是归属于2个对称性圆的状况,以下图所显示:

编码完成:

#include bits/stdc++.h #define m_p make_pair#define p_i pair int, int #define _for(i, a) for(register int i = 0, lennn = (a); i lennn; ++i)#define _rep(i, a, b) for(register int i = (a), lennn = (b); i = lennn; ++i)#al(a) cout "Debuging...|" #a ": " a "\n"#define mem(a, b) memset(a, b, sizeof(a))#define mem0(a) memset(a, 0, sizeof(a))#define fil(a, b) fill(a.begin(), a.end(), b);#define scl(x) scanf("%lld", x)#define sc(x) scanf("%d", x)#define abs(x) ((x) 0 ? (x) : -(x))#define PI acos(-1)#define lowbit(x) (x (-x))using namespace std;typedef long long LL;typedef unsigned long long ULL;const int maxn = 2005;const int maxm = 1000005;const int maxp = 30;const int inf = 0x3f3f3f3f;const LL INF = 0x3f3f3f3f3f3f3f3f;const int mod = ;const double eps = 1e-12;const double E = 2.;typedef struct poi { double x, y; poi() {} poi(double x, double y) :x(x), y(y) {} void inp() { scanf("%lf%lf", x, } bool operator (poi tem) { if(fabs(x-tem.x) =eps) return y tem.y; else return x tem.x; } //点排列-先排x再排y poi operator + (poi tem) { return poi(x + tem.x, y + tem.y); } //点/空间向量 相加 poi operator - (poi tem) { return poi(x - tem.x, y - tem.y); } poi operator * (double tem) { return poi(x * tem, y * tem); } double operator * (poi tem) { return x * tem.x + y * tem.y; } //点积 double operator ^ (poi tem) { return x * tem.y - y * tem.x; } //叉积 poi operator / (double tem) { return poi(x / tem, y / tem); } int dcmp(double x) { if (x eps) return 0; else return x 0 ? -1 : 1; } bool operator == (poi tem) { return dcmp(x - tem.x) == 0 dcmp(y - tem.y) == 0; }} Vector;double Dot(Vector a, Vector b) { return a.x*b.x + a.y*b.y; } //点积double Length(Vector a) { return sqrt(Dot(a, a)); } //长短double Angle(Vector a, Vector b) { return acos(Dot(a, b) / Length(a) / Length(b)); }//夹角double Cross(Vector a, Vector b) { return a.x*b.y - a.y*b.x; } //叉积double Area(poi a, poi b, poi c) { return Cross(b - a, c - a) / 2; } //三点求三角形总面积double sgn(double x) { return fabs(x) - eps 0 ? 0 : (x 0 ? 1 : -1); }long double X, Y, R;int n;poi a[maxn];double b[maxn];int bl; void cal(Vector p12, Vector p13) { R = Dot(p12, p13) / (Length(p12) * Length(p13));} void sol() { _for(i, n) scanf("%lf%lf", a[i].x, a[i].y); int ans = 0; _for(i, n) { bl = 0; _for(j, n) { if(Cross(a[i], a[j]) 0) { cal(a[j] - a[i], a[j]); b[bl++] = R; } } sort(b, b + bl); for(int i = 0, j = 0; i i = j) { while(j bl fabs(b[j] - b[i]) = eps) ++j; ans = max(ans, j - i); } } printf("%d\n", ans + 1);} int main() { //ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); while(cin n) { sol(); } return 0;}
C题Cover the Tree 

题意:让你一个n-一个连接点的无根树,随后求出最少的遮盖全部边的链(相对路径)的数量,及其这种链。

题解:链的数量便是(叶子连接点数量+1)/2,随后立即求出全部叶子连接点的dfs序就可以了了,而且把这种叶子连接点依照dfs序排列,最终依照间距为(叶子连接点数量/2)过去往后面配对輸出就可以了了。

实际证实全过程以下()

 

D题Duration

每日签到题,变换一下立即算就可以了了。

F题Fake Maxpooling

题意:让你三数量n,m,k,n和m表明引流矩阵的行数和列数,引流矩阵的每个原素相当于其行数和列数的最少公倍率,给你求出这一引流矩阵的k*k的子引流矩阵的较大值的和。

正解应当是二维简单序列+提升求n*m的引流矩阵,時间繁杂数为O(nm)

自然还可以立即暴力行为求n*m的引流矩阵,或是用二维st表维护保养,時间繁杂数为O(nmlogn),参量并不大应当不容易请求超时。

提升求n*m的引流矩阵的方式(相近于线形筛,确保每一个lcm(i,j)都但求一次)为

编码完成

#include bits/stdc++.h #define m_p make_pair#define _for(i, a) for(register int i = 0, lennn = (a); i lennn; ++i)#define _rep(i, a, b) for(register int i = (a), lennn = (b); i = lennn; ++i)using namespace std;typedef long long LL;const int maxn = 5005; int n, m, k;int a[maxn][maxn];int gcd[maxn][maxn];deque LL inline void init() { memset(gcd,0,sizeof(gcd)); _rep(i, 1, n) { _rep(j, 1, m) { if(!gcd[i][j]){ for(int k=1;k*i =n k*j k++){ gcd[k*i][k*j]=k; a[k*i][k*j]=i*j*k; } } } }}void sol() { init(); _rep(i, 1, n) { dq.clear(); _rep(j, 1, m) { while(dq.size() dq.front() j - k + 1) dq.pop_front(); while(dq.size() a[i][dq.back()] = a[i][j]) dq.pop_back(); dq.push_back(j); a[i][j] = a[i][dq.front()]; } } _rep(j, 1, m) { dq.clear(); _rep(i, 1, n) { while(dq.size() dq.front() i - k + 1) dq.pop_front(); while(dq.size() a[dq.back()][j] = a[i][j]) dq.pop_back(); dq.push_back(i); a[i][j] = a[dq.front()][j]; } } LL sum = 0; _rep(i, k, n) { _rep(j, k, m) { sum += a[i][j]; } } cout sum "\n";}int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); while(cin n m k) { sol(); } return 0;}
 J题Just Shuffle

题意:让你一个排序a,及其一个整数金额k,这一排序是某一个排序p换置k次后的結果,如今给你求出这一排序。

最先这一题必须了解对组成数学课中的换置有一定掌握,不明白的能够参照我的blog(组成数学课——群论学习培训小结)

了解换置的基本要素后这一题就行干了。

依据题意大家能够了解 p ^ k = a (^表明换置)

因而 p = a ^ z  (  ( z * k ) % r == 1),即z是k在模r实际意义下的逆元(由于k为质数,全部逆元一定存有)。

这儿r就每一个循环系统的循环系统长短,因而大家求出z后,把当今循环系统再换置z次后便是回答。

trick:求逆元立即用费马小定理求会请求超时(参量较为大),必须用拓展欧几里得求或是立即枚举类型逆元。

官方网题解:

编码完成:

#include bits/stdc++.h #define ll long longusing namespace std;const int N = 1e5+7;int a[N],res[N];int vis[N];ll k;vector int ll quick_pow(ll a,ll b,ll mod){ ll res=1; while(b){ if(b 1) res=(res*a)%mod; b =1; a=(a*a)%mod; } return res;}ll inv(ll x,ll mod){return quick_pow(x,mod-2,mod)%mod;}void calc(){ int len=v.size(); ll Inv; // ll Inv=inv(1ll*k,1ll*len)%len; // cout Inv endl; for(int i=0;i i++) if(1ll*i*k%len==1) Inv=i; for(int i=0;i i++) res[v[i]]=v[(i+Inv)%len];}int main(){ cin.sync_with_stdio(false); int n;cin n k; for(int i=1;i i++) cin a[i]; for(int i=1;i i++){ if(!vis[i]){ v.clear(); int x=a[i]; while(!vis[x]){ v.push_back(x); vis[x]=1; x=a[x]; } calc(); } } for(int i=1;i i++){ if(i==1) cout res[i]; else cout " " res[i]; } cout endl; return 0;}

 

 

 

 

 

 

思考和小结

早期并不是非常圆满,每日签到题出的也很艰辛,也就间接性造成后边写自身善于的换置时,所剩時间都不多了,并且还读不对题意。同伴b题的精密度也被卡的瘋狂自闭,随后就崩了,還是太菜了。。。。。

文中连接: news_show_411688.aspx   共享到: 腾迅 新浪网 每个人网 电子邮件 个人收藏夹 拷贝网站地址 大量 (责任编辑:admin)

织梦二维码生成器
顶一下
(0)
0%
踩一下
(0)
0%
------分隔线----------------------------
无法在这个位置找到: ajaxfeedback.htm
栏目列表
推荐内容


扫描二维码分享到微信