「GDKOI2021普及组Day1」简要题解

Thunder_S · 2021-01-29 20:13:32 · 个人记录

T1

题目大意：给出一个n\times n的01矩阵，其中a_{1,1}=1，a_{1,i}表示第i列和第n列所有元素的异或值（不包括a_{1,i}），a_{i,1}表示第i行和第n行所有元素的异或值（不包括a_{i,1}），现在更改这个矩阵的里的一个数，问更改的数是哪个。n\le 2000

题解：

如果这个矩阵有元素进行改动，那么可以知道a_{1,i}和a_{i,1}可能会有元素有问题

那么可以将这个矩阵的有问题的a_{1,i}和a_{i,1}找到，然后分类讨论

1. 行和列上都没有问题：那么显然更改了a_{1,1}
2. 行和列上都只有一个元素有问题：行和列的交点就是更改的元素
3. 行上全部有问题、列上只有一个有问题（反之亦然）：行上都有问题说明在更改的数在第n行，那么对应的哪列有问题更改的数就在哪列
4. 行和列上的元素本身有问题
5. 只有行有问题（或只有列）：那么就是a_{n,1}（或者a_{1,n}）
6. 行和列都是全部有问题：a_{n,n}

Code

#include<cstdio>
#define N 2005
using namespace std;
int n,num,rnum,cnum,a[N][N],c[N],r[N],err[N*N][3],err_r[N],err_c[N];
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;++i)
    {
        for (int j=1;j<=n;++j)
        {
            scanf("%d",&a[i][j]);
            if (j!=1) c[i]^=a[i][j];
            if (i!=1) r[j]^=a[i][j];
        }
    }
    c[n]^=a[n][1];
    r[n]^=a[1][n];
    if (a[1][1]==1)
    {
        printf("1 1\n");
        return 0;
    }
    for (int i=2;i<n;++i)
    {
        if (c[i]^c[n]!=a[i][1]) ++cnum,err_c[cnum]=i,++num,err[num][1]=i,err[num][2]=1;
        if (r[i]^r[n]!=a[1][i]) ++rnum,err_r[rnum]=i,++num,err[num][1]=1,err[num][2]=i;
    }
    if (num==1)
    {
        printf("%d %d\n",err[1][1],err[1][2]);
        return 0;
    }
    if (num==2)
    {
        if (rnum==1&&cnum==1)
        {
            printf("%d %d\n",err_c[cnum],err_r[rnum]);
            return 0;
        }
    }
    if (num==n-2)
    {
        if (cnum==n-2) printf("%d 1\n",n);
        else printf("1 %d\n",n);
        return 0;
    }
    if (num==n-1)
    {
        if (cnum==1) printf("%d %d\n",err_c[cnum],n);
        else printf("%d %d\n",n,err_r[rnum]);
    }
    if (num==2*(n-2))
    {
        printf("%d %d\n",n,n);
        return 0;
    }
    return 0;
}

T2

题目大意：有一宽度为n的水槽，水槽两边无限高，每个单位长度都有一定的高度，水会往左右扩散至第一个比自己高度高的位置。q次操作，每次将第x位的水灌到y（操作之间没有影响），问水会扩散到多少个格子。n,q\le2\times10^5。

题解：

想到一种显然的暴力就是从当前位置往左右枚举，直到找到一个比自己高的位置，时间复杂度O(qn)

考虑优化，发现可以不用枚举，可以二分，同时维护一下区间最大值即可。

维护区间最大值建议使用ST表，时间复杂度O(1)查询最大值，总的时间复杂度O(q\log n)

如果用线段树时间复杂度会到O(q\log^2n)，会被卡

Code

