2019.11.12 题解报告

2019.11.12 题解报告

\[\text{我也是个广♂东♂人所以我们可能是老♂乡}\]
\[\text{By:Unluckiestblock}\]

答题情况:

总成绩 : 170 , 排名 : /
T1 : 100 T2 : 50 T3 : 20

各题目分析:

题目 1 :
预估成绩 : 100 实际成绩 : 100 考试用时 : 9 : 12 ~ 10 : 04
今天改变了考试策略 , 花费了1个半小时的时间考虑各题目 ,
写的时候思路非常清晰 , 写了线段树 , 很快实现 , 过掉大样例 .
题目 2 :
预估成绩 : 50 实际成绩 : 50 考试用时 : 10 : 13 ~ 10 : 51
一开始考虑线段树做法 , 发现需要用到能够查询排名的数据结构
由于不会平衡树 , 就考虑部分分
发现可以使用优先队列水过前50%的数据 , 验证正确性后很快写完
过掉大样例
题目 3 :
预估成绩 : 20 实际成绩 : 20 考试用时 : 10 : 05 ~ 10 : 13
没有什么感觉 , 先写了 20 分的部分分 , 之后就先考虑T2

题目解析:

T1:

题目要求:

给定一长度为N的数列, 数的值域为[1,N]
给定M个区间[Li, Ri], 要求使 [Li, Ri]中没有重复的数
求字典序最小的填数方案

分析题意:
暂不考虑M个限制条件, 先将数列全部填为1

对区间之间的情况进行分类讨论:

对于两互不相交的限制区间:
显然, 应将两区间内分别填入 [1, Ri-Li+1]
对于两相交的限制区间:
- 例: [1,5]和[4,8]
  前5个数字显然应填入 1 ~ 5,
  由于第6个位置仅被 [4,8] 覆盖, 则可填入[1,3] 内的数
  则6 ~ 8应填入 : 1 2 3
  可能会出现数字"重复利用" 的情况

考虑将当前位置可选择的数存入集合.
将各限制区间按照左端点升序主, 右端点升序次进行排序
然后按照坐标升序, 枚举各限制区间
可以发现, 由于左端点升序, 则枚举的区间左侧的数全部可以被回收

设置两指针, 一指向最后一个被回收的位置, 一指向当前应被填入的位置
对于当前枚举的区间[Li, Ri] :

将回收指针右移至 Li - 1, 同时回收对应位置填入的数
将填入指针右移至Ri, 每次右移取出集合内最小的数, 填入指针位置

可以使用 set/priority_queue 来维护最小的没有被填入的数
也可使用线段树通过打标记进行维护
单次删除/插入复杂度都为 O(logn)

由于一个位置只会被两指针分别指向一次,
即: 只会发生n次插入与 n次删除操作,
故总复杂度为O(nlogn)

T2:

题目要求:
给定一长度为N数列 a[i] 和数字 M, 对于每一个 i, 计算出在 [1,i-1] 中,
最多能选多少个数字, 使得这些数字的和不超过 M - a[i].
输出未选择的数字数

50 % 数据:
使用两优先队列维护 [1,i]中已选的数和 [1,i]中未选的数
已选的数使用大根堆, 未选的数使用小根堆

对于每一枚举的i, 按顺序完成下列三过程:

循环将大根堆堆顶元素与小根堆堆顶元素进行比较,
若交换后使选择的数总和变小, 则进行交换
循环将大根堆堆顶元素移入小根堆,
直至可使第i个元素插入后选择的数总和 <=M
循环将小根堆堆顶元素移入大根堆,
直至可使第i个元素插入后选择的数总和 <=M
插入第i个元素, 此时大根堆内元素数量, 即最多能选择的数字数

100 % 数据:
满分做法可以使用权值线段树.
线段树上每个结点维护对应权值区间范围内有多少个数字以及这些数字的和是多少.

查询时每次判断左子树对应区间范围内有多少数字,相加后的和是否超过限制.
超过则向左递归否则向右递归.

