2019南京站（重温经典）

导语

日常练习，这一次做的不是很满意

涉及的知识点

思维，乘法逆元，组合数学，拓扑排序，DP，二分图最大权匹配，平面几何

链接：南京2019区域赛 [Cloned]

题目

A

题目大意：给出一个正整数n，找到一个最小的整数k使得集合 { 1 , 2 , … n } \{1,2,\dots n\} {1,2,…n}的任意一个大小为$k$的子集都至少存在两个元素使得其中一个是另一个的因子

思路：一开始认为是素数个数加1，但后来找到了反例：$1,2,3,4,5,6,7,8,9$，如果按照素数个数加一，那么k的大小为5，但是可以找到 { 5 , 6 , 7 , 8 , 9 } \{5,6,7,8,9\} {5,6,7,8,9}这个集合不满足条件
最简单的方法是直接找规律，可以发现k的大小为$2,3,3,4,4\dots$，结果就是$(n+1)/2+1$

代码

#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;
}

C

题目大意：给出一个数字矩阵，对路径的定义：从起始格到终点上元素必须严格递增，公差为1，并且终点之后不可再拓展，格子数不得小于4，求出路径条数

思路：一开始从方案数的方向取考虑，是没错的，但是对于4以及多于4的路径的统计就出现了问题，最后看了题解才知道，忽略了一个比较重要的点：终点之后不可拓展，但是可以从终点向前取4个，5个等，也就是，长度为7的路径，可以创造出长度为4,5,6,7的路径，那么其实可以将4以及4之后的方案数视为一个整体
设$dp[i][j][k]$表示以$(i,j)$为终点，长度为k的路径条数，可以得到这样的递推式：$dp[i][j][k]=dp[i][j][k]+dp[i^{\prime }][j^{\prime }][k-1]$，$(i^{\prime },j^{\prime })$是$(i,j)$的相邻格，元素之差为1且$(i,j)$数据更大
在基本上确定了dp的取法与定义后，接下来就是决定dp的顺序，对于任何路径来说，第一个点必然没有其他相邻点比它小，那么可以用DAG中出度与入度的概念，有比该点大1的相邻格，该点出度+1，有比该点小1的相邻格，该点入度-1，之后可以通过拓扑排序，构造不同路径长度下的可行方案数，其余见代码

代码

