头像

WA声闹彻明




离线:5小时前


最近来访(568)
用户头像
Latrix
用户头像
稚廿
用户头像
藏锋守拙
用户头像
琴岛森林
用户头像
yu_yu
用户头像
sealt
用户头像
MilkloveJh
用户头像
lxkang
用户头像
1332442933
用户头像
-捷
用户头像
trace1729
用户头像
种花家的蒟蒻
用户头像
sweet_tea
用户头像
JesseChan
用户头像
太雪菜
用户头像
WA-TLE
用户头像
不高兴的兽奶
用户头像
Fetoy
用户头像
夜寐
用户头像
eric_f

活动打卡代码 AcWing 1089. 烽火传递

#include<stdio.h>
#include<iostream>
#include<string.h>

using namespace std;

const int N=2e5+10;
int w[N],f[N],q[N];

int main()
{
    f[0]=0;

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

    int hh=0,tt=0;
    for(int i=1;i<=n;i++)
    {
        if(hh<=tt && i-q[hh]>m)hh++;
        f[i]=f[q[hh]]+w[i];
        while(hh<=tt && f[q[tt]]>=f[i])tt--;
        q[++tt]=i;
    }

    int res=1e9;
    for(int i=n;i>=n-m+1;i--)res=min(f[i],res);

    printf("%d\n",res);

    return 0;
}


活动打卡代码 AcWing 135. 最大子序和

注意点

1.答案可能为负数,所以初始值要为负无穷,而不是零

2.序列长度至少为1

3.q队列中最开始不能为空,一定要存入下标零,其对应的前缀和s[0]==0,不然如果最大子序处于最前面的话就会WA

#include<stdio.h>
#include<iostream>

#define ll long long

using namespace std;

const int N=3e5+10;
ll s[N];
int q[N];

int main()
{
    int n,m;
    ll res=-1e10;

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&s[i]);
        res=max(res,s[i]);
        s[i]+=s[i-1];
    }

    int hh=0,tt=0;
    for(int i=1;i<=n;i++)
    {
        if(hh<=tt && i-q[hh]>m)hh++;//超出范围的排除
        if(hh<=tt)res=max(res,s[i]-s[q[hh]]);
        //合法范围内的最大值(必须得非空)
        while(hh<=tt && s[q[tt]]>=s[i])tt--;
        //不够优秀的选择排除
        q[++tt]=i;
    }

    printf("%lld\n",res);
    return 0;
}


活动打卡代码 AcWing 1084. 数字游戏 II

数位DP求助链接
这题之前真的给WA哭了

#include<stdio.h>
#include<iostream>
#include<vector>
#include<string.h>

using namespace std;

const int N=110;
int dp[12][N][10],n;
//dp[i][j][k]:长度为i,modn为j,最高位数字为k的合法方案数

int mod(int x)
{
    //cout<<x<<" "<<x%n<<" "<<x%n+n<<" "<<(x%n+n)%n<<endl;

    return ((x%n)+n)%n;
}

void init()
{
    for(int i=0;i<10;i++)dp[1][i%n][i]++;


    //(j-k)modn+kmodn=(j-k+k)modn=jmodn
    for(int i=2;i<12;i++)
        for(int j=0;j<n;j++)
            for(int k=0;k<10;k++)
                for(int p=0;p<10;p++)
                    dp[i][j][k]+=dp[i-1][mod(j-k)][p];
}

int get(int x)
{
    if(!x)return 1;

    vector<int> num;
    while(x)
    {
        num.push_back(x%10);
        x/=10;
    }

    int res=0;
    int last=0;
    for(int i=num.size()-1;i>=0;i--)
    {
        int u=num[i];
        for(int j=0;j<u;j++)
            res+=dp[i+1][mod(0-last)][j];

        last=mod(last+u);
    }
    if(last==0)res++;

    return res;
}
int main()
{
    int a,b,m;

    while(cin>>a>>b>>n)
    {
        memset(dp,0,sizeof(dp));

        init();//注意因为init()中用到了n,要注意输入n和init的顺序

        cout<<get(b)-get(a-1)<<endl;
    }


    return 0;
}


问题 数位DP

数位DP

题目链接 数字游戏II

错误代码如下,希望路过的大佬帮忙找找问题看

#include<stdio.h>
#include<iostream>
#include<vector>

using namespace std;

const int N=110;
int dp[35][N][10],n;
//dp[i][j][k]:长度为i,modn为j,最高位数字为k的合法方案数

int mod(int x)
{
    //cout<<x<<" "<<x%n<<" "<<x%n+n<<" "<<(x%n+n)%n<<endl;
    if(x>=0)return x%n;
    else return ((x%n)+n)%n;
}

