Java教程

8.1

本文主要是介绍8.1，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

ABC262E

题意：

给定\(n\)个点\(m\)条边，选\(k\)个点染红，其他点染蓝，问有多少种方法，让偶数条边两端颜色不同？对\(998244353\)取模

\(1\leq n,m\leq 2*10^5,0\leq k\leq n\)

题解：

假设有\(a\)染红色点的度数和，\(b\)条边两端都是红色的，\(c\)为两端颜色不同的边数

\[a=2*b+c \]

如果\(c\)是偶数，那么\(a\)一定要是偶数，直接枚举用了几个奇数度的点染红，

#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define double long double
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-15)
    const int N=5e5+10,mod=998244353,inv2=5e8+4,inf=2e9;
    const double pi=acos(-1.0);
    int n,m,k;
    int rd[N];
    int s[2];
    int fac[N],inv[N];
    inline int fast(int x,int k)
    {
        int ret=1;
        while(k)
        {
            if(k&1) ret=ret*x%mod;
            x=x*x%mod;
            k>>=1;
        }
        return ret;
    }
    inline void init(int n=5e5)
    {
        fac[0]=inv[0]=1;
        for(int i=1;i<=n;++i) fac[i]=fac[i-1]*i%mod;
        inv[n]=fast(fac[n],mod-2);
        for(int i=n-1;i>=1;--i) inv[i]=inv[i+1]*(i+1)%mod;
    }
    inline int C(int n,int m)
    {
        if(n<m||m<0) return 0;
        return fac[n]*inv[m]%mod*inv[n-m]%mod;
    }
    inline void main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);cout.tie(0);
        cin>>n>>m>>k;
        for(int i=1;i<=m;++i)
        {
            int x,y;cin>>x>>y;
            ++rd[x],++rd[y];
        }
        init();
        for(int i=1;i<=n;++i)
        {
            ++s[rd[i]&1];
        }
        int ans=0;
        for(int i=0;i<n;i+=2)
        {
            ans+=C(s[1],i)*C(s[0],k-i)%mod;
            ans%=mod;
        }
        cout<<ans<<'\n';
    }
}
signed main()
{
    red::main();
    return 0;
}
/*

*/

CF1110E

题意：

给定数组\(c,t\)，每次操作可以让\(c_i=c_{i+1}+c_{i-1}-c_i\)

问能不能通过操作让\(c\)和\(t\)相等。

数组长度\(\leq 10^5\)，\(0\leq c_i,t_i\leq 2*10^9\)

题解：

首先，如果\(c_1\neq t_1\)或者\(c_n\neq t_n\)，肯定不可能。

设\(a_i=c_{i}-c_{i-1}\)

那么操作过后

\[a_{i+1}=c_{i+1}-(c_{i+1}+c_{i-1}-c_i)=c_{i}-c_{i-1}=a_i\\ a_{i}=(c_{i+1}+c_{i-1}-c_i)-c_{i-1}=c_{i+1}-c_i=a_{i+1} \]

发现就是两个位置互换了一下。

那么题目就是给两个差分数组，随便排序之后能不能一样。

#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define double long double
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-15)
    const int N=2e5+10,mod=1e9+7,inv2=5e8+4,inf=2e9;
    const double pi=acos(-1.0);
    int n;
    int a[N],b[N];
    inline void main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);cout.tie(0);
        cin>>n;
        bool flag=1;
        for(int i=1;i<=n;++i)
        {
            cin>>a[i];
        }
        for(int i=1;i<=n;++i)
        {
            cin>>b[i];
        }
        if(a[1]!=b[1]||a[n]!=b[n]) flag=0;
        for(int i=n;i>=1;--i)
        {
            a[i]-=a[i-1];
            b[i]-=b[i-1];
        }
        sort(a+1,a+n+1);
        sort(b+1,b+n+1);
        
        for(int i=1;i<=n;++i) flag&=(a[i]==b[i]);
        if(flag) cout<<"Yes\n";
        else cout<<"No\n";
        //c[i]=c[i+1]+c[i-1]-c[i];
        //c[i]-c[i-1]=c[i+1]-c[i];
        //d[i]=d[i+1]
    }
}
signed main()
{
    red::main();
    return 0;
}
/*
7 2 4 12
7 -5 2 8
7 -5 8 2
*/

P3760

题意：

给定一个序列，求所有子区间和的异或值。

\(n\leq 10^5,\sum a_i\leq 10^6\)

题解：

\(solution1\)

题目要求

\(\bigoplus \sum_{l=0}^n\sum_{r=l+1}^n(s[r]-s[l])\)

二进制数考虑按位

枚举位数\(k\)和右端点，如何快速求有多少满足要求的左端点？

