2018hdu多校第三场

A. Ascending Rating

题意

给定一个序列 a[1..n],对于每个长度为 m 的连续子区间,
求出区间 a 的最大值以及从左往右扫描该区间时 a 的最大值的
变化次数。

$1 \leq n,m\leq 1e7$

分析

滑动窗口最大值是单调队列的经典问题,但是最大值的变化次数怎么求?

反着扫,队列的大小就是当前区间的最大值变化次数。

为什么呢?

因为单调队列维护的是一个递减的数列,队首是当前区间的最大值,那么从尾到首,大小是不断递增的。也就是最大值的变化次数。 所以要反过来扫才能求出结果。

代码

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
// ybmj
#include <bits/stdc++.h>
using namespace std;
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define lson_len (len - (len >> 1))
#define rson_len (len >> 1)
#define pb(x) push_back(x)
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const int maxn = 1e7 + 7;
int a[maxn];
int main() {
// /*
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
// */
std::ios::sync_with_stdio(false);
int T;
scanf("%d", &T);
while (T--) {
int n, m, k, p, q, r, mod;
scanf("%d%d%d%d%d%d%d", &n, &m, &k, &p, &q, &r, &mod);
for (int i = 1; i <= k; i++) scanf("%d", a + i);
for (int i = k + 1; i <= n; i++)
a[i] = (1LL * a[i - 1] * p + 1LL * q * i + r) % mod;
deque<pii> dq;
ll A = 0, B = 0;
for (int i = n; i >= 1; i--) {
while (dq.size() && dq.front().second - i >= m) dq.pop_front();
while (dq.size() && a[i] >= dq.back().first) dq.pop_back();
dq.push_back(mp(a[i], i));
if (i <= n - m + 1) {
A += dq.front().first ^ i;
B += dq.size() ^ i;
}
}
printf("%lld %lld\n", A, B);
}
}

C. Dynamic Graph Matching

题意

给定一个 n 个点的无向图,m 次加边或者删边操作。

在每次操作后统计有多少个匹配包含 k = 1, 2, …,n/2 条边。

$1\leq n\leq 10, 1 \leq m \leq 3e4$

分析

$dp[i][k]$:表示第i次操作,所覆盖集合为k的种类数.

对于加边操作

1
2
3
4
5
edge (u,v)
int S = (1 << u) & (1 << v);

if((k & S) == S)
dp[i][k] = dp[i-1][k] + dp[i-1][k ^ S];

对于删边操作

1
2
if((k & S) == S)
dp[i][k] = dp[i-1][k] - dp[i-1][k ^ S];

这样即使有重边也不用怕

代码

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
54
55
56
57
58
59
60
61
62
63
64
// ybmj
#include <bits/stdc++.h>
using namespace std;
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define lson_len (len - (len >> 1))
#define rson_len (len >> 1)
#define pb(x) push_back(x)
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const int maxn = 1111;
const int mod = 1e9+7;
int dp[2][maxn];
int cnt[maxn], ans[maxn];
int main() {
// /*
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
// */
std::ios::sync_with_stdio(false);
int T;
scanf("%d", &T);
while (T--) {
int n, m;
scanf("%d%d", &n, &m);
char s[10];
int all = 1 << n;
for (int i = 0; i < all; i++) {
dp[0][i] = dp[1][i] = 0;
cnt[i] = __builtin_popcount(i);
}
dp[0][0] = 1;
for (int i = 1, u, v; i <= m; i++) {
scanf("%s%d%d", s, &u, &v);
u--, v--;
int S = (1 << u) | (1 << v);
if (s[0] == '+') {
for (int k = 0; k < all; k++) {
dp[i & 1][k] = dp[i & 1 ^ 1][k];
if ((k & S) == S)
(dp[i & 1][k] += dp[i & 1 ^ 1][k ^ S]) %= mod;
}
} else {
for (int k = 0; k < all; k++) {
dp[i & 1][k] = dp[i & 1 ^ 1][k];
if ((k & S) == S) (dp[i & 1][k] -= dp[i & 1 ^ 1][k ^ S] - mod) %= mod;
}
}
for (int k = 0; k <= n; k++) ans[k] = 0;
for (int k = 0; k < all; k++) (ans[cnt[k]] += dp[i & 1][k]) %= mod;
for (int k = 2; k <= n; k += 2) {
printf("%d%c", ans[k], k < n ? ' ' : '\n');
}
}
}
}

D-Euler Function

题意

问第k小的n,满足$\phi(n)$为合数, $k \leq 1e9$

分析

对于$n = p_1^{k_1}p_2^{k_2}$, $\phi(n) = p_1^{k_1-1}(p_1-1)p_2^{k_2-1}(p_2-1)$

