本文主要是介绍Codeforces Round #301 (Div. 2) 解题报告(ABCD)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
A Combination Lock
n位0~9密码锁两种状态之间，问最少拨多少次。注意可能越过'0'。直接上代码。。
#include <bits/stdc++.h>
using namespace std; char num1[1010];
char num2[1010];int main(){int n;cin>>n;cin>>num1>>num2;int ans=0;for(int i=0;i<n;i++){int tmp=abs(num1[i]-num2[i]);tmp=min(tmp,num1[i]+10-num2[i]);tmp=min(tmp,num2[i]+10-num1[i]);ans+=tmp;}cout<<ans<<endl;return 0;
} B School Marks
就是一个人去考n门课，总分不能高于x，所有课得分的中位数不能低于y。现在已经考了k门，问能否达成要求。
贪心。因为总分不能太高，如果中位数不够高直接用y来补，补完以后全部考1分。
#include <bits/stdc++.h>
using namespace std; int a[10100];
int b[10100];int main(){int n,k,p,x,y;cin>>n>>k>>p>>x>>y;int cnt=0;for(int i=1;i<=k;i++){cin>>a[i];if(a[i]>=y)cnt++;}int mid=(n+1)/2;int need=mid-cnt;for(int i=k+1;i<=k+need;i++){a[i]=y;}if(need<0)need=0;for(int i=k+need+1;i<=n;i++){a[i]=1;}int sum=0;for(int i=1;i<=n;i++){sum+=a[i];}bool ok=1;if(sum>x)ok=0;for(int i=1;i<=n;i++)b[i]=a[i];sort(b+1,b+n+1);if(b[mid]<y)ok=0;if(ok){for(int i=k+1;i<=n;i++){cout<<a[i]<<" ";}}else{cout<<"-1"<<endl;}return 0;
} C Ice Cave
走冰迷宫。有两种冰，完好的和破损的，完好的走过会变成破损的，破损的走过会掉下去，需要在终点掉下去，问是否可实现。
BFS。搜一条完好的冰路到终点。如果终点是完好的，需要再有一个相邻格子是完好的能够走过去再回到终点。注意起点和终点可能重合，需要特判。
#include <bits/stdc++.h>
using namespace std; char mp[510][510];
bool vis[510][510];
int dirn[]={-1,1,0,0};
int dirm[]={0,0,-1,1};struct pt{int x,y;pt(int x,int y):x(x),y(y){}pt(){}
};int main(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++){scanf("%s",mp[i]+1);}int sn,sm;int tn,tm;cin>>sn>>sm;cin>>tn>>tm;queue<pt> que;que.push(pt(sn,sm));vis[sn][sm]=1;while(!que.empty()){pt cur = que.front(); que.pop();for(int i=0;i<4;i++){int newn=cur.x+dirn[i];int newm=cur.y+dirm[i];if(newn<1)continue;if(newn>n)continue;if(newm<1)continue;if(newm>m)continue;if(!vis[newn][newm]){if(mp[newn][newm]=='.' || (newn==tn&&newm==tm) ){vis[newn][newm]=1;que.push(pt(newn,newm));}}}}//特判重合 if(tn==sn&&tm==sm){int cnt=0;for(int i=0;i<4;i++){if(mp[tn+dirn[i]][tm+dirm[i]]=='.')cnt++;}if(cnt){cout<<"YES"<<endl;return 0;}else{cout<<"NO"<<endl;return 0;}}if(vis[tn][tm]){if(mp[tn][tm]=='X'){cout<<"YES"<<endl;}else{int cnt=0;for(int i=0;i<4;i++){if(mp[tn+dirn[i]][tm+dirm[i]]=='.')cnt++;}if(cnt>1|| ( abs(sn-tn)+abs(sm-tm)==1&&cnt==1 ) ){ //注意特别猥琐的情况 cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}}else{cout<<"NO"<<endl;}return 0;
} D Bad Luck Island
一个岛上，有石头剪刀布三种人，他们会不断随机碰面，输的人就没了。问到最后石头剪刀布剩下的概率分别是多少。
概率dp。dp(i,j,k)表示岛上还有i个石头，j个剪刀，k个布。dp(i,j,k)可以由dp(i+1,j,k)，dp(i,j+1,k)，dp(i,j,k+1)转移而来。例如dp(i+1,j,k)->dp(i,j,k)，发生这种情况肯定是石头和布碰面，石头没了，根据它们的数量算一下概率。要注意一种情况，同种类型的人碰面是不会发生结果的，所以计算的时候要把那部分概率按比例摊给其他情况。具体见代码。
#include <bits/stdc++.h>
using namespace std; double dp[110][110][110];int main(){int a,b,c;cin>>a>>b>>c;dp[a][b][c]=1;for(int i=a;i>=0;i--){for(int j=b;j>=0;j--){for(int k=c;k>=0;k--){if(i==a&&j==b&&k==c)continue;double sum=i+j+k+1;if(sum<=1)continue;double tmp1=0,tmp2=0,tmp3=0;double t=0;tmp1 += dp[i+1][j][k]*k/sum*(i+1)/(sum-1);tmp1 += dp[i+1][j][k]*(i+1)/sum*k/(sum-1);//计算同类人碰面的概率并按比例分摊，下同。 t=(i+1)/sum*(i)/(sum-1)+(j-1)/sum*(j)/(sum-1)+(k-1)/sum*(k)/(sum-1);if(t<1.0)tmp1/=(1.0-t);tmp2 += dp[i][j+1][k]*i/sum*(j+1)/(sum-1);tmp2 += dp[i][j+1][k]*(j+1)/sum*i/(sum-1);t=(i-1)/sum*(i)/(sum-1)+(j+1)/sum*(j)/(sum-1)+(k-1)/sum*(k)/(sum-1);if(t<1.0)tmp2/=(1.0-t);tmp3 += dp[i][j][k+1]*j/sum*(k+1)/(sum-1);tmp3 += dp[i][j][k+1]*(k+1)/sum*j/(sum-1);t=(i-1)/sum*(i)/(sum-1)+(j-1)/sum*(j)/(sum-1)+(k+1)/sum*(k)/(sum-1);if(t<1.0)tmp3/=(1.0-t);dp[i][j][k]=tmp1+tmp2+tmp3;}}}double ansa=0;double ansb=0;double ansc=0;for(int i=1;i<=a;i++){ansa+=dp[i][0][0];}for(int i=1;i<=b;i++){ansb+=dp[0][i][0];}for(int i=1;i<=c;i++){ansc+=dp[0][0][i];}printf("%.10lf %.10lf %.10lf\n",ansa,ansb,ansc);return 0;
}
这篇关于Codeforces Round #301 (Div. 2) 解题报告(ABCD)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
