A. Adrien and Austin

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5;
int n, k;
int main()
{
    cin >> n >> k;
    if (n == 0) cout << "Austin\n";
    else if (k == 1) {
        if (n % 2) cout << "Adrien\n";
        else cout << "Austin\n";
    } else cout << "Adrien\n";
    return 0;
}

 

D. Country Meow

 

听说是红书上的板子

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include<bits/stdc++.h>
using namespace std;
 
struct point {
    double x, y, z;
    point(double xx = 0, double yy = 0, double zz = 0):
        x(xx), y(yy), z(zz) {}
};
 
double dist(point p1, point p2) {
    double dx = p1.x - p2.x, dy = p1.y - p2.y, dz = p1.z - p2.z;
    return dx * dx + dy * dy + dz * dz;
}
 
double dot(point p1, point p2) {
    return p1.x * p2.x + p1.y * p2.y + p1.z * p2.z;
}
 
const int INF = 0x3f3f3f3f, maxn = 1e2+5;
int npoint, nouter;
point pt[maxn], outer[4], res;
double radius, tmp;
const double eps = 1e-6;
 
void ball() {
    point q[3];
    double m[3][3], sol[3], L[3], det;
    int i, j;
    res.x = res.y = res.z = radius = 0;
    switch (nouter) {
    case 1:
        res = outer[0];
        break;
    case 2:
        res.x = (outer[0].x + outer[1].x) / 2;
        res.y = (outer[0].y + outer[1].y) / 2;
        res.z = (outer[0].z + outer[1].z) / 2;
        radius = dist(res, outer[0]);
        break;
    case 3:
        for (i = 0; i < 2; ++i) {
            q[i].x = outer[i + 1].x - outer[0].x;
            q[i].y = outer[i + 1].y - outer[0].y;
            q[i].z = outer[i + 1].z - outer[0].z;
            sol[i] = dot(q[i], q[i]);
        }
        for (i = 0; i < 2; ++i) for (j = 0; j < 2; ++j)
            m[i][j] = dot(q[i], q[j]) * 2;
        det = m[0][0] * m[1][1] - m[0][1] * m[1][0];
        if (fabs(det) < eps) return;
        L[0] = (sol[0] * m[1][1] - sol[1] * m[0][1]) / det;
        L[1] = (sol[1] * m[0][0] - sol[0] * m[1][0]) / det;
        res.x = outer[0].x + q[0].x * L[0] + q[1].x * L[1];
        res.y = outer[0].y + q[0].y * L[0] + q[1].y * L[1];
        res.z = outer[0].z + q[0].z * L[0] + q[1].z * L[1];
        radius = dist(res, outer[0]);
        break;
    case 4:
        for (i = 0; i < 3; ++i) {
            q[i].x = outer[i + 1].x - outer[0].x;
            q[i].y = outer[i + 1].y - outer[0].y;
            q[i].z = outer[i + 1].z - outer[0].z;
            sol[i] = dot(q[i], q[i]);
        }
        for (i = 0; i < 3; ++i) for (j = 0; j < 3; ++j)
            m[i][j] = dot(q[i], q[j]) * 2;
        det = m[0][0] * m[1][1] * m[2][2] +
              m[0][1] * m[1][2] * m[2][0] +
              m[0][2] * m[2][1] * m[1][0] -
              m[0][2] * m[1][1] * m[2][0] -
              m[0][1] * m[1][0] * m[2][2] -
              m[0][0] * m[1][2] * m[2][1];
        if (fabs(det) < eps) return;
        for (j = 0; j < 3; ++j) {
            for (i = 0; i < 3; ++i) m[i][j] = sol[i];
            L[j] =  (m[0][0] * m[1][1] * m[2][2] +
                  m[0][1] * m[1][2] * m[2][0] +
                  m[0][2] * m[2][1] * m[1][0] -
                  m[0][2] * m[1][1] * m[2][0] -
                  m[0][1] * m[1][0] * m[2][2] -
                  m[0][0] * m[1][2] * m[2][1]) / det;
            for (i = 0; i < 3; ++i) m[i][j] = dot(q[i], q[j]) * 2;
        }
        res = outer[0];
        for (i = 0; i < 3; ++i) {
            res.x += q[i].x * L[i];
            res.y += q[i].y * L[i];
            res.z += q[i].z * L[i];
        }
        radius = dist(res, outer[0]);
    }
}
 
void minball(int n) {
    ball();
    if (nouter < 4)
        for (int i = 0; i < n; ++i)
            if (dist(res,pt[i]) - radius > eps) {
                outer[nouter] = pt[i];
                ++nouter;
                minball(i);
                --nouter;
                if (i) {
                    point t = pt[i];
                    memmove(&pt[1], &pt[0], sizeof(point) * i);
                    pt[0] = t;
                }
            }
}
 