#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
int n,m,in[1212][1212],out[1212][1212],maze[1212][1212],Next[4][2]= {0,1,1,0,0,-1,-1,0};
ll res,dp[1212][1212][5];
const int mod=1e9+7;
struct node {int x,y;
};
void BFS() {queue<node>q;for(int i=1; i<=n; i++)for(int j=1; j<=m; j++)if(!in[i][j]) {//录入入度为0的节点，准备拓扑BFSq.push({i,j});dp[i][j][1]=1;}while(!q.empty()) {auto t=q.front();q.pop();int x=t.x,y=t.y;for(int i=0; i<4; i++) {int xx=x+Next[i][0],yy=y+Next[i][1];if(xx<1||yy<1||xx>n||yy>m)continue;if(maze[xx][yy]==maze[x][y]+1) {//邻接点可拓展，更新对应的方案数dp[xx][yy][2]=(dp[x][y][1]+dp[xx][yy][2])%mod;//邻接点长度为2方案数来自于(x,y)长度为1的方案dp[xx][yy][3]=(dp[x][y][2]+dp[xx][yy][3])%mod;//邻接点长度为3方案数来自于(x,y)长度为2的方案dp[xx][yy][4]=(dp[x][y][3]+dp[xx][yy][4]+dp[x][y][4])%mod;//邻接点长度大于等于4方案数来自于(x,y)长度为3的方案数与大于等于4的方案数if(--in[xx][yy]==0)q.push({xx,yy});//拓扑排序，出现新的根节点}}}
}
int main() {cin.tie(0);ios::sync_with_stdio(0);cin >>n>>m;for(int i=1; i<=n; i++)for(int j=1; j<=m; j++)cin >>maze[i][j];for(int i=1; i<=n; i++)for(int j=1; j<=m; j++)for(int k=0; k<4; k++) {int x=i+Next[k][0],y=j+Next[k][1];if(x<1||y<1||x>n||y>m)continue;if(maze[i][j]==maze[x][y]+1)in[i][j]++;//统计入度出度if(maze[i][j]==maze[x][y]-1)out[i][j]++;//同上}BFS();//广搜统计方案数for(int i=1; i<=n; i++)for(int j=1; j<=m; j++)if(!out[i][j])res=(res+dp[i][j][4])%mod;//对于出度为0的点统计经过该点长度大于等于4的方案数cout <<res;return 0;
}

H

题目大意：a需要找b，有三类人，支持a找到b（包括a），不支持，无所谓，每个人（除了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.tie(0);ios::sync_with_stdio(0);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;
}

J

题目大意：略

思路：KM模板题，需要注意图的构造，构造完后需要使用$O(n^3)$的模板求最大权完美匹配

代码

#include <bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=512;
int pre[maxn],match[maxn],delta[maxn],graph[maxn][maxn],n,res,l[maxn],r[maxn];
int a[maxn],p[maxn],b[maxn],c[maxn];
bool visl[maxn],visr[maxn];
void maxmatch(int u) {int x,y=0,d,id=0;memset(pre,0,sizeof(pre));//pre用来记录上一条边for(int i=1; i<=n; i++)delta[i]=inf;//初始化右点集match[y]=u;//初始化匹配关系while(1) {x=match[y];d=inf;//初始化visr[y]=1;//访问for(int i=1; i<=n; i++) {if(visr[i])continue;if(delta[i]>l[x]+r[i]-graph[x][i]) {//能否加一条边x-idelta[i]=l[x]+r[i]-graph[x][i];pre[i]=y;//连接一条未匹配边}if(delta[i]<d) {//找到一条修改值最少的点d=delta[i];//记录数值id=i;//记录编号}}for(int i=0; i<=n; i++)if(visr[i])l[match[i]]-=d,r[i]+=d;//尝试修改else delta[i]-=d;//该边不是最短边，减去后可能成为最短边y=id;if(match[y]==-1)break;//无法继续匹配}while(y) {//构造匹配match[y]=match[pre[y]];y=pre[y];}
}
int KM() {memset(match,-1,sizeof(match));//清空匹配memset(l,0,sizeof(l));memset(r,0,sizeof(r));for(int i=1; i<=n; i++) {memset(visr,0,sizeof(visr));maxmatch(i);//BFS左点集}for(int i=1; i<=n; i++)if(match[i]!=-1)res+=graph[match[i]][i];return res;
}
signed main() {ios::sync_with_stdio(0);cin.tie(0);cin >>n;for(int i=1; i<=n; i++)cin >>a[i];for(int i=1; i<=n; i++)cin >>p[i];for(int i=1; i<=n; i++)cin >>b[i];for(int i=1; i<=n; i++)cin >>c[i];//录入数据for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)for(int k=1; k<=n; k++)if(b[i]+c[j]>a[k])graph[i][j]+=p[k];//如果可以打败，建边cout <<KM();return 0;
}
/*
4
1 2 3 4
1 1 1 1
0 0 1 1
0 1 1 2
*/

K

题目大意：给出一个三角形，给出一个点，如果这个点不在边界上输出-1，如果点在边界上，求出另一个点，使得两点间连线能够将三角形平分成两个面积相等的部分

思路：首先判断给出的点是否在边界上，如果不在就直接输出-1，如果在，就尝试另外两条边上的两点，求出总三角形面积，如图，求出三角形在不同情况下满足总面积/2的高，然后根据高算出对应坐标即可

代码

#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;
}

参考文献

1. Digital Path（记忆化搜索）