第一次打abc正赛
D. Magical Cookies
D - Magical Cookies (atcoder.jp)
题意
给定一个矩阵,矩阵每个点放着一种饼干,饼干种类用小写英文字母表示。进行如下操作:
- 检查当前矩阵的每行每列,如果某行某列的饼干的全部为同一种,就消去该行或该列。且当前满足条件的所有行或列同时进行消去操作。
- 如果操作1后的矩阵出现了新的满足条件的行或列,则重复操作1,否则输出当前剩余的饼干数。
思路
显然,饼干的种类不超过26种,用两个二维数组分别表示每行每列的各个种类的饼干数,在用两个变量表示当前列和行的长度,模拟操作的过程即可。最后输出剩余行或列的乘积。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int h, w;
cin >> h >> w;
vector c(h, vector<char>(w));
for(int i = 0; i < h; i++) {
for(int j = 0; j < w; j++) {
cin >> c[i][j];
}
}
vector dx(h, vector<int>(26));
vector dy(w, vector<int>(26));
for(int i = 0; i < h; i++) {
for(int j = 0; j < w; j++) {
dx[i][c[i][j] - 'a']++;
dy[j][c[i][j] - 'a']++;
}
}
vector<bool> fx(h), fy(w);
int hc = h, wc = w;
for(int _ = 0; _ < h + w; _++) {
vector<pair<int, int>> tx, ty;
for(int i = 0; i < h; i++) {
if(fx[i]) continue;
for(int j = 0; j < 26; j++) {
if(dx[i][j] == wc && wc > 1) {
tx.push_back({i, j});
}
}
}
for(int i = 0; i < w; i++) {
if(fy[i]) continue;
for(int j = 0; j < 26; j++) {
if(dy[i][j] == hc && hc > 1) {
ty.push_back({i, j});
}
}
}
for(auto [x, y] : tx) {
fx[x] = true;
for(int i = 0; i < w; i++) {
dy[i][y]--;
}
hc--;
}
for(auto [x, y] : ty) {
fy[x] = true;
for(int i = 0; i < h; i++) {
dx[i][y]--;
}
wc--;
}
}
cout << wc * hc << "\n";
return 0;
}
E. Prerequisites
E - Prerequisites (atcoder.jp)
题意
有若干本书,看某本书前需要看完其它书,求看书1前需要看的书的顺序。
思路
最初用并查集+拓扑排序做,但是拓扑排序是在一个有向图中进行的,用并查集并不合适。
正确的思路是以书1为根节点遍历一次就可以了,用一个数组记录某本数是否看过,然后按遍历的顺序倒着输出。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<vector<int>> adj(n + 1);
for(int i = 1; i <= n; i++) {
int c;
cin >> c;
while(c--) {
int p;
cin >> p;
adj[i].push_back(p);
}
}
vector<bool> vis(n + 1);
auto dfs = [&](auto self, int x) {
if(vis[x]) {
return;
}
for(int y : adj[x]) {
self(self, y);
vis[y] = true;
}
if(x != 1) {
cout << x << " ";
}
};
dfs(dfs, 1);
return 0;
}
F. Shortcuts
题意
在一个直角坐标系中有若干个点,可以按顺序经过这些点,最后所得的答案为走过的距离总和。也可以选择跳过一些点,但如果跳过了\(c\)个点,最后的答案要加上\(2^{c-1}\),求最小的答案。
思路
显然是dp,设\(a[i]\)为第\(i\)个点,\(dp[i][j]\)为当前走到点\(i\),且跳了\(j\)个点的最小值。则转态转移方程为\(dp[i+p][j+p-1]=min(dp[i+p][j+p-1],dp[i][j]+dist(a[i+p],a[i]))\)
最后取\(dp[n-1]\)中加上\(2^{c-1}\)后的最小值。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
double dist(pair<double, double> &a, pair<double, double> &b) {
double x = (a.first - b.first);
double y = (a.second - b.second);
return sqrt(x * x + y * y);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<pair<double, double>> a(n);
for(int i = 0; i < n; i++) {
cin >> a[i].first >> a[i].second;
}
vector dp(n, vector<double>(30, 1e9));
dp[0][0] = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < 30; j++) {
for(int p = 1; j + p - 1 < 30 && i + p < n; p++) {
dp[i + p][j + p - 1] = min(dp[i + p][j + p - 1], dp[i][j] + dist(a[i + p], a[i]));
}
}
}
double ans = 1e9;
for(int i = 0; i < 30; i++) {
ans = min(ans, dp[n - 1][i] + (i == 0 ? 0 : 1 << (i - 1)));
}
cout << fixed << setprecision(10) << ans << "\n";
return 0;
}
F. Ai + Bj + Ck = X (1 <= i, j, k <= N)
G - Ai + Bj + Ck = X (1 <= i, j, k <= N) (atcoder.jp)
题意
给定\(N,A,B,C,X\),求满足\(1\le i,j,k\le N\)且使\(Ai+Bj+Ck=X\)成立的三元组\((i,j,k)\)个数。
思路
从1到N枚举\(i\),把原式转化为二元丢番图方程。然后根据通解求满足条件的数量。本题卡精度,用int28。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = __int128;
ll exgcd(ll a, ll b, ll &x, ll &y) {
if(b == 0) {
x = 1, y = 0;
return a;
} else {
ll g = exgcd(b, a % b, y, x);
y -= (a / b) * x;
return g;
}
}
template <typename T, typename U>
T ceil(T x, U y) {
if(x > 0 && y > 0 || x < 0 && y < 0) {
return (x + y - 1) / y;
}
return x / y;
}
template <typename T, typename U>
T floor(T x, U y) {
if(x > 0 && y > 0 || x < 0 && y < 0) {
return x / y;
}
return (x - y + 1) / y;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int64_t n, a, b, c, x;
cin >> n >> a >> b >> c >> x;
int64_t ans = 0;
for(ll i = 1; i <= n; i++) {
ll j, k;
ll g = exgcd(b, c, j, k);
if((x - a * i) % g) {
continue;
}
j *= (x - a * i) / g;
k *= (x - a * i) / g;
ll lo = max(ceil(1 - j, c / g), ceil(k - n, b / g));
ll hi = min(floor(n - j, c / g), floor(k - 1, b / g));
if(hi >= lo) {
ans += hi - lo + 1;
}
}
cout << ans << "\n";
return 0;
}
- Beginner AtCoder Contest 315beginner atcoder contest 315 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 beginner atcoder contest 310