时间复杂度 O(NlogN)，期望得分 100 分.

T3:

题目要求:
给定一长为 N 的数列 a[i]. 数列中数字有正有负.
要求选出数列中前若干个数字, 分成 K 段, 使得每一段的和的最大值尽可能小.

20 % 数据:
K = 1
即: 查询最小前缀和
在取前缀和时记录最小的前缀和即可

50 % 数据:
要求最大的最小, 想到二分答案. 关键在于二分答案 mid 后怎么判断.
当 K 不等于 1 时, 可使用 DP 来解决.

用 f[i]表示前 i 个数字中，最多可以分成多少段, 使得每一段的和都小于等于 mid.
若存在 f[i]>=K，则 mid 是可行解，往小的范围继续二分.
否则 mid 不合法, 往大的范围继续二分.
转移方程如下：
f[i] = max(f[j]+1), 其中 S[i]-S[j]<=mid
S 数组为数列 a 的前缀和数组, 正确性显然.
时间复杂度为 O(logRange*N^2)，结合 K=1 的情况，期望得分 50 分。

100 %数据:
解法：二分+DP+离散化+树状数组

50% 数据中这个 DP 很慢. 主要是状态转移太慢. 考虑如何优化状态转移.
当 S[i]和 mid 固定时, 符合条件的 j 就是那些满足 S[j]>=S[i]-mid 的 j.
而转移时就是在这些符合条件的 j 里面找一个 f[j]的最大值.很容易想到使用数据结构来优化。

理论上我们可以使用权值线段树,
但这里由于 a[i]的范围很大, 其部分和 S[j]的范围就更大了,使用权值线段树容易超时.

而且我们发现 S[j]是已知的且不变的，所以我们使用预处理离散化+树状数组会更好:
先预处理出 S 数组, 然后离散化.
建立树状数组记录对应前缀和大小为 S[j]时, 最大的 f[j]是多少.
那么接下来每次查询时就是查询树状数组中某个前缀的最大值.
时间复杂度为 O(logRange*NlogN). 期望得分 100 分.

代码实现:

T1:

考场代码 (正解):

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <ctype.h>
#define ls (now << 1)
#define rs (now << 1 | 1)
#define max(a, b) (a > b ? a : b)
const int MARX = 2e5 + 10;
//=============================================================
struct node
{
    int L, R, data;
    bool use;
}tree[MARX << 2];
struct Request
{
    int l, r;
}request[MARX];
int T, N, M, ans[MARX];
bool vis[MARX];
//=============================================================
inline int read()
{
    int s = 1, w = 0; char ch = getchar();
    for(; ! isdigit(ch); ch = getchar()) if(ch == '-') s = -1;
    for(; isdigit(ch); ch = getchar()) w = (w << 1) + (w << 3) + (ch ^ '0');
    return s * w;
}
bool cmp(Request fir, Request sec)
{
    if(fir.l == sec.l) return fir.r < sec.r;
    return fir.l < sec.l;
}
void Build(int now, int L, int R)
{
    tree[now].L = L, tree[now].R = R;
    if(L == R) {tree[now].use = 0; tree[now].data = L; return;}
    int mid = (L + R) >> 1;
    Build(ls, L, mid), Build(rs, mid + 1, R);
    tree[now].use = 0;
}
int query(int now)
{
    if(tree[now].L == tree[now].R)
    {
      tree[now].use = 1;
      return tree[now].data;
    }
    int ret = 0;
    if(! tree[ls].use) ret = query(ls);
    else ret = query(rs);
    tree[now].use = (tree[ls].use && tree[rs].use);
    return ret;
}
void change(int now, int pos)
{
    if(tree[now].L == tree[now].R) {tree[now].use = 0; return ;}
    int mid = (tree[now].L + tree[now].R) >> 1;
    if(pos <= mid) change(ls, pos);
    else change(rs, pos);
    tree[now].use = 0;
}
void Memset0()
{
    for(int i = 1; i <= N; i ++) ans[i] = 1;
    Build(1, 1, N);
}
//=============================================================
signed main()
{
    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);
    T = read();
    while(T --)
    {
      N = read(), M = read();
      Memset0();
      for(int i = 1; i <= M; i ++) request[i].l = read(), request[i].r = read();
      std :: sort(request + 1, request + M + 1, cmp);

      int nowl = 1, nowr = 1, pos;
      for(int i = 1; i <= M; i ++)
      {
        int L = request[i].l, R = request[i].r;
        for(; nowl < L; nowl ++) change(1, ans[nowl]);
        for(nowr = max(nowr, L); nowr <= R; nowr ++) ans[nowr] = query(1);
      }

      printf("%d", ans[1]);
      for(int i = 2; i <= N; i ++) printf(" %d", ans[i]);
      putchar('\n');
    }
}
/*
3
2 1
1 2

4 2
1 2
3 4

5 2
1 3
2 4
*/

