---

 

预计分数：60+50+0=110

实际分数：60+81+0=144

全场rank13？全校rank1？貌似题很难啊23333

---

 

 

 

T1:

https://www.luogu.org/problem/show?pid=T11834

一道比noipT2还难的题，考场上果断打60分暴力走人

正解：对于字符a进行猜想，假定是最多的，计算a-b的值最大的就好

　　　后者可以用两个前缀和维护，代码实现的技巧比较多

 

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 const int MAXN=1001; 8 inline void read(int &n) 9 {10     char c=getchar();n=0;bool flag=0;11     while(c<'0'||c>'9')    c=='-'?flag=1,c=getchar():c=getchar();12     while(c>='0'&&c<='9')    n=n*10+c-48,c=getchar(); flag==1?n=-n:n=n;13 }14 string a;15 int happen[MAXN];16 int happenmax[MAXN][MAXN];17 int happenmin[MAXN][MAXN];18 int ans=0;19 int main()20 {21     //freopen("a.in","r",stdin);22     //freopen("a.out","w",stdout);23     int meiyong;24     cin>>meiyong;25     cin>>a;26     for(int i=0;i
           
            nowmax) nowmax=happen[k];36 if(happen[k]
            
             ans) ans=nowmax-nowmin;39 }40 }41 printf("%d",ans);42 return 0;43 }
            
           
          
         
        
       
      

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 const int MAXN=1001; 8 inline void read(int &n) 9 {10     char c=getchar();n=0;bool flag=0;11     while(c<'0'||c>'9')    c=='-'?flag=1,c=getchar():c=getchar();12     while(c>='0'&&c<='9')    n=n*10+c-48,c=getchar(); flag==1?n=-n:n=n;13 }14 string a;15 int happen[MAXN];16 int happenmax[MAXN][MAXN];17 int happenmin[MAXN][MAXN];18 int ans=0;19 int main()20 {21     //freopen("a.in","r",stdin);22     //freopen("a.out","w",stdout);23     int meiyong;24     cin>>meiyong;25     cin>>a;26     for(register int i=0;i
           
            nowmax) nowmax=happen[k];36 if(happen[k]
            
             ans) ans=nowmax-nowmin;39 }40 }41 printf("%d",ans);42 return 0;43 }
            
           
          
         
        
       
      

 

T2

https://www.luogu.org/problem/show?pid=T11832

noip难度居然有计算几何题，，，，，，。。。。。。。

幸亏不是很难

做这道题需要会两个东西

1.判断两直线相交

2.根据反射定理求对称点

但是悲催的是我第二个知识点不会，也就意味着我基本上五十分左右。

