1.17考试

· · 个人记录

T1

给定两个数字n,m，要求求出一个长度为len的序列a满足以下条件：

1.len <= n

2.\displaystyle \sum_{i = 1}^{len}a_i = m

3.\forall a_i,i \in [1, len]都是n!的约数

输出任意一个合法的序列，若没有则输出>w<,n <= 20

题解：

对于这道题首先20!大的一批，所以我们考虑需要换一个方法处理n!的所有约数，那么怎么做呢？我们可以处理出n!的所有质因数，然后dfs暴力组合一下处理出n!的所有约数就好了啦，然后考虑到贪心，我们对于它的所有约数从大到小枚举搜索就ok了。

#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
const int N = 10000005;
ll m, is[N], ans[N];
int n, flag, cnt, goal = 8, c[N], prime[20] = {0, 2, 3, 5, 7, 11, 13, 17, 19};
inline ll read()
{
    ll x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
    return x * f;
}
void dfs(int x, int now, ll res)
{
    if(res == 0) {if(x - 1 <= n) flag = x - 1; return;}
    if(flag || x > n) return;
    for(int i = now; i >= 1; i --)
        if(is[i] <= res)
        {
            ans[x] = is[i];
            dfs(x + 1, i, res - is[i]);
            if(flag) return; ans[x] = 0;
        }
}
void get(int x, ll num)
{
    if(x == goal + 1) return is[++ cnt] = num, void();
    ll now = 1;
    for(int i = 0; i <= c[x]; i ++, now = now * prime[x]) get(x + 1, num * now);
}
void work()
{
    for(int i = 1; i <= 8; i ++)
    {
        if(prime[i] > n) {goal = i - 1; break;}
        for(int j = 2; j <= n; j ++)
        {
            int x = j;
            if(x % prime[i] == 0) while(x % prime[i] == 0) c[i] ++, x /= prime[i];
        }
    }
    get(1, 1); sort(is + 1, is + cnt + 1); dfs(1, cnt, m);
    if(!flag) printf(">w<\n");
    else
    {
        printf("%d\n", flag);
        for(int i = 1; i <= flag; i ++) printf("%lld ", ans[i]);
    }
}
int main()
{
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
    n = read(); m = read();
    work();
    fclose(stdin);
    fclose(stdout);
    return 0;
}

官方题解：

对于 100% 的数据，我们把 dp 改成贪心就行辣。算出 n! 的所有约数 (n = 20 的时候其实也只有 40000 多一点)，然后从大到小能选就选。

有趣的是这个贪心可以保证，一定可以在 n 步之内把它减成 0.

当然还有另外一个有理有据的做法。首先你需要知道阶乘进位制，即把 数字分解成 \sum_{k}a_k * k!且 a_k ≤ k。

然后如果你直接把 m 这么分解可能会出现不是 n! 的约数的情况。比 如 m = 100 = 96 + 4 = 4 × 4! + 2 × 2!, 但是 96 并不是 120 的约数。

思考，问题出现在 a_k = k 的情况下。

但是我们可以换一下么……令新的进位制第 k 位的权值为 n * (n -1). . .(n- k) 就行辣，因为 a_k < n - k所以这个数字一定是 n! 的约数。 那么现在思考贪心做法就知道他为什么对辣，因为我们每次相当于去掉 的数字一定不会比刚才的数学算法取出的数字小，自然只能更优。

T2

给定一棵以一为根的有根树，定义两条深度递增的路径是相似的当且仅 当两条路径长度相同并且对应位置的点的度数相同。现在请求出不相似的 路径一共有多少种。 注意一个点也算是一条路径。

题解：

对于这道题，显然我们需要先统计度数，统计完度数之后显然就可以把问题转化成在度数构成的串上求出有多少个本质不同的子串，那么我们可以自然地想到SAM求解。

但是问题来了，字符串到底是什么呢？

em...思考一下我们发现，因为要保证深度递增，所以每个点构成的“度数串”一定是以他的父亲为基础的，所以我们在原来SAM的基础上把last改成插入他父亲时的编号就好了。

#include <iostream>
#include <cstdio>
#include <map>
#define ll long long
using namespace std;
const int N = 1e6 + 1;
int deg[N], n, head[N], tot, cnt = 1, fa[N << 1], len[N << 1];
ll ans;
map<int, int> tr[N << 1];
struct node{int to, nex;}a[N << 1];
inline int getc()
{
    static const int L = 1 << 15;
    static char buf[L], *S = buf, *T = buf;
    if (S == T)
    {
        T = (S = buf) + fread(buf, 1, L, stdin);
        if (S == T) return EOF;
    }
    return *S++;
}
inline int read()
{
    static int c, x;
    while (!isdigit(c = getc())); x = c - '0';
    while (isdigit(c = getc())) x = (x << 1) + (x << 3) + c - '0';
    return x;
}
void add(int x, int y) {a[++ tot].to = y; a[tot].nex = head[x]; head[x] = tot;}
int insert(int now, int x, int last)
{
    int np = ++ cnt, p = last, q, nq; len[np] = len[p] + 1;
    for(; p && !tr[p][x]; p = fa[p]) tr[p][x] = np;
    if(!p) fa[np] = 1;
    else
    {
        q = tr[p][x];
        if(len[q] == len[p] + 1) fa[np] = q;
        else
        {
            len[nq = ++ cnt] = len[p] + 1; fa[nq] = fa[q]; fa[q] = fa[np] = nq;
            tr[nq] = tr[q];
            for(; p && tr[p].count(x) && tr[p][x] == q; p = fa[p]) tr[p][x] = nq;
        }
    }
    ans += len[np] - len[fa[np]];
    return np;
}
void dfs(int x, int fa, int last)
{
    int now = insert(x, deg[x], last);
    for(int i = head[x]; i; i = a[i].nex)
    {
        int y = a[i].to;
        if(y == fa) continue;
        dfs(y, x, now);
    }
}
int main()
{
    freopen("B.in", "r", stdin);
    freopen("B.out", "w", stdout);
    n = read();
    for(int i = 1, x, y; i <= n - 1; i ++)
    {
        x = read(); y = read();
        add(x, y); add(y, x);
        deg[x] ++; deg[y] ++;
    }
    dfs(1, 0, 1); printf("%lld\n", ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}
T3

是个提交答案题，并木有改耶。。。

小测

懒得写了，详见链接~~

点我有惊喜哦

点我有更多惊喜哦