头像

xuyuyuan


访客:1544

离线:8分钟前


问题 Acwing 163

xuyuyuan
2小时前

题目链接 Acwing 163

我遇到了WA问题。

错误的代码:

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
typedef pair<int,int> pii;
int n,m,a[N],l[N],r[N];
bool st[N];
void move(int p){
    r[l[p]]=r[p];
    l[r[p]]=l[p];
    st[p]=true;
}
int main(){
    cin>>n>>m;
    int k=0;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        if(!x)
            continue;
        if(!k||a[k]*x<0)
            a[++k]=x;
        else
            a[k]+=x;
    }
    n=k;
    priority_queue<pii,vector<pii>,greater<pii>> heap;
    int cnt=0,res=0;
    for(int i=1;i<=n;i++){
        if(a[i]>0){
            cnt++;
            res+=a[i];
        }
    }
    for(int i=1;i<=n;i++){
        l[i]=i-1;
        r[i]=i+1;
        heap.push({abs(a[i]),i});
    }
    while(cnt>m){
        while(st[heap.top().second])
            heap.pop();
        auto t=heap.top();
        heap.pop();
        int v=t.first,p=t.second;
        if(l[p]!=0&&r[p]!=m+1||a[p]>0){
            res-=v;
            cnt--;
            int left=l[p],right=r[p];
            a[p]+=a[left]+a[right];
            heap.push({abs(a[p]),p});
            move(left),move(right);
        }
        else
            move(p);
    }
    cout<<res;
}

编译器报了WA错误

求大佬帮忙检查



问题 AcWing 179

xuyuyuan
14天前

题目链接 AcWing 179

我遇到了WA问题。

错误的代码:

#include<bits/stdc++.h>
using namespace std;
const int N=10;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
char op[5]="udlr";
string s,e="12345678x";
unordered_map<string,int> state;
unordered_map<string,string> pre;
bool check(int x,int y){
    if(x<0||x>=3||y<0||y>=3)
        return false;
    return true;
}
bool bfs(){
    queue<string> q;
    q.push(s),state[s]=0;
    while(!q.empty()){
        string temp=q.front();
        q.pop();
        string now=temp;
        if(now==e)
            return true;
        int k=temp.find('x');
        int x=k/3,y=k%3;
        for(int i=0;i<4;i++){
            int a=x+dx[i],b=y+dy[i];
            if(!check(a,b))
                continue;
            int t=a*3+b;
            swap(temp[k],temp[t]);
            if(!state.count(temp)){
                state[temp]=i;
                pre[temp]=now;
                q.push(temp);
            }
            swap(temp[t],temp[k]);
        }
    }
    return false;
}
int main(){
    for(int i=0;i<9;i++){
        char c;
        cin>>c;
        s+=c;
    }
    if(bfs()){
        vector<char> v;
        string now=e;
        while(now!=s){
            v.push_back(op[state[now]]);
            now=pre[now];
        }
        for(int i=v.size()-1;i>=0;i--)
            cout<<v[i];
    }
    else
        cout<<"unsolvable";
}

编译器报了WA错误

求大佬们帮忙检查




活动打卡代码 AcWing 1116. 马走日

xuyuyuan
14天前
#include<bits/stdc++.h>
using namespace std;
int T,n,m,a,b,ans,vis[20][20];
int vis[20][20];
int dx[8]={2,1,-1,-2,-2,-1,1,2};
int dy[8]={1,2,2,1,-1,-2,-2,-1};
void dfs(int x,int y,int step){
    if(step==n*m){
        ans++;
        return;
    }
    for(int i=0;i<8;i++){
        int kx=x+dx[i];
        int ky=y+dy[i];
        if(kx>=0&&kx<n&&ky>=0&&ky<m&&vis[kx][ky]==0){
            vis[kx][ky]=1;
            dfs(kx,ky,step+1);
            vis[kx][ky]=0;
        }
    }
}
int main(){
    scanf("%d",&T);
    while(T--){
        ans=0;
        memset(vis,0,sizeof(vis));
        scanf("%d %d %d %d",&n,&m,&a,&b);
        vis[a][b]=1;
        dfs(a,b,1);
        printf("%d\n",ans);
    }
    return 0;
}


问题 AcWing 173

xuyuyuan
16天前

题目链接 AcWing 173

我遇到了WA问题。

错误的代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1010,M=1000010;
int n,m,dist[N][N];
char g[N][N];
pair<int,int> q[M];
void bfs(){
    memset(dist,-1,sizeof dist);
    int hh=0,tt=-1;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(g[i][j]=='1'){
                dist[i][j]=0;
                q[++tt]={i,j};
            }
        }
    }
    int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
    while(hh<=tt){
        auto t=q[hh++];
        for(int i=0;i<4;i++){
            int a=t.first+dx[i],b=t.second+dy[i];
            if(a<0||a>=n||b<0||b>=m||dist[a][b]!=-1)
                continue;
            dist[a][b]=dist[t.first][t.second]+1;
            q[++tt]={a,b};
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)
        cin>>g[i];
    bfs();
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++)
            cout<<dist[i][j]<<' ';
        cout<<endl;
    }
}

