进行一个题的乱做(7.8-7.14)

7.8

昨天早自习被通知不用上了，但还得等一个小时才能来机房，下面在查迟到，于是昨天早上就推了这个题的式子，今天才来做

起初这道题我看成了操作一个数让他严格小于前后两个，都写完了一测样例

…

设 $f_{i,j,1}$ 为进行操作， $i$ 满足条件，并操作完后前 $i$ 位有 $j$ 个满足条件，

设 $f_{i,j,0}$ 为不对 $i$ 进行操作，前 $i$ 个有 $j$ 个满足条件，

不操作的很好转移，就找前一个数操作或不操作的最小值即可

f_{i,j,0}=\min (f_{i-1,j,0},f_{i-1,j,1})

如果这一位操作，那么我们分两种情况

先看前一位不操作，也就是从 $f_{i-1,j-1,0}$ 转移过来

如果想第 $i$ 位满足条件，那么就需要 $i-1,i+1$ 都小于它

也就是

f_{i,j,1}=f_{i-1,j-1,0}+\max (a_{i-1}-a_{i}+1,0)+ \max (a_{i+1}-a_{i}+1)

如果前面的想操作，那就只能从 $i-2$ 转移过来，因为使 $i$ 满足条件就不能让 $i-1$ 满足

在更新 $f_{i-2,j-1,1}$ 的时候，a_{i-1}也会被更新，那我们也需要考虑上,也就是在 $a_{i-2}-1-a_{i}+1$ 和 $a_{i-1}-a_{i}+1$ 取个最小值，分别代表 $a_{i-1}\ge a_{i-2}$ 和 $a_{i-2}\ge a_{i-1} \ge a_{i}$ 的情况

f_{i,j,1}=f_{i-2,j-1,1}+\max (0,\min (a_{i-2}-a_{i},a_{i-1}-a_{i}+1))+\max (0,a[i+1]-a[i]+1)

上述两式取最小即可

最后直接输出 $\min (f_{n,i,1},f_{n,i,0})$

注意初始化

(感觉DP的初始化都很史)

#include<iostream>
#include<cstring>
using namespace std;
const int N=5010;
int f[N][N][2];
int a[N];
int n;
int main()
{
    memset(f,0x3f,sizeof(f));
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    a[0]=-1e9;
    a[n+1]=-1e9;
    f[0][0][0]=0;
    f[1][1][1]=max(0,a[2]-a[1]+1);
    for(int i=1;i<=n;i++)
    {
        f[i][0][0]=f[i-1][0][0];
        for(int j=1;j<=(i+1)/2;j++)
        {
            f[i][j][0]=min(f[i-1][j][1],f[i-1][j][0]);
            if(i>1)
                f[i][j][1]=min(f[i-2][j-1][0]+max(0,a[i-1]-a[i]+1)+max(0,a[i+1]-a[i]+1),f[i-2][j-1][1]+max(0,min(a[i-1]-a[i]+1,a[i-2]-a[i]))+max(0,a[i+1]-a[i]+1));
        }
    }
    for(int i=1;i<=(n+1)/2;i++)
        cout<<min(f[n][i][0],f[n][i][1])<<" ";
}

CF895C

起初发现当质因子个数为偶数是才是完全平方数，看到 $a$ 很小也确实往分解质因数上靠，但最后还是没想出来，看看题解发现能用状压

由于质因数个数很小， $70$ 以内的只有 $19$ 个，于是我们状压质因数，当某一位为 $0$ 时，我们就让它为偶数个，为 $1$ 则为奇数个

设 $f_{i,st}$ 为前 $i$ 个质数，选了第 $i$ 个后质数状态为 $st$ 的方案数

我们存下每个数出现的次数，记为 $cnt_{x}$ ，当遍历到 $x$ 时这个数可以有 $2^{cnt_{x}}$ 种选法，当选奇数个时， $x$ 中有奇数个数的质因子会影响整个状态的奇偶性，我们提前将这些影响记下来，具体的

int st=0;
for(int j=0;j<19;j++)
{
    while(x%pre[j]==0)
    {
        x=x/pre[j];
        st=st^(1<<j);
    }
}

在最后转移的时候直接将这些异或上就好

选奇数个时有 $2^{cnt_{x}-1}$ 种选择，偶数同理，那就在转移的时候直接乘上就可以

最后需要减去空集的情况

