hihocoder [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 ;

 }

巴特西

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

A：最小排列

B：最大前缀和

C：质数

D: 随机排列2

最新文章

热门文章