# A 贪心得知，Alice 每次一定会取走当前剩余的最小值，而 Bob 每次一定会取走当前剩余的最大值。 因此，对于给定的所有整数进行排序，$2n$ 个整数做 $n-1$ 轮后剩下的两个数一定是第 $n$ 小与第 $n$ 大。 时间复杂度 $O(n\log n)$. - 注意 $n=10^5$，数组至少要开 $2\times 10^5$！ - main 函数里不要开大数组！！！ - 使用 cin/cout 时遇到大规模数据请务必关闭同步流，并且不要与 scanf/printf 之类函数混用！ ```cpp int n,a[200050]; void solve() { scanf("%d",&n); for(int i=1;i<=(n<<1);i++) scanf("%d",&a[i]); sort(a+1,a+(n<<1)+1); printf("%d\n",a[n]+a[n+1]); } ``` --- # B 差分后求出前缀和数组即可。 时间复杂度 $O(n)$. - 注意 `long long` ```cpp int n,m,a[100050]; ll b[100050]; void solve() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=m;i++) { int l,r,d; scanf("%d%d%d",&l,&r,&d); b[l]+=d; b[r+1]-=d; } for(int i=1;i<=n;i++) { b[i]+=b[i-1]; printf("%lld%c",b[i]+a[i],i==n?'\n':' '); } } ``` --- # C 首先显然需要对于某个 $i$ 满足 $\sum \frac{i(i+1)}2 = a+b$. 满足以上条件后，下证对于每种情况都存在构造方案： 首先一定存在某个 $i$ 使得 $0 \le \sum\frac{i(i+1)}2 - a \lt i$ 成立，然后我们从这个 $1,2,3,\cdots,i$ 的序列中去掉 $\sum\frac{i(i+1)}2 - a$，就得到了 $a$，剩下的部分就是 $b$. 因此，从大到小贪心放盒子即可。 时间复杂度 $O(\sqrt{a+b})$. ```cpp char ans[2020]; void solve() { int a,b; scanf("%d%d",&a,&b); int flag=0; for(int i=1;i<=2000;i++) if(i*(i+1)/2==a+b) { flag=i; break; } if(!flag) { puts("NO"); return; } puts("YES"); for(int i=flag;i>=1;i--) { if(i<=a) ans[i]='A',a-=i; else ans[i]='B'; } puts(ans+1); } ``` --- # D 观察三个函数： - 当符号为按位与 `&` 时，`x&(x-1)` 的含义也就是消除 $x$ 二进制位上最低位的 $1$。因此总操作次数为 $x$ 二进制上 $1$ 的个数； - 当符号为按位或 `|` 时，如果 $x$ 初始时最低位为 $1$，那么 `x|(x-1)=x` 恒成立；如果 $x$ 初始时最低位为 $0$，那么 $x-1$ 的最低位为 $1$，在执行一次后将来到循环状态。因此总操作次数为 $[x\text{是偶数}]$； - 当符号为按位异或 `^` 时，如果当前 $x=1$，那么 $1\oplus 0=1$ 恒成立；否则，记当前最低位 $1$ 的位置为 $p$，所有比 $p$ 更高的位在进行一次异或操作后都将变为 $0$，而所有比 $p$ 更低的位本应都是 $0$，但在 $x-1$ 后都将变为 $1$，因此在一次操作后 $x$ 将会变为 $2^{p+1}-1$，操作两次后将变为 $1$，此后将来到循环状态。综上，总操作次数为 $[x\text{是偶数}]+1$，特殊的，当 $x=1$ 时总操作次数为 $0$. 对于这三个函数的前缀和函数： - 当符号为按位与 `&` 时，考虑统计 $1\sim n$ 内每个数的二进制上 $1$ 的个数之和。按每一位出现的次数来计算，例如在 $2^i$ 位上的数是以 $2^{i+1}$ 作为周期循环出现的，且每个周期内的前 $2^i$ 个数为 $0$，后 $2^i$ 个数为 $1$，因此直接整除后计算周期数统计个数，最后一个周期根据模数计算个数即可。 - 当符号为按位或 `|` 时，因为只有在 $x$ 是偶数时次数为 $1$，因此 $\lfloor\frac n 2\rfloor$ 即为答案； - 当符号为按位异或 `^` 时，除 $x=1$ 时答案为 $0$ 外，其余情况下在 $x$ 为偶数时次数为 $2$，为奇数时次数为 $1$，也就是在 $x\ge 2$ 时次数均为“按位或 `|` ”时 $+1$，因此答案即 $\lfloor\frac n 2\rfloor+n-1$. 时间复杂度 $O(T\log n)$. ```cpp void solve() { long long n,ans=0; cin>>n; for(int i=0;i<=56;i++) { ans+=(n+1)/(1LL<<(i+1))*(1LL<<i); ans+=max(0LL,(n+1)%(1LL<<(i+1))-(1LL<<i)); } cout<<ans<<' '; cout<<n/2<<' '; cout<<n/2+n-1<<'\n'; } ``` --- # E 先考虑直接扔向出口的可行角度，从点 $P$ 向圆 $O$ 作切线，得到两个切点记作 $C,D$，那么可行角度也就是向量 $\overrightarrow{PC}$ 与向量 $\overrightarrow{PD}$ 之间的夹角 $\theta_1$。因为题目保证 $R\ge 1$ 且点 $P$ 不在圆内及圆上（抱歉“或圆上”这三个字在赛时忘了打上去了，但这种情况如果存在的话特判下就行），所以 $0 \lt \theta_1 \lt 180^{\circ}$. 根据向量点乘 $Dot(\overrightarrow{PC},\overrightarrow{PD})=|\overrightarrow{PC}|\cdot|\overrightarrow{PD}|\cdot\cos \theta_1$，得： $$ \theta_1=\arccos\frac{Dot(\overrightarrow{PC},\overrightarrow{PD})}{|\overrightarrow{PC}|\cdot|\overrightarrow{PD}|} $$ 再考虑扔到墙上之后反弹至出口的可行角度，我们延长任意反弹后的轨迹，可以发现其均交汇至同一点上，这个点也就是点 $P$ 对于直线 $AB$ 的对称点 $P'$. 接下来的做法同上，从点 $P'$ 向圆 $O$ 作切线，得到两个切点记作 $C',D'$，记可行角度为 $\theta_2$，得： $$ \theta_2=\arccos\frac{Dot(\overrightarrow{P'C'},\overrightarrow{P'D'})}{|\overrightarrow{P'C'}|\cdot|\overrightarrow{P'D'}|} $$ 最后，注意到题目中限制点 $P$ 到墙的直线距离一定不大于墙到出口的最近距离，换句话说 $\theta_1$ 与 $\theta_2$ 一定不存在重叠的部分，因此我们便可以直接取 $\frac{\theta_1+\theta_2}{360^{\circ}}$ 作为答案。 时间复杂度 $O(T)$. ```cpp const double PI=acos(-1.0); struct Point{ double x,y; Point(){} Point(double x,double y):x(x),y(y){} }; typedef Point Vector; Vector operator - (const Vector &a,const Vector &b){ // 两点相减为向量 return Vector(a.x-b.x,a.y-b.y); } inline double Dot(Vector a,Vector b){ // 点积 return a.x*b.x+a.y*b.y; } inline double Length(Vector a){ // 向量长度（首尾点距） return sqrt(Dot(a,a)); } inline double Angle(Vector a,Vector b){ // 两向量夹角 return acos(Dot(a,b)/(Length(a)*Length(b))); } struct Line{ Point s,e; Line(){} Line(Point _s,Point _e){ s=_s; e=_e; } Point symmetryPoint(Point &p){ double a=e.x-s.x,b=e.y-s.y; double t=((p.x-s.x)*a+(p.y-s.y)*b)/(a*a+b*b); return Point(2*s.x+2*a*t-p.x,2*s.y+2*b*t-p.y); } } struct Circle{ Point o; double r; Circle(){} Circle(Point o,double r):o(o),r(r){} int getTangentPoints(Point &p,vector<Point> &vec){ double d=Distance(p,o),b=atan2(p.y-o.y,p.x-o.x); double delta=acos(r/d); vec.push_back(getPoint(b+delta)); if(dcmp(delta)){ vec.push_back(getPoint(b-delta)); return 2; } return 1; } } void solve() { Point p; Line l; Circle o; cin>>p.x>>p.y; cin>>o.o.x>>o.o.y>>o.r; cin>>l.s.x>>l.s.y>>l.e.x>>l.e.y; Point p2=l.symmetryPoint(p); // 求P相对于AB的对称点 vector<Point> v1,v2; assert(o.getTangentPoints(p,v1)==2); // 求P对O的两切点 assert(o.getTangentPoints(p2,v2)==2); // 求P2对O的两切点 cout<<(Angle(v1[0]-p,v1[1]-p)+Angle(v2[0]-p2,v2[1]-p2))/(PI*2)*100<<'\n'; } ``` 计算几何的题目大部分其实就是看你有没有整理出一套属于自己的板子。基本上认真学一遍，整理出板子之后，很多原本看起来很难的题目基本调用几个现成的函数就能直接解决了的。加油！ **附加题**：如果去掉“点 $P$ 到墙的直线距离一定不大于墙到出口的最近距离”这一条限制，这题要怎么做呢~ （其实也简单滴，只是难度应该会提升到组队赛水平，就不整活啦）