2023年福建农林大学程序设计校赛个人题解（无D解析)

这是一道原题

https://ac.nowcoder.com/acm/contest/58568/A

2023年福建农林大学程序设计校赛个人题解（无D解析)

A-这是一道原题

问题解析

从绿色材料合成到金色材料。

用 whilewhile 循环判断材料数是否能合成，能就合，合成后下一级材料数增加，原料数加上合成出的材料数。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>

//#pragma GCC optimize(2)
//#pragma GCC optimize(3)

#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50, MOD = 1e9 + 7;

void hecheng(int&a, int&b)
{
    while (a >= 3)
    {
        int x = a / 3;
        a %= 3;
        a += x;
        b += x;
    }
}

void solve()
{
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    hecheng(a, b);
    hecheng(b, c);
    hecheng(c, d);
    cout << a << " " << b << " " << c << " " << d;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

B-健康阳光，积极向上!

问题解析

想不到什么很好做法，直接暴力了。

根据贪心来说，要想结果越小，删掉的质因数就要越大。

对所有数进行质因数分解并记录下来，最后对所有质因数从大到小排序，把最前面 kk个质数当作我们要删除的质因子。

然后我们把剩下的质因子全部乘起来就行。

分解因数的复杂度在 O(2ai)O(\log_{2}{a_i}) 到 O(n)O(\sqrt n) 之间 。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>

//#pragma GCC optimize(2)
//#pragma GCC optimize(3)

#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50, MOD = 1e9 + 7;

int a[N];
vector<int>v;

void divide(int n)
{
    for (int i = 2; i <= n / i; i++)
    {
        if (n % i == 0)
        {
            int s = 0;
            while (n % i == 0)
            {
                v.push_back(i);
                n /= i;
            }
        }
    }
    if (n > 1)v.push_back(n);
}

void solve()
{
    int n, k;
    cin >> n >> k;
    if (k > 2e5 * 17)
    {
        cout << 1 << endl;
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        divide(a[i]);
    }
    sort(v.begin(), v.end(), greater<int>());
    int ans = 1;
    for (int i = k; i < v.size(); i++)
        ans = ans * v[i] % MOD;
    cout << ans << endl;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

C-字一色大四喜四杠子四暗刻单骑役满确定！

问题解析

遍历字符串看有没有 7z7z 就行。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>

//#pragma GCC optimize(2)
//#pragma GCC optimize(3)

#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50, MOD = 1e9 + 7;

void solve()
{
    int n;
    string s;
    cin >> n >> s;
    for (int i = 1; i < n; i++)
    {
        if (s[i - 1] == '7' && s[i] == 'z')
        {
            cout << "YES" << endl;
            return;
        }
    }
    cout << "NO" << endl;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

D-荣！断幺九，一番，1000点！

问题解析

说实话，这题我没想懂，不咋打雀不知道是不是只要胡牌且没有幺九牌就是段幺九。而且也不知道给的牌型是不是已经胡了让判断胡的排序。不太懂，如果有出题人能帮我解个惑就好了。

（代码学的一个大佬写的，感觉懂了点什么又好像没懂）

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>

//#pragma GCC optimize(2)
//#pragma GCC optimize(3)

#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50, MOD = 1e9 + 7;

void solve() 
{
    string s;
    cin >> s;
    int n = s.size();
    map<string, int>mymap;
    for (int i = 0; i < n; i++)
    {
        if (s[i] == '1' || s[i] == '9' || s[i] == 'z')
        {
            cout << "NO" << endl;
            return;
        }
    }
    for (int i = 0; i < n; i += 2)
    {
        string t;
        t += s[i];
        t += s[i + 1];
        mymap[t]++;
    }
    for (auto& i : mymap)
    {
        if (i.second >= 2)
        {
            map<string, int>mymap2;
            mymap2 = mymap;
            mymap2[i.first] -= 2;
            int cnt = 2;
            for (auto& j : mymap2)
            {
                if (j.second >= 3)
                {
                    j.second -= 3;
                    cnt += 3;
                }
                if (j.second != 0 && j.first[0] - '0' <= 7)
                {
                    string a = j.first;
                    a[0]++;
                    string b = a;
                    b[0]++;
                    while (j.second > 0 && mymap2[a] > 0 && mymap2[b] > 0)
                    {
                        j.second--;
                        mymap2[a]--;
                        mymap2[b]--;
                        cnt += 3;
                    }
                }
            }
            if (cnt == 14)
            {
                cout << "YES" << endl;
                return;
            }
        }
    }
    cout << "NO" << endl;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

E-可爱即是正义！

问题解析

区间前缀和模板，枚举所有 rr 行 cc 列的子矩阵然后用矩阵前缀和快速算结果，维护最大值就行。

注意数据可能使得最大的矩阵和为负数，维护最大值的变量初始值要够小。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>

//#pragma GCC optimize(2)
//#pragma GCC optimize(3)

#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50, MOD = 1e9 + 7;

int a[2050][2050], s[2050][2050], n, m;

void init()
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
}

int get_sum(int x1, int y1, int x2, int y2)
{
    return s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
}

void solve()
{
    int r, c;
    cin >> n >> m >> r >> c;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    init();
    int mx = -1e18;
    for (int i = 1; i <= n - r + 1; i++)
        for (int j = 1; j <= m - c + 1; j++)
            mx = max(mx, get_sum(i, j, i + r - 1, j + c - 1));
    cout << mx;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

F-炉石传说这个游戏是没有（任何BUG）的！

问题解析

基础的计数 dpdp 。

设状态转移数组 ff ，f[i]f[i] 表示前 ii 个字符的分割方式有 f[i]f[i] 种。

状态转移：如果一个长为 lenlen 的字符串 sisi 能匹配字符串 strstr 上 jj 到 j−len+1j-len+1 的这一段，则有 f[j+len−1]=f[j+len−1]+f[j−1]f[j+len-1] = f[j+len-1] + f[j-1] 。

思路不难，主要是匹配字符串的方法。

遍历字符串 strstr ，枚举每个位置 jj ,判断以当前字符为起点是否有字符串 sisi 能和它匹配。

这里可以用字符串哈希快速匹配，预处理 strstr 的哈希数组复杂度为：O(length(str))O(length(str)) ，预处理 nn 个字符串 ss 的哈希值的复杂度为：O(∑i=0nlength(si))O(\sum_{i=0}^nlength(s_i)) 。

每次匹配字符串复杂度为：O(1)O(1) 。

总复杂度：O(∑i=0nlength(si)∗length(str))O(\sum_{i=0}^n length(s_i) * length(str))

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>

//#pragma GCC optimize(2)
//#pragma GCC optimize(3)

#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50, MOD = 1e9 + 7;

int base = 13331;
ull hash_str[N], bpow[N], a[N];
int f[N];

void init(string s)
{
    int n = s.size();
    bpow[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        hash_str[i] = (hash_str[i-1] * base + s[i - 1]);
        bpow[i] = bpow[i - 1] * base;
    }
}

ull get_hash(int l, int r)
{
    return hash_str[r] - hash_str[l - 1] * bpow[r - l + 1];
}

void solve() {
    int n;
    string s;
    cin >> n >> s;
    vector<string>v(n);
    init(s);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
        ull res = 0, len = v[i].size();
        for (int j = 1; j <= len; j++)
        {
            res = (res * base + v[i][j - 1]);
        }
        a[i] = res;
    }
    int len = s.size();
    f[0] = 1;
    for (int i = 1; i <= len; i++)
    {
        
        for (int j = 0; j < n; j++)
        {
            int len2 = v[j].size();
            if (i + len2 - 1 <= len)
            {
                if (get_hash(i, i + len2 - 1) == a[j])
                {
                    f[i + len2 - 1] = (f[i - 1] + f[i + len2 - 1]) % MOD;
                }
            }
        }
    }
    cout << f[len] << endl;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

G-蒸蒸日上！

问题解析

出题人看来非常喜欢三国杀这款游戏呀，那我去给三国杀刷个好评罢。（逃）

根据给的字符串输出对应的外号就行。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>

//#pragma GCC optimize(2)
//#pragma GCC optimize(3)

#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50, MOD = 1e9 + 7;

void solve()
{
    string s;
    cin >> s;
    if (s == "XuSheng") s = "DaBao";
    else if (s == "GanNing") s = "DaGui";
    else if (s == "QuYi") s = "BaiMa";
    else if (s == "HuangZhong") s = "LaoBao";
    cout << s;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

H-圆皱率_

问题解析

这题面真是给我笑死，不过我觉得题意不是很清楚，一开始都不理解要干啥，最好优化一下或者给样例加个解释罢。

（话说我这种又玩原又玩粥又玩农的算啥皮）

这题是想让你从里面选择一个子序列，使得子序列的和最大，但是不能让 aaaa 和 AAAA 挨着。

我们先把豌豆的三种基因状态 AA、Aa、aaAA、Aa、aa 分别设为 1、2、31、2、3 。

动态规划。

设二维状态转移数组 ff ，f[i][j]f[i] [j] 表示在前 ii 个豌豆中取，且最后一个豌豆状态为 jj 的最大价值为 f[i][j]f[i] [j] ，j=0j = 0 表示一个豌豆都没取。

状态转移：

  • 每次都有：f[i][j]=f[i−1][j]f[i] [j] = f[i-1] [j] 。
  • 如果当前的豌豆状态为 11 ，则 f[i][1]=max(f[i][1]，f[i][j]+ai)(j=0,1,2)f[i] [1] = max(f[i] [1]，f[i] [j] + a_i) (j = 0,1,2)。
  • 如果当前的豌豆状态为 22 ，则 f[i][2]=max(f[i][1]，f[i][j]+ai)(j=0,1,2,3)f[i] [2] = max(f[i] [1]，f[i] [j] + a_i) (j = 0,1,2,3)。
  • 如果当前的豌豆状态为 33 ，则 f[i][3]=max(f[i][1]，f[i][j]+ai)(j=0,2,3)f[i] [3] = max(f[i] [1]，f[i] [j] + a_i) (j = 0,2,3)。

最后答案为：max(f[n][j])(j=0,1,2,3)max(f[n] [j]) (j=0,1,2,3) 。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>

//#pragma GCC optimize(2)
//#pragma GCC optimize(3)

#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50, MOD = 1e9 + 7;

int a[N], f[N][4], b[N];


void solve()
{
    string s;
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> a[i];
    for (int i = 1; i <= n; i++)
    {
        cin >> s;
        if (s == "AA")b[i] = 1;
        else if (s == "Aa")b[i] = 2;
        else b[i] = 3;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= 3; j++)
            f[i][j] = f[i - 1][j];
        if (b[i] == 1)
        {
            
            for (int j = 0; j < 3; j++)
                f[i][b[i]] = max(f[i][b[i]], f[i - 1][j] + a[i]);
        }
        else if (b[i] == 2)
        {
            for (int j = 0; j <= 3; j++)
                f[i][b[i]] = max(f[i][b[i]], f[i - 1][j] + a[i]);
        }
        else
        {
            for (int j = 0; j <= 3; j++)
                if (j != 1)
                    f[i][b[i]] = max(f[i][b[i]], f[i - 1][j] + a[i]);
        }
    }
    int mx = 0;
    for (int i = 0; i <= 3; i++)mx = max(mx, f[n][i]);
    cout << mx;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

I-你说得对，但是……_

问题解析

但是原神是一款…………

首先我们要知道，11 并不是一个质数，然后我们再知道，对于相邻的两个数，它们的最大公约数是 11 。

那么我们可以先按照 a[i]=ia[i] = i 的方式来排列，然后依次判断 gcd(a[i]，i)gcd(a[i]，i) 是否为质数，如果为质数，我们就可以把它和下一位数：a[i+1]a[i+1] 进行交换，这样可以保证 a[i]a[i] 和 a[i+1]a[i+1] 和他们对应位置数的最大公约数都是 11 。

由于这一步会使得我们的字典序变大，所以如果 gcd(a[i]，i)gcd(a[i]，i) 不为质数，我们就不用交换了。

特别的，如果 gcd(a[n]，n)gcd(a[n]，n) 为质数，因为已经没有下一位了，所以我们只能和上一位，即：a[n−1]a[n-1] 进行交换。

这里判断质数我用的是 Miller−RabinMiller-Rabin 素性测试，不认识的大家可以学习一下。用试除法应该也是可以过的。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>

//#pragma GCC optimize(2)
//#pragma GCC optimize(3)

#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50, MOD = 1e9 + 7;

int a[N];

int gcd(int a,int b)
{
    return a%b==0?b:gcd(b,a%b);
}

ll qmul(ll a,ll b,ll mod)//快速乘
{
    ll c=(ld)a/mod*b;
    ll res=(ull)a*b-(ull)c*mod;
    return (res+mod)%mod;
}
ll qpow(ll a,ll n,ll mod)//快速幂
{
    ll res=1;
    while(n)
    {
        if(n&1) res=qmul(res,a,mod);
        a=qmul(a,a,mod);
        n>>=1;
    }
    return res;
}
bool is_prime(ll n)//Miller Rabin Test
{
    if(n<3||n%2==0) return n==2;//特判
    ll u=n-1,t=0;
    while(u%2==0) u/=2,++t;
    ll ud[]={2,325,9375,28178,450775,9780504,1795265022};
    for(ll a:ud)
    {
        ll v=qpow(a,u,n);
        if(v==1||v==n-1||v==0) continue;
        for(int j=1;j<=t;j++)
        {
            v=qmul(v,v,n);
            if(v==n-1&&j!=t){v=1;break;}//出现一个n-1，后面都是1，直接跳出
            if(v==1) return 0;//这里代表前面没有出现n-1这个解，二次检验失败
        }
        if(v!=1) return 0;//Fermat检验
    }
    return 1;
}

void solve()
{
    int n;
    cin >> n;
    for(int i=1;i<=n;i++)a[i]=i;
    for (int i = 2; i <= n; i ++)
    {
        int x=gcd(a[i],i);
        if(is_prime(x))
        {
            if(i<n)swap(a[i],a[i+1]);
            else swap(a[i-1],a[i]);
        }
    }
    for(int i=1;i<=n;i++)cout<<a[i]<<" ";
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

J-蓝色妖精小姐的树

问题解析

从数据的方式和表情包来看，都告诉了我们这题用的是珂朵莉树。

珂朵莉树是一个神奇的算法，专门负责处理这类区间修改（区间赋值）和区间询问问题，做法很暴力，所以一般只适用于随机数据，对于出题人自己造的数据，是可以把珂朵莉树给卡到超时的。

具体的大伙可以去看看珂朵莉树的由来。

至于树的问题，我们可以通过 dfsdfs 序来确定每一个子树的根 uu 负责的是哪个区间，修改这一整个子树，就相当于修改这个区间。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>

//#pragma GCC optimize(2)
//#pragma GCC optimize(3)

#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 1e5 + 50, MOD = 1e9 + 7;

struct node {
    int l, r;
    mutable int val;
    node(int l, int r = -1, int val = 0) :l(l), r(r), val(val) {}
    bool operator<(const node& o)const
    {
        return l < o.l;
    }
};

set<node>s;

int qpow(int x, int k, int mod = 1e9 + 7)
{
    int num = 1;
    x %= mod;
    while (k)
    {
        if (k & 1)num = num * x % mod;
        k >>= 1;
        x = (x * x) % mod;
    }
    return num;
}

//核心操作，将包含pos点的区间分成[l,pos-1]和[pos,r]两个区间
set<node>::iterator split(int pos)
{
    //找l不小于pos的第一个node
    auto it = s.lower_bound(node(pos));
    if (it != s.end() && it->l == pos)
        return it;
    --it;
    if (pos > it->r)return s.end();
    int l = it->l, r = it->r, val = it->val;
    s.erase(it);
    s.insert(node(l, pos - 1, val));
    //return的是插入节点后，该节点在set的iterator
    return s.insert(node(pos, r, val)).first;
}

//区间加值
void add(int l, int r, int val = 1)
{
    split(l);
    auto itr = split(r + 1), itl = split(l);
    //给itl到itr之间所有元素加上val
    for (; itl != itr; ++itl)itl->val += val;
}

//区间赋值
void assign(int l, int r, int val = 0)
{
    split(l);
    auto itr = split(r + 1), itl = split(l);
    //删除itl到itr-1的全部元素
    s.erase(itl, itr);
    s.insert(node(l, r, val));
}

//如果reversed为0，说明找第k小元素；反之找第k大元素
int myrank(int l, int r, int k, bool reversed = 0)
{
    if (reversed)k = r - l + 2 - k;
    split(l);
    auto itr = split(r + 1), itl = split(l);
    vector<PII>v;
    for (; itl != itr; ++itl)
        v.push_back({ itl->val,itl->r - itl->l + 1 });
    sort(v.begin(), v.end());
    for (auto i : v)
    {
        k -= i.second;
        if (k <= 0)return i.first;
    }
    return -1;
}

//计算区间[l,r]所有元素的k次幂的和
int sum(int l, int r, int k, int mod = 1e9 + 7)
{
    split(l);
    auto itr = split(r + 1), itl = split(l);
    int res = 0;
    for (; itl != itr; ++itl)
        res = (res + (itl->r - itl->l + 1) * qpow(itl->val, k, mod) % mod) % mod;
    return res;
}

int seed, vmax;
int a[N], b[N];
PII c[N];

vector<int>tree[N];

int rnd()
{
    int ret = seed;
    seed = (seed * 7 + 13) % MOD;
    return ret;
}

void dfs(int x, int y, int&z)
{
    z++;
    c[x].first = z;
    for (auto& i : tree[x])
    {
        if (i == y)continue;
        
        dfs(i, x, z);
    }
    c[x].second = z;
}

void solve() 
{
    int n, m;
    cin >> n >> m >> seed >> vmax;
    for (int i = 1; i <= n; i++)
    {
        a[i] = (rnd() % vmax) + 1;
        //cout << a[i] << " ";
    }
    for (int i = 2; i <= n; i++)
    {
        int x = (rnd() % (i - 1)) + 1;
        tree[i].push_back(x);
        tree[x].push_back(i);
    }
    int idx = 0;
    dfs(1, 0, idx);
    for (int i = 1; i <= n; i++)
    {
        s.insert(node(c[i].first, c[i].first, a[i]));
    }
    //cout << endl;
    for (int i = 1; i <= m; i++)
    {
        int op = (rnd() % 2) + 1;
        int u = (rnd() % n) + 1;
        int x = (rnd() % vmax) + 1;
        int l = c[u].first, r = c[u].second;
        //cout << op << " " << l << " " << r << " " << x << " " << y << endl;
        if (op == 1)assign(l, r, x);
        else if (op == 2)cout << sum(l, r, x) << endl;
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}
全部评论

相关推荐

头像
11-25 14:57
中金所技术公司_业务
offer比较的一些建议：互联网、银行、金融科技、国企、央企
【专栏介绍】银行、证券等金融科技岗一直是很火热的校招求职方向，但有很多应届生由于对这个方向认知不足而没有留意机会，也有很多同学擅长互联网、但却不知道如何准备金融科技岗的笔面试，特别是对金融科技岗的工作性质、行业形势、就业前景等也不太清晰。因此，作为混迹多年金融科技行业的打工人，哨哥决定整理专栏《银行等金融科技行业校招求职攻略》，通过职场真实经验分享减少金融科技岗的校招求职“信息差”，帮助牛友们摆脱学生思维，摆脱误导信息，拿到满意offer！【作者介绍】作为创作者，哨哥已经持续多年为在校生们提供求职辅导和职业规划，也持续多年和金融科技职场人士交流，覆盖银行、保险、证券、期货、公募基金、私募、信托...
牛客吹哨人：25届需要银行等金融科技、国企央企组织的话，留言哦~
投递阿里巴巴等公司10个岗位 > 银行等金融科技行业校招求...
点赞 评论 收藏
分享
11-29 11:21
门头沟学院 Java
接offer了，结束秋招
总包48.5w，意想不到的价格
想开了的垂耳兔很喜欢拱白菜：转人工
点赞 评论 收藏
分享
10-24 14:41
蚌埠坦克学院 Java
不是哥们…还以为又行了
不是哥们，以为是又来机会了新一批笔试
有趣的牛油果开挂了：最近这个阶段收到些杂七杂八的短信是真的烦
点赞 评论 收藏
分享
头像
11-26 16:16
山东大学 嵌入式软件工程师
提前预习，Leader的PUA话术
实习er：“你表现得很好，部门领导给你打分都很高，转正希望很大”“过两天新来几个实习生，他们简历很优秀，在XX大厂实习过”“这个项目单独给你做，挤一挤时间完成他，其他实习生我没给，对转正有用”“就你这工作态度，以后哪个公司敢要你？”“这么简单的任务都完成不好，你还想不想转正了？”“你别觉得自己了不起，你离我的要求还差得远呢。”“别人怎么都能做好，就你不行？你是不是能力有问题？”“你要是再这样下去，实习评价肯定好不了。”“我对你很失望，你根本没有发挥出你的潜力。”“你怎么这么笨啊？教了你多少次了还不会，我都怀疑你是不是根本没用心。”“你看看你做的这点事儿，就这水平还大学生呢？我随便找个高中生都比...
牛肉爆大虾：我对你是比较失望的，我当初给你的评级是高于你的面试表现的.......（省略200字）
你觉得哪一届的校招最难？ 上班苦还是上学苦呢？
点赞 评论 收藏
分享
评论
1
收藏
分享

全站热榜

正在热议
# 拼多多求职进展汇总 #
238204次浏览 2041人参与
# ai智能作图 #
30673次浏览 368人参与
# 阿里云管培生offer #
63426次浏览 1764人参与
# 25届秋招总结 #
414749次浏览 4164人参与
# 实习，投递多份简历没人回复怎么办 #
2442318次浏览 34752人参与
# 地方国企笔面经互助 #
7086次浏览 17人参与
# 北方华创开奖 #
67337次浏览 554人参与
# 我在牛爱网找对象 #
74967次浏览 556人参与
# 虾皮求职进展汇总 #
94532次浏览 768人参与
# 机械求职避坑tips #
23881次浏览 249人参与
# 发工资后，你做的第一件事是什么 #
9591次浏览 43人参与
# 我的实习求职记录 #
6136637次浏览 84036人参与
# 25届机械人为了秋招做了哪些准备？ #
26501次浏览 364人参与
# 投格力的你，拿到offer了吗？ #
47553次浏览 337人参与
# 机械人怎么评价今年的华为 #
158120次浏览 1353人参与
# 华为工作体验 #
111952次浏览 867人参与
# 实习想申请秋招offer，能不能argue薪资 #
36458次浏览 310人参与
# 如果再来一次，你还会选择这个工作吗？ #
116906次浏览 1149人参与
# 国央企笔面经互助 #
88659次浏览 897人参与
# 在职场上，你最讨厌什么样的同事 #
6250次浏览 92人参与
# 产运销实习日记 #
28288次浏览 326人参与
# 软件开发投递记录 #
1482341次浏览 23949人参与
牛客网
牛客企业服务