可以发现除了1,2,3,4,6以外都是合数。

代码

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
// ybmj
#include <bits/stdc++.h>
using namespace std;
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define lson_len (len - (len >> 1))
#define rson_len (len >> 1)
#define pb(x) push_back(x)
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define first fi
#define second se
#define my_unique(a) a.resize(distance(a.begin(), unique(a.begin(), a.end())))
#define my_sort_unique(c) (sort(c.begin(), c.end())), my_unique(c)
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;

int main() {
// /*
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
// */
std::ios::sync_with_stdio(false);
int T;
scanf("%d", &T);
while (T--) {
int k;
scanf("%d", &k);
printf("%d\n", k + 4 + (k != 1));
}
}

F-Grab The Tree

题意

给定一棵 n 个点的树,每个点有权值。两个人玩游戏,先手需要占领若干不相邻的点,然后后手占领剩下所有点。

每个人的得分为占领的点权异或和,分高的获胜。问最优策略下游戏的结果

分析

设sum为所有点权的异或和

若sum不为0,那么先手只要选择最高位为1的那个点,选一个就可以啦,然后就赢了。

如果为0,那一定是平局。 如果当前位为0,那么说明这个点权的出现次数一定为偶数次,那么Q拿奇数次,T也会拿奇数次,Q拿偶数次,T也会拿偶数次,始终是一样的。

代码

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
// ybmj
#include <bits/stdc++.h>
using namespace std;
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define lson_len (len - (len >> 1))
#define rson_len (len >> 1)
#define pb(x) push_back(x)
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define first fi
#define second se
#define my_unique(a) a.resize(distance(a.begin(), unique(a.begin(), a.end())))
#define my_sort_unique(c) (sort(c.begin(), c.end())), my_unique(c)
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;

int main() {
// /*
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
// */
std::ios::sync_with_stdio(false);
int T;
scanf("%d", &T);
while (T--) {
ll sum = 0;
int n;
scanf("%d", &n);
for (int i = 0, x; i < n; i++) {
scanf("%d", &x);
sum ^= x;
}
for (int i = 0, u, v; i < n - 1; i++) scanf("%d%d", &u, &v);
if (!sum)
printf("D\n");
else
printf("Q\n");
}
}

L. Visual Cube

题意

画一个魔方…

分析

这种题目,首先要确定关键点的坐标,然后分块作图

分析

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
// ybmj
#include <bits/stdc++.h>
using namespace std;
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define lson_len (len - (len >> 1))
#define rson_len (len >> 1)
#define pb(x) push_back(x)
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const int maxn = 1000;
char maze[maxn][maxn];
int a, b, c;

void solve(pii lt, pii ld, pii rt, pii rd) {
for (int i = 1; i <= ld.first; i++)
for (int k = 1; k <= rt.second; k++) maze[i][k] = '.';
// center
int flag = 1;
for (int i = b * 2 + 1; i <= ld.first; i++) {
for (int k = 1; k <= a * 2 + 1; k++) {
if (flag) {
if (k & 1)
maze[i][k] = '+';
else
maze[i][k] = '-';
} else {
if (k & 1) maze[i][k] = '|';
}
}
flag ^= 1;
}
// top
flag = 1;
for (int i = 1; i < b * 2 + 1; i++) {
for (int k = b * 2 + 2 - i; k <= rt.second + 1 - i; k++) {
if (flag) {
if (k & 1)
maze[i][k] = '+';
else
maze[i][k] = '-';
} else {
if (!(k & 1)) maze[i][k] = '/';
}
}
flag ^= 1;
}
// right
flag = 1;
for (int k = rt.second; k >= rt.second - b * 2; k--) {
for (int i = rt.second - k + 1; i <= rt.second - k + 1 + 2 * c ;
i++) {
if (flag) {
if (i & 1)
maze[i][k] = '+';
else
maze[i][k] = '|';
} else {
if (!(i & 1)) maze[i][k] = '/';
}
}
flag ^= 1;
}
// out
for (int i = 1; i <= ld.first; i++) {
for (int k = 1; k <= rt.second; k++) printf("%c", maze[i][k]);
puts("");
}
}
int main() {
// /*
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
// */
std::ios::sync_with_stdio(false);
int T;
scanf("%d", &T);
while (T--) {
scanf("%d%d%d", &a, &b, &c);
pii lt = {1, 1};
pii ld = {c * 2 + 1 + b * 2, 1};
pii rt = {1, a * 2 + 1 + b * 2};
pii rd = {c * 2 + 1 + b * 2, a * 2 + 1 + b * 2};
solve(lt, ld, rt, rd);
}
}
Thank you for your support!