竞赛讨论区 > 【题解】2022牛客寒假算法基础集训营3
头像
四糸智乃
发布于 2022-01-28 18:00
+ 关注

【题解】2022牛客寒假算法基础集训营3 精

出题人认为的难度升序排序

ADBELICGJKHF

A、智乃的Hello XXXX

输出hello world即可，当然，也可以随便输出其他符合要求的答案。大概是让萌新了解一下spj，毕竟本场有很多spj。

时间复杂度，空间复杂度 

#include<bits/stdc++.h>
using namespace std;
int main()
{
    cout<<"hello world"<<endl;
}

B、智乃买瓜

简单背包，简单来讲，这道题的题解就写在题面里边了。

1.购买一整个重量为的西瓜

2.把瓜劈开，购买半个重量为的西瓜

3.不进行购买操作

对应着DP转移的三个决策，不妨开一个的数组，示现在放到第个西瓜，且当前的重量为。

显然有DP转移方程：

注意当或者时这一项是没有的。

当然，实际处理的时候习惯将二维数组用滚动数组优化成一维。

时间复杂度，空间复杂度 

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int n,m,x;
const long long mod=1e9+7;
long long dp[MAXN]; 
int main()
{
    dp[0]=1;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&x);
        for(int i=m;i;--i)
        {
            if(i>=x/2)dp[i]+=dp[i-x/2];
            if(i>=x)dp[i]+=dp[i-x];
            while(dp[i]>=mod)dp[i]-=mod;
        }
    }
    for(int i=1;i<=m;++i)
    {
        printf("%lld%c",dp[i]," \n"[i==m]);
    }
    return 0;
}

C、智乃买瓜(another version)

这道题属于是萌新也能做的多项式题（多项式除法）当然，解这道题不需要这么麻烦的理解啦。

看到题目之后很自然的逆向思维，既然这道题是原题输入输出的倒置。不妨去想，怎么把放进背包的物品取出来。

观察题目，说整只西瓜的质量都是偶数，那么最终答案为什么会出现质量和为奇数的情况？显然是由于有买半个瓜的决策。

那么就可以从小到大逆推，首先能够知道，的值实际上就是质量为2的瓜的数目。

接下来的问题在意，已经知道了整个背包的信息（DP数组），如何把这些质量为2的瓜从背包中取出？

观察DP转移方程，是一个加法和式。

天然的逆向思维，怎么加上去的，就怎么减回来。

则有

（移项）

（令，下标偏移1个单位）

这样，我们就得到了原题的逆动态规划转移方程，倒着来一遍还原即可，和上一道题一样，实际处理时习惯使用滚动数组优化到一维。

以下内容不太用关注(=-=)如果你对此没有疑问的话。

还有一个不太关键的问题：这道题的解是否唯一，显然是不唯一的，就算你胡乱生成一个数组，也总是能够得到一个有穷范围内可以表示的解（当然，也许很大，所以还需要一些卷积加速的手段），那如何保证std这样的方法不会超过限制？

换句话说这个题只讨论到这里是不够严谨的，如何证明std拿到的解，其西瓜数目是最少的？

这个题最小解唯一，因为从本质来讲，这道题就是让你将若干个形如生成函数的积还原，并且你已知了每一步的以及，那么显然无论正着推还是反过来，步骤都是唯一的。

如果没懂的话，简单来讲，这道题就好像是现在有若干个数字，你不知它们都是几，但是你知道它们的乘积是X(比如a*b*c*d=X)，然后你可以通过一个固定操作知道乘积中最后一个数字是谁（而且保证这个数字是最小的），比如现在是d，所以你取出了d，然后令X=x/d，除完之后拿到了新的X，并且你继续通过这个操作知道现在里面最后一个乘进去的数字是c...然后进行若干轮重复操作后，你剩下一个X=1和a,b,c,d四个数字，所以说X是a,b,c,d四个数的乘积，并且这个过程是一个唯一过程。换句话说，最小解的唯一性是由于每一步拿取的数字唯一保证的。