void init()
{
    for(int i=0;i<10;i++)dp[1][i%n][i]++;


    //(j-k)modn+kmodn=(j-k+k)modn=jmodn
    for(int i=2;i<N;i++)
        for(int j=0;j<n;j++)
            for(int k=0;k<10;k++)
                for(int p=0;p<10;p++)
                    dp[i][j][k]+=dp[i-1][mod(j-k)][p];
}

int get(int x)
{
    if(!x)return 1;

    vector<int> num;
    while(x)
    {
        num.push_back(x%10);
        x/=10;
    }

    int res=0;
    int last=0;
    for(int i=num.size()-1;i>=0;i--)
    {
        int u=num[i];
        for(int j=(i==(num.size()-1));j<u;j++)
        {
            res+=dp[i+1][mod(0-last)][j];
        }

        last=mod(last+u);
    }
    if(last==0)res++;

    for(int i=1;i<=num.size()-1;i++)
        for(int j=0;j<=9;j++)
        {
            res+=dp[i][0][j];
        }


    return res;
}
int main()
{
    int a,b,m;

    while(cin>>a>>b>>n)
    {
        m=n;
        init();//注意因为init()中用到了n,要注意输入n和init的顺序
        n=m;
        cout<<get(b)-get(a-1)<<endl;
    }


    return 0;
}

真的离谱啊,不懂为什么init()之后n的值会发生变化,这bug给我搞疯了快



活动打卡代码 AcWing 1085. 不要62

#include<stdio.h>
#include<iostream>
#include<vector>

using namespace std;

const int N=12;
int dp[N][10];//dp[i][j]表示长度为i,且最高位数字为j的合法方案数

void init()
{
    for(int i=0;i<10;i++)dp[1][i]=1;
    dp[1][4]=0;//一位数字的时候,除了4其他方法均合法

    //dp[i][j]=sigma(dp[i-1][k])
    //其中j!=4 && k!=4 && !(j==6 && k==2)
    for(int i=2;i<11;i++)
        for(int j=0;j<10;j++)
            for(int k=0;k<10;k++)
            {
                if(j!=4 && k!=4 && !(j==6 && k==2))
                    dp[i][j]+=dp[i-1][k];
            }
}

int get(int x)
{
    if(!x)return 1;//一定不能忘记判边界条件

    vector<int> num;
    while(x)
    {
        num.push_back(x%10);
        x/=10;
    }

    int last=0,res=0;
    for(int i=num.size()-1;i>=0;i--)
    {
        int u=num[i];

        for(int j=0;j<u;j++)//枚举左边分支的情况
            if(j!=4 && !(last==6 && j==2))
                res+=dp[i+1][j];

        if((last==6 && u==2) || u==4)break;
        last=u;
        //判断右边分支是否合法,不合法则退出
        //否则就进入右边分支

        if(!i)res++;
    }

    return res;
}
int main()
{
    init();

    int l,r;
    while(cin>>l>>r,l||r)
        cout<<get(r)-get(l-1)<<endl;

    return 0;
}


活动打卡代码 AcWing 115. 给树染色

#include<stdio.h>
#include<iostream>
#include<queue>

using namespace std;

const int N=1010;
int n,root,ans;

struct node{
    int sum,father,size;
    double avg;
}nd[N];

int find()//寻找目前为止所有点中值最大的点,返回其下标
{
    float maxx=0;
    int pos=0;
    for(int i=1;i<=n;i++)
        if(i!=root && nd[i].avg>maxx)
        {
            pos=i;
            maxx=nd[i].avg;
        }

    return pos;
}
int main()
{
    cin>>n>>root;
    for(int i=1;i<=n;i++)
    {
        cin>>nd[i].sum;

        ans+=nd[i].sum;
        nd[i].avg=nd[i].sum;
        nd[i].size=1;
    }
    for(int i=1;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        nd[b].father=a;
    }

    for(int i=1;i<n;i++)
    {
        int max_pos=find();//找到当前位置平均值最小的一组
        //该组一定紧随其父之后
        nd[max_pos].avg=-1;
        //此次合并之后,如果最大值下标仍是max_pos是没意义的
        int max_fa=nd[max_pos].father;
        ans+=nd[max_pos].sum*nd[max_fa].size;

        nd[max_fa].sum+=nd[max_pos].sum;
        nd[max_fa].size+=nd[max_pos].size;//将当前点加到父节点当中去
        nd[max_fa].avg=(double)nd[max_fa].sum/nd[max_fa].size;

        for(int i=1;i<=n;i++)//认祖归宗
            if(nd[i].father==max_pos)
                nd[i].father=max_fa;
    }

    cout<<ans;
    return 0;
}