double smallest_ball() {
    radius = -1;
    for (int i = 0; i < npoint; ++i) {
        if (dist(res, pt[i]) - radius > eps) {
            nouter = 1;
            outer[0] = pt[i];
            minball(i);
        }
    }
    return sqrt(radius);
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> npoint;
    for (int i = 0; i < npoint; ++i) cin >> pt[i].x >> pt[i].y >> pt[i].z;
    printf("%.10f\n", smallest_ball());
    return 0;
}

 

G. Pyramid

 

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
#include<bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
long long T, n;
long long ex_gcd(long long a, long long b, long long &x, long long &y)
{
    if (!b) {
        x =  1;
        y = 0;
        return a;
    }
    long long ret = ex_gcd(b, a%b, y, x);
    y -= a/b * x;
    return ret;
}
 
inline long long get_inv(long long a, long long M)
{
    static long long x, y;
    assert(ex_gcd(a, M, x, y) == 1);
    return (x %M + M) % M;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    long long inv = get_inv(24, MOD);
    scanf("%lld", &T);
    while (T--) {
        scanf("%lld", &n);
        long long res = ((n+3)*(n+2) %MOD * (n+1) %MOD * (n) % MOD) * inv % MOD;
        printf("%lld\n", res);
    }
    return 0;
}

 

I. Magic Potion

 

二分图匹配

由于每个人最多只能喝一次药，所以把每个人复制一遍，建立二分图匹配。

由于最多只有k瓶药，所以得到的匹配数一定小于等于不喝药的匹配数+k。

现场第二次向图中复制点的时候错了，结果以为不能用匈牙利算法，但事实证明可以。

用网络流：从S连到所有people，从相应的people连到monster，再从S连一条容量为k的边，到点P，从P连到所有people。跑一遍最大流。

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
#include<bits/sdtc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5;
int n, m, k, V;
vector<int>G[maxn];
int match[maxn];
bool used[maxn];
int cnt[maxn];
void add_edge(int u, int v) {
	G[u].push_back(v);
	G[v].push_back(u);
}
bool dfs(int v) {
	used[v] = 1;
	for (int i = 0; i < G[v].size(); i++) {
		int u = G[v][i], w = match[u];
		if (w < 0 || !used[w] && dfs(w)) {
			match[v] = u;
			match[u] = v;
			return true;
		}
	}
	return false;
}
int bi_match() {
	int res = 0;
	memset(match, -1, sizeof(match));
	for (int v = 1; v <= V; v++) {
		if (match[v] < 0) {
			memset(used, 0, sizeof(used));
			if (dfs(v)) {
				res++;
			}
		}
	}
	return res;
}
int main() {
	scanf("%d%d%d", &n, &m, &k);
	V = n + m;
	for (int i = 1; i <= n; i++) {
		int p;
		scanf("%d", &p);
		cnt[i] = p;
		for (int j = 0; j < p; j++) {
			int q;
			scanf("%d", &q);
			add_edge(i, n + q);
		}
	}
	int ans = bi_match();
	if (k != 0) {
		V = 2 * n + m;
		for (int i = 1; i <= n; i++) {
			int p = cnt[i];
			for (int j = 0; j < p; j++) {
				int q = G[i][j];
				add_edge(i + m + n, q);
			}
		}
		ans = min(ans + k, bi_match());
	}
	printf("%d\n", ans);
	return 0;
}

 

J. Prime Game

 

dp[i]表示左端点在i，右端点在i到n的所有区间的答案之和。

则左端点往右更新时，先把左端点所在的长度为1的区间删掉，再把受到左端点影响的所有区间答案-1.至于有多少区间受到影响，需要预处理出来。

预处理质因数分解和dp[1]，以及每个元素在后面最近出现的位置。

质因数分解的时候用vector会很慢，用数组很快。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6 + 10;
int n;
int a[maxn];
map<int, map<int, int> >pos;
int p[maxn];
ll dp[maxn];
set<int>st;
bool is_prime[maxn];
int cnt[maxn];
int vc[maxn][30];
void sieve(int n) {
	for (int i = 0; i <= n; i++)is_prime[i] = true;
	is_prime[0] = is_prime[1] = false;
	for (int i = 2; i <= n; i++) {
		if (is_prime[i]) {
			vc[i][cnt[i]++] = i;
			for (int j = 2 * i; j <= n; j += i) {
				vc[j][cnt[j]++] = i;
				is_prime[j] = false;
			}
		}
	}
}
ll ans = 0;
int main() {
	sieve(1000000);
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < cnt[a[i]]; j++) {
			st.insert(vc[a[i]][j]);
		}
		dp[1] += (ll)st.size();
	}
	for (int i = 1; i < maxn; i++)p[i] = n + 1;
	for (int i = n; i >= 1; i--) {
		for (int j = 0; j < cnt[a[i]]; j++) {
			int v = vc[a[i]][j];
			pos[i][v] = p[v];
			p[v] = i;
		}
	}
	for (int i = 2; i <= n; i++) {
		dp[i] = dp[i - 1] - (ll)cnt[a[i-1]];
		for (int j = 0; j < cnt[a[i-1]]; j++) {
			int v = vc[a[i-1]][j];
			dp[i] -= (ll)(pos[i-1][v] - i);
		}
	}
	for (int i = 1; i <= n; i++) {
		ans += dp[i];
	}
	cout << ans << endl;
	return 0;
}

 

