比赛时写到D题，比赛后补完了，记录一下第一次补完，以及第一次写题解

A

题意

给你一个序列A，和下标x, 问第x个元素是多少

思路

直接输出Ax，注意下标从1开始

代码

1
2
3
4
5
6
7
8
9
10
void solve()
{
    int n;
    cin>>n;
    vector<int> a(n+1);
    for(int i=1;i<=n;++i) cin>>a[i];
    int x;
    cin>>x;
    cout<<a[x]<<'\n';
}

B

题意

给你N个长度不一样的序列A，和下标x，y，问Ax，y是多少

思路

使用vector的动态数组，注意x和y下标都从1开始

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void solve()
{
    int n;
    cin>>n;
    vector<int> a[n+1];
    for(int i=1;i<=n;++i)
    {
        int L;
        cin>>L;
        for(int j=0;j<L;++j)
        {
            int xx;
            cin>>xx;
            a[i].push_back(xx);
       }
    }
    int x,y;
    cin>>x>>y;
    cout<<a[x][y-1]<<'\n';
}

C

题意

给你N个长度不一样的序列A，Ai的长度为Li，和一个一维数组C，然后将Ci个Ai放入B中，问Bk的值

思路

枚举找到k在哪一个Ai上，然后输出。注意下标k是从0开始的

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void solve()
{
    int n;
    ll k;
    cin>>n>>k;
    vector<vector<int>> a(n+1);
    vector<int> l(n+1);
    for(int i=1;i<=n;++i)
    {
        int L;
        cin>>L;
        l[i]=L;
        for(int j=0;j<L;++j)
        {
            int xx;
            cin>>xx;
            a[i].push_back(xx);
        }
    }
    vector<int> c(n+1);
    for(int i=1;i<=n;++i) cin>>c[i];
    int idx=1;
    for(;idx<=n;++idx)
    {
        if(k>(ll)l[idx]*c[idx])
        {
            k-=l[idx]*c[idx];
        }
        else break;
    }
    cout<<a[idx][(k-1)%l[idx]]<<"\n";
}

D

题意

给一个序列A，可以进行k次操作，每次可以给Ai加上i（下标从1开始），问最大的A中最小值是多少

思路

既然要最大的最小值，那肯定k次要都使用完，每次选择最小值加不就好了，于是我想到优先队列，正准备开始写，看了一下k的范围1e18？？！
好的，思路完全偏了，最大的最小值，噢！二分啊
二分答案，如果答案是mid的时候，cnt（操作的数量）<=k,说明这个答案是可以的，继续寻找更大的答案
r的初始值需要设置一个极大的值，我刚开始想着r不会超过A中最小值的ki，但是可能数值太大，longlong也会爆，导致wa了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
int n;
ll k;
bool check(const vector<ll>& a,ll x)
{
    ll cnt=0;
    for(int i=1;i<=n;++i)
    {
        ll now=a[i];
        if(now>=x) continue;
        ll diff=x-now;
        ll op=(diff+i-1)/i;
        cnt+=op;
        if(cnt>k) return false;
    }
    if(cnt>k) return false;
    return true;
}
void solve()
{
    cin>>n>>k;
    vector<ll> a(n+1);
    ll minn=1e18;
    ll maxx=0;
    //ll wz=0;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i];
        minn=min(a[i],minn);
        //if(a[i]==minn) wz=i;
    }
    ll l=minn,r=2e18;
    ll ans=l;
    while(l<=r)
    {
        ll mid=(r+l)>>1;
        if(check(a,mid))
        {
            l=mid+1;
            ans=mid;
        }
        else r=mid-1;
    }
    cout<<ans<<'\n';
}

E

题意

给你m块布，每条覆盖了Li到Ri。进行q次查询，是否可以从 M 块布中恰好选择两块布，使得Si到Ti至少有一条布覆盖，其他单元格没有被任何布覆盖

思路

