think-cell Round 1(CF1930)题解

C-Lexicographically Largest

题意：
$ 给定一个数组a,每次可以将a_i+i拿出来扔到c数组，然后删除a_i,求字典序最大的c(c数组不能存在相同的数，为从大到小排列的集合) $
思路：
思考可以发现不同的数( $ a_i+i $ )可以从后往前拿不影响，但如果有相同的数,比如3 3，先拿后再拿前得到的数组为3，先拿钱再拿后为3 2
因此对于相同的两个数看作一个区间，区间内可以拿取r-1位置的数将r的数减1，可以从后往前枚举，判断当前数是否出现过，出现过则减去出现次数直至没出现过(需要路径压缩，否则会tle)，直至没出现过，扔进数组
时间复杂度：$ O(nlogn) $

void solve(){
    cin>>n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    vector<ll> ans;
    map<ll,int> cnt;
    for(int i=n;i>=1;i--){
        ll x=a[i]+i;
        while(1){
            if(cnt[x]){
                ll y=x;
                cnt[y]+=cnt[x-cnt[x]];
                x-=cnt[x];
            }
            else{
                ans.push_back(x);
                break;
            }
        }
        cnt[x]++;
    }
    sort(ans.begin(),ans.end(),greater<>());
    for(auto it:ans)cout<<it<<" ";
    cout<<"\n";
}

优化：其实就是按 $ a_i+1 $ 排序，每次$ t=min(t-1,a_i) $ (但是排序有log复杂度，最终复杂度一样)

D-Sum over all Substrings

题意： 均为01串
有一个模式串p,定义一个字符串q为p-good: $ 对于一个p_i在q中总能找到一个区间，使得p_i占一半以上 $
$ 定义f(p)为p-good串中1出现最小的次数 $
$ 计算 \sum {i=1}^{N} \sum _{j=i}^{N} f(p_ip{i+1}…p_j)$
思路：

• 简单版：暴力枚举每个子串,分析如何判断,发现对于一个q只需要管1的位置放在哪,一个1可以照顾模式串的 $ [i-1,i+1] $ 的区间；每次枚举到当前i时，判断是否有覆盖，没有则在i+1放一个1,复杂度 $ O(N^3) $
• 困难版：考虑dp，$ dp_i 表示以i为前缀的所有串的贡献 $
  • $ s_i=0时，dp_i=dp_{i-1} $
  • $ s_i=1时，dp_i=dp_{i+3}+n-i+1 $在i+1位置上放，则$ [i,i+2] $ 都不用考虑了，状态从i+3转移过来,以i为前缀的字符串有n-i+1个，每个增加1贡献

    void solve(){
      int n;
      cin>>n;
      ll ans=0;
      vector<ll> dp(n+10);
      string s;
      cin>>s;
      s=" "+s;
      for(int i=n;i>=1;i--){
      if(s[i]=='0')dp[i]=dp[i+1];
      else dp[i]=dp[i+3]+n-i+1;
      ans+=dp[i];
      }
      cout<<ans<<"\n";
    }