如果不带模，那确实这样的最小解唯一，但是这里仍有不严谨的地方，由于模了，那每次取得这个最小的数万一不是而是咋办？

显然是不可能的，因为这道题的西瓜数目最大才1000，所以这种情况被直接排除了。

这里给我们提供的启示是，如果不保证西瓜数目的最大值（1000）要求任意构造，你仍然可以用std的思路求解，但是在还原时要使用卷积加速的手段求解，当然，输出的格式要改成，输出西瓜的重量+这种重量西瓜的数目，这就是另外一道题了。

时间复杂度，空间复杂度。 

#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
const int MAXN=1005;
long long dp[MAXN];
int m;
vector<int>ans;
int main()
{
    dp[0]=1;
    scanf("%d",&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%lld",&dp[i]);
    }
    for(int i=1;i<=m;++i)
    {
        while(dp[i])
        {
            ans.push_back(i*2);
            assert(ans.size()<=1000);
            for(int j=0;j<=m;++j)
            {
                if(j+i<=m)dp[j+i]-=dp[j];
                while(j+i<=m && dp[j+i]<0)dp[j+i]+=mod;
                if(j+i+i<=m)dp[j+i+i]-=dp[j];
                while(j+i+i<=m && dp[j+i+i]<0)dp[j+i+i]+=mod;
            }
        }
    }
    printf("%d\n",ans.size());
    for(int i=0;i<ans.size();++i)
    {
        printf("%d%c",ans[i]," \n"[i+1==ans.size()]);
    }
    return 0;
}

D、智乃的01串打乱

签到题，找到第一个0和第一个1的位置直接交换即可。

时间复杂度，空间复杂度。 

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
char s[MAXN];
int n;
char& f(char c)
{
    for (int i = 0; i < n; ++i)
    {
        if (s[i] == c)return s[i];
    }
    assert(0);
    return s[0];
}
int main()
{
    scanf("%d", &n);
    scanf("%s", s);
    assert(strlen(s)==n);
    swap(f('0'), f('1'));
    printf("%s\n", s);
    return 0;
}

E、智乃的数字积木(easy version)

按照题意模拟，每次取色相同的一整段进行从大到小排序。

这里萌新需要学习的两个小技巧

数组切段

每年看新生代码的时候尤其是有切字符串或者切数组这种需求的时候，发现新生切串一般都写的贼麻烦，其实这种只用写一个for+一个while语句就可以实现。 

for (int l = 1, r = 1; l <= n; l = r + 1, r = l)
{
    while (r < n && (a[l]==a[r+1]) )++r;
    printf("[%d,%d] ",l ,r);
}

lambda

sort需要传排序函数的时候，如果cmp函数没有重复利用的必要，可以使用匿名函数在调用sort函数时直接定义。

比如int数组从大到小进行排序，可以这么写 

sort(a + 1, a + 1 + n, [](const int&A, const int&B) {
     return A > B;
});

这样做的好处是在面向过程的编程中，不会破坏编程的连续性，你可以顺着在一个函数过程中直接写，不用在跳出函数外部额外写一个函数，可以增加写代码的速度。

时间复杂度，空间复杂度。 

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const long long mod = 1e9 + 7;
int n, m, k,u,v;
int col[MAXN];
char s[MAXN];
long long cal()
{
    for (int l = 1, r = 1; l <= n; l = r + 1, r = l)
    {
        while (r < n && col[r + 1] == col[l])++r;
        sort(s + l, s + 1 + r, [](const char&A, const char&B) {
            return A > B;
        });
    }
    long long ret = 0;
    for (int i = 1; i <= n; ++i)
    {
        ret = ret * 10 + (s[i] - '0');
        ret %= mod;
    }
    return ret;
}
void modify_col(int col_from, int col_to)
{
    for (int i = 1; i <= n; ++i)
    {
        if(col[i]==col_from)col[i]=col_to;
    }
    return;
}
int main()
{
    scanf("%d %d %d", &n, &m, &k);
    scanf("%s", s + 1);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &col[i]);
    }
    printf("%lld\n", cal());
    while (k--)
    {
        scanf("%d %d",&u,&v);
        modify_col(u,v);
        printf("%lld\n", cal());
    }
    return 0;
}

