期望得分：60+ +0=60+
实际得分：30+56+0=86
时间规划极端不合理，T2忘了叉积计算，用解析几何算，还有的情况很难处理，浪费太多时间，最后gg
导致T3只剩50分钟，20分钟写完代码，没调出来
设sum[i][j] 表示字母j出现次数的前缀和
那么题目要求我们 最大化sum[r][x]-sum[l-1][x]-(sum[r][y]-sum[l-1][y])
如果枚举r，再枚举y，时间复杂度为O（n*26），是可以承受的
但此时还有l-1未知，能否O（1）找到l-1呢？
我们发现式子可以化为 ：sum[r][x]-sum[r][y]-(sum[l-1][x]-sum[l-1][y]）
这样减号两边形式相同
那就可以用前缀和来维护
所以设mi[i][j] 表示 当前 sum[i]-sum[j] 的最小值
在枚举r之前，l肯定已经计算过，所以sum的第一维可以不再mi中体现
那么ans=max（sum[r][x]-sum[r][y]-mi[x][y]，sum[r][y]-sum[l][x]-mi[y][x]）
小细节：
zhx的std中，
另外记录了当前每个字符的上一个出现的位置last[i]，更新mi[i][j]的位置pos[i][j]
在更新答案的时候，是sum[r][x]-sum[r][y]-mi[x][y]-(pos[x][y]==last[i])
原因是因为 题目中要求 用来计算答案的 字母必须在所选区间出现过
std 每次在用sum更新mi时，不能保证用的这个字符出现过
还不明白的话 ，把std 的那句判等去掉，跑一遍数据：hhfffff
所以 我们仅需要在更新mi的时候，判断sum[]是否为真
便可以把这个特殊判断和last，pos 数组 去掉
#include<cstdio> #include<cstring> #include<algorithm>using namespace std;#define N 1000001int sum[N],mi[26][26]; char s[N];int main() {freopen("a.in","r",stdin);freopen("a.out","w",stdout);int n;scanf("%d",&n); scanf("%s",s+1);int ans=0;memset(mi,63,sizeof(63));for(int i=1;i<=n;i++){int now=s[i]-'a';sum[now]++;for(int j=0;j<26;j++) if(sum[j]) ans=max(ans,max(sum[now]-sum[j]-mi[now][j],sum[j]-sum[now]-mi[j][now]));for(int j=0;j<26;j++) {if(sum[j] && sum[j]-sum[now]<mi[j][now]) mi[j][now]=sum[j]-sum[now];if(sum[j] && sum[now]-sum[j]<mi[now][j]) mi[now][j]=sum[now]-sum[j];}}printf("%d",ans); }
gg了。。。。。。
反射那块是怎么求的？
最后的交点怎么求的？
#include<cmath> #include<cstdio> #include<iostream> #include<algorithm>using namespace std;const double eps=1e-8;struct Point {double x,y;Point() { };Point(double a,double b) { x=a; y=b; }void init() { scanf("%lf%lf",&x,&y); } }v,p,w1,w2,m1,m2;Point operator + (Point A,Point B) { return Point(A.x+B.x,A.y+B.y); } Point operator - (Point A,Point B) { return Point(A.x-B.x,A.y-B.y); } Point operator * (Point A,double a) { return Point(A.x*a,A.y*a); }int dcmp(double a) { if(fabs(a)<eps) return 0; return a>0 ? 1 : -1; }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(dcmp(Cross(P2-P1,P3-P1))*dcmp(Cross(P2-P1,P4-P1))==1) return false;if(dcmp(Cross(P4-P3,P1-P3))*dcmp(Cross(P4-P3,P2-P3))==1) return false;if(dcmp(fmax(P1.x,P2.x)-fmin(P3.x,P4.x))==-1) return false;if(dcmp(fmax(P1.y,P2.y)-fmin(P3.y,P4.y))==-1) return false;if(dcmp(fmax(P3.x,P4.x)-fmin(P1.x,P2.x))==-1) return false;if(dcmp(fmax(P3.y,P4.y)-fmin(P1.y,P2.y))==-1) return false;return true; }Point GetLineProjection(Point P,Point A,Point B) {Point v=B-A;return A+v*(Dot(v,P-A)/Dot(v,v)); }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); }bool check() {if(!cross(v,p,w1,w2)){if(!cross(v,p,m1,m2)) return true;if(dcmp(Cross(m1-v,m2-v))==0 && dcmp(Cross(m1-p,m2-p))==0) return true;}if(dcmp(Cross(m2-m1,v-m1))*dcmp(Cross(m2-m1,p-m1))==1) {Point foot=GetLineProjection(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(p,foot,w1,w2)) return true;}return false;}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()) puts("YES");else printf("NO");return 0; }
bfs，结构体内char数组3*3*6表示状态，map判重
#include<map> #include<queue> #include<cstring> #include<cstdio> #include<iostream>using namespace std;struct node {char s[3][3][6]; }cur,nxt;queue<node>q; map<string,int>mp;string t;int sum[4],cnt;bool v[3][3][4];bool vis() {t.clear();for(int i=0;i<3;i++)for(int j=0;j<3;j++) t+=nxt.s[i][j];return mp.count(t); }void dfs(int i,int j,int k,char c) {cnt++;v[i][j][k]=true;if(!k){if(nxt.s[i][j][2]==c && !v[i][j][2]) dfs(i,j,2,c);if(nxt.s[i][j][3]==c && !v[i][j][3]) dfs(i,j,3,c);if(i && nxt.s[i-1][j][1]==c && !v[i-1][j][1]) dfs(i-1,j,1,c);}else if(k==1){if(nxt.s[i][j][2]==c && !v[i][j][2]) dfs(i,j,2,c);if(nxt.s[i][j][3]==c && !v[i][j][3]) dfs(i,j,3,c);if(i!=2 && nxt.s[i+1][j][0]==c && !v[i+1][j][0]) dfs(i+1,j,0,c);}else if(k==2){if(nxt.s[i][j][0]==c && !v[i][j][0]) dfs(i,j,0,c);if(nxt.s[i][j][1]==c && !v[i][j][1]) dfs(i,j,1,c);if(j!=0 && nxt.s[i][j-1][3]==c && !v[i][j-1][3]) dfs(i,j-1,3,c);}else {if(nxt.s[i][j][0]==c && !v[i][j][0]) dfs(i,j,0,c);if(nxt.s[i][j][1]==c && !v[i][j][1]) dfs(i,j,1,c);if(j!=2 && nxt.s[i][j+1][2]==c && !v[i][j+1][2]) dfs(i,j+1,2,c);} } bool judge() {memset(v,false,sizeof(v)); bool ok=false;for(int i=0;i<3 && !ok;i++)for(int j=0;j<3 && !ok;j++)for(int k=0;k<4 && !ok;k++)if(nxt.s[i][j][k]=='R') {cnt=0;dfs(i,j,k,'R');if(cnt!=sum[0]) return false;ok=true;}ok=false;for(int i=0;i<3 && !ok;i++)for(int j=0;j<3 && !ok;j++)for(int k=0;k<4 && !ok;k++)if(nxt.s[i][j][k]=='G') {cnt=0;dfs(i,j,k,'G');if(cnt!=sum[1]) return false;ok=true;}ok=false;for(int i=0;i<3 && !ok;i++)for(int j=0;j<3 && !ok;j++)for(int k=0;k<4 && !ok;k++)if(nxt.s[i][j][k]=='B') {cnt=0;dfs(i,j,k,'B');if(cnt!=sum[2]) return false;ok=true;}ok=false;for(int i=0;i<3 && !ok;i++)for(int j=0;j<3 && !ok;j++)for(int k=0;k<4 && !ok;k++)if(nxt.s[i][j][k]=='O') {cnt=0;dfs(i,j,k,'O');if(cnt!=sum[3]) return false;ok=true;}return true; }int main() {freopen("c.in","r",stdin);freopen("c.out","w",stdout);for(int i=0;i<3;i++)for(int j=0;j<3;j++){scanf("%s",cur.s[i][j]);for(int k=0;k<5;k++) t+=cur.s[i][j][k];for(int k=0;k<4;k++)switch(cur.s[i][j][k]){case 'R':sum[0]++; break;case 'G':sum[1]++; break;case 'B':sum[2]++; break;case 'O':sum[3]++; break;}}q.push(cur);mp[t]=1;bool ok;string a,b;while(!q.empty()){cur=q.front(); q.pop();a.clear();for(int i=0;i<3;i++)for(int j=0;j<3;j++)a+=cur.s[i][j];// leftfor(int i=0;i<3;i++){ok=true;for(int j=0;j<3 && ok;j++) if(cur.s[i][j][4]=='1') ok=false;if(!ok) continue;nxt=cur;swap(nxt.s[i][0],nxt.s[i][1]);swap(nxt.s[i][1],nxt.s[i][2]);if(vis()) continue;if(judge()) { printf("%d",mp[a]); return 0; }b.clear();for(int i=0;i<3;i++)for(int j=0;j<3;j++)b+=nxt.s[i][j];mp[b]=mp[a]+1;q.push(nxt);}// rightfor(int i=0;i<3;i++){ok=true;for(int j=0;j<3 && ok;j++) if(cur.s[i][j][4]=='1') ok=false;if(!ok) continue;nxt=cur;swap(nxt.s[i][2],nxt.s[i][1]);swap(nxt.s[i][1],nxt.s[i][0]);if(vis()) continue;if(judge()) { printf("%d",mp[a]); return 0; }b.clear();for(int i=0;i<3;i++)for(int j=0;j<3;j++)b+=nxt.s[i][j];mp[b]=mp[a]+1;q.push(nxt);}// upfor(int j=0;j<3;j++){ok=true;for(int i=0;i<3 && ok;i++) if(cur.s[i][j][4]=='1') ok=false;if(!ok) continue;nxt=cur;swap(nxt.s[0][j],nxt.s[1][j]);swap(nxt.s[1][j],nxt.s[2][j]);if(vis()) continue;if(judge()) { printf("%d",mp[a]); return 0; }b.clear();for(int i=0;i<3;i++)for(int j=0;j<3;j++)b+=nxt.s[i][j];mp[b]=mp[a]+1;q.push(nxt);} // downfor(int j=0;j<3;j++){ok=true;for(int i=0;i<3 && ok;i++) if(cur.s[i][j][4]=='1') ok=false;if(!ok) continue;nxt=cur;swap(nxt.s[2][j],nxt.s[1][j]);swap(nxt.s[1][j],nxt.s[0][j]);if(vis()) continue;if(judge()) { printf("%d",mp[a]); return 0; }b.clear();for(int i=0;i<3;i++)for(int j=0;j<3;j++)b+=nxt.s[i][j];mp[b]=mp[a]+1;q.push(nxt);}} }