@happyforever 2018-11-07T13:20:14.000000Z 字数 8116 阅读 522

11.7北京测试解题报告

清北学堂 解题报告

各题状况

期望得分： $70+80+80$
实际得分： $50+50+80$

T1

写啥啊。。。。
暴力！
总共用时刚好一小时
耶

话说出锅之后让我修还行
hhhhh
顺便把T2的也修掉吧

T2

刚开始想了个错误的做法（漏考虑了一个情况）
还好写注释的时候就发现了，不然得亏死。
吔

......
给自己一耳光。
总共用了大概 $40min?$

T3

$woc$ 这题暴力分这么足的吗
然后就。。。写了全部的部分分
最后还剩了半小时就写了个莫队，纯粹是为了打发时间，最后也确实没调出来

有关lwl今天考挂了

写给自己吧应该是。。。
我感觉老师应该不会看我的解题报告，所以写上大概也无伤大雅
如果老师您看了这东西，反正我写的也不是什么违规的东西 $QwQ$

$lwl$ 今天考了 $20$ 分，前两个题都爆零，最后一题有 $20$ 分

题目及考场代码

T1

/*
 * 50分模拟
 * 70分考虑并查集？
 * 把可以同时进餐的人放到一个并查集里面
 * 最后检查是否存在没有快乐的人参加的并查集
 *
 * 那么怎么确定某两个人是否可以同时进餐?
 * 假设我们现在只关注两个序列：0~n-1，0~m-1
 * 那么最多lcm(n,m)的长度后会出现循环
 * 也就是说，最多会有lcm(n,m)天对答案有贡献
 * 3*2000*2000的每次将可以同时进餐的两人标记到同一个数组里面
 * 复杂度应该没分析错。。
 *
 * 除此之外。。
 * 我个人认为如果数据很大或者数据随机，有极大的可能是Yes
 * 嘛，反正不会正解，直接输出也无所谓qwq
 */
#include <cstdio>
#include <algorithm>
inline int read()
{
    int n=0,w=1;register char c=getchar();
    while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
    return n*w;
}
const int N=2001;
int n,m,k,fa[N*3],siz[N*3];
int gcd(int a,int b)
{return b?gcd(b,a%b):a;}
int find(int x)
{return fa[x]==x?fa[x]:fa[x]=find(fa[x]);}
inline void work(int b)
{
    int x;
    for(int i=0;i<b;++i)
    {
        x=find(read());
        k-=siz[x];
        siz[x]=0;
    }
}
inline void work2()
{
    int lcm,fi,fj,aa,bb;
    lcm=n*m/gcd(n,m);
    m+=n,k+=m;
    aa=0,bb=n;
    for(int i=0;i<lcm;++i)
    {
        fi=find(aa),fj=find(bb);
        if(fi!=fj)fa[fj]=fi,siz[fi]+=siz[fj];
        ++aa,++bb;
        if(aa==n)aa=0;
        if(bb==m)bb=n;
    }
}
int main()
{
    freopen("happy2.in","r",stdin);
    freopen("happy2.out","w",stdout);
    int T=read(),lcm,aa,bb,cc;
    while(T--)
    {
        n=read(),m=read(),k=read();
        if(n>2001 || m>2001 || k>2001)
        {
            puts("Yes");
            continue;
        }
        n+=m+k;
        for(int i=0;i<n;++i)fa[i]=i,siz[i]=1;
        n-=m+k;
        if(!k)work2();
        else
        {
            lcm=1ll*n*m*k/gcd(n,gcd(m,k));
            m+=n,k+=m;
            aa=0,bb=n,cc=m;
            for(int i=0,fi,fj,fk;i<lcm;++i)
            {
                fi=find(aa),fj=find(bb),fk=find(cc);
                if(fk!=fj)fa[fk]=fj,siz[fj]+=siz[fk];
                if(fi!=fj)fa[fj]=fi,siz[fi]+=siz[fj];
                ++aa,++bb,++cc;
                if(aa==n)aa=0;
                if(bb==m)bb=n;
                if(cc==k)cc=m;
            }
        }
        for(int i=1;i<=3;++i)
            work(read());
        puts(k?"No":"Yes");
    }
    fclose(stdin);fclose(stdout);
    return 0;
}

