Educational Codeforces Round 120 (Rated for Div. 2) D,E 题解

1622D - Shuffle
题意：
给定一个长度为 n n n 的 01 01 01 序列 a a a，现在执行如下操作至多一次：选择一段连续的子串 [ l , r ] [l,r] [l,r]，字串中恰好有 k k k 个 1 1 1，并将这个字串按任意顺序重新排列。求最后本质不同的序列个数对 998244353 998244353 998244353 取模后的结果
1 ≤ n ≤ 2000 1 leq n leq 2000 1≤n≤2000
solution:
做法1：
我们并不在乎去操作哪一段，或者怎样取排列，只在乎最后本质不同的序列。那么如果我们枚举序列发生变化这一段的两个端点（端点元素必须变换），就可以保证最后得到本质不同的序列。
并且我们枚举的这一段中显然不能超过 k k k 个 1 1 1，但是小于 k k k 是可以的，因为我们枚举的是变化的区域而不是执行操作的区域，最后这一段的方案数就是除去两个必变化的端点组合数求答案即可，复杂度 $O(n^2)
code:
#include 

using namespace std;

typedef long long ll;

const int maxn=5050;
const int p=998244353;

ll f[maxn][maxn];
int n,k;
string s;

int pre[maxn];


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    cin>>s;
    f[0][0]=1;
    for(int i=1;i<=n;i++){
        f[i][0]=1;
        for(int j=1;j<=i;j++) f[i][j]=(f[i-1][j-1]+f[i-1][j])%p;
    }
    
    s='#'+s;
    for(int i=1;i<=n;i++) pre[i]=pre[i-1]+(s[i]=='1');
    if(pre[n]k) break;
            if(s[i]=='0') cnt1--;
            if(s[j]=='0') cnt1--;
            ans=(ans+f[cnt][cnt1])%p;  
        }
    }
    cout< 
做法2： 
考虑操作选择的子串，如果要满足恰好 
    
     
      
       
        k
       
      
      
       k
      
     
    k 个 
    
     
      
       
        1
       
      
      
       1
      
     
    1，那么我们肯定选择无法再向两边（
    
     
      
       
        0
       
      
      
       0
      
     
    0）扩展的极长子串，因为该子串的子串的方案都是其子集。并且很显然这样的方案数就是子串长度中选 
    
     
      
       
        k
       
      
      
       k
      
     
    k 个位置放 
    
     
      
       
        1
       
      
      
       1
      
     
    1 的方案数。 
但是考虑到上述极长子串大概率是相交的，必然存在重复贡献。 
如果 
    
     
      
       
        k
       
       
        >
       
       
        =
       
       
        2
       
      
      
       k>=2
      
     
    k>=2，相邻两个极长子串的公共部分就是前一个子串的 
    
     
      
       
        [
       
       
        2
       
       
        ,
       
       
        k
       
       
        ]
       
      
      
       [2,k]
      
     
    [2,k] 和 后一个子串的 
    
     
      
       
        [
       
       
        1
       
       
        ,
       
       
        k
       
       
        −
       
       
        1
       
       
        ]
       
      
      
       [1,k-1]
      
     
    [1,k−1]，也就是说前一个子串的第 
     
      
       
        
         1
        
       
       
        1
       
      
     1 个 
     
      
       
        
         1
        
       
       
        1
       
      
     1 和后一个子串的第 
     
      
       
        
         k
        
       
       
        k
       
      
     k 个 
     
      
       
        
         1
        
       
       
        1
       
      
     1 是唯一不相互包含的。 
当前一个子串的第 
    
     
      
       
        1
       
      
      
       1
      
     
    1 个 
    
     
      
       
        1
       
      
      
       1
      
     
    1 位置变动时，最后操作产生的序列永远不可能与以后一个子串为操作单位时相同，重复贡献产生于当前一个子串的第 
     
      
       
        
         1
        
       
       
        1
       
      
     1 个 
     
      
       
        
         1
        
       
       
        1
       
      
     1 和后一个子串的第 
     
      
       
        
         k
        
       
       
        k
       
      
     k 个 
     
      
       
        
         1
        
       
       
        1
       
      
     1 不动的时候。 
