头像

Fancy_z




离线:5小时前


活动打卡代码 AcWing 885. 求组合数 I

Fancy_z
1天前
#include<iostream>
#include<algorithm>
using namespace std;
const int N=2010,mod=1e9+7;
int c[N][N];
void init()
{
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<=i;j++)
        {
            if(!j)c[i][j]=1;
            else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
        }
    }
}
int main()
{
    init();
    int n;
    cin>>n;
    while(n--)
    {
        int a,b;
        cin>>a>>b;
        cout<<c[a][b]<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 3. 完全背包问题

Fancy_z
1天前
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;

int f[N][N];
int v[N],w[N];
int main()
{
    int n.m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];

    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            f[i][j]=f[i][j];
            if(j>=v[i])
            {
                f[i][j]=max(f[i-1][j],f[i][j-v[i]+w[i]);
            }
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}


活动打卡代码 AcWing 2. 01背包问题

Fancy_z
1天前
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;

int f[N][N];
int v[N],w[N];
int main()
{
    int n.m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];

    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            f[i][j]=f[i-1][j];
            if(j>=v[i])
            {
                f[i][j]=max(f[i-1][j],f[i-1][j-v[i]+w[i]);
            }
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}



Fancy_z
1天前
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=110;
int n;
const double eps=1e-6;
double a[N][N];

int gauss()
{
    int c;
    int r;
    for(c=0,r=0;c<n;c++)
    {
        int t=c;
        for(int i=r;i<n;i++)
        {
            if(fabs(a[i][c])>fabs(a[t][c]))
            {
                t=i;
            }
        }


    if(fabs(a[t][c])<eps)continue;

    for(int i=c;i<=n;i++)swap(a[t][i],a[r][i]);
    for(int i=n;i>=c;i--)a[r][i]/=a[r][c];

    for(int i=r+1;i<n;i++)
    {
        if(fabs(a[i][c])>eps)
        {
            for(int j=n;j>=c;j--)
            a[i][j]-=a[r][j]*a[i][c];
        }
    }
    r++;
    }

    if(r<n)
    {
        for(for(int i=r;i<n;i++)
        {
        if(fabs(a[i][n])>eps)
        {
            return 2;
        }
        return 1;

    }
    for(int i=n-1;i>=0;i--)
    {
        for(int j=i+1;j<n;j++)
        a[i][n]-=a[i][j]*a[j][n];
    }
    return 0;
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n+1;j++)
        {
            cin>>a[i][j];
        }
    }
    int t=gauss();
    if(t==0)
    {
        for(int i=0;i<n;i++)printf("%d.2lf\n",a[i][n]);
    }
    else if(t==1)puts("Infinite group solutions");
    else puts("No solution");
    return 0;
}



Fancy_z
1天前

题目描述

完全背包问题(每个物品可以选多次)

选法:
(1)从1~i个物品中选,不选第i个物品,f[i-1][j]
(2)从1~i个物品中选,可选多个第i个物品,
f[i-1][j-v],f[i-1][j-2v]…

所以f[i][j]=max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2v]+2w…)
用j-v代替上面的j得
f[i][j-v]=max(f[i-1][j-2v]+w,f[i-1][j-3v]+w…)总式子比上面少w

所以f[i][j]=max(f[i-1][j],f[i],[j-v]+w)


算法1

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int V[N],W[N];
int f[N][N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>V[i]>>W[i];

    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            f[i][j]=f[i-1][j];  //从1~i中选,不选第i个物品
            if(j>=V[i])
            {
                f[i][j]=max(f[i-1][j],f[i][j-V[i]]+W[i]);   
            }
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}


算法2

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int V[N],W[N];
int f[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>V[i]>>W[i];

    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            f[j]=f[j];
            if(j>=V[i])
            {
                f[j]=max(f[j],f[j-V[i]]+W[i]);
            }
        }
    }
    cout<<f[m]<<endl;
    return 0;
}




Fancy_z
2天前

题目描述

01背包问题(每个物品只能用一次)

选法共有2^n次

优化方法:DP(在不改变原来代码的基础上进行空间优化,等价变形)

