CF1920题解

C.Partitioning the Array

题意：
给定长度为n的数组，将其分为k份，模一个数m后，每一份相等
思路： 枚举n的因子，然后对于每个相同的位置求gcd，gcd不等于1则计数

#include <bits/stdc++.h>
using namespace std; 
void solve(){
    int n; 
    cin >> n;

    int A[n];
    for (int &i : A)
        cin >> i;
    
    int ans = 0;
    for (int k = 1; k <= n; k++){
        if (n % k == 0){
            int g = 0;
            for (int i = 0; i + k < n; i++)
                g = __gcd(g, abs(A[i + k] - A[i]));
            ans += (g != 1);
        }
    }
    cout<<ans<<"\n";
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); 
    int tc; 
    cin >> tc;
    while (tc--) 
        solve();
}

D.Array Repetition

题意：
有两个操作：
操作1：1 x将x加入数组后方
操作2：2 x将目前数组赋值x次加到后方
若干次操作后，给定询问q,输出当前位置的数字 思路：
二分，创建a,b两个数组一个放数，一个放总数(操作2放的数记为-1)，每次二分比x更大的数量的位置

• 若b[l]=x说明为最后一个数，直接从后往前找第一个不是-1的数
• 否则，若a[l]=-1说明数在当前循环中，x%=b[l-1]，如果为0则说明在当前末尾，找出第一个数即可；否则继续二分
• 若a[l]!=-1,若a[l-1]=-1说明在当前末尾找第一个数，否则即为当前数

  void solve(){
    int n,q;
    cin>>n>>q;
    vector<ll> a,b;
    ll num=0;
    while(n--){
        int op;
        ll x;
        cin>>op>>x;
        if(op==1)a.push_back(x),b.push_back(++num);
        else{
            if((__int128)num*(x+1)>1e18)num=1e18,num++;
            else num*=(x+1);
            a.push_back(-1),b.push_back(num);
        }
    }
    while(q--){
        ll x;
        cin>>x;
        while(1){
            int l=0,r=a.size()-1;
            while(l<r){
                int mid=l+r>>1;
                if(b[mid]>x)r=mid;
                else l=mid+1;
            }
            if(b[l]==x){
                if(a[l]!=-1)cout<<a[l]<<" ";
                else{
                    while(a[l]==-1)l--;
                    cout<<a[l]<<" ";                    
                }
                break;
            }
            else{
                if(a[l]==-1){
                    x%=b[l-1];
                    l--;
                    if(x==0){
                        while(a[l]==-1)l--;
                        cout<<a[l]<<" ";
                        break;
                    }
                }
                else{
                    l--;
                    if(a[l]==-1){
                        while(a[l]==-1)l--;
                        cout<<a[l]<<" ";
                        break;                        
                    }
                    else{
                        cout<<a[l]<<" ";
                        break;
                    }
                }
            }
        }
    }
    cout<<"\n";
  }  
  

  E.Counting Binary Strings

  题意：
  找出符合下列性质的01串个数，

• 有n个子串满足只有一个1
• 这样的子串长度最多为k

思路：
对于一个1来说，若左边有n个0,右边有m个0，则满足第一条性质的串为(n+1)*(m+1)个
因为满足第二条性质，所以n+m+1<=k即(n+1)*(m+1)<=k+1
拓展到多个1 用数组 $ a_1,a_2,a_3,…$ 表示被1间隔开的0的各个区间长度
则 $ sum=a_1 \cdot a_2 + a_2 \cdot a_3+…+ $
考虑dp
$dp_{i,j}=\sum_{p=1}^{min(\frac{i}{j},k+1-j)}dp_{i-j \cdot p,p} $

void solve(){
    int n,k;
    cin>>n>>k;
    vector<vector<int>> dp(n+1,vector<int>(n+1));
    for(int i=1;i<=n;i++)dp[0][i]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            for(int p=1;p*j<=i&&p+j<=k+1;p++){
                dp[i][j]=(dp[i][j]+dp[i-p*j][p])%mod;
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)ans=(ans+dp[n][i])%mod;
    cout<<ans<<"\n";
}