T2:

考场代码：

//
/*
By:Luckyblock
两堆维护 已选的 和 未选的物品
*/
#include <cstdio>
#include <ctype.h>
#include <queue>
#define ll long long
const int MARX = 1e5 + 10;
//=============================================================
int T, N, M, W[MARX];
int ans, sum;
//=============================================================
inline int read()
{
    int s = 1, w = 0; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') s = -1;
    for(; isdigit(ch); ch = getchar()) w = (w << 1) + (w << 3) + (ch ^ '0');
    return s * w;
}
void Memset0()
{
    sum = 0;
}
//=============================================================
signed main()
{
    freopen("gohome.in", "r", stdin);
    freopen("gohome.out", "w", stdout);
    T = read();
    while(T --)
    {
      Memset0();
      std :: priority_queue <int> q1, q2;//q1已选 q2未选
      N = read(), M = read();
      for(int i = 1; i <= N; i ++) W[i] = read();

      for(int i = 1; i <= N; i ++)
      {
        while(M - sum < W[i]) q2.push(- 1 * q1.top()), sum -= q1.top(), q1.pop();
        if(! q2.empty() && (!q1.empty()))
          while(-1 * q2.top() < q1.top())
          {
            int top1 = q1.top(), top2 = -1 * q2.top();
            q1.pop(), q2.pop();
            sum -= (top1 - top2), q1.push(top2);
            q2.push(- 1 * top1);
          }
        if(! q2.empty())
          while(- 1 * q2.top() + sum + W[i] <= M)
          {
            q1.push(- 1 * q2.top()), sum += -1 * q2.top(); q2.pop();
            if(q2.empty()) break;
          }

        sum += W[i], q1.push(W[i]);
        printf("%d ", i - q1.size());
      }
      printf("\n");
    }
}
/*
1
10 39614758
32410480 7432940 21964807 27525176 37308134 29973772 25948616 26120579 14053831 8907239
*/

正解 :

#include<bits/stdc++.h>

#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 2e5 +11;
int T,n;
LL cnt[N];
LL m,a[N],b[N],q[N],c[N];
int add(int k,LL d,LL *t){
    for(;k<=n;k+=k&-k)t[k]+=d;
}
LL g(int k,LL *t){
    if(k<0)return 0;
    LL A=0;
    for(;k;k-=k&-k)A+=t[k];
    return A;
}
int main(){
    freopen("gohome.in", "r", stdin);
    freopen("gohome.out", "w", stdout);
    ios::sync_with_stdio(false);
    for(cin>>T;T;T--){
        memset(q,0,sizeof q);
        memset(cnt,0,sizeof cnt);
        cin>>n>>m;
        for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
        sort(b+1,b+1+n);
        int len =unique(b+1,b+1+n)-b-1;
        for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+1+len,a[i])-b;
        for(int i=1;i<=n;i++){
            int l=0,r=n,ok=0;
            LL MAX=g(n,q);
            while(l<=r){
                int mid=l+r>>1;
                if(b[a[i]]+g(mid,q)<=m){
                    ok=mid;
                    l=mid+1;
                }else r=mid-1;
            }
            ok++;
            if(ok>n){
                add(a[i],b[a[i]],q);
                add(a[i],1,cnt);
                cout<<0<<' ';
            }else{
                int now=g(ok,cnt)-g(ok-1,cnt);//ok
                int l=0,r=now,ans=0;
                LL need=g(ok-1,q);
                while(l<=r){
                    LL mid=l+r>>1;
                    if(mid*b[ok]+b[a[i]]+need<=m){
                        ans=mid;
                        l=mid+1;
                    }else r=mid-1;
                }
                cout<<g(n,cnt)-g(ok-1,cnt)-ans<<' ';
                add(a[i],b[a[i]],q);
                add(a[i],1,cnt);
            }
        }
        cout<<endl;
    }
    return 0;
}

