头像

粉黛




离线:17小时前


最近来访(18)
用户头像
wyzde18
用户头像
hualahuala
用户头像
像野草一样倔强
用户头像
HH123_


粉黛
2天前

题目链接: 八数码

我遇到了TLE问题。(离谱,输入都没输进去……)
偶对了,大多数都是抄的Y总的,但是我还是没找出bug
Dev-C++无法运行,但AcWing自带的可以

求更正,谢谢!

错误的代码:

#include<iostream>
#include<algorithm>
#include<cstring>
#include<unordered_map>
#include<queue>
#include<vector>

#define x first
#define y second

using namespace std;

typedef pair<int,string> PIS;

string ed="12345678x";
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

int f(string state)
{
    int res=0;
    for(int i=0;i<state.size();i++)
    {
        if(state[i]!='x')
        {
            int t=state[i]-'1';
            res+=abs(i/3-t/3)+abs(i%3-t%3);
        }
    }
    return res;
}

string bfs(string start)
{
    char op[]="urdl";

    unordered_map< string,int >dist;
    unordered_map< string,pair<char,string> >prev;
    priority_queue< PIS,vector<PIS>,greater<PIS> >heap;

    dist[start]=0;
    heap.push({f(start),start});

    while(heap.size()) 
    {
        auto t=heap.top();
        heap.pop();

        string state=t.y;
        if(state==ed)break;//break;

        int x,y;
        for(int i=0;i<9;i++)
            if(state[i]=='x')
            {
                x=i/3,y=i%3;//x=i/3,y=i%3;
                break;
            }
        string source=state;
        for(int i=0;i<4;i++)
        {
            int a=x+dx[i],b=y+dy[i];
            if(a<=0||a>=3||b<0||b>=3)continue;
            state=source;
            swap(state[x*3+y],state[a*3+b]);
            if(dist.count(state)==0||dist[state]>dist[source]+1)
            {
                dist[state]=dist[source]+1;
                prev[state]={op[i],source};
                heap.push({dist[state]+f(state),state});
            }
        }
    }
    string res;
    while(ed!=start)
    {
        res+=prev[ed].x;
        ed=prev[ed].y;
    }
    reverse(res.begin(),res.end());
    return res;
}
int main()
{
    string stat,sep;
    string c;
    while (cin >> c,cout<<c)
    {
        stat += c;
        if (c != "x") sep += c;
    }
    int cnt=0;
    for(int i=0;i<8;i++)
        for(int j=0;j<8;j++)
            if(sep[i]>sep[j])
                cnt++;
    if(cnt&1)
        cout<<"ullddrurdllurdruldr";
    else
        cout<<bfs(stat)<<endl;
}

报错:Time Limit Exceeded



活动打卡代码 AcWing 1018. 最低通行费

粉黛
1个月前
#include<iostream>
using namespace std;
int a[102][102];
long long D[102][102];
const int INF=1e+9;
int main()
{
    int T;
        int n,m;
        cin>>n;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                cin>>a[i][j];
                D[i][j]=INF; 
            }
        D[1][1]=a[1][1];
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                if(i>1)D[i][j]=min(D[i][j],D[i-1][j]+a[i][j]);
                if(j>1)D[i][j]=min(D[i][j],D[i][j-1]+a[i][j]);
            }
        cout<<D[n][n]<<endl;
}


活动打卡代码 AcWing 898. 数字三角形

粉黛
1个月前

倒序DP

#include<iostream>
using namespace std;
int f[600][600];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
        {
            cin>>f[i][j];
        }
    for(int i=n-1;i>=1;i--)
        for(int j=1;j<=i;j++)
        {
            f[i][j]=max(f[i+1][j],f[i+1][j+1])+f[i][j];
        }
    cout<<f[1][1]<<endl;
}


活动打卡代码 AcWing 1021. 货币系统