编译器报了WA错误

求大佬们帮忙检查一下!!!



问题 双向BFS TLE

xuyuyuan
18天前

题目链接 AcWing 190

我遇到了TLE问题。

错误的代码:

#include<bits/stdc++.h>
using namespace std;
const int N=6;
int n;
string s,p,a[N],b[N];
int extance(queue<string> q,unordered_map<string,int> da,unordered_map<string,int> db,string a[N],string b[N]){
    int d=da[q.front()];
    while(da.size()&&da[q.front()]==d){
        auto t=q.front();
        q.pop();
        for(int i=0;i<n;i++){
            for(int j=0;j<t.size();j++){
                if(t.substr(j,a[i].size())==a[i]){
                    string r=t.substr(0,j)+b[i]+t.substr(j,a[i].size());
                    if(db.count(r))
                        return da[t]+db[r]+1;
                    if(da.count(r))
                        continue;
                    da[t]=da[r]+1;
                    q.push(r);
                }
            }
        }
    }
    return 11;
}
int bfs(){
    queue<string> qa,qb;
    unordered_map<string,int> da,db;
    qa.push(s),qb.push(p);
    da[s]=db[p]=0;
    int t,step=0;
    while(qa.size()&&qb.size()){
        if(qa.size()<qb.size())
            t=extance(qa,da,db,a,b);
        else
            t=extance(qb,da,db,b,a);
        if(t<=10)
            return t;
        if(++step==10)
            return -1;
    }
    return -1;
}
int main(){
    cin>>s>>p;
    while(cin>>a[n]>>b[n])
        n++;
    int t=bfs();
    if(t==-1)
        puts("No ANSWER!");
    else
        cout<<t;
}

编译器报了TLE错误

求大佬们帮忙检查一下!!!




xuyuyuan
23天前

题目链接 Acwing 850

我遇到了TLE问题。

错误的代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1.5*1e6;
typedef pair<int,int> pii;
int n,m,h[N],e[N],w[N],ne[N],idx,dist[N];
bool st[N];
void add(int a,int b,int c){
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int dij(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    priority_queue<pii,vector<pii>,greater<pii>> head;
    head.push({0,1});
    while(head.size()){
        auto t=head.top();
        head.pop();
        int ver=t.second,dis=t.first;
        if(st[ver])
            continue;
        for(int i=h[ver];i!=-1;i=ne[i]){
            int j=e[i];
            if(dist[j]>dis+w[i]){
                dist[j]=dis+w[i];
                head.push({dist[j],j});
            }
        }
    }
    if(dist[n]==0x3f3f3f3f)
        return -1;
    return dist[n];
}
int main(){
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    int t=dij();
    printf("%d",t);
}

编译器报了TLE的错误?
求大佬们帮忙检查一下



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

xuyuyuan
29天前
#include<bits/stdc++.h>
using namespace std;
const int N=2010;
int n,m,f[N];
struct point{
    int v,w;
};
int main(){
    vector<point> vv;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        int v,w,s;
        cin>>v>>w>>s;
        for(int k=1;k<=s;k*=2){
            s-=k;
            vv.push_back({v*k,w*k});
        }
        if(s>0)
            vv.push_back({v*s,w*s});
    }
    for(auto p:vv)
        for(int j=m;j>=p.v;j--)
            f[j]=max(f[j],f[j-p.v]+p.w);
    cout<<f[m];
}



xuyuyuan
29天前
#include<bits/stdc++.h>
using namespace std;
string x,y;
int dp[10001][2001];
int n,m;
int main(){
    cin>>n>>m>>x>>y;
    x=' '+x;
    y=' '+y;
    for(int i=1;i<=x.size();i++){
        for(int j=1;j<=y.size();j++){
            if(x[i]==y[j])
                dp[i+1][j+1]=dp[i][j]+1;
            else
                dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
        }
    }
    cout<<dp[x.size()][y.size()];
    return 0;
}



xuyuyuan
29天前
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,a[N],q[N];
int main(){
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    int len=0;
    q[0]=-2e9;
    for(int i=0;i<n;i++){
        int l=0,r=len;
        while(l<r){
            int mid=l+r+1>>1;
            if(q[mid]<a[i])
                l=mid;
            else
                r=mid-1;
        }
        len=max(len,r+1);
        q[r+1]=a[i];
    }
    cout<<len<<endl;
}


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

xuyuyuan
29天前
/*
f[i][j]=f[i-1][j]+a[i][j]
       =f[i-1][j-1]+a[i][j]
*/
#include<bits/stdc++.h>
using namespace std;
const int N=510,INF=0x3f3f3f3f;
int n,f[N][N],a[N][N];
int main(){
    cin>>n;
    memset(f,-INF,sizeof f);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            cin>>a[i][j];
    f[1][1]=a[1][1];
    for(int i=2;i<=n;i++)
        for(int j=1;j<=i;j++)
            f[i][j]=max(f[i-1][j]+a[i][j],f[i-1][j-1]+a[i][j]);
    int res=-INF;
    for(int i=1;i<=n;i++)
        res=max(res,f[n][i]);
    cout<<res;
}