#include<iostream>
#include<cstring>
#define int long long
using namespace std;
const int P=1000000007;
const int N=(1<<19);
int OvO;
int f[2][N];
int cnt[71];
int n;
int QWQ[1000010];
int pre[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67};
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        cnt[x]++;
    }
    QWQ[0]=1;
    for(int i=1;i<=100000;i++)
        QWQ[i]=QWQ[i-1]*2%P;
    f[0][0]=1;
    for(int i=1;i<=70;i++)
    {
        if(cnt[i]==0)
            continue;
        OvO^=1;
        memset(f[OvO],0,sizeof(f[OvO]));
        int x=i;
        int st=0;
        for(int j=0;j<19;j++)
        {
            while(x%pre[j]==0)
            {
                x=x/pre[j];
                st=st^(1<<j);
            }
        }
        for(int j=0;j<(1<<19);j++)
        {
            f[OvO][st^j]=(f[OvO][st^j]+f[OvO^1][j]*QWQ[cnt[i]-1]%P)%P;
            f[OvO][j]=(f[OvO][j]+f[OvO^1][j]*QWQ[cnt[i]-1]%P)%P;
        }
    }
    cout<<(f[OvO][0]-1+P)%P;
}

CF229D

妙妙题，但不会，直接进入题解

设 $f_{i,j}$ 为从第 $j+1$ 到第 $i$ 个塔都合并到 $i$ ，那代价就是 $i-j$

转移就是枚举一个 $k$ , $f_{i,i}=\min (f_{j,k})+i-j-1$

要求后面的必须大于等于前面的，那我们捣鼓一个高度前缀和，要求就是 $pre_{i}-pre_{j}\ge pre_{j}-pre_{k}$

$k$ 找最大时，f_{j,k}最小，我们设一个 $pos$ 数组， $pos_{j}$ 代表满足条件的最接近 $j$ 的那个 $k$ ,那我们直接直接枚举 $i,j$ ，当碰见从后往前第一个 $j$ ,符合 $pre_{i}-pre_{j}\ge pre_{j}-pre_{pos_{j}}$ 时，我们就更新
$f$ 和 $pos$

f_{i,j}=f_{j,pos_{j}}+i-j-1

pos_{i}=j

直接推到最后就好了

(估计下次碰到这类题还不很会，虽然很妙妙，但会不了一点)

#include<iostream>
#define int long long
using namespace std;
const int P=1000000007;
int n;
int f[5010][5010];
signed main()
{
    cin>>n;
    f[1][1]=1;
    int ans=0;
    for(int i=2;i<=n+1;i++)
        for(int j=1;j<=i;j++)
        {
            f[i][j]=f[i-1][j]+f[i][j-1]%P;
            if((i+j)%2==1)
                ans=(ans+f[i][j])%P;
        }
    cout<<ans;
}

CF354C

首先有一个暴力的想法就是枚举公因数，判断对于每一个 $i$ ，是否都是 $a_{i} \bmod x \le k$

显然会 $T$

我们换一种方式枚举

还是枚举公因数 $x$ ,我们发现每一个符合条件的数都在 $[nx,nx+k]$ 这个区间里，现在问题就变成了如何快速求解区间内数的个数，那前缀和查分就可以解决，至于枚举复杂度

调和级数好闪，拜谢调和级数

#include<iostream>
using namespace std;
int n,k;
int vis[1000010];
int s[1000010];
int minn=1e9;
int w[1000010];
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
        vis[w[i]]++;
        minn=min(minn,w[i]);
    }
    for(int i=1;i<=1000000;i++)
        s[i]=s[i-1]+vis[i];
    if(minn<=k+1)
    {
        cout<<minn;
        return 0;
    }
    int ans=0;
    for(int i=1;i<=1000000;i++)
    {
        int sum=0;
        for(int j=1;j;j++)
        {
            sum=sum+s[min(1000000,j*i+k)]-s[min(1000000,j*i-1)];
            if(j*i+k>=1000000)
                break;
        }
        if(sum==n)
            ans=i;
    }
    cout<<ans;
}

7.9

CF837D

有朴素DP, $f_{i,j,k,l}$ 前 $i$ 个选了 $j$ 个,二的数量是 $k$ ,五的数量是 $l$ ,然后每一个存 $0,1$ 代表是否能到达

显然空间不够，而每个存 $0,1$ 又太浪费，于是我们把一维状态拉出来当作值, $f_{i,j,k}$ 代表前 $i$ 个选了 $j$ 个，五的数量是 $j$ 时的二的数量。

