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

题目传送: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;
}

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

波比源码 » Codeforces Round #301 (Div. 2) — (A,B,C,D)

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