选法:
(1)所有不选第i个物品的方案,各种选法的总价值为f[i-1][j]
(2)所有选择第i个物品的方案,分为其他物品随便选加上物品i的方案,随便选的方案价值为f[i-1][j-v[i]],就规定了j一定大于等于v[i]物品i的价值为w[i],
所以总价值最大要在以上两种方案中选最大的,即max(f[i-1][j],f[i-1][j-vi)


算法1

二维数组f[i][j]表示前i个物品,总体积不超过j,表示的是选法的集合,代表集合当值每一种方案的 总价值

f[N][V]就表示N个物品中,总体积不超过V的总价值最大的方案的集合,因为该集合每个数的值就代表价值,所以在既定的物品数量中,总体积最大的方案的总价值就最大。

所以f[V][N]就是答案

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int f[N][N];
int v[N],w[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];

    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)  //体积由0开始
        {
            //递归求选法
            f[i][j]=f[i-1][j];  //选到第i个物品前,即不选第i个物品
            if(j>=v[i])
            f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]); 
        }
    }
    int res=0;
    for(int i=0;i<=m;i++) res=max(res,f[n][i]);//循环求到最大的
    //但实际上f[n][m]就是最大的
    //cout<<f[n][m]<<endl;
    cout<<res<<endl;
    return 0;
}

算法2

一维数组f[j] 滚动数组

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int f[N];
int v[N],w[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];

    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=v[i];j--) //从大到小,确保j-v[i]没有重复计算过
        {

            f[j]=max(f[j],f[j-v[i]]+w[i]);  
        }
    }

    cout<<f[m]<<endl;
    return 0;
}



Fancy_z
2天前

题目描述

快速幂求逆元

逆元:将除法变成乘法
a/b 同余于 a*x(mod p)

整数x即为b的逆元

由费马定理得:b^(p-1) 同余于1(mod p)
可以转化成:b * b^(p-2)

所以转化成用快速幂求b^(p-2) mod p;

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
int qmi(int a,int k,int p)
{
    int res=1;
    while(k)
    {
        if(k&1)res=(LL)res*a%p;
        k>>=1;
        a=(LL)a*a%p;
    }
    return res;
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a,k,p;
        cin>>a>>p;
        int res=qmi(a,p-2,p);
        if(a%p)cout<<res<<endl;     //若if(res),则没有考虑p-2=0的情况
        else cout<<"impossible"<<endl;
    }
    return 0;
}



Fancy_z
2天前

题目描述

求组合数

C(a,b)=a!/(a-b)!b!
而a/b mod d !=(a mod d)/(b mod d)
所以利用逆元
a/b mod d = (a mod d) * (b的逆元 mod d)

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;

const int N=100010,mod=1e9+7;

int fact[N],infact[N];

int qmi(int a,int k,int p)
{
    int res=1;
    while(k)
    {
        if(k&1)res=(LL)res*a%p;
        a=(LL)a*a%p;
        k>>=1;
    }
    return res;
}
int main()
{
    fact[0]=infact[0]=1;
    for(int i=1;i<N;i++)
    {
        fact[i]=(LL)fact[i-1]*i%mod;   //i的阶乘
        infact[i]=(LL)infact[i-1]*qmi(i,mod-2,mod)%mod;    //i的逆元的阶乘的算法
    }

    int n;
    cin>>n;
    while(n--)
    {
        int a,b;
        cin>>a>>b;
        cout<<(LL)fact[a]*infact[b]%mod*infact[a-b]%mod<<endl;
    }
    return 0;
}




Fancy_z
2天前

题目描述

求组合数

C(a,b)表示从a中选b个数有多少种选法

C(a,b)=C(a-1,b)+C(a-1,b-1) 可看成一个矩阵,所求的位置等于上一行的两个位置相加

所以可以利用递增,从C(0,0)开始赋值

不从计算的角度,从选出次数多少的角度

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;

const int N=2010,mod=1e9+7;
int c[N][N];
void init()
{
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<=i;j++)
        {
            if(!j)c[i][j]=1;   //只有一种选法,边界
            else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;  //防止溢出,%mod
        }
    }
}
int main()
{
    init();
    int n;
    cin>>n;
    while(n--)
    {
        int a,b;
        cin>>a>>b;
        cout<<c[a][b]<<endl;
    }
    return 0;
}





Fancy_z
2天前
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
LL exgcd(LL a, LL b, LL &x, LL &y)
{
    if (!b)
    {
        x = 1; y = 0;
        return a;
    }
    LL d = exgcd(b, a%b, y, x);
    y -= a / b*x;
    return d;
}
int main()
{
    int n;
    cin >> n;
    bool has_answer = true;
    LL a1, m1;
    cin >> a1>>m1;
    LL k1, k2;
    for (int i = 0; i < n - 1; i++)
    {
        LL a2, m2;
        cin >> a2 >> m2;

        LL d;
        d = exgcd(a1, a2, k1, k2);
        if ((m2 - m1) % d)
        {
            has_answer = false;
            break;
        }
        LL t = a2 / d;
        k1 *= (m2 - m1) / d;
        k1 = (k1%t + t) % t;
        m1 = m1 + a1 * k1;
        a1 =abs( a1  / d* a2);

    }
    if (has_answer)
    {
        cout << (m1%a1 + a1) % a1 << endl;
    }
    else cout << "-1" << endl;
    return 0;
}