T2

/*
 * p=0: 输出0
 * p=1: 统计有多少人被怀疑(假设有x个),ans=x(x-1)/2
 *
 * 有关正解的思考：
 * 对每个人记录有多少人是怀疑他的
 * 那么对每个人只要求出他后面有多少人可以跟他组成合法方案就行了
 * 但是。。。如果有一个人认为有嫌疑的两人同时被叫去喝茶只会对答案有1的贡献
 *
 * n<=1000: n^2枚举
 * 同时用一个数组记录哪些人同时被一个人怀疑，统计答案时刨除
 * 
 */
#include <cstdio>
#include <algorithm>
inline int read()
{
    int n=0,w=1;register char c=getchar();
    while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
    return n*w;
}
const int N=3e5+1;
int n,p,a[N],map[1001][1001];
long long ans;
int main()
{
    freopen("suspect.in","r",stdin);
    freopen("suspect.out","w",stdout);
    n=read(),p=read();
    if(!p){printf("0");goto E;}
    for(int x,y,i=1;i<=n;++i)
    {
        x=read(),y=read();
        ++map[x][y],++map[y][x];
        ++a[x],++a[y];
    }
    for(int i=1;i<=n;++i)
        for(int j=i+1;j<=n;++j)
            if(a[i]+a[j]-map[i][j]>=p)
                ++ans;
    printf("%I64d",ans);
E:  fclose(stdin);fclose(stdout);
    return 0;
}

T3

/*
 * 数列中没有两个一样的数：每次询问输出0
 * 另外25%的数据：每次暴力扫一段区间统计答案，用桶记录每个数的出现次数，O(nm)
 * 另外20%的数据：每次暴力扫一段区间统计答案，离散化后映射记录原数值，依然用桶记录每个数的出现次数，O(nm)
 * 另外20%的数据：sum[i][0/1]表示1~i有多少0/1，如果sum[r][1]-sum[l-1][1]是偶数那么答案为1，否则答案为0
 *
 * 100%的话。。。我赌他很多都是1~(290000~300000)
 * 那就先预处理出来这个东西然后访问的时候直接访问，其他情况暴力算qwq
 * emmmmm
 * 好像空间开不下了。。。。
 * 注意到每次操作其实可以看做所有元素的异或和再异或上这个区间内每个元素一次
 *
 * 考虑离线做？
 * 把所有问题读进来之后按左端点排序，左端点相同按右端点从左到右排序？
 * 还是考虑莫队。。。按照l/size进行排序
 */
