[CF 1828] Codeforces Round 873 (Div. 2) • CC's

A Divisible Array#

第一题是简单的构造。第 $i$ 个数字是 $i$ 的时候总和是 $n(n+1)/2$ ，为了凑个条件三，我们给所有数再乘 $2$ 就可以了。

B. Permutation Swap#

第二题实际上是形成了 k 组互不干扰的集合，集合中的数字可以随意调换顺序。那么我们要做的就很简单了，检查每个数字到其目标位置的距离，然后取最大公约数。

#include <algorithm>
#include <iostream>
using namespace std;
constexpr int XN = 200010;

int a[XN];

int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }
int main() {
  ios::sync_with_stdio(false);

  int kase;
  cin >> kase;
  while (kase--) {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
      cin >> a[i];
    int res = a[1] - 1;
    for (int i = 2; i <= n; i++)
      res = gcd(res, abs(a[i] - i));
    cout << res << '\n';
  }
  return 0;
}

cpp

C. Counting Orders#

第三题是简单的组合数学。以大到小（更强限制下没有选中的数字可以延续在更弱的限制中使用）的顺序考虑限制中每个位置的选择方案数，这部分可以二分搜索。然后把每个位置的选择方案数累乘即可。

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
constexpr int XN = 200010;
constexpr ll MOD = 1e9 + 7;

int n;
int lim[XN];
int choices[XN];

int solve() {
    vector<int> t;
    for (int i = 0; i < n; i++) {
        int idx = lower_bound(choices, choices + n, lim[i]) - choices;
        if (choices[idx] <= lim[i]) idx++;
        if(idx>=n)return 0;
        t.push_back(n - idx + 1 - 1);
    }
    ll res = t[0];
    for (int i = 1; i < t.size(); i++) {
        if(t[i]-i<=0)return 0;
        res = (res * (t[i] - i)) % MOD;
    }
    return res;
}
int main() {
    ios::sync_with_stdio(false);

    int kase;
    cin >> kase;
    while (kase--) {
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> choices[i];
        }
        for (int i = 0; i < n; i++) {
            cin >> lim[i];
        }
        sort(lim, lim + n);
        reverse(lim,lim+n);
        sort(choices, choices + n);
        cout << solve() << '\n';
    }
}

cpp

D1. Range Sorting (Easy Version)#

首先能够发现一个数组如果能划分成多个不重叠的区域分别排序，那就一定别合在一起，前者的代价更小。

考虑固定一维边界，比如开头。如果结尾右移一个位置：如果新进入区间的数字是最大的，那就独自作为新的区域；如果不是，那说明它在排序后会位于前方的某个位置。我们挪动这个数字的唯一办法是以其当前位置和目标位置作为左右端点执行一次排序。但是当我们把这个数字挪动到新位置时，同样会跨过区间内的其他数字，这些数字在就结尾的答案中将被挪动到了它们的目标位置。我们永远不会排序两个重叠的区间，排序两个重叠区间不如直接排序二者的并。因此，新数字导致的全新排序区域即以区间内这些数字的最小目标位置为左端点。我们只需要把目前的排序答案从最右侧弹出端点，直到新的左区间可以加入即可。每次弹出和加入新端点的代价可以累计计算。由于每个数字的左区间最多加入一次，整个复杂度就是 $O(n^2\log n)$ ，符合题目要求。

#include <algorithm>
#include <cstring>
#include <deque>
#include <iostream>
#include <vector>
#include <set>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
constexpr int XN = 5010;

int ft[XN];
inline int lowbit(int x) {
    return x&-x;
}
inline void ftadd(int pos, int x) {
    while (pos < XN) {
        ft[pos] += x;
        pos += lowbit(pos);
    }
}
inline ll ftget(int pos) {
    int res = 0;
    while (pos != 0) {
        res += ft[pos];
        pos -= lowbit(pos);
    }
    return res;
}

int n;
int a[XN];
int a_sorted[XN];

