总体

这一次离我们的目标还有一道题，不过我也知道最后的这一道题其实是最不容易攻克的一部分，这一次总结之后，我发现我们还是在一些基本的概念上的不深入，还有就是对于一些套路的不熟悉，在这一方面还是有很大的进步空间。
题目链接

题目A

一道签到题，我还没上线队友就做了，就显得我很没用（嘿嘿），题意就是，题目大意：给出一个正整数n，找到一个最小的整数k使得集合{1,2,…n}的任意一个大小为k的子集都至少存在两个元素使得其中一个是另一个的因子。
我看了一下，这边主要就是要往这一方面想，其实像是一个纯纯的找规律题。这里直接放上代码把。

代码

#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
int T,n;
int main() {cin.tie(0);ios::sync_with_stdio(0);cin >>T;while(T--) {cin >>n;cout <<(n+1)/2+1<<endl;}return 0;
}

题目B

lucas定理参考链接
这题要用到的一个定理，参见上面的链接，简单解释一下就是组合数学中的取模定理，但是具体起来里面也是有很多东西在里面的。
回到这道题，这其实是关于一个染色方案数的问题，但是这个方案数是要经过很多个格子组合得到的，其实我们很容易能发现，如果我们从一个角开始向下进行，那么我们知道后面的情况是以前面出现的情况为拓展的。说白了就是后面走的路线是在前面基础上再乘或加一个数，最终得到更大方格的方案数。
如果当前被染色的区域是个 r ( r ≥ 2 ) 行 c ( c ≥ 2 ) 列的矩形，那么接下来要么扩充成r+1 行 c列的矩阵(扩充行)，要么扩充成 r行 c + 1列的矩形(扩充列)。并且根据当前状态中最后一个被染色的格子在哪个角上，扩充行/列的方案都是唯一的。
从 1 ∗ 1 的矩阵，到 n ∗ m 的矩阵，一共要扩充n+m-2
次，其中有 n − 1次是扩充行，这样的决策有下面的一个式子来表示：
$C_{n-1}^{n+m-2}$
最后一定要注意一个特判的情况，n=1和m=1的时候我们直接算答案就行（不注意这一点的话会出错 ）
最后值得说一下的就是上面提到的lucas定理，其实这么长时间了我也是第一次遇到，像这种定理一般都是在特定的地方有特定的作用，平时还是要注重积累。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10,mod=1e9+7;ll fact[N],infact[N];ll qmi(ll a,ll k,ll p)//快速幂求逆元
{ll res=1;while(k){if(k&1) res=(ll)res*a%p;k>>=1;a=(ll)a*a%p;}return res;
}
ll C(ll a,ll b,ll mod)//小费马求组合数
{return (ll)fact[a]*infact[b]%mod*infact[a-b]%mod;
}
ll lucas(ll n,ll m,ll p)//卢卡斯定理，这里直接套用上面链接里的公式
{if(m==0) return 1;return (C(n%p,m%p,p)*lucas(n/p,m/p,p)%p);
}
int main()
{fact[0]=1,infact[0]=1;for(int i=1; i<N; i++)//预处理{fact[i]=(ll)fact[i-1]*i%mod;infact[i]=(ll)infact[i-1]*qmi(i,mod-2,mod)%mod;}int t;scanf("%d",&t);while(t--){ll n,m;ll ans=0;scanf("%lld%lld",&n,&m);if(n==1||m==1) ans=2;else{ans=4*lucas(n+m-2,n-1,mod);}ans=ans%mod;printf("%lld\n",ans);}return 0;
}

题目H

这道题我当时是很迷的，但是完事之后再回来看的时候又感觉到好像是当时的思路没有打开。先介绍题意：a需要找b，然后这里给出了三类人，支持，不支持，无所谓，每个人（除了a）都在不同的房间里，对每一个人可以询问三种问题：b在几号房，你是谁，谁在x号房，支持者会给出真，不支持者会给出假，第三类会随意给出，现在给出三类人的数量，现在判断a是否能找到b，如果能找到，至少询问几个问题
队友的思路：如果支持者大于另两类之和，显然a总能找到b，因为a只要问下一个人，他必定答真。里面还有一种特殊情况，就是给出的三个数是1,0,0，代表只有一个b，就无需询问了，所以这里要特判一下询问的次数是零。

代码

#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
int a,b,c;
int main() {cin >>a>>b>>c;if(a==1&&b==0&&c==0)cout <<"YES\n0";else if(a>b+c)cout <<"YES\n"<<2*(b+c)+1;else cout <<"NO";return 0;
}

题目K

就是一道纯纯的几何题，题意上没有什么值得特别注意的，就是给出四个点，前三个点确定一个三角形，然后对于第四个点，如果这个点不在边界上输出-1，如果点在边界上，求出在三角形边界上的另一个点，使得两点间连线能够将三角形平分成两个面积相等的部分

思路：首先判断给出的点是否在边界上，如果不在就直接输出-1，如果在，就尝试另外两条边上的两点，求出总三角形面积。这里主要是分出了两种情况，一种是点就在端点上，这种情况其实是比较简单的，因为另一个点一定就是对边的中点；另一种情况就是在边上，这种情况也是要分成三种子情况，因为总共有三条边，然后另外一个点一定在另外两条边的其中一条上，所以这边也要判断一下究竟是在哪一条边上。