#include<cstring>
#include<iostream>
#define int long long
using namespace std;
const int N=210;
int wu[210],er[210];
int n,k;
int f[N][N*40];
int w[N];
int WU(int x)
{
    int ans=0;
    while(x%5==0)
    {
        x=x/5;
        ans++;
    }
    return ans;
}
int ER(int x)
{
    int ans=0;
    while(x%2==0)
    {
        x=x/2;
        ans++;
    }
    return ans;
}
signed main()
{   
    memset(f,-0x3f,sizeof(f));
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
        wu[i]=WU(w[i]);
        er[i]=ER(w[i]);
    }
    f[0][0]=0;
    for(int i=1;i<=n;i++)
        for(int j=min(i,k);j>=1;j--)
            for(int l=5200;l>=wu[i];l--)
                f[j][l]=max(f[j][l],f[j-1][l-wu[i]]+er[i]);
    int ans=0;
    for(int i=0;i<=5200;i++)
        ans=max(ans,min(i,f[k][i]));
    cout<<ans;
}

7.13

CF1271D

当最后一个可以转移到 $u$ 的城堡进行转移时，是最优的,设 $f_{i,j}$ 为前 $i$ 个城堡，第 $i$ 个有 $j$ 个士兵所得的价值最大值，转移就是

f_{i,j}=f_{i-1,j-b_{i}}

f_{i,j}=\max(f_{i,j},f_{i,j+1}+c_{i})

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int N=5010;
int f[N][N];
int n,m,k;
int a[N],b[N],c[N];
int lead[N];
vector<int> g[N];
int main()
{
    memset(f,-0x3f,sizeof(f));
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i]>>b[i]>>c[i];
        lead[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        lead[v]=max(lead[v],u);
    }
    for(int i=1;i<=n;i++)
        g[lead[i]].push_back(i);
    int now=k;
    f[0][k]=0;
    for(int i=1;i<=n;i++)
    {
        now=now+b[i];
        for(int j=now;j-b[i]>=a[i];j--)
            f[i][j]=f[i-1][j-b[i]];
        for(int it:g[i])
            for(int j=0;j<now;j++)
                f[i][j]=max(f[i][j],f[i][j+1]+c[it]);
    }
    int ans=-0x3f3f3f3f;
    for(int i=0;i<=now;i++)
        ans=max(ans,f[n][i]);
    if(ans<0)
        cout<<-1;
    else
        cout<<ans;
}

7.14

CF1151E

让求连通块个数，可以转化成点数减边数

一个点的权值 $w_{i}$ 所做的贡献是

w_{i} \times (n-w_{i}+1)

一条边 $w_{i},w_{i-1}$ 所做的贡献是

\min(w_{i},w_{i-1}) \times \max(n-w_{i},w_{i-1}+1)

#include<iostream>
#define int long long
using namespace std;
const int N=100010;
int ans=0;
int n;
int w[N];
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
        ans=ans+w[i]*(n-w[i]+1);
    }
    for(int i=2;i<=n;i++)
        ans=ans-min(w[i],w[i-1])*(n-max(w[i],w[i-1])+1);
    cout<<ans;
}

梦熊

魔法阵是一个大小任意的方阵，设 $i$ 行 $j$ 列有 $a_{i,j}$ 个魔法石

$a_{i,j}\ge m$
设魔法阵大小为 $k$ ，任意从魔法阵选出 $k$ 个格子，满足任意两个格子不在同一行且不在同一列，那么选出的 $k$ 个格子的石子数之和相同
魔法阵对角线石子数不超过 $n$

$n,m$ 为给定常数，有多少种可能的魔法阵，模 $998244353$

对于第二个条件，我们设每行有一个数 $x_{i}$ ,每列有一个数 $y_{j}$ ,则 $a_{i,j}=x_{i}+y_{j}$ ,可以发现，当每个 $x_{i}-1$ 时, $y_{i}+1$ ,这样， $a$ 矩阵不会改变，为了满足其他条件，我们钦定 $\min (x_{i})=0$ ,那么这样,第一个条件就容易满足了，即 $\min(y_{i}) \ge m$ ,那么第三个条件就是

\sum_{i=1}^{k} x_{i}+y_{i} \le n

我们可以将 $n$ 个球放在 $2k$ 个格子里，后 $k$ 个格子每一个都要 $\ge m$ ,前 $k$ 个至少有一个 $0$ ,我们将后 $k$ 个统一减 $m$ ，就变成了

将 $n-k\times m$ 个球放在 $2k$ 个格子里,前 $k$ 个至少有一个 $0$

\begin{pmatrix} n-k\times m+2k\\ 2k \end{pmatrix} - \begin{pmatrix} n-k\times m+k\\ 2k \end{pmatrix}

进行一个题的乱做(7.8-7.14)

qtanglani 发布于 2024-07-08

最后更新于 2024-07-15

7.8

调和级数好闪，拜谢调和级数

7.9

7.13

7.14

7.15

qtanglani