头像

ghostq


访客:4019

离线:9天前


活动打卡代码 AcWing 5. 多重背包问题 II

ghostq
9天前
package main
import"fmt"
var(
    n int
    m int
    v[12010]int
    w[12010]int
    f[12010]int
)
func main(){
    fmt.Scanf("%d%d",&n,&m)
    cnt:=0
    for i:=1;i<n+1;i++{
        a:=0
        b:=0
        s:=0
        fmt.Scanf("%d%d%d",&a,&b,&s)
        k:=1
        for k<=s{
            cnt++
            v[cnt]=a*k
            w[cnt]=b*k
            s-=k
            k*=2
        }
        if s>0{
            cnt++
            v[cnt]=a*s
            w[cnt]=b*s
        }
    }
    n=cnt
    for i:=1;i<n+1;i++{
        for j:=m;j>v[i]-1;j--{
            f[j]=func(a,b int)int{if a>b{return a}else{return b}}(f[j],f[j-v[i]]+w[i])
        }
    }
    fmt.Printf("%d",f[m])
    fmt.Printf("\n")
}


活动打卡代码 AcWing 4. 多重背包问题

ghostq
12天前
//#define LOCAL
#include<bits/stdc++.h>
int n,m,v[110],w[110],s[110],f[110][110];
int main(){
#ifdef LOCAL
    freopen("多重背包问题 I.in","r",stdin);
    freopen("多重背包问题 I.out","w",stdout);
#endif
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::cin>>n>>m;
    for(int i=1;i<=n;i++)std::cin>>v[i]>>w[i]>>s[i];
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
            for(int k=0;k<=s[i]&&k*v[i]<=j;k++)
                f[i][j]=std::max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k);
    std::cout<<f[n][m]<<std::endl;
    return 0;
}


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

ghostq
12天前
//#define LOCAL
#include<bits/stdc++.h>
int n,f[110];
int sg(int x){
    if(f[x]!=-1)return f[x];
    std::unordered_set<int>S;
    for(int i=0;i<x;i++)for(int j=0;j<=i;j++)S.insert(sg(i)^sg(j));
    for(int i=0;;i++)if(!S.count(i))return f[x]=i;
}
int main(){
#ifdef LOCAL
    freopen("拆分-Nim游戏.in","r",stdin);
    freopen("拆分-Nim游戏.out","w",stdout);
#endif
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::cin>>n;
    memset(f,-1,sizeof f);
    int res=0;
    while(n--){
        int x;
        std::cin>>x;
        res^=sg(x);
    }
    if(res)std::cout<<"Yes"<<std::endl;
    else std::cout<<"No"<<std::endl;
    return 0;
}


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

ghostq
14天前
//#define LOCAL
#include<bits/stdc++.h>
int n,m,s[110],f[10010];
int sg(int x){
    if(f[x]!=-1)return f[x];
    std::unordered_set<int>S;
    for(int i=0;i<m;i++){
        int sum=s[i];
        if(x>=sum)S.insert(sg(x-sum));
    }
    for(int i=0;;i++)if(!S.count(i))return f[x]=i;
}
int main(){
#ifdef LOCAL
    freopen("集合-Nim游戏.in","r",stdin);
    freopen("集合-Nim游戏.out","w",stdout);
#endif
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::cin>>m;
    for(int i=0;i<m;i++)std::cin>>s[i];
    std::cin>>n;
    memset(f,-1,sizeof f);
    int res=0;
    for(int i=0;i<n;i++){
        int x;
        std::cin>>x;
        res^=sg(x);
    }
    if(res)std::cout<<"Yes"<<std::endl;
    else std::cout<<"No"<<std::endl;
    return 0;
}


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

ghostq
14天前
package main
import"fmt"
var(
    n int=0
    x int=0
    res int=0
)
func main(){
    fmt.Scanf("%d",&n)
    for i:=1;i<=n;i++{
        fmt.Scanf("%d",&x)
        if i%2!=0{
            res^=x
        }
    }
    if res!=0{
        fmt.Printf("Yes\n")
    }else{
        fmt.Printf("No\n")
    }
}


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

ghostq
20天前
package main
import"fmt"
var(
    n,x,res int
)
func main(){
    fmt.Scanf("%d",&n)
    for n!=0{
        n--
        fmt.Scanf("%d",&x)
        res^=x
    }
    if res!=0{
        fmt.Printf("Yes\n")
    }else{
        fmt.Printf("No\n")
    }
}


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

ghostq
20天前
package main
import"fmt"
var(
    n int=0
    m int=0
    p[30]int
)
func main(){
    fmt.Scanf("%d%d",&n,&m)
    for i:=0;i<m;i++{
        fmt.Scanf("%d",&p[i])
    }
    res:=0
    i:=1
    for i<1<<m{
        t:=1
        cnt:=0
        for j:=0;j<m;j++{
            if i>>j&1!=0{
                cnt++
                if t*p[j]>n{
                    t=-1
                    break
                }
                t*=p[j]
            }
        }
        if t!=-1{
            if cnt%2!=0{
                res+=n/t
            }else{
                res-=n/t
            }
        }
        i+=1
    }
    fmt.Printf("%d",res)
    fmt.Printf("\n")
}