也就是说，设有两个相邻的极长子串 
    
     
      
       
        [
       
       
        
         l
        
        
         1
        
       
       
        ,
       
       
        
         r
        
        
         1
        
       
       
        ]
       
       
        ,
       
       
        [
       
       
        
         l
        
        
         2
        
       
       
        ,
       
       
        
         r
        
        
         2
        
       
       
        ]
       
      
      
       [l_1,r_1],[l_2,r_2]
      
     
    [l1,r1],[l2,r2]，且满足 
    
     
      
       
        
         l
        
        
         1
        
       
       
        <
       
       
        
         l
        
        
         2
        
       
       
        <
       
       
        
         r
        
        
         1
        
       
       
        <
       
       
        
         r
        
        
         2
        
       
      
      
       l_1 
设 
    
     
      
       
        [
       
       
        
         l
        
        
         2
        
       
       
        ,
       
       
        
         r
        
        
         1
        
       
       
        ]
       
      
      
       [l_2,r_1]
      
     
    [l2,r1] 中有 
    
     
      
       
        c
       
       
        n
       
       
        t
       
      
      
       cnt
      
     
    cnt 个 
    
     
      
       
        1
       
      
      
       1
      
     
    1，则重复的方案数为 
    
     
      
       
        
         C
        
        
         
          
           r
          
          
           1
          
         
         
          −
         
         
          
           l
          
          
           2
          
         
         
          +
         
         
          1
         
        
        
         
          c
         
         
          n
         
         
          t
         
        
       
      
      
       C_{r_1-l_2+1}^{cnt}
      
     
    Cr1−l2+1cnt 
复杂度 
    
     
      
       
        O
       
       
        (
       
       
        n
       
       
        )
       
      
      
       O(n)
      
     
    O(n) 
code: 
#include 

using namespace std;

typedef long long ll;

const int maxn=2e5+10;
const int p=998244353;

ll n,k;

ll fac[maxn];
int l[maxn],r[maxn];

string s;

ll qpow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1) res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}

inline ll cal(int n,int m){
    return fac[n]*qpow(fac[m],p-2)%p*qpow(fac[n-m],p-2)%p;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin>>n>>k;
    fac[0]=1;
    for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%p;
    cin>>s;
    s='#'+s;
    if(k==0){
        cout<<1<k&&j+1<=n) break;
            j++;
        }
        
        if(cnt==k){
            if(j==n+1){
                l[++tot]=i,r[tot]=n;
                break;
            }
            else l[++tot]=i,r[tot]=j,j++;
        }
        else break;

        if(s[i]=='1') cnt--;
    }
    //for(int i=1;i<=tot;i++) cout<1) ans=(ans-cal(r[i-1]-l[i]+1,k-1)+p)%p;
    }

    cout< 
1622E - Math Test 
题目描述： 
有 
    
     
      
       
        n
       
      
      
       n
      
     
    n 个学生，
    
     
      
       
        m
       
      
      
       m
      
     
    m 个问题，当某个学生答对了第 
    
     
      
       
        j
       
      
      
       j
      
     
    j 个问题，可以获得 
    
     
      
       
        
         p
        
        
         j
        
       
      
      
       p_j
      
     
    pj 的分数。对于第 
    
     
      
       
        i
       
      
      
       i
      
     
    i 个学生，他预估总共会得到 
    
     
      
       
        
         x
        
        
         i
        
       
      
      
       x_i
      
     
    xi 的分数，但是实际上假设他的得分为 
    
     
      
       
        
         r
        
        
         i
        
       
      
      
       r_i
      
     
    ri，那么他的惊喜值就是 
    
     
      
       
        ∣
       
       
        
         x
        
        
         i
        
       
       
        −
       
       
        
         r
        
        
         i
        
       
       
        ∣
       
      
      
       |x_i-r_i|
      
     
    ∣xi−ri∣。 