只能覆盖Si到Ti，那么两条布一个左端点在Si，一个右端点在Ti。然后我们在左端点在Si的布里面寻找R<=Ti的，右端点在Ti的布里面寻找L>=Si的，因为Si到Ti里面都需要布覆盖，那我们在R中要寻找max，在L中寻找min，然后判断R>=L-1
如果找到的L=Si，R=Ti，有可能是一个布
此时我们需要在寻找一个布，分为4个情况
1.l = L，r = R
2.l = L，r< R
3.l > L, r = R
4.l > L, r < R
对于1，我们直接使用map来计数相同的布的个数
对于2，我们可以在左端点在Si的布中直接寻找最小的r，判断r < R
相同的，对于3，我们可以在右端点在Ti的布中直接寻找最大的l，判断l > L
对于4，我们可以使用一个数组Right,Right[i]表示以i开始的最小r的值，然后判断Right[L+1] < R

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
const int N=2e5+5,inf=0x3f3f3f3f;
vector<int> r[N],l[N];
int R[N];
map<pair<int,int>,int> mp;
void solve()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;++i)
    {
        int x,y;
        cin>>x>>y;
        mp[{x,y}]++;
        r[x].push_back(y);
        l[y].push_back(x);
    }
    
    for(int i=1;i<=n;++i)
    {
        if(!r[i].empty()) sort(r[i].begin(),r[i].end());
        if(!l[i].empty()) sort(l[i].begin(),l[i].end());
    }
    
    R[n+1]=inf;
    for(int i=n;i>=0;--i)
    {
        R[i]=R[i+1];
        if(!r[i].empty())
        {
            R[i]=min(R[i],r[i].front());
        }
    }
    
    int q;
    cin>>q;
    while(q--)
    {
        int x,y;
        cin>>x>>y;
        int f=0;
        int ll=inf,rr=0;
        
        auto xx=upper_bound(r[x].begin(),r[x].end(),y);
        if(xx!=r[x].begin()) rr=*(xx-1);
        auto yy=lower_bound(l[y].begin(),l[y].end(),x);
        if(yy!=l[y].end()) ll=*yy;
        
        if(ll!=inf&&rr!=0&&rr>=ll-1)
        {
            if(ll==x&&rr==y)
            {
                if(mp[{ll,rr}]>=2) f=1;
                else if(R[ll+1]<rr) f=1;
                else if(!r[ll].empty()&&r[ll].front()<rr) f=1;
                else if(!l[rr].empty()&&l[rr].back()>ll) f=1;
            }
            else f=1;
        }
        if(f) cout<<"Yes\n";
        else cout<<"No\n";
    }
}

F

题意

给定一个长度为 N−1 的序列 D，构造一个  P，使得对于每一个 1≤i≤N−1，在后缀 Pi…PN 中，最大值和次大值的下标差的绝对值等于 Di，求满足条件的P数量。

思路

我们可以从后往前推，相当于每次在前面加一个Pi
假设在后缀Pi+1...PN中,最大值下标为x，次大值下标为y，|x-y|=Di+1
现在我们加入Pi，有3种可能性
1.Pi变成最大值，那次大值下标就是x,那么|i-x|=Di
2.Pi变成次大值，那最大值不变还是x,那么|x-i|=Di
3.Pi不是最大值也不是次大值，此时因为x，y不变，推出Di=Di+1
Pi的取值可以在N-i-1中选择

