A - Takahashi san
#include <bits/stdc++.h>
using namespace std;
#define ll long long
using vi = vector<int>;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s , t;
cin >> s >> t;
cout << s << " san\n";
return 0;
}
B - World Meeting
//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
using namespace std;
#define ll long long
#define int long long
using vi = vector<int>;
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vi w( 24 );
for( int i = 1 , a , b ; i <= n ; i ++ )
cin >> a >> b , w[b] += a;
int res = 0;
for( int l = 0 , r = 8 ; l <= 23 ; l ++ , r ++ ){
int cnt = 0;
for ( int i = l ; i <= r ; i ++ )
cnt += w[ i % 24 ];
res = max( res , cnt );
}
cout << res << "\n";
return 0;
}
C - Sensors
#include <bits/stdc++.h>
using namespace std;
#define ll long long
using vi = vector<int>;
int dx[] = {0,0,1,-1,1,1,-1,-1};
int dy[] = {1,-1,0,0,1,-1,1,-1};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int H,W;cin >> H >> W;
vector<string> s(H);
for (int i = 0;i < H;i++){
cin >> s[i];
}
vector<vector<int>> vis(H,vector<int>(W));
int res = 0;
auto dd = [&](int x,int y)->void{
queue<pair<int,int>> q;
q.emplace(x,y);
while (!q.empty()){
auto [u,v] = q.front();
q.pop();
if (vis[u][v]) continue;
vis[u][v] = 1;
for (int i = 0;i < 8;i++){
int tx = u + dx[i],ty = v + dy[i];
if (tx < 0 || tx >= H || ty < 0 || ty >= W || vis[tx][ty]) continue;
if (s[tx][ty] == '.') continue;
q.emplace(tx,ty);
}
}
};
for (int i = 0;i < H;i++){
for (int j = 0;j < W;j++){
if (vis[i][j] || s[i][j] == '.') continue;
res++;
dd(i,j);
}
}
cout << res << endl;
return 0;
}
D - Printing Machine
枚举开始时间,然后把所有已经到达的加入到队列中,然后每次贪心的选择结束时间最少的即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
using i32 = int32_t;
using vi = vector<int>;
using pii = pair<int, int>;
const int inf = 1e9, INF = 1e18;
const int mod = 998244353;
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n;
cin >> n;
vector<pii> p(n);
for (auto &[x, y]: p) cin >> x >> y;
p.emplace_back(LLONG_MAX, LLONG_MAX);
sort(p.begin(), p.end());
multiset<int> cnt;
int now = 0, res = 0;
for (int i = 0; i < n;) {
now = max(now, p[i].first);
for (; i < n and p[i].first <= now; i++)
cnt.insert(p[i].first + p[i].second);
while (!p.empty() and now < p[i].first) {
auto it = cnt.lower_bound(now);
if (it == cnt.end()) break;
cnt.erase(it);
now++, res++;
}
}
cout << res << "\n";
return 0;
}
E - Our clients, please wait a moment
根据汽车火车分别建图,然后求两遍最短路,然后枚举换乘点即可
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
using vi = vector<int>;
const int inf = 1e18;
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n ;
cin >> n;
int a , b , c;
cin >> a >> b >> c;
vector<vi> g( n+1 , vi( n + 1 ) );
auto f = g;
for( int i = 1 ; i <= n ; i ++ ){
for( int j = 1 , x ; j <= n ; j ++ ){
cin >> x;
g[i][j] = x * a;
f[i][j] = x * b + c ;
}
}
vi dis( n+1 , inf );
vi dis1(n + 1,inf);
dis[1] = 0;
priority_queue<pair<int,int> , vector<pair<int,int>> , greater<pair<int,int>>> q;
q.emplace( 0 , 1 );
vi vis( n + 1 );
while( !q.empty() ){
auto [ d , x ] = q.top();
q.pop();
if( vis[x] ) continue;
vis[x] = 1;
for( int y = 1 ; y <= n ; y ++ ){
if( dis[y] <= d + g[x][y] ) continue;
dis[y] = d + g[x][y];
q.emplace( dis[y] , y );
}
}
dis1[n] = 0;
priority_queue<pair<int,int> , vector<pair<int,int>> , greater<pair<int,int>>> q1;
q1.emplace( 0 , n );
vi vis1( n + 1 );
while( !q1.empty() ){
auto [ d , x ] = q1.top();
q1.pop();
if( vis1[x] ) continue;
vis1[x] = 1;
for( int y = 1 ; y <= n ; y ++ ){
if( dis1[y] <= d + f[x][y] ) continue;
dis1[y] = d + f[x][y];
q1.emplace( dis1[y] , y );
}
}
int res = 1e18;
for (int i = 1;i <= n;i++){
res = min(res,dis[i] + dis1[i]);
}
cout << res << endl;
return 0;
}
F - Sensor Optimization Dilemma
\(f[i][j]\)表示前\(i\)个部分用了\(j\)个 1 型监控器最少用多少个 2 型监控器。然后枚举一下\(i\)位用了多少个 1 型监控器即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
using i32 = int32_t;
using vi = vector<int>;
using pii = pair<int, int>;
const int inf = 1e10, INF = 1e18;
const int mod = 998244353;
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n;
cin >> n;
vi d(n + 1);
for (int i = 1; i <= n; i++) cin >> d[i];
int l1, c1, k1, l2, c2, k2;
cin >> l1 >> c1 >> k1 >> l2 >> c2 >> k2;
vector f(n + 1, vi(k1 + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= k1; j++) {
f[i][j] = inf;
for (int k = 0, t; k <= j; k++) {
t = d[i] - k * l1, t = (t + l2 - 1) / l2;
f[i][j] = min(f[i][j], f[i - 1][j - k] + t);
if (t == 0) break;
}
}
}
int res = INF;
for (int i = 0; i <= k1; i++)
if (f[n][i] <= k2) res = min(res, c1 * i + c2 * f[n][i]);
if( res == INF ) cout << "-1\n";
else cout << res << "\n";
return 0;
}
G - offence
一个不太好想的区间 dp
\(f[l][r]\)表示\([l,r]\)经过若干次操作后所能剩下的最短长度,则答案即为\(f[0][n-1]\)
转移首先考虑用两个子区间拼起来的最优解,其次再考虑端点为o
或f
的情况。
#include <bits/stdc++.h>
using namespace std;
#define int long long
using i32 = int32_t;
using vi = vector<int>;
using pii = pair<int, int>;
const int inf = 1e10, INF = 1e18;
const int mod = 998244353;
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int K;
string s;
cin >> s >> K;
int n = s.size();
vector f(n + 1, vi(n + 1));
for (int l = 0; l < n; l++)
for (int r = 0; r < n; r++)
f[l][r] = r - l + 1;
for (int len = 2; len <= n; len++) {
for (int l = 0, r = len - 1; r < n; l++, r++) {
if (len == 2) {
if (s[l] == 'o' and s[r] == 'f') f[l][r] = 0;
} else {
for (int k = l; k < r; k++)
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r]);
if (s[r] == 'f') {
for (int k = l; k < r; k++)
if (s[k] == 'o' and f[k + 1][r - 1] == 0)
f[l][r] = min(f[l][r], (k == 0) ? 0 : f[l][k - 1]);
}
if (s[l] == 'o') {
for (int k = l + 1; k <= r; k++) {
if (s[k] == 'f' and f[l + 1][k - 1] == 0)
f[l][r] = min(f[l][r], max(f[k + 1][r] - K, 0ll));
}
}
}
}
}
cout << f[0][n - 1] << "\n";
return 0;
}
- Beginner AtCoder Contest 325beginner atcoder contest 325 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 beginner atcoder contest 332 beginner atcoder contest 327