Codeforces Round #301 (Div. 2) — （A,B,C,D）

A. Combination Lock

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

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;
}

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;
}

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，您必须在下载后24小时内删除！
3. 不得使用于非法商业用途，不得违反国家法律。否则后果自负！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 本站源码并不保证全部能正常使用，仅供有技术基础的人学习研究，请谨慎下载
8. 如遇到加密压缩包，请使用WINRAR解压,如遇到无法解压的请联系管理员！