B - The Middle Day
难度: ⭐
题目大意
在某颗星球上一年有n个月, 给定每个月的天数, 设一年的总天数是m, 请问第m/2(小数向上取整)天是第几个月的第几天;
解题思路
数据不大, 暴力即可;
神秘代码
#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 = 1e4 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m;
int f[N];
signed main(){
cin >> n;
int a, b;
for (int i = 1; i <= n; i++) {
cin >> f[i];
f[i] += f[i - 1];
}
int mid = (f[n]+1) / 2;
for (int i = 1; i <= n; i++) {
if (f[i] >= mid) {
b = i - 1;
break;
}
}
cout << b + 1 << ' '<<mid - f[b];
return 0;
}
C - Flavors
难度: ⭐⭐
题目大意
给定n个卡片, 每个卡片有两个属性, 点数x和分数y; 我们要从中选出两张卡片, 如果这两张卡片的点数不同, 那么就获得y1+y2; 如果相同则获得y1+y2/2, 其中y1>=y2; 问可以获得的最大分数为多少;
解题思路
对于相同的点数我们可以只存其中最大的两个分数, 把所有点数按照各自的两个分数从大到小排序, 答案就是 取排序后第一个点数的两个分数, 或者取第一个和第二个点数各自最大分数, 取这两种情况的最大值;
神秘代码
#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 = 3e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m;
PII f[N];
signed main(){
cin >> n;
for (int i = 1; i <= n; i++) {
int a, b;
cin >> a >> b;
if (b > f[a].first) {
f[a].second = f[a].first;
f[a].first = b;
}
else if (b > f[a].second) {
f[a].second = b;
}
}
sort(f + 1, f+1 + n, greater<>());
cout << max(f[1].first + f[1].second / 2, f[1].first + f[2].first);
return 0;
}
D - Magical Cookies
难度: ⭐⭐⭐⭐
题目大意
给定一个由小写字母组成字符矩阵, 我们需要一直进行以下操作, 直到无法再操作;
先遍历所有的行, 如果某行剩下的所有字母均为同一种字母并且数量大于1个, 那么我们就可以标记这些字母;
再遍历所有的列, 如果某列剩下的所有字母均为同一种字母并且数量大于1个, 那么我们就可以标记这些字母;
最后我们把所有被标记字母从矩阵中去除;
问最后矩阵还剩下多少个字母;
解题思路
本题确实是没有什么好的算法, 所以只好考虑模拟; 那么我们要遍历所有字母, 并且操作完之后还要重复上述过程, 大致相当于O(n3)的复杂度, 这个是一定会超时的, 所以要考虑优化; 因为当我们删除一行时, 可能会由此出现新的满足条件的列, 所以最外层的n我们是很难优化的, 只能取考虑优化遍历; 我们遍历无非就是想看看这一行/列是否是由同一种字母组成, 那我们可以开一个数组st[i][j], 表示第i行中字母j的数量, 如果该字母的数量等于第i行的长度, 那么就说明是由同一种字母组成, 这样我们就可以把O(n2)变成O(26n);
和st[i][j]相对应的fst[i][j]表示第i列中字母j的数量; rs[i]表示当前第i行的长度为多少, cs[i]表示当前第i列的长度为多少; 首先我们先遍历行i, 如果有满足条件的字母j, 那么就可以让st[i][j]清零, 注意: 当我们把一行的字母j删除后, 那么每一列中字母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 = 2e3 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, res;
char g[N][N];
int st[N][N], fst[N][N];
int rs[N], cs[N];
bool ro[N], co[N];
signed main(){
IOS;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> g[i][j];
st[i][g[i][j] - 'a']++;
fst[j][g[i][j] - 'a']++;
}
}
for (int i = 1; i <= n; i++) rs[i] = m;
for (int j = 1; j <= m; j++) cs[j] = n;
while (1) {
vector<int> rv, cv;
bool qu = false;
for (int i = 1; i <= n; i++) {
if (ro[i]) continue;
for (int j = 0; j < 26; j++) {
if (st[i][j] == rs[i] && st[i][j] >= 2) {
qu = true;
ro[i] = true;
st[i][j] = 0;
rv.push_back(j);
}
}
}
for (int i = 1; i <= m; i++) {
if (co[i]) continue;
for (int j = 0; j< 26; j++) {
if (fst[i][j] == cs[i] && fst[i][j] >= 2) {
qu = true;
co[i] = true;
fst[i][j] = 0;
cv.push_back(j);
}
}
}
for (int x : rv) {
for (int i = 1; i <= m; i++) {
fst[i][x]--;
cs[i]--;
}
}
for (int x : cv) {
for (int i = 1; i <= n; i++) {
st[i][x]--;
rs[i]--;
}
}
if (!qu) {
break;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (!ro[i] && !co[j]) {
res++;
}
}
}
cout << res;
return 0;
}
E - Prerequisites
难度: ⭐⭐⭐
题目大意
给定n本书, 编号为1~n, 并且每本书都有各自的前提书单, 我们需要把第i本书的书单上的书都看完才能去看第i本书, 问我们最少看多少本书才能看图书1; 按照阅读顺序输出书的编号, 不用输出1, 答案不唯一;
解题思路
类似于拓扑序列的思路, 我们可以把第i本书和它前提书单上的书建立一条边; 我们用数组st[i]表示第i本书是否以及被阅读, 然后我们从1开始dfs, 对于第u本书, 我们先遍历它前提清单上的所有书j, 如果j已经被阅读了就跳过, 否则就对j进行dfs; 这样我们就可以遍历完看图书1之前所有需要阅读的书了, 对于其中的每一本书, 我们只要遍历完它的前提书单就可以输出这本书了;
神秘代码
#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, idx;
int C[N];
bool st[N];
vector<int> v;
int h[N], e[N], ne[N];
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u) {
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (st[j]) continue;
dfs(j);
st[j] = true;
}
if (u!=1) cout << u << ' ';
}
signed main(){
cin >> n;
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i++) {
cin >> C[i];
for (int j = 1; j <= C[i]; j++) {
int x;
cin >> x;
add(i, x);
}
}
dfs(1);
return 0;
}
F - Shortcuts
难度: ⭐⭐⭐⭐
- Beginner AtCoder Contest 315 abcbeginner atcoder contest 315 beginner atcoder contest abc contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334