首页

11.9 讲课的补题

# gym104768K / QOJ7687 Randias Permutation Task

容易发现答案最多为 min⁡(n!,2m)\min(n!,2^m) ，由于 n×m≤180n\times m\le 180 ，那么答案 ≤9!=362880\le 9!=362880 。因此复杂度为 O(ans)O(ans) 级别的爆搜都是对的。维护一下当前的答案集合，枚举下一个排列是选还是不选即可。

int n,m;
vector <int> tmp,a[200];
vector < vector<int> > temp;
set< vector<int> > S;
int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++) a[i].push_back(read());
    for(int i=1;i<=m;i++)
    {
        tmp.resize(n),temp.clear();
        for(auto p:S)
        {
            for(int j=0;j<n;j++) tmp[j]=p[a[i][j]-1];
            temp.push_back(tmp);
        }
        for(auto x:temp) S.insert(x);
        S.insert(a[i]);
    }
    cout<<S.size();
    cerr<<endl<<1e3*clock()/CLOCKS_PER_SEC<<"ms";
    return 0;
}

# CF1468M Similar Sets

看到 ∑ki≤2×105\sum k_i\le 2\times 10^5 ，考虑根号分治。下设 m=∑kim=\sum k_i ，我们考虑那些大小超过 m\sqrt{m} 的序列，显然这样的序列不会超过 m\sqrt{m} 个，我们每次可以暴力遍历除了它以外的所有序列进行判断，这部分复杂度是 O(mm)O(m\sqrt{m}) 的。现在我们再只考虑那些大小 <m<\sqrt{m} 的序列，我们可以暴力枚举这些数列的所有元素对 (x,y)(x,y) ，并把它们全部储存起来然后判断是否有两个相同数对即可。这里有一个常用结论：将 nn 分成若干个不超过 xx 的数字，它们的平方和的最大值约等于 nxnx 。则元素对的数量级别是 O(mm)O(m\sqrt{m}) 的，那么这一部分复杂度也是 O(mm)O(m\sqrt{m}) 的。因此总复杂度也是 O(mm)O(m\sqrt{m})

# ABC259Ex Yet Another Path Counting

首先有一个显然的暴力，对于每种颜色找到其所有格子，然后枚举起点和终点用组合数 O(1)O(1) 计算答案。然后还能想到一种 dp 做法，就是对于每种颜色，设 fi,jf_{i,j} 表示所有可能的起点走到 (i,j)(i,j) 的方案数，转移是平凡的。我们考虑将它们综合起来，考虑题目中一个隐藏的限制，∑cnti=n2\sum cnt_i=n^2 ，我们不妨将两种方法结合一下。我们设立一个阈值 BB ，当这个颜色对应的格子数量 ≥B\ge B 时，这样的格子只会有 n2B\frac{n^2}{B} 个，我们用第二种方法，时间复杂度为 O(n4B)O(\frac{n^4}{B}) ；当格子数量 <B<B 时，我们用第一种方法，根据上一题的结论，复杂度是 O(nB)O(n^B) 的。平衡一下复杂度，取 B=nB=n 即可，总时间复杂度为 O(n3)O(n^3) 。

# QOJ6405 Barkley

不妨先考虑 k=1k=1 的情况，设 g(l,r)g(l,r) 表示区间 [l,r][l,r] 的 gcd⁡\gcd ，那么就相当于求 max⁡x=lrgcd⁡(g(l,x−1),g(x+1,r))\max\limits_{x=l}^{r}\gcd(g(l,x-1),g(x+1,r)) 。考虑左端点固定后 gcd⁡(l,x)\gcd(l,x) 会形成一些连续段，那么显然删除突变点是最优的，即每个不同取值第一次出现的位置。并且由于段的个数只会有 log⁡V\log V 级别，因此我们直接倍增找出每个连续段的开头位置，然后求出删掉它的答案并不断取 max⁡\max 即可。那么对于 kk 更大的情况，容易发现删掉一个位置后右边的区间可以变成一个 k−1k-1 的子问题，因此写成递归的形式即可。总时间复杂度为 O(nlog⁡2V+∑log⁡k+1V)O(n\log^2V+\sum \log^{k+1}V) 。

