https://ac.nowcoder.com/acm/contest/4138

G. 草莓2

 

题意:nmn\cdot m 的网格,每格初始有一些草莓,每天早上wls收集这格所有草莓,下午向相邻格移动或者不动,每天晚上每格会多一个草莓,问 kk天最多收集多少草莓。

由于数据量特别小,枚举可以发现始终存在哈密顿回路。

则如果 k>nmk>n\cdot m 则收集完一圈之后回到第0天的地方再沿路收集最优。

否则直接dfs找最优解。

注意本题dfs可能走重复格子!!如:1000,0,1000,1,1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
ll n, m, sx, sy, k;
ll a[20][20];
int dx[]{ -1,1,0,0 };
int dy[]{ 0,0,-1,1 };
ll sum, ans;
void dfs(ll x, ll y, ll res, ll dep) {
if (dep == k) {
ans = max(ans, res);
return;
}
ll tmp = a[x][y];
a[x][y] = 0;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) {
dfs(nx, ny, res + a[nx][ny], dep + 1);
}
}
a[x][y] = tmp;
}
int main() {
scanf("%lld%lld%lld%lld%lld", &n, &m, &sx, &sy, &k);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
scanf("%lld", &a[i][j]);
sum += a[i][j];
}
}
if (k >= n * m)
ans = sum + n * m * (n*m - 1) / 2 + n * m*(k - n * m);
else {
dfs(sx, sy, a[sx][sy], 1);
ans += k * (k - 1) / 2;
}
cout << ans << endl;
return 0;
}

 

H. 游戏

 

题意:有 11nn 这些数字各一个。你用这些数字进行若干轮游戏。 对于每一轮,如果剩下的数字个数超过 11 个,那么就等概率随机选择两个剩下的数字删去。如果这两个数字互质,得一分。重复以上操作直到没数字可以删除为止。请问最后期望得多少分?

由期望可加性可得答案等于每个数对的出现概率之和,每个数对的概率相等,所以只要求互质的数对个数。

而这就是 11nn 所有书的欧拉函数值之和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
int n;
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
const ll p_max = 1E5 + 100;
ll phi[p_max];
void get_phi() {
phi[1] = 1;
static bool vis[p_max];
static ll prime[p_max], p_sz, d;
FOR(i, 2, p_max) {
if (!vis[i]) {
prime[p_sz++] = i;
phi[i] = i - 1;
}
for (ll j = 0; j < p_sz && (d = i * prime[j]) < p_max; ++j) {
vis[d] = 1;
if (i % prime[j] == 0) {
phi[d] = phi[i] * prime[j];
break;
}
else phi[d] = phi[i] * (prime[j] - 1);
}
}
}
int gcd(int a, int b) {
if (a < b)swap(a, b);
return b == 0 ? a : gcd(b, a%b);
}
int x, y;
int main() {
scanf("%d", &n);
get_phi();
for (int i = 2; i <= n; i++)x += phi[i];
y = n - 1 + (n & 1);
int m = gcd(x, y);
x /= m; y /= m;
cout << x << '/' << y << endl;
return 0;
}

 

K. 修炼

 

题意:两人初始能力值 v1,v2v_1,v_2 都为0,每天可以增加各自 a1,a2a_1,a_2 ,每天获得一点技能点,可以用来提升 a1a_1a2a_2 ,给定一些 b1,b2b_1,b_2 的组合,若满足其中一种组合的 v1b1&&v2b2v_1\geq b_1\&\&v_2\geq b_2 ,则胜利,问最短几天获胜。

对每种组合二分求最小天数,总的能力值之和为 ta1+ta2+1+2++tt\cdot a_1+t\cdot a_2+1+2+\cdots +t,总能力值要大于 b1+b2b_1+b_2 ,且由于用每天的技能点可以得到 111+2++t1+2+\cdots +t 的任意数,所以只要 ta1b1ta1+1+2++tt\cdot a_1\leq b_1\leq t\cdot a_1+1+2+\cdots +t ,就一定能凑出 b1b_1,也就能得到 v2b2v_2\geq b_2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
ll n, a1, a2, b1, b2;
ll ans = INF;
bool check(ll t) {
if (t*a1 + t * a2 + (1 + t)*t / 2 < b1 + b2)return false;
if ((t*a1 + (1 + t)*t / 2 < b1) || (t*a2 + (1 + t)*t / 2 < b2))return false;
return true;
}
int main() {
scanf("%lld%lld%lld", &a1, &a2, &n);
for (int i = 0; i < n; i++) {
scanf("%lld%lld", &b1, &b2);
ll L = 0, R = b1 + b2;
while (L < R) {
ll mid = (L + R) / 2;
if (check(mid))R = mid;
else L = mid + 1;
}
ans = min(ans, L);
}
cout << ans << endl;
return 0;
}

 

L. 图

 

题意:一个 nn 个点的有向图,初始每个顶点都有一个颜色,黑或白。 每一轮,每个顶点的颜色会改变,规则如下:如果在上一轮,有奇数个黑色顶点连向他,那么这个顶点会变成黑的;如果在上一轮,有偶数个黑色顶点连向他,那么这个顶点会变成白的。初始状态为第 00 轮。小渣渣想要知道对于某一个点,从第 00 轮开始,最少过了几轮,使得它在这几轮结束的时候,顶点是黑色的次数大于等于 kk 次(第 00 轮结束也算)?

状压枚举每点的颜色状态,每个状态的后继状态唯一,并且起点固定,状态有限,所以状态转换图是一个 ρ\rho 型的图,即一条长链最终进入一个环。

预处理出每个点长链阶段最多的黑色次数,和环的长度,每个点在环阶段的黑色次数,就可以把 kk 先减去长链次数,再数出环里的次数,以及最后一次在环里还要走的距离。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int N = 21;
int vis[1 << N];
int n, m, q, st, ed;
vector<int> G[N];
int a[1 << N][N], b[N];
int pre[N][1 << N];
int main() {
cin >> n >> m >> q;
for (int i = 1; i <= n; i++) scanf("%d", &a[1][i]);
for (int i = 0, u, v; i < m; i++) {
scanf("%d%d", &u, &v);
G[v].push_back(u);
}
int now = 0;
for (int i = 1; i <= n; i++) now += a[1][i] << (i - 1);
vis[now] = 1; now = 0;
for (int t = 2;; t++, now = 0) {
for (int j = 1; j <= n; j++) {
for (int k : G[j]) a[t][j] ^= a[t - 1][k];
now += a[t][j] << (j - 1);
}
if (vis[now]) {
st = vis[now]; ed = t - 1;
break;
}
vis[now] = t;
}
for (int i = 1; i <= ed; i++) {
for (int j = 1; j <= n; j++) pre[j][i] = pre[j][i - 1] + a[i][j];
}
while (q--) {
int x; ll k;
scanf("%d%lld", &x, &k);
if (k == 0) { printf("0\n"); continue; }
if (k > pre[x][ed]) {
if (pre[x][ed] == 0) printf("-1\n");
else {
ll ans = ed; k -= pre[x][ed];
int dif = pre[x][ed] - pre[x][st - 1];
if (dif == 0) { printf("-1\n"); continue; }
ll t = (k - 1) / dif; ans += t * (ed - st + 1); k -= t * dif;
ans += lower_bound(pre[x] + st, pre[x] + ed + 1, k + pre[x][st - 1]) - (pre[x] + st - 1);
printf("%lld\n", ans - 1);
}
}
else printf("%d\n", lower_bound(pre[x], pre[x] + ed + 1, k) - pre[x] - 1);
}
return 0;
}