2020-2021 ACM-ICPC Brazil Subregional Programming Contest
A Sticker Album
概率递推, f[i] 表示得到 i 张贴纸要开包数的期望
则当 a > 0 时, 1~a, f[i] = 1(开一包至少 a 张贴纸)
i > a, 则 (f[i]=frac{sum_{j=i-b}^{i-a}f[j]}{b-a+1}+1) (在得到[i-b,i-a]张贴纸的基础上, 随便开一包得至少 a 张贴纸)
当 a == 0, 直接就是 (f[i]=frac{sum_{j=i-b}^{i-a}f[j]}{b-a+1} + 1)
带入 a = 0, 两边都有f[i]移项 解得 (f[i]=frac{sum_{j=i-b}^{i-1} + b + 1}{b})
维护个sum 即可 表示 f[i-b]~f[i - (a ? a : 1)] 即可
int main() {
IOS; cin >> n >> a >> b;
rep (i, 1, n) {
if (a) f[i] = s / (b - a + 1) + 1;
else f[i] = (s + b + 1) / b;
s += (a ? f[max(i + 1 - a, 0ll)] : f[i]) - f[max(i - b, 0ll)];
}
cout << precision(5) << f[n];
return 0;
}
B Battleship
模拟
bool v[11][11];
int main() {
IOS; cin >> n; bool f = 1;
rep (i, 1, n) {
int d, l, r, c; cin >> d >> l >> r >> c;
if (!d) for (int j = 0; j < l; ++j)
if (c + j > 10 || v[r][c + j]) f = 0;
else v[r][c + j] = 1;
else for (int j = 0; j < l; ++j)
if (r + j > 10 || v[r + j][c]) f = 0;
else v[r + j][c] = 1;
}
cout << (f ? 'Y' : 'N');
return 0;
}
C Concatenating Teams
说白了就是如果存在 $a^, = a+S, b^,=T+b, T == S $ 则 (a, a^,,b,b^,) 都不是
不存在相同字串, 直接全hash一边, 并存下所有的 S 和 T 即可, 对于 (b^,=T+b) reverse一下 形式就如同 (a^, = a+S) 了 只不过 T 变成原来的反串了
怕卡hash, 用了双hash
const int N = 1e5 + 5, P[2] = { 131, 13331 };
bool va[N], vb[N];
string a[N], b[N];
ull p[2][N * 10] = { {1}, {1} }, has[2][N * 10], rhas[2][N * 10];
unordered_map<ull, int> x[2], y[2];
unordered_set<ull> sta[2], stb[2];
void hashstr(string& a) {
rep(i, 1, a.size()) rep(j, 0, 1) has[j][i] = has[j][i - 1] * P[j] + a[i - 1];
}
void rhashstr(string& a) {
rep(i, 1, a.size()) rep(j, 0, 1) rhas[j][i] = rhas[j][i - 1] * P[j] + a[a.size() - i];
}
void init(int n, string* a, unordered_map<ull, int>* x, unordered_set<ull>* sta) {
sort(a + 1, a + 1 + n, [](string& a, string& b) { return a.size() < b.size(); });
rep(i, 1, n) {
hashstr(a[i]); x[0][has[0][a[i].size()]] = x[1][has[1][a[i].size()]] = i;
rep(j, 1, a[i].size() - 1) if (x[0].count(has[0][j]) && x[1].count(has[1][j]))
sta[0].insert(has[0][a[i].size()] - has[0][j] * p[0][a[i].size() - j]),
sta[1].insert(has[1][a[i].size()] - has[1][j] * p[1][a[i].size() - j]);
}
}
int work(int n, string* a, unordered_map<ull, int>* x, unordered_set<ull>* stb, bool* va) {
rep(i, 1, n) {
hashstr(a[i]); rhashstr(a[i]);
rep(j, 1, a[i].size() - 1) {
if (x[0].count(has[0][j]) && x[1].count(has[1][j]) &&
stb[0].count(rhas[0][a[i].size() - j]) && stb[1].count(rhas[1][a[i].size() - j]))
va[i] = va[x[0][has[0][j]]] = 1;
}
}
int ans = 0;
rep(i, 1, n) if (va[i] == 0) ++ans;
return ans;
}
D
E Party Company
朴素的想, 领导关系构成一棵树(每个人最多有一个领导(父亲节点)), 且年龄也满足树形结构(领导比手下年龄大)
任何一个party的年龄 l, r, 要找参与者就要找这个party的所有者 (O_i) 的手下和其领导的手下, 领导的领导的手下...
不如干脆直接把party的所有者改成 (O_i) 的某个祖先(领导的领导的领导...) 正好使得这个祖先的年龄 <= r (树上倍增LCA)
然后就是 dfs 了, 每个点都会影响其孩子, 那就 dfs完当前点x的所有孩子, 再把当前x 的贡献消掉就好, 线段树/树状 都行
struct STFrom {
static const int N = 1e5 + 5;
int f[N][20], dep[N], lg[N], t;
vector<int> *h;
void init(int n, vector<int>* H) {
t = log2(n - 1) + 1; h = H;
rep(i, 1, n) dep[i] = 0;
rep(i, 1, n) lg[i] = lg[i >> 1] + 1;
}
void bfs(int s) {
queue<int> q; q.push(s); dep[s] = 1;
rep(i, 0, t) f[s][i] = 0;
while (!q.empty()) {
int x = q.front(); q.pop();
for (auto y : h[x]) {
if (dep[y]) continue;
dep[y] = dep[x] + 1; f[y][0] = x;
for (int j = 1; j <= t; ++j) f[y][j] = f[f[y][j - 1]][j - 1];
q.push(y);
}
}
}
int find(int x, int r, int* a) {
per (i, lg[dep[x]], 0) if (f[x][i] && a[f[x][i]] <= r) x = f[x][i];
return x;
}
} ST;
const int N = 1e5 + 5;
int n, m, _, k, cas;
int a[N], c[N], fa[N], b[N];
VI h[N], g[N];
void add(int x, int k) { for (; x <= N; x += -x & x) c[x] += k; }
int ask(int x) { int ans = 0; for (; x; x -= -x & x) ans += c[x]; return ans; }
void dfs(int x) {
for (auto i : g[x]) add(i, 1);
b[x] = ask(a[x]);
for (auto y : h[x]) dfs(y);
for (auto i : g[x]) add(i, -1);
}
int main() {
IOS; cin >> n >> m >> a[1] >> fa[1];
rep (i, 2, n) cin >> a[i] >> fa[i], h[fa[i]].pb(i);
ST.init(n, h); ST.bfs(1);
rep (i, 1, m) {
int id, l, r; cin >> id >> l >> r;
id = ST.find(id, r, a); g[id].pb(l);
}
dfs(1); rep (i, 1, n) cout << b[i] << ' ';
return 0;
}
F Fastminton
模拟
int a[2], b[2];
bool f = 0;
int main() {
IOS; string s; cin >> s;
for (auto c : s) {
if (a[0] + a[1] < 3 && abs(a[0] - a[1]) < 2) {
if (c == 'S') ++b[f];
else if (c == 'R') ++b[f ^= 1];
if ((b[f] >= 5 && b[f] - b[f ^ 1] >= 2) || b[f] == 10)
b[f] = b[f ^ 1] = 0, ++a[f];
}
if (c != 'Q') continue;
if (a[0] + a[1] == 3 || abs(a[0] - a[1]) == 2)
cout << a[0] << ' ' << (a[0] > a[1] ? "(winner) - " : "- ") << a[1] << (a[1] > a[0] ? " (winner)
" : "
");
else cout << a[0] << " (" << b[0] << (f ? ") - " : "*) - ") << a[1] << " (" << b[1] << (f ? "*)
" : ")
");
}
return 0;
}
G Game Show!
贪心, 不断取a[i], 再不断取max
int main() {
IOS; cin >> n; k = m = 100;
rep (i, 1, n) cin >> _, umax(m, k += _);
cout << m;
return 0;
}
H SBC's Hangar
组合数学 不超过 r 的方案数量 - 不超过 l - 1 的方案数量就是答案
不超过 x 的方案数量怎么求呢?
保证任意 较大的行李都比较小的行李的两倍 重
那不就是排好序之后 (a[i] > sum_{j=1}^{i-1} a[i]) 吗
不选 a[i] 那前面的 1~i-1 个物品随便选够 k 减即可, 那不就是组合数学吗?
ll c[N][N], a[N], l, r;
void init(int n){
rep (i, 0, n) {
c[i][0] = 1;
rep (j, 1, i) c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
}
}
ll work(ll v, int k) {
ll ans = 0;
per (i, n, 1) if (k && a[i] <= v)
ans += c[i - 1][k], v -= a[i], --k;
return ans + (k == 0);
}
int main() {
IOS; cin >> n >> k; init(n);
rep (i, 1, n) cin >> a[i]; sort(a + 1, a + 1 + n);
cin >> l >> r; cout << work(r, k) - work(l - 1, k);
return 0;
}
I
J
K
L Lavaspar
暴力模拟题意, 用位压表示这个格子有哪些串
int a[41][41], c[21][26], b[41][41], d[4][2] = {{1, 0}, {0, 1}, {1, 1}, {1, -1}};
char s[45], str[21][20];
void work(int k, int x, int y, int de) {
rep (i, 0, 25) c[0][i] = c[k][i];
for (int i = 1; str[k][i] && x <= n && y <= m && y; ++i)
--c[0][a[x][y]], x += d[de][0], y += d[de][1];
rep (i, 0, 25) if (c[0][i]) return;
for (int i = 1; str[k][i]; ++i) b[x -= d[de][0]][y -= d[de][1]] |= 1 << k;
}
int main() {
IOS; cin >> n >> m;
rep (i, 1, n) {
cin >> s + 1;
rep (j, 1, m) a[i][j] = s[j] ^ 'A';
}
cin >> cas;
rep (i, 1, cas) {
cin >> str[i] + 1;
for (int j = 1; str[i][j]; ++j) ++c[i][str[i][j] ^ 'A'];
}
rep (k, 1, cas) rep (i, 1, n) rep (j, 1, m) rep (t, 0, 3) work(k, i, j, t);
rep (i, 1, n) rep (j, 1, m) if (__builtin_popcount(b[i][j]) > 1) ++_;
cout << _;
return 0;
}
M
N Number Multiplication
因为质数有序, 直接报以算就好了
算第 i 个质数就从 pri[i - 1] 枚举到 sqrt(w) 就好了
算出来 pri[i] 再把其对其他权值的贡献的影响除掉
ll a[N], b[N] = {2};
vector<PII> h[N];
int main() {
IOS; cin >> m >> n >> k; unordered_set<ll> st;
rep (i, 1, n) cin >> a[i];
rep (i, 1, k) {
int u, v, c; cin >> u >> v >> c;
h[u].pb({v, c});
}
rep (i, 1, m) {
ll x = a[h[i][0].fi]; b[i] = x;
rep (j, b[i - 1], x / j) if (x % j == 0) { b[i] = j; break; }
for (auto &y : h[i]) rep (j, 1, y.se) a[y.fi] /= b[i];
}
rep (i, 1, m) cout << b[i] << ' ';
return 0;
}
P (HDU - 3605)
10个点, 那么每个人的状态用位压表示就 1024 种, 转换完之后直接 网络流板子即可
int h[N], ne[M], to[M], co[M], tot, now[N];
int d[N], s = 1025, t = 1026, maxflow, a[N], b[11];
void add(int u, int v, int c) {
ne[++tot] = h[u]; to[h[u] = tot] = v; co[tot] = c;
ne[++tot] = h[v]; to[h[v] = tot] = u; co[tot] = 0;
}
bool bfs() {
memset(d, 0, sizeof d); memcpy(now, h, sizeof h);
queue<int> q; q.push(s); d[s] = 1;
while (!q.empty()) {
int x = q.front(); q.pop();
for (int i = h[x]; i; i = ne[i]) {
if (!co[i]) continue;
int y = to[i];
if (d[y]) continue;
d[y] = d[x] + 1; q.push(y);
if (y == t) return 1;
}
}
return 0;
}
int dinic(int x, int flow) {
if (x == t) return flow;
int rest = flow, k;
for (int& i = now[x]; i && rest; i = ne[i]) {
if (!co[i]) continue;
int y = to[i];
if (d[y] != d[x] + 1) continue;
k = dinic(y, min(rest, co[i]));
if (!k) d[y] = 0;
co[i] -= k, co[i ^ 1] += k; rest -= k;
}
return flow - rest;
}
int main() {
IOS;
while(cin >> k >> m) {
n = (1 << m) - 1; tot = 1;
memset(h, 0, sizeof h); memset(a, 0, sizeof a);
rep (i, 1, k) {
int cur = 0;
rep (j, 1, m) if (cin >> _, _) cur ^= 1 << j - 1;
++a[cur];
}
rep (i, 1, n) if (a[i]) {
rep (j, 1, m) if (i >> j - 1 & 1) add(i, t + j, inf);
add(s, i, a[i]);
}
rep (i, 1, m) cin >> b[i], add(i + t, t, b[i]);
int flow = maxflow = 0;
while (bfs()) while (flow = dinic(s, inf)) maxflow += flow;
cout << (maxflow == k ? "YES
" : "NO
");
}
return 0;
}