cf 301 div2
来源：程序员人生 发布时间：2015-06-16 08:48:03 阅读次数：2782次
A - Combination Lock
题目大意：给有n个（0⑼）环圈密码锁，数串 s1->s2最少移动次数；
题目分析：
简单摹拟；
代码：
const int N=100007;
char s1[N],s2[N];
int main()
{
int n;
while(scanf("%d",&n)==1)
{
int ans=0;
scanf("%s%s",s1+1,s2+1);
for(int i=1;i<=n;i++)
{
int a=s1[i]-'0';
int b=s2[i]-'0';
if(a>b) swap(a,b);
ans+=min(b-a,a+(9-b)+1);
}
printf("%d
",ans);
}
return 0;
}
B - School Marks
题目大意：n个数，已知其中 k个；已知中位数>=y；且所有数sum<=x；填剩下n-k个数；
题目分析：
由于sum要小于x，所以尽可能填小数。 mid左侧填1，右侧填y；
代码：
vector<int> ans;
int main()
{
int n,k,p,x,y;
while(scanf("%d%d%d%d%d",&n,&k,&p,&x,&y)==5)
{
ans.clear();
int sum=0;
int mi=0;
int flag=0;
for(int i=0;i<k;i++)
{
int v;cin>>v;
if(v>=y) flag++;
if(v<y) mi++;
sum+=v;
}
if(mi>n/2||sum>x){
printf("⑴
");
continue;
}
while(n/2+1-(k-mi)<0&&flag>1){
mi++;
flag--;
}
for(int i=0;i<n/2-mi;i++){
ans.push_back(1);
sum+=1;
}
for(int i=0;i<n/2+1-(k-mi);i++)
{
ans.push_back(y);
sum+=y;
flag=1;
}
if(sum<=x&&flag&&(signed int)ans.size()+k==n){
for(int i=0;i<(signed int)ans.size();i++){
if(!i) printf("%d",ans[i]);
else
printf(" %d",ans[i]);
}
printf("
");
}
else{
printf("⑴
");
}
}
return 0;
}
C - Ice Cave
题目大意：给迷宫，X不能走，' . '走两次，从(r1,c2)--->(r2,c2)要求（r2,c2)走两次；
题目分析：
dfs，cnt记录次数，（好吧，我是用的还标记，’*‘表示已走了1遍）；
代码：
const int N=100007;
char gra[555][555];
int go[4][2]={{0,1},{0,⑴},{⑴,0},{1,0}};
int r1,c1,r2,c2;
int ok;
int n,m;
void dfs(int cx,int cy)
{
int x,y;
if(ok) return;
for(int i=0;i<4;i++)
{
x=cx+go[i][0];
y=cy+go[i][1];
if(1<=x&&x<=n&&1<=y&&y<=m)
{
if(gra[x][y]!='X'){
if(gra[x][y]=='*'){
if(x==r2&&y==c2)
ok=1;
}
else{
gra[x][y]='*';
dfs(x,y);
//gra[x][y]='.';
}
}
}
}
}
int main()
{
while(scanf("%d%d",&n,&m)==2)
{
ok=0;
for(int i=1;i<=n;i++)
scanf("%s",&gra[i][1]);
scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
if(gra[r2][c2]=='X') gra[r2][c2]='*';
dfs(r1,c1);
if(ok) printf("YES
");
else
printf("NO
");
}
return 0;
}
/*
4 6
X...XX
...XX.
.X..X.
.....X
1 6
4 6
*/
D - Bad Luck Island
题目大意：初始3物种：r个石头，s个剪刀，p个布；任意1对碰面的几率是相等的（不斟酌，同种碰面）；求最后只剩下1个物种的几率；
题目分析：
几率知识，假设当前存在（石头，剪刀，布）：（i,j,k)；那末下1步如果挂了石头（i⑴,j,k)，那末几率是 dp[ i ][ j ][ k ] * ( i * k ) /（ i * k + i * j + j * k）；
其它同理；
代码：
const int N=100007;
double dp[110][110][110];
int main()
{
int r,s,p;
while(scanf("%d%d%d",&r,&s,&p)==3)
{
for(int i=0;i<=r;i++){
for(int j=0;j<=s;j++){
for(int k=0;k<=p;k++){
dp[i][j][k]=0.0;
}
}
}
dp[r][s][p]=1.0;
for(int i=r;i>=0;i--){
for(int j=s;j>=0;j--){
for(int k=p;k>=0;k--){
if((i==0&&j==0&&k==0)) continue;
if(((i+1)*k+j*k+(i+1)*j)>0) //保证，这1转移能成立，分母不为0；
dp[i][j][k]+=1.0*(dp[i+1][j][k]*(i+1)*k)/((i+1)*k+j*k+(i+1)*j);
if(((j+1)*i+i*k+(j+1)*k)>0)
dp[i][j][k]+=1.0*(dp[i][j+1][k]*(j+1)*i)/((j+1)*i+i*k+(j+1)*k);
if((i*j+i*(k+1)+j*(k+1))>0)
dp[i][j][k]+=1.0*(dp[i][j][k+1]*(k+1)*j)/(i*j+i*(k+1)+j*(k+1));
//cout<<dp[i][j][k]<<endl;
}
}
}
double a=0.0,b=0.0,c=0.0;
for(int i=1;i<=r;i++) a+=dp[i][0][0];
for(int j=1;j<=s;j++) b+=dp[0][j][0];
for(int k=1;k<=p;k++) c+=dp[0][0][k];
printf("%.12f %.12f %.12f
",a,b,c);
}
return 0;
}
//cf！！！！！！！！什么时候div1！！！
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
