头像

chinaxjh

none


访客:4377

离线:10小时前



chinaxjh
21天前

题目链接 AcWing 176

用了题解思路,后来甚至和题解从头到尾对了一遍也没有问题,只好求助

错误的代码:

#include<bits/stdc++.h>
using namespace std;
#define fori(i,a,n) for(i=a;i<=n;i++)
#define ford(i,n,a) for(i=n;i>=a;i--)
typedef long long ll;
typedef double db;
typedef long double ld;
typedef unsigned long long ull;
const int N=20003;
const int M=203;
int n,m,i,ss,tt,ww,cc,ee,qq,len,a[N],b[N],las[N],nxt[N],p[N],ans[N][M];
bool vis[N][M];
struct node
{
    int u,f,w;
    node(int x,int y,int z):u(x),f(y),w(z) {}
    friend bool operator < (node a,node b)
    {
        return a.w>b.w;
    }
};
priority_queue <node> q;
void add(int s,int t,int w)
{
    len++;
    a[len]=t;
    b[len]=w;
    nxt[len]=las[s];
    las[s]=len;
}

void ask(int c,int s,int e)
{
    int x,y,i;
    while (!q.empty()) q.pop();
    q.push(node(s,0,0));
    ans[s][0]=0;

    while (!q.empty())
    {
        x=q.top().u;
        y=q.top().f;
        q.pop();
        vis[x][y]=true;
        if (x==e) 
        {
            printf("%d\n",ans[x][y]);
            return;
        }
        if (y<c)
        if (!vis[x][y+1])
        if (ans[x][y]+p[x]<ans[x][y+1]) 
        {
            ans[x][y+1]=ans[x][y]+p[x];
            q.push(node(x,y+1,ans[x][y+1]));
        }
        for (i=las[x];i;i=nxt[i])
        if (y-b[i]>=0)
        {
            if (vis[a[i]][y-b[i]]) continue;
            if (ans[x][y]<ans[a[i]][y-b[i]])
            {
                ans[a[i]][y-b[i]]=ans[x][y];
                q.push(node(a[i],y-b[i],ans[a[i]][y-b[i]]));
            }
        }

    }
    puts("impossible");
}
int main()
{
    cin>>n>>m;
    fori(i,1,n)
    scanf("%d",&p[i]);
    fori(i,1,n)
    {
        scanf("%d%d%d",&ss,&tt,&ww);
        add(ss+1,tt+1,ww);
        add(tt+1,ss+1,ww);
    }
    cin>>qq;
    fori(i,1,qq)
    {
        scanf("%d%d%d",&cc,&ss,&ee);
        memset(ans,0x3f,sizeof(ans));
        memset(vis,false,sizeof(vis));
        ask(cc,ss+1,ee+1);
    }
}

当然,大佬可以直接吐槽我很弱



活动打卡代码 AcWing 165. 小猫爬山

chinaxjh
2个月前
#include<bits/stdc++.h>
using namespace std;
#define fori(i,a,n) for(i=a;i<=n;i++)
#define ford(i,n,a) for(i=n;i>=a;i--)
typedef long long ll;
typedef double db;
typedef long double ld;
typedef unsigned long long ull;
int m,w,i,k,n,ans,c[1000],a[1000];
void search(int k,int num)
{
    int i;
    if (num>=ans) return;
    if (k>n) 
    {
        ans=min(ans,num);
        return;
    }
    fori(i,1,num)
    if (a[i]+c[k]<=w)
    {
        a[i]+=c[k];
        search(k+1,num);
        a[i]-=c[k];
    }
    num++;
    a[num]=c[k];
    search(k+1,num);
}
int main()
{
    cin>>n>>w;
    fori(i,1,n)
        cin>>c[i];
    sort(c+1,c+1+n);
    reverse(c+1,c+1+n);
    ans=10000;
    search(1,0);
    cout<<ans<<endl;
}