代码

#include <bits/stdc++.h>
using namespace std;typedef long long ll;const double eps = 1e-10;int sign(double x)//判断浮点数的符号
{if(fabs(x) <= eps) return 0;if(x > 0) return 1;else return -1;
}struct Point
{double x,y;Point() {}//定义运算Point(double _x,double _y){x = _x;y = _y;}Point operator + (const Point &b)const{return Point(x+b.x,y+b.y);}Point operator - (const Point &b)const{return Point(x-b.x,y-b.y);}Point operator * (const double &k)const //乘常数{return Point(x*k,y*k);}Point operator / (const double &k)const{return Point(x/k,y/k);}double len(){return x * x + y * y;}
};
typedef Point Vector;//定义将点重定义为向量
Point p[4],pp;//直接预定义变量，p三个点，pp一个点double cross(Vector a,Vector b)//叉积
{return a.x * b.y - a.y * b.x;
}
double dot(Vector a,Vector b)//点积
{return a.x * b.x + a.y * b.y;
}
double dis(Point a,Point b)//两点之间的距离
{return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}
Point answer(int flag)
{Point ans;if(flag == 1){double d1 = dis(pp,p[2]);double d2 = dis(pp,p[3]);if(fabs(d1 - d2) <= eps)ans = p[1];else{double rate;Vector v1,v2,v3;if(d1 > d2){v1 = pp - p[2],v2 = p[1] - p[2],v3 = p[3] - p[2];double dd = fabs(cross(v1,v2)) / v2.len();double hh = fabs(cross(v3,v2)) / v2.len();rate = hh / dd;ans = p[2] + (p[1]-p[2]) * 0.5 * rate;}else{v1 = pp - p[3],v2 = p[1] - p[3],v3 = p[2] - p[3];double dd = fabs(cross(v1,v2)) / v2.len();double hh = fabs(cross(v3,v2)) / v2.len();rate = hh / dd;ans = p[3] + (p[1]-p[3]) * 0.5 * rate;}}}else if(flag == 2){double d1 = dis(pp,p[1]);double d2 = dis(pp,p[3]);if(fabs(d1 - d2) <= eps)ans = p[2];else{double rate;Vector v1,v2,v3;if(d1 > d2){v1 = pp - p[1],v2 = p[2] - p[1],v3 = p[3] - p[1];double dd = fabs(cross(v1,v2)) / v2.len();double hh = fabs(cross(v3,v2)) / v2.len();rate = hh / dd;ans = p[1] + (p[2]-p[1]) * 0.5 * rate;}else{v1 = pp - p[3],v2 = p[2] - p[3],v3 = p[1] - p[3];double dd = fabs(cross(v1,v2)) / v2.len();double hh = fabs(cross(v3,v2)) / v2.len();rate = hh / dd;ans = p[3] + (p[2]-p[3]) * 0.5 * rate;}}}else if(flag == 3){double d1 = dis(pp,p[1]);double d2 = dis(pp,p[2]);if(fabs(d1 - d2) <= eps)ans = p[3];else{double rate;Vector v1,v2,v3;if(d1 > d2){v1 = pp - p[1],v2 = p[3] - p[1],v3 = p[2] - p[1];double dd = fabs(cross(v1,v2)) / v2.len();double hh = fabs(cross(v3,v2)) / v2.len();rate = hh / dd;ans = p[1] + (p[3]-p[1]) * 0.5 * rate;}else{v1 = pp - p[2],v2 = p[3] - p[2],v3 = p[1] - p[2];double dd = fabs(cross(v1,v2)) / v2.len();double hh = fabs(cross(v3,v2)) / v2.len();rate = hh / dd;ans = p[2] + (p[3]-p[2]) * 0.5 * rate;}}}return ans;
}
void solve()
{Point ans;for(int i = 1; i <= 3; i ++)scanf("%lf%lf",&p[i].x,&p[i].y);scanf("%lf%lf",&pp.x,&pp.y);if(pp.x == p[1].x && pp.y == p[1].y)//判断第四个点是否是端点{Point mid = (p[2] + p[3]) / 2.0;printf("%.10f %.10f\n",mid.x,mid.y);return ;}if(pp.x == p[2].x && pp.y == p[2].y){Point mid = (p[1] + p[3]) / 2.0;printf("%.10f %.10f\n",mid.x,mid.y);return ;}if(pp.x == p[3].x && pp.y == p[3].y){Point mid = (p[1] + p[2]) / 2.0;printf("%.10f %.10f\n",mid.x,mid.y);return ;}int flag = 0;//判断第四个点是否合法Vector v1 = pp - p[1],v2 = pp - p[2],v3 = pp - p[3];if(sign(dot(v1,v2)) == -1 && sign(cross(v1,v2)) == 0) flag = 3;else if(sign(dot(v1,v3)) == -1 && sign(cross(v1,v3)) == 0) flag = 2;else if(sign(dot(v2,v3)) == -1 && sign(cross(v2,v3)) == 0) flag = 1;if(!flag){printf("-1\n");return ;}ans=answer(flag);//flag 1表示在p2和p3两点之间的边上，2表示在p1和p3之间的边上，3表示在p1和p2之间的边上printf("%.10f %.10f\n", ans.x, ans.y);
}int main()
{int T;scanf("%d",&T);while(T--){solve();}return 0;
}