A - tcdr
#include <bits/stdc++.h>
using namespace std;
int32_t main() {
string s;
cin >> s;
for( auto i : s){
if( i != 'a' and i != 'e' and i != 'i' and i != 'o' and i != 'u' )
cout << i;
}
return 0;
}
B - The Middle Day
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
int n, sum = 0;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i], sum += a[i];
sum = sum / 2 + 1;
for (int i = 1; i <= n; i++) {
if (sum > a[i])sum -= a[i];
else {
cout << i << " " << sum << "\n";
return 0;
}
}
return 0;
}
C - Flavors
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
int n ;
cin >> n;
map<int,vector<int>> a;
for( int f , s ; n ; n -- )
cin >> f >> s, a[f].push_back(s);
vector<int> b;
int res = 0;
for( auto &[k,v] : a ){
sort(v.begin(), v.end() , greater<int>());
b.push_back(v[0]);
if( v.size() >= 2 ) res = max( res , v[0] + v[1] / 2 );
}
sort( b.begin(), b.end() , greater<int>() );
if( b.size() >= 2 ) res = max( res , b[0] + b[1] );
cout << res << "\n";
return 0;
}
D - Magical Cookies
赛时被这道题卡住了很久。
一开始写了一个暴力的代码但是把复杂度估计错了。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
int n, m;
cin >> n >> m;
vector<string> f(n), g;
for (auto &i: f) cin >> i;
for (bool flag; n > 0 and m > 0;) {
flag = true;
set<int> r , c;
for (int i = 0, t; i < n and m >= 2 ; i++) {
t = 1;
for (int j = 1; t and j < m; j++)
if (f[i][j] != f[i][0]) t = 0;
if (t == 0) continue;
r.insert(i);
}
for (int j = 0, t; j < m and n >= 2 ; j++) {
t = 1;
for (int i = 1; t and i < n; i++)
if (f[i][j] != f[0][j]) t = 0;
if (t == 0) continue;
c.insert(j);
}
if( r.empty() and c.empty() ) break;
g = vector<string>();
for( int i = 0 ; i < n ; i ++ ){
if( r.count(i) ) continue;
g.push_back("");
for( int j = 0 ; j < m ; j ++ ){
if( c.count(j) ) continue;
g.back() += f[i][j];
}
}
n = g.size();
if(n) m = g.front().size();
f = g;
}
cout << n * m << "\n";
return 0;
}
认真读题后,发现删除行列只能是整行整列的形式,所以剩下的部分始终是一个矩形。并且我们实际上并不关注行列的字母排列,只需要知道行列中字母的数量。所以我们维护每一行列中字母的数量即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<string> f(n);
for (auto &i: f) cin >> i;
vector<array<int, 26>> R(n), C(m);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
R[i][f[i][j] - 'a']++, C[j][f[i][j] - 'a']++;
for (int x, y; n > 0 and m > 0;) {
vector<pair<int, int>> r, c;
for (int i = 0; i < R.size() and m >= 2 ; i++)
for (int j = 0; j < 26; j++)
if (R[i][j] == m) r.emplace_back(i, j);
for (int i = 0; i < C.size() and n >= 2 ; i++)
for (int j = 0; j < 26; j++)
if (C[i][j] == n) c.emplace_back(i, j);
if( r.empty() and c.empty() ) break;
for( auto [ rr , ch] : r ){
R[rr][ch] = 0;
for( int i = 0 ; i < C.size() ; i ++ )
C[i][ch] = max( 0ll , C[i][ch] - 1);
}
for( auto [cc,ch] : c ){
C[cc][ch] = 0;
for( int i = 0 ; i < R.size() ; i ++ )
R[i][ch] = max(0ll , R[i][ch] - 1);
}
n -= r.size() , m -= c.size();
}
cout << n * m << "\n";
return 0;
}
E - Prerequisites
反向建图,然后从\(1\)开始dfs 求出生成树,生成树上点即为必须要读的前驱。然后统计前驱中入读为零的点即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n;
cin >> n;
vector<vector<int>> e(n + 1), g(n + 1);
vector<int> vis(n + 1), inner(n + 1);
for (int i = 1, x; i <= n; i++) {
cin >> x;
e[i].resize(x);
for (auto &y: e[i]) cin >> y;
}
auto dfs = [&g, &vis, &inner, e](auto &&self, int x) {
if (vis[x]) return;
vis[x] = 1;
for (auto y: e[x]) {
g[y].push_back(x), inner[x]++;
self(self, y);
}
return ;
};
dfs(dfs, 1);
vector<int> res;
queue<int> q;
for (int i = 1; i <= n; i++)
if (vis[i] and inner[i] == 0) q.push(i);
while (!q.empty()) {
auto x = q.front();
q.pop();
res.push_back(x);
for (auto y: g[x]) {
inner[y]--;
if (inner[y] == 0) q.push(y);
}
}
res.pop_back();
for (auto i: res)
cout << i << " ";
return 0;
}
F - Shortcuts
可以知道的是能够跳过的点的数量其实不多。估算后大约最多只能跳过30个点,因为跳的点足够多之后反而不如直接走更优。
那么这样的就可以dp,状态\(f[i][j]\)表示走到点\(i\)跳过\(j\)个点的最优解。然后可以直接枚举转移到当前状态跳过了多少个点\(k\),则转移为\(f[i][j]=\min(f[i][j],f[i-k-1][j-k]) + dis(i,i-k-1)+dirt(j , j - k )\),其中\(dis\)表示两点的距离,\(dirt\)是先减去跳过\(j-k\)个点的惩罚再加上\(j\)个点的惩罚。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
typedef pair<double, double> pdd;
const double inf = 1e10;
double dis(pdd a, pdd b) {
return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}
double dirt(int x, int y) {
double ans;
if (x > 0) ans = (1ll << (x - 1));
else ans = 0;
if (y > 0) ans -= (1ll << (y - 1));
return ans;
}
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n;
cin >> n;
vector<pdd> d(n + 1);
for (int i = 1; i <= n; i++)
cin >> d[i].first >> d[i].second;
vector f(n + 1, vector(35, (double) (inf)));
f[1][0] = 0;
for (int x = 2; x <= n; x++)
for (int j = 0; j < 35; j++)
for (int k = 0, y = x - 1; y >= 1 and k <= j; k++, y--)
f[x][j] = min(f[x][j], f[y][j - k] + dis(d[x], d[y]) + dirt( j , j - k ));
cout << fixed << setprecision(10) << *min_element(f[n].begin(), f[n].end()) << "\n";
return 0;
}
G - Ai + Bj + Ck = X (1 <= i, j, k <= N)
枚举\(i\)的值,然后方程就变成了\(Bj+Ck=X-Ai\)。用扩欧解丢番图方程即可。
注意本体精度问题。
#include <bits/stdc++.h>
using namespace std;
#define int __int128
typedef long long ll;
int read() {
int x = 0, f = 1, ch = getchar();
while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
if (ch == '-') f = -1, ch = getchar();
while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
return x * f;
}
int exgcd(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, x, y);
int z = x;
x = y, y = z - y * (a / b);
return d;
}
template<typename T, typename U>
T ceil(T x, U y) {
return (x > 0 ? (x + y - 1) / y : x / y);
}
template<typename T, typename U>
T floor(T x, U y) {
return (x > 0 ? x / y : (x - y + 1) / y);
}
int32_t main() {
int n = read(), a = read(), b = read(), c = read(), x = read(), res = 0;
for (int i = 1, j, k, m, d, bp, cp, l, r; i <= n; i++) {
m = x - a * i;
d = exgcd(b, c, j, k);
if (m % d) continue;
j *= m / d, k *= m / d;
bp = b / d, cp = c / d;
l = max(ceil(1 - j, cp), ceil(k - n, bp));
r = min(floor(n - j, cp), floor(k - 1, bp));
if (r >= l) res += r - l + 1;
}
cout << (ll) res << "\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