2017.10.1解题报告


预计分数: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<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 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<a.length();i++)
27     {
28         memset(happen,0,sizeof(happen));
29         for(int j=i;j<a.length();j++)
30         {
31             int nowmax=0,nowmin=0x7fff;
32             happen[a[j]]++;
33             for(register int k=97;k<=122;k++)
34             {
35                 if(happen[k]>nowmax)    nowmax=happen[k];
36                 if(happen[k]<nowmin&&happen[k])    nowmin=happen[k];
37             }
38             if(nowmax-nowmin>ans)    ans=nowmax-nowmin;
39         }
40     }
41     printf("%d",ans);
42     return 0;
43 }
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 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<a.length();i++)
27     {
28         memset(happen,0,sizeof(happen));
29         for(register int j=i;j<a.length();j++)
30         {
31             int nowmax=0,nowmin=0x7fff;
32             happen[a[j]]++;
33             for(register int k=97;k<=122;k++)
34             {
35                 if(happen[k]>nowmax)    nowmax=happen[k];
36                 if(happen[k]<nowmin&&happen[k])    nowmin=happen[k];
37             }
38             if(nowmax-nowmin>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<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<iostream>
 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)<eps)?0:(x<0?-1:1);}
16 struct Point
17 {
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&&pa.x<jb.x) && (pb.x>ja.x&&pb.x>jb.x) )    {cout<<"NO";return 0;}
47         if( (pa.y<ja.y&&pa.y<jb.y) && (pb.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<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<algorithm>
  6 using namespace std;
  7 const double eps=1e-8;
  8 int sgn(double a)
  9 {
 10     if (fabs(a)<eps) return 0;
 11     else
 12     {
 13         if (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明明一眼秒掉了,思路对,算法也对,可惜就是没调出来(赛后调了一个小时调处来了。。。。),看来自己的代码能力还需要加强啊。。。。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏HTML5学堂

揭开身份证验证的神秘面纱

正则验证身份证号码 HTML5学堂:曾经一直觉得用正则验证身份证号码是很简单的~但是,当真正挖掘身份证号码的规则之后,才发现,想要写好一个正则验证也没有那么容易...

4345
来自专栏HansBug's Lab

1934: [Shoi2007]Vote 善意的投票

1934: [Shoi2007]Vote 善意的投票 Time Limit: 1 Sec  Memory Limit: 64 MB Submit: 1174  ...

2847
来自专栏数据结构与算法

BZOJ2152: 聪聪可可(点分治)

聪聪和可可是兄弟俩,他们俩经常为了一些琐事打起来,例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑(可是他们家只有一台电脑)……遇到这种问题,一般情况...

963
来自专栏ml

HDUOJ---2110

Crisis of HDU Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/3276...

2517
来自专栏章鱼的慢慢技术路

今日头条2018校园春季招聘研发岗位笔试(第一场)经验

1183
来自专栏潇涧技术专栏

Python Algorithms - C1 Introduction

算法导论是一本经典的大而全的算法书籍,而本书Python Algorithms不是来取代而是来补充算法导论的,因为算法导论提供的是简易的伪代码和详细的证明,而本...

822
来自专栏ACM算法日常

照明系统设计(动态规划)- UVA 11400

You are given the task to design a lighting system for a huge conference hall. A...

891
来自专栏区块链大本营

漏洞连载|浮点与精度处理不当的那些事儿

“言治骨角者,既切之而复磋之;治玉石者,既琢之而复磨之,治之已精,而益求其精也。”——宋·朱熹

1251
来自专栏技术博客

设计模式之前奏(UML类图)

本人菜菜一个,最近一直在博客园游走闲逛,看到了各种技术,各种各种……。便看到了大话设计模式这本书,下了电子版的看了看第一章,感觉相当不错,不仅通俗易懂,而且与实...

2183
来自专栏aCloudDeveloper

string 之 strlen函数

Author: bakari  Date: 2012/8/9 近两年好多的IT公司喜欢拿一些库函数来考,string函数库当然是首选,除此之外,像qsort,S...

1957

扫码关注云+社区

领取腾讯云代金券