F、智乃的数字积木(hard version)

启发式合并，每次选较小的颜色往大的块上面并。

具体来讲，这道题要维护若干个颜色相同的“块”。

对于每一个块，其实并不需要每一次都暴力排序，其实我们只需要知道其中有几个1，几个2，几个3...

使用桶排序的思路统计每个块中数字的个数。

然后它一定是形如一个99..9988..8877..7766..6655..5544..4433...的形式，可以拆解成若干个连续相同的数字。

比如9999887766=9999*1000000+88*10000+77*100+66。

这个东西它等于，其中是位数，是构造的数字。

有了这种数学方法，我们就可以快速求一个块在全局ans中提供的答案是多少，见std代码中的calc::部分。

然后现在的需求就是设计一种数据结构维护一个全局的ans，全局ans=每个块的答案之和。

对于这种维护一个全局答案的题目不用每次都全部求一边，只需要在修改时先减去原本的贡献，然后修改后再加回来即可，也就是说通过维护该变量的形式而不是每次都求解。

接下来的问题在于，每次染色后如何合并颜色相同的块。

这里设计算法的时候要注意，不要考虑同时合并多个块，只考虑两个块之间的二合并。

因为你一旦陷入思考染色后三个同色块相邻的情况就会继续思考四个五个...

对于染色后需要合并多个色块的情况，都转化为相邻块之间的二合并。

合并色块实际上就是将色块里面的桶中的数字直接相加。见block operator + (const block &A, const block&B)的运算符重载，这个合并可以视为是的。

那么如何枚举颜色相同的块呢，比如现在要讲颜色变为。

这里用到的数据结构应该是一个平衡树或者不定长数组储存相同颜色的块。

这里随便用什么都可以，看自己的喜好，这里使用平衡树维护实际上就是用std::set维护，不定长数组实际上就是用std::vector。

用set在查找的时候可以用自带的二分查找，比较方便，而且保证插入的时候有序，缺点就是这样写总体复杂度为。

然后接下来每次合并的时候暴力枚举相同颜色的块。

问题来了，如何保证每次暴力枚举颜色相同色块的时间复杂度？

这里就用到启发式合并了，即每一次暴力枚举颜色时，取维护色块颜色和颜色的数据结构尺寸较小的那个暴力插入到另一个当中，然后清空该数据结构。

假设色块的总数为则每次暴力合并的总时间复杂度为，均摊到每次操作的均摊复杂度就是。

这个时间复杂度计算的方法是：考虑暴力插入的次数，每次合并结束后，较小尺寸数据结构的尺寸都会至少翻倍，那么每一个元素的暴力插入次数就会小于次，所以总复杂度就是。

然后就是一些小细节的处理可以使用并查集维护。