M. Mediocre String Problem

 

拓展KMP+Manacher

题意：有两个字符串s，t，要求从s中取出一段子串，从t中取出一段前缀，s的子串在前，t的前缀在后，拼成一个回文串，并且取出的s的子串的长度要严格大于取出的t的前缀的长度，求不同取法的个数。

找回文串的问题可以自然想到转化为找相同串。把S串倒过来，则只需要在新的串S’ 中找与t串有公共前缀的子串。拓展KMP算法找到S’ 串的每一个后缀与t串的最长公共前缀，但这两个相同串之间必然需要包含一个回文串，否则不满足严格大于的条件。则相当于需要找到原S串以某个位置k开头的回文串个数，用Manacher可以得到每个对称轴的最长回文半径，加上前缀和，即可得到以每个位置为开头的回文串个数。

枚举每一个公共前缀，由于回文串不断往对称轴缩进仍然是回文串，所以公共前缀的长度可以不断减小，仍然保持回文串。则S’ 串每一个位置对答案的贡献为公共前缀的长度* 以当前位置为右端点的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
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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int maxn = 1e7 + 10;
char s[maxn], p[maxn];
ll cnt[maxn], a[maxn];
ll ans;
int nxt[maxn], extend[maxn];
void getNext(char str[])
{
	int i = 0, j, po, len = strlen(str);
	nxt[0] = len;
	while (str[i] == str[i + 1] && i + 1 < len) i++; nxt[1] = i;
	po = 1;
	for (i = 2; i < len; i++)
	{
		if (nxt[i - po] + i < nxt[po] + po)
			nxt[i] = nxt[i - po];
		else
		{
			j = nxt[po] + po - i;
			if (j < 0) j = 0;
			while (i + j < len && str[j] == str[j + i]) j++; nxt[i] = j;
			po = i;
		}
	}
}
 
void exkmp(char s1[], char s2[])
{
	int i = 0, j, po, len = strlen(s1), l2 = strlen(s2);
	getNext(s2);
	while (s1[i] == s2[i] && i < l2 && i < len) i++; extend[0] = i;
	po = 0;
	for (i = 1; i < len; i++)
	{
		if (nxt[i - po] + i < extend[po] + po)
			extend[i] = nxt[i - po];
		else
		{
			j = extend[po] + po - i;
			if (j < 0) j = 0;
			while (i + j < len && j < l2 && s1[j + i] == s2[j]) j++; extend[i] = j;
			po = i;
		}
	}
}
char Ma[maxn * 2];
int Mp[maxn * 2];
void Manacher(char s[], int len) {
	int l = 0;
	Ma[l++] = '$';
	Ma[l++] = '#';
	for (int i = 0; i < len; i++) {
		Ma[l++] = s[i];
		Ma[l++] = '#';
	}
	Ma[l] = 0;
	int mx = 0, id = 0;
	for (int i = 0; i < l; i++) {
		Mp[i] = mx > i ? min(Mp[2 * id - i], mx - i) : 1;
		while (Ma[i + Mp[i]] == Ma[i - Mp[i]])Mp[i]++;
		if (i + Mp[i] > mx) {
			mx = i + Mp[i];
			id = i;
		}
	}
}
int main() {
	scanf("%s%s", s, p);
	int n = strlen(s), m = strlen(p);
	reverse(s, s + n);
	Manacher(s, n);
	for (int i = 0; i < 2 * n + 2; i++) {
		cnt[i / 2]++;
		cnt[(i + Mp[i] - 1) / 2]--;
	}
	for (int i = 1; i < n; i++) {
		cnt[i] += cnt[i - 1];
	}
	for (int i = 0; i < n; i++)cnt[i]++;
	exkmp(s, p);
	for (int i = 1; i < n; i++) {
		if (extend[i] == 0)continue;
		ans += extend[i] * cnt[i - 1];
	}
	cout << ans << endl;
	return 0;
}