#include <set>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
inline int read()
{
    int n=0,w=1;register char c=getchar();
    while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
    return n*w;
}
const int N=3e5+1;
std::set<int> se;
int n,m,size,a[N],emp[N],sum[N][3],map[N],vis[N],ans[N];
struct Query{
    int l,r,id;
    bool operator<(const Query &x)const
    {return l/size==x.l/size?r<x.r:l/size<x.l/size;}
}que[N];
inline void work2()
{
    for(int i=1;i<=n;++i)
    {
        sum[i][0]=sum[i-1][0];
        sum[i][1]=sum[i-1][1];
        ++sum[i][a[i]];
    }
    m=read();int l,r;
    while(m--)
    {
        l=read(),r=read();
        puts((sum[r][1]==sum[l-1][1] || sum[r][1]-sum[l-1][1]&1)?"0":"1");
    }
}
int tmp,etmp;
inline void add(int x)
{
    tmp^=map[a[x]];
    if(!vis[a[x]])
        etmp^=map[a[x]];
    ++vis[a[x]];
}
inline void del(int x)
{
    tmp^=map[a[x]];
    --vis[a[x]];
    if(!vis[a[x]])
        etmp^=map[a[x]];
}
inline void work1()
{
    m=read();int l,r,ans;
    while(m--)
    {
        ans=0,l=read(),r=read();
        memset(vis,0,sizeof vis);
        for(int i=l;i<=r;++i)
            ++vis[a[i]];
        for(;l<=r;++l)
            if(vis[a[l]] && (vis[a[l]]&1)==0)
            {
                ans^=map[a[l]];
                ++vis[a[l]];
            }
        printf("%d\n",ans);
    }
}
inline void work3()
{
    //完犊子，没写出来
    for(int i=1;i<=m;++i)
        que[i]=(Query){read(),read(),i};
    std::sort(que+1,que+1+m);
    int l=1,r=1;
    for(int i=1;i<=m;++i)
    {
        while(l<que[i].l)del(l--);
        while(l>que[i].l)add(l++);
        while(r<que[i].r)add(r++);
        while(r>que[i].r)del(r--);
        ans[que[i].id]=tmp^etmp;
    }
    for(int i=1;i<=m;++i)
        printf("%d\n",ans[i]);
}
int main()
{
    freopen("xor.in","r",stdin);
    freopen("xor.out","w",stdout);
    bool flag1=true,flag2=true;
    n=read(),size=sqrt(n);
    for(int i=1;i<=n;++i)
    {
        emp[i]=a[i]=read();
        if(flag1)
        {
            if(!se.count(a[i]))
                se.insert(a[i]);
            else    flag1=false;
        }
        if(flag2 && a[i]>1)flag2=false;
    }
    if(flag1)
    {
        m=read();
        while(m--)puts("0");
        goto E;
    }
    else
        if(flag2)
            work2();
        else
        {
            std::sort(emp+1,emp+1+n);
            for(int x,i=1;i<=n;++i)
            {
                x=std::lower_bound(emp+1,emp+1+n,a[i])-emp;
                map[x]=a[i],a[i]=x;
            }
            if(n<=1000)
                work1();
            else    work3();
        }
E:  fclose(stdin);fclose(stdout);
    return 0;
}

正解及代码

T1

考虑简化过的情况：只有两个序列，且 $n,m$ 互质
那么显然在经过 $n\times m$ 天之后每个男生都和每个女生聚会过了
此时只要有人是快乐的就会将快乐传递给所有人
那么再考虑 $\gcd(n,m)\ne 1$ 的情况，此时第 $0$ 个男生可以跟第 $\gcd(n,m),2\gcd(n,m)\cdots$ 个女生聚会，第 $1$ 个男生可以跟第 $\gcd(n,m)+1,2\gcd(n,m)+1\cdots$ 个女生聚会，以此类推……
这时可以转化成将 $\gcd(n,m)$ 个人捆到一起之后，如果有一组人（捆到一起算一组）都是快乐的，那么所有人都可以变得快乐
而三个序列就直接求出来 $\gcd(\gcd(n,m),k)$ 就行了
所以正解做法就是求给出的快乐的人的编号能否构成在 $\gcd(\gcd(n,m),k)$ 的完全剩余系

