hihocoder [Offer收割]编程练习赛61

[Offer收割]编程练习赛61

A：最小排列

给定一个长度为m的序列b[1..m]，再给定一个n，求一个字典序最小的1~n的排列A，使得b是A的子序列。

贪心即可，b是A的子序列，把不在b中的元素，从小到大放在队列中，再把b按顺序放入另一个队列中，每次取出两队列中较小值即可。

 #include<bits/stdc++.h>
 using namespace std;
 typedef long long ll;
 bool vis[];
 queue<int>q1, q2;
 vector<int>ans;
 int main()
 {
     int n, m, x;
     cin >> n >> m;
     for(int i = ; i < m; i++)scanf("%d", &x), vis[x] = , q1.push(x);
     for(int i = ; i <= n; i++)if(!vis[i])q2.push(i);
     while(!q1.empty() && !q2.empty())
     {
         if(q1.front() > q2.front())
         {
             ans.push_back(q2.front());
             q2.pop();
         }
         else ans.push_back(q1.front()), q1.pop();
     }
     while(!q1.empty())ans.push_back(q1.front()), q1.pop();
     while(!q2.empty())ans.push_back(q2.front()), q2.pop();
     for(int i = ; i < ans.size(); i++)
         printf("%d\n", ans[i]);
     return ;
 }

B：最大前缀和

给定一个长度为n的序列a[1..n]，现在你可以进行最多k次操作，每次操作能交换序列中任意两个数，要求最大化最大前缀和的值。

最大前缀和的定义：

k最大为3

思路：

先求出前缀和，比如对于样例：

