Codeforces Round 757 (Div. 2)(D 质因数dp D2筛法优化调和级数)

A：排序就行

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
 
const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
int a[N],s[N];
int f[N];
vector<int> g[N];
void solve()
{
    int l,r;
   cin>>n>>l>>r>>k;
   vector<int> a;
   for(int i=1;i<=n;i++){
       int x;
       cin>>x;
       if(l<=x&&r>=x){
           a.push_back(x);
       }
   }
   sort(a.begin(),a.end());
   int res=0;
   for(auto x:a){
       if(k>=x) res++,k-=x;
   }
   cout<<res<<"\n";
   
}
 
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;
 
    cin>>t;
    while(t--) solve();
}

B：

直接0开始根据次数从左右两边对称放

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
 
const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
PII a[N];
void solve()
{
   cin>>n;
   vector<int> res(n+1);
   for(int i=1;i<=n;i++){
       cin>>a[i].first;
       a[i].second=i;
   }
   sort(a+1,a+1+n,greater<>());
   int x=1;
   int ans=0;
   for(int i=2;i<=n;i+=2)
   {
       ans+=(x*2)*(a[i].first+a[i-1].first);
       res[a[i].second]=x;
       res[a[i-1].second]=-x;
       x++;
   }
   if(n&1) ans+=2*x*a[n].first,res[a[n].second]=x;
   cout<<ans<<"\n";
   for(int i=0;i<=n;i++) cout<<res[i]<<" \n"[i==n];
}
 
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;
 
    cin>>t;
    while(t--) solve();
}

C：

考虑每一位二进制的贡献

假设当前第i位的二进制的1的个数k,0的个数是n-k

那么贡献就是 2^(n-k) * 2^(k-1)*(2^i)

解锁一下2^(k-1)=

Ck1+Ck3...+Ck 就是从k个里面取奇数个1的方案数等于2^(k-1)

因为CK0+Ck1+Ck2+...Ckk=2^k,取奇数就是2^（k-1）

所以可以化简成2^(n-1*i)

特判一个1都没

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10,mod=1e9+7;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
 
const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
PII a[N];
int qmi(int a, int k, int p)  // 求a^k mod p
{
    int res = 1 % p;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

void solve()
{
   cin>>n>>m;
   int x=0;
   for(int i=1;i<=m;i++){
       int l,r,y;cin>>l>>r>>y;
       x|=y;
   }
   int res=0;
   for(int i=0;i<=30;i++)
   {
       if(x>>i&1){
           res+=(1<<i)%mod*qmi(2,n-1,mod)%mod;
           res%=mod;
       }
   }
   cout<<res<<"\n";
}
 
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;
 
    cin>>t;
    while(t--) solve();
}

+

D1：

因为最大值是5e6

方程为

f[i]:为重拍数组a后前缀的gcd==i的前缀gcd之和的最大值

那么i可以由哪些转移过来呢

i肯定是由i的倍数转移过来的，不然gcd就变小

即f[x]=max(f[x],f[i]+(x-i)*cnt[x])

x是i的某个倍数?

cnt[x]代表x的个数，前缀gcd由i变成了x

那么变化就是（x-i）*cnt[x]

为啥是（x-i）呢，因为是由前缀gcd和==i过来的x

cnt[i]里面包含了cnt[x]

但是这里面的cnt[x]个数的gcd由i变成了x,cnt[i]-cnt[x]的个数的gcd依然还是i

#include<bits/stdc++.h>
using namespace std;
const int N = 5e6+10,mod=1e9+7;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
 
const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
int cnt[N];
int f[N];
void solve()
{
   cin>>n;
   for(int i=1,x;i<=n;i++){
       cin>>x;
       cnt[x]++;
   }
   for(int i=1;i<N;i++){
       for(int j=i+i;j<N;j+=i)
       cnt[i]+=cnt[j];
   }
   f[1]=n;
   for(int i=1;i<N;i++)
   {
       for(int j=i+i;j<N;j+=i)
       {
           f[j]=max(f[j],f[i]+(j-i)*cnt[j]);
       }
   }
   cout<<*max_element(f+1,f+N);
}
 
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t=1;
 
    //cin>>t;
    while(t--) solve();
}

D2：

根据转移可以优化

比如

f[4]转移肯定最优是转移f[2]

那么f[1]就是多余的

f[16]里面

肯定直接从8里面转最优，而不是通过f[2],f[4]转过来，因为我中间肯定还能放一些数

f[1] f[2] f[4] f[8]?

所以我们可以优化只从质数倍的数转移过来

统计个数的时候也一样，

i*primes[j]<N 就从

i的个数就增加i*prime[j]的数的个数，逆序增加，也是个优化

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 20000010;

// cnt(i) 表示i的所有质数倍数的数量，dp(i) 表示以i作为最大gcd的答案
ll cnt[N], dp[N];
int prime[N / 10], cntp;
bool st[N];

void get_prime (int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) prime[cntp ++ ] = i;
        for (int j = 0; i * prime[j] <= n; j ++ )
        {
            st[i * prime[j]] = true;
            if (i % prime[j] == 0) break;
        }
    }
}

void solve ()
{
    get_prime(N - 1);
    int n; cin >> n;
    for (int i = 1, x; i <= n && cin >> x; i ++ ) ++ cnt[x];
    // 找出所有倍数的数量
    for(int j=0;j<cntp;j++){
        for(int i=(N-1)/prime[j];i>=1;i--){
            cnt[i]+=cnt[i*prime[j]];
        }
    }
    dp[1] = cnt[1];
    ll ans = 0;
    for (int i = 1; i < N; i ++ )
    {
        for (int j = 0; j < cntp && (ll)i * prime[j] < N; j ++ )
        {
            int ij = i * prime[j];
            dp[ij] = max(dp[ij], (ll)cnt[ij] * (ij - i) + dp[i]);
        }
        ans = max(ans, dp[i]);
    }
    cout << ans << endl;
}

signed main ()
{
    solve();
    return 0;
}