头像

妙WA种子_


访客:2335

离线:3小时前


活动打卡代码 AcWing 868. 筛质数

妙WA种子_
3小时前
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e6+10;
int prime[N];
int v[N];
int m;

int primes(int n)       //埃氏筛
{
    int cnt=0;
    memset(v,0,sizeof v);
    for(int i=2;i<=n;i++)
    {
        if(v[i]) continue;
        cnt++;
        for(int j=i;j<=n/i;j++) v[i*j]=1;
    }
    return cnt;
}

int prim(int n)     //线性筛法
{
    memset(v,0,sizeof v);   //最小质因子
    m=0;        //质因数的个数
    for(int i=2;i<=n;i++)
    {
        if(v[i]==0) {       //没有被更新就是质数
            v[i]=i,prime[++m]=i;    
        }
        for(int j=1;j<=m;j++){
            if(prime[j]>v[i] || prime[j]>n/i) break;        //如果,i有比prime[j]更小的质因子,或者超出n的范围,则停止循环

            v[i*prime[j]]=prime[j];
        }
    }
    //for(int i=1;i<=m;i++) cout<<prime[i]<<endl;

    return m;
}

int main()
{
    int n;
    cin>>n;
    cout<<prim(n)<<endl;
    return 0;
}






活动打卡代码 AcWing 867. 分解质因数

妙WA种子_
3小时前
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;

const int N=1e4+10;

int p[N], c[N];
int m=0;

void divide(int n) {
    m=0;                //因子个数

    for(int i=2;i<=n/i;i++)
    {
        if(n%i==0) {
            p[++m]=i,c[m]=0;    //p是质数,c是质数数量
            while(n%i==0) n/=i,c[m]++;
        }
    }

    if(n>1)     //如果有大于根号n的质数,需要特判
    {
        p[++m]=n;c[m]=1;
    }

    for(int i=1;i<=m;i++)       //输出
    {
        cout<<p[i]<<" "<<c[i]<<endl;   
    }
}

int main()
{
    int t;
    cin>>t;

    while(t--)
    {
        int x;
        cin>>x;

        divide(x);

        cout<<endl;
    }

    return 0;
}






妙WA种子_
4小时前
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;

int n;
int a;

bool is_prime(int x)
{
    if(x<2) return false;

    for(int i=2;i<=x/i;i++)
    {
        if(x%i==0) return false;
    }
    return true;
}

int main()
{
    cin>>n;

    while(n--)
    {

        scanf("%d",&a);

        if(is_prime(a))
        {
            cout<<"Yes"<<endl;
        }
        else 
        {
            cout<<"No"<<endl;
        }
    }
}







新鲜事 原文

316.减操作 这一道题是不是有special Judge? 样例没过也能A掉。


活动打卡代码 AcWing 316. 减操作

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e2 + 10;
const int d = 10000+1;
int n, t, a[maxn], f[maxn][d*3];
int ans[maxn];

//本题答案不唯一,应该是由special Judge


void dp()
{
    f[1][a[1]+d] = 1;
    f[2][a[1]-a[2]+d] = -1;
    for(int i = 3; i <= n; i++)
        for(int j = -10000+d; j <= 10000+d; j++)
        {
            if(f[i-1][j] != 0)
            {
                f[i][j+a[i]] = 1;
                f[i][j-a[i]] = -1;
            }
        }
}

void print()
{
    int s = t + d;
    for(int i = n; i >= 1; i--)
    {
        ans[i] = f[i][s];
        s -= ans[i]*a[i];
    }
    int cnt = 0;
    for(int i = 2; i <= n; i++)
    {
        if(ans[i] == 1)
        {
            printf("%d\n", i - cnt - 1);
            cnt++;
        }
    }
    for(; cnt < n-1; cnt++) puts("1");
}

int main()
{
    cin >> n >> t;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    dp(); print();
    return 0;
}





题目描述

提供了注释,主要是不懂如何输出多个最优方案。


(线性DP + DFS) 复杂度玄学

C++ 代码

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

//LCS记录多种方案:
//

const int N=100;
int n,m;
char s1[N];
char s2[N];
int f[N][N];
char path[N];


//可以提前预处理来优化
void dfs(int i,int j,int u,int len)
{
    if(u>len)
    {
        puts(path+1);
        return ;
    }

    if(s1[i]==s2[j])
    {
        path[u]=s1[i];
        dfs(i+1,j+1,u+1,len);
    }
    else
    {
        for (int k = 0; k < 26; k ++ )  //枚举是可行的
        {
            int a = 0; // 在s1中,下一个字母k出现在哪里
            int b = 0; // 在s2中,下一个字母k出现在哪里

            for (int x = i; x <= n; x ++ )
                if (s1[x] == 'a' + k)
                {
                    a = x;
                    break;
                }

            for (int x = j; x <= m; x ++ )
                if (s2[x] == 'a' + k)
                {
                    b = x;
                    break;
                }

            if (a && b && f[a][b] == f[i][j])   //虽然可能有两个位置的f值是相同的
                                                //但是我们可以保证,如果是两个位置对分别相等(但并不是最优)的情况下,f的值一定不同,比如样例中的第二位。
            {
                dfs(a, b, u, len);
            }
        }
    }
}

