A.
谜之第1题，明明是第1题AC率比C还要低。题目是求在n个不同重量袋子选4袋，2袋给A，2袋给B，使2人获得重量相同，求问方案数。
我也是一脸懵b。。。o(n2)暴力枚举发现把第i行列和第j行列去掉，再求剩下的a[i]+a[j]数就是解
用容斥，要把(i,i)(i,j)(j,i)(j,j)加回来，想o(n3)，结果tle
结果发现求结果时只求a[i]+a[j]个数就行了，只需改变跟a[i]+a[j]有关的计数就可以了。
还要有一个计数器，储存每个数字分别有多少个
然后直接计数与a[i]+a[j]相关数据
#include#include #include #include #include #include #include #include
B.
意外地很简单。dp一波，dp[n,i]表示银币投n次正好i次向上的概率，然后
dp(n,i)=dp(n-1,i)*(1-p(n))+dp(n-1,i-1)*p(n)，解决
#include#include #include #include #include #include #include #include
C.
题目大意就是求去除某边使n个边的有向无环图变成n-1条边的有向无环图的边编号集合
这里不是判个圈就解决的，不仅要让有向树只有1个0入度点（编号还必须是1），并且所有0出度点只有1个入度
所以判完圈后，还要把标记在圈上的边分别操作，并判断0入度点数和0入度点是不是1号
#include#include #include #include #include #include #include #include
D.
虽说最近搞了MVPTree，也是跟查询点有关。。。但是这题没有给确定点，没法搞~~场上没做
题目不能O(n3)（就是两两确定点，再向外探索点确定个数），会超时
看了其他人的代码后才领悟，敢情是极角排序
看下图就知道是怎么回事了。。。点要跟O点距离原点不足R，那么以自身点为中心，R半径的圆与O圆（半径同样为R）相交部分就是原点的可选范围。
再加入一个点，只要对应圆也包含原来可选范围的一部分，这一部分的原点画的圆也能包含新点
就像这样：
红色区域包含3个圆，仔细观察就会发现其实就是蓝色扇形与棕色扇形对应角相交的部分
可以大胆推断，新点与O点相交角包含区域可默认为可选区域
区域包含的角越多，包含的对应点也越多
然后代码就是这样：（场上排第2名的代码，除开排版问题比较容易看懂）
#include#include #include #include #define Mn 2005//平面点集中点数using namespace std;const double eps = 1e-9;//精度调高点没跑~const double pi = acos(-1.0);#define sqr(x) ((x) * (x))double R;//定长struct point{ double x,y; void read() { scanf("%lf%lf",&x,&y); } void print() { printf("%lf%lf\n",x,y); } double friend dis(const point &a,const point &b) { return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y)); }} p[Mn + 5];struct alpha{ double v; bool flag; bool friend operator <(const alpha &a,const alpha &b)//排序专用偏序关系 { return a.v < b.v; }} alp[Mn * Mn + 5]; //C(N,2)*2的可能交点（可能极角）void solve(int n,int r){ R = r;//本题内为单位圆 for(int i = 0; i < n; i++) p[i].read(); int MAX = 0; for(int i = 0; i < n; i++) { int t = 0; for(int j = 0; j < n; j++) { if(i == j) continue; double theta,phi,D; D = dis(p[i],p[j]); if(D > 2.0 * R)//距离超界直接秒杀 continue;//关键部分 theta = atan2(p[j].y - p[i].y,p[j].x - p[i].x); if(theta < 0) theta += 2 * pi; phi = acos(D / (2.0 * R)); alp[t].v = theta - phi + 2 * pi; alp[t].flag = true; alp[t + 1].v = theta + phi + 2 * pi; alp[t + 1].flag = false; t += 2; } sort(alp,alp + t); int sum = 0; for(int j = 0; j < t; j++) { if(alp[j].flag) sum ++; else sum --; if(sum > MAX) MAX = sum; } } printf("%d\n",MAX + 1);}int main(){ int n,r; while(~scanf("%d%d",&n,&r)) { solve(n,r); }}