如果右端点是\(1\)，那么左端点：

要么是\(0\)，且左端点低于第\(k\)位的部分小于等于右端点低于第\(k\)位的部分

要么是\(1\)，且左端点低于第\(k\)位的部分大于右端点低于第\(k\)位的部分。

因为后者涉及做减法的时候会不会借位，如果借位，那么第\(k\)位的\(01\)就反转了。

右端点是\(1\)类似。

开两个树状数组，分别维护第\(k\)位是\(0\)和\(1\)的情况。

\(solution2\)

题解区的神仙还能继续优化。

下面引用自 Ntokisq 神仙

如果左右端点的第\(k\)位相同，那么其实就是在求逆序对数。

第\(k\)位不同时，其实是在算顺序对，但是贡献只有不同时才有，不妨用容斥，先不考虑相同不相同，再减去第\(k\)位相同的贡献。

第\(k\)位相同的贡献其实在算逆序对数的时候也算出来了。

那么怎么求序列的逆序对数呢？这个问题肯定是\(O(nlogn)\)的。

但是本题只要求逆序对的奇偶性。

有一个结论：如果一个排列经过\(x\)次交换邻项后变得有序，那么\(x\)和排列的逆序对数奇偶性相同。

可以推导出另一个结论：一个排列的逆序对数的奇偶性与\(n\)减去该排序的环数相同。

最终状态\(p_i=i\)，那么有序的排序是有\(n\)个环的。

每次交换，要么减少一个环，要么增加一个环，减少一个环的话，还需要再花操作一次操作加回来，所以奇偶性也是相同。

求排列的环数可以\(O(n)\)

\(solution3\)

下面是另一种解法

可以直接算出每个数字出现多少次，因为算贡献是\(x-y=v\)的形式，且值域不是很大

设\(f_x\)是\(x\)作为区间和的出现次数，\(s_i\)是\(i\)作为前缀和的出现次数

\[f_x=\sum_{i=0}^ns_i*s_{i+x} \]

设\(s'\)是\(s\)翻转后的数组

\[f_x=\sum_{i=0}^ns_i*s'_{m-i-x} \]

就可以卷积了

\(solution4\)

固定左端点，枚举右端点，就可以求出左端点固定时的\([l,r]\)和的异或值。

那么每次左端点左移一位，其实就是把之前有的所有异或值全部\(+a[l]\)，再把\(a[l]\)插入进去

考虑到\(\sum a_i\)很小，可以每次一位一位的加，然后用\(01trie\)实现。

\(01tire\)实现每次给所有数字\(+1\)是可以实现的：考虑倒着建\(trie\)树，第\(k\)层的儿子代表数字\(x\)的第\(k\)位是\(0\)还是\(1\)，那么给所有数字\(+1\)就是从根节点开始，如果该节点有右儿子，说明这个右儿子这里应该进位，递归进入，然后把该节点的左右儿子翻转一下，更新该节点的信息。

#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define double long double
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-15)
    const int N=1e6+10,mod=1e9+7,inv2=5e8+4,inf=2e9;
    const double pi=acos(-1.0);
    int n;
    int a[N],s[N];
    struct BIT
    {
        int tr[N];
        inline void clear()
        {
            for(int i=1;i<=1000001;++i) tr[i]=0;
        }
        inline void update(int x,int k=1)
        {
            for(int i=x;i<=1000001;i+=lowbit(i)) tr[i]+=k;
        }
        inline int query(int y)
        {
            int sum=0;
            for(int i=y;i;i-=lowbit(i)) sum+=tr[i];
            return sum;
        }
    }T[2];
    inline void main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);cout.tie(0);
        cin>>n;
        for(int i=1;i<=n;++i)
        {
            cin>>a[i];
            s[i]=s[i-1]+a[i];
        }
        int ans=0;
        for(int k=0;k<=20;++k)
        {
            T[0].clear();T[1].clear();
            int sum=0,tmp=(1<<k)-1;
            T[0].update(1);
            for(int i=1;i<=n;++i)
            {
                int now=0,val=s[i]&tmp;
                if((s[i]>>k)&1)
                {
                    now=T[0].query(val+1)+T[1].query(1000001)-T[1].query(val+1);
                    T[1].update(val+1);
                }
                else
                {
                    now=T[0].query(1000001)-T[0].query(val+1)+T[1].query(val+1);
                    T[0].update(val+1);
                }
                now%=2;
                sum^=now;
            }
            if(sum) ans|=(1<<k);
        }
        cout<<ans<<'\n';
    }
}
signed main()
{
    red::main();
    return 0;
}
/*
7 2 4 12
7 -5 2 8
7 -5 8 2
*/
这篇关于8.1的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航