发布时间：2024-02-21

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";
}