时间复杂度，空间复杂度。 

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int MAXM = 100005;
const int MAX_CNT = 10;
const long long mod = 1e9 + 7;
const long long inv9 = 111111112;
namespace calc {
long long pow10[MAXN];
void init(int n)
{
    pow10[0] = 1;
    for (int i = 1; i <= n; ++i)
    {
        pow10[i] = pow10[i - 1] * 10 % mod;
    }
}
//11111111               base=1, len=8
//2222222222             base=2, len=10
//333333333333333        base=3, len=15
long long make_number(long long base, long long len)
{
    long long ret = (pow10[len] - 1) * inv9 % mod * base % mod;
    if (ret < 0)ret += mod;
    return ret;
}
}
long long ans;
int col_to_id[MAXM], id_to_col[MAXM];
vector<int> col_blocks[MAXM];
int n, m, k, fa[MAXN * 2], col[MAXN], u, v;
char s[MAXN];
int findf(int x)
{
    return x == fa[x] ? x : fa[x] = findf(fa[x]);
}
void unions(int x, int y)
{
    if (findf(x) != findf(y))
    {
        fa[findf(x)] = findf(y);
    }
    return;
}
struct block
{
    int l, r;
    int col_id;
    int cnt[MAX_CNT];
    bool enable;
    long long get_val()
    {
        long long ret = 0;
        for (int i = 9; ~i; --i)
        {
            long long temp = calc::make_number(i, cnt[i]);
            ret = ret * calc::pow10[cnt[i]] % mod;
            ret += temp;
            ret %= mod;
        }
        ret *= calc::pow10[n - r];
        ret %= mod;
        return ret;
    }
};
block operator + (const block &A, const block&B)
{
    block C;
    C.l = min(A.l, B.l);
    C.r = max(A.r, B.r);
    C.col_id = A.col_id;
    C.enable = true;
    for (int i = 0; i < MAX_CNT; ++i)
    {
        C.cnt[i] = A.cnt[i] + B.cnt[i];
    }
    return C;
}
vector<block>b;
void dsu_init()
{
    for (int i = 1; i <= n * 2; ++i)
    {
        fa[i] = i;
    }
}
void init_block()
{
    int cnt[MAX_CNT];
    for (int l = 1, r = 1; l <= n; l = r + 1, r = l)
    {
        while (r < n && col[r + 1] == col[l])++r;
        memset(cnt, 0, sizeof(cnt));
        for (int i = l; i <= r; ++i)
        {
            cnt[s[i] - '0']++;
            unions(i, n + 1 + b.size());
        }
        block current_block;

        current_block.l = l;
        current_block.r = r;
        current_block.col_id = col_to_id[col[l]];
        current_block.enable = true;
        memcpy(current_block.cnt, cnt, sizeof(cnt));
        col_blocks[col[l]].push_back(b.size());
        b.push_back(current_block);

    }
}
void init_ans()
{
    ans = 0;
    for (auto i : b)
    {
        ans += i.get_val();
        if (ans >= mod)ans -= mod;
    }
    return;
}
void modify_ans(long long val, long long op)
{
    ans += val * op;
    ans = (ans % mod + mod) % mod;
}
void init_col()
{
    for (int i = 1; i <= m; ++i)
    {
        col_to_id[i] = i;
        id_to_col[i] = i;
    }
}
void vector_merge(vector<int>&V_from, vector<int>&V_to, int t_col_id)
{
    for (auto it : V_from)
    {
        if (!b[it].enable)continue;
        b[it].col_id = t_col_id;
        modify_ans(b[it].get_val(), -1);
        if (b[it].l > 1)
        {
            block &Lblock = b[findf(b[it].l - 1) - n - 1];
            if (Lblock.col_id == t_col_id)
            {
                modify_ans(Lblock.get_val(), -1);
                unions(b[it].l - 1, n + 1 + it);
                b[it] = Lblock + b[it];
                Lblock.enable = false;

            }
        }
        if (b[it].r < n)
        {
            block &Rblock = b[findf(b[it].r + 1) - n - 1];
            if (Rblock.col_id == t_col_id)
            {
                modify_ans(Rblock.get_val(), -1);
                unions(b[it].r + 1, n + 1 + it);
                b[it] = b[it] + Rblock;
                Rblock.enable = false;

            }
        }
        modify_ans(b[it].get_val(), 1);
        V_to.push_back(it);
    }
    V_from.clear();
}
void modify_col(int col_from, int col_to)
{
    if (col_from == col_to)return;
    int from_id = col_to_id[col_from];
    int to_id = col_to_id[col_to];
    vector<int>&V_from = col_blocks[from_id];
    vector<int>&V_to = col_blocks[to_id];
    int updated_block_vector_id = V_from.size() < V_to.size() ? to_id : from_id;
    int empty_block_vector_id = V_from.size() < V_to.size() ? from_id : to_id;
    if (V_from.size() < V_to.size())
    {
        vector_merge(V_from, V_to, to_id);
    }
    else
    {
        vector_merge(V_to, V_from, from_id);
    }
    col_to_id[col_to] = updated_block_vector_id;
    id_to_col[updated_block_vector_id] = col_to;
    col_to_id[col_from] = empty_block_vector_id;
    id_to_col[empty_block_vector_id] = col_from;
}
int main()
{
    scanf("%d %d %d", &n, &m, &k);
    scanf("%s", s + 1);
    calc::init(n);
    dsu_init();
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &col[i]);
    }
    init_col();
    init_block();
    init_ans();
    printf("%lld\n", ans);
    while (k--)
    {
        scanf("%d %d", &u, &v);
        modify_col(u, v);
        printf("%lld\n", ans);
    }
    return 0;
}

