头像

不念过去_努力向前




离线:11小时前


最近来访(0)

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

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int w[N],f[N][N],v[N];
int main()
{
    int n,V;
    cin>>n>>V;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++)//枚举所有物品
        for(int j=v[0];j<=V;j++)//枚举所有体积
        {
            f[i][j]=f[i-1][j];
            if(j>=v[i])f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
        }
    cout<<f[n][V]<<endl;
    return 0;
}


活动打卡代码 AcWing 894. 拆分-Nim游戏

#include<iostream>
#include<cstring>
#include<unordered_set>
#include<algorithm>
using namespace std;
const int N=110;
int state[N];
int n,res;
int sg(int x)
{
    if(state[x]!=-1)return state[x];
    unordered_set<int>s;
    for(int i=0;i<x;i++)//这里指的是分成两堆这两堆的石子个数可以为零,也就是全部拿走,可以是其他数字,为了防
        for(int j=0;j<=i;j++)//止重复情况出现,先默认第二堆的石子数量小于等于第一堆
            s.insert(sg(i) ^ sg(j));//这里注意我们是保存的该状态可以到达的状态的sg的值。分成两堆之后对用的sg
    for(int i=0;;i++)//值即为sg(i,j)=sg(i)^sg(j),这很关键
        if(!s.count(i))
            return state[x]=i;
}
int main()
{
    memset(state,-1,sizeof state);
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        res ^= sg(x);
    }
    if(res)puts("Yes");
    else puts("No");
    return 0;
}


活动打卡代码 AcWing 892. 台阶-Nim游戏

#include<iostream>
using namespace std;
int main()
{
    int n,res=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        if(i%2)
            res^=x;
    }
    if(res)puts("Yes");
    else puts("No");
    return 0;
}



//解异或方程组过程和高斯消元是相同的,只不过具体得标准有些变化,首先就是要先找到当前列非零行就好,不必找到最大
//的,之后就是把当前行交换到我们执行的行中去,之后仍然是把这一列的数字都变成零,运算就是异或运算,这里注意这个
//操作仅仅是在操作列的这个数字不为零的时候才进行,之后就是要进行回溯,回溯的过程要注意。
#include<iostream>
#include<algorithm>
using namespace std;
const int N=110;
int matrix[N][N],n;
void out()
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<=n;j++)cout<<matrix[i][j]<<' ';
        puts("");
    }
    puts("");
}
int gauss()
{
    int r,c;
    for(r=c=0;c<n;c++)
    {
        int t=r;
        for(int i=r;i<n;i++)
            if(matrix[i][c])
            {
                t=i;
                break;
            }
        if(!matrix[t][c])continue;
        for(int i=c;i<=n;i++)swap(matrix[r][i],matrix[t][i]);
        for(int i=r+1;i<n;i++)
            if(matrix[i][c])
                for(int j=n;j>=c;j--)
                    matrix[i][j]^=matrix[r][j];
        r++;
    }
    if(r<n)
    {
        for(int i=r;i<n;i++)
            if(matrix[i][n])return -1;
        return 2;
    }
    for(int i=n-1;i>=0;i--)
        for(int j=i+1;j<n;j++)
            matrix[i][n]^=matrix[j][n] & matrix[i][j];
    return 1;
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n+1;j++)
            cin>>matrix[i][j];
    int t=gauss();
    if(t==-1)puts("No solution");
    else if(t==2)puts("Multiple sets of solutions");
    else for(int i=0;i<n;i++)cout<<matrix[i][n]<<endl;
    return 0;
}


活动打卡代码 AcWing 893. 集合-Nim游戏

