2023年福建农林大学程序设计校赛个人题解(无D解析)
A-这是一道原题
问题解析
从绿色材料合成到金色材料。
用 w h i l e while while 循环判断材料数是否能合成,能就合,合成后下一级材料数增加,原料数加上合成出的材料数。
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-健康阳光,积极向上!
问题解析
想不到什么很好做法,直接暴力了。
根据贪心来说,要想结果越小,删掉的质因数就要越大。
对所有数进行质因数分解并记录下来,最后对所有质因数从大到小排序,把最前面 k k k个质数当作我们要删除的质因子。
然后我们把剩下的质因子全部乘起来就行。
分解因数的复杂度在 O ( log 2 a i ) O(\log_{2}{a_i}) O(log2ai) 到 O ( n ) O(\sqrt n) O(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-字一色大四喜四杠子四暗刻单骑役满确定!
问题解析
遍历字符串看有没有 7 z 7z 7z 就行。
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-可爱即是正义!
问题解析
区间前缀和模板,枚举所有 r r r 行 c c c 列的子矩阵然后用矩阵前缀和快速算结果,维护最大值就行。
注意数据可能使得最大的矩阵和为负数,维护最大值的变量初始值要够小。
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)的!
问题解析
基础的计数 d p dp dp 。
设状态转移数组 f f f , f [ i ] f[i] f[i] 表示前 i i i 个字符的分割方式有 f [ i ] f[i] f[i] 种。
状态转移:如果一个长为 l e n len len 的字符串 s i si si 能匹配字符串 s t r str str 上 j j j 到 j − l e n + 1 j-len+1 j−len+1 的这一段,则有 f [ j + l e n − 1 ] = f [ j + l e n − 1 ] + f [ j − 1 ] f[j+len-1] = f[j+len-1] + f[j-1] f[j+len−1]=f[j+len−1]+f[j−1] 。
思路不难,主要是匹配字符串的方法。
遍历字符串 s t r str str ,枚举每个位置 j j j ,判断以当前字符为起点是否有字符串 s i si si 能和它匹配。
这里可以用字符串哈希快速匹配,预处理 s t r str str 的哈希数组复杂度为: O ( l e n g t h ( s t r ) ) O(length(str)) O(length(str)) ,预处理 n n n 个字符串 s s s 的哈希值的复杂度为: O ( ∑ i = 0 n l e n g t h ( s i ) ) O(\sum_{i=0}^nlength(s_i)) O(∑i=0nlength(si)) 。
每次匹配字符串复杂度为: O ( 1 ) O(1) O(1) 。
总复杂度: O ( ∑ i = 0 n l e n g t h ( s i ) ∗ l e n g t h ( s t r ) ) O(\sum_{i=0}^n length(s_i) * length(str)) O(∑i=0nlength(si)∗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-圆皱率_
问题解析
这题面真是给我笑死,不过我觉得题意不是很清楚,一开始都不理解要干啥,最好优化一下或者给样例加个解释罢。
(话说我这种又玩原又玩粥又玩农的算啥皮)
这题是想让你从里面选择一个子序列,使得子序列的和最大,但是不能让 a a aa aa 和 A A AA AA 挨着。
我们先把豌豆的三种基因状态 A A 、 A a 、 a a AA、Aa、aa AA、Aa、aa 分别设为 1 、 2 、 3 1、2、3 1、2、3 。
动态规划。
设二维状态转移数组 f f f , f [ i ] [ j ] f[i] [j] f[i][j] 表示在前 i i i 个豌豆中取,且最后一个豌豆状态为 j j j 的最大价值为 f [ i ] [ j ] f[i] [j] f[i][j] , j = 0 j = 0 j=0 表示一个豌豆都没取。
状态转移:
- 每次都有: f [ i ] [ j ] = f [ i − 1 ] [ j ] f[i] [j] = f[i-1] [j] f[i][j]=f[i−1][j] 。
- 如果当前的豌豆状态为 1 1 1 ,则 f [ i ] [ 1 ] = m a x ( f [ i ] [ 1 ] , f [ i ] [ j ] + a i ) ( j = 0 , 1 , 2 ) f[i] [1] = max(f[i] [1],f[i] [j] + a_i) (j = 0,1,2) f[i][1]=max(f[i][1],f[i][j]+ai)(j=0,1,2)。
- 如果当前的豌豆状态为 2 2 2 ,则 f [ i ] [ 2 ] = m a x ( f [ i ] [ 1 ] , f [ i ] [ j ] + a i ) ( j = 0 , 1 , 2 , 3 ) f[i] [2] = max(f[i] [1],f[i] [j] + a_i) (j = 0,1,2,3) f[i][2]=max(f[i][1],f[i][j]+ai)(j=0,1,2,3)。
- 如果当前的豌豆状态为 3 3 3 ,则 f [ i ] [ 3 ] = m a x ( f [ i ] [ 1 ] , f [ i ] [ j ] + a i ) ( j = 0 , 2 , 3 ) f[i] [3] = max(f[i] [1],f[i] [j] + a_i) (j = 0,2,3) f[i][3]=max(f[i][1],f[i][j]+ai)(j=0,2,3)。
最后答案为: m a x ( f [ n ] [ j ] ) ( j = 0 , 1 , 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-你说得对,但是……_
问题解析
但是原神是一款…………
首先我们要知道, 1 1 1 并不是一个质数,然后我们再知道,对于相邻的两个数,它们的最大公约数是 1 1 1 。
那么我们可以先按照 a [ i ] = i a[i] = i a[i]=i 的方式来排列,然后依次判断 g c d ( a [ i ] , i ) gcd(a[i],i) gcd(a[i],i) 是否为质数,如果为质数,我们就可以把它和下一位数: a [ i + 1 ] a[i+1] a[i+1] 进行交换,这样可以保证 a [ i ] a[i] a[i] 和 a [ i + 1 ] a[i+1] a[i+1] 和他们对应位置数的最大公约数都是 1 1 1 。
由于这一步会使得我们的字典序变大,所以如果 g c d ( a [ i ] , i ) gcd(a[i],i) gcd(a[i],i) 不为质数,我们就不用交换了。
特别的,如果 g c d ( a [ n ] , n ) gcd(a[n],n) gcd(a[n],n) 为质数,因为已经没有下一位了,所以我们只能和上一位,即: a [ n − 1 ] a[n-1] a[n−1] 进行交换。
这里判断质数我用的是 M i l l e r − R a b i n Miller-Rabin Miller−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-蓝色妖精小姐的树
问题解析
从数据的方式和表情包来看,都告诉了我们这题用的是珂朵莉树。
珂朵莉树是一个神奇的算法,专门负责处理这类区间修改(区间赋值)和区间询问问题,做法很暴力,所以一般只适用于随机数据,对于出题人自己造的数据,是可以把珂朵莉树给卡到超时的。
具体的大伙可以去看看珂朵莉树的由来。
至于树的问题,我们可以通过 d f s dfs dfs 序来确定每一个子树的根 u u u 负责的是哪个区间,修改这一整个子树,就相当于修改这个区间。
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;
}
文章评论