chinaxjh
3个月前
#include<bits/stdc++.h>
using namespace std;
#define fori(i,a,n) for(i=a;i<=n;i++)
#define ford(i,n,a) for(i=n;i>=a;i--)
typedef long long ll;
typedef double db;
typedef long double ld;
typedef unsigned long long ull;
const int N=1e6+5;
const ull base=10007;
char s[N];
ull sum1[N],sum2[N],pows[N];
int ans,i,len,testcase;
ull gethashz(int x,int y)
{
    return sum1[y]-sum1[x-1]*pows[y-x+1];
}
ull gethashf(int x,int y)
{
    return sum2[x]-sum2[y+1]*pows[y-x+1];
}
int ji(int x)
{
    int l,r,bo;
    bo=0;
    l=(ans-1)/2+1;
    r=min(x-1,len-x);
    while (l<=r)
    {
        int mid;
        mid=(l+r)/2;
        if (gethashz(x-mid,x-1)==gethashf(x+1,x+mid))
        {
            bo=mid;
            l=mid+1;
        } else r=mid-1;
    }
    return bo*2+1;
}
int ou(int x)
{
    int l,r,bo;
    bo=0;
    l=ans/2+1;
    r=min(x,len-x);
    while (l<=r)
    {
        int mid;
        mid=(l+r)/2;
        if (gethashz(x-mid+1,x)==gethashf(x+1,x+mid))
        {
            bo=mid;
            l=mid+1;
        } else r=mid-1;
    }
    return bo*2;
}
int main()
{
    pows[0]=1;
    fori(i,1,1e6)
    pows[i]=pows[i-1]*base;
    while (++testcase)
    {
        memset(sum1,0,sizeof(sum1));
        memset(sum2,0,sizeof(sum2));
        scanf("%s",s+1);
        ans=1;
        if (s[1]=='E'&&s[2]=='N'&&s[3]=='D') break;
        len=strlen(s+1);
        fori(i,1,len)
        sum1[i]=sum1[i-1]*base+(ull)(s[i]-'a'+1);
        ford(i,len,1)
        sum2[i]=sum2[i+1]*base+(ull)(s[i]-'a'+1);
        fori(i,1,len)
        ans=max(ans,ji(i));
        fori(i,1,len-1)
        if (s[i]=s[i+1]) ans=max(ans,ou(i));
        cout<<"Case "<<testcase<<": "<<ans<<endl;
    }
}


活动打卡代码 AcWing 137. 雪花雪花雪花

chinaxjh
3个月前
#include<bits/stdc++.h>
using namespace std;
#define fori(i,a,n) for(i=a;i<=n;i++)
#define ford(i,n,a) for(i=n;i>=a;i--)
typedef long long ll;
typedef double db;
typedef long double ld;
typedef unsigned long long ull;
const int Mod=1145141;
const int N=100005;
ll bo,n,j,i,t,m,las[Mod+5],a[N][8],b[N],nxt[N],c[8];
bool pd(ll x,ll y)
{
    ll i,j,k,t,boo;
    fori(i,1,6)
    {
        j=i;
        t=1;
        c[t]=a[x][j];
        j++;
        if (j>6) j=1;
        while (j!=i)
        {
            t++;
            c[t]=a[x][j];
            j++;
            if (j>6) j=1;
        }
        boo=true;
        for (j=1;j<=6;j++)
        if (a[y][j]!=c[j]) boo=false;
        if (boo) return true;
    }
    fori(i,1,6)
    {
        j=i;
        t=1;
        c[t]=a[x][j];
        j--;
        if (j==0) j=6;
        while (j!=i)
        {
            t++;
            c[t]=a[x][j];
            j--;
            if (j==0) j=6;
        }
        boo=true;
        for (j=1;j<=6;j++)
        if (a[y][j]!=c[j]) boo=false;
        if (boo) return true;
    }
    return false;
}
ll gethash(ll i)
{
    ll j,ans,jia,cheng;
    cheng=1;
    jia=0;
    fori(j,1,6)
    jia=(jia+a[i][j])%Mod,
    cheng=cheng*a[i][j]%Mod;
    ans=(jia+cheng)%Mod;
}
int main()
{
    cin>>n;
    fori(j,1,6)
        scanf("%lld",&a[1][j]);
    t=gethash(1);
    m++;
    las[t]=m;
    b[m]=1;
    fori(i,2,n)
    {
        fori(j,1,6)
        scanf("%lld",&a[i][j]);
        t=gethash(i);
        if (las[t]==0)
        {
            m++;
            las[t]=m;
            b[m]=i;
        } else {
            bo=true;
            for (j=las[t];j;j=nxt[j])
            if (pd(i,b[j])) 
            {
                puts("Twin snowflakes found.");
                return 0;
            }
            if (bo)
            {
                m++;
                b[m]=i;
                nxt[las[t]]=m;
                las[t]=m;

            }
        }
    }
    puts("No two snowflakes are alike.");
}


活动打卡代码 AcWing 138. 兔子与兔子

chinaxjh
3个月前
#include<bits/stdc++.h>
using namespace std;
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ld;
typedef unsigned long long ull;
const int base=1145141;
const int N=1000000+5;
char s[N];
int x1,x2,yy1,yy2;
ull i,len,n,pows[N],sum[N];
ull gethash(int x,int y)
{
    return (ull)(sum[y]-sum[x-1]*pows[y-x+1]);
}
int main()
{
    cin>>s+1;
    len=strlen(s+1);
    pows[0]=1;
    for (i=1;i<=len;i++)
    pows[i]=pows[i-1]*base;
    for (i=1;i<=len;i++)
    sum[i]=sum[i-1]*base+(ull)(s[i]-'a'+1);
    cin>>n;
    while (n--)
    {
        scanf("%d%d%d%d",&x1,&yy1,&x2,&yy2);
        if (gethash(x1,yy1)==gethash(x2,yy2)) puts("Yes");
        else puts("No");
    }
}



