https://atcoder.jp/contests/abc308/tasks_print
A - New Scheme
过水已隐藏。
代码：
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
bool Memory_Begins;
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
template < class Z >
inline void read (Z &tmp) {
Z x = 0, f = 0;
char c = getchar ();
for ( ; c < '0' || c > '9' ; c = getchar ()) f |= (c == '-');
for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
tmp = !f ? x : -x;
}
int s[10];
bool Memory_Ends;
signed main () {
fprintf (stderr, "%.3lf MB\n", (&Memory_Begins - &Memory_Ends) / 1048576.0);
for (int i = 1;i <= 8; ++ i) read (s[i]);
int ok = 1;
for (int i = 1;i < 8; ++ i) ok &= (s[i] <= s[i + 1]);
for (int i = 1;i <= 8; ++ i) ok &= (s[i] >= 100 && s[i] <= 675);
for (int i = 1;i <= 8; ++ i) ok &= (s[i] % 25 == 0);
if (ok) printf ("Yes\n");
else printf ("No\n");
fprintf (stderr, "%.3lf ms\n", 1e3 * clock () / CLOCKS_PER_SEC);
return 0;
}
/*
Things to check:
1. int ? long long ? unsigned int ? unsigned long long ?
2. array size ? is it enough ?
*/
B - Default Price
很水：直接用 map 记一下即可。
代码：
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
bool Memory_Begins;
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
template < class Z >
inline void read (Z &tmp) {
Z x = 0, f = 0;
char c = getchar ();
for ( ; c < '0' || c > '9' ; c = getchar ()) f |= (c == '-');
for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
tmp = !f ? x : -x;
}
int n, m;
char c[105][25], d[105][25];
int p[105];
map < string, int > mp;
bool Memory_Ends;
signed main () {
fprintf (stderr, "%.3lf MB\n", (&Memory_Begins - &Memory_Ends) / 1048576.0);
read (n), read (m);
for (int i = 1;i <= n; ++ i) scanf ("%s", c[i] + 1);
for (int j = 1;j <= m; ++ j) scanf ("%s", d[j] + 1);
for (int i = 0;i <= m; ++ i) read (p[i]);
mp.clear ();
for (int i = 1;i <= m; ++ i) {
int len = strlen (d[i] + 1);
string str = "";
for (int j = 1;j <= len; ++ j) {
str += (char) (d[i][j]);
}
mp[str] = p[i];
}
int ans = 0;
for (int i = 1;i <= n; ++ i) {
int len = strlen (c[i] + 1);
string str = "";
for (int j = 1;j <= len; ++ j) {
str += (char) (c[i][j]);
}
if (mp[str]) ans += mp[str];
else ans += p[0];
}
printf ("%d\n", ans);
fprintf (stderr, "%.3lf ms\n", 1e3 * clock () / CLOCKS_PER_SEC);
return 0;
}
/*
Things to check:
1. int ? long long ? unsigned int ? unsigned long long ?
2. array size ? is it enough ?
*/
C - Standings
分数比较。然后排序。
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
bool Memory_Begins;
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
template < class Z >
inline void read (Z &tmp) {
Z x = 0, f = 0;
char c = getchar ();
for ( ; c < '0' || c > '9' ; c = getchar ()) f |= (c == '-');
for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
tmp = !f ? x : -x;
}
struct person {
int id;
ll suc, fai;
inline bool operator < (person p1) {
ll fir = suc * p1.fai, sec = p1.suc * fai;
if (fir != sec) return fir > sec;
else return id < p1.id;
}
} p[200005];
int n;
bool Memory_Ends;
signed main () {
fprintf (stderr, "%.3lf MB\n", (&Memory_Begins - &Memory_Ends) / 1048576.0);
read (n);
for (int i = 1;i <= n; ++ i) {
read (p[i].suc), read (p[i].fai);
p[i].fai += p[i].suc;
p[i].id = i;
}
sort (p + 1, p + 1 + n);
for (int i = 1;i <= n; ++ i) printf ("%d ", p[i].id);
printf ("\n");
fprintf (stderr, "%.3lf ms\n", 1e3 * clock () / CLOCKS_PER_SEC);
return 0;
}
/*
Things to check:
1. int ? long long ? unsigned int ? unsigned long long ?
2. array size ? is it enough ?
*/
D - Snuke Maze
可以直接 BFS，记录一下当前的点 + 字符。
记得加一下记忆化。
我以前写的代码因没有考虑方向寄了。
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
bool Memory_Begins;
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
template < class Z >
inline void read (Z &tmp) {
Z x = 0, f = 0;
char c = getchar ();
for ( ; c < '0' || c > '9' ; c = getchar ()) f |= (c == '-');
for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
tmp = !f ? x : -x;
}
int n, m;
char s[505][505];
int vis[505][505];
queue < pair < int, int > > q;
int mp[170];
bool Memory_Ends;
signed main () {
fprintf (stderr, "%.3lf MB\n", (&Memory_Begins - &Memory_Ends) / 1048576.0);
read (n), read (m);
for (int i = 1;i <= n; ++ i) scanf ("%s", s[i] + 1);
memset (mp, 0, sizeof mp);
mp['s'] = 1, mp['n'] = 2, mp['u'] = 3, mp['k'] = 4, mp['e'] = 5;
if (s[1][1] == 's') q.push (make_pair (1, 1));
while (!q.empty ()) {
int u = q.front ().first, v = q.front ().second;
q.pop ();
if (vis[u][v]) continue;
vis[u][v] = 1;
if (u == n && v == m) break;
for (int i = -1;i <= 1; ++ i) {
for (int j = -1;j <= 1; ++ j) {
if (abs (i) + abs (j) != 1) continue;
if (u + i < 1 || u + i > n) continue;
if (v + j < 1 || v + j > m) continue;
int X = mp[s[u][v]], Y = mp[s[u + i][v + j]];
if (!X || !Y) continue;
if (X < 5 && X + 1 == Y) q.push (make_pair (u + i, v + j));
if (X == 5 && Y == 1) q.push (make_pair (u + i, v + j));
}
}
}
if (vis[n][m]) printf ("Yes\n");
else printf ("No\n");
fprintf (stderr, "%.3lf ms\n", 1e3 * clock () / CLOCKS_PER_SEC);
return 0;
}
/*
Things to check:
1. int ? long long ? unsigned int ? unsigned long long ?
2. array size ? is it enough ?
*/
E - MEX
考虑先计数 \((i, j)\) 满足 \(1 \leq i < j \leq n\) 并且 \(s_{i}\) 为 E，\(s_{j}\) 为 X（按 \((A_i, A_j)\) 分开计数）。
这样可以直接前缀和做。
然后枚举一下 \(s_k\) 为 M 的 \(i\)，再枚举一下 \(A_i, A_j, A_k\)，带权计一下数即可。
代码：
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
bool Memory_Begins;
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
template < class Z >
inline void read (Z &tmp) {
Z x = 0, f = 0;
char c = getchar ();
for ( ; c < '0' || c > '9' ; c = getchar ()) f |= (c == '-');
for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
tmp = !f ? x : -x;
}
const int N = 2e5 + 5;
ll f[N][3][3];
int n, a[N];
ll sum[N][3][3];
char s[N];
inline int mex (int i, int j, int k) {
if (i != 0 && j != 0 && k != 0) return 0;
if (i != 1 && j != 1 && k != 1) return 1;
if (i != 2 && j != 2 && k != 2) return 2;
return 3;
}
bool Memory_Ends;
signed main () {
fprintf (stderr, "%.3lf MB\n", (&Memory_Begins - &Memory_Ends) / 1048576.0);
read (n);
for (int i = 1;i <= n; ++ i) read (a[i]);
scanf ("%s", s + 1);
for (int i = 1;i <= n; ++ i) {
for (int j = 0;j < 3; ++ j) {
for (int k = 0;k < 3; ++ k) {
f[i][j][k] = f[i - 1][j][k];
}
}
if (s[i] == 'M') f[i][a[i]][0] ++;
if (s[i] == 'E') f[i][a[i]][1] ++;
if (s[i] == 'X') f[i][a[i]][2] ++;
}
for (int i = n - 1;i >= 1; -- i) {
for (int j = 0;j < 3; ++ j) {
for (int k = 0;k < 3; ++ k) {
sum[i][j][k] = sum[i + 1][j][k];
}
}
if (s[i] == 'E') {
sum[i][a[i]][0] += f[n][0][2] - f[i][0][2];
sum[i][a[i]][1] += f[n][1][2] - f[i][1][2];
sum[i][a[i]][2] += f[n][2][2] - f[i][2][2];
}
}
ll ans = 0;
for (int i = 0;i < 3; ++ i) {
for (int j = 0;j < 3; ++ j) {
for (int k = 0;k < 3; ++ k) {
for (int _ = 1;_ <= n; ++ _) {
if (s[_] == 'M' && a[_] == i) ans += mex (i, j, k) * sum[_ + 1][j][k];
}
}
}
}
printf ("%lld\n", ans);
fprintf (stderr, "%.3lf ms\n", 1e3 * clock () / CLOCKS_PER_SEC);
return 0;
}
/*
Things to check:
1. int ? long long ? unsigned int ? unsigned long long ?
2. array size ? is it enough ?
*/