2020-2021 ICPC - Gran Premio de Mexico - Repechaje
2024-03-25 17:43:04
A. Atsa’s Checkers Board
给定一个
n
∗
m
n * m
n∗m大小的矩阵,在该矩阵内放置黑色白色的石头,要保证每个
2
∗
2
2 * 2
2∗2的矩阵都有两个黑石头和两个白石头,问有多少种摆放方式
可以发现当有两块颜色相同的石头摆放在一起的时候,整个矩阵的摆放方式就确定了
可以发现第一行至少有一对颜色相同石子相连的方案数是
1
<
<
m
−
2
1 << m - 2
1<<m−2,而第一列至少有一对颜色相同石子相连的方案数是
1
<
<
n
−
2
1 << n - 2
1<<n−2
第一行第一列同时出现两两颜色不相同的情况有2种
因此总情况数就是
(
1
<
<
m
)
+
(
1
<
<
n
)
−
2
(1 << m) + (1 << n) - 2
(1<<m)+(1<<n)−2
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 3200;
const int INF = 0x3f3f3f3f;
const double pi = acos(-1.0);
const double eps = 1e-8;
inline ll rd() {
ll x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
int main() {
ll n, m;
n = rd();
m = rd();
if (n < 2 || m < 2) {
puts("0");
return 0;
}
printf("%lld\n", (1LL << n) + (1LL << m) - 2);
return 0;
}
E. Enterprise Recognition Program
给定一个树形图代表一个公司的主从结构,并且公司中有
n
n
n个员工,老板节点编号为
0
0
0,老板不属于员工
操作
m
m
m次,并且有两种操作
第一种操作是给员工
e
e
e发
v
v
v元的奖金
第二种操作是给员工
e
e
e及其所有上司发
v
v
v元的奖金
询问
q
q
q次,并且有两种询问
第一种询问是询问员工
x
x
x有多少奖金
第二种询问是询问员工
x
x
x的下属和员工
x
x
x共有多少奖金
设置一个
e
a
r
n
earn
earn数组,
e
a
r
n
[
i
]
[
0
]
earn[i][0]
earn[i][0]表示公司用操作一发给员工
i
i
i的奖金,
e
a
r
n
[
i
]
[
1
]
earn[i][1]
earn[i][1]表示公司用操作二发给员工
i
i
i的奖金,
e
a
r
n
[
i
]
[
2
]
earn[i][2]
earn[i][2]表示员工
i
i
i的下属们的总奖金
从老板节点开始往下
d
f
s
dfs
dfs,从叶子节点往上累加奖金即可
以下为两个递推公式,
u
u
u为当前员工,
v
v
v为
u
u
u的下属
e
a
r
n
[
u
]
[
1
]
+
=
e
a
r
n
[
v
]
[
1
]
;
earn[u][1] += earn[v][1];
earn[u][1]+=earn[v][1];
e
a
r
n
[
u
]
[
2
]
+
=
e
a
r
n
[
v
]
[
0
]
+
e
a
r
n
[
v
]
[
1
]
+
e
a
r
n
[
v
]
[
2
]
;
earn[u][2] += earn[v][0] + earn[v][1] + earn[v][2];
earn[u][2]+=earn[v][0]+earn[v][1]+earn[v][2];
具体逻辑在代码中体现
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#define lowbit(x) ((x) & -(x))
#define endl "\n"
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e6 + 10, NN = 2e3 + 10, INF = 0x3f3f3f3f, LEN = 20;
const ll MOD = 1e9 + 7;
const ull seed = 31;
const double pi = acos(-1.0), eps = 1e-8;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
struct Edge {
int next, to;
} edge[N];
int num_edge, n, m, q, boss;
int head[N], cha[N];
ll earn[N][3];
void add_edge(int from, int to) {
edge[num_edge].next = head[from];
edge[num_edge].to = to;
head[from] = num_edge++;
}
void init() {
memset(head, -1, sizeof head);
}
void dfs(int u) {
for (int i = head[u]; i != -1; i = edge[i].next) {
int v = edge[i].to;
dfs(v);
earn[u][1] += earn[v][1];
earn[u][2] += earn[v][0] + earn[v][1] + earn[v][2];
}
}
int main() {
// ios::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
n = read(), m = read(), q = read();
init();
for (int i = 1; i <= n; ++i) {
int x = read();
add_edge(x, i);
if (x == 0)
boss = i;
}
for (int i = 1; i <= m; ++i) {
int m = read(), e = read(), v = read();
earn[e][m - 1] += v;
}
dfs(boss);
while (q--) {
int op = read(), x = read();
if (op == 1)
printf("%lld\n", earn[x][0] + earn[x][1]);
else
printf("%lld\n", earn[x][2] + earn[x][1] + earn[x][0]);
}
return 0;
}
K. Kitchen Waste
有
n
n
n个面包,
m
m
m口锅,每口锅中都装了一定体积的汤,要将汤淋在面包上,面包也有体积,一体积汤能淋一体积面包
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e7 + 10;
const int INF = 0x3f3f3f3f;
inline ll read() {
ll x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
int n, m;
int a[N], b[N];
int main() {
n = read();
m = read();
for (int i = 1; i <= n; ++i)
a[i] = read();
for (int i = 1; i <= m; ++i)
b[i] = read();
int pos = 1;
for (int i = 1; i <= m; ++i) {
while (b[i] >= a[pos]) {
b[i] -= a[pos];
++pos;
if (pos > n)
break;
}
if (pos > n)
break;
}
int ans = 0;
for (int i = 1; i <= m; ++i)
ans += b[i];
printf("%d\n", ans);
return 0;
}