206/734
1002.Mindis【补】
图上一点关于圆心的反演
#include <bits/stdc++.h> using namespace std; const int maxn=500005; const long double eps=1e-15; int sgn ( long double x ) { return ( x > eps ) - ( x < -eps ) ; } struct Point{ long double x,y; Point(){} Point(long double _x,long double _y){ x=_x;y=_y; } Point operator +(const Point &b)const{ return Point(x+b.x,y+b.y); } Point operator /(const long double &k)const{ return Point(x/k,y/k); } Point operator -(const Point &b)const { return Point(x-b.x,y-b.y); } Point operator *(const long double &rhs)const{ return Point(x*rhs,y*rhs); } long double operator*(const Point &b)const{ return x*b.x+y*b.y; } long double operator ^(const Point &b) const { return x*b.y-y*b.x; } bool operator==(Point b)const{ return sgn(x-b.x)==0&&sgn(y-b.y)==0; } long double len() { return sqrt(x*x+y*y); } long double len2() { return x*x+y*y; } long double distance(Point p) { return sqrt((x-p.x)*(x-p.x)+(y-p.y)*(y-p.y)); } Point rotleft(){ return Point(-y,x); } Point trunc(long double r) { long double l=len(); if (!sgn(l)) return *this; r/=l; return Point(x*r,y*r); } }; struct Line{ Point s,e; Line(){} Line(Point _s,Point _e){ s=_s; e=_e; } long double length() { return s.distance(e); } long double dispointtoline(Point p) { return fabs((p-s)^(e-s))/length(); } Point crosspoint(Line v) { long double a1=(v.e-v.s)^(s-v.s); long double a2=(v.e-v.s)^(e-v.s); return Point((s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1)); } Point lineprog(Point p) { return s+(((e-s)*((e-s)*(p-s)))/((e-s).len2())); } }; struct Circle{ Point p;long double r; Circle(){} Circle(long double x,long double y,long double _r) { p=Point(x,y); r=_r; } int relationline(Line v) { long double dst=v.dispointtoline(p); if (sgn(dst-r)<0) return 2; else if (sgn(dst-r)==0) return 1; else return 0; } int pointcrossline(Line v,Point &p1,Point &p2) { if (!(*this).relationline(v)) return 0; Point a=v.lineprog(p); long double d=v.dispointtoline(p); d=sqrt(r*r-d*d); if (sgn(d)==0) { p1=a; p2=a; return 1; } p1=a+(v.e-v.s).trunc(d); p2=a-(v.e-v.s).trunc(d); return 2; } }; long double dist(Point p,Point q) { return p.distance(q); } int main() { int T; Point c=Point(0,0); scanf("%d",&T); while (T--) { double t; long double r; long double x1,y1,x2,y2; //cin >> r; //cin >>x1 >>y1; //cin >>x2 >>y2; scanf("%lf",&t);r =t; scanf("%lf",&t);x1 =t; scanf("%lf",&t);y1 =t; scanf("%lf",&t);x2 = t; scanf("%lf",&t);y2 = t; Point P(x1,y1); Point Q(x2,y2); long double rr = P.distance(c); long double k = r*r/(rr*rr); Point PP(x1*k,y1*k); Point QQ(x2*k,y2*k); Line L(PP,QQ); Circle C(0,0,r); Point a; long double ans = 0; if (P==Q) { ans = 2*(r-rr); } else if (C.relationline(L) >=1 ) { ans = PP.distance(QQ)*rr/r; } else { Point mid = ((P+Q)/2); Line Y(mid,c); Point p1,p2; C.pointcrossline(Y,p1,p2); ans = min(p1.distance(P)+p1.distance(Q),p2.distance(P)+p2.distance(Q)); } double res = (double)ans; printf("%.12f ",res); } return 0; }
1003. Inversion
暴力。先打个ST表，对每个Bi暴力求最大值即可。
#include <bits/stdc++.h> using namespace std; const int maxn=100005; int T,n,a[maxn],dp[19][maxn]; inline void init() { for (int i=1;i<=n;++i) dp[0][i]=a[i]; for (int i=1;i<19;++i) for (int j=1;j+(1<<i)-1<=n;++j) dp[i][j]=max(dp[i-1][j],dp[i-1][j+(1<<(i-1))]); } inline int query(int l,int r) { int x=0; while ((1<<(x+1))<=r-l+1) ++x; return max(dp[x][l],dp[x][r-(1<<x)+1]); } int main() { scanf("%d",&T); while (T--) { scanf("%d",&n); for (int i=1;i<=n;++i) scanf("%d",&a[i]); init(); for (int i=2;i<=n;++i) { int res=0; for (int j=1;j<=n;j+=i) res=max(res,query(j,min(n,j+i-2))); printf("%d%c",res,i==n?' ':' '); } } return 0; }
1008. Kirinriki
暴力。枚举中点+双指针。复杂度O(n^2)
#include <bits/stdc++.h> const long long mod = 1e9+7; const double ex = 1e-10; #define inf 0x3f3f3f3f using namespace std; char S[5500]; int l ; int m; int check1(int mid) { int L = max(0,2*mid-l+1); int R = min(l-1,2*mid); int ll = L; int rr = R; int tans = 0; int sum = 0; //cout << mid <<":"<<endl; while (L<mid){ sum += abs(S[L]-S[R]); while (sum > m) sum -= abs(S[ll++]-S[rr--]); tans = max(tans,L-ll+1); //cout << ll <<" " << L <<" "<<rr <<" " <<R <<" "<<sum <<endl; L++,R--; } return tans; } int check2(int mid) { int L = max(0,2*mid-l+2); int R = min(l-1,2*mid+1); int ll = L; int rr = R; int tans = 0; int sum = 0; //cout << mid <<":"<<endl; while (L<=mid){ sum += abs(S[L]-S[R]); while (sum > m) sum -= abs(S[ll++]-S[rr--]); tans = max(tans,L-ll+1); //cout << ll <<" " << L <<" "<<rr <<" " <<R <<" "<<sum <<endl; L++,R--; } return tans; } int main() { int t; scanf("%d",&t); while (t--){ scanf("%d",&m); scanf("%s",S); l = strlen(S); int ans = 0; for (int i = 0; i < l; i++){ ans = max(ans,check1(i)); if (i+1 == l) continue; ans = max(ans,check2(i)); } printf("%d ",ans); } return 0; }
1010. Gameia
#include <bits/stdc++.h> using namespace std; const int maxn=505; int T,n,K,fa[maxn],deg[maxn],vis[maxn]; inline void solve() { int tot=0; for (int i=1;i<=n;++i) if (!deg[i]) { int u=i; while (true) { if (u==1||vis[fa[u]]) { puts("Alice"); return; } vis[u]=vis[fa[u]]=1; if (fa[u]==1) break; ++tot; if (vis[fa[fa[u]]]) break; --deg[fa[fa[u]]]; --deg[fa[u]]; if (deg[fa[fa[u]]]>0) break; u=fa[fa[u]]; } } puts(tot<=K?"Bob":"Alice"); } int main() { scanf("%d",&T); while (T--) { memset(vis,0,sizeof vis); memset(deg,0,sizeof deg); scanf("%d%d",&n,&K); for (int i=2;i<=n;++i) { scanf("%d",&fa[i]); ++deg[fa[i]]; } solve(); } return 0; }
1011. Classes
画出venn图，所有块大小都大于等于0就合法。
#include <bits/stdc++.h> #define maxn 100010 #define inf 0x3f3f3f3f #define REP(i,x,y) for(int i=x;i<(y);i++) #define RREP(i,x,y) for(int i=x;i>(y);i--) using namespace std; typedef long long ll; typedef pair<int,int> pii; int a,b,c,ab,bc,ac,abc; int main() { int T;scanf("%d",&T); while(T--) { int n;scanf("%d",&n); int maxx=0; while(n--) { scanf("%d %d %d %d %d %d %d",&a,&b,&c,&ab,&bc,&ac,&abc); int sum=a+b+c-ab-bc-ac+abc; if(sum<0) continue; int tmp1=a-ab-ac+abc; if(tmp1<0) continue; tmp1=ab-abc; if(tmp1<0) continue; if(abc<0) continue; if(ac-abc<0) continue; if(bc-abc<0) continue; if(b-bc-ab+abc<0) continue; if(c-bc-ac+abc<0) continue; maxx=max(maxx,sum); } printf("%d ",maxx); } }