2018.10.13队测总结

T3 克卜勒(kepler)<好题(毒瘤题)置顶>

解题思路：

用两个树状数组维护，第一个树状数组按编号插入，维护小圈内各点是否通达（小圈内路径上的点编号相邻，如区间查询的值等于总点数则连通，另外要考虑反着走），第二个树状数组每个小圈开三个点分别记录小圈起始点，起始点和结束点是否连通，和结束点的信息，就可以用区间查询（原理同上）统计是否连通。修改时分别维护两个树状数组信息。

#pragma GCC optimize(2)#include
    
     #include
     
      #include
      
       #include
       
        #define low(x) (x&(-x))using namespace std;typedef long long ll;int read(){    int x=0,f=1;char ch=getchar();    while (ch<'0'||ch>'9') ch=='-'&&(f=-1),ch=getchar();    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();    return x*f;}const int N=10010,M=5e5+10;int n,tot,sum;bool val[M];int *a[N],st[N],ed[N],siz[N],w[M],belong[M];struct BIT{    int c[M<<1];    void add(int x,int y,int k){for (;x<=k;x+=low(x)) c[x]+=y;}    int query(int x){int su=0;while (x) su+=c[x],x-=low(x);return su;}}bit[2];bool get(int x,int y){    if (x==y) return 1;    if (x>y) swap(x,y);    return (bit[0].query(y)-bit[0].query(x-1)==y-x+1)||        (bit[0].query(x)-bit[0].query(a[belong[x]][1]-1)+bit[0].query(a[belong[y]][siz[belong[y]]])-bit[0].query(y-1)==siz[belong[y]]-(y-x-1));}//判小圈两点是否相通bool get1(int x,int y){    if (x==y) return 1;    if (x>y) swap(x,y);    return (bit[1].query(y)-bit[1].query(x-1)==y-x+1)||(bit[1].query(x)+bit[1].query(3*n)-bit[1].query(y-1)==3*n-y+1+x);}//判大圈两点是否相通int main(){    n=read();a[0]=&w[0];    for (int i=1;i<=n;++i)    {        siz[i]=read();        a[i]=a[i-1]+siz[i-1];        for (int j=1;j<=siz[i];++j)val[++sum]=read(),w[sum]=sum,belong[sum]=i;        st[i]=read(),ed[i]=read();    }    for (int i=1;i<=n;++i)        for (int j=1;j<=siz[i];++j)bit[0].add(a[i][j],val[a[i][j]],sum);    for (int i=1,x;i<=n;++i)    {        x=i*3;bit[1].add(x-1,get(a[i][st[i]],a[i][ed[i]]),n*3);        bit[1].add(x-2,val[a[i][st[i]]],n*3);        bit[1].add(x , val[a[i][ed[i]]],n*3);    }    for (int i=0,_=read(),x,y,mode;i<_;++i)    {        mode=read();        if (mode==1)        {            x=read();int u=belong[x];            if (x==a[u][st[u]])                 bit[1].add(3*u-2,-val[x],n*3),bit[1].add(3*u-2,val[x]^1,n*3);            else if (x==a[u][ed[u]])                 bit[1].add(3*u,-val[x],n*3),bit[1].add(3*u,val[x]^1,n*3);            bit[1].add(u*3-1,-get(a[u][st[u]],a[u][ed[u]]),n*3);            bit[0].add(x,-val[x],sum),bit[0].add(x,val[x]^1,sum);            bit[1].add(u*3-1,get(a[u][st[u]],a[u][ed[u]]),n*3),val[x]^=1;        }        if (mode==2)        {            x=read(),y=read();            int u=belong[x],v=belong[y];            if            (                (get1(3*u,3*v-2)&&get(x,a[u][ed[u]])&&get(y,a[v][st[v]]))||                (get1(3*v,3*u-2)&&get(x,a[u][st[u]])&&get(y,a[v][ed[v]]))            )puts("Yes");//先从大圈判，再从小圈判，否则会被卡，见下图            else if (u==v&&get(x,y)) puts("Yes");else puts("No");        }    }    return 0;}
       
      
     
    

下图黑点表示可以通行，白点反之，双边表示大圈边，单边表示小圈边，此时A点和B点仍可连通

T1 我要的幸福（happiness）

解题思路：模拟(考场已A，无心写思路）

#include
    
     #include
     
      using namespace std;int read(){    int x=0;char ch=getchar();    while (ch<'0'||ch>'9') ch=getchar();    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();    return x;}const int N=1010;int n,m,top;int a[N][N];bool bo[N][N];int sta[N*2];bool dfs(int x,int y){    if (bo[x][y]||(!a[x][y])) return 0;    if (x==n&&y==m) return sta[++top]=a[x][y],1;    if (x==n)    {        if (dfs(x,y+1)) return sta[++top]=a[x][y],1;        else return bo[x][y]=1,0;    }    if (y==m)    {        if (dfs(x+1,y)) return sta[++top]=a[x][y],1;        else return bo[x][y]=1,0;    }    if (a[x+1][y]
      
       1) printf("%d ",sta[top]),--top;        printf("%d\n",sta[1]);    }    return 0;}
      
     
    

---

T2 天黑黑(dark)

解题思路：模拟(考场已A，无心写思路）

#pragma GCC optimize(2)#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;typedef long long ll;int read(){    int x=0,f=1;char ch=getchar();    while (ch<'0'||ch>'9') ch=='-'&&(f=-1),ch=getchar();    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();    return x*f;}const int N=4e5+10;int a[N],top=1,tot;ll sum;char s[N];bool cmp(int x,int y){return x>y;}int dfs(int i){    if (s[i]=='X') return 1;    else if (s[i]=='A') return dfs(++tot)+dfs(++tot);    else return max(dfs(++tot),dfs(++tot));}int main(){    scanf("%s",s+1);    while (~scanf("%d",&a[top]))++top;    sort(a+1,a+top,cmp);    int q=dfs(++tot);    for (int i=1;i<=q;++i) sum+=a[i];    printf("%lld\n",sum);    return 0;}