现在 
    
     
      
       
        n
       
      
      
       n
      
     
    n 个学生对于 
    
     
      
       
        m
       
      
      
       m
      
     
    m 个问题的答题情况（对/错）已经知道，要求设定每道题对应的分数 
    
     
      
       
        
         p
        
        
         j
        
       
      
      
       p_j
      
     
    pj，满足 
    
     
      
       
        p
       
      
      
       p
      
     
    p 是一个 
    
     
      
       
        [
       
       
        1
       
       
        ,
       
       
        m
       
       
        ]
       
      
      
       [1,m]
      
     
    [1,m] 的全排列，并且使得所有学生的惊喜值 
    
     
      
       
        ∑
       
       
        ∣
       
       
        
         x
        
        
         i
        
       
       
        −
       
       
        
         r
        
        
         i
        
       
       
        ∣
       
      
      
       sum |x_i-r_i|
      
     
    ∑∣xi−ri∣最大 

    
     
      
       
        1
       
       
        ≤
       
       
        n
       
       
        ≤
       
       
        10
       
       
        ,
       
       
        ∑
       
       
        m
       
       
        ≤
       
       
        1
       
       
        
         0
        
        
         4
        
       
      
      
       1 leq n leq 10,sum m leq 10^4
      
     
    1≤n≤10,∑m≤104 

    
     
      
       
        s
       
       
        o
       
       
        l
       
       
        u
       
       
        t
       
       
        i
       
       
        o
       
       
        n
       
       
        :
       
      
      
       solution:
      
     
    solution: 
由于绝对值符号的影响，我们即使知道了每个学生哪几道题对了，也无法知道对最后惊喜值权重的影响，
    
     
      
       
        n
       
      
      
       n
      
     
    n 很小，考虑二进制枚举每个学生的 
    
     
      
       
        ∣
       
       
        
         x
        
        
         i
        
       
       
        −
       
       
        
         r
        
        
         i
        
       
       
        ∣
       
      
      
       |x_i-r_i|
      
     
    ∣xi−ri∣ 是变成 
    
     
      
       
        
         x
        
        
         i
        
       
       
        −
       
       
        
         r
        
        
         i
        
       
      
      
       x_i-r_i
      
     
    xi−ri 还是 
    
     
      
       
        
         r
        
        
         i
        
       
       
        −
       
       
        
         x
        
        
         i
        
       
      
      
       r_i-x_i
      
     
    ri−xi。 
接着对于每道题的分数 
    
     
      
       
        
         p
        
        
         j
        
       
      
      
       p_j
      
     
    pj 来说，我们知道其关于最后惊喜值的多项式的系数，我们希望惊喜值最大，那么根据系数降序排序，来从大到小安排 
    
     
      
       
        
         p
        
        
         j
        
       
      
      
       p_j
      
     
    pj 即可，并且由于我们知道预估分数 
    
     
      
       
        
         x
        
        
         i
        
       
      
      
       x_i
      
     
    xi 的贡献，我们可以求出每次的惊喜值，与之前最大值比较判断是否为最优解即可 
code: 
#include 

using namespace std;

typedef long long ll;

const int maxn=1e4+10;
#define endl 'n'

string s[15];

int n,m;
int ans[maxn],x[maxn];

struct node{
    int v,id;
    bool operator <(const node &oth)const{
        return v>t;
    while(t--){
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>x[i];
        for(int i=1;i<=n;i++){
            cin>>s[i];
            s[i]='#'+s[i];
        }
        // 1:xi-ri
        // 0:ri-xi
        ll mx=-1e18;
        for(int i=0;i<(1<>(j-1))&1){
                    res+=x[j];
                    for(int k=1;k<=m;k++){
                        if(s[j][k]=='1') cnt[k].v--;
                    }
                }
                else{
                    res-=x[j];
                    for(int k=1;k<=m;k++){
                        if(s[j][k]=='1') cnt[k].v++;
                    }
                }
            }
            sort(cnt+1,cnt+m+1);
            for(int j=1;j<=m;j++) res+=1ll*j*cnt[j].v;
            if(res>mx){
                mx=res;
                for(int j=1;j<=m;j++) ans[cnt[j].id]=j;
            }
        }
        for(int i=1;i<=m;i++) cout<
Educational Codeforces Round 120 (Rated for Div. 2) D,E 题解

C/C++/C#相关栏目本月热门文章
