大家好，又见面了，我是全栈君。
比赛地址
第十届北航程序设计竞赛网络预赛
A. face the truth
题意：
“差点儿全部队伍都通过了题目”的含义是“有超过一半的队伍过了题目”。如今n个队里有m个队伍通过了题目。问是不是差点儿全部队伍都通过了题目。
题解：
读懂题。
代码：
#include <cstdio>
int n, m;
int main()
{
while(scanf("%d%d", &n, &m) == 2)
puts(n < m * 2 ? "Wonderful Contest!" : "_(:3_|Z)_");
return 0;
}
B. flame of despair
题意：
给定m个数字串{x_i}，请你构造一个最小的数字串包括这些数，且是n的倍数，求满足条件的最小解。
n <= 1000, m <= 5, x_i < 10^9。
题解：
说是包括某个数字，不如说是与某个串匹配成功，多模板串匹配能够想到使用AC自己主动机。
每一个数字至少匹配一次。能够想到利用二进制的0和1来表示某个数字是否已经匹配过，最多有2 ^ m种匹配状态。
说到n的倍数，做过vijos P1065 最小数字倍数非常easy想到利用模n的余来表示是否是n的倍数。（没做过也能够想到
大概能够想到一种定义状态的方法，dp[自己主动机节点][模n余数][匹配状态]能够表示一个唯一的状态的最小数字长度。
考虑状态转移。则是枚举一个加在末尾的数字d，那么dp[i][j][k]能够转移到dp[i’][(j * 10 + d) % n][k’]。当中i’表示在节点i处再用d做匹配得到的新节点，k’表示到新节点之后的新匹配状态，尽管有可能会出现状态转移的环。可是走环必然会使解变差。所以不用考虑环的问题。
考虑最小解。我们发现仅仅要从dp[i][j][k]比較小的開始，不断地拓展。直到达到某个点的匹配状态为m个数字均被匹配，不难想到利用bfs来维护这个性质。
所以能够想到的解法是：起始状态是向空串加0~9的那9个状态，通过bfs到达终态。将转移路径上使用的数字输出。注意答案不可能为-1，由于能够生成的数是正整数全集。
时间复杂度O(nm2^mlogx)。
代码：
代码中AC自己主动机的last指针是存后缀连接用的，val表示存的数字标号，实际上仅仅须要用fail指针就能够做这道题了。
#include <cstdio>
#include <cstring>
const int maxn = 1010, maxw = 50, maxsize = 10, maxs = 33;
int n, m, tot;
struct AC
{
int ch[maxsize], fail, last, val;
} trie[maxw];
void insert(int no)
{
int x, now = 0, len = 0, num[10] = {};
scanf("%d", &x);
while(x)
{
num[len++] = x % 10;
x /= 10;
}
for(int i = len - 1; i >= 0; --i)
{
if(!trie[now].ch[num[i]])
trie[now].ch[num[i]] = ++tot;
now = trie[now].ch[num[i]];
}
trie[now].val = no;
}
void build()
{
int que[maxn], l = 0, r = 0;
for(int i = 0; i < maxsize; ++i)
if(trie[0].ch[i])
que[r++] = trie[0].ch[i];
while(l != r)
for(int i = 0, now = que[l++]; i < maxsize; ++i)
if(trie[now].ch[i])
{
int u = trie[now].ch[i], v = trie[now].fail;
que[r++] = u;
if(r >= maxw)
r = 0;
while(v && !trie[v].ch[i])
v = trie[v].fail;
trie[u].fail = v = trie[v].ch[i];
trie[u].last = trie[v].val ? v : trie[v].last;
trie[u].val = trie[u].val ? trie[u].val : trie[trie[u].last].val; }}int SD(int o, int r, int z){ return (o * maxn + r) * maxs + z;}void DS(const int &id, int &s, int &t, int &q){ s = id / maxs / maxn; t = id / maxs % maxn; q = id % maxs;}int l, r, que[maxw * maxn * maxs + 123], pre[maxw * maxn * maxs + 123][2], ans[maxw * maxn * maxs + 123], len;bool f[maxw][maxn][maxs], flag;int main(){ while(scanf("%d%d", &n, &m) == 2) { int maxk = 1 << m; tot = 0; memset(trie, 0, sizeof trie); for(int i = 1; i <= m; ++i) insert(i); build(); memset(f, 0, sizeof f); l = r = flag = 0; f[0][0][0] = 1; que[r++] = SD(0, 0, 0); while(l < r) { int i, j, k; DS(que[l], i, j, k); for(int t = 0; t < maxsize; ++t) { int v = i, jj = (j * 10 + t) % n, kk = k; while(v && !trie[v].ch[t]) v = trie[v].fail; if(trie[v].ch[t]) v = trie[v].ch[t]; for(int vv = v; trie[vv].val; vv = trie[vv].last) kk |= 1 << trie[vv].val - 1; if(!jj && kk + 1 == maxk) { pre[r][0] = l; pre[r][1] = t; que[r] = SD(v, jj, kk); flag = 1; break; } if(!f[v][jj][kk]) { pre[r][0] = l; pre[r][1] = t; que[r++] = SD(v, jj, kk); f[v][jj][kk] = 1; } for(int vv = v; trie[vv].val; vv = trie[vv].last) if(!f[vv][jj][kk]) { pre[r][0] = l; pre[r][1] = t; que[r++] = SD(vv, jj, kk); f[vv][jj][kk] = 1; } } if(flag) break; ++l; } if(flag) { int i, j, k, jj; len = 0; while(r > 0) { ans[len++] = pre[r][1]; r = pre[r][0]; } for(i = len - 1; i >= 0; --i) printf("%d", ans[i]); putchar('\n'); } else puts("-1"); } return 0;}
C. he is…
题意：
给定一个字母组成的字符串。找出里面仅仅出现一次的大写或小写字母，假设有多解或者无解输出-1。
题解：
统计。扫一遍。
代码：
#include <cstdio>
char str[233333];
int main()
{
while(scanf("%s", str) == 1)
{
int pos1, pos2, sum1 = 0, sum2 = 0;
for(int i = 0; str[i]; ++i)
if(str[i] >= 'a' && str[i] <= 'z')
{
pos1 = i;
++sum1;
}
else if(str[i] >= 'A' && str[i] <= 'Z')
{
pos2 = i;
++sum2;
}
if(sum1 == 1 && sum2 != 1)
printf("%d\n", pos1 + 1);
else if(sum1 != 1 && sum2 == 1)
printf("%d\n", pos2 + 1);
else
puts("-1");
}
return 0;
}
D. 幻想乡的危机
题意：
给定一个二分图，左边的数为0 ~ 2 ^ n – 1，右边的数为0 ~ 2 ^ m – 1，随意两点i和j间的边权为i xor j，求最大权匹配。
n, m <= 10。
题解：
考虑当n = m的时候是0 ~ 2 ^ n – 1与0 ~ 2 ^ n – 1匹配，而左边不论什么一个数i都能够在右边找到唯一的一个数j。使得j是i取反后的数字。这样的映射是一一相应的，即每一个点都能匹配到末n个二进制位为1的边。
再考虑n ≠ m的情况，最好还是设n < m，则m里最多选2 ^ n个数字去和左边的匹配，而左边的数除了末n位之外都是0，最好还是从m这边全选高位为1的，则能够匹配到最大值。
故，共2 ^ min{n, m}对点匹配。每条边的权值都为2 ^ max{n, m} – 1。
代码：
#include <cstdio>
int n, m;
void swap(int &x, int &y)
{
int t = x;
x = y;
y = t;
}
int main()
{
while(scanf("%d%d", &n, &m) == 2)
{
if(n < m)
swap(n, m);
printf("%d\n", ((1 << n) - 1) * (1 << m));
}
return 0;
}
E. 了不起的Th0r
题意：
给定n个阶段，每一个阶段有一个能力值，这个能力值是等概率在[1, p]间取的正整数。
求n个阶段能力值一直不低于f1或者至少连续k个阶段能力一直不低于f2的概率。保证2 * k > n。
n <= 300, p <= 1000, k <= 300, f1 <= f2 <= 1000。
题解：
看到“或”想到容斥原理来做。P(A ∪ B) = P(A) + P(B) – P(A ∩ B)。
首先设某阶段能力值不低于f1的概率为e1，不低于f2的概率为e2。
第一种情况非常显然是e1 ^ n。
在n > k的时候要考虑另外一种情况。
另外一种情况能够看作是连续k个阶段能力不低于f2，后来的概率随意。
而在2 * k > n的约束下，最多同一时候有这样一个超常发挥的区间。能够通过枚举这个区间的起点统计。
这个区间的起点满足：假设不是从第一个阶段開始，那么这个阶段之前的一个阶段能力没有达到f2。
则另外一种情况的概率为e2 ^ k + (n – k) * (1 – e2) * e2 ^ k。
两种情况同一时候满足，即有连续k个阶段能力不低于f2，其余阶段能力不低于f1，则能够算出是e2 ^ k * e1 ^ (n – k) + (n – k) * (e1 – e2) * e2 ^ k * e1 ^ (n – k – 1)。
代码：
实际上不须要使用long double，也不须要手写pow。
#include <cstdio>
#include <cstring>
int n, p, k, f1, f2;
long double E1, E2, E3, E4, x;
long double pow(long double x, int k)
{
if(k < 0)
return 0;
long double ret = 1.0;
while(k)
{
if(k & 1)
ret = ret * x;
x = x * x;
k >>= 1;
}
return ret;
}
int main()
{
while(scanf("%d%d%d%d%d", &n, &p, &k, &f1, &f2) == 5)
{
E1 = p >= f1 ? (p - f1 + 1.0) / p : 0; E2 = p >= f2 ? (p - f2 + 1.0) / p : 0; E3 = E1 - E2; E4 = 1 - E2; x = pow(E1, n); if(n > k) x += pow(E2, k) * ((n - k) * E4 + 1 - pow(E1, n - k - 1) * ((n - k) * E3 + E1)); printf("%.3f\n", (double)x); } return 0;}
F. 子串
题意：
给定两个字符串A和B，求A的一个子序列等于B的一个子串或者B的一个子序列等于A的一个子串，这个子序列的间隔中浪费不超过k的字符，求最长的子串长度。
设n和m是字符串A、B的长度，则0 < n, m <= 100, k <= 100。
题解：
当然是做两遍咯，A串考虑子序列。B串考虑子串。
f[i][j][k]能够表示A的前i个字符与B的前j个字符浪费恰好k个字符时最长匹配的长度。pos[i][j][k]表示f[i][j][k]上一次匹配成功的位置。
非常easy想到怎么做。注意一下最開始就可以。
时间复杂度O(nmk)。
代码：
#include <cstdio>
#include <cstring>
int n, m, k, f[111][111][111], pos[111][111][111];
int solve(char s[], char t[])
{
int ans = 0;
n = strlen(s + 1);
m = strlen(t + 1);
memset(f, 0, sizeof f);
memset(pos, 0, sizeof pos);
for(int i = 0; i <= n; ++i)
for(int j = 0; j <= m; ++j)
for(int o = 0; o <= k; ++o)
{
if(ans < f[i][j][o])
ans = f[i][j][o];
if(i < n && (f[i + 1][j][o] < f[i][j][o] || f[i + 1][j][o] == f[i][j][o] && pos[i + 1][j][o] < pos[i][j][o]))
{
f[i + 1][j][o] = f[i][j][o];
pos[i + 1][j][o] = pos[i][j][o];
}
if(i < n && j < m && s[i + 1] == t[j + 1])
{
int oo = o + (pos[i][j][o] ? i - pos[i][j][o] : 0);
if(oo <= k && f[i + 1][j + 1][oo] <= f[i][j][o] + 1)
{
f[i + 1][j + 1][oo] = f[i][j][o] + 1;
pos[i + 1][j + 1][oo] = i + 1;
}
}
}
return ans;
}
int max(int x, int y)
{
return x < y ? y : x;
}
int main()
{
char s[110], t[110];
while(scanf("%s%s%d", s + 1, t + 1, &k) == 3)
printf("%d\n", max(solve(s, t), solve(t, s)));
return 0;
}
G. 奇怪的强迫症
题意：
给定一个n * m的双色矩阵，求有多少个子矩阵也是双色的。
n, m <= 1000
题解：
算反面，总的子矩阵个数为n * (n – 1) * m * (m – 1) / 4，双色矩阵个数等于总矩阵个数减去单色矩阵个数。
单色矩阵的个数等于把每一个点当作右下角，向左向上延伸能达到的同色点的个数之和。
每一个点上的问题能够利用单调栈做，按行使用单调栈则须要先预处理列上能延伸的距离，按列的话同理。
时间复杂度O(nm)。
代码：
#include <cstdio>
#include <cstring>
const int maxn = 1010;
typedef long long LL;
LL n, m, h[maxn][maxn], top, hh[maxn], no[maxn], sum, ans;
char str[maxn][maxn];
int main()
{
while(scanf("%lld%lld", &n, &m) == 2)
{
for(LL i = 1; i <= n; ++i)
scanf("%s", str[i] + 1);
for(LL j = 1; j <= m; ++j)
for(LL i = 1; i <= n; ++i)
h[i][j] = str[i][j] == str[i - 1][j] ? h[i - 1][j] + 1 : 1; ans = n * (n + 1) / 2 * m * (m + 1) / 2; for(LL i = 1; i <= n; ++i) for(LL j = 1; j <= m; ++j) { if(str[i][j] != str[i][j - 1]) { top = 0; no[top] = j - 1; sum = 0; } while(top > 0 && h[i][j] <= hh[top]) { sum -= hh[top] * (no[top] - no[top - 1]); --top; } hh[++top] = h[i][j]; no[top] = j; sum += hh[top] * (no[top] - no[top - 1]); ans -= sum; } printf("%lld\n", ans); } return 0;}
H. 节操君与他的粉丝
题意：
给定三组点{a_i}、{b_i}和{c_i}。点数分别为n、m和q，每组点的横坐标同样，纵坐标递增。将随意两点连起来的代价是两点间的欧几里得距离，求将全部点连起来所需的最小代价。
n, m <= 10000, q <= 5, |坐标| <= 10^9。
题解：
题目问的也能够说是用最短最少的边将全部点连起来。一个不难想到的方法是将全部点互相连边，从中选出点数减一条边，将全部点连成一颗最小生成树。
若总点数为N。则总边数是O(N^2)的。建图就会超时。
我们考虑一下建图，发现有很多没用的边。
有一个定理：平面最小生成树是角最优三角剖分的一个子集。
首先看一下什么是三角剖分：（from 百度百科）
如果V是二维实数域上的有限点集。边e是由点集中的点作为端点构成的封闭线段, E为e的集合。 那么该点集V的一个三角剖分T = (V, E)是一个平面图G。该平面图满足 1.除了端点，平面图中的边不包括点集中的不论什么点。 2.没有相交边。 3.平面图中全部的面都是三角面，且全部三角面的合集是散点集V的凸包。
Delaunay三角剖分满足一个性质：（from 百度百科）
存在一个圆经过a, b两点，圆内(注意是圆内，圆上最多三点共圆)不含点集V中不论什么其它的点，这一特性又称空圆特性。
那么我们能够证明上面的定理：（from 王栋《浅析平面Voronoi图的构造及应用》）
设角最优三角剖分为DT(S)，最小生成树为MST，如果存在一条边ab∈DT(S)，则由三角剖分的定理能够知道过a, b有一个空圆。因此如果ab不属于DT(S)，那么过a, b的圆不可能是空的。也就是说。具有直径ab的圆周上或圆内必有S中的点。如果c在该圆周上或者圆内，那么|ac|<|ab|，而且|bc|<|ab|。那么，我们删除ab，把树T分成Ta和Tb两部分。最好还是如果c∈Ta。那么我们加入边cb，能够合并成新的树，而且的总长度小于T。因此包括ab的树长度不可能是最小的。
所以必定MST∈DT(S)。
所以仅仅要我们建立的图包括Delaunay三角剖分，那么对其求最小生成树一定最优。
前两组点互相找纵坐标相差最小的两个点连边。前两组点对第三组点全部点连边，随意一组点内相邻点连边。再求最小生成树就可以。
代码：
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn = 21000;
int n, m, q, tot;
double ans;
struct point
{
LL x, y;
} a[maxn], b[maxn], c[maxn];
LL dist(const point &a, const point &b)
{
return (a.x - b.x) * (a.x - b.x) + (b.y - a.y) * (b.y - a.y);
}
struct edge
{
int u, v;
LL w;
bool operator < (const edge &x) const
{
return w < x.w;
}
} e[maxn * 20];
int fa[maxn];
int find(int x)
{
return x == fa[x] ? x : fa[x] = find(fa[x]);}int main(){ while(scanf("%d%d%d", &n, &m, &q) == 3) { for(int i = 1; i <= n; ++i) scanf("%lld%lld", &a[i].x, &a[i].y); for(int i = 1; i <= m; ++i) scanf("%lld%lld", &b[i].x, &b[i].y); for(int i = 1; i <= q; ++i) scanf("%lld%lld", &c[i].x, &c[i].y); tot = 0; for(int i = 1, j = 1; i <= n; ++i) { while(j < m && b[j].y < a[i].y) ++j; if(i > 1) e[tot++] = (edge){i - 1, i, dist(a[i - 1], a[i])}; if(j > 1) e[tot++] = (edge){i, n + j - 1, dist(a[i], b[j - 1])}; e[tot++] = (edge){i, n + j, dist(a[i], b[j])}; for(int k = 1; k <= q; ++k) e[tot++] = (edge){i, n + m + k, dist(a[i], c[k])}; } for(int i = 1; i <= m; ++i) { if(i > 1) e[tot++] = (edge){n + i - 1, n + i, dist(b[i - 1], b[i])}; for(int k = 1; k <= q; ++k) e[tot++] = (edge){n + i, n + m + k, dist(b[i], c[k])}; } for(int i = 2; i <= q; ++i) e[tot++] = (edge){n + m + i - 1, n + m + i, dist(c[i - 1], c[i])}; sort(e, e + tot); n += m + q; for(int i = 1; i <= n; ++i) fa[i] = i; ans = 0; for(int i = 0; i < tot; ++i) if(find(e[i].u) != find(e[i].v)) { fa[find(e[i].u)] = find(e[i].v); ans += sqrt(e[i].w); } printf("%.6f\n", ans + 1e-10); } return 0;}
I. 暴力大法好
题意：
设f(i)等于i的十进制位上各位数字之积，求[L, R]之间有多少个i满足f(i) = X。
0 <= L, R < 10 ^ 18, 1 < X < 10 ^ 18。
题解：
不难想到按位来做这道题。能够考虑数位dp，然后分别算出[1, L – 1]和[1, R]有多少个点满足条件。
f(i)是0 ~ 9的数字的乘积，除了0之外一定能够被分解成2 ^ i * 3 ^ j * 5 ^ k * 7 ^ l的形式，当中0 <= i <= 54, 0 <= j <= 36, 0 <= k, l <= 18。
能够用dp[len][i][j][k][l]表示位数为len的数里，满足f(x) = 2 ^ i * 3 ^ j * 5 ^ k * 7 ^ l的x的个数，则dp[len][……]能够由dp[len – 1][……]的结果加上末尾加一个非0数字得到。
预先处理出dp[……]之后就非常好统计了。
对于一段区间[1, K]，最好还是设K的十进制位上由高到低各自是a_1, a_2, …, a_m。
则[1, K] 能够划分为[10 ^ 0, 10 ^ 1 – 1], [10 ^ 1, 10 ^ 2 – 1], …., [10 ^ (m – 1), 10 ^ m – 1], [1 * 10 ^ m, 2 * 10 ^ m – 1], …, [(a_1 – 1) * 10 ^ m, a_1 * 10 ^ m – 1], [a_1 * 10 ^ m + 1 * 10 ^ (m – 1), a_1 * 10 ^ m + 2 * 10 ^ (m – 1) – 1], ……, [a_1 * 10 ^ m + … + (a_(m – 1) – 1) * 10, a_1 * 10 ^ m + … + a_(m – 1) * 10 – 1], [a_1 * 10 ^ m + … + a_(m – 1) * 10 + 1, a_1 * 10 ^ m + … + a_m]，分别来统计。
比方说K = 14285，则分别统计0xxxx, 00xxx, 000xx, 0000x, 11xxx, 12xxx, 13xxx, 141xx, 1421x, 1422x, 1423x, 1424x, 1425x, 1426x, 1427x, 14281~14285里满足条件的个数。xx部分是已经用dp[……]算过的部分。
设最大数为x。数据组数为T。时间复杂度O(log^5x + TlogX)。
韬神表示他的搜索随随便便干掉我的dp。
代码：
#include <cstdio>
const int d[10][4] = {
{0, 0, 0, 0},
{0, 0, 0, 0},
{1, 0, 0, 0},
{0, 1, 0, 0},
{2, 0, 0, 0},
{0, 0, 1, 0},
{1, 1, 0, 0},
{0, 0, 0, 1},
{3, 0, 0, 0},
{0, 2, 0, 0}
};
long long L, R, X, a[4], f[19][55][37][19][19];
bool flag;
void fact()
{
int s[4] = {2, 3, 5, 7};
for(int i = 0; i < 4; ++i)
{
a[i] = 0;
while(X % s[i] == 0)
{
++a[i];
X /= s[i];
}
}
flag = X > 1 || a[0] > 54 || a[1] > 36 || a[2] > 18 || a[3] > 18;
}
long long sum(long long M)
{
if(M <= 0 || flag)
return 0;
int len = 0, num[20] = {};
long long sum = 0;
while(M > 0)
{
num[len++] = M % 10;
M /= 10;
}
long long now[4] = {a[0], a[1], a[2], a[3]};
for(int i = len - 1; i > 0; --i)
sum += f[i][now[0]][now[1]][now[2]][now[3]];
for(int i = len - 1; i >= 1; --i)
{
if(!num[i])
return sum;
for(int j = 1; j < num[i]; ++j)
{
now[0] -= d[j][0];
now[1] -= d[j][1];
now[2] -= d[j][2];
now[3] -= d[j][3];
if(now[0] >= 0 && now[1] >= 0 && now[2] >= 0 && now[3] >= 0)
sum += f[i][now[0]][now[1]][now[2]][now[3]];
now[0] += d[j][0];
now[1] += d[j][1];
now[2] += d[j][2];
now[3] += d[j][3];
}
now[0] -= d[num[i]][0];
now[1] -= d[num[i]][1];
now[2] -= d[num[i]][2];
now[3] -= d[num[i]][3];
if(now[0] < 0 || now[1] < 0 || now[2] < 0 || now[3] < 0)
return sum;
}
long long tmp = 1;
for(int i = 0; i < now[0] && tmp < 10; ++i)
tmp *= 2;
for(int i = 0; i < now[1] && tmp < 10; ++i)
tmp *= 3;
for(int i = 0; i < now[2] && tmp < 10; ++i)
tmp *= 5;
for(int i = 0; i < now[3] && tmp < 10; ++i)
tmp *= 7;
if(tmp <= num[0])
++sum;
return sum;
}
int main()
{
f[0][0][0][0][0] = 1;
for(int len = 1; len <= 18; ++len)
for(int i = 0; i <= (len << 1) + len; ++i)
for(int j = 0; j <= len << 1; ++j)
for(int k = 0; k <= len; ++k)
for(int l = 0; l <= len; ++l)
{
for(int o = 1; o <= 9; ++o)
if(i >= d[o][0] && j >= d[o][1] && k >= d[o][2] && l >= d[o][3])
f[len][i][j][k][l] += f[len - 1][i - d[o][0]][j - d[o][1]][k - d[o][2]][l - d[o][3]];
}
while(scanf("%lld%lld%lld", &L, &R, &X) == 3)
{
fact();
printf("%lld\n", sum(R) - sum(L - 1));
}
return 0;
}
J. 防御塔的搭建
题意：
求1~n的排列分别排成升序须要的最少交换次数之和E(n)，答案模10 ^ 9 + 7。
0 <= n <= 100000。
题解：
对于一个确定的排列P, 假设i向P_i连一条有向边，就会形成n个点若干个有向环的图，最少次数交换一定是在环内的置换。
如果一共同拥有m个环，长度分别为a_1, …, a_m，交换次数应该为\sum_{i = 1} ^ m {a_i – 1}，而\sum_{i = 1} ^ m {a_i} = n，所以最少交换次数就是n – m。
如今考虑n – 1的答案与n的答案的关系，最好还是设f(n)表示1~n的排列排成升序的最少交换次数期望值。
假设已经算出了f(n – 1)。能够考虑1~n的排列P的最后一个数字是什么。假设P_n就是n，那么添加一个环；假设P_n不是n，那它一定是加入了一条边进入某一个已有的环。
那么f(n) = 1 / n * f(n – 1) + (1 – 1 / n) * (f(n – 1) + 1) = f(n – 1) + (n – 1) / n，化成E(n)的形式就是E(n) = n * E(n – 1) + (n – 1) * (n – 1)!，递推解决。
时间复杂度O(n)。
代码：
#include <cstdio>
const int maxn = 100010, mod = 1000000007;
int t, n, f[maxn];
int main()
{
for(int i = 2, fact = 1; i < maxn; ++i)
{
f[i] = ((long long)i * f[i - 1] + (i - 1ll) * fact) % mod;
fact = fact * (long long)i % mod;
}
while(scanf("%d", &n) == 1)
printf("Case #%d: %d\n", ++t, f[n]);
return 0;
}
K. 防御塔的能量
题意：
给定一个n点的有根树，每一个点有两个属性p_i和c_i。
你能够对每一个点定义一个q_i，要求0 <= q_i <= m。
定义完之后能够令t_i = |q_i – c_i|。而且算出i的子树里t_j < t_i的节点j的个数记为num_i。
已知\sum_{i = 1} ^ n {p_i * num_i} = s，求有多少种定义{q_i}的方案。
父节点编号一定小于孩子节点。
1 <= n <= 11, 0 <= c_i <= m <= 100, s <= 100, p_i <= 20。
题解：
设t_i可能的最大值为lim。(lim <= m)
不难想到一个搜索的算法。枚举1~n的排列P依照例如以下定义赋值(t_i)大小关系：
1. 假设P_i是P_(i + 1)的祖先或是没有直系关系。则考虑t_{P_i} <= t_{P_(i + 1)}的情况。
2. 假设P_i是P_(i + 1)的孩子，则考虑t_{P_i} < t_{P_(i + 1)}的情况。
这样枚举排列不会漏算或多算不论什么一种情况。且能在不真正枚举q_i的情况下算出哪些大小关系的情况满足\sum_{i = 1} ^ n {p_i * num_i} = s。
对于满足情况的排列则又能够利用dp算出对于的方案数，这种算法时间复杂度是O(n! nlim)。
在满足条件的排列比較少的时候能比較快出解，可是非常明显s = 0或是菊花树就能够把进入dp计数的次数提高到一半左右。
因为满足上面的条件，不难考虑到将排列转化为压缩的状态，能够用[点集][最后一个点]将排列转化整合。
假设已经会了上述的搜索。不难想到dp[点集][最后一个点][已经凑的权和][当前的赋值的上限]来计算，可是这样会MLE。
考虑将“最后一个点”这一维省掉，我们发现。假设先用父节点更新了全部的状态。再用孩子节点更新全部的状态。那么父节点更新的时候就算使用了表义上等于孩子节点的方案。可是因为孩子节点还没用来更新这个状态。所以在更新父节点时，父节点赋值等于孩子节点赋值的情况并不会算入新的状态。能够直接使用。
所以能够对于赋值上限，先算出某一层的结果，再去算更高一层，每一层要依照树的dfs序先用深度较低的点更新全部它能更新的状态。
实际上题目中给出了“父节点编号一定小于孩子节点”的约束条件，则不用计算dfs序而是直接顺序枚举就可以。
对于节点u，能够将f[赋值上限i][点集j’][权和k’]由f[i][j][k] + f[i – 1][j][k]来更新。当中u不在j中。j’ = j ∪ u。k’ = k + (j中u的孩子个数)。
注意，f[i][j][k]也要继承f[i – 1][j][k]的方案；一个t_i可能相应两个p_i。
这道题比較卡取模的部分。。
。
所以能够滚动第一维。取模也晚一点（更新次数当然不会超过10^9的）。
新的状态转移方程就是f[j’][k’] += f[j][k]。j’ k’定义同上。
利用位运算能够在统计孩子的地方再做优化，时间复杂度O(nslim2^n)。
代码：
__builtin_popcount()是统计一个数字二进制位上1的个数的函数。
#include <cstdio>
#include <cstring>
const int maxn = 11, maxs = 100, maxw = 1 << 11, mod = 1000000007;
int n, m, s, p[maxn], c[maxn], fa[maxn], e[maxn], ans;
int lim, size;
long long f[maxw][maxs + 1];
int main()
{
while(scanf("%d%d%d", &n, &m, &s) == 3)
{
lim = 0;
size = 1 << n;
memset(fa, 0, sizeof fa);
memset(e, 0, sizeof e);
for(int i = 1, u, v; i < n; ++i)
{
scanf("%d%d", &u, &v);
fa[--v] = --u;
}
for(int i = 1; i < n; ++i)
for(int j = i; j; j = fa[j])
e[fa[j]] |= 1 << i;
for(int i = 0; i < n; ++i)
{
scanf("%d%d", p + i, c + i);
if(c[i] < m - c[i])
c[i] = m - c[i];
if(lim < c[i])
lim = c[i];
}
ans = 0;
memset(f, 0, sizeof f);
f[0][0] = 1;
for(int i = 0; i <= lim; ++i)
{
for(int u = 0; u < n; ++u)
if(i <= c[u])
for(int j = 0; j < size; ++j)
if(~(j >> u) & 1)
{
int jj = j ^ (1 << u), delta = __builtin_popcount(e[u] & j) * p[u];
for(int k = delta; k <= s; ++k)
{
f[jj][k] += f[j][k - delta];
if(i >= 1 && i <= m - c[u])
f[jj][k] += f[j][k - delta];
}
}
for(int j = 0; j < size; ++j)
for(int k = 0; k <= s; ++k)
f[j][k] %= mod;
}
printf("%d\n", f[size - 1][s]);
}
return 0;
}
L. 防御塔的处理器
题意：
给定一个n点m边的有向图。每一个点有点权，求每一个点从某个起点走到该点的点权和最大值。
n, m <= 100000。
题解：
每一个点取指向它的点中答案的最大值，加上自己的点权即为该点答案。
点数较多，须要用邻接表或边集数组存图。
我写的记忆化搜索。
代码：
vector<int> e模拟了邻接表，题目比較卡内存的时候慎用。
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 100010;
int n, m, t[maxn], f[maxn], ans;
vector<int> e[maxn];
int max(int a, int b)
{
return a < b ? b : a;
}
int F(int v)
{
if(f[v] != -1)
return f[v];
int Max = 0;
for(int i = 0, j = (int)e[v].size(); i < j; ++i)
Max = max(Max, F(e[v][i]));
return f[v] = Max + t[v];
}
int main()
{
while(scanf("%d%d", &n, &m) == 2)
{
ans = 0;
memset(f, -1, sizeof f);
for(int i = 1; i <= n; ++i)
{
scanf("%d", t + i);
e[i].clear();
}
for(int u, v; m--; )
{
scanf("%d%d", &u, &v);
e[v].push_back(u);
}
for(int i = 1; i <= n; ++i)
ans = max(ans, F(i));
printf("%d\n", ans);
}
return 0;
}
M. 防御塔的完好
题意：
给定每一个点的高度。统计有多少对相邻的点高度不一样，统计k遍。
题解：
依照题意扫一遍，答案乘k。
代码：
#include <cstdio>
const int maxn = 100010;
int n, k, h[maxn], ans;
int main()
{
while(scanf("%d%d", &n, &k) == 2)
{
for(int i = 1; i <= n; ++i)
scanf("%d", h + i);
ans = 0;
for(int i = 1; i < n; ++i)
if(h[i] != h[i + 1])
++ans;
printf("%d\n", ans * k);
}
return 0;
}
小记
考期的做题顺序是ACDGJMLFHIEB，较晚地发现了LM两道水题，E题想多了&推错了贡献了12次罚时，K题写错枚举顺序导致赛事结束也没做出来。
题写的还不够多，经验太少。思维能力不足。
感谢纪平神犇、约瑟大爷、BillGod等各位大神百忙之中（清华集训等）与我讨论。
（尽管啥也没讨论出来
我好弱啊。
发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/115948.html原文链接：https://javaforall.cn
【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛
【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...
