比赛题目训练系列03 (2020 ICPC Universidad Nacional de Colombia Programming Contest)
顺便提一嘴这个公式（北师2020校赛）：
(
C
n
0
)
3
−
(
C
n
1
)
3
+
(
C
n
2
)
3
−
.
.
.
+
(
−
1
)
n
C
n
n
=
{
0
,
n
为
奇
数
(
3
n
)
!
(
n
!
)
3
.
(C_{n}^{0})^3 - (C_{n}^{1})^3 + (C_{n}^{2})^3 - ... + (-1)^nC_{n}^{n} = \begin{cases}0,n为奇数\\ \frac{(3n)!}{(n!)^3}. \end{cases}
(Cn0)3−(Cn1)3+(Cn2)3−...+(−1)nCnn={0,n为奇数(n!)3(3n)!.
A. Approach
- 一个人从 A 走到 B，一个人从 C 走到 D. 同时出发，相同的速度，到终点即停止。问他们最短距离是多少。
- 浮点数有误差，这个题栽了一下。float 精度是 6~7 位，double 精度是 14 ~ 15 位。
- 另外一个小心的地方，就是在把向量标准化的时候，以及求二次函数对称轴的时候，小心分母会出现为0的情况。
- 这个题思路很简单，分为两个过程，一个人先停下来，第二个人再停下来。然后用向量表示两者的距离。第一个过程两人距离是 ∣ ( x 1 + v 1 t ) − ( x 2 + v 2 t ) ∣ |(\bold{x_1} + \bold{v_1}t) - (\bold{x_2} + \bold{v_2}t)| ∣(x1+v1t)−(x2+v2t)∣ 。第二个过程是 ∣ x 2 + v 1 t − x 3 ∣ |\bold{x_2} + \bold{v_1}t - \bold{x_3}| ∣x2+v1t−x3∣. 可以平方一下，就转化为二次函数。也可以三分求最值。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define x first
#define y second
using namespace std;
const double eps = 1e-8;
int sign(double x) {
if (fabs(x) < eps) return 0;
if (x < 0) return -1;
return 1;
}
double min_f(double a, double b, double c, double t1, double t2) {
if (a == 0) {
if (b > 0) return t1;
else return t2;
}
else {
double s = -b / (2 * a);
if (s < t1) return t1;
else if (s < t2) return s;
return t2;
}
}
typedef pair<double, double> P;
P operator -(P a, P b) {
return { a.x - b.x, a.y - b.y };
}
P operator +(P a, P b) {
return { a.x + b.x, a.y + b.y };
}
double operator * (P a, P b) {
return a.x * b.x + a.y * b.y;
}
P operator *(P a, double t) {
return { a.x * t, a.y * t };
}
P operator / (P a, double t) {
return { a.x / t, a.y / t };
}
double len(P p) {
return sqrt(p * p);
}
P normalize(P p) {
if (!sign(len(p))) return { 0, 0 };
return p / len(p);
}
int main() {
P A, B, C, D;
cin >> A.x >> A.y >> B.x >> B.y >> C.x >> C.y >> D.x >> D.y;
if (len(B - A) > len(D - C)) swap(A, C), swap(B, D);
P V1 = normalize(B - A), V2 = normalize(D - C);
double a, b, c;
a = (V1 - V2) * (V1 - V2), b = (A - C) * (V1 - V2) * 2, c = (A - C) * (A - C);
double t1 = len(B - A);
double res1 = min_f(a, b, c, 0, t1);
double ans1 = len(A + V1 * res1 - C - V2 * res1);
double t2 = len(D - C);
a = V2 * V2, b = (C - B) * V2 * 2, c = (C - B) * (C - B);
double res2 = min_f(a, b, c, t1, t2);
double ans2 = len(C + V2 * res2 - B);
printf("%.10f\n", fabs(min(ans1, ans2)));
return 0;
}
C. Cipher count
- 题意转述：求由 a a a 种字母组成的长度为 k k k 的字符串，最小循环节为其自身的数量是多少。
- 首先，我们考虑长度为 i 的字符串的数量是多少，答案就是 a i a^i ai，那么，我们可以类比埃氏筛，有多少个不满足要求的串呢？我们找到所有能够整除 i i i 的数 d d d。那么，由 f ( d ) f(d) f(d) 拼成长度为 k k k 的字符串都是不满足要求的，都要减掉。这样，很自然地就推出了 f ( i ) = a i − ∑ d ∣ i f ( d ) f(i) = a^i - \sum\limits_{d|i}f(d) f(i)=ai−d∣i∑f(d). 最后的答案就是 ∑ i = 1 k f ( i ) \sum\limits_{i=1}^{k}f(i) i=1∑kf(i)
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int maxn = 5000010;
ll f[maxn];
int main() {
ll A, K;
scanf("%lld%lld", &A, &K);
f[0] = 1;
for (int i = 1; i <= K; i++) f[i] = f[i - 1] * A % mod;
for (int i = 1; i <= K; i++) {
for (int j = 2 * i; j <= K; j += i) f[j] = (f[j] - f[i] + mod) % mod;
}
ll ans = 0;
for (int i = 1; i <= K; i++) ans = (ans + f[i]) % mod;
printf("%lld\n", ans);
return 0;
}
D. Dice
- 题意：题意：有 n n n 个 k k k 面的骰子， k k k 面编号分别为 1 , 2 , 3 , , , k 1,2,3,,,k 1,2,3,,,k，Diego对这些筛子进行了一些操作，使它们都不能摇到编号是 m m m 的倍数那一面，摇到其他面的概率相同。问：抛完这 n n n 个骰子，它们的结果相加后得到一个 m m m 的倍数的概率。
- 设 n 个骰子凑出 i 的方案数为
P
n
(
i
)
P_n(i)
Pn(i)，则
P
n
(
i
)
=
∑
P
n
−
1
(
x
)
∗
P
n
−
1
(
y
)
,
(
x
+
y
)
m
o
d
m
=
=
i
.
P_n(i) = \sum P_{n-1}(x) * P_{n-1}(y), (x + y) \ mod\ m ==i.
Pn(i)=∑Pn−1(x)∗Pn−1(y),(x+y) mod m==i. 显然，用快速幂可以解决这个问题。
( a 0 ( n ) a 1 ( n ) . . . a m − 1 ( n ) ) = ( a 0 ( 1 ) a m − 1 ( 1 ) . . . a 1 ( 1 ) a 1 ( 1 ) a 0 ( 1 ) . . . a m − 2 ( 1 ) . . . a m − 1 ( 1 ) a m − 2 ( 1 ) . . . a 0 ( 1 ) ) n − 1 ( a 0 ( 1 ) a 1 ( 1 ) . . . a m − 1 ( 1 ) ) \begin{pmatrix}a_0^{(n)} \\a_1^{(n)} \\.\\.\\.\\a_{m-1}^{(n)}\end{pmatrix} = \begin{pmatrix}a_0^{(1)} & a_{m-1}^{(1)} &.&.&.&a_{1}^{(1)}\\a_{1}^{(1)} &a_{0}^{(1)}&.&.&.&a_{m-2}^{(1)}\\.\\.\\.\\a_{m-1}^{(1)} &a_{m-2}^{(1)}&.&.&.&a_{0}^{(1)}\end{pmatrix}^{n-1}\begin{pmatrix}a_0^{(1)} \\a_1^{(1)} \\.\\.\\.\\a_{m-1}^{(1)}\end{pmatrix} ⎝⎜⎜⎜⎜⎜⎜⎜⎛a0(n)a1(n)...am−1(n)⎠⎟⎟⎟⎟⎟⎟⎟⎞=⎝⎜⎜⎜⎜⎜⎜⎜⎛a0(1)a1(1)...am−1(1)am−1(1)a0(1)am−2(1).........a1(1)am−2(1)a0(1)⎠⎟⎟⎟⎟⎟⎟⎟⎞n−1⎝⎜⎜⎜⎜⎜⎜⎜⎛a0(1)a1(1)...am−1(1)⎠⎟⎟⎟⎟⎟⎟⎟⎞
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 210;
typedef long long ll;
const ll mod = 1000000007;
ll a[maxn], f[maxn][maxn], N, K, M;
ll mod_pow(ll x, ll n) {
ll res = 1;
while (n) {
if (n & 1) res = res * x % mod;
x = x * x % mod;
n >>= 1;
}
return res;
}
void mul(ll c[], ll a[], ll b[][maxn]) {
ll tmp[maxn] = { 0 };
for (int i = 0; i < M; i++) {
for (int j = 0; j < M; j++) {
tmp[i] = (tmp[i] + b[i][j] * a[j]) % mod;
}
}
memcpy(c, tmp, sizeof tmp);
}
void mul(ll c[][maxn], ll a[][maxn], ll b[][maxn]) {
ll tmp[maxn][maxn] = { 0 };
for (int i = 0; i < M; i++) {
for (int j = 0; j < M; j++) {
for (int k = 0; k < M; k++) {
tmp[i][j] = (tmp[i][j] + a[i][k] * b[k][j]) % mod;
}
}
}
memcpy(c, tmp, sizeof tmp);
}
int main() {
scanf("%lld%lld%lld", &N, &K, &M);
for (int i = 0; i < M; i++) {
a[i] = K / M;
}
for (ll i = K / M * M + 1; i <= K; i++) {
a[i % M]++;
}
a[0] = 0;
for (int i = 0; i < M; i++) {
for (int j = 0; j < M; j++) {
f[i][j] = a[(M - j + i) % M];
//printf("%lld ", a[(M - j + i) % M]);
}
//cout << endl;
}
ll n = N - 1;
while (n) {
if (n & 1) mul(a, a, f);
mul(f, f, f);
n >>= 1;
}
//printf("%lld %lld\n", a[0], mod_pow(mod_pow(K - K / M, N), mod - 2) % mod);
ll ans = a[0] * mod_pow(mod_pow(K - K / M, N), mod - 2) % mod;
printf("%lld\n", ans);
return 0;
}
H. Happy game
- 题意：求一个字符串中有多少个本质不同回文子串，且这些子串的长度为奇数
- 马拉车算法+字符串哈希。因为马拉车算法有一个这样的性质，就是可以找到所有长度为奇数的回文子串（因此，为了找到偶数回文子串，需要将字符串扩展），而字符串哈希可以在 O(1) 的时间判断本质不同的串。
- 小心字符串哈希，base[0] 一定要初始化为 1.
#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_set>
using namespace std;
const int maxn = 100010;
typedef unsigned long long ll;
char str[maxn];
int p[maxn], N;
unordered_set<ll> substr;
ll h[maxn], base[maxn];
const ll P = 131;
void Hash(int N) {
base[0] = 1;
for (int i = 1; i <= N; i++) {
h[i] = h[i - 1] * P + str[i];
base[i] = base[i - 1] * P;
}
}
ll get(int l, int r) {
return h[r] - h[l - 1] * base[r - l + 1];
}
void insert(int l, int r) {
if (r - l + 1 == 1) return;
substr.insert(get(l, r));
}
void manacher() {
str[0] = '$', str[N + 1] = '^';
int mr = 0, mid;
for (int i = 1; i <= N; i++) {
if (i < mr) p[i] = min(p[2 * mid - i], mr - i);
else p[i] = 1;
while (str[i - p[i]] == str[i + p[i]]) {
p[i]++;
insert(i - p[i] + 1, i + p[i] - 1);
}
if (i + p[i] > mr) {
mr = i + p[i];
mid = i;
}
}
}
int main() {
scanf("%d%s", &N, str + 1);
Hash(N);
manacher();
printf("%d\n", substr.size());
return 0;
}
I. Incredible photography
- 题意：给你一段序列，以某点为起点，你的移动规则是找到一个你能看到的高度严格大于你的点，然后你可以移动到那个点，之后又可以以相同的规则进行移动。求出以每个点为起点时能移动的最长距离。
- 很显然是单调栈+拓扑图最长路径。但是有一个关键的问题，就是这个找的是每个数向左看，和比他大的数第一个数相等的，且距离离他最远数。那么这个其实很简单，就是在维护单调栈的时候，如果出现
a[stk[tt]] == a[i]的情况，就把这个 stk[tt] 记录下来。后面往单调栈里面推入数字的时候，不推入 i 而推入 stk[tt]。这样子，就算出现 5 3 5 5 3 5 这样子的东西，就算中间数字不是连续的，也是可以正确的找到离他最远的符合要求的那个数字。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
const int maxn = 100010, maxm = 200010;
int h[maxn], e[maxm], ne[maxm], w[maxm], idx;
int a[maxn], N, stk[maxn];
int din[maxn];
ll f[maxn];
void add(int a, int b, int c) {
swap(a, b);
din[b]++;
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
void build1() {
int tt = 0;
for (int i = 1; i <= N; i++) {
bool flag = false;
//小心 id 别设置成 bool 类型喽
int id;
while (tt && a[stk[tt]] < a[i]) tt--;
//小心别写成 tt & a[stk[tt]] == a[i] !!!
if (tt && a[stk[tt]] == a[i]) {
flag = true, id = stk[tt];
tt--;
}
if (tt) add(i, stk[tt], i - stk[tt]);
if (flag) {
stk[++tt] = id;
}
else stk[++tt] = i;
}
}
void build2() {
int tt = 0;
for (int i = N; i >= 1; i--) {
bool flag = false;
int id;
while (tt && a[stk[tt]] < a[i]) tt--;
if (tt && a[stk[tt]] == a[i]) {
flag = true, id = stk[tt];
tt--;
}
if (tt) add(i, stk[tt], stk[tt] - i);
if (flag) {
stk[++tt] = id;
}
else stk[++tt] = i;
}
}
void toposort() {
queue<int> que;
for (int i = 1; i <= N; i++) {
if (din[i] == 0) {
que.push(i);
}
}
while (que.size()) {
int u = que.front(); que.pop();
for (int i = h[u]; i != -1; i = ne[i]) {
int v = e[i];
f[v] = max(f[v], f[u] + w[i]);
if (--din[v] == 0) que.push(v);
}
}
}
int main() {
memset(h, -1, sizeof h);
scanf("%d", &N);
for (int i = 1; i <= N; i++) scanf("%d", &a[i]);
build1();
build2();
//for (int i = 1; i <= N; i++) {
// for (int j = h[i]; j != -1; j = ne[j]) {
// int v = e[j];
// printf("%d %d %d\n", i, v, w[j]);
// }
// printf("*** %d\n", din[i]);
//}
toposort();
for (int i = 1; i <= N; i++) {
printf("%lld%c", f[i], i == N ? '\n' : ' ');
}
return 0;
}