活动打卡代码 AcWing 111. 畜栏预定

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<queue>


using namespace std;

const int N=50010;
struct node{
    int l,r,x;
    bool operator < (const node t) const{
        return l<t.l;
    }
}Range[N];
typedef pair<int,int> PII;
int pos[N];

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>Range[i].l>>Range[i].r,Range[i].x=i;
    sort(Range+1,Range+1+n);

    priority_queue<PII,vector<PII>,greater<PII> > q;
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(!q.empty() && q.top().first<Range[i].l)
        {
            pos[Range[i].x]=q.top().second;
            q.pop();
        }
        else pos[Range[i].x]=++cnt;

        PII tmp;
        tmp={Range[i].r,pos[Range[i].x]};
        q.push(tmp);
    }

    cout<<q.size()<<endl;
    for(int i=1;i<=n;i++)cout<<pos[i]<<endl;

    return 0;
}


活动打卡代码 AcWing 110. 防晒

#include<stdio.h>
#include<iostream>
#include<algorithm>

using namespace std;

int c,ll;
const int N=2550;
struct node{
    int minx,maxx;
    bool operator <(const node t)const{
        return minx>t.minx;
    }
}cow[N];
struct nodes{
    int spf,num;
    bool operator <(const nodes t)const{
        return spf<t.spf;
    }
}cover[N];

int find(int x)//二分查找最后一个小于等于x的cover[i].spf的下标i
{
    int l=1,r=ll;
    while(l<r)
    {
        int mid=(l+r+1)>>1;
        if(cover[mid].spf<=x)l=mid;
        else r=mid-1;
    }

    return l;
}
int main()
{
    cin>>c>>ll;
    for(int i=1;i<=c;i++)
        cin>>cow[i].minx>>cow[i].maxx;
    for(int i=1;i<=ll;i++)
        cin>>cover[i].spf>>cover[i].num;

    sort(cow+1,cow+1+c);
    sort(cover+1,cover+1+ll);

    int res=0;
    for(int i=1;i<=c;i++)
    {
        int last=find(cow[i].maxx);
        while(cover[last].spf>=cow[i].minx && cover[last].num==0)
            last--;
        if(cover[last].spf>=cow[i].minx)
        {
            cover[last].num--;
            res++;
        }
    }

    cout<<res<<endl;

    return 0;
}


活动打卡代码 AcWing 1082. 数字游戏

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<vector>

using namespace std;

const int N=35;
int dp[N][10];//dp[i][j]表示最左端是j,长度为i的数字情况数
void init()
{
    for(int i=0;i<=9;i++)dp[1][i]=1;

    for(int i=1;i<N;i++)
    {
        for(int j=0;j<=9;j++)
        {
            for(int k=j;k<=9;k++)
                dp[i][j]+=dp[i-1][k];
            //cout<<dp[i][j]<<" ";
        }
        //puts("");
    }


    //dp[i][j]=dp[i-1][k] --> k>=j
}

int get(int x)
{
    if(x==0)return 1;

    vector<int> nums;

    while(x)
    {
        nums.push_back(x%10);
        x/=10;
    }

    int res=0,last=0;
    for(int i=nums.size()-1;i>=0;i--)
    {
        int u=nums[i];

        if(u>=last)//存在合法情况
        {
            for(int j=last;j<u;j++)//左侧分支的情况
                res+=dp[i+1][j];
            last=u;//右侧分支
        }
        else break;

        if(i==0)res++;
    }

    return res;
}
int main()
{
    init();

    int a,b;

    while(cin>>a>>b)
        cout<<get(b)-get(a-1)<<endl;

    return 0;
}


活动打卡代码 AcWing 1081. 度的数量

#include<stdio.h>
#include<iostream>
#include<vector>

using namespace std;

const int N=35;
int C[N][N];
int x,y,k,b;

void init()
{
    for(int i=0;i<=N;i++)
        for(int j=0;j<=i;j++)
            if(j==0)C[i][j]=1;
            else C[i][j]=C[i-1][j-1]+C[i-1][j];
}
int get(int x)
{
    vector<int> num;
    while(x)
    {
        num.push_back(x%b);
        x/=b;
    }

    int res=0,last=0;
    for(int i=num.size()-1;i>=0;i--)
    {
        if(num[i]>0)
        {
            res+=C[i][k-last];

            if(num[i]>1)
            {
                if(k-last-1>=0)res+=C[i][k-last-1];
                break;
            }
            else
            {
                last++;
                if(last>k)break;
            }
        }

        if(i==0 && last==k)res++;
    }

    return res;
}
int main()
{
    init();

    cin>>x>>y>>k>>b;

    cout<<get(y)-get(x-1);

    return 0;
}