int main() {
    ios::sync_with_stdio(false);

    int kase;
    cin >> kase;
    while (kase--) {
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            a_sorted[i] = a[i];
        }
        sort(a_sorted, a_sorted + n);
        for (int i = 0; i < n; i++)
            a[i] = lower_bound(a_sorted, a_sorted + n, a[i]) - a_sorted+1;
        ll ans = 0;
        for (int l = 0; l < n; l++) {
            vector<int> div;
            memset(ft,0,sizeof(ft));
            div.push_back(-1);
            ll res = 0;

            for (int r = l; r < n; r++) {
                int kth=ftget(a[r]);
                while (!div.empty() && *div.rbegin() >= kth) {
                    int nxt = *(div.rbegin() + 1) + 1;
                    res -= *div.rbegin() - nxt;
                    div.erase(div.end() - 1);
                }
                res += (r - l) - (*div.rbegin() + 1);
                div.push_back(r - l);
                ftadd(a[r],1);

                ans += res;
            }
        }
        cout << ans << "\n";
    }

    return 0;
}

cpp

D2. Range Sorting (Hard Version)#

虽然 D1 的做法相比 $O(n^2)$ 的答案略差，但可以过。不过 D2 就寄了——没法继续优化的。我们并没有办法优化掉右区间移动的部分..想要做到这一点，意味着我们需要在左区间移动前后，找到一种办法维护不同右区间的答案。然而该问题里 $r-l$ 这个代价不容易分散到点上。

属于挖性质挖浅了。

#include <algorithm>
#include <cstring>
#include <stack>
#include <iostream>
#include <vector>
#include <set>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
constexpr int XN = 300010;
constexpr int XP=20;

int n;
int a[XN],a_sorted[XN];
int l[XN],r[XN];
int maxx[XN][XP];

int main(){
    ios::sync_with_stdio(false);

    int kase;
    cin >> kase;
    while (kase--){
        cin >> n;
        for (int i = 0; i < n; i++){
            cin >> a[i];
            a_sorted[i] = a[i];
        }
        sort(a_sorted, a_sorted + n);
        for (int i = 0; i < n; i++)
            a[i] = lower_bound(a_sorted, a_sorted + n, a[i]) - a_sorted;
        
        stack<int> q;
        for(int i=0;i<n;i++){
            while(!q.empty() && a[q.top()]>a[i])q.pop();
            if(q.empty())l[i]=-1;
            else l[i]=q.top();
            q.push(i);
        }
        while(!q.empty())q.pop();
        for(int i=n-1;i>=0;i--){
            while(!q.empty() && a[q.top()]>a[i])q.pop();
            if(q.empty())r[i]=n;
            else r[i]=q.top();
            q.push(i);
        }

        for(int i=0;i<n;i++)maxx[i][0]=a[i];
        for(int p=1;p<XP;p++){
            for(int i=1<<(p-1);i<n;i++){
                maxx[i][p]=max(maxx[i][p-1],maxx[i-(1<<(p-1))][p-1]);
            }
        }

        ll ans = 0;
        for(int i=1;i<=n;i++)ans+=(ll)i*(i-1)/2;
        for (int i = 0; i < n; i++){
            int t=l[i];
            for(int p=XP-1;p>=0;p--){
                if(t+1>=(1<<p) && maxx[t][p]<a[i])
                    t-=1<<p;
            }
            ans-=(ll)(r[i]-i)*(l[i]-t);
        }
        cout<<ans<<endl;
    }

    return 0;
}

cpp

E. Palindrome Partition#

E 寄了。对题目理解出了问题，下意识以为在统计所有子串的划分方案总和，但是统计方案总和需要优化这么个东西

f(r)=\sum_{l} (f(l-1)+1)[t(l..r)]

其中 $t$ 表示该子串是回文串。鉴于 $t$ 似乎并没有递推的性质，这个离散的东西目测没法维护。

既然只是单纯统计合法子串，就可以用方案间的包含关系了。统计回文串的办法有很多，马拉车或者直接哈希。然后就是简单确定最短的转移位置。这个可以靠维护优先队列来做到。

#include <algorithm>
#include <string>
#include <cstring>
#include <stack>
#include <iostream>
#include <vector>
#include <set>
#include <queue>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
constexpr int XP = 20;
constexpr int XN = 500010;
constexpr ll MOD=1e9+7;

