AtCoder Beginner Contest 328
A - Not Too Hard (atcoder.jp)
#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';
using namespace std;
using i64 = long long;
typedef pair<i64, i64> PII;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
i64 n, x, ans = 0;
cin >> n >> x;
vector<int> a(n);
for (auto &i : a) {
cin >> i;
if (i <= x) ans += i;
}
cout << ans << '\n';
return 0;
}
B - 11/11 (atcoder.jp)
只有月份和日期都是由同一个数字组成时,才可能有重期日
#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';
using namespace std;
using i64 = long long;
typedef pair<i64, i64> PII;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
vector<int> D(N + 1);
i64 ans = 0;
for (int i = 1; i <= N; i ++) {
cin >> D[i];
int op = i % 10;
if (i < 10) {
while (op <= D[i]) {
ans ++;
op = op * 10 + op;
}
} else if (i < 100 && i % 10 == i / 10) {
while (op <= D[i]) {
ans ++;
op = op * 10 + op;
}
}
}
cout << ans << '\n';
return 0;
}
C - Consecutive (atcoder.jp)
前缀和处理一下相邻相同的个数即可
#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';
using namespace std;
using i64 = long long;
typedef pair<i64, i64> PII;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, Q;
string s;
cin >> N >> Q >> s;
vector<int> pre(N + 1);
s = " " + s;
for (int i = 1; i <= N; i ++) {
pre[i] = pre[i - 1];
if (s[i] == s[i - 1])pre[i] ++;
}
while (Q--) {
int l, r;
cin >> l >> r ;
cout << pre[r] - pre[l] << '\n';
}
return 0;
}
D - Take ABC (atcoder.jp)
貌似正解是用栈来做,不过我直接模拟也能过,就是时间卡的有点极限
#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';
using namespace std;
using i64 = long long;
typedef pair<i64, i64> PII;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
int pos = 0;
while (pos < s.size()) {
if (s.substr(pos, 3) == "ABC") {
s.erase(pos, 3);
pos --;
pos = max(pos, 0);
if (s[pos] == 'B') pos --;
pos = max(pos, 0);
continue;
}
pos ++;
}
cout << s << '\n';
return 0;
}
E - Modulo MST (atcoder.jp)
不能直接用克鲁斯卡尔算法去做
因为克鲁斯卡尔是按照固定权值下的计算最小生成树,但是这题是要求取模意义下的最小生成树,按照权值排序得到的结果不一定是最小的,不过观察到这题的范围很小,所以可以直接暴力去做
考虑对\(M\)条边选出\(N-1\)条边出来,多余就\(return\),如果在合并的过程中发现是个环也\(return\),剩下的就是比较了
#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';
using namespace std;
using i64 = long long;
typedef pair<i64, i64> PII;
struct Edge {
i64 v, u, w;
};
constexpr int N = 10;
struct UFS {
int p[N], rank[N], sz; /
void link(int x, int y) {
if (x == y)
return;
if (rank[x] > rank[y])
p[y] = x;
else
p[x] = y;
if (rank[x] == rank[y])
rank[y]++;
}
void init(int n) {
sz = n;
for (int i = 0; i <= sz; i++) {
p[i] = i;
rank[i] = 0;
}
}
int find(int x) {
return x == p[x] ? x : (p[x] = find(p[x]));
}
void unin(int x, int y) {
link(find(x), find(y));
}
void compress() {
for (int i = 0; i < sz; i++)
find(i);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
i64 N, M, K;
cin >> N >> M >> K;
vector<Edge> g(M);
for (int i = 0; i < M; i ++) {
cin >> g[i].u >> g[i].v >> g[i].w;
g[i].w %= K;
}
i64 ans = K;
vector<bool> vis(M);
auto dfs = [&](auto self,int edge,int step){
if(step >= M){
if(edge != N - 1) return ;
UFS ufs;
ufs.init(N);
i64 sum = 0;
for(int i = 0;i < M;i ++){
if(!vis[i]) continue;
int u = ufs.find(g[i].u);
int v = ufs.find(g[i].v);
if(u == v) return ;
ufs.link(u,v);
sum = (sum + g[i].w) % K;
}
ans = min(ans, sum % K);
return ;
}
vis[step] = true;
self(self, edge + 1, step + 1);
vis[step] = false;
self(self, edge, step + 1);
};
dfs(dfs,0,0);
cout << ans << '\n';
return 0;
}
- Beginner AtCoder Contest 328beginner atcoder contest 328 328 beginner atcoder contest contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 334 beginner atcoder contest 332 beginner atcoder contest 315