int n,q,lg[N];
ll st[N][21],a[N];
ll gcd(ll x,ll y)
{
    if(y==0) return x;
    return gcd(y,x%y);
}
ll query(int l,int r)
{
    if(l>r) return 0;
    int k=lg[r-l+1];
    return gcd(st[l][k],st[r-(1<<k)+1][k]);
}
ll solve(int l,int r,int k,ll g)
{
    if(k==0) return gcd(g,query(l,r));
    ll ans=solve(l+1,r,k-1,g);
    int R=l;
    ll tmp=gcd(a[l],g);
    while(true)
    {
        for(int i=lg[n];i>=0;i--)
            if(R+(1<<i)-1<=n && st[R][i]%tmp==0) R+=(1<<i);
        if(R>r) break;
        ans=max(ans,solve(R+1,r,k-1,tmp));
        tmp=gcd(tmp,a[R]);
    }
    return ans;
}
int main()
{
    n=read(),q=read();
    for(int i=1;i<=n;i++) a[i]=readll(),st[i][0]=a[i];
    for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
    for(int i=1;i<=lg[n];i++)
        for(int j=1;j+(1<<i)-1<=n;j++)
            st[j][i]=gcd(st[j][i-1],st[j+(1<<i-1)][i-1]);
    while(q--)
    {
        int l=read(),r=read(),k=read();
        cout<<solve(l,r,k,0)<<'\n';
    }
    return 0;
}

# gym104768I / QOJ7685 Barkley II

考虑去枚举 mex=xmex=x ，那么我们其实只需要找出所有不出现 xx 的极长区间即可，只需要简单地记录 xx 上一次出现得位置就能找出这些区间，然后对于这些区间都做一遍区间数颜色。显然总共的区间个数不会超过 2n2n ，离线下来扫描线加树状数组即可，最后对于每个枚举到的 mexmex ，用最多的区间颜色数减去它去更新一下答案。至于正确性，因为如果真实的 mexmex 更小，那么一定有一个更长的区间去对应于这个 mexmex ，因此答案不会更劣。时间复杂度为线性对数。

int n,m,a[N],tmp[N],tr[N],ans[N];
vector <int> pos[N];
vector <PII> vt[N];
int lowbit(int x)
{
    return x&-x;
}
void add(int x,int v)
{
    while(x<=n) tr[x]+=v,x+=lowbit(x);
}
int query(int x)
{
    int ans=0;
    while(x!=0) ans+=tr[x],x-=lowbit(x);
    return ans;
}
int main()
{
    int T=read();
    while(T--)
    {
        n=read(),m=read();
        for(int i=1;i<=n;i++)
        {
            a[i]=read();
            if(a[i]<=n+1) pos[a[i]].emplace_back(i);
        }
        for(int i=1;i<=n+1;i++)
        {
            int last=1;
            for(int j=0;j<pos[i].size();j++)
            {
                int x=pos[i][j];
                if(last<=x-1) vt[x-1].push_back({last,i});
                last=x+1;
            }
            if(last<=n) vt[n].push_back({last,i});
            if(pos[i].size()==0) break;
        }
        for(int i=1;i<=n;i++)
        {
            int last=tmp[a[i]]+1;
            tmp[a[i]]=i,add(last,1),add(i+1,-1);
            for(int j=0;j<vt[i].size();j++)
            {
                PII p=vt[i][j];
                ans[p.second]=max(ans[p.second],query(p.first));
            }
        }
        int maxx=-1;
        for(int i=1;i<=n+1;i++)
        {
            maxx=max(maxx,ans[i]-i);
            if(pos[i].size()==0) break;
        }
        cout<<maxx<<'\n';
        for(int i=1;i<=n+1;i++) tmp[a[i]]=tr[i]=ans[i]=0,pos[i].clear(),vt[i].clear();
    }
    return 0;
}

# gym104768C / QOJ7679 Master of Both IV

