预计分数:60+50+0=110 实际分数:60+81+0=144 全场rank13?全校rank1?貌似题很难啊23333
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 }
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 }
https://www.luogu.org/problem/show?pid=T11835
T3。。大爆搜?
就这么一眼秒了?
看了看表还有两个小时,开始敲代码
但是越敲越不对,
主体是BFS,移动用DFS,string判重,考虑了三种情况,最后判断能否成立的时候再来个DFS。。。。
1个小时写完,感觉脑袋都要炸了
调了一个小时,没调出来,果断放弃。。。。。。。
总结:
这次试从成绩上来说应该是考的不错的,但是我自己还是很不满意,T3明明一眼秒掉了,思路对,算法也对,可惜就是没调出来(赛后调了一个小时调处来了。。。。),看来自己的代码能力还需要加强啊。。。。