首页 > 代码库 > 模拟测试（vj）
模拟测试（vj）
做这份模拟测试，已经崩溃了，英文看不懂，题意理解错。到结束了只a了第一题，人生陷入了低谷，于是花了一天的时间终于把不会的弄明白了，在这里写一份总结~
T1，简单的模拟，如果打枪打中一支鸟，将这个位置设为0，并向两边扩散，注意这个位置一定要有鸟。
代码~
#include<bits/stdc++.h>using namespace std;int a[30000];int n,m;int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; cin>>m; for(int i=1;i<=m;i++) { int t1,t2; cin>>t1>>t2; if(a[t1]>=t2) { int l=t2-1,r=a[t1]-t2; a[t1-1]+=l,a[t1+1]+=r; a[t1]=0; } } for(int i=1;i<=n;i++) cout<<a[i]<<"\n"; return 0;}T2.dp的思想，我们设dp[i][t][w]表示在i个取完之后总厚度为t，上面的宽度为w，于是记忆化搜索就很好写出来啦（初始化dp为-1，为没有走过）
#include<bits/stdc++.h>#define inf 120390420using namespace std;int w[300],t[300];int n;int f[300][300][300];int dp(int i,int tt,int ww){ if(tt>200||ww>200) return inf; if(i==n+1) return ww<=tt?tt:inf; int &ans=f[i][tt][ww]; if(ans>=0) return ans; return ans=min(dp(i+1,tt+t[i],ww),dp(i+1,tt,ww+w[i]));}int main(){ cin>>n; memset(f,-1,sizeof(f)); for(int i=1;i<=n;i++) cin>>t[i]>>w[i]; cout<<dp(1,0,0)<<endl; return 0; }附带同学的代码，背包的思想：将t看成费用，而w为价值，于是二分+背包就可以出来了，不过他好像没有用二分
#include<bits/stdc++.h>using namespace std;int n;int t[200],w[200];int f[200];int sum=0,s=0;int solve(int x){ f[0]=0; for(int i=1;i<=x;i++) f[i]=-12214019; for(int i=1;i<=n;i++) for(int j=x;j>=t[i];j--) f[j]=max(f[j],f[j-t[i]]+w[i]); return x>=(s-f[x]);}int main(){ cin>>n; for(int i=1;i<=n;i++) { cin>>t[i]>>w[i];sum+=t[i];s+=w[i];} for(int i=1;i<=sum;i++) if(solve(i)) { cout<<i<<endl;break; } return 0;}
T3.就是运用数学的知识，首先我们可以推出夹在两个1-1之间的0的个数是2^（n-1），而可重集合的全排列是等于C(num,a),C(num-a,b)以此类推，于是我们利用乘法原理就可以做出来了。组合数的话用杨辉三角，起点从0开始，这也算小技巧吧，get+，由于数据比较小，不用高精度快速幂，也感觉不错~
#include<bits/stdc++.h>#define LL long long#define mod 1000000007using namespace std;LL n,m;LL b[2000000];LL c[2000][2000];vector<LL> q;vector<LL> v;int Pow(int a,int b){ int ans=1; for(int i=1;i<=b;i++) ans=(ans*a)%mod; return ans%mod;}int main(){ cin>>n>>m; for(int i=0;i<=1000;i++) c[i][0]=1; for(int i=1;i<=1000;i++) for(int j=1;j<=1000;j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod; if(m==0) {cout<<"0\n";return 0;} for(LL i=1;i<=m;i++) cin>>b[i]; b[0]=0; b[m+1]=n+1; sort(b,b+m+2); for(LL i=1;i<=m+1;i++) if(b[i]-b[i-1]>1){ q.push_back(b[i]-b[i-1]-1); if(i!=1&&i!=m+1) v.push_back(b[i]-b[i-1]-1); } LL tot=n-m, ans=1; for(LL i=0;i<q.size();i++) { ans*=c[tot][q[i]],ans%=mod; tot-=q[i]; } for(LL i=0;i<v.size();i++) ans*=Pow(2,v[i]-1),ans%=mod; cout<<ans<<endl; return 0;}
T4.就是模拟，我们可以运用巧妙地办法，只计算在1，n或1，m中的次数，根据奇偶性，其中的碰撞次数应该为m+n-2，于是我们每一次计算的时候判断边界条件就可以了~
#include<bits/stdc++.h>#define inf 12831240#define LL long longusing namespace std;LL n,m;map<LL,LL> book[300000];LL ans=1;LL sx,sy;LL x,y;int main(){ cin>>n>>m;cin>>x>>y; char s[2];cin>>s; if(s[0]==‘D‘) sx=1;else sx=-1; if(s[1]==‘R‘) sy=1;else sy=-1; LL res=n+m-2; if(x==1||y==1||x==n||y==m) book[x][y]=1,res--; LL num=0; while(1) { LL dis=inf; num++; if(num>=1293821){ cout<<"-1";return 0;} if(sx==1) dis=min(dis,n-x);else dis=min(dis,x-1); if(sy==1) dis=min(dis,m-y);else dis=min(dis,y-1); x+=sx*dis,y+=dis*sy,ans+=dis; if(x==1) sx=1;else if(x==n) sx=-1; if(y==1) sy=1;else if(y==m) sy=-1; if(book[x][y]==0) book[x][y]=1,res--; if(res==0) {cout<<ans<<endl;return 0;} } return 0;}T5.是一道树形dp，我们枚举所有的边，然后断掉这条边之后，在剩下的两个联通块中分别找出到各个节点距离之和最小的节点，然后和ans进行比较，比较的时候注意，很多小细节要加以深思，比如说/2,*的部分。我们可以设size[x]表示以x为根节点的子树的大小，f[x]表示x到各个位置的距离，然后根据关系就可以求解了，具体看代码的dfs和find部分~
#include<bits/stdc++.h>#define maxn 124890#define LL long longusing namespace std;struct Edge{LL w,to,next;}e[maxn];LL cnt=1,n;LL ans=1e18;LL head[maxn],f[maxn],sz[maxn];void add(LL u,LL v,LL w){ e[++cnt].to=v; e[cnt].w=w; e[cnt].next=head[u]; head[u]=cnt;}void dfs(LL x,LL fa){ f[x]=0,sz[x]=1; for(LL i=head[x];i;i=e[i].next) { LL j=e[i].to; if(j!=fa) { dfs(j,x); sz[x]+=sz[j],f[x]+=sz[j]*e[i].w+f[j]; } }}LL find(LL x,LL fa,LL &p,LL num){ p=min(p,f[x]);// cout<<x<<" "<<f[x]<<"\n"; for(LL i=head[x];i;i=e[i].next)if(e[i].to!=fa) { f[e[i].to]=f[x]+(num-2*sz[e[i].to])*e[i].w; find(e[i].to,x,p,num); }}int main(){ cin>>n; for(LL i=1;i<=n-1;i++) { LL t1,t2,t3; cin>>t1>>t2>>t3; add(t1,t2,t3); add(t2,t1,t3); } LL i=2; while(i<=cnt) { dfs(e[i].to,e[i^1].to); dfs(e[i^1].to,e[i].to); LL p1=1e18,p2=1e18; find(e[i].to,e[i^1].to,p1,sz[e[i].to]); find(e[i^1].to,e[i].to,p2,sz[e[i^1].to]); LL sum=0; for(LL ii=1;ii<=n;ii++) sum+=f[ii];//表示该节点到其他节点的距离，算2倍 ans=min(ans,sum/2+sz[e[i].to]*sz[e[i^1].to]*e[i].w+p1*sz[e[i^1].to]+p2*sz[e[i].to]); i+=2; } cout<<ans<<endl; return 0;}
模拟测试（vj）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。