如果交换两个值a[l]和a[r]，那么[l, r）的前缀和就加上a[r] - a[l]

如果要枚举l和r的话就达到n平方的复杂度，所以可以直接枚举sum数组

每次枚举一个前缀和，那么在前缀和包括的数字中选取一个最小值，不包括的数字中选取一个最大值，那么就可以直接求出该前缀和经过转化可以达到的最大值，可以用线段树查询区间最小值和最大值，时间复杂度O（nlog(n)）

对于k=2的情况，一开始我以为是在k=1的解的情况下，交换那两个值，更新前缀和，再重新模拟一次，但是这样是错误的。

反例：

　　　10 3
　　　　-10 9 -8 7 -6 5 -4 3 2 1

前缀和：-10 -1 -9 -2 -8 -3 -7 -4 -2 -1

在第一次循环找最大的前缀和时，找到交换的点是-10 和 7

　　　　7 9 -8 -10 -6 5 -4 3 2 1

前缀和 7 16 8 -2 -8 -3 -7 -4 -2 -1

最大前缀和为16

在此基础上第二次找到的最大前缀和是，交换-8 5

　　　　7 9 5 -10 -6 -8 -4 3 2 1

前缀和：7 16 21 11 5 -3 -7 -4 -2 -1

最大前缀和：21

在此基础上，第三次找最大前缀和，交换 -10 3

　　　　7 9 5 3 -6 -8 -4 -10 2 1

前缀和 7 16 21 24 18 10 6 -4 -2 -1

最大前缀和：24

但是正解应该是在最开始基础上用-10 -8 -6交换3 2 1

最开始：-10 9 -8 7 -6 5 -4 3 2 1

前缀和：-10 -1 -9 -2 -8 -3 -7 -4 -2 -1

正解：3 9 2 7 1 5 -4 -10 -8 -6

最大前缀和：27

那么之前的方法就不适用了吗？

不是的。

在k=1的时候，枚举每个前缀和，求出在前缀和中的数字最小值，和不在前缀和中数字的最大值。

那么k=2的时候，枚举每个前缀和，求出在前缀和中数字的最小和次小，和不在前缀的最大和次大，k=3时同理

那么还可以用线段树吗?

当然可以，在取出最小值时，把最小值的那个点更改成INF，再求最小值就是次小值了，同理可以求出。

线段树不熟练，代码啰嗦，这道题也可以直接用set模拟。

 #include<bits/stdc++.h>
 using namespace std;
 typedef long long ll;
 const int maxn = +;
 #define MID(l, r) ((l) + ((r) - (l)) / 2)
 #define lc ((o)<<1)
 #define rc ((o)<<1|1)
 ll a[maxn];
 struct node
 {
     ll l, r, mmax, mmin, idmin, idmax;
 }tree[maxn];
 void pushup(int o)
 {
     if(tree[lc].mmax > tree[rc].mmax)
     {
         tree[o].mmax = tree[lc].mmax;
         tree[o].idmax = tree[lc].idmax;
     }
     else
     {
         tree[o].mmax = tree[rc].mmax;
         tree[o].idmax = tree[rc].idmax;
     }
     if(tree[lc].mmin > tree[rc].mmin)
     {
         tree[o].mmin = tree[rc].mmin;
         tree[o].idmin = tree[rc].idmin;
     }
     else
     {
         tree[o].mmin = tree[lc].mmin;
         tree[o].idmin = tree[lc].idmin;
     }
 }
 void build(ll o, ll l, ll r)
 {
     tree[o].l = l, tree[o].r = r;
     if(l == r)
     {
         tree[o].mmax = tree[o].mmin = a[l];
         tree[o].idmin = tree[o].idmax = l;
         return;
     }
     ll m = MID(l, r);
     build(lc, l, m);
     build(rc, m + , r);
     pushup(o);
     //cout<<o<<" "<<l<<" "<<r<<" "<<tree[o].mmax<<" "<<tree[o].mmin<<endl;
 }
 ll ql, qr;//查询区间[ql, qr]中的max,min
 ll ans_max, ans_min;
 ll max_id, min_id;
 void query(int o)
 {
     if(ql <= tree[o].l && qr >= tree[o].r)//[L, R]包含在[ql, qr]区间内，直接用该节点的信息，达到线段树查询快的操作
     {
         if(ans_max < tree[o].mmax)
         {
             ans_max = tree[o].mmax;
             max_id = tree[o].idmax;
         }
         if(ans_min > tree[o].mmin)
         {
             ans_min = tree[o].mmin;
             min_id = tree[o].idmin;
         }
         return;
     }
     int m = MID(tree[o].l, tree[o].r);
     if(ql <= m)query(lc);
     if(qr > m)query(rc);
 }
 //单点更新，a[p] = v;
 ll p, v;
 void update(ll o)
 {
     if(tree[o].l == tree[o].r)
     {
         tree[o].mmax = v;
         tree[o].mmin = v;
         return;
     }
     ll m = MID(tree[o].l, tree[o].r);
     if(p <= m)update(lc);
     else update(rc);
     pushup(o);
 }

 ll sum[maxn];
 ll INF = 1e18 + ;
 int main()
 {
     ll n, k;
     scanf("%lld%lld", &n, &k);

     ll MAX = -INF, L = , R = , c = ;
     for(int i = ; i <= n; i++)
     {
         scanf("%lld", &a[i]);
         sum[i] = sum[i - ] + a[i];
         MAX = max(MAX, sum[i]);
     }
     build(, , n);

     ll lid[], lmin[], rid[], rmax[];
     for(int i = k; i < n - k + ; i++)
     {
         for(int j = ; j <= k; j++)
         {
             ans_min = INF;
             ql = , qr = i, query();
             lid[j] = min_id, lmin[j] = ans_min;
             p = min_id, v = INF, update();

             ans_max = -INF;
             ql = i + , qr = n, query();
             rid[j] = max_id, rmax[j] = ans_max;
             p = max_id, v = -INF, update();
         //cout<<i<<endl;
         //cout<<lid<<" "<<lmin<<" "<<rid<<" "<<rmax<<endl;
         }
         ll l = , r = ;
         for(int j = ; j <= k; j++)
         {
             l += lmin[j];
             r += rmax[j];
             p = lid[j], v = lmin[j], update();
             p = rid[j], v = rmax[j], update();
         }
         if(sum[i] + r - l > MAX)
         {
             MAX = sum[i] + r - l;
         }
     }
     cout<<MAX<<endl;
     return ;
 }

集合的写法：

 #include<bits/stdc++.h>
 using namespace std;
 typedef long long ll;
 const int maxn = 1e6 + ;
 const int mod = 1e9 + ;

 set<int>lmin, rmax;
 map<int, int>lnum, rnum;
 void add(set<int>&a, map<int, int>&b, int x)//在可重复集合中加入x
 {
     a.insert(x);
     b[x]++;
 }
 void sub(set<int>&a, map<int, int>&b, int x)//在可重复集合中删除x
 {
     b[x]--;
     if(b[x] == )a.erase(a.find(x));
 }
 int Find(set<int>&a, map<int, int>&b, bool flag)//在可重复集合中取出最小值 最大值
 {
     set<int>::iterator it;
     int ans;
     if(flag)//取出最小值
     {
         it = a.begin();
         ans = *it;
         b[ans]--;
         if(b[ans] == )a.erase(it);
     }
     else
     {
         it = a.end();
         it--;
         ans = *it;
         b[ans]--;
         if(b[ans] == )a.erase(it);
     }
     return ans;
 }
 int a[], b[], c[];
 int main()
 {
     int n, k;
     cin >> n >> k;
     for(int i = ; i <= n; i++)
         cin >> a[i];
     ll sum = , ans = ;
     for(int i = ; i <= k; i++)add(lmin, lnum, a[i]), sum += a[i];
     ans = sum;
     for(int i = k + ; i <= n; i++)add(rmax, rnum, a[i]);
     for(int i = k + ; i <= n - k + ; i++)
     {
         ll tot = ;
         for(int j = ; j <= k; j++)b[j] = Find(lmin, lnum, );//在前缀集合中取出前k小
         for(int j = ; j <= k; j++)c[j] = Find(rmax, rnum, );//在非前缀集合中取出前k大
         for(int j = ; j <= k; j++)tot = tot + c[j] - b[j];//计算差值
         ans = max(ans, sum + tot);//更新答案
         sum += a[i];//更新答案
         for(int j = ; j <= k; j++)//将取出的数字放回去
         {
             add(lmin, lnum, b[j]);
             add(rmax, rnum, c[j]);
         }
         add(lmin, lnum, a[i]);//前缀加上该点
         sub(rmax, rnum, a[i]);//非前缀删除该点
     }
     cout<<ans<<endl;
     return ;
 }

C：质数

我们称一个数是好的数，当且仅当他可以写成质数个质数的乘积。

现在给定l,r，求[l,r]内有几个好的数。第一行两个正整数l,r，满足1 ≤ l ≤ r ≤ 10⁹，且0 ≤ r-l ≤ 10⁶。

思路：

直接用素数线性筛法，筛选小素数的时候，把l-r区间中该素数的倍数过一遍，求出每个数的分解式中该素数的指数，最后就可以求出这个区间中的每一个数字由x个素数相乘，再判断这个x是不是素数即可

 #include<bits/stdc++.h>
 using namespace std;
 typedef long long ll;
 const int maxn = +;
 int is_prime[maxn], tot[maxn];//这是ab区间上的素数
 bool is_prime_small[maxn];//这是(2,根号b)区间的素数
 int sum_prime(ll a, ll b)//[a, b]区间内素数筛选
 {
     for(ll i = ; i * i <= b; i++)is_prime_small[i] = ;
     is_prime_small[] = is_prime_small[] = ;
     for(ll i = ; i <= b - a; i++)is_prime[i] = i + a;
     for(ll i = ; i * i <= b; i++)
     {
         if(is_prime_small[i])//如果是小区间上的素数那就直接筛选小区间和大区间
         {
             for(ll j =  * i; j * j <= b; j += i)is_prime_small[j] = ;//筛选小区间

             for(ll j = max(2LL, (a + i - ) / i) * i; j <= b; j += i)//j初始化的时候是ab区间中第一个i的倍数
             {
                 //cout<<j<<" "<<i<<" "<<is_prime[j - a]<<endl;
                 while(is_prime[j - a] % i == )
                 {
                     is_prime[j - a] /= i;
                     tot[j - a]++;
                 }
             }
         }
     }
     int sum = ;
     for(ll i = ; i <= b - a; i++)if(is_prime[i] != )tot[i]++;
     for(ll i = ; i <= b - a; i++)if(is_prime_small[tot[i]])sum++;
     return sum;
 }

 int main()
 {
     //freopen("out.txt", "w", stdout);
     int a, b;
     cin >> a >> b;
     cout<<sum_prime(a, b)<<endl;;
     return ;
 }

D: 随机排列2

一个长度为n的排列p[1..n]的价值是这样定义的：一开始你有一个数x，x的值一开始为0，然后对于1 ≤ i ≤ n，如果p[i] > x，则令x=p[i]；排列p[1..n]的价值就是x的值的改变次数。

求对于所有长度为n的[1,2…n]的排列，他们的价值之和，答案对109+7取模。

找规律：

n比较小的时候先算出答案

n = 1 ans = 1

n = 2 ans = 3

n = 3 ans = 11

n = 4 ans = 50

感觉没什么规律。

首先对于1-n的排列中，如果n是第一个，那么x值的改变次数就是1，这种情况有(n - 1)！种情况

那就把答案先加上n - 1的阶乘

用上面的总数减去(n - 1)!看看还差多少

n = 1 ans = 0! + 0 =

n = 2 ans = 1! + =

n = 3 ans = 2! + =

n = 4 ans = 3! + = 50

感觉有点规律：

上述同色的数字中：

2 = 2 * 1

9 = 3 * 3

44 = 4 * 11

可以推出规律：a[n] = （n - 1)! + n * a[n - 1]