G、智乃的树旋转(easy version)

还是题解就写在了题目当中。

认真读题，注意这么一句话智乃最近学习了树旋转，树旋转的本质是二叉树旋转轴节点与其父节点父子关系的改变

所以二重循环枚节点，当发现在两颗树中某一对节点互为父子关系时，直接输出原本是父亲的节点。

如果不存在这么一个节点，说明不用旋转，输出0即可。

时间复杂度，空间复杂度 

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
struct tree
{
    int fa;
    int ch[2];
} t[MAXN], a[MAXN];
int input_tree(tree* t, int n)
{
    int x, y;
    std::vector<bool> v(n + 1, true);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d %d", &x, &y);
        v[x] = v[y] = false;
        t[i].ch[0] = x;
        t[i].ch[1] = y;
        if (x)t[x].fa = i;
        if (y)t[y].fa = i;
    }
    for (int i = 1; i <= n; ++i)
    {
        if (v[i])return i;
    }
    return -1;
}
int n, root_a, root_t;
vector<int>vv;
int main()
{
    scanf("%d", &n);
    root_a = input_tree(a, n);
    root_t = input_tree(t, n);
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
        {
            if(t[i].fa==j&&a[j].fa==i)
            {
                printf("1\n%d\n",i);
                return 0;
            }
        }
    }
    printf("0\n");
}

H、智乃的树旋转(hard version)

还是注意这么一句话智乃最近学习了树旋转，树旋转的本质是二叉树旋转轴节点与其父节点父子关系的改变

思考这么一个问题：如果对某一个非根节点，一直作为旋转轴进行旋转，那么最后会发生什么。

显然，最终该节点一定被转到了整棵树的根部。

当你意识到这个问题之后，此时你仿佛tarjan灵魂附体，你发明了splay伸展树（当然，如果只是简单的一直旋转，这种操作称之为单旋，对于平衡树而言复杂度是假的）。

不过抛开时间复杂度不谈，splay的核心思想就是如果对二叉树的某个节点一直进行旋转，则该节点最终会被放到根的位置，而树结构修改根节点信息是的。至于为什么最终splay的旋转是复杂的双层旋转，是由于双旋的均摊复杂度是。

不过本题你写单旋写双旋都可以通过，甚至对于本题而言,写单旋更优。

对于本题而言，构造双层旋转的次数上界为次，构造单层旋转的次数上界为。（我并没有卡双旋，因为这样会很毒瘤） 

void dfs(int root)
{
    splay(root);
    vis[root] = true;
    if (a[root].ch[0])dfs(a[root].ch[0]);
    if (a[root].ch[1])dfs(a[root].ch[1]);
}

核心代码就是一个先序遍历，当遍历到需要还原的节点时就伸展到根，然后从打乱的树中删除，删除可以直接打懒标记。

