Codeforces Round #301 (Div. 2) -- （A,B,C,D）
來源：程序員人生 發布時間：2015-05-15 08:16:42 閱讀次數：2996次
題目傳送：Codeforces Round #301 (Div. 2)
A. Combination Lock
水題，求最小移動次數，簡單貪心1下便可
AC代碼：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <cctype>
#define LL long long
#define INF 0x7fffffff
using namespace std;
int n;
char s1[1005];
char s2[1005];
int main() {
scanf("%d", &n);
scanf("%s %s", s1, s2);
int ans = 0;
for(int i = 0; i < n; i ++) {
if(s2[i] > s1[i]) {
ans += min(s2[i] - s1[i], s1[i] + 10 - s2[i]);
}
else {
ans += min(s1[i] - s2[i], s2[i] + 10 - s1[i]);
}
}
printf("%d
", ans);
return 0;
}
B. School Marks
也比較簡單，就是有點繁瑣，具體看代碼吧
AC代碼：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <cctype>
#define LL long long
#define INF 0x7fffffff
using namespace std;
int n, k, p, x, y;
int a[1005];
int main() {
scanf("%d %d %d %d %d", &n, &k, &p, &x, &y);
int tot = 0;//記錄當前的總和
int cnt = 0;//記錄當前大于y的數目
for(int i = 0; i < k; i ++) {
scanf("%d", &a[i]);
tot += a[i];
if(a[i] >= y) {
cnt ++;
}
}
int mid = (n + 1) / 2;
int xu;//記錄最少所需要的數
if(k - cnt >= mid) {//當前如果有半數都比y小則輸出⑴
printf("⑴
");
return 0;
}
if(cnt < mid) {//比y大的少于mid的情況
xu = (mid - cnt) * y;
xu += (n - k - (mid - cnt));
if(xu <= x - tot) {
for(int i = 0; i < n - k - (mid - cnt); i ++) {
printf("1 ");
}
for(int i = 0; i < mid - cnt; i ++) {
printf("%d ", y);
}
}
else {
printf("⑴
");
}
}
else { //比y大的大于等于mid的情況
xu = n - k;
if(xu <= x - tot) {
for(int i = 0; i < n - k; i ++) {
printf("1 ");
}
}
else printf("⑴
");
}
return 0;
}
C. Ice Cave
題意：很簡單，就是1個n*m的冰面，有的破碎了，走1次就會陷下去，有的完好的，不過走1次就破碎了，下次走就會陷下去，給你1個出發點和終點，看出發點能否走到終點那里陷下去，注意出發點肯定是破碎的，且終點可能會和出發點相同
思路：首先，特判1下出發點和終點相同的情況，然后bfs1下看出發點能否能走到終點，然后根據終點的情況分類，當終點為破碎的冰時，只要找到路徑即YES，否則NO，當終點為完好的冰時，到了終點后還要走出去再回來，這里注意，只要當前挨著的冰有1塊為'.'（即完好的），則成立，輸出YES，否則輸出NO；只需要預處理1下原來終點挨著的冰塊的'.'的個數cnt便可（cnt>=2就YES，否則NO），然后這里需要特判1下出發點和終點挨著的情況（由于此時只需要cnt>=1便可，這里特別猥瑣）
AC代碼：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <cctype>
#define LL long long
#define INF 0x7fffffff
using namespace std;
struct node {
int x, y;
node(int x,int y) : x(x), y(y) {}
};
int n, m;
int mp[505][505];
int mx[4] = {⑴, 0, 1, 0};
int my[4] = {0, 1, 0, ⑴};
int r1, c1;
int r2, c2;
char s[505];
int bfs() { //bfs找路徑
queue<node> que;
mp[r1][c1] --;
que.push(node(r1, c1));
while(!que.empty()) {
node tmp = que.front();
que.pop();
for(int i = 0; i < 4; i ++) {
int xx = tmp.x + mx[i];
int yy = tmp.y + my[i];
if(xx >= 1 && xx <= n && yy <= m && yy >= 1) {
if(xx == r2 && yy == c2) return 1;
if(mp[xx][yy] == 2) {
mp[xx][yy] --;
que.push(node(xx, yy));
}
}
}
}
return 0;
}
int main() {
scanf("%d %d", &n, &m);
for(int i = 0; i < n; i ++) {
scanf("%s", s);
int len = strlen(s);
for(int j = 0; j < len; j ++) {
if(s[j] == '.') {
mp[i + 1][j + 1] = 2;
}
else {
mp[i + 1][j + 1] = 1;
}
}
}
scanf("%d %d %d %d", &r1, &c1, &r2, &c2);
int cnt = 0;//記錄終點旁邊有幾個'.'
for(int i = 0; i < 4; i ++) {
int xx = r2 + mx[i];
int yy = c2 + my[i];
if(mp[xx][yy] == 2) cnt ++;
}
if(r1 == r2 && c1 == c2) {//特判1下出發點和終點相同的情況
if(cnt >= 1) {
printf("YES
");
}
else printf("NO
");
return 0;
}
int flag = 0;//特判1下出發點和終點相鄰的情況，這里特別坑，感覺坑了好多人
for(int i = 0; i < 4; i ++) {
int xx = r1 + mx[i];
int yy = c1 + my[i];
if(xx == r2 && yy == c2) {
flag = 1;
break;
}
}
if(flag) {
if(mp[r2][c2] == 1) {
printf("YES
");
}
else {
if(cnt >= 1) {
printf("YES
");
}
else printf("NO
");
}
return 0;
}
//出發點和終點不相同且不相鄰的情況
if(mp[r2][c2] == 1) {
if(bfs()) {
printf("YES
");
}
else printf("NO
");
}
else {
if(bfs()) {
if(cnt >= 2) {
printf("YES
");
}
else printf("NO
");
}
else printf("NO
");
}
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[r][s][p]為1，具體看代碼
AC代碼：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <cctype>
#define LL long long
#define INF 0x7fffffff
using namespace std;
int r, s, p;
double dp[105][105][105];
int main() {
cin >> r >> s >> p;
dp[r][s][p] = 1;
for(int i = r; i >= 0; i --) {
for(int j = s; j >= 0; j --) {
for(int k = p; k >= 0; k --) {
if(i == r && j == s && k == p) continue;
double sum = i + j + k + 1; //上1狀態的總數
if(sum <= 1) continue;//全為0的時候就不需要計算了
double t1 = 0, t2 = 0, t3 = 0;
double t = 0;
t1 = 2.0 * dp[i + 1][j][k] * (i + 1) / sum * k / (sum - 1);
//當隨機出現的是相同的人時的幾率，這個幾率不應當算到dp里面
t = (i+1)/sum*i/(sum⑴) + j/sum*(j⑴)/(sum⑴) + k/sum*(k⑴)/(sum⑴);
if(t < 1.0) t1 /= (1.0 - t);//通過比例消掉
t2 = 2.0 * dp[i][j + 1][k] * (j + 1) / sum * i / (sum - 1);
t = i/sum*(i⑴)/(sum⑴) + (j+1)/sum*j/(sum⑴) + k/sum*(k⑴)/(sum⑴);
if(t < 1.0) t2 /= (1.0 - t);
t3 = 2.0 * dp[i][j][k + 1] * (k + 1) / sum * j / (sum - 1);
t = i/sum*(i⑴)/(sum⑴) + j/sum*(j⑴)/(sum⑴) + (k+1)/sum*k/(sum⑴);
if(t < 1.0) t3 /= (1.0 - t);
dp[i][j][k] = t1 + t2 + t3;//統計上1狀態到當前狀態的幾率
}
}
}
double ansr = 0;
double anss = 0;
double ansp = 0;
for(int i = 1; i <= r; i ++) {
ansr += dp[i][0][0];
}
for(int i = 1; i <= s; i ++) {
anss += dp[0][i][0];
}
for(int i = 1; i <= p; i ++) {
ansp += dp[0][0][i];
}
printf("%.12lf %.12lf %.12lf
", ansr, anss, ansp);
return 0;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