#include<cmath> 
#include<cstdio>
#include<algorithm>
#define inf 2147483647
#define N 500005
#define ll long long 
using namespace std;
int n,q,x,l,r,mid,res,L,R;
ll y,a[N],sum[N],f[N][20],lg[N];
int query(int l,int r)
{
    int x=lg[r-l+1];
    return max(f[l][x],f[r-(1<<x)+1][x]);   
} 
int main()
{
    freopen("water.in","r",stdin);
    freopen("water.out","w",stdout);
    scanf("%d%d",&n,&q);
    for (int i=1;i<=n;++i)
        scanf("%lld",&a[i]),f[i][0]=a[i];
    for (int i=2;i<=n;++i) lg[i]=lg[i>>1]+1;
    for (int j=1;j<=18;++j)
        for (int i=1;i<=n;++i)
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
    for (int i=1;i<=n;++i)
        sum[i]=sum[i-1]+a[i];
    a[0]=a[n+1]=inf;
    for (int i=1;i<=q;++i)
    {
        scanf("%d%lld",&x,&y);
        l=1;r=x-1;
        res=0;
        while (l<=r)
        {
            mid=(l+r)>>1;
            if (query(mid,r)>=y) res=mid,l=mid+1;
            else r=mid-1;
        }
        L=res;
        l=x+1;r=n;
        res=n+1;
        while (l<=r)
        {   
            mid=(l+r)>>1;
            if (query(l,mid)>=y) res=mid,r=mid-1;
            else l=mid+1;
        }
        R=res;
        printf("%lld\n",(R-L-1)*y-(sum[R-1]-sum[L]));
    }
    return 0;
}

T3

题目大意：给出n个数（n是偶数），现在要删去一些数，让剩下的数两两配对后和在[l,r]，问最少删去多少个数（必须删去偶数个，如果全删完了也满足条件，可以不删）。n\le 10^6

题解：

先将序列排序

发现如果(a,c)(b,d)是合法的，那么(a,d)(b,c)也是合法的（a\le b\le c\le d）

略证：

因为(a,c)合法，那么l\le a+c\le r

同理l\le b+d\le r

那么l\le a+c\le a+d\le b+d\le r

所以(a,d)(b,c)合法

那么可以思考一种贪心

用两个指针分别指到头尾（设头元素是x，尾元素是y）

如果x+y>r，那么y已经无法造成合法贡献了，可以直接删除

同理如果x+y<l，x也不会造成任何贡献

如果l\le x+y\le r，那么就可以把x,y配对，然后往下走

最后注意判断如果删掉了奇数那就再删一个

Code

#include<cstdio>
#include<algorithm>
#define N 1000005
using namespace std;
int n,l,r,ans,a[N];
int main()
{
    freopen("match.in","r",stdin);
    freopen("match.out","w",stdout);
    scanf("%d%d%d",&n,&l,&r);
    for (int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    int i=1,j=n;
    while (i<j)
    {
        if (a[i]+a[j]>r) --j,++ans;
        else if (a[i]+a[j]<l) ++i,++ans;
        else if (a[i]+a[j]>=l&&a[i]+a[j]<=r) ++i,--j;
    }
    if (i==j) ++ans;
    printf("%d\n",ans);
    return 0;
}

T4

题目大意：给出一张n点m边的图，q次询问，每次询问要求从x开始，只能经过边权\le w的边，问最多能到达多少个点。n,q\le2\times10^5,m\le4\times10^5

题解：

其实运用了一个显而易见的结论将题目简化了。

由于询问之间互相独立，考虑离线，发现会走的边只会在最小生成树上，那么将询问的w和每条边的边权从小到大排序，每次询问将所有\le w的边加入，维护并查集的同时记录连通块大小即可

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 200005
using namespace std;
struct node
{
    int from,to,val;
}a[N<<1];
struct ques
{
    int id,val,pos;
}c[N];
int n,m,q,x,y,z,f[N],size[N],ans[N];
bool cmpm(node x,node y) {return x.val<y.val;}
bool cmpq(ques x,ques y) {return x.val<y.val;}
int find(int x)
{
    if (f[x]!=x) f[x]=find(f[x]);
    return f[x];
}
int main()
{
    freopen("travel.in","r",stdin);
    freopen("travel.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;++i)
        f[i]=i,size[i]=1;
    for (int i=1;i<=m;++i)
        scanf("%d%d%d",&a[i].from,&a[i].to,&a[i].val);
    sort(a+1,a+m+1,cmpm);
    scanf("%d",&q);
    for (int i=1;i<=q;++i)
        scanf("%d%d",&c[i].pos,&c[i].val),c[i].id=i;
    sort(c+1,c+q+1,cmpq);
    int i=1,j=1;
    while (j<=q)
    {
        while (a[i].val<=c[j].val&&i<=m)
        {
            int xx=find(a[i].from),yy=find(a[i].to);
            if (xx!=yy)
            {
                f[xx]=yy;
                size[yy]+=size[xx];
            }
            ++i;
        }
        int xx=find(c[j].pos);
        ans[c[j].id]=size[xx];
        ++j;
    }
    for (int i=1;i<=q;++i)
        printf("%d\n",ans[i]);
    return 0;
}