int main()
{
    scanf("%s",s1+1);
    scanf("%s",s2+1);

    n=strlen(s1+1);   
    m=strlen(s2+1);

    for(int i=n;i>=1;i--)
    {
        for(int j=m;j>=1;j--)
        {
            f[i][j]=max(f[i+1][j],f[i][j+1]);

            if(s1[i]==s2[j])
            {
                f[i][j]=max(f[i][j],f[i+1][j+1]+1);
            }
        }
    }

    dfs(1,1,1,f[1][1]);

    //cout<<f[1][1]<<endl;

    return 0;
}



活动打卡代码 AcWing 315. 旅行

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

//LCS记录多种方案:
//

const int N=100;
int n,m;
char s1[N];
char s2[N];
int f[N][N];
char path[N];


//可以提前优化
void dfs(int i,int j,int u,int len)
{
    if(u>len)
    {
        puts(path+1);
        return ;
    }

    if(s1[i]==s2[j])
    {
        path[u]=s1[i];
        dfs(i+1,j+1,u+1,len);
    }
    else
    {
        for (int k = 0; k < 26; k ++ )  //枚举是可行的
        {
            int a = 0; // 在s1中,下一个字母k出现在哪里
            int b = 0; // 在s2中,下一个字母k出现在哪里

            for (int x = i; x <= n; x ++ )
                if (s1[x] == 'a' + k)
                {
                    a = x;
                    break;
                }

            for (int x = j; x <= m; x ++ )
                if (s2[x] == 'a' + k)
                {
                    b = x;
                    break;
                }

            if (a && b && f[a][b] == f[i][j])   //虽然可能有两个位置的f值是相同的
                                                //但是我们可以保证,如果是两个位置对分别相等的情况下,f的值一定不同,比如样例中的第二位。
            {
                dfs(a, b, u, len);
            }
        }
    }
}

int main()
{
    scanf("%s",s1+1);
    scanf("%s",s2+1);

    n=strlen(s1+1);   
    m=strlen(s2+1);

    for(int i=n;i>=1;i--)
    {
        for(int j=m;j>=1;j--)
        {
            f[i][j]=max(f[i+1][j],f[i][j+1]);

            if(s1[i]==s2[j])
            {
                f[i][j]=max(f[i][j],f[i+1][j+1]+1);
            }
        }
    }

    dfs(1,1,1,f[1][1]);

    //cout<<f[1][1]<<endl;

    return 0;
}







活动打卡代码 AcWing 314. 低买

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

const int N=5010,INF=0x3f3f3f3f;

int a[N];
int f[N];
int g[N];
int n;

int main()
{
    scanf("%d",&n);

    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }


    g[0]=1;

    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<i;j++)
        {
            if(!j || a[j]>a[i])
            {
                f[i]=max(f[i],f[j]+1);
            }
        }

        for(int j=1;j<i;j++)
        {
            if(a[j]==a[i])  //如果两种方案的买入日序列不同,但是价格序列相同,则认为这是相同的方案(只计算一次)。
                            //所以,需要把a[i]==a[j]时的方案数清楚,避免重复。
                f[j]=0;
        }

        for(int j=0;j<i;j++)
        {
            if((!j || a[j]>a[i]) && f[i]==f[j]+1)
                g[i]+=g[j];
        }
    }

    int ans=0,cnt=0;

    for(int i=1;i<=n;i++) ans=max(ans,f[i]);
    for(int i=1;i<=n;i++)
        if(f[i]==ans)
        {
            cnt+=g[i];
        }

    cout<<ans<<" "<<cnt<<endl;

    return 0;
}








题目描述


算法1

(暴力枚举) $O(nm^2)$

C++ 代码

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

typedef long long LL;

const int N=110;
int n,m;
int a[N][N];
LL f[N][N];
int p[N][N];    //记录方案:i种花在第j列的时候,i-1种花在哪里。

void get_path(int i,int j)
{
    if(i==0) return ;
    get_path(i-1,p[i][j]);
    printf("%d ",j);
}

int main()
{
    scanf("%d %d",&n,&m);

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }

    memset(f,0xcf,sizeof f);

    f[0][0]=0;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int pos=0;
            for(int k=0;k<j;k++)
            {
                if(f[i-1][k]>f[i-1][pos]) pos=k;
            }
            f[i][j]=f[i-1][pos]+a[i][j];
            p[i][j]=pos;
        }
    }

    LL ans=0;

    for(int i=n;i<=m;i++)
    {
        if(f[n][i]>f[n][ans]) ans=i;
    }

    cout<<f[n][ans]<<endl;

    get_path(n,ans);


    return 0;
}




活动打卡代码 AcWing 313. 花店橱窗

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

typedef long long LL;

const int N=110;
int n,m;
int a[N][N];
LL f[N][N];
int p[N][N];

void get_path(int i,int j)
{
    if(i==0) return ;
    get_path(i-1,p[i][j]);
    printf("%d ",j);
}

int main()
{
    scanf("%d %d",&n,&m);

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }

    memset(f,0xcf,sizeof f);

    f[0][0]=0;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int pos=0;
            for(int k=0;k<j;k++)
            {
                if(f[i-1][k]>f[i-1][pos]) pos=k;
            }
            f[i][j]=f[i-1][pos]+a[i][j];
            p[i][j]=pos;
        }
    }

    LL ans=0;

    for(int i=n;i<=m;i++)
    {
        if(f[n][i]>f[n][ans]) ans=i;
    }

    cout<<f[n][ans]<<endl;

    get_path(n,ans);


    return 0;
}