#include <cstdio>
#include <cstring>
inline int read()
{
    int n=0,w=1;register char c=getchar();
    while(c<'0' || c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
    return n*w;
}
const int N=1e5+1;
int n,m,k,g,tot,xx;
bool a[N];
int gcd(int a,int b)
{return b?gcd(b,a%b):a;}
inline void work(int x)
{
    for(int i=1;i<=x;++i)
    {
        xx=read()%g;
        if(!a[xx])--tot;
        a[xx]=true;
    }
}
int main()
{
    freopen("happy2.in","r",stdin);
    freopen("happy2.out","w",stdout);
    int T=read();
    while(T--)
    {
        memset(a,false,sizeof a);
        n=read(),m=read(),k=read();
        tot=g=gcd(gcd(n,m),k);
        for(int i=1;i<=3;++i)work(read());
        puts(tot?"No":"Yes");
    }
    fclose(stdin);fclose(stdout);
    return 0;
}

T2

记 $d[i]$ 表示第 $i$ 个人被选的次数， $f[i]$ 表示有多少人被 $d[i]$ 个人的选
对 $f$ 数组求后缀和， $sum[i]$ 表示被选择次数 $\ge d[i]$ 的人的个数
枚举选取方案中的第一个人 $i$ ，则合法的第二个人至多 $sum[p]−d[i]$ 个
假如 $d[i]\gt p−d[i]$ 则要去掉一个 $i$
假如 $d[i]+d[j]−c[i][j]\lt p，也要去掉一个$ j $，仅用枚举$ c[i][j]\gt 0 $的$ j $即可由于对于所有的$ i $，$ c[i][j]\gt 0 $的$ j $的总数不超过$ n $，所以该做法复杂度为$ O(n)$

#include <cstdio>
const int N=3e5+1;
typedef long long LL;
struct Edge{
    int v,nxt;
}edge[1000001];
int n,p,tot,head[N],c[N],ed[N];
void add(int u,int v)
{edge[++tot]=(Edge){v,head[u]};head[u]=tot;}
inline int read()
{
    int n=0;register char c=getchar();
    while(c<'0' || c>'9')c=getchar();
    while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
    return n;
}
inline void update(int x)
{
    if(x==0){++c[0];return;}
    for(;x<=N;x+=x&-x)
        ++c[x];
}
inline int get(int x)
{
    if(x==-1)return 0;
    int sum=0;
    for(;x;x-=x&-x)
        sum+=c[x];
    return sum+c[0];
}
int main()
{
    freopen("suspect.in","r",stdin);
    freopen("suspect.out","w",stdout);
    LL ans=0;
    n=read(),p=read();
    for(int a,b,i=1;i<=n;++i)
    {
        a=read(),b=read();
        add(a,b),add(b,a);
        ++ed[a],++ed[b];
    }
    for(int i=1;i<=n;++i)
        update(ed[i]);
    for(int sum,i=1;i<=n;++i)
    {
        if(ed[i]>=p)ans+=n-1;
        else
        {
            sum=n-get(p-ed[i]-1);
            if(ed[i]>=p-ed[i])--sum;
            for(int v,j=head[i];j;j=edge[j].nxt)
            {
                v=edge[j].v;
                if(ed[v]==p-ed[i])--sum;
                --ed[v];
            }
            for(int j=head[i];j;j=edge[j].nxt)
                ++ed[edge[j].v];
            ans+=sum;
        }
    }
    printf("%I64d",ans>>1);
    fclose(stdin);fclose(stdout);
    return 0;
}

T3

可以写莫队。。。。

可以发现每次求答案相当于区间内所有数的异或和再异或当前区间内出现的数的异或和（区间内每个相同的数只算一次）
也就是把区间内每个数都去掉一个之后的异或和
考虑用树状数组维护每个数值的前一次出现是在哪个位置（前驱），那么每次更新这个前驱的位置，维护当前区间内所有数的异或和再异或上区间内出现的数的异或和

#include <map>
#include <vector>
#include <cstdio>
const int N=3e5+1;
#define mp(x,y) std::make_pair(x,y)
#define pr std::pair<int,int>
inline int read()
{
    int n=0;register char c=getchar();
    while(c<'0' || c>'9')c=getchar();
    while(c>='0' && c<='9')n=n*10+c-'0',c=getchar();
    return n;
}
int n,m,c[N],a[N],b[N],ans[N],nxt[N];
std::map<int,int> vis,pre;
std::vector<pr> q[N];
void add(int x,int w)
{for(;x<=n;x+=x&-x)c[x]^=w;}
int sum(int x)
{
    int res=0;
    for(;x;x-=x&-x)
        res^=c[x];
    return res;
}
int main()
{
    freopen("xor.in","r",stdin);
    freopen("xor.out","w",stdout);
    n=read();int now=0;
    for(int i=1;i<=n;++i)
    {
        a[i]=read();
        ++vis[a[i]];
        nxt[pre[a[i]]]=i;
        pre[a[i]]=i;
        if(vis[a[i]]>1)
            now^=a[i];
        b[i]=now;
    }
    m=read();
    for(int l,r,i=1;i<=m;++i)
    {
        l=read(),r=read();
        q[l].push_back(mp(r,i));
    }
    for(int ql,qr,size,i=1;i<=n;++i)
    {
        size=q[i].size();
        for(int j=0;j<size;++j)
            ans[q[i][j].second]=sum(q[i][j].first)^b[q[i][j].first];
        ql=nxt[i];
        if(ql)add(ql,a[i]);
    }
    for(int i=1;i<=m;++i)
        printf("%d\n",ans[i]);
    fclose(stdin);fclose(stdout);
    return 0;
}