T1
枚举右端点,前缀和优化。对于当前点x，答案为 sum[x][r]-sum[x][l-1]-(sum[z][r]-sum[z][l-1]) 整理为 sum[x][r]-sum[z][r]-(sum[x][l-1]-sum[z][l-1]) 我们已知x和sum[x][r],对于z我们枚举，对于sum[x][l-1]-sum[z][l-1]我们需要一个最小的 用minv[x][y]表示sum[x]-sum[y]的最小值。
#include <cstdio> #define N 1000500 char s[N]; int n,last[26],sum[26],pr[26][26],minv[26][26]; int max(int a,int b){return a>b?a:b;} int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); scanf("%d%s",&n,s+1); int ans=0; for(int j=1;j<=n;++j) { int p=s[j]-'a'; sum[p]++; last[p]=j; for(int i=0;i<=25;++i) { if(sum[i]&&i!=j) ans=max(ans,sum[i]-sum[p]-minv[i][p]-(last[i]==pr[i][p])), ans=max(ans,sum[p]-sum[i]-minv[p][i]-(last[i]==pr[p][i])); } for(int i=0;i<=25;++i) { if(sum[i]-sum[p]<minv[i][p]) minv[i][p]=sum[i]-sum[p],pr[i][p]=j; if(sum[p]-sum[i]<minv[p][i]) minv[p][i]=sum[p]-sum[i],pr[p][i]=j; } } printf("%d\n",ans); return 0; }
T2
计算几何
判断两条直线是否相交 如果两个人连线与墙相交的话 一定是NO 如果两个人分布在墙一侧 我们可以用对称找到一个点在墙另一边的对称点 这样就成了在墙的两侧 判断连线是否与墙相交 这个题它还是线段。 所以不能只找交点，还需要判断交点是否在线段上
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const double eps=1e-8; int sgn(double a) { if (fabs(a)<eps) return 0; else { if (a>0.0) return 1; else return -1; } } struct point { double x,y; point(){} point(double a,double b) { x=a;y=b; } void init() { scanf("%lf%lf",&x,&y); } point operator+(const point &a)const { point ans; ans.x=x+a.x; ans.y=y+a.y; return ans; } point operator-(const point &a)const { point ans; ans.x=x-a.x; ans.y=y-a.y; return ans; } point operator*(const double &a)const { point ans; ans.x=x*a; ans.y=y*a; return ans; } void print() { printf("%lf %lf\n",x,y); } }v,p,w1,w2,m1,m2; double cross(point a,point b) { return a.x*b.y-a.y*b.x; } double dot(point a,point b) { return a.x*b.x+a.y*b.y; } bool cross(point p1,point p2,point p3,point p4) { if (sgn(cross(p2-p1,p3-p1))*sgn(cross(p2-p1,p4-p1))==1) return false; if (sgn(cross(p4-p3,p1-p3))*sgn(cross(p4-p3,p2-p3))==1) return false; if (sgn(max(p1.x,p2.x)-min(p3.x,p4.x))==-1) return false; if (sgn(max(p1.y,p2.y)-min(p3.y,p4.y))==-1) return false; if (sgn(max(p3.x,p4.x)-min(p1.x,p2.x))==-1) return false; if (sgn(max(p3.y,p4.y)-min(p1.y,p2.y))==-1) return false; return true; } point getcross(point p1,point p2,point p3,point p4) { double a=p2.y-p1.y; double b=p1.x-p2.x; double c=-p1.x*p2.y+p1.y*p2.x; double d=p4.y-p3.y; double e=p3.x-p4.x; double f=-p3.x*p4.y+p3.y*p4.x; double x=(b*f-c*e)/(a*e-b*d); double y=(a*f-c*d)/(b*d-a*e); return point(x,y); } point calcfoot(point p1,point p2,point p3) { double ratio=dot(p1-p2,p3-p2)/dot(p3-p2,p3-p2); return p2+(p3-p2)*ratio; } bool check() { if (!cross(v,p,w1,w2)) { if (!cross(v,p,m1,m2)) return true; if (sgn(cross(m1-v,m2-v))==0 && sgn(cross(m1-p,m2-p)==0)) return true; } if (sgn(cross(m2-m1,v-m1))*sgn(cross(m2-m1,p-m1))==1) { point foot=calcfoot(p,m1,m2); foot=foot*2.0-p; if (cross(v,foot,m1,m2)) { foot=getcross(v,foot,m1,m2); if (!cross(v,foot,w1,w2) && !cross(foot,p,w1,w2)) return true; } } return false; } int main() { freopen("b.in","r",stdin); freopen("b.out","w",stdout); v.init(); p.init(); w1.init(); w2.init(); m1.init(); m2.init(); if (check()) printf("YES\n"); else printf("NO\n"); return 0; }
T3
怀疑人生的BFS
#include<cstdio> #include<cstdlib> #include<cstring> #include<queue> using namespace std; #define get(a,b,c) ((a-1)*12+(b-1)*4+c) int en,tmp[4][4],color[37],map[9][5],q[37],nowmap[4][4],newmap[4][4]; bool num[9],use[90000000],right[37],row[4],col[4],col_find[5]; char s[10]; struct rec { int sta,step; rec(){} rec(int a,int b) { sta=a;step=b; } }; queue<rec> que; struct edge { int e; edge *next; }*v[37],ed[100]; void add_edge(int s,int e) { en++; ed[en].next=v[s];v[s]=ed+en;v[s]->e=e; en++; ed[en].next=v[e];v[e]=ed+en;v[e]->e=s; } bool check(int nows) { memset(num,false,sizeof(num)); for (int a=3;a>=1;a--) for (int b=3;b>=1;b--) if (a!=3 || b!=3) { tmp[a][b]=nows%10; num[nows%10]=true; nows/=10; } for (int a=0;a<9;a++) if (!num[a]) { tmp[3][3]=a; break; } int cnt=0; for (int a=1;a<=3;a++) for (int b=1;b<=3;b++) for (int c=1;c<=4;c++) { cnt++; color[cnt]=map[tmp[a][b]][c]; } memset(right,false,sizeof(right)); memset(col_find,false,sizeof(col_find)); for (int a=1;a<=36;a++) if (!right[a]) { if (col_find[color[a]]) return false; col_find[color[a]]=true; int front=1,tail=1; q[1]=a; right[a]=true; for (;front<=tail;) { int now=q[front++]; for (edge *e=v[now];e;e=e->next) if (color[e->e]==color[now] && !right[e->e]) { right[e->e]=true; q[++tail]=e->e; } } } return true; } int main() { freopen("c.in","r",stdin); freopen("c.out","w",stdout); for (int a=1;a<=3;a++) for (int b=1;b<=3;b++) { add_edge(get(a,b,1),get(a,b,3)); add_edge(get(a,b,1),get(a,b,4)); add_edge(get(a,b,2),get(a,b,3)); add_edge(get(a,b,2),get(a,b,4)); if (a!=3) add_edge(get(a,b,2),get(a+1,b,1)); if (b!=3) add_edge(get(a,b,4),get(a,b+1,3)); } int cnt=0; for (int a=1;a<=3;a++) for (int b=1;b<=3;b++) { scanf("%s",s+1); for (int c=1;c<=4;c++) if (s[c]=='R') map[cnt][c]=0; else { if (s[c]=='G') map[cnt][c]=1; else { if (s[c]=='B') map[cnt][c]=2; else map[cnt][c]=3; } } if (s[5]=='1') row[a]=col[b]=true; cnt++; } int nows=1234567; if (check(nows)) { printf("0\n"); return 0; } que.push(rec(nows,0)); use[nows]=true; rec now; while (que.size()) { now=que.front(); que.pop(); int step=now.step; int nows=now.sta; memset(num,false,sizeof(num)); for (int a=3;a>=1;a--) for (int b=3;b>=1;b--) if (a!=3 || b!=3) { nowmap[a][b]=nows%10; num[nows%10]=true; nows/=10; } for (int a=0;a<9;a++) if (!num[a]) { nowmap[3][3]=a; break; } int news=0; for (int a=1;a<=3;a++) { if (!row[a]) { for (int b=1;b<=3;b++) for (int c=1;c<=3;c++) newmap[b][c]=nowmap[b][c]; int x=newmap[a][1]; newmap[a][1]=newmap[a][2];newmap[a][2]=newmap[a][3];newmap[a][3]=x; news=0; for (int b=1;b<=3;b++) for (int c=1;c<=3;c++) if (b!=3 || c!=3) news=news*10+newmap[b][c]; if (!use[news]) { use[news]=true; if (check(news)) { printf("%d\n",step+1); return 0; } que.push(rec(news,step+1)); } x=newmap[a][1]; newmap[a][1]=newmap[a][2];newmap[a][2]=newmap[a][3];newmap[a][3]=x; news=0; for (int b=1;b<=3;b++) for (int c=1;c<=3;c++) if (b!=3 || c!=3) news=news*10+newmap[b][c]; if (!use[news]) { use[news]=true; if (check(news)) { printf("%d\n",step+1); return 0; } que.push(rec(news,step+1)); } } if (!col[a]) { for (int b=1;b<=3;b++) for (int c=1;c<=3;c++) newmap[b][c]=nowmap[b][c]; int x=newmap[1][a]; newmap[1][a]=newmap[2][a];newmap[2][a]=newmap[3][a];newmap[3][a]=x; news=0; for (int b=1;b<=3;b++) for (int c=1;c<=3;c++) if (b!=3 || c!=3) news=news*10+newmap[b][c]; if (!use[news]) { use[news]=true; if (check(news)) { printf("%d\n",step+1); return 0; } que.push(rec(news,step+1)); } x=newmap[1][a]; newmap[1][a]=newmap[2][a];newmap[2][a]=newmap[3][a];newmap[3][a]=x; news=0; for (int b=1;b<=3;b++) for (int c=1;c<=3;c++) if (b!=3 || c!=3) news=news*10+newmap[b][c]; if (!use[news]) { use[news]=true; if (check(news)) { printf("%d\n",step+1); return 0; } que.push(rec(news,step+1)); } } } } return 0; }