粉黛
2个月前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
long long f[4000];
long long a[20];
int main()
{
    int n,m;
    cin >> n >> m;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
    }
    f[0]=1;
    for (int i = 1; i <= n; i ++ )
        for (int j = a[i]; j <= m; j ++ )
        {
            f[j]+=f[j-a[i]];
        }
    cout<<f[m]<<endl;
    return 0;
}



粉黛
2个月前
#include<iostream>
using namespace std;
int a[101];
int b[101];
int main()
{
    int K;
    cin>>K;
    while(K--)
    {
        int N;
        int mlen=0;
        cin>>N;
        for(int i=1;i<=N;i++)
        {
            cin>>a[i];
            b[i]=0;
         } 
        int len=0;
        for(int i=1;i<=N;i++)
        {
            int l=0,r=len;
            while(l<r)
            {
                int mid =(l+r+1)>>1;
                if(b[mid]<a[i])l=mid;
                else r=mid-1;
            }
            b[r+1]=a[i];
            len=max(len,r+1);
         } 
        mlen=len;len=0;
        for(int i=1;i<=N;i++)
            b[i]=0;
        for(int i=1;i<=N;i++)
        {
            int l=0;
            int r=len;
            //cout<<r<<" "<<len<<endl;
            while(l<r)
            {
                int mid =(l+r+1)>>1;
                if(b[mid]>a[i])l=mid;
                else r=mid-1;
            }
            b[r+1]=a[i];
            len=max(len,r+1);
         }
        mlen=max(mlen,len);
        //cout<<len<<endl;
        cout<<mlen<<endl;
    }
}



活动打卡代码 AcWing 1015. 摘花生

粉黛
2个月前

基础数字三角形模板

#include<iostream>
using namespace std;
int a[102][102];
long long D[102][102];
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                cin>>a[i][j];
            }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                D[i][j]=max(D[i-1][j],D[i][j-1])+a[i][j];
            }
        long long ans=-1000000;
        for(int i=1;i<=m;i++)ans=max(ans,D[n][i]);
        cout<<ans<<endl;
    }
}



粉黛
2个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

int abaaba[300000];

int main()
{
    int n;
    int mlen=0;
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
        int a;
        cin >> a;
        int l=0,r=mlen;
        while(l<r)
        {
            int mid=(l+r+1)>>1;
            if(abaaba[mid]<a)l=mid;
            else r=mid-1;
        }
        mlen=max(mlen,r+1);
        abaaba[r+1]=a;
    }
    cout<<mlen<<endl;
}



粉黛
3个月前
#include<iostream>
using namespace std;
int Find(int x)
{
    int sum=0;
    while(x)
    {
        x&=x-1;
        sum++;
    }
    return sum;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int a;
        cin>>a;
        cout<<Find(a)<<" ";
    }
 } 


活动打卡代码 AcWing 798. 差分矩阵

粉黛
3个月前
#include<iostream>
using namespace std;
int a[1010][1010];
int b[1010][1010];
int main()
{
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
            b[i][j]+=a[i][j];
            b[i+1][j]-=a[i][j];
            b[i][j+1]-=a[i][j];
            b[i+1][j+1]+=a[i][j];
        }
    for(int i=1;i<=q;i++)
    {
        int x1,x2,y1,y2,c;
        cin>>x1>>y1>>x2>>y2>>c;
        b[x1][y1]+=c;
        b[x1][y2+1]-=c;
        b[x2+1][y1]-=c;
        b[x2+1][y2+1]+=c;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j];
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
}


活动打卡代码 AcWing 790. 数的三次方根

粉黛
3个月前
#include<iostream>
using namespace std;
int main()
{
    double n;
    cin>>n;
    double l=-100000,r=100000;
    while(r-l>=0.0000001)
    {
        double mid=(l+r)/2.0;
        if(mid*mid*mid>=n)r=mid;
        else l=mid;
    }
    printf("%lf",(l+r)/2.0);
}