cf 301 div2
來源：程序員人生 發布時間：2015-06-16 08:48:03 閱讀次數：2928次
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！！！
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
