HLOJ-DAY 5

Posted on By 张, 高畅 HLOJ-DAY 5无评论

休息日，但是晚自习！

于是被抓回来写BLOG了。

[T3]

原题

很显然这题一定是有固定的方案的。

首先对于 n \equiv 0 (mod 2) ，直接构造输出两个 [1,n] 就可以。

但对于 n \equiv 1 (mod 2) ，可能需要费一点脑子。

可以操作 [1,n] 、 [1,n-1] 、 [n-1,n] 、[n-1,n] 就可以了。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;
int a[N],c[N];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    printf("%d %d\n",1,n);
    if(n&1)
    {
        printf("%d %d\n",1,n-1);
        printf("%d %d\n",n-1,n);
        printf("%d %d\n",n-1,n);
        for(int i=1;i<=m-4;i++)printf("%d %d\n",1,n);
    }
    else
    {
        printf("%d %d\n",1,n);
        for(int i=1;i<=m-2;i++)printf("%d %d\n",1,n);
    }
    return 0;
}

[T4]

原题

什么？为什么是绿题。

ZGC真是越来越智障了。

首先这是一个区间的问题，其次是一个亦或的问题。

因此我们要考虑转成前缀的问题。

考虑 x=0 或 x=2^n

显然亦或值再怎么大肯定不会超过 2^n ，因此只要不取到 0 就可以了。

我们可以构造 [1\bigoplus 0,2\bigoplus 1,…,(2^n-1)\bigoplus (2^n-2)] 长度 2^n-1

而 x 不为这两个的时候，考虑 i 与 i \bigoplus x，在 a 中只能有一个，随便选一个，长度为 2^{n-1}-1

#include<bits/stdc++.h>
using namespace std;
const int N=(1<<20);
int n,m,x,st[N];
vector<int>res;
int main()
{
    scanf("%d%d",&n,&x);
    m=(1<<n);
    st[0]=st[x]=1;
    for(int i=1;i<m;i++)
    {
        if(!st[i]&&!st[i^x])
        {
            res.push_back(i);
            st[i^x]=1;
        }
    }
    for(int i=res.size()-1;i>=1;i--)res[i]^=res[i-1];
    printf("%d\n",res.size());
    for(auto item:res)printf("%d ",item);
    return 0;
}

[T5]

原题
令 f_i 为左边第一个 x 满足 a_x=b_i，g_i 为右边第一个 x 满足 a_x=b_i

然后这个东西 O(n) 就可以维护。

接下来考虑有没有解以及怎么构造的情况。

按 b_i 进行排序以后，查询 \max_a(f_i,i)=b_i 且 \min_b(f_i,i)=b_i，如果成立，就证明可以通过操作 [f_i,i] 使这一位归位；同时查询\max_a(i,g_i)=b_i 且 \min_b(i,g_i)=b_i 如果是，可以操作 [i,g_i] 使此位归位。

最大最小值的维护可以使用 ST表 /线段树

CODE:

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,INF=0x3f3f3f3f;
int n;
int a[N],b[N],c[N],T[N];
int f[N],g[N];
int Max[N][25],Min[N][25],Log[N];
inline void init()
{
    scanf("%d",&n);
    memset(Max,-0x3f,sizeof Max);
    memset(Min,0x3f,sizeof Min);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        T[i]=-INF;
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&b[i]);
        T[a[i]]=i;
        f[i]=T[b[i]];
    }
    Log[0]=-1;
    for(int i=1;i<=n;i++)
    {
        T[i]=INF;
        Log[i]=Log[i>>1]+1;
        Max[i][0]=a[i];
        Min[i][0]=b[i];
        c[i]=i;
    }
    for(int i=n;i;i--)
    {
        T[a[i]]=i;
        g[i]=T[b[i]];
    }
    for(int j=1;j<=Log[n];j++)
    {
        for(int i=1;i+(1<<j)-1<=n;i++)
        {
            Max[i][j]=max(Max[i][j-1],Max[i+(1<<(j-1))][j-1]);
            Min[i][j]=min(Min[i][j-1],Min[i+(1<<(j-1))][j-1]);
        }
    }
}
int get_max(int x,int y)
{
    int k=Log[y-x+1];
    return max(Max[x][k],Max[y-(1<<k)+1][k]);
}
int get_min(int x,int y)
{
    int k=Log[y-x+1];
    return min(Min[x][k],Min[y-(1<<k)+1][k]);
}
int cmp(int x,int y){return b[x]<b[y];}
vector<pair<int,int> >res;
int main()
{
    init(); 
    sort(c+1,c+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        int x=c[i];
        if(f[x]!=-INF&&get_max(f[x],x)==b[x]&&get_min(f[x],x)==b[x])res.push_back({f[x],x});
        else if(g[x]!=INF&&get_max(x,g[x])==b[x]&&get_min(x,g[x])==b[x])res.push_back({x,g[x]});
        else
        {
            puts("-1");
            return 0;
        }
    }
    printf("%d\n",res.size());
    for(auto item:res)printf("%d %d\n",item.first,item.second);
    return 0;
}