//这里一点不同的就是我们每次可以拿的石子的个数固定的,也就是说当前的局面是可算的,但是呢,游戏结束的状态是受前
//提条件的限制的。为解决这类问题,引入sg函数,sg(x)表示当前状态的一个映射值,如果sg(x)=0的话那么游戏结束,这样
//的话,就可以把游戏结束的条件统一,这样就可以转化为经典的nim游戏问题了,有n个石子堆,对应n个sg(x)的值,我们依
//照nim游戏规律就可以判断先手是什么状态了。sg函数的定义是以石子的个数作为当前的状态值,设当前状态x可以到达的所
//有状态组成集合s,那么sg(x)就为不存在于s中的最小的自然数。在计算sg值得时候使用了记忆化搜索,也就是事先先检查
//这个值是否被计算过。吐过被计算过我们直接返回该状态的值。否则的话就进行计算,之后把该状态保存下来。
#include<iostream>
#include<cstring>
#include<unordered_set>
#include<algorithm>
using namespace std;
const int N=110,M=10010;
int state[M],operations[N];
int n,k;
int sg(int x)
{
    if(state[x]!=-1)return state[x];
    unordered_set<int>s;//表示可以到达的状态sg函数值
    for(int i=0;i<k;i++)
    {
        int t=operations[i];
        if(x>=t)s.insert(sg(x-t));//表示我拿掉这些石子之后状态的映射值
    }
    for(int i=0;;i++)
        if(!s.count(i))//如果当前值一次都没有出现的话。说明找到count(x)返回x出现的次数
            return state[x]=i;
}
int main()
{
    memset(state,-1,sizeof state);
    cin>>k;
    for(int i=0;i<k;i++)cin>>operations[i];
    cin>>n;
    int res=0;
    while(n--)
    {
        int x;
        cin>>x;
        res=res^sg(x);
    }
    if(res)puts("Yes");
    else puts("No");
    return 0;
}


活动打卡代码 AcWing 891. Nim游戏

//通常的Nim游戏的定义是这样的:有若干堆石子,每堆石子的数量都是有限的,合法的移动是“选择一堆石子并拿走若干颗
//(不能不拿)”,如果轮到某个人时所有的石子堆都已经被拿空了,则判负(因为他此刻没有任何合法的移动)。抽象一下
//就是现在由对局的两个人,每人轮流在有限的操作集合中选取一个操作(这个操作由当前局面决定),如果其中一方在某一局
//面下的操作集合为空,那么这方就判负。这类问题判断先手时必胜还是必败,设这个n堆石子的个数与分别是p1...pn如果
//p1 ^ p2 ^ p3 ^...^ pn==0的话,那么先手就为负,否则先手为胜。这里的先手胜指的是先手第一步特定的操作下。
#include<iostream>
using namespace std;
int main()
{
    int n,res=0;
    cin>>n;
    while(n--)
    {
        int x;
        cin>>x;
        res=res^x;
    }
    if(res)puts("Yes");
    else puts("No");
    return 0;
}


活动打卡代码 AcWing 890. 能被整除的数

//因为p是质数,因此用来找到个数很容易,是使用容斥原理即可,使用S1...Sn分别表示P1...Pn整除n的个数,那么能够被其
//中之一整除的个数就是S1...Sn的并集.计算并集的过程使用了容斥原理,通过文氏图可以找到规律,也就是n个集合
//加上偶数个集合的交集,再减去奇数个集合的交集,之后得到的答案即为所求。计算被p整除的数的个数的时候,使
//n/p(使用倍数去想),计算交集的时候即为n/(p1*p1...)。因为我们最后要枚举全部的集合(从文氏图来看除掉重复计算的
//部分)所以可以使用dfs来计算,也就是每次的选的集合个数不同,这样从n个集合中选择k个集合,共有k位,之后使用dfs
//可以实现,但是枚举所有情况,因此使用二进制法,0表示不选当前集合,1表示选当前集合,这样共有2^n-1中方法。我们
//就一个一个方法来枚举,反正就是奇数个就减去,偶数个就加上,交集就是这些对应的n/(p1*p1...),单个集合就是n/p。
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=20;
int primes[N],m,n;
int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++)cin>>primes[i];
    int res=0;
    for(int i=1;i<1<<m;i++)//每次迭代代表多一种选法
    {
        LL pro=1,cnt=0;
        for(int j=0;j<m;j++)//共有m位,每一位对应一个集合j
            if(i>>j & 1)
            {
                cnt++;
                if(pro*primes[j]>n)//这里判断是不是当前的分母已经大于n,要是大于的话整除个数自然就是0,就不必继续
                {
                    pro=-1;
                    break;
                }
                pro*=primes[j];
            }
        if(pro!=-1)//这个条件一定注意
        {
            if(cnt%2)res+=n/pro;
            else res-=n/pro;
        }
    }
    cout<<res;
    return 0;
}