设 x=lcm(S)x=lcm(S) ，y=xor(S)y=xor(S) ，那么显然有 x≥max⁡(S),y<2×max⁡(S)x\ge \max(S),y<2\times \max(S) ，所以可能的情况只有两种，y=0y=0 或者 y=max⁡(S)y=\max(S) 。考虑 y=0y=0 的情况，事实上就是问有多少个非空子集异或和为 00 ，这是一个经典结论，假设所有数字组成的线性基大小为 xx ，那么数量就是 2n−x−12^{n-x}-1 ，因为考虑不在线性基里的 n−xn-x 个元素，对于它们的任何一个非空子集的异或和，我们一定能从线性基中用唯一的方案异或出这个数，使得这两部分的总异或和为 00 。而对于第二种情况，我们可以直接枚举最大值 xx 。方案数分成两部分，对于 xx 这个数，就必须选奇数次，设 cntxcnt_x 表示 xx 的出现次数，那么方案数就是 (cntx1)+(cntx3)+⋯=2cntx−1\binom{cnt_x}{1}+\binom{cnt_x}{3}+\cdots=2^{cnt_x-1} ；而剩下的数就必须是 xx 的约数（不包含自己），我们需要从这些约数中选一些子集使得其异或和为 00 ，这又变成了第一部分的那个问题，仍然用线性基解决即可，然后用乘法原理将两部分方案数合并即可。总时间复杂度为 O(nlog⁡2V)O(n\log^2V) 。

struct LB{
    int p[25],siz;
    void init()
    {
        siz=0;
        for(int i=0;i<=18;i++) p[i]=0;
    }
    void insert(int x)
    {
        for(int i=18;i>=0;i--)
        {
            if((x>>i&1)==0) continue;
            if(p[i]==0)
            {
                p[i]=x,siz++;
                break;
            }
            x^=p[i];
        }
    }
} h[N],A;
int n,a[N],cnt[N],pw[N],tmp[N];
int add(int x,int y)
{
    x+=y;
    return x>=mod?x-mod:x;
}
int main()
{
    pw[0]=1;
    for(int i=1;i<=200000;i++) pw[i]=add(pw[i-1],pw[i-1]);
    int T=read();
    while(T--)
    {
        n=read();
        for(int i=1;i<=n;i++) tmp[i]=cnt[i]=0,h[i].init();
        A.init();
        for(int i=1;i<=n;i++) a[i]=read(),cnt[a[i]]++,h[i].init();
        for(int i=1;i<=n;i++)
        {
            if(cnt[i]==0) continue;
            for(int j=i+i;j<=n;j+=i)
            {
                if(cnt[j]==0) continue;
                tmp[j]+=cnt[i],h[j].insert(i);
            }
        }
        for(int i=1;i<=n;i++) A.insert(a[i]);
        int ans=pw[n-A.siz]-1;
        for(int i=1;i<=n;i++)
        {
            if(cnt[i]==0) continue;
            ans=add(ans,1ll*pw[cnt[i]-1]*pw[tmp[i]-h[i].siz]%mod);
        }
        cout<<ans<<'\n';
    }
    return 0;
}

# CF1468L Prime Divisors Selection

先特判掉 k=1k=1 的情况，此时显然无解。我们将所有数分成两类，A 类是只有一个质因子的，B 类是有多个质因子的。如果一个质因子在 A 类中的出现次数 ≤1\le 1 ，那么包含这个质因子的所有数都不能被选择，我们将这些质因子都扔掉。此时留下来的只有那些在 A 类中出现次数 ≥2\ge 2 的质因子组成的数，那么当 kk 大于剩下的数的数量也是无解的了。我们考虑剩下的情况，下设 cntcnt 表示出现次数 ≥2\ge 2 的质因子数量。如果 k≥2×cntk\ge 2\times cnt ，我们就可以直接对每个质因子都选两个 A 类，然后剩下的随便选一些 B 类即可；否则如果 kk 是偶数，只需要随便 k2\frac{k}{2} 个质因子，然后每个质因子随便选两个 A 类即可。剩下的就是 kk 是奇数且 k<2×cntk<2\times cnt 的情况，容易想到，如果某个质因子在 A 类的出现次数 ≥3\ge 3 ，那我们就选三个包含它的 A 类数，然后就又变成 kk 是偶数的情况了。那么剩下的情况就是每个质因子在 A 类的出现次数都等于 22 ，此时我们考虑利用 B 类数，我们找到质因子个数最小的一个 B 类数 xx ，假设它有 p1,p2⋯pmp_1,p_2\cdots p_m 共 mm 个质因子，对于这 mm 个质因子当中的每一个，我们都选出两个包含它的 A 类数，然后还要再选上 xx ，此时就共选了 2m+12m+1 个数，因此如果 k<2m+1k<2m+1 就无解，否则由于 kk 是奇数，因此我们还需要选偶数个，按照偶数的做法选即可。

