2023年暑假集训总结/6.29-526互联

6-27

T1有毒爱排列

　　有毒让你求长度为 n 且逆序对个数对 p 取余为 k 的排列的个数，答案对 998244353取模。

　　考试时我考虑到设 fi,j 表示放了数 1 ∼ i，此时逆序对个数 mod p = j 的排列个数。转移显然，枚举 i + 1 放到哪个位置即可，时间复杂度 O(n^2p)。得了60分，而后通过观察性质可以发现n>p时答案就是 n!/p，那么可以把 n 压到 100，时间复杂度 O(p^3 )。

　　std:

#include<bits/stdc++.h>
using namespace std;
#define int long long
int const N=1e4+10;
int const K=100+5;
int const mod=998244353;
int f[N][K],nw[K],w[K],n,p,k;
signed main(){
    freopen("per.in","r",stdin);
    freopen("per.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>p>>k;
    if (n>p){
    int g=1;
    for (int i=1;i<=n;++i)
        if (i!=p) g*=i,g%=mod;
    cout<<g<<'\n';
        return 0;
    }
    f[1][0]=1,++nw[1%p];
    for (int i=2;i<=n;++i){
        ++nw[i%p];
        for (int j=0;j<p;++j){
            int q=(i%p-j+p)%p;
            w[j]=nw[q];
        }
        for (int la=0;la<p;++la)
            for (int ni=0;ni<p;++ni)
                f[i][(la+ni)%p]+=f[i-1][la]*w[ni]%mod,f[i][(la+ni)%p]%=mod;
    }
    cout<<f[n][k]<<'\n';
    return 0;
}

T2有毒爱 AT

　　有毒得到了一个字符串，这个字符串上的每一个字符都代表着某题在某场 agc 中的题目编号（例如：FEABCDD）。我们定义吊打子序列为 ABCDE 或 ABCDEF。有毒会询问多次，每次有毒会询问一个区间 [li , ri ]，设字符串 t 为 sli,...,ri。你需要回答 t 最多能划分成几个不相交的吊打子序列。

　　直接n^2可拿45分，考虑优化这个匹配过程，我们从右往左枚举每个左端点，依然是考虑贪心匹配，我们考虑后缀 i → 后缀 i − 1 会改变哪些东西。往开头增加一个字母等价于从这个字母开始往后贪心匹配最靠前的且能匹配的字母。所以我们开个 set 维护一下每种字符出现的位置即可。

　　std：

//A tree without skin will surely die.
//A man without face is invincible.
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&-x)
int const N=5e5+10;
int ans[N];set<int>s[6];
vector< pair<int,int> >a[N];
struct Tree_Array{
    int c[N];
    void update(int x,int v){while (x<N) c[x]+=v,x+=lowbit(x);}
    int query(int x){int res=0;while (x) res+=c[x],x-=lowbit(x);return res;}
}T;
signed main(){
    freopen("agc.in","r",stdin);
    freopen("agc.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n,q;cin>>n;
    string t;cin>>t>>q,t=" "+t;
    for (int i=1;i<=q;++i){
        int l,r;cin>>l>>r;
        a[l].push_back({r,i});
    }
    for (int i=n;i>=1;--i){
        if (t[i]!='A') s[t[i]-'A'].insert(i);
        else{
            int y=i,flg=1;
            for (int j=1;j<5;++j)
                if (s[j].lower_bound(y)!=s[j].end()) y=*s[j].lower_bound(y);
                else{flg=0;break;}
            if (flg){
                y=i;
                for (int j=1;j<5;++j){
                    int p=*s[j].lower_bound(y);
                    s[j].erase(s[j].lower_bound(y)),y=p;
                }
                T.update(y,1);
            }else s[t[i]-'A'].insert(i);
        }
        for (auto g:a[i]){
            int r=g.first,id=g.second;
            ans[id]=T.query(r);
        }
    }
    for (int i=1;i<=q;++i) cout<<ans[i]<<'\n';
    return 0;
}

T3妈妈生的

　　鱼给了你一个 1 ∼ n 的排列 a。

　　我们定义一次操作为执行以下两种函数之一：

　　• 执行一次 f()，这需要 x 的代价。

　　• 选择一个整数 b (1 ≤ b ≤ n)，然后执行 s(b)，这需要 y 的代价。

　　当 a 满足 ∀i (1 ≤ i ≤ n), ai = i 时，停止操作，否则继续进行下一次操作。你需要令停止操作时花费的代价最少，并输出这个最少代价。如不理解题意可以看样例解释。两种函数代码如下：

void f(){
  for (int i=1;i<=n;++i)
  if (a[i]<i) swap(a[i],a[a[i]]);
 }

void s(int x){
  vector<int>b;map<int,int>vis;
  while (!vis[x]) vis[x]=1,b.push_back(x),x=a[x];
  sort(b.begin(),b.end());
  reverse(b.begin(),b.end());
  for (int i=0;i<b.size();++i) a[b[i]]=b[(i+1)%b.size()];
 }

　　考虑观察 f() 函数和 s(x) 函数本质是什么。一个 swap(ai , aai ) 相当于在置换环上把 ai 删掉，令 ai 变成自环，然后 ai 左边那个数连向 ai 右边那个数。所以每个置换环都是独立的。如果我们仅仅用 f() 函数，那么操作次数就是所有置换环需要 f() 次数的 max。我们继续思考 f() 函数的本质，发现对于一个点 i，如果点 i 左边的点的权值比它大，那么它会被删掉。我们用链表维护当前置换环内的数，删掉一个数就判一下它的 next 是否满足条件。由于每个数只会被删一次，复杂度是对的。时间复杂度 O(n log n)，瓶颈在于排序。

　　std：

//A tree without skin will surely die.
//A man without face is invincible.
#include<bits/stdc++.h>
using namespace std;
#define int long long
int const N=1e6+10;
int a[N],vis[N],f[N],ct,pre[N],del[N],nxt[N],suf[N];
vector<int>s,vec;
void d(int x){
    nxt[pre[x]]=nxt[x],pre[nxt[x]]=pre[x];
    if (!del[nxt[x]] && (vec[pre[x]]>vec[nxt[x]])) s.push_back(nxt[x]);
}
signed main(){
    freopen("sort.in","r",stdin);
    freopen("sort.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n,x,y;cin>>n>>x>>y;
    for (int i=1;i<=n;++i) cin>>a[i];
    for (int i=1;i<=n;++i){
        if (vis[i]) continue;
        int y=i;vec.clear();vector<int>v;ct=0;
        while (!vis[y]) vec.push_back(y),vis[y]=1,y=a[y];
        for (int i=1;i<vec.size();++i) pre[i]=i-1;pre[0]=vec.size()-1;
        for (int i=0;i<vec.size()-1;++i) nxt[i]=i+1;nxt[vec.size()-1]=0;
        for (int i=0;i<vec.size();++i) del[i]=0;
        for (int i=0;i<vec.size();++i) if (vec[pre[i]]>vec[i]) v.push_back(i);
        if (vec.size()==1) continue;
        int lun=0;
        while (1){
            ++lun;for (auto i:v) ++ct,del[i]=1;
            if (ct==vec.size()-1) break;
            s.clear();for (auto i:v) d(i);
            sort(s.begin(),s.end());
            s.erase(unique(s.begin(),s.end()),s.end());
            v=s;
        }
        f[++f[0]]=lun;
        for (auto i:vec) vis[i]=1;
    }
    sort(f+1,f+f[0]+1,[](int x,int y){return x>y;});
    int ans=1e18;f[++f[0]]=1;
    for (int i=f[0];i;--i) suf[i]=suf[i+1]+f[i];
    for (int i=1;i<=f[0];++i) ans=min(ans,(i-1)*y+f[i]*x);
    cout<<ans<<'\n';
    return 0;
}