ll qpow(ll a,int b,ll m){
    ll res=1;
    a%=m;
    for(;b;b>>=1,a=(a*a)%m){
        if(b&1)res=(res*a)%m;
    }
    return res;
}

struct SH{
    ll h[XN];
    ll p,m;
    ll pp[XN];
    SH(){
        p=26;
        m=MOD;
        pp[0]=1;
        for(int i=1;i<XN;i++)pp[i]=(pp[i-1]*p)%m;
    }
    void init(const string &str){
        for(int i=0;i<str.size();i++){
            h[i+1]=(h[i]*p+(str[i]-'a'+1))%m;
        }
    }

    ll get(int l,int r){
        ll t=(h[l-1]*pp[r-l+1])%m;
        ll res=((h[r]-t)%m+m)%m;
        return res;
    }
} sp,ss;

int maxlen[XN];
char str[XN],rev[XN];

int f[XN];
vector<int> quit[XN];

int main(){
    ios::sync_with_stdio(false);
    int kase;cin>>kase;
    while(kase--){
        int n;cin>>n;
        for(int i=0;i<n;i++)cin>>str[i];
        for(int i=0;i<n;i++)rev[i]=str[i];
        reverse(rev,rev+n);

        sp.init(str);
        ss.init(rev);
        // cout<<"done"<<endl;
        for(int i=0;i<n;i++)maxlen[i]=0;
        for(int i=0;i<n;i++){
            int l=0,r=i+1+1; // [ )
            while(l+1<r){
                int mid=(l+r)/2;
                int a=i-mid+1,b=i+mid;
                if(a>=0 && b<n && sp.get(a+1,i+1)==ss.get(n-(b+1)+1,n-(i+1)-1+1)){
                    l=mid;
                }else r=mid;
            }
            maxlen[i]=l;
        }

        for(int i=0;i<n;i++)f[i]=0;
        for(int i=0;i<n;i++)quit[i].clear();
        set<int> mid;
        for(int i=0;i<n;i++){
            for(auto x:quit[i])mid.erase(x);
            
            if(!mid.empty()){
                int prev=*mid.rbegin();
                int len=i-prev;
                int prevl=prev-len+1;
                if(prevl-1>=0)f[i]=f[prevl-1];
                f[i]++;
            }

            if(maxlen[i]>0){
                int r=i+maxlen[i];
                quit[r+1].push_back(i);
                mid.insert(i);
            }
        }

        ll res=0;
        for(int i=0;i<n;i++)res+=f[i];
        cout<<res<<"\n";
    }

    return 0;
}

cpp

F. Two Centroids#

首先能猜测到两个点是相邻的关系，否则两点路径间的其他点也都是中点，这（直觉上）是一个更严格的情况。同时，简单检查后可以发现奇数点会寄，因为在切断少点一侧的中点后必有一边将大于 $\lfloor n/2 \rfloor$ 。这启发我们在有两个中点时，树的某种大小将是对称的情况。当某个点 $u$ 为中点时，我们考虑如何使得它某个邻居成为另一个中点：另一个中点只能是最大子树的根 $v$ ，其他情况都会产生更大的子树，更容易不合法。现在我们面临的情况是已经不合法了，需要补充点。在挪动前子树 $v$ 大小 $w$ 不超过 $n/2$ ，挪动后则严格小于这个值，只有新出现的以 $u$ 为根的子树可能破坏掉中点的条件，它的大小为 $n-w$ 。设需要增加 $d$ 个点，

n-w<=(n+d)/2
2n-2w<=n+d
d>=n-2w

plaintext

则需要补充的点数量为 $n-2w$ ， $w$ 为中点 $u$ 最大子树 $v$ 的大小。

现在考虑如何维护树的中点。首先一个点时讨论中点没有意义，干脆设置成自身；当点增加时，只有当某个子树大小超过 n/2，才会导致中点变化，变化方向是向这个子树移动。由于移动的条件是子树大小超过了 n/2，所以剩余点严格小于 n/2，在中点挪动后等于 n/2，一样符合中点的要求，因此中点可以维护了。增加节点带来的子树大小变化、切换中点带来的大小变化，需要一个数据结构来统计，可以使用 DFS 序 + 线段树。