北京集训DAY1

 1 /*
 2     枚举右端点,前缀和优化。对于当前点x，答案为
 3     sum[x][r]-sum[x][l-1]-(sum[z][r]-sum[z][l-1])        
 4     整理为
 5     sum[x][r]-sum[z][r]-(sum[x][l-1]-sum[z][l-1])
 6     我们已知x和sum[x][r],对于z我们枚举，对于sum[x][l-1]-sum[z][l-1]我们需要一个最小的
 7     用minv[x][y]表示sum[x]-sum[y]的最小值。
 8 */
 9 #include<cstdio>
10 #include<cstdlib>
11 #include<cstring>
12 #include<vector>
13 
14 using namespace std;
15 
16 const int maxn=1000010;
17 
18 int n,ans,p[26][26],minv[26][26],sum[26],last[26];
19 
20 char s[maxn];
21 
22 int hh() {
23     freopen("a.in","r",stdin);
24     freopen("a.out","w",stdout);
25     scanf("%d",&n);
26     scanf("%s",s+1);
27     for (int a=1;a<=n;a++) {
28         int c=s[a]-'a';
29         sum[c]++;
30         last[c]=a;
31         for(int b=0;b<26;b++)
32             if(b!=a&&sum[b]) ans=max(ans,max(sum[c]-sum[b]-minv[c][b]-(last[b]==p[c][b]),sum[b]-sum[c]-minv[b][c]-(last[b]==p[b][c])));
33         for(int b=0;b<26;b++) {
34             if(sum[c]-sum[b]<minv[c][b]) minv[c][b]=sum[c]-sum[b],p[c][b]=a;
35             if(sum[b]-sum[c]<minv[b][c]) minv[b][c]=sum[b]-sum[c],p[b][c]=a;
36         }
37     }
38     printf("%d
",ans);
39 
40     return 0;
41 }
42 
43 int sb=hh();
44 int main(int argc,char**argv) {;}

题解

  1 /*
  2     一道计算几何吧。
  3     这完全是考直线与方程式啊！！！ 虽然我并不会写
  4     于是输出No 拿了54分
  5      
  6     主要是判断两条直线是否相交 
  7     如果两个人连线与墙相交的话 一定是NO
  8     如果两个人分布在墙一侧 我们可以用对称找到一个点在墙另一边的对称点
  9     这样就成了在墙的两侧 判断连线是否与墙相交 
 10     
 11     这个题它还是线段。
 12     所以不能只找交点，还需要判断交点是否在线段上 
 13 */
 14 #include<cstdio>
 15 #include<cstdlib>
 16 #include<cstring>
 17 #include<cmath>
 18 #include<algorithm>
 19 
 20 using namespace std;
 21 
 22 const double eps=1e-8;
 23 
 24 int sgn(double a) {
 25     if (fabs(a)<eps) return 0;
 26     else {
 27         if (a>0.0) return 1;
 28         else return -1;
 29     }
 30 }
 31 
 32 struct point {
 33     double x,y;
 34     point(){}
 35     point(double a,double b) {
 36         x=a;y=b;
 37     }
 38     void init() {
 39         scanf("%lf%lf",&x,&y);
 40     }
 41     point operator+(const point &a)const {
 42         point ans;
 43         ans.x=x+a.x;
 44         ans.y=y+a.y;
 45         return ans;
 46     }
 47     point operator-(const point &a)const {
 48         point ans;
 49         ans.x=x-a.x;
 50         ans.y=y-a.y;
 51         return ans;
 52     }
 53     point operator*(const double &a)const {
 54         point ans;
 55         ans.x=x*a;
 56         ans.y=y*a;
 57         return ans;
 58     }
 59     void print() {
 60         printf("%lf %lf
",x,y);
 61     }
 62 }v,p,w1,w2,m1,m2;
 63 
 64 double cross(point a,point b) {
 65     return a.x*b.y-a.y*b.x;
 66 }
 67 
 68 double dot(point a,point b) {
 69     return a.x*b.x+a.y*b.y;
 70 }
 71 
 72 bool cross(point p1,point p2,point p3,point p4) {
 73     if (sgn(cross(p2-p1,p3-p1))*sgn(cross(p2-p1,p4-p1))==1) return false;
 74     if (sgn(cross(p4-p3,p1-p3))*sgn(cross(p4-p3,p2-p3))==1) return false;
 75     if (sgn(max(p1.x,p2.x)-min(p3.x,p4.x))==-1) return false;
 76     if (sgn(max(p1.y,p2.y)-min(p3.y,p4.y))==-1) return false;
 77     if (sgn(max(p3.x,p4.x)-min(p1.x,p2.x))==-1) return false;
 78     if (sgn(max(p3.y,p4.y)-min(p1.y,p2.y))==-1) return false;
 79     return true;
 80 }
 81 
 82 point getcross(point p1,point p2,point p3,point p4) {
 83     double a=p2.y-p1.y;
 84     double b=p1.x-p2.x;
 85     double c=-p1.x*p2.y+p1.y*p2.x;
 86     double d=p4.y-p3.y;
 87     double e=p3.x-p4.x;
 88     double f=-p3.x*p4.y+p3.y*p4.x;
 89     double x=(b*f-c*e)/(a*e-b*d);
 90     double y=(a*f-c*d)/(b*d-a*e);
 91     return point(x,y);
 92 }
 93 
 94 point calcfoot(point p1,point p2,point p3) {
 95     double ratio=dot(p1-p2,p3-p2)/dot(p3-p2,p3-p2);
 96     return p2+(p3-p2)*ratio;
 97 }
 98 
 99 bool check() {
100     if (!cross(v,p,w1,w2)) {
101         if (!cross(v,p,m1,m2)) return true;
102         if (sgn(cross(m1-v,m2-v))==0 && sgn(cross(m1-p,m2-p)==0)) return true;      
103     }
104     if (sgn(cross(m2-m1,v-m1))*sgn(cross(m2-m1,p-m1))==1) {
105         point foot=calcfoot(p,m1,m2);
106         foot=foot*2.0-p;
107         if (cross(v,foot,m1,m2)) {
108             foot=getcross(v,foot,m1,m2);
109             if (!cross(v,foot,w1,w2) && !cross(foot,p,w1,w2)) return true;
110         }
111     }
112     return false;
113 }
114 
115 int main() {
116     freopen("b.in","r",stdin);
117     freopen("b.out","w",stdout);
118     v.init();
119     p.init();
120     w1.init();
121     w2.init();
122     m1.init();
123     m2.init();
124     if (check()) printf("YES
");
125     else printf("NO
");
126     return 0;
127 }

题解

  1 /*
  2     一道腾讯马拉松的题目 这题还真是蛋疼
  3     题目 真是没什么好说的 一道很裸的BFS搜索题 
  4     但是这个状态真是很麻烦 
  5     判重麻烦 搜索麻烦  这题就是麻烦 
  6      
  7 */
  8 #include<cstdio>
  9 #include<cstdlib>
 10 #include<cstring>
 11 #include<queue>
 12 
 13 using namespace std;
 14 
 15 #define get(a,b,c) ((a-1)*12+(b-1)*4+c)
 16 
 17 int en,tmp[4][4],color[37],map[9][5],q[37],nowmap[4][4],newmap[4][4];
 18 
 19 bool num[9],use[90000000],right[37],row[4],col[4],col_find[5];
 20 
 21 char s[10];
 22 
 23 struct rec
 24 {
 25     int sta,step;
 26     rec(){}
 27     rec(int a,int b)
 28     {
 29         sta=a;step=b;
 30     }
 31 };
 32 
 33 queue<rec> que;
 34 
 35 struct edge
 36 {
 37     int e;
 38     edge *next;
 39 }*v[37],ed[100];
 40 
 41 void add_edge(int s,int e)
 42 {
 43     en++;
 44     ed[en].next=v[s];v[s]=ed+en;v[s]->e=e;
 45     en++;
 46     ed[en].next=v[e];v[e]=ed+en;v[e]->e=s;
 47 }
 48 
 49 bool check(int nows)
 50 {
 51     memset(num,false,sizeof(num));
 52     for (int a=3;a>=1;a--)
 53         for (int b=3;b>=1;b--)
 54             if (a!=3 || b!=3)
 55             {
 56                 tmp[a][b]=nows%10;
 57                 num[nows%10]=true;
 58                 nows/=10;
 59             }
 60     for (int a=0;a<9;a++)
 61         if (!num[a])
 62         {
 63             tmp[3][3]=a;
 64             break;
 65         }
 66     int cnt=0;
 67     for (int a=1;a<=3;a++)
 68         for (int b=1;b<=3;b++)
 69             for (int c=1;c<=4;c++)
 70             {
 71                 cnt++;
 72                 color[cnt]=map[tmp[a][b]][c];
 73             }
 74     memset(right,false,sizeof(right));
 75     memset(col_find,false,sizeof(col_find));
 76     for (int a=1;a<=36;a++)
 77         if (!right[a])
 78         {
 79             if (col_find[color[a]]) return false;
 80             col_find[color[a]]=true;
 81             int front=1,tail=1;
 82             q[1]=a;
 83             right[a]=true;
 84             for (;front<=tail;)
 85             {
 86                 int now=q[front++];
 87                 for (edge *e=v[now];e;e=e->next)
 88                     if (color[e->e]==color[now] && !right[e->e])
 89                     {
 90                         right[e->e]=true;
 91                         q[++tail]=e->e;
 92                     }
 93             }
 94         }
 95     return true;
 96 }
 97 
 98 int main()
 99 {
100     freopen("c.in","r",stdin);
101     freopen("c.out","w",stdout);
102 
103     for (int a=1;a<=3;a++)
104         for (int b=1;b<=3;b++)
105         {
106             add_edge(get(a,b,1),get(a,b,3));
107             add_edge(get(a,b,1),get(a,b,4));
108             add_edge(get(a,b,2),get(a,b,3));
109             add_edge(get(a,b,2),get(a,b,4));
110             if (a!=3) add_edge(get(a,b,2),get(a+1,b,1));
111             if (b!=3) add_edge(get(a,b,4),get(a,b+1,3));
112         }
113     int cnt=0;
114     for (int a=1;a<=3;a++)
115         for (int b=1;b<=3;b++)
116         {
117             scanf("%s",s+1);
118             for (int c=1;c<=4;c++)
119                 if (s[c]=='R') map[cnt][c]=0;
120                 else 
121                 {
122                     if (s[c]=='G') map[cnt][c]=1;
123                     else
124                     {
125                         if (s[c]=='B') map[cnt][c]=2;
126                         else map[cnt][c]=3;
127                     }
128                 }
129             if (s[5]=='1') row[a]=col[b]=true;
130             cnt++;
131         }
132     int nows=1234567;
133     if (check(nows))
134     {
135         printf("0
");
136         return 0;
137     }
138     que.push(rec(nows,0));
139     use[nows]=true;
140     rec now;
141     while (que.size())
142     {
143         now=que.front();
144         que.pop();
145         int step=now.step;
146         int nows=now.sta;
147         memset(num,false,sizeof(num));
148         for (int a=3;a>=1;a--)
149             for (int b=3;b>=1;b--)
150                 if (a!=3 || b!=3)
151                 {
152                     nowmap[a][b]=nows%10;
153                     num[nows%10]=true;
154                     nows/=10;
155                 }
156         for (int a=0;a<9;a++)
157             if (!num[a])
158             {
159                 nowmap[3][3]=a;
160                 break;
161             }
162         int news=0;
163         for (int a=1;a<=3;a++)
164         {
165             if (!row[a])
166             {
167                 for (int b=1;b<=3;b++)
168                     for (int c=1;c<=3;c++)
169                         newmap[b][c]=nowmap[b][c];
170                 int x=newmap[a][1];
171                 newmap[a][1]=newmap[a][2];newmap[a][2]=newmap[a][3];newmap[a][3]=x;
172                 news=0;
173                 for (int b=1;b<=3;b++)
174                     for (int c=1;c<=3;c++)
175                         if (b!=3 || c!=3) news=news*10+newmap[b][c];
176                 if (!use[news])
177                 {
178                     use[news]=true;
179                     if (check(news))
180                     {
181                         printf("%d
",step+1);
182                         return 0;
183                     }
184                     que.push(rec(news,step+1));
185                 }
186                 x=newmap[a][1];
187                 newmap[a][1]=newmap[a][2];newmap[a][2]=newmap[a][3];newmap[a][3]=x;
188                 news=0;
189                 for (int b=1;b<=3;b++)
190                     for (int c=1;c<=3;c++)
191                         if (b!=3 || c!=3) news=news*10+newmap[b][c];
192                 if (!use[news])
193                 {
194                     use[news]=true;
195                     if (check(news))
196                     {
197                         printf("%d
",step+1);
198                         return 0;
199                     }
200                     que.push(rec(news,step+1));
201                 }
202             }
203             if (!col[a])
204             {
205                 for (int b=1;b<=3;b++)
206                     for (int c=1;c<=3;c++)
207                         newmap[b][c]=nowmap[b][c];
208                 int x=newmap[1][a];
209                 newmap[1][a]=newmap[2][a];newmap[2][a]=newmap[3][a];newmap[3][a]=x;
210                 news=0;
211                 for (int b=1;b<=3;b++)
212                     for (int c=1;c<=3;c++)
213                         if (b!=3 || c!=3) news=news*10+newmap[b][c];
214                 if (!use[news])
215                 {
216                     use[news]=true;
217                     if (check(news))
218                     {
219                         printf("%d
",step+1);
220                         return 0;
221                     }
222                     que.push(rec(news,step+1));
223                 }
224                 x=newmap[1][a];
225                 newmap[1][a]=newmap[2][a];newmap[2][a]=newmap[3][a];newmap[3][a]=x;
226                 news=0;
227                 for (int b=1;b<=3;b++)
228                     for (int c=1;c<=3;c++)
229                         if (b!=3 || c!=3) news=news*10+newmap[b][c];
230                 if (!use[news])
231                 {
232                     use[news]=true;
233                     if (check(news))
234                     {
235                         printf("%d
",step+1);
236                         return 0;
237                     }
238                     que.push(rec(news,step+1));
239                 }
240             }
241         }
242     }
243 
244     return 0;
245 }

题解