没办法，推推结论偏偏分吧，

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #define Vector Point 6 using namespace std; 7 inline void read(int &n) 8 { 9     char c=getchar();n=0;bool flag=0;10     while(c<'0'||c>'9')    c=='-'?flag=1,c=getchar():c=getchar();11     while(c>='0'&&c<='9')    n=n*10+c-48,c=getchar(); flag==1?n=-n:n=n;12 }13 const double PI=acos(-1);14 const double eps=1e-10;15 int dcmp(double x)    {
    return (fabs(x)
          
           <0?-1:1);}16 struct Point17 {18     double x,y;19     Point(double x=0,double y=0):x(x),y(y){};20 }pa,pb,qa,qb,ja,jb;21 Vector operator + (Vector A,Vector B) {
    return Vector(A.x + B.x,A.y + B.y);}22 Vector operator - (Vector A,Vector B) {
    return Vector(A.x - B.x,A.y - B.y);}23 Vector operator * (Vector A,double P) {
    return Vector(A.x * P,A.y * P);}24 Vector operator / (Vector A,double P) {
    return Vector(A.x / P,A.y / P);}25 bool operator < (const Point &a,const Point &b){
    return a.x < b.x || (a.x == b.x && a.y < b.y);}26 bool operator == (const Point &a,const Point &b){
    return dcmp(a.x - b.x)==0 && dcmp(a.y - b.y)==0;}27 28 double Cross(Vector A,Vector B){
    return A.x * B.y-A.y * B.x;}29 bool SPI(Point a1, Point a2, Point b1,Point b2)//判断两线段是否相交 30 {31     double c1 = Cross(a2-a1,b1-a1) , c2 = Cross(a2-a1,b2-a1),32            c3 = Cross(b2-b1,a1-b1) , c4 = Cross(b2-b1,a2-b1);33     return dcmp(c1)*dcmp(c2)<0 && dcmp(c3)*dcmp(c4)<0;34 }35 int main()36 {37     //freopen("b.in","r",stdin);38     //freopen("b.out","w",stdout);39     cin>>pa.x>>pa.y>>pb.x>>pb.y>>qa.x>>qa.y>>qb.x>>qb.y>>ja.x>>ja.y>>jb.x>>jb.y;40     if(SPI(pa,pb,ja,jb))    {cout<<"NO";return 0;}// 视线被镜子反射 41     if(SPI(pa,pb,qa,qb)==0&&SPI(pa,pb,ja,jb)==0)    {cout<<"YES";return 0;}//都没挡住 42     if(pa.x>pb.x)    swap(pa,pb);43     if(ja.x>jb.x)    swap(ja,jb);44     if(SPI(pa,pb,qa,qb))// 墙挡住，镜子没挡住 45     {46         if( (pa.x
           
            
             ja.x&&pb.x>jb.x) ) {cout<<"NO";return 0;}47 if( (pa.y
             
              
               ja.y&&pb.y>jb.y) ) {cout<<"NO";return 0;}48 if(SPI(pa,ja,qa,qb)||SPI(pb,jb,qa,qb)) {cout<<"NO";return 0;}49 }50 cout<<"YES";51 return 0;52 }
              
             
            
           
          
         
        
       
      

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 using namespace std;  7 const double eps=1e-8;  8 int sgn(double a)  9 { 10     if (fabs(a)
           
            0.0) return 1; 14 else return -1; 15 } 16 } 17 struct point 18 { 19 double x,y; 20 point(){} 21 point(double a,double b) 22 { 23 x=a;y=b; 24 } 25 void init() 26 { 27 scanf("%lf%lf",&x,&y); 28 } 29 point operator+(const point &a)const 30 { 31 point ans; 32 ans.x=x+a.x; 33 ans.y=y+a.y; 34 return ans; 35 } 36 point operator-(const point &a)const 37 { 38 point ans; 39 ans.x=x-a.x; 40 ans.y=y-a.y; 41 return ans; 42 } 43 point operator*(const double &a)const 44 { 45 point ans; 46 ans.x=x*a; 47 ans.y=y*a; 48 return ans; 49 } 50 void print() 51 { 52 printf("%lf %lf\n",x,y); 53 } 54 }v,p,w1,w2,m1,m2; 55 double cross(point a,point b) 56 { 57 return a.x*b.y-a.y*b.x; 58 } 59 double dot(point a,point b) 60 { 61 return a.x*b.x+a.y*b.y; 62 } 63 bool cross(point p1,point p2,point p3,point p4) 64 { 65 if (sgn(cross(p2-p1,p3-p1))*sgn(cross(p2-p1,p4-p1))==1) return false; 66 if (sgn(cross(p4-p3,p1-p3))*sgn(cross(p4-p3,p2-p3))==1) return false; 67 if (sgn(max(p1.x,p2.x)-min(p3.x,p4.x))==-1) return false; 68 if (sgn(max(p1.y,p2.y)-min(p3.y,p4.y))==-1) return false; 69 if (sgn(max(p3.x,p4.x)-min(p1.x,p2.x))==-1) return false; 70 if (sgn(max(p3.y,p4.y)-min(p1.y,p2.y))==-1) return false; 71 return true; 72 } 73 point getcross(point p1,point p2,point p3,point p4) 74 { 75 double a=p2.y-p1.y; 76 double b=p1.x-p2.x; 77 double c=-p1.x*p2.y+p1.y*p2.x; 78 double d=p4.y-p3.y; 79 double e=p3.x-p4.x; 80 double f=-p3.x*p4.y+p3.y*p4.x; 81 double x=(b*f-c*e)/(a*e-b*d); 82 double y=(a*f-c*d)/(b*d-a*e); 83 return point(x,y); 84 } 85 point calcfoot(point p1,point p2,point p3) 86 { 87 double ratio=dot(p1-p2,p3-p2)/dot(p3-p2,p3-p2); 88 return p2+(p3-p2)*ratio; 89 } 90 bool check() 91 { 92 if (!cross(v,p,w1,w2)) 93 { 94 if (!cross(v,p,m1,m2)) return true; 95 if (sgn(cross(m1-v,m2-v))==0 && sgn(cross(m1-p,m2-p)==0)) return true; 96 } 97 if (sgn(cross(m2-m1,v-m1))*sgn(cross(m2-m1,p-m1))==1) 98 { 99 point foot=calcfoot(p,m1,m2);100 foot=foot*2.0-p;101 if (cross(v,foot,m1,m2))102 {103 foot=getcross(v,foot,m1,m2);104 if (!cross(v,foot,w1,w2) && !cross(foot,p,w1,w2)) return true;105 }106 }107 return false;108 }109 int main()110 {111 v.init();112 p.init();113 w1.init();114 w2.init();115 m1.init();116 m2.init();117 if (check()) printf("YES\n");118 else printf("NO\n");119 return 0;120 }
           
          
         
        
       
      

 

T3 

https://www.luogu.org/problem/show?pid=T11835

T3。。大爆搜？

就这么一眼秒了？

看了看表还有两个小时，开始敲代码

但是越敲越不对，

主体是BFS，移动用DFS，string判重，考虑了三种情况，最后判断能否成立的时候再来个DFS。。。。

1个小时写完，感觉脑袋都要炸了

调了一个小时，没调出来，果断放弃。。。。。。。

 

 

 

 

总结：

这次试从成绩上来说应该是考的不错的，但是我自己还是很不满意，T3明明一眼秒掉了，思路对，算法也对，可惜就是没调出来（赛后调了一个小时调处来了。。。。），看来自己的代码能力还需要加强啊。。。。