//这也是一种组合数,先把题意转化为n*n的图上的问题,即为从原点出发运动到(n,n),0表示右移,1表示上移,直到运动到
//目标点,题意即为任何一组前缀序列中0的个数都不少于1的个数。对应于图上即为我经过的任意一个点这个点的横坐标都不
//得小于纵坐标的值,真样的话就对应于不得超过主对角线以上,我们以主对角线上方的第一个对角线为研究对象。那么发现
//凡是超过主对角线的任何先都会经过这条对角线。一这条对角线为对称轴那么目标点(n,n)就映射为(n-1,n+1),根据组合数
//要到达(n,n)必须要走2*n步,总的方案数就是C(2n,n),不符合要求的就是C(2n,n-1)那么总方案数就是C(2n,n)-C(2n,n-1)
//根据阶乘样式展开通分化简,就可以得到C(2n,n)/n+1。这个数叫做卡特兰数。
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int p=1e9+7;
LL quick_power(LL a,int b,int p)
{
    LL res=1;
    while(b)
    {
        if(b & 1)res=res*a%p;
        b>>=1;
        a=a*a%p;
    }
    return res;
}
int main()
{
    int n;;
    cin>>n;
    LL res=1;
    int a=2*n,b=n;
    for(int i=a;i>a-b;i--)res=res*i%p;
    for(int i=1;i<=b;i++)res=res*quick_power(i,p-2,p)%p;
    res=res*quick_power(n+1,p-2,p)%p;
    cout<<res;
    return 0;
}


活动打卡代码 AcWing 888. 求组合数 IV

//求精确的组合数,就要从定义出发,也就是说C(a,b)=a*(a-1)*(a-2)*...*(a-b+1)/1*2*3*...*b。优化的方法就是我们先找
//到分子分母的质因子相乘的形式。之后把相同的质因子进行指数化简,一个一个质因子来化简,同时我们在找各种质因子的
//次数时采用一种很舒服的方式,也就是说质数p在一个阶乘中出现的次数,也就是说可以这么来n(p)=x/p+x/p^2+x/p^3...
//一直加到分母大于分子为止。这个是求x的阶乘中p出现的个数。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N=5010;
int primes[N],number,answer_idex[N];
bool is_de[N];
void pr(int n)//线性筛法求质数因子
{
    for(int i=2;i<=n;i++)
    {
        if(!is_de[i])primes[number++]=i;
        is_de[i]=true;
        for(int j=0;primes[j]<=n/i;j++)
        {
            is_de[primes[j]*i]=true;
            if(i%primes[j]==0)break;
        }
    }
}
int get_np(int x,int p)
{
    int res=0;
    while(x)//求质数因子p在x阶乘中出现的次数
    {
        res+=x/p;
        x/=p;
    }
    return res;
}
vector<int>mul(vector<int>& a,int b)//高精度乘法
{
    int t=0;
    vector<int>res;
    for(int i=0;i<a.size();i++)
    {
        t+=a[i]*b;
        res.push_back(t%10);
        t/=10;
    }
    while(t)
    {
        res.push_back(t%10);
        t/=10;
    }
    return res;
}
int main()
{
    int a,b;
    cin>>a>>b;
    pr(a);//求出1-a所有质数,(b<a)
    for(int i=0;i<number;i++)//用来化简相同质因子
    {
        int p=primes[i];
        answer_idex[i]=get_np(a,p)-get_np(b,p)-get_np(a-b,p);
    }
    vector<int>res;
    res.push_back(1);//初始化答案。
    for(int i=0;i<number;i++)
        for(int j=1;j<=answer_idex[i];j++)
            res=mul(res,primes[i]);//每个因子分别乘以对应的次数倍
    for(int i=res.size()-1;i>=0;i--)cout<<res[i];
    return 0;

}


活动打卡代码 AcWing 887. 求组合数 III

//适用于a b均非常大的情况下,使用的方法是lucas定理,这个定理指的是C(a,b)=C(a%p,b%p)*C(a/p,b/p)这里的式子
//仅限于p是质数才成立,我们具体写代码的时候只用为C(a/p,b/p)再次调用lucas定理即可,(a%p,b%p)可以直接算出来。
//这里的迭代停止的条件是a为零,如果a为零的话对应的就是b/p为零,因此我们可以提前结束迭代也就是b<p时、
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
int p;//由于访问次数很多因此设为全局变量
LL quick_power(LL a,LL b)
{
    LL res=1;
    while(b)
    {
        if(b & 1)res=res*a%p;
        b>>=1;
        a=a*a%p;
    }
    return res;
}
LL C(LL a,LL b)
{
    LL res=1;
    for(int i=1,j=a;i<=b;i++,j--)
    {
        res=res*j%p;
        res=res*quick_power(i,p-2)%p;
    }
    return res;
}
LL lucas(LL a,LL b)
{
    if(b<p)return C(a,b);
    return C(a%p,b%p)*lucas(a/p,b/p)%p;
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        LL a,b;
        cin>>a>>b>>p;
        cout<<lucas(a,b)<<endl;
    }
    return 0;
}