ghostq
20天前

题目描述

给定一个整数$n$和$m$个不同的质数$p1,p2,\cdots,pm$。

请你求出$1$~$n$中能被$p1,p2,\cdots,pm中的至少一个数整除的整数有多少个。

样例

输入样例:
10 2
2 3
输出样例:
7

算法1

(y大神的做法) $O(不详)$

y大神的视频讲解

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>
int n,m,p[30];
int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::cin>>n>>m;
    for(int i=0;i<m;i++)std::cin>>p[i];
    int res=0;
    for(int i=1;i<1<<m;i++){
        int t=1,cnt=0;
        for(int j=0;j<m;j++)
            if(i>>j&1){
                cnt++;
                if((long long)t*p[j]>n){
                    t=-1;
                    break;
                }
                t*=p[j];
            }
        if(t!=-1){
            if(cnt%2)res+=n/t;
            else res-=n/t;
        }
    }
    std::cout<<res<<std::endl;
    return 0;
}

C 代码

#include<stdio.h>
int n,m,p[30];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)scanf("%d",&p[i]);
    int res=0;
    for(int i=1;i<1<<m;i++){
        int t=1,cnt=0;
        for(int j=0;j<m;j++)
            if(i>>j&1){
                cnt++;
                if((long long)t*p[j]>n){
                    t=-1;
                    break;
                }
                t*=p[j];
            }
        if(t!=-1){
            if(cnt%2)res+=n/t;
            else res-=n/t;
        }
    }
    printf("%d\n",res);
    return 0;
}

Java 代码

import java.util.*;
public class Main{
    static int n;
    static int m;
    static int[]p=new int[30];
    public static void main(String[]arg){
        Scanner input=new Scanner(System.in);
        n=input.nextInt();
        m=input.nextInt();
        for(int i=0;i<m;i++)p[i]=input.nextInt();
        int res=0;
        for(int i=1;i<1<<m;i++){
            int t=1;
            int cnt=0;
            for(int j=0;j<m;j++)
                if((i>>j&1)!=0){
                    cnt++;
                    if((long)t*p[j]>n){
                        t=-1;
                        break;
                    }
                    t*=p[j];
                }
            if(t!=-1){
                if(cnt%2!=0)res+=n/t;
                else res-=n/t;
            }
        }
        System.out.print(res);
        System.out.print("\n");
    }
}

Python 代码

import java.util.*;
public class Main{
    static int n;
    static int m;
    static int[]p=new int[30];
    public static void main(String[]arg){
        Scanner input=new Scanner(System.in);
        n=input.nextInt();
        m=input.nextInt();
        for(int i=0;i<m;i++)p[i]=input.nextInt();
        int res=0;
        for(int i=1;i<1<<m;i++){
            int t=1;
            int cnt=0;
            for(int j=0;j<m;j++)
                if((i>>j&1)!=0){
                    cnt++;
                    if((long)t*p[j]>n){
                        t=-1;
                        break;
                    }
                    t*=p[j];
                }
            if(t!=-1){
                if(cnt%2!=0)res+=n/t;
                else res-=n/t;
            }
        }
        System.out.print(res);
        System.out.print("\n");
    }
}

Python3 代码

n=0
m=0
p=[0 for i in range(30)]
n,m=map(int,input().split())
p=list(map(int,input().split()))
res=0
i=1
while i<1<<m:
    t=1
    cnt=0
    for j in range(m):
        if i>>j&1!=0:
            cnt+=1
            if t*p[j]>n:
                t=-1
                break
            t*=p[j]
    if t!=-1:
        if cnt%2!=0:
            res+=n//t
        else:
            res-=n//t
    i+=1
print(res,end='')
print('\n',end='')

Go 代码

package main
import"fmt"
var(
    n int=0
    m int=0
    p[30]int
)
func main(){
    fmt.Scanf("%d%d",&n,&m)
    for i:=0;i<m;i++{
        fmt.Scanf("%d",&p[i])
    }
    res:=0
    i:=1
    for i<1<<m{
        t:=1
        cnt:=0
        for j:=0;j<m;j++{
            if i>>j&1!=0{
                cnt++
                if t*p[j]>n{
                    t=-1
                    break
                }
                t*=p[j]
            }
        }
        if t!=-1{
            if cnt%2!=0{
                res+=n/t
            }else{
                res-=n/t
            }
        }
        i+=1
    }
    fmt.Printf("%d",res)
    fmt.Printf("\n")
}



ghostq
1个月前

C++ 代码