但是还有一个问题，我们可不可以不用大数分解算法去分解质因数呢，其实是可以的。首先只有 <109<10^9 的质数才是有用的，因为其它质数的出现次数最多为 11 。我们再线性筛求出 10610^6 以内的质数，用它们去找出每个 A 类质数。而对于剩下的数，要不是一个 ≤109\le 10^9 的质数的平方，要不是一个质数。因此我们直接对出现过的 ≤109\le 10^9 的数判断它的平方是否出现在序列中就行，剩下的数就一定没用了，这样我们就避免了使用大数分解算法。实现起来比较麻烦。

# gym104768J / QOJ7686 The Phantom Menace

不妨去枚举循环同构的偏移量 xx ，容易发现就是要求第一个集合中的字符串的长度为 xx 的后缀与第二个集合中的字符串的长度为 xx 的前缀匹配，且第二个集合中的字符串的长度为 n−xn-x 的后缀与第一个集合中的字符串的长度为 n−xn-x 的前缀匹配。哈希去重后我们对每个前后缀编号，然后将前后缀看成点，让每个串的前缀向后缀连边，不难发现只需要求解有向图欧拉回路即可。时间复杂度 O(nm)O(nm) 。

int T,n,m,deg[N],ans[M],cnt,tmp1[N],tmp2[N],c1,c2;
bool vis[M];
ull pw[N];
vector <ull> ha[N<<1],vt;
vector <PII> g[M];
string s;
ull get(int i,int l,int r)
{
    if(l>r) return 0;
    return ha[i][r]-ha[i][l-1]*pw[r-l+1];
}
void dfs(int u)
{
    for(int i=(int)g[u].size()-1;i>=0;i=(int)g[u].size()-1)
    {
        PII p=g[u][i];
        g[u].pop_back();
        if(vis[p.second]) continue;
        dfs(p.first);
        vis[p.second]=true,ans[++cnt]=p.second;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    pw[0]=1;
    for(int i=1;i<=1000000;i++) pw[i]=pw[i-1]*base;
    cin>>T;
    while(T--)
    {
        bool res=false;
        cin>>n>>m;
        cnt=c1=c2=0;
        for(int i=1;i<=2*n;i++)
        {
            cin>>s;
            ha[i].clear(),ha[i].resize(m+1);
            for(int j=1;j<=m;j++) ha[i][j]=ha[i][j-1]*base+s[j-1]-'a';
        }
        ull B=(base<<15);
        for(int i=0;i<m;i++)
        {
            vt.clear();
            for(int j=1;j<=n;j++)
            {
                ull a=get(j,1,i),b=get(j,i+1,m)+B;
                vt.push_back(a),vt.push_back(b);
            }
            for(int j=n+1;j<=n*2;j++)
            {
                ull a=get(j,1,m-i)+B,b=get(j,m-i+1,m);
                vt.push_back(a),vt.push_back(b);
            }
            sort(vt.begin(),vt.end());
            vt.erase(unique(vt.begin(),vt.end()),vt.end());
            int start=0,s=vt.size();
            for(int j=1;j<=s;j++) deg[j]=0,g[j].clear();
            for(int j=1;j<=n;j++)
            {
                ull a=get(j,1,i),b=get(j,i+1,m)+B;
                int p=lower_bound(vt.begin(),vt.end(),a)-vt.begin()+1;
                int q=lower_bound(vt.begin(),vt.end(),b)-vt.begin()+1;
                deg[p]++,deg[q]--,g[p].push_back({q,j}),start=p;
            }
            for(int j=n+1;j<=n*2;j++)
            {
                ull a=get(j,1,m-i)+B,b=get(j,m-i+1,m);
                int p=lower_bound(vt.begin(),vt.end(),a)-vt.begin()+1;
                int q=lower_bound(vt.begin(),vt.end(),b)-vt.begin()+1;
                deg[p]++,deg[q]--,g[p].push_back({q,j});
            }
            bool flag=true;
            for(int j=1;j<=s && flag;j++)
                if(deg[j]!=0) flag=false;
            if(flag==false) continue;
            cnt=c1=c2=0;
            for(int j=1;j<=2*n;j++) vis[j]=false;
            dfs(start);
            for(int j=1;j<=2*n && flag;j++)
                if(vis[j]==false) flag=false;
            if(flag==false) continue;
            for(int j=cnt;j>=1;j--)
            {
                if(ans[j]>n) tmp2[++c2]=ans[j]-n;
                else tmp1[++c1]=ans[j];
            }
            for(int j=1;j<=c1;j++) cout<<tmp1[j]<<" ";
            cout<<'\n';
            for(int j=1;j<=c2;j++) cout<<tmp2[j]<<" ";
            cout<<'\n';
            res=true;
            break;
        }
        if(res==false) cout<<"-1"<<'\n';
    }
    return 0;
}

# QOJ2831 Game Theory

不妨先找到初始状态下的 kk ，然后考虑 aka_k 。如果 ak=1a_k=1 ，则操作后 11 的个数减少，kk 会向左移动；如果 ak=0a_k=0 ，则操作后 11 的个数增多，kk 会向右移动。那么移动路径一定是先左右来回运动，每次遇到一个不同的就反向，最后一路走到头全部变成 00 。观察到 kk 左边 00 的个数是等于右边 11 的个数的，并且可以发现，其实答案就是 kk 右侧的 11 的下标之和减去 kk 左侧的 00 的下标之和的差乘 22 再加上 kk ，化简一下其实就是整体的 11 的下标之和乘 22 减去 k2k^2 ，因此线段树维护区间中 11 的下标之和、区间中 11 的数量以及一个翻转的懒标记即可。时间复杂度 O((n+q)log⁡n)O((n+q)\log n) 。

struct node{
    ll sum;
    int cnt,rev;
} tr[N<<2];
int n,q;
char c[N];
void pushup(int k)
{
    tr[k].sum=tr[k<<1].sum+tr[k<<1|1].sum,tr[k].cnt=tr[k<<1].cnt+tr[k<<1|1].cnt;
}
void pushdown(int k,int l,int r)
{
    if(tr[k].rev)
    {
        int mid=(l+r)>>1;
        tr[k<<1].cnt=mid+1-l-tr[k<<1].cnt,tr[k<<1].sum=1ll*(l+mid)*(mid-l+1)/2-tr[k<<1].sum;
        tr[k<<1|1].cnt=r-mid-tr[k<<1|1].cnt;
        tr[k<<1|1].sum=1ll*(mid+1+r)*(r-mid)/2-tr[k<<1|1].sum;
        tr[k<<1].rev^=1,tr[k<<1|1].rev^=1;
        tr[k].rev=0;
    }
}
void build(int k,int l,int r)
{
    tr[k].rev=0;
    if(l==r)
    {
        tr[k].sum=(c[l]=='1'?l:0),tr[k].cnt=(c[l]=='1'?1:0);
        return;
    }
    int mid=(l+r)>>1;
    build(k<<1,l,mid),build(k<<1|1,mid+1,r);
    pushup(k);
}
void upd(int k,int l,int r,int L,int R)
{
    if(R<l || r<L) return;
    if(L<=l && r<=R)
    {
        tr[k].cnt=r-l+1-tr[k].cnt,tr[k].sum=1ll*(l+r)*(r-l+1)/2-tr[k].sum;
        tr[k].rev^=1;
        return;
    }
    int mid=(l+r)>>1;
    pushdown(k,l,r);
    upd(k<<1,l,mid,L,R),upd(k<<1|1,mid+1,r,L,R);
    pushup(k);
}
int main()
{
    while(cin>>n>>q)
    {
        for(int i=1;i<=n;i++) cin>>c[i];
        build(1,1,n);
        while(q--)
        {
            int l=read(),r=read();
            upd(1,1,n,l,r);
            cout<<(tr[1].sum*2-1ll*tr[1].cnt*tr[1].cnt)%mod<<'\n';
        }
    }
    return 0;
}

# CF1725E Electrical Efficiency

（以前做过）

# CF1468B Bakery

先将询问离线下来。显然答案会随着 kk 的增加而减少，考虑当 kk 减少时去维护这几个连续段，同一个连续段内的可以把生产的面包全部卖完，如果因为 kk 的减少导致面包没有卖完，我们就让这段不断向后合并即可。那么每个连续段显然需要记录它总共生产的面包数量和总共的天数，这样判断一下天数乘 kk 与总共生产的面包数量的大小关系就知道是否需要合并了，这些连续段可以用一个 set 维护，按照总共生产的面包数量除以天数从大到小排序就行。然后连续段的合并也可以用并查集简单维护，每次询问的答案就是区间长度的 max⁡\max 了，注意还要特殊处理右端点为 nn 的情况。

更新于

请我喝[茶]~(￣▽￣)~*

YC乌龙 微信支付

微信支付

YC乌龙 支付宝

支付宝

YC乌龙 贝宝

贝宝