由上面3种情况可以推出状态其实和次大值的位置没有关系，我们假设f[i][j]
表示在后缀Pi...PN中，最大值的下标为j的数量
状态转移
如果Di=Di+1
f[i][j]+=f[i+1][j]×(N−i−1) （对应3）
如果j-i=Di
f[i][i]+=f[i+1][j] （对应1）
f[i][j]+=f[i+1][j] (对应2)
但是现在的时间复杂度是O(N2) TLE
我们需要优化！！！
可以使用线段树优化
1.区间乘法：当 D[i] = D[i+1] 时，将区间 [i+1, n] 的值全部乘以 (n - i - 1)
2.单点修改：处理2，3的时候，更新f[i]
3.单点查询: 获取f[i]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
typedef long long ll;
const int N=2e5+5,mod=998244353;
#define ls (p<<1)
#define rs (p<<1 |1)
ll tree[N<<2],tag[N<<2];
int n;
int a[N];
void pushup(int p)
{
    tree[p]=(tree[ls]+tree[rs])%mod;
}
void pushmul(int p,ll x)
{
    tree[p]=tree[p]*x%mod;
    tag[p]=tag[p]*x%mod;
}
void pushdown(int p)
{
    if(tag[p]==1) return ;
    pushmul(ls,tag[p]);
    pushmul(rs,tag[p]);
    tag[p]=1;
}
void build(int p,int l,int r)
{
    tree[p]=0;
    tag[p]=1;
    if(l==r)
    {
        return ;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
}
ll check(int p,int k,int l,int r)
{
    if(l==r)
    {
        return tree[p];
    }
    pushdown(p);
    int mid=(l+r)>>1;
    if(k<=mid) return check(ls,k,l,mid);
    else return check(rs,k,mid+1,r);
}
void xgmul(int p,int l,int r,int L,int R,ll x)
{
    if(L<=l&&r<=R)
    {
        pushmul(p,x);
	    return ;
    }
    pushdown(p);
    int mid=(l+r)>>1;
    if(L<=mid) xgmul(ls,l,mid,L,R,x);
    if(R>mid) xgmul(rs,mid+1,r,L,R,x);
    pushup(p);
}
void xgadd(int p,int k,int l,int r,ll x)
{
    if(l==r)
    {
        tree[p]+=x;
        tree[p]%=mod;
        return ;
    }
    pushdown(p);
    int mid=(l+r)>>1;
    if(k<=mid) xgadd(ls,k,l,mid,x);
    else xgadd(rs,k,mid+1,r,x);
    pushup(p);
}
void solve()
{
   cin>>n;
   for(int i=1;i<n;++i)
   {
        cin>>a[i];
   }
   a[n]=0;
   if(a[n-1]!=1)
   {
        cout<<"0\n";
        return ;
   }
   build(1,1,n);
   xgadd(1,n,1,n,1);
   xgadd(1,n-1,1,n,1);
   for(int i=n-2;i>=1;--i)
   {

        int j=a[i]+i;
        ll v=0;
        if(j<=n) v=check(1,j,1,n);
        if(a[i]==a[i+1])
        {
            xgmul(1,1,n,1,n,n-i-1);
        }
        else xgmul(1,1,n,1,n,0);
        if(v)
        {
            xgadd(1,j,1,n,v);
            xgadd(1,i,1,n,v);
        }    
    }
    cout<<tree[1]%mod<<"\n";
}

G

题意

有 N个苹果，第 i个苹果会在时间 Ti掉落在 Xi 处，可以在任意位置放机器人，机器人从 0 时刻开始移动，速度不大于1，每个机器人同一时刻只能吃一个苹果，求最少需要多少个机器人，才能吃完全部苹果。

思路

假设一个机器人在Ti的时候吃了Xi位置上的苹果，现在要去Tj时间Xi位置上的苹果，由于速度<=1，
可以推出∣Xi​−Xj​∣<=Tj​−Ti​
拆开整理一下得出
1.Ti​+Xi​<=Tj​+Xj​
2.Ti​−Xi​<=Tj​−Xj​
然后我们令 A=T-X，B=T+X
得出 Ai<=Aj &&Bi<=Bj​ 的时候，机器人可以从i到j吃到苹果
题目问我们最少需要但是机器人才可以吃完苹果 那么就变成了求最长严格递减子序列的问题
我们需要先对A排序，然后对B进行求解

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
typedef long long ll;
const int N=3e5+5;
struct node{
    int x,y;
};
node a[N];
int f[N];
bool cmp(node a,node b)
{
    if(a.x!=b.x) return a.x<b.x;
    return a.y<b.y; 
}
void solve()
{
    int n;
    cin>>n;
    for(int i=0;i<n;++i)
    {
        int t,x;
        cin>>t>>x;
        a[i]={t-x,t+x};
    }
    sort(a,a+n,cmp);
    int cnt=0;
    f[cnt++]=a[0].y;
    for(int i=1;i<n;++i)
    {
        if(a[i].y<f[cnt-1])
        {
            f[cnt++]=a[i].y;
        }
        else {
            int l=0,r=cnt-1,pos=-1;
            while(l<=r)
            {
                int mid=(l+r)>>1;
                if(f[mid]<a[i].y)
                {
                    pos=mid;
                    r=mid-1;
                }
                else if(f[mid]==a[i].y)
                {
                    pos=-1;
                    break;
                }
                else l=mid+1;
            }
            if(pos!=-1) f[pos]=a[i].y;
        }
    }
    cout<<cnt<<"\n";
}