时间复杂度，空间复杂度。 

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
struct tree
{
    int fa;
    int ch[2];
} t[MAXN], a[MAXN];
void rot(int root)
{
    int fa = t[root].fa;
    int gfa = t[fa].fa;
    int t1 = (root != t[fa].ch[0]);
    int t2 = (fa != t[gfa].ch[0]);
    int ch = t[root].ch[1 ^ t1];
    t[root].fa = gfa;
    t[root].ch[1 ^ t1] = fa;
    t[fa].ch[0 ^ t1] = ch;
    t[fa].fa = root;
    t[ch].fa = fa;
    t[gfa].ch[0 ^ t2] = root;
    return;
}
int input_tree(tree* t, int n)
{
    int x, y;
    std::vector<bool> v(n + 1, true);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d %d", &x, &y);
        v[x] = v[y] = false;
        t[i].ch[0] = x;
        t[i].ch[1] = y;
        if (x)t[x].fa = i;
        if (y)t[y].fa = i;
    }
    for (int i = 1; i <= n; ++i)
    {
        if (v[i])return i;
    }
    return -1;
}
vector<int>ans;
bool vis[MAXN] = {true};
int n, root_a, root_t;
//单层旋转
void splay(int root)
{
    while (!vis[t[root].fa])
    {
        ans.push_back(root);
        rot(root);
    }
    return;
}
/*
//双层旋转
void splay(int root)
{
    while(!vis[t[root].fa])
    {
        int fa=t[root].fa,gfa=t[fa].fa;
        if(gfa&&!vis[gfa])
        {
            if((t[fa].ch[0]==root)^(t[gfa].ch[0]==fa))
            {
                rot(root);
                ans.push_back(root);
            }
            else
            {
                ans.push_back(fa);
                rot(fa);
            }
        }
        ans.push_back(root);
        rot(root);
    }
    return;
}
*/
void dfs(int root)
{
    splay(root);
    vis[root] = true;
    if (a[root].ch[0])dfs(a[root].ch[0]);
    if (a[root].ch[1])dfs(a[root].ch[1]);
}
int main()
{

    scanf("%d", &n);
    root_a = input_tree(a, n);
    root_t = input_tree(t, n);
    dfs(root_a);
    printf("%d\n", ans.size());
    for (auto i : ans)printf("%d\n", i);
}

I、智乃的密码

首先把这几个条件拆开来看，也就是变成这样6个条件：

1、长度不小于

2、长度不大于

3、有小写英文字母

4、有大写英文字母

5、有数字

6、有特殊字符

你发现这6个条件可以拆开分别考虑。

同时这6个条件在固定所选子串的其中一个端点后，另一个端点的合法性是单调的。

所以可以使用二分或者尺取的方式直接判断每一个条件的合法区间。

最后取一个合法区间的并集即可。

时间复杂度，空间复杂度 

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
int n,l,r,a[4][MAXN],limit[4];
long long ans;
char s[MAXN];
void presum(int a[])
{
    for(int i=1;i<=n;++i)
    {
        a[i]+=a[i-1];
    }
}
bool has(int a[],int l,int r)
{
    return a[r]-a[l-1]>0;
}
int type(char c)
{
    if(c>='A'&&c<='Z')return 0;
    if(c>='a'&&c<='z')return 1;
    if(c>='0'&&c<='9')return 2;
    return 3;
}
int get_limit()
{
    int temp[4];
    memcpy(temp,limit,sizeof(temp));
    sort(temp,temp+4);
    return temp[1];
}
int cal(int border)
{
    int L=1,R=n;
    L=max(border-r+1,L);
    R=min(border-l+1,R);
    R=min(get_limit(),R);
    return L<=R?R-L+1:0;
}
int main()
{
    scanf("%d %d %d",&n,&l,&r);
    scanf("%s",s+1);
    assert(strlen(s+1)==n);
    for(int i=1;i<=n;++i)
    {
        a[type(s[i])][i]++;
    }
    for(int i=0;i<4;++i)
    {
        presum(a[i]);
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=0;j<4;++j)
        {
            while(has(a[j],limit[j]+1,i))++limit[j];
        }
        ans+=cal(i);
    }
    printf("%lld\n",ans);
    return 0;
}

