B - Round-Robin Tournament
难度: ⭐
题目大意
给定n个字符串, 每个字符串的长度为n; 如果第i个字符串的第j个字符为'o', 说明i在比赛中赢了j, 如果是'x', 则是j赢了i; 最后按照赢比赛的数量从多到少进行排序;
解题思路
暴力即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 100 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m;
char g[110][110];
PII w[110];
bool cmp(PII a,PII b){
if(a.second==b.second) return a.first<b.first;
else return a.second>b.second;
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++) w[i].first=i;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>g[i][j];
if(j>i){
if(g[i][j]=='o') w[i].second++;
else w[j].second++;
}
}
}
sort(w+1,w+1+n,cmp);
for(int i=1;i<=n;i++) cout<<w[i].first<<' ';
return 0;
}
C - World Tour Finals
难度: ⭐
题目大意
现在有m个题目, 每个题目有对应的分数; 给定n个人这m个题的答题的情况; 对于每个人, 他最少还要答对多少道未答对的题才可以超越其他人的分数;
解题思路
把题目按照分数从大到小排序后暴力即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 100 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, maxn;
PII f[N];
int p[N];
string s[N];
bool cmp(PII a, PII b){
return a.second > b.second;
}
signed main(){
cin >> n >> m;
for(int i = 1; i <= m; i++){
f[i].first = i;
cin >> f[i].second;
}
for(int i = 1; i <= n; i++){
cin >> s[i];
s[i] = ' ' + s[i];
for(int j = 1; j < s[i].size(); j++){
if(s[i][j] == 'o'){
p[i] += f[j].second;
}
}
p[i] += i;
maxn = max(maxn, p[i]);
}
sort(f + 1, f + 1 + m, cmp);
for(int i = 1; i <= n; i++){
int dis = maxn - p[i];
if(dis == 0){
cout << 0 << endl;
continue;
}
int num = 0;
for(int j = 1; j <= m; j++){
if(dis >= 0 && s[i][f[j].first] == 'x'){
num++;
dis -= f[j].second;
}
}
cout << num << endl;
}
return 0;
}
D - Merge Slimes
难度: ⭐⭐
题目大意
现在有n种大小的史莱姆, 给定这n种史莱姆的大小和数量, 相同大小的两个史莱姆可以合成为一个其两倍大小的史莱姆; 请问最后我们可以得到的最少史莱姆数量是多少;
解题思路
怎么说呢, 有点高估这个题了...就是一道很简单的贪心, 把所有史莱姆从小到大排序, 只要能合成就和合成, 用map更新各种史莱姆的数量即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 1e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, num;
int c[N], s[N];
map<int,int> mp;
signed main(){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> s[i] >> c[i];
mp[s[i]] = c[i];
}
for(auto t : mp){
int a = t.first, b = t.second;
int x = b / 2;
b %= 2;
mp[2 * a] += x;
num += b;
}
cout << num;
return 0;
}
E - Playlist
难度: ⭐⭐⭐
题目大意
小莫的歌单里有n首个, 每首歌的时间为Ti, 随机播放这个歌单, 当一首歌结束后会立刻放下一首歌; 问第1首歌在第(m+0.5)秒时还在播放的概率是多少;
解题思路
一个很明显的概率dp, 对于题目的要求, 我们只需要求出在第(m - T1 +1)秒到第m秒中恰好有歌结束的概率和即可; 状态转移类似于背包的思想; 记得最后要对res再做一次取模;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 1e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, res;
int t[N], dp[N];
int qmid(int a, int b){
int res = 1;
while(b){
if(b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
signed main(){
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> t[i];
dp[0] = 1;
for(int i = 0; i <= m; i++){
for(int j = 1; j <= n; j++){
if(t[j] > i) continue;
dp[i] = (dp[i] + dp[i - t[j]] * qmid(n, mod - 2)) % mod;
}
}
for(int i = max(0ll, m - t[1] + 1); i <= m; i++){
res = (res + dp[i]) % mod;
}
res = res * qmid(n, mod - 2) % mod;
cout << res;
return 0;
}
F - Push and Carry
难度: ⭐⭐⭐⭐
题目大意
坐标平面上有人和箱子, 人现在在(xa, ya)，箱子在(xb, yb); 他想把箱子推到(xc,y~c); 他在 (x,y) 时，通过 1 次动作可以：
移动到 (x+1, y), 移动前箱子在 (x+1, y) 时，将被推到 (x+2, y);
移动到 (x-1, y), 移动前箱子在 (x-1, y)时，将被推到 (x-2, y);
移动到 (x, y+1), 移动前箱子在 (x, y+1)时，将被推到 (x, y+2);
移动到 (x, y-1), 移动前箱子在 (x, y-1) 时，将被推到 (x, y-2);
请求出将箱子被推到(xc, yc)所需的最少操作数。
解题思路
一道很麻烦的分类讨论; 想求最少步数, 那么人到箱子和箱子到仓库走的都是曼哈顿距离; 想要箱子到仓库的路程是曼哈顿距离, 那么人就需要到达箱子周围的一个位置, 我们称为出发点; 比如仓库在箱子右边, 那么人就要到达箱子左边; 如果仓库在箱子的右上角, 那么人可以选择到达箱子的左边或下边, 看看哪个最终的路程短就选哪个, 我们用X和Y来表示;
人到达出发点所用的路程就是其曼哈顿距离, 但是也有特殊情况, 就是人在箱子左边, 但是出发点在箱子右边, 这样人就需要多走两步绕过箱子, 上下的情况也一样;
推箱子到仓库的时候, 如果箱子和仓库不在同一条线上, 说明箱子需要中途需要转弯, 转弯也要多走两步
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 2e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, res;
int xa, ya, xb, yb, xc, yc;
int dis(int x1, int y1, int x2, int y2){
int res = abs(x1 - x2) + abs(y1 - y2);
if(xa == x2 && x2 == xb && (ya < yb && y2 > yb || ya > yb && y2 < yb)) res += 2;
if(ya == y2 && y2 == yb && (xa < xb && x2 > xb || xa > xb && x2 < xb)) res += 2;
return res;
}
signed main(){
cin >> xa >> ya >> xb >> yb >> xc >> yc;
int X = 0, Y = 0;
if(xc > xb) X = -1;
if(xc < xb) X = 1;
if(yc > yb) Y = -1;
if(yc < yb) Y = 1;
if(X == 0) cout << dis(xa, ya, xb, yb + Y) + abs(yb - yc);
else if(Y == 0) cout << dis(xa, ya, xb + X, yb) + abs(xb - xc);
else cout << min(dis(xa, ya, xb + X, yb), dis(xa, ya, xb, yb + Y)) + abs(xb - xc) + abs(yb - yc) + 2;
}
- Beginner AtCoder Contest 323 abcbeginner atcoder contest 323 beginner atcoder contest abc 题解323 beginner atcoder contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 334