#include<bits/stdc++.h>
int qmi(int a,int k,int p){
    int res=1;
    while(k){
        if(k&1)res=(long long)res*a%p;
        a=(long long)a*a%p;
        k>>=1;
    }
    return res;
}
int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    int n;
    std::cin>>n;
    int a=2*n,b=n;
    int res=1;
    for(int i=a;i>a-b;i--)res=(long long)res*i%1000000007;
    for(int i=1;i<=b;i++)res=(long long)res*qmi(i,1000000005,1000000007)%1000000007;
    res=(long long)res*qmi(n+1,1000000005,1000000007)%1000000007;
    std::cout<<res<<std::endl;
    return 0;
}

C 代码

#include<stdio.h>
int qmi(int a,int k,int p){
    int res=1;
    while(k){
        if(k&1)res=(long long)res*a%p;
        a=(long long)a*a%p;
        k>>=1;
    }
    return res;
}
int main(){
    int n;
    scanf("%d",&n);
    int a=2*n,b=n;
    int res=1;
    for(int i=a;i>a-b;i--)res=(long long)res*i%1000000007;
    for(int i=1;i<=b;i++)res=(long long)res*qmi(i,1000000005,1000000007)%1000000007;
    res=(long long)res*qmi(n+1,1000000005,1000000007)%1000000007;
    printf("%d",res);
    return 0;
}

Java 代码

import java.util.*;
public class Main{
    static long qmi(long a,long k,long p){
        long res=1;
        while(k!=0){
            if((k&1)!=0)res=(long)res*a%p;
            a=(long)a*a%p;
            k>>=1;
        }
        return res;
    }
    public static void main(String[]arg){
        Scanner input=new Scanner(System.in);
        long n;
        n=input.nextLong();
        long a=2*n;
        long b=n;
        long res=1;
        for(long i=a;i>a-b;i--)res=(long)res*i%1000000007;
        for(long i=1;i<=b;i++)res=(long)res*qmi(i,1000000005,1000000007)%1000000007;
        res=(long)res*qmi(n+1,1000000005,1000000007)%1000000007;
        System.out.print(res);
    }
}

Python 代码

def qmi(a,k,p):
    res=1
    while k!=0:
        if k&1!=0:
            res=res*a%p
        a=a*a%p
        k>>=1
    return res
n=0
n=int(raw_input())
a,b=2*n,n
res=1
for i in range(a,a-b,-1):
    res=res*i%1000000007
for i in range(1,b+1):
    res=res*qmi(i,1000000005,1000000007)%1000000007
res=res*qmi(n+1,1000000005,1000000007)%1000000007
print res

Python3 代码

def qmi(a,k,p):
    res=1
    while k!=0:
        if k&1!=0:
            res=res*a%p
        a=a*a%p
        k>>=1
    return res
n=0
n=int(input())
a,b=2*n,n
#### Go 代码
res=1
for i in range(a,a-b,-1):
    res=res*i%1000000007
for i in range(1,b+1):
    res=res*qmi(i,1000000005,1000000007)%1000000007
res=res*qmi(n+1,1000000005,1000000007)%1000000007
print(res)

Go 代码

package main
import"fmt"
func qmi(a,k,p int)int{
    res:=1
    for k!=0{
        if k&1!=0{
            res=res*a%p
        }
        a=a*a%p
        k>>=1
    }
    return res
}
func main(){
    var n int
    fmt.Scanf("%d",&n)
    a,b:=2*n,n
    res:=1
    for i:=a;i>a-b;i--{
        res=res*i%1000000007
    }
    for i:=1;i<=b;i++{
        res=res*qmi(i,1000000005,1000000007)%1000000007
    }
    res=res*qmi(n+1,1000000005,1000000007)%1000000007
    fmt.Printf("%d",res)
}


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

ghostq
1个月前
package main
import"fmt"
var(
    cnt int
    sum,primes[5010]int
    st[5010]bool
)
func getprimes(n int){
    for i:=2;i<=n;i++{
        if!st[i]{
            primes[cnt]=i;
            cnt++
        }
        for j:=0;primes[j]<=n/i;j++{
            st[primes[j]*i]=true;
            if primes[j]%i==0{
                break
            }
        }
    }
}
func get(n,p int)int{
    res:=0
    for n!=0{
        res+=n/p
        n/=p
    }
    return res
}
func mul(a[]int,b int)[]int{
    c:=[]int{}
    t:=0
    for i:=0;i<len(a);i++{
        t+=a[i]*b
        c=append(c,t%10)
        t/=10
    }
    for t!=0{
        c=append(c,t%10)
        t/=10
    }
    return c
}
func main(){
    a:=0
    b:=0
    fmt.Scanf("%d%d",&a,&b)
    getprimes(a)
    for i:=0;i<cnt;i++{
        p:=primes[i]
        sum[i]=get(a,p)-get(a-b,p)-get(b,p)
    }
    res:=[]int{}
    res=append(res,1)
    for i:=0;i<cnt;i++{
        for j:=0;j<sum[i];j++{
            res=mul(res,primes[i])
        }
    }
    for i:=len(res)-1;i>=0;i--{
        fmt.Printf("%d",res[i])
    }
}