T3:

考场代码：

//
/*
By:Luckyblock
K = 1
查询最小前缀和
*/
#include <cstdio>
#include <ctype.h>
#include <cstring>
#define min(a, b) (a < b ? a : b)
#define ll long long
const int MARX = 1e5 + 10;
const ll INF = 1e12;
//=============================================================
int T, N, K;
//=============================================================
inline int read()
{
    int s = 1, w = 0; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') s = -1;
    for(; isdigit(ch); ch = getchar()) w = (w << 1) + (w << 3) + (ch ^ '0');
    return s * w;
}
void Memset()
{

}
void solveK1()
{
    ll sum = 0, ans = INF;
    for(int i = 1; i <= N; i ++)
    {
      ll now = read();
      sum += now, ans = min(ans, sum);
    }
    printf("%I64d\n", ans);
}
//=============================================================
signed main()
{
    freopen("candy.in", "r", stdin);
    freopen("candy.out", "w", stdout);
    T = read();
    while(T --)
    {
      Memset();
      N = read(), K = read();
      if(K == 1) {solveK1(); continue;}
    }
}

正解 :

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn=2e5+5;
ll a[maxn],f[maxn];

int bit[maxn*2+100];
void update(int x,int d){
    for(int i=x;i>0;i-=i&-i) bit[i]=max(bit[i],d);
}
int querysuf(int x,int B){
    int ret=-1e9;
    for(int i=x;i<B;i+=i&-i) ret=max(bit[i],ret);
    return ret;
}
void remove(int x,int B){
    for(int i=x;i<B;i+=i&-i) bit[i]=-1e9;
    for(int i=x;i>0;i-=i&-i) bit[i]=-1e9;
}

vector<ll> disc;
int getid(ll x){return lower_bound(disc.begin(),disc.end(),x)-disc.begin()+1;}

bool check(ll ans,int n,int k){// sum<=ans
    disc.clear();
    for(int i=1;i<=n;i++) {
        disc.push_back(a[i]);
        disc.push_back(a[i]-ans);
    }
    disc.push_back(0);
    sort(disc.begin(),disc.end());
    disc.erase(unique(disc.begin(),disc.end()),disc.end());

    for(int i=1;i<=disc.size();i++) remove(i,disc.size());
    f[0]=0;
    update(getid(0),f[0]);
    for(int i=1;i<=n;i++) {
        f[i]=querysuf(getid(a[i]-ans),disc.size()+1)+1;
        update(getid(a[i]),f[i]);
        if(f[i]>=k) return true;
    }
    return false;
}

int main(){
   freopen("candy.in", "r", stdin);
   freopen("candy.out", "w", stdout);
    int T; scanf("%d",&T);
    while(T--){
        int n,k;
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++) {
            scanf("%I64d",a+i);
            a[i]+=a[i-1];
        }
        ll l=1LL*-1e9*1e6,r=1LL*1e9*1e6;
        while(l+1<r){//  ans -> ( ]
            ll mid=(l+r)/2;//
            if(check(mid,n,k)) r=mid;//
            else l=mid;
        }
        printf("%I64d\n",r);
    }
    return 0;
}