J、智乃的C语言模除方程

这道题就分情况讨论随便算一算就行了。

不过这道题的重点不在于数学计算，而是如何建模。

首先第一个难点,,区间都是包含数轴正负数轴，这个就很讨厌，所以第一步，首先把所有问题都移动到正半轴,考虑，见std的主函数部分。

接下来观察题目中所求的东西：统计中的解的个数。

首先定义一个二元函数，其中中括号称为艾弗森括号，当括号内的表达式为真时，值为否则为。

问题转化成了求。

如果用图像来表示的话，本题的模型可以表示为：二维平面上有若干个点，选取一个矩阵，问矩阵中包括了多少个点。

这是啥呢，这不是二维前缀和？

所以令。

所以答案（二维前缀和的容斥，看不懂的话去学一下二维前缀和https://blog.nowcoder.net/n/1f56ba230f0841888738f6c246bfd8f1）

所以问题最终被转化成了最一般的形式，即的求法。

同时因为的定义都是1到某个数字连续，所以答案肯定是关于P有循环节的，然后其实就除一下模一下就行了。

时间复杂度，空间复杂度。 

#include<bits/stdc++.h>
using namespace std;
long long _l, _r, _L, _R, P, ans;
long long calcEx(long long x, long long y)
{
    x = min(P - 1, x);
    long long round = (y + 1) / P;
    long long last = (y + 1) % P;
    return (x + 1) * round + min(last, x + 1) - 1;
}
long long calc(long long l, long long r, long long L, long long R)
{
    return calcEx(r, R) - calcEx(l - 1, R) - calcEx(r, L - 1) + calcEx(l - 1, L - 1);
}
int main()
{
    scanf("%lld %lld %lld %lld %lld", &P, &_l, &_r, &_L, &_R);
    P = abs(P);
    if (_l <= 0 && 0 <= _r)
    {
        long long base = ((long long)1e10) / P * P;
        ans += (base + _R) / P - (base + _L - 1) / P;
    }
    if (_R > 0 && _r > 0)
    {
        ans += calc(max(1LL, _l), _r, max(1LL, _L), _R);
    }
    if (_L < 0 && _l < 0)
    {
        ans += calc(max(1LL, -_r), -_l, max(1LL, -_R), -_L);
    }
    printf("%lld\n", ans);
    return 0;
}

K、智乃的C语言模除方程(another version)

首先可以按照上一道题的做法去做（直接改上一题的calcEx即可），但是实际上这道题在思维上更简单了，不需要转化成二维前缀和。

首先你要知道一个叫做整除分块的数论板子。

整除分块是处理形如，其中为循环变量，为什么叫他分块呢，是因为对于形如的式子，对于只有种结果。

然后模除可以改写成一次除法+一次减法的形式，即

这个也是一个经典套路，但凡你碰到这个东西要循环枚举的时候你就可以把它变成，然后尝试整除分块。

对于本题，首先把它变形为，然后在整除分块的过程中就是常数，令其等于。

原式等于，把左侧的看成是一个等差数列。

问题转化成求一个等差数列的第项到第项中有多少项的值在到范围内，显然满足条件的是项到第项中连续的某一段，直接计算即可。

时间复杂度，空间复杂度。 