[T6]

弱化版原题
不是为什么还要推式子
总之大家只要知道：
i\cdot j\cdot k\cdot \gcd(i,j,k) \geq i\cdot \gcd(i,j) \cdot \gcd(i,k)\cdot \gcd(j,k)+j\cdot \gcd(j,i) \cdot\ gcd(j,k)\cdot \gcd(i,k)+k \cdot \gcd(k,i)\cdot \gcd(k,j)\cdot \gcd(i,j)

相当于

$lcm(i,j,k) \geq i+j+k$

但是 lcm 增长的势头显然是要比加法来得快的。

因此反向操作,用 C_{r-l+1}^{3} – [lcm(i,j,k)

对原式进行放缩，由于 i<j<k ，因此 lcm(i,j,k)<3k

又因为 lcm(i,j,k) 肯定是 k 的倍数，因此 lcm(i,j,k)=k 或 lcm(i,j,k)=2k

对于等于 2k 的情况，我们令 x=\frac{2k}{i}，y=\frac{2k}{j}，z=\frac{2k}{k}=2

我们对老前辈的式子动一下手脚

$lcm(i,j,k)1=\frac{i+j+k}{2k}>1=\frac{1}{x}+\frac{1}{y}+\frac{1}{z}>1=\frac{1}{x}+\frac{1}{y}>\frac{1}{2}通过枚举，(x,y)=(4,3)或(5,3)因此(i,j,k)=(3t,4t,6t)或(6t,10t,15t)。
这个东西可以直接算出来。
但是对于k$ 的情况，由于实在不好做，于是离线。
将值域内所有的每个数进行因数分解存入 vector
然后用树状数组计算贡献。
具体来说，枚举到 i 的第 j 的约数时，贡献是 Size_i-j-1，其中 Size_i 是 i 因数个数。
答案更新采用类似双指针一样的算法更新。
CODE:

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,M=2e5;
typedef long long LL;
struct node
{
    int l,r,id;
}q[N];
int cmp(node a,node b){return a.r<b.r;}
struct fenwick
{
    LL tr[N];
    int lowbit(int x){return x&(-x);}
    void modify(int x,int v){for(;x<=M;x+=lowbit(x))tr[x]+=v;}
    LL query(int x)
    {
        LL res=0;
        for(;x;x-=lowbit(x))res+=tr[x];
        return res;
    }
}BIT;
LL C_3(int x){return 1LL*x*(x-1)/2LL*(x-2)/3LL;}
vector<int>factor[N];
LL res[N];
int main()
{
    int T;
    scanf("%d",&T);
    for(int i=1;i<=T;i++)
    {
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].id=i;
        res[i]=C_3(q[i].r-q[i].l+1)-max(0LL,(q[i].r/6LL)-((q[i].l-1)/3LL))-max(0LL,(q[i].r/15LL)-((q[i].l-1)/6LL));
    }
    for(int i=1;i<=M;i++)
    {
        for(int j=i+i;j<=M;j+=i)factor[j].push_back(i);
    }
    sort(q+1,q+T+1,cmp);
    int cur=1;
    for(int i=1;i<=M;i++)
    {
        for(int j=0;j<factor[i].size();j++)BIT.modify(factor[i][j],factor[i].size()-j-1);
        for(;cur<=T&&q[cur].r<=i;cur++)res[q[cur].id]-=(BIT.query(q[cur].r)-BIT.query(q[cur].l-1));
    }
    for(int i=1;i<=T;i++)printf("%lld\n",res[i]);
    return 0;
}
训练日志

发表回复