2 solutions

  • 1
    @ 2022-9-11 22:07:22

    我们将一个人的成绩对应到三维空间中的位置向量,pi=(x,y,z)\vec p_i=(x,y,z),一种排名的计算步骤被抽象为

    1. 确定一个法向量v\vec v , 这个法向量需要满足这些条件:
    • vv>0\vec v \cdot \vec v > 0
    • v\vec v指向第一卦限(v[0],v[1],v[2]0\vec v[0],\vec v[1],\vec v[2]\ge 0)
    1. $\text{GPA}_i=v[0]p[0]+v[1]p[1]+v[2]p[2]=\vec v \cdot \vec p_i$,随后就可以得到小林排名。

    为什么这里不需要限制v[0]+v[1]+v[2]=1v[0]+v[1]+v[2] = 1呢?这是因为只要v[0]+v[1]+v[2]0v[0]+v[1]+v[2] \neq 0,计算出来的GPA只是等比例放大缩小,不影响排名。

    设小林的位置向量是Q\vec Q,利用v\vec v当作平面的法向量,可以确定一个过Q\vec Q点的平面F(v)\mathbb F(\vec v)(关于v\vec v的函数)。

    虽然F(v)\mathbb F(\vec v)千变万化,但是我们并不需要考虑那么多的情况,实际上我们只需要考虑:

    • F(v)\mathbb F(\vec v)经过包括QQ点的至少三个点
    • v=x or y or z\vec v=x \text{ or } y \text{ or } z

    rank(F)\text{rank}(\mathbb F)表示如果确定平面是F\mathbb F,小林的排名是多少,我们发现使得小林排名最高的F\mathbb F中,一定至少有一个F0\mathbb F_0经过了包括QQ点的至少三个点,即"临界条件"(使得rank(F)\text{rank}(\mathbb F)变化)。

    而还有三个临界条件,分别就是Oxy,Oyz,OxzOxy,Oyz,Oxz

    此时O(n3)O(n^3)算法就有了,枚举两个点R,SR,S,法向量就是n=RQ×SQ\vec n=\vec {RQ} \times \vec {SQ}(或者n-\vec n),然后计算所有人的GPA得到小林的排名。记得把v=(1,0,0),(0,1,0),(0,0,1)\vec v=(1,0,0),(0,1,0),(0,0,1)这几种情况考虑进去。

    mm维的情况也有对应的O(nm)O(n^m)的算法。这启示我们一件事,确定评价标准是一个非常主观的事情,可以让你高也让你低。所以最重要的还是是学到真正的本事。

    #ifndef H1__
    #define H2__
    #include<bits/stdc++.h>
    using namespace std;
    int qr(){
    	int ret=0,c=getchar();
    	while(!isdigit(c)) c=getchar();
    	while( isdigit(c)) ret=ret*10+c-48,c=getchar();
    	return ret;
    }
    using ll = long long;
    int n;
    const int maxn=5050+5;
    
    struct NODE{
    	ll x,y,z;
    	NODE():x(),y(),z(){}
    	NODE(const ll&a,const ll&b,const ll&c):x(a),y(b),z(c){}
    	NODE(const NODE&a):x(a.x),y(a.y),z(a.z){}
    	NODE operator - (const NODE&a)const{
    		return NODE(x-a.x,y-a.y,z-a.z);
    	}
    	NODE operator - ()const{
    		return NODE(-x,-y,-z);
    	}
    	NODE operator % (const NODE&a)const{
    		const ll&X=a.x;
    		const ll&Y=a.y;
    		const ll&Z=a.z;
    		return NODE(y*Z-z*Y,-x*Z+z*X,x*Y-y*X);
    	}
    	long long operator * (const NODE&a)const{
    		return x*a.x+y*a.y+z*a.z;
    	}
    	long long&operator[](const int&a){
    		assert(0<=a&&a<=2);
    		if(a==0) return x;
    		else if(a==1) return y;
    		else return z;
    		//impossible case
    	}
    	NODE&operator = (const NODE&a){
    		x=a.x; y=a.y; z=a.z;
    		return *this;
    	}
    }dat[maxn];
    
    int calc(NODE normal){
    	if(normal[0]<0||normal[1]<0||normal[2]<0)
    		normal=-normal;
    	if(normal[0]<0||normal[1]<0||normal[2]<0)
    		return n;
    	if(normal*normal==0)
    		return n;
    	ll proj=normal*dat[1];
    	int cnt=0;
    	for(int t=2;t<=n;++t)
    		if(normal*dat[t]<=proj)
    			++cnt;
    	return n-cnt;
    }
    
    int main(){
    	n=qr();
    	for(int t=1;t<=n;++t){
    #ifdef H1__
    		int x=qr(),y=qr(),z=0;
    #else
    		int x=qr(),y=qr(),z=qr();
    #endif
    		dat[t]=NODE(x,y,z);
    	}
    	NODE vec=dat[2]-dat[1];
    	int f=1;	
    	for(int t=2;t<=n;++t)
    		if(vec%(dat[t]-dat[1])*(vec%(dat[t]-dat[1])))
    			f=0;
    	// if(vec[0]>=0&&vec[1]>=0&&vec[2]>=0) return cout<<n<<endl,0;
    	// vec=-vec;
    	// if(vec[0]>=0&&vec[1]>=0&&vec[2]>=0) return cout<<n<<endl,0;
    	if(f) return puts("1"),0;
    #ifdef H1__
    	NODE v2=NODE(0,0,1);
    	int ans=n;
    	for(int t=2;t<=n;++t){
    		NODE v1=dat[t]-dat[1];
    		NODE normal=v1%v2;
    		//cerr<<normal[0]<<' '<<normal[1]<<endl;
    		ans=min(ans,calc(normal));
    	}
    	//cerr<<"H1__"<<endl;		
    #else
    	int ans=n;
    	for(int t=2;t<=n;++t){
    		for(int i=2;i<=n;++i){
    			NODE v1=dat[t]-dat[1],v2=dat[i]-dat[1];
    			NODE normal=v1%v2;
    			//cerr<<normal[0]<<' '<<normal[1]<<endl;
    			//cerr<<v1[0]<<' '<<v1[1]<<' '<<v1[2]<<endl;
    			ans=min(ans,calc(normal));
    		}
    	}	
    	//cerr<<"!H1__"<<endl;
    #endif
    	ans=min({ans,calc({1,0,0}),calc({0,1,0}),calc({0,0,1})});
    	cout<<ans<<endl;
    	return 0;
    }
    #undef H1__
    #endif
    
    • 0
      @ 2022-9-13 13:01:34

      emmm……我看1≤n≤450,要不这道题暴力破解好了…… 我们以0.01为精度,依次枚举各部分分数占比,这样就能得到小林的最高排名了。 显然这也是一个O(n^3)的算法。 考虑到float乘int会比int乘int慢一些(如有不对请指出),我们枚举时会将 for(float i=0.00;i<=1.00;i+=0.01)改写为 for(int i=0;i<=100;++i)。 代码见下:

      #include<bits/stdc++.h>
      using namespace std;
      int n,ans;
      int c1,c2;
      struct node{
      	bool b;
      	int x,y,z;
      	int all;
      }scr[451];
      bool cmp(node a,node b){
      	if(a.all>b.all) return true;
      	if(a.all==b.all&&b.b==true) return true;
      	return false;
      }
      
      int main(){
      	scanf("%d",&n);
      	scr[1].b=true;
      	for(int i=1;i<=n;++i){
      		scanf("%d%d%d",&scr[i].x,&scr[i].y,&scr[i].z);
      	}
      	ans=450;
      
      	for(c1=0;c1<=100;c1++){
      		for(c2=0;c2<=100-c1;c2++){
      			for(int i=1;i<=n;++i){
      				scr[i].all=c1*scr[i].x+c2*scr[i].y+(100-c1-c2)*scr[i].z;
      			}
      			sort(scr+1,scr+n+1,cmp);
      			int scr1=-1,rck=-1;
      			//for(int i=1;i<=n;++i)) printf("c1=%d,c2=%d,scr[%d]=%d\n",c1,c2,i,scr[i].all);
      			for(int i=1;i<=n;++i){
      				if(scr1!=scr[i].all){
      					scr1=scr[i].all;
      					rck=i;
      
      				}
      				if(scr[i].b==true){
      					if(rck<ans) ans=rck;
      					break;
      				}
      			}
      		}
      	}
      
      	printf("%d",ans);
      	return 0;
      }
      

      (中间有一些注释是我比赛时debug用的) (其实H1也能枚举过,不过枚举的精度应当是1/2907,因为似乎有个测试数据跟17或19有点关系(2907=9*17*19))

      • @ 2022-9-14 15:24:39

        这种做法能通过的比较重要的原因是本题的值域非常小且为整点。也就是说命题人造数据的时候并没有考虑到还有这种做法

    • 1

    Information

    ID
    160
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    9
    Tags
    (None)
    # Submissions
    242
    Accepted
    16
    Uploaded By