2017.10.1 QBXT 模拟赛

时间:2022-12-16 23:12:57

  题目链接

   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]的最小值。
2017.10.1 QBXT 模拟赛2017.10.1 QBXT 模拟赛
#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;
}
View Code

 

    T2

  计算几何
判断两条直线是否相交 如果两个人连线与墙相交的话 一定是NO 如果两个人分布在墙一侧 我们可以用对称找到一个点在墙另一边的对称点 这样就成了在墙的两侧 判断连线是否与墙相交 这个题它还是线段。 所以不能只找交点,还需要判断交点是否在线段上
2017.10.1 QBXT 模拟赛2017.10.1 QBXT 模拟赛
#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;
}
View Code

 

    T3

  怀疑人生的BFS
2017.10.1 QBXT 模拟赛2017.10.1 QBXT 模拟赛
#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;
}
View Code