chinaxjh
4个月前
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=32;
int n,i,a[6];
ll f[N][N][N][N][N];
int main()
{
    while (1)
    {
        cin>>n;
        if (n==0) break;
        memset(a,0,sizeof(a));
        for (i=1;i<=n;i++)
        scanf("%d",&a[i]);
        memset(f,0,sizeof(f));
        f[0][0][0][0][0]=1;

        for (int a1=0;a1<=a[1];a1++)
         for (int a2=0;a2<=min(a1,a[2]);a2++)
          for (int a3=0;a3<=min(a2,a[3]);a3++)
           for (int a4=0;a4<=min(a3,a[4]);a4++)
            for (int a5=0;a5<=min(a4,a[5]);a5++)
            {
                if (a1!=a[1])
                  f[a1+1][a2][a3][a4][a5]+=f[a1][a2][a3][a4][a5];
                if (a2!=a[2])
                  f[a1][a2+1][a3][a4][a5]+=f[a1][a2][a3][a4][a5];
                if (a3!=a[3])
                  f[a1][a2][a3+1][a4][a5]+=f[a1][a2][a3][a4][a5];
                if (a4!=a[4])
                  f[a1][a2][a3][a4+1][a5]+=f[a1][a2][a3][a4][a5];
                if (a5!=a[5])
                  f[a1][a2][a3][a4][a5+1]+=f[a1][a2][a3][a4][a5];
            }
        cout<<f[a[1]][a[2]][a[3]][a[4]][a[5]]<<endl;
    }
}




活动打卡代码 AcWing 279. 自然数拆分

chinaxjh
4个月前
#include<bits/stdc++.h>
using namespace std;
const int N=4003;
long long f[N];
int n,i,j;
int main()
{
    cin>>n;
    f[0]=1;
    for (i=1;i<n;i++)
      for (j=i;j<=n;j++)
      f[j]=(f[j-i]+f[j])%2147483648;
    cout<<f[n]<<endl;
}


活动打卡代码 AcWing 273. 分级

chinaxjh
4个月前
#include<bits/stdc++.h>
using namespace std;
const int N=2003;
const int inf=1e9;
int a[N],b[N],f[N][N];
int n,i,j,anss,ans,ansd;
int main()
{
    cin>>n;
    for (i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        b[i]=a[i];
    } 
    sort(b+1,b+1+n);
    for (i=1;i<=n;i++)
    {
        anss=inf;
        for (j=1;j<=n;j++)
        {
            anss=min(anss,f[i-1][j]);
            f[i][j]=anss+abs(a[i]-b[j]);
        }
    }
    ans=inf;
    for (i=1;i<=n;i++) ans=min(ans,f[n][i]);
    reverse(b+1, b+1+n);
    for (i=1;i<=n;i++)
    {
        anss=inf;
        for (j=1;j<=n;j++)
        {
            anss=min(anss,f[i-1][j]);
            f[i][j]=anss+abs(a[i]-b[j]);
        }
    }
    ansd=inf;
    for (i=1;i<=n;i++) ansd=min(ansd,f[n][i]);
    cout<<min(ans,ansd)<<endl;
}


活动打卡代码 AcWing 312. 乌龟棋

chinaxjh
4个月前
#include<bits/stdc++.h>
using namespace std;
int n,m,i,k,j,t,f[50][50][50][50],a[1000],b[1000];
int main()
{
    cin>>n>>m;
    for (i=1;i<=n;i++) scanf("%d",&a[i]);
    for (i=1;i<=m;i++)
    {
        scanf("%d",&k);
        b[k]++;
    }
    for (i=0;i<=b[1];i++)
     for (j=0;j<=b[2];j++)
      for (k=0;k<=b[3];k++)
       for (t=0;t<=b[4];t++)
       {
           if (i!=0) f[i][j][k][t]=max(f[i-1][j][k][t],f[i][j][k][t]);
           if (j!=0) f[i][j][k][t]=max(f[i][j-1][k][t],f[i][j][k][t]);
           if (k!=0) f[i][j][k][t]=max(f[i][j][k-1][t],f[i][j][k][t]);
           if (t!=0) f[i][j][k][t]=max(f[i][j][k][t-1],f[i][j][k][t]);
           f[i][j][k][t]=f[i][j][k][t]+a[1+i+2*j+3*k+4*t];
       }
      cout<<f[b[1]][b[2]][b[3]][b[4]]<<endl;
}



chinaxjh
4个月前
#include<bits/stdc++.h>
using namespace std;
const int N=3005;
int a[N],b[N],f[N][N],i,j,n,m,val,ans;
int main()
{
    cin>>n;
    m=n;
    for (i=1;i<=n;i++) scanf("%d",&a[i]);
    for (i=1;i<=m;i++) scanf("%d",&b[i]); 
    for (i=1;i<=n;i++)
    {
        val=0;
        if (b[0]<a[i]) val=f[i-1][0];
        for (j=1;j<=m;j++)
        {
            if (a[i]==b[j]) f[i][j]=val+1;
            else f[i][j]=f[i-1][j];
            if (b[j]<a[i]) val=max(val,f[i-1][j]);
        }
    }
    for (j=1;j<=m;j++) ans=max(ans,f[n][j]);
    cout<<ans<<endl;
}