#include<bits/stdc++.h>
using namespace std;
long long _l, _r, _L, _R, P, ans;
long long segment_intersect(long long S1, long long T1, long long S2, long long T2)
{
    long long S = max(S1, S2);
    long long T = min(T1, T2);
    return max(0LL, T - S + 1);
}
long long cal(long long a, long long d, long long base, long long len)
{
    if (d == 0)
    {
        return _l <= a && a <= _r ? segment_intersect(_L, _R, base, base + len) + segment_intersect(_L, _R, -base - len, -base ) : 0;
    }
    long long s = a > _r ? (a - _r + d - 1) / d : 0;
    long long t = a >= _l ? (a - _l) / d : -1;
    t = min(t, len - 1);
    return segment_intersect(_L, _R, base + s, base + t) + segment_intersect(_L, _R, -base - t, -base - s);
}
int main()
{
    scanf("%lld %lld %lld %lld %lld", &P, &_l, &_r, &_L, &_R);
    if (P < 0)
    {
        P = -P;
        _l = -_l;
        _r = -_r;
        swap(_l, _r);
    }
    _l = max(_l, 0LL);
    for (long long l = 1, r; l <= P; l = r + 1)
    {
        r = P / (P / l);
        long long a = P % l;
        long long d = P / l;
        ans += cal(a, d, l, r - l + 1);
    }
    ans += cal(P, 0, P + 1, 1000000000);
    printf("%lld\n", ans);
    return 0;
}

L、智乃的数据库

按照题意进行模拟即可。

分组的话可以使用并查集或者hash，如果使用hash进行数组元素分组的话有个小技巧，就是利用sort将分组转化成数组切段，这样写起来就比较清爽了。

时间复杂度空间复杂度。 

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1005;
const int MAXS=100005;
const long long base=131;
const long long mod=1e9-7;
int n,m,k;
int dat[MAXN][MAXN];
int id[MAXN];
vector<int>group_id;
vector<int>ans;
long long hash_val[MAXN];
map<string,int>col_id;
char s[MAXS];
void hash_push(long long &hash,long long val)
{
    hash=(hash*base%mod+val)%mod;
}
void read_sql()
{
    scanf("%*s %*s %*s %*s %*s %*s %s",s);
    for(int l=0,r=0;s[l];l=r+2)
    {
        while(s[r+1]!=','&&s[r+1]!=';')++r;
        s[r+1]='\0';
        group_id.push_back(col_id[s+l]);
    }
    return;
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;++i)
    {
        id[i]=i;
    }
    for(int i=0;i<m;++i)
    {
        scanf("%s",s);
        col_id[s]=i;
    }
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<m;++j)
        {
            scanf("%d",&dat[i][j]);
        }
    }
    read_sql();
    for(int i=0;i<n;++i)
    {
        for(auto &j:group_id)
        {
            hash_push(hash_val[i],dat[i][j]);
        } 
    }
    sort(id,id+n,[](const int &A,const int &B){
        return hash_val[A]<hash_val[B];
    });
    for(int l=0,r=0;l<n;l=r+1)
    {
        while(r+1<n&&hash_val[id[r+1]]==hash_val[id[l]])++r;
        ans.push_back(r-l+1);
    }
    printf("%d\n",ans.size());
    for(auto &i:ans)printf("%d ",i);
    return 0;
}
2026最新求职资料大礼包领取
真题
历年笔试真题附答案
2024年秋招-蚂蚁集团-工程数据挖掘岗笔试
2024年秋招-京东-产品运营岗笔试
2023年飞猪秋招算法岗笔试
全部 >
面经
面试常考问题整理
0928携程笔试题解
腾讯三面已上岸
22届-国企上岸经验分享
全部 >
内推
员工内推码获取
拼多多内推拼多多内推码
阿里云智能-弹性计算高级研发工程师/高级技术专家-北京/杭州
国科微电子最新社招/校招，岗位多多
全部 >
大家都在关注
校招日程表 笔试日历 ai模拟面试 面试宝典 剑指offer 知识点专项练习

全部评论

(10) 回帖
加载中...
话题 回帖
返回全部帖子

本文相关内容

等你来战

查看全部

热门推荐

牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”