2019南京区域赛
2019年南京区域赛 .
以下题目按照个人认为的难度顺序排列.
题目连接
https://www.jisuanke.com/contest/5528/challenges
A. A Hard Problem
一般这种标题都是正话反说?
可能看到这个题之后,有灵感的人可以立马猜出结论.
我个人倾向于打表找规律,利用位运算枚举小数据的情况,得到一个大概结论的规律.
打表代码
#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
char ch=getchar();int f=1,x=0;
while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
return f*x;
}
bool ok(vector<int> chosen){
for(int i=0;i<chosen.size();i++)
for(int j=0;j<chosen.size();j++)
if(i!=j){
int a=chosen[i];
int b=chosen[j];
if(a>b) if(a%b==0) return true;
else if(b%a==0) return true;
}
return false;
}
bool solve(int n,int k){
for(int i=1;i<=((1<<n)-1);i++){
vector<int> vec;
for(int j=0;j<n;j++)
if((1<<j)& i) vec.pb(j+1);
if(vec.size()==k)
if(ok(vec)==0) return false;
}
return true;
}
int main(){
/*
int n,k;while(cin>>n>>k){
cout<<solve(n,k)<<endl;
}
*/
for(int n=2;n<=20;n++){
int ans=n;
for(int j=n;j>=1;j--){
if(solve(n,j)==0) break;
ans=j;
}
cout<<n<<" : "<<ans<<endl;
}
return 0;
}通过代码
//ac
#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
char ch=getchar();int f=1,x=0;
while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
return f*x;
}
int main(){
int T=read();while(T--){
int n=read();
cout<<(n+1)/2+1<<"\n";
}
return 0;
}H Prince and Princess
这个题在现场赛的时候坑了不少队伍,感觉一方面是题意杀,另一方面是1 0 0 这个数据可能没想到.
在这个题目当中,随机的人和存心捣乱的人可以看成一类人,
输入为1 0 0 的时候其实一个人都不用问了,因为只有一个人肯定是公主.
这个题目可能可以吸取的教训是从比较小的数据开始推算一下结果,可能就会把一些特殊情况规避掉.
通过代码
#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
char ch=getchar();int f=1,x=0;
while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
return f*x;
}
int main(){
int a,b,c;
while(~scanf("%d%d%d",&a,&b,&c)){
if(a==1&&b==0&&c==0) printf("YES\n0\n");
else if(a>b+c) printf("YES\n%d\n",2*(b+c)+1);
else printf("NO\n");
}return 0;
}K. Triangle
一个较为基础的计算几何题目,二分的思路也非常好想.
计算几何非常容易写出问题,因为涉及到很多double的运算,往往是非常危险的,而且比较难出样例进行测试.
是时候需要整理一下计算几何的模板了.
下面放几份我通过的代码,细节实现略有不同.
通过代码1
// first
//
#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
char ch=getchar();int f=1,x=0;
while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
return f*x;
}
const double eps=1e-6;
struct point
{
double x; //x坐标
double y; //y坐标
}a,b,c,p; //定义点
//判断点是否在线上，在返回1，不在返回0
int onSegement(point p1,point p2,point Q)
{
double maxx,minx,maxy,miny;
maxx = p1.x >p2.x ?p1.x :p2.x ; //矩形的右边长
minx = p1.x >p2.x ?p2.x :p1.x ; //矩形的左边长
maxy = p1.y >p2.y ?p1.y :p2.y ; //矩形的上边长
miny = p1.y >p2.y ?p2.y :p1.y ; //矩形的下边长
if( ((Q.x -p1.x )*(p2.y -p1.y) == (p2.x -p1.x) *(Q.y -p1.y)) && ( Q.x >= minx && Q.x <= maxx ) && ( Q.y >= miny && Q.y <= maxy))
return 1;
else
return 0;
}
#define x1 x_1
#define y1 y_1
#define x2 x_2
#define y2 y_2
#define x3 x_3
#define y3 y_3
double cal(point a,point b,point c){
double x_1=a.x;
double y_1=a.y;
double x_2=b.x;
double y_2=b.y;
double x_3=c.x;
double y_3=c.y;
double ans=fabs(0.5*(x1*y2+x2*y3+x3*y1-x1*y3-x2*y1-x3*y2));
return ans;
// bug is here 我居然写了两次 - x_1*y_3 :|
// 实际上第一份代码就是cal函数没写对,泪目
double res=fabs(0.5*(x_1*y_2+x_2*y_3+x_3*y_1-x_1*y_3-x_1*y_3-x_2*y_1-x_3*y_2));
return res;
}
/*
double cal(point a,point b,point c){
double x_1=a.x;
double y_1=a.y;
double x_2=b.x;
double y_2=b.y;
double x_3=c.x;
double y_3=c.y;
double res=fabs(0.5*(x_1*y_2+x_2*y_3+x_3*y_1-x_1*y_3-x_1*y_3-x_2*y_1-x_3*y_2));
return res;
}
*/
int main(){
int T=read();while(T--){
scanf("%lf%lf",&a.x,&a.y);
scanf("%lf%lf",&b.x,&b.y);
scanf("%lf%lf",&c.x,&c.y);
scanf("%lf%lf",&p.x,&p.y);
if(fabs(p.x*2-a.x-b.x)<eps && fabs(p.y*2-a.y-b.y) <eps) {
printf("%.12f %.12f\n",c.x,c.y);
continue;
}
else if(fabs(p.x*2-a.x-c.x)<eps && fabs(p.y*2-a.y-c.y)<eps) {
printf("%.12f %.12f\n",b.x,b.y);
continue;
}else if(fabs(p.x*2-b.x-c.x)<eps && fabs(p.y*2-b.y-c.y)<eps){
printf("%.12f %.12f\n",a.x,b.y);
continue;
}
if(onSegement(a,b,p)) ;
else if(onSegement(b,c,p)) swap(a,c);
else if(onSegement(a,c,p)) swap(b,c);
else {
printf("-1\n");
continue;
}
double area1=cal(a,p,c);
double area2=cal(b,p,c);
if(area1>=area2) ;
else swap(a,b);
double area=cal(a,b,c)*0.5;
double l=0,r=1;
int cnt=1000;
point ans;
while(cnt--){
double m=(l+r)*0.5;
point pos;
pos.x=a.x+(c.x-a.x)*m;
pos.y=a.y+(c.y-a.y)*m;
double tmp=cal(pos,a,p);
ans.x=pos.x;
ans.y=pos.y;
if(tmp<area) l=m;
else r=m;
}
printf("%.15f %.15f\n",ans.x,ans.y);
}
return 0;
}通过代码2
#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long #define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
char ch=getchar();int f=1,x=0;
while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
return f*x;
}
#define db double
const db eps=1e-9;
class point{
public:
double x;
double y;
point(double x_=0,double y_=0):x(x_),y(y_){}
friend const point operator+(const point& p1,const point& p2){
return point(p1.x+p2.x,p1.y+p2.y);
};
friend const point operator-(const point& p1,const point& p2){
return point(p1.x-p2.x,p1.y-p2.y);
};
friend const point operator*(const point& p,const double& m){
return point(p.x*m,p.y*m);
};
friend const point operator*(const double& m,const point& p){
return point(p.x*m,p.y*m);
};
friend const point operator/(const point& p,const double& m){
return point(p.x/m,p.y/m);
};
friend ostream& operator <<(ostream& out,point& a){
printf("(%lf,%lf)",a.x,a.y);
return out;
};
}a,b,c,p;
typedef point vect2;//重命名，向量也是用坐标表示
class line{
public:
point start;
point end;
line(point s=point(0,0),point e=point(0,0)):start(s),end(e){}
};
double cross(point O,point A,point B){//叉乘
double oa_x=A.x-O.x;
double oa_y=A.y-O.y;
double ob_x=B.x-O.x;
double ob_y=B.y-O.y;
return oa_x*ob_y-oa_y*ob_x;
}
bool pointIsOnLine(point O,line L){
point S=L.start;
point E=L.end;
if(cross(O,S,E)==0//在直线L上
and min(S.x,E.x)<=O.x&&O.x<=max(S.x,E.x)
and min(S.y,E.y)<=O.y&&O.y<=max(S.y,E.y))
return true;
else return false;
}
double getArea(point a,point b,point c){
return fabs(0.5*cross(a,b,c));
}
/*
double cal(point a,point b,point c){
db dis1=sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
db dis2=sqrt((a.x-c.x)*(a.x-c.x)+(a.y-c.y)*(a.y-c.y));
db dis3=sqrt((b.x-c.x)*(b.x-c.x)+(b.y-c.y)*(b.y-c.y));
double aa=dis1;
double bb=dis2;
double cc=dis3;
double p=0.5*(aa+bb+cc);
return sqrt(p*(p-aa)*(p-bb)*(p-cc));
}
*/
point getMid(point a,point b){
return point(0.5*(a.x+b.x),0.5*(a.y+b.y));
}
int main(){
int T=read();while(T--){
scanf("%lf%lf",&a.x,&a.y);
scanf("%lf%lf",&b.x,&b.y);
scanf("%lf%lf",&c.x,&c.y);
scanf("%lf%lf",&p.x,&p.y);
line ab=line(a,b);
line bc=line(b,c);
line ac=line(a,c);
if(pointIsOnLine(p,ab)) ;
else if(pointIsOnLine(p,bc)) swap(a,c);
else if(pointIsOnLine(p,ac)) swap(b,c);
else {
printf("-1\n");
continue;
}
//--------------------------------------------------------------
if(fabs(p.x-a.x)<eps && fabs(p.y-a.y)<eps) {
point o=getMid(b,c);
printf("%.15f %.15f\n",o.x,o.y);
continue;
}else if(fabs(p.x-b.x)<eps && fabs(p.y-b.y) < eps){
point o=getMid(a,c);
printf("%.15f %.15f\n",o.x,o.y);
continue;
}
else if(fabs(p.x-c.x)<eps && fabs(p.y-c.y) <eps) {
point o=getMid(a,b);
printf("%.15f %.15f\n",o.x,o.y);
continue;
}
point o=getMid(b,c);
if(fabs(o.x-p.x)<eps && fabs(o.y-p.y)<eps) {
printf("%.15f %.15f\n",a.x,a.y);
continue;
}
o=getMid(a,b);
if(fabs(o.x-p.x)<eps && fabs(o.y-p.y) < eps){
printf("%.15f %.15f\n",c.x,c.y);
continue;
}
o=getMid(a,c);
if(fabs(o.x-p.x)<eps && fabs(o.y-p.y) <eps){
printf("%.15f %.15f\n",b.x,b.y);
continue;
}
//--------------------------------------------------------------
double area1=getArea(a,p,c);
double area2=getArea(b,p,c);
if(fabs(area1-area2)<eps) {
printf("%.15f %.15f\n",c);
}else if(area1<area2) swap(a,b);
double l=0,r=1;
double area=getArea(a,b,c)*0.5;
int cnt=1000;
while(cnt--){
double m=(l+r)*0.5;
point pos;
pos.x=a.x+(c.x-a.x)*m;
pos.y=a.y+(c.y-a.y)*m;
double tmp=getArea(pos,a,p);
if(tmp<area) l=m;
else r=m;
}
double delta=l;
point ans;
ans.x=a.x+(c.x-a.x)*delta;
ans.y=a.y+(c.y-a.y)*delta;
printf("%.15f %.15f\n",ans.x,ans.y);
}
return 0;
}D. Digital Path
记忆化搜索,本质上是一个有向无环图,这就很适合使用dp来解决这个问题.
一个可能的坑点是 -2 -1 0 1 2 这种链也是符合条件的.
#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
char ch=getchar();int f=1,x=0;
while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
return f*x;
}
const int maxv=1e3+10;
int a[maxv][maxv];
ll dp[maxv][maxv][6];
bool vis[maxv][maxv];
int n,m;
bool in(int x,int y){
if(x>=1&&x<=n&&y>=1&&y<=m) return true;
return false;
}
int dx[]={-1,0,1,0};
int dy[]={0,-1,0,1};
const ll mod=1e9+7;
void foo(int x,int y){
if(vis[x][y]) return;
//cout<<x<<" "<<y<<endl;
bool flag=0;
for(int i=0;i<4;i++){
int tx=x+dx[i];
int ty=y+dy[i];
/*
cout<<"tx "<<tx<<" ty "<<ty<<endl;
cout<<in(tx,ty)<<endl;
*/
if(in(tx,ty)){
if(a[x][y]==a[tx][ty]+1) {
foo(tx,ty);
for(int i=1;i<=3;i++){
dp[x][y][i+1]+=dp[tx][ty][i];
dp[x][y][i+1]%=mod;
}
dp[x][y][4]+=dp[tx][ty][4];
dp[x][y][4]%=mod;
}
}
}
vis[x][y]=true;
return ;
}
int main(){
while(~scanf("%d%d",&n,&m)){
inc(i,1,n) inc(j,1,m) {
scanf("%d",&a[i][j]);
dp[i][j][0]=dp[i][j][1]=dp[i][j][2]=dp[i][j][3]=dp[i][j][4]=0;
vis[i][j]=0;
}
inc(i,1,n) inc(j,1,m) {
int o=0;
inc(k,0,3){
int x=i,y=j,tx=dx[k]+i,ty=dy[k]+j;
if(in(tx,ty)){
if(a[tx][ty]+1==a[x][y]) o++;
}
}
if(o==0) dp[i][j][1]=1,vis[i][j]=1;
}
inc(i,1,n) inc(j,1,m) foo(i,j);
/*
inc(i,1,n){
inc(j,1,m) printf("%4d",dp[i][j][3]);
putchar('\n');
}
inc(i,1,n) {
inc(j,1,m) printf("%4d",dp[i][j][4]);
putchar('\n');
}
*/
ll res=0;
inc(i,1,n) {
inc(j,1,m){
int chu=0;
int x=i,y=j;
for(int k=0;k<=3;k++){
int tx=x+dx[k];
int ty=y+dy[k];
if(a[tx][ty]==a[x][y]+1) chu++;
}
if(chu==0) res=(res+dp[x][y][4])%mod;
}
}
printf("%lld\n",res);
}return 0;
}J. Spy
感觉是很巧妙的,略微有点题意杀.
利用了二分图最大权匹配的模型,KM算法各种资料上都是 $n^4$的,或者有的模板号称是$n^3$,但是其实很慢.
如果现场赛没有合适的模板就会gg,还是平时注重积累吧.
https://blog.csdn.net/qq_43497140/article/details/103337606
这个代码的 KM算法部分 是网上找的,有时间自己研究一下KM算法具体的原理,暂时把这个代码加入模板吧.
通过代码
#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
char ch=getchar();int f=1,x=0;
while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
return f*x;
}
const int maxv=400+10;
ll a[maxv],p[maxv],b[maxv],c[maxv];
const int N=maxv;
int n;
int nx,ny;
#define g w
int g[N][N];
int linker[N];
ll lx[N],ly[N];
ll slack[N];
bool visx[N],visy[N];
ll pre[N];
void bfs( ll k ){
ll x , y = 0 , yy = 0 , delta;
memset( pre , 0 , sizeof(pre) );
for( ll i = 1 ; i <= n ; i++ ) slack[i] = LONG_MAX;
linker[y] = k;
while(1){
x = linker[y]; delta = LONG_MAX; visy[y] = true;
for( ll i = 1 ; i <= n ;i++ ){
if( !visy[i] ){
if( slack[i] > lx[x] + ly[i] - w[x][i] ){
slack[i] = lx[x] + ly[i] - w[x][i];
pre[i] = y;
}
if( slack[i] < delta ) delta = slack[i] , yy = i ;
}
}
for( ll i = 0 ; i <= n ; i++ ){
if( visy[i] ) lx[linker[i]] -= delta , ly[i] += delta;
else slack[i] -= delta;
}
y = yy ;
if( linker[y] == -1 ) break;
}
while( y ) linker[y] = linker[pre[y]] , y = pre[y];
}
ll KM(){
memset( lx , 0 ,sizeof(lx) );
memset( ly , 0 ,sizeof(ly) );
memset( linker , -1, sizeof(linker) );
for( ll i = 1 ; i <= n ; i++ ){
memset( visy , false , sizeof(visy) );
bfs(i);
}
ll res = 0 ;
for( ll i = 1 ; i <= n ; i++ ){
if( linker[i] != -1 ){
res += w[linker[i]][i] ;
}
}
return res;
}
/*
bool DFS(int x){
visx[x] = true;
for(int y = 0; y < ny; y++){
if(visy[y])continue;
ll tmp = lx[x] + ly[y]-g[x][y];
if(tmp == 0){
visy[y] = true;
if(linker[y] == -1 || DFS(linker[y])){
linker[y] = x;
return true;
}
}
else if(slack[y] > tmp)
slack[y] = tmp;
}
return false;
}
ll KM(){
memset(linker,-1,sizeof(linker));
memset(ly,0,sizeof(ly));
for(int i = 0;i < nx;i++){
lx[i] = LONG_MIN;
for(int j = 0;j < ny;j++)
if(g[i][j] > lx[i])
lx[i] = g[i][j];
}
for(int x = 0;x < nx;x++){
for(int i = 0;i < ny;i++)
slack[i] = LONG_MAX;
while(true){
memset(visx,false,sizeof(visx));
memset(visy,false,sizeof(visy));
if(DFS(x))break;
ll d = LONG_MAX;
for(int i = 0;i < ny;i++)
if(!visy[i] && d > slack[i])
d = slack[i];
for(int i = 0;i < nx;i++)
if(visx[i])
lx[i]-= d;
for(int i = 0;i < ny;i++){
if(visy[i])ly[i] += d;
else slack[i]-= d;
}
}
}
ll res = 0;
for(int i = 0;i < ny;i++)
if(linker[i] != -1)
res += g[linker[i]][i];
return res;
}
*/
void getw(){
inc(i,1,n) scanf("%lld",a+i);
inc(i,1,n) scanf("%lld",p+i);
inc(i,1,n) scanf("%lld",b+i);
inc(i,1,n) scanf("%lld",c+i);
inc(i,1,n) inc(j,1,n) {
w[i][j]=0;
ll v=b[i]+c[j];
inc(k,1,n) if(v>a[k]) w[i][j]+=p[k];
}
}
bool show=false;
int main(){
while(~scanf("%d",&n)){
getw();
nx=ny=n;
if(show)
inc(i,1,n) {
inc(j,1,n) printf("%4lld",w[i][j]);
putchar('\n');
}
printf("%lld\n",KM());
}return 0;
}B. chessboard
lucas定理在这个题目中作为了STL一样的工具性存在.
这个题目真的是太太太太难读了!!!
我说一个我认为是正确的理解: 要保证在涂格子的任何时刻,已经涂的格子中任何两个在已涂格子上的距离等于曼哈顿距离.
另外一个困难就是要得到得到最后结果的公式,感觉挺需要数学直觉的.
可能需要场上自己想一些小样例之后大力猜结论.
通过代码
#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
char ch=getchar();int f=1,x=0;
while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
return f*x;
}
const int N=2e6+10;
const ll mod=1e9+7;
ll a[N];
void init(){ a[0]=1; inc(i,1,2000000) a[i]=a[i-1]*i%mod; }
ll ksm(ll a,ll n,ll p){
ll res=1;
while(n){
if(n&1) res=res*a%p;
a=a*a%p;
n>>=1;
}return res;
}
ll c(ll n,ll m,ll p){
if(n<m) return 0;
return a[n]*ksm(a[m],p-2,p)%p*ksm(a[n-m],p-2,p)%p;
}
int main(){
init();int T=read();while(T--){
ll n,m;scanf("%lld%lld",&n,&m);
if(n==1&&m==1) printf("1\n");
else if(n==1 || 1==m) printf("2\n");
else printf("%lld\n",4LL*c(n+m-2,n-1,mod)%mod);
}return 0;
}and More
本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！