下面来解释一下这个式子

首先对于(n - 1)!这个没什么好说的，就是n为首位的排列数目

那么n*a[n - 1]是怎么来的呢，其实这里我也证明不了，只是找规律发现的

下面举个例子

a[3] = 9

那么3的全排列为 1 2 3 、1 3 2 、2 1 3、2 3 1、3 1 2、3 2 1

那么在这个基础上放4，这里4不放在首位，因为放在首位的已经在(n - 1)!计算过了。（请看下图）

首先找到规律发现，加入4之后，序列和原来序列相比多了11，就等于a[3]

而且原来的序列重复了3次，那么价值就是3*a[3]

上面两个加起来就是4*a[3]

所以a[4] = 3! + 4 * a[3]

对于a[n]的话也是这样的，n-1的序列会重复n-1次，这里就加上了(n - 1) * a[n - 1]

而且最终的每个序列和原来相比总增加量也为a[i]（这里只是发现的规律，至于为什么增加这么多我也不知道）

a[n] = (n - 1)! + n * a[n - 1]

知道了这个规律就可以直接写代码了

 #include<bits/stdc++.h>
 using namespace std;
 typedef long long ll;
 const int maxn = 1e6 + ;
 const int mod = 1e9 + ;
 ll a[maxn];
 int main()
 {
     ll p = ;
     a[] = ;
     for(int i = ; i < maxn; i++)
     {
         p = p * (i - ) % mod;//p表示(i - 1)的阶乘
         a[i] = p + i * a[i - ];
         a[i] %= mod;
     }
     int n;
     cin >> n;
     cout<<a[n]<<endl;
     return ;
 }