五月模拟题（C++）编程部分

没有模板写不出来😂

第三题，迷宫问题，直接bfs 不多说了，上代码 #include<cstdio> #include<cstring> #include<iostream> #include<queue> using namespace std; int n; char mp[1010][1010]; struct node {     int x,y,k; }; int dir[4][2]={1,0,-1,0,0,1,0,-1}; int x,y,ans; queue<node>qu; int vis[1010][1010]; int main() {     scanf("%d",&n);     memset(mp,'#',sizeof(mp));     node temp,temp1;     for(int i=1;i<=n;i++)     {         for(int j=1;j<=n;j++)         {             scanf(" %c",&mp[i][j]);             if(mp[i][j]=='@')             {                 temp.x=i;                 temp.y=j;                 temp.k=0;                 vis[i][j]=1;                 qu.push(temp);             }             if(mp[i][j]=='*')             {                 x=i;                 y=j;             }         }     }     while(!qu.empty())     {         temp=qu.front();         qu.pop();         if(temp.x==x&&temp.y==y)         {             ans=temp.k;             break;         }         for(int i=0;i<4;i++)         {             temp1.x=temp.x+dir[i][0];             temp1.y=temp.y+dir[i][1];             temp1.k=temp.k+1;             if(mp[temp1.x][temp1.y]!='#'&&!vis[temp1.x][temp1.y])             {                 vis[temp1.x][temp1.y]=1;                 qu.push(temp1);             }         }     }     printf("%d\n",ans); }

两个60%，第一个还超时了，第三个没弄出来，，，，菜是原罪

第二题，买票问题 其实就是一个背包，将一张票一张票的购买视为第m+1种物品 有两个地方需要注意一下，一个是这个背包需要至少装满n+1的大小，也就是说要注意状态转移和初始化合法状态的问题，第二个就是，有可能买n+k（k>1）张票花的最少钱数会比买n+1张票的的少 #include<cstdio> #include<cstring> #include<iostream> using namespace std; int n,m,k; int x[1010],y[1010]; long long dp[2010]; int main() {     scanf("%d %d %d",&n,&m,&k);     for(int i=0;i<m;i++)     {         scanf("%d %d",&x[i],&y[i]);     }     x[m]=k;     y[m]=1;     m++;     memset(dp,-1,sizeof(dp));     dp[0]=0;     for(int i=0;i<m;i++)     {         for(int j=y[i];j<=n+1002;j++)         {             if(dp[j-y[i]]!=-1)             {                 if(dp[j]==-1)                 {                     dp[j]=dp[j-y[i]]+x[i];                 }                 else if(dp[j-y[i]]+x[i]<dp[j])                 {                     dp[j]=dp[j-y[i]]+x[i];                 }             }         }     }     int ans=dp[n+1002];     for(int i=n+1002;i>=n+1;i--)     {         if(dp[i]<ans)             ans=dp[i];     }     cout<<ans<<endl; }

大佬 ，我第二题不会，知道是动态规划；麻烦给下思路。第三题是迷宫问题，用回溯，但是我没有调试出来

第一题，统计矩形区域内的星星数量，100000次询问 二维树状数组的模板题 直接上代码 #include<cstdio> int tree[5555][5555]; int n,m; int x1,y1,x2,y2; int lowbit(int x) {     return x&(-x); } void add(int x,int y,int val) {     while(x<=1000)     {         for(int i=y;i<=1000;i+=lowbit(i))         {             tree[x][i]+=val;         }         x+=lowbit(x);     } } int sum(int x,int y) {     int res=0;     while(x>0)     {         for(int i=y;i>0;i-=lowbit(i))         {             res+=tree[x][i];         }         x-=lowbit(x);     }     return res; } int query(int x1,int y1,int x2,int y2) {     return sum(x2,y2)+sum(x1-1,y1-1)-sum(x2,y1-1)-sum(x1-1,y2); } int main() {     scanf("%d",&n);     for(int i=0;i<n;i++)     {         scanf("%d %d",&x1,&y1);         add(x1,y1,1);     }     scanf("%d",&m);     for(int i=0;i<m;i++)     {         scanf("%d %d %d %d",&x1,&y1,&x2,&y2);         printf("%d\n",query(x1,y1,x2,y2));     } }