CF补题题解2023.5

spdarkle · 2023-05-26 21:25:12 · 个人记录

CF补题题解2023.5

说明：CF题直接去luogu看翻译，AT题会附上简要题意

1749D

对于操作类问题，经常从极端情况入手。注意到 \gcd(a,1)=1，那么每个数列都会有一种方案，就是在开头不断移除

那么只要某一时刻，除位置1之外有一个位置合法，就说明挂掉了

接着就容易得到长为 n 且有且仅有一种方案的序列的充要条件是：

\forall i\in[2,n],j\in[2,i],\gcd(a_i,j)\neq 1

换言之即为 a_i 含有 [2,i] 范围中的所有质因子才能满足条件，设 g_i=lcd(1,2,3,4……,i),f_i 为长为 i 的序列中有且仅有一种移除方案的序列个数

则显然有 f_i=f_{i-1}\times \lfloor\frac{m}{g_i}\rfloor

正难则反，容斥一下就可以得到最终结果

ll n,m,f[N],g[N],v[N];
int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=2;i<=n;i++)if(!v[i])for(int j=i+i;j<=n;j+=i)v[j]=true;
    f[1]=m%p,g[1]=1;
    ll tmp=m%p,ans=0;
    for(int i=2;i<=n;i++){
        g[i]=v[i]?g[i-1]:g[i-1]*i;
        if(g[i]>m)g[i]=m+1;
        f[i]=f[i-1]*((m/g[i])%p)%p;
        tmp=tmp*(m%p)%p;
        ans+=tmp-f[i];
        ans%=p;
    }
    ans=(ans%p+p)%p;
    printf("%lld\n",ans);
}

1837D

这个题告诉我们，有时候，暴力的复杂度，其实是很低的，只是你想不到而已

考虑一个贪心的想法：每次选最长的合法序列染色，这个可以在 O(n) 算出

然后每一次都这样暴力染色，到最后直接输出答案即可

What???这么简单吗??

考虑证明时间复杂度：

只要合法，每一次选走最长的，就会导致同一类型的括号被选完……，一共两种类型，则肯定最多跑两组……

事实上，括号序列问题的套路是：将左括号视作1，右括号视作-1，求前缀和

#include<bits/stdc++.h>
using namespace std;
int n,k,t,f[505050],g[505050],c[505050],h[505050],w[505050];
char a[1000050];
void calc(){
    g[n+1]=f[n+1]=f[0]=g[0]=h[0]=w[0]=h[n+1]=w[n+1]=0;
    for(int i=1;i<=n;i++)f[i]=f[i-1]+(a[i]=='('&&c[i]==0);
    for(int i=n;i;--i)g[i]=g[i+1]+(a[i]==')'&&c[i]==0);
    for(int i=1;i<=n;i++)h[i]=h[i-1]+(a[i]==')'&&c[i]==0);
    for(int i=n;i;--i)w[i]=w[i+1]+(a[i]=='('&&c[i]==0);
} 
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=0;i<=n+1;i++)c[i]=0;
        cin>>a+1;
        int cnt=0,num=0,tag=0;
        while(1){
            calc();
            if(f[n]!=g[1]){
                cout<<"-1\n";
                tag=1;
                break;
            }
            if(f[n]==0)break;
            int mx=0,nx=0,cnt=0;++num;
            for(int i=1;i<=n;i++){//正：mx 
                if(c[i])continue;
                if(a[i]=='('&&cnt+1<=g[i])++cnt;
                if(a[i]==')'&&cnt)--cnt,nx+=2;
            }
            cnt=0;
            for(int i=1;i<=n;i++){//正：mx 
                if(c[i])continue;
                if(a[i]==')'&&cnt+1<=w[i])++cnt;
                if(a[i]=='('&&cnt)--cnt,mx+=2;
            }
            if(mx>nx){
                for(int i=1;i<=n;i++){//正：mx 
                    if(c[i])continue;
                    if(a[i]==')'&&cnt+1<=w[i])c[i]=num,++cnt;
                    if(a[i]=='('&&cnt)c[i]=num,--cnt;
                }
            }
            else {
                for(int i=1;i<=n;i++){//正：mx 
                    if(c[i])continue;
                    if(a[i]=='('&&cnt+1<=g[i])c[i]=num,++cnt;
                    if(a[i]==')'&&cnt)--cnt,c[i]=num;
                }
            }
    //  for(int i=1;i<=n;i++)cout<<c[i]<<" ";
    //  cout<<"\n"; 
        }
        if(tag)continue;
        cout<<num<<"\n";
        for(int i=1;i<=n;i++)cout<<c[i]<<" ";
        cout<<"\n"; 
    }
}

1775E

真的很好的一道题！

一个重要的思路是：序列全0=差分数组全0=前缀和数组全0

重要应用是：单点操作通过计算前缀和时候就会变成整体的区间操作，而区间操作在差分后又会变成朴素的单点操作

如果我们把原序列转化为前缀和的话，我们进行的单项操作就变成区间操作

那么选出两个数，等价于是给一段区间+1/-1

选出三个数呢？设为 a,b,c，设为加一的情况，则[1,a]+1,[1,b]-1,[1,c]+1=[1,a]+1,[1,a]-1,[a+1,b]-1,[1,a]+1,[a+1,b]+1,[b+1,c]+1=[1,a]+1,[b+1,c]+1

那么多个数的情况，如出一辙

我们选出一个子序列事实上就变为了抽出若干段，将这些段整体+/- 1

那么就有最小操作数为前缀和数组的最大最小值绝对值之和(如果只有正负数就是其中之一)

signed main(){
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<=n;i++)a[i]+=a[i-1];
        int mx=0,mn=1e18;
        for(int i=1;i<=n;i++){
            if(a[i]>0)mx=max(a[i],mx);
            if(a[i]<0)mn=min(a[i],mn);
        }
        if(mn==1e18)mn=0;
        cout<<mx-mn<<"\n";
    } 
}

1788D

首先考虑计算

显然，两个点相撞之后在相互作用力下不会再移动。

一维的直线运动问题，显然在速度相同的情况下讨论运动方向。

引理：运动方向始终不变

证明：

设向左为 0,向右为 1

我们讨论当前点为 1 的情况，为 0 的情况根据对称性显然成立

考虑分类讨论与其最近的点的运动状况

运动状况是 0，双向奔赴，显然在速度相同的情况下是一定会撞上然后不动的
运动状况是 1，那么其前面的第一个运动状况为 0 的点(显然存在，也即最后一个点及其之前 )会使得所有为 1 的点全部撞上停止运动

综上，两种情况均满足，引理得证

我们考虑计算方案

显然，如果我们将运动方向抽象为一个 01 序列 a ，那么我们实质上 f(S)=\sum_{i=1}^{|S|-1}[a_i=1][a_{i+1}=0]

那么我们考虑统计贡献。

统计贡献的方法是看每一个单一贡献的组成部分，将组成部分单独抽离进行计算求和

那么这题贡献显然是一个数对。

接着我们计算数对 (i,j) 的贡献，显然此时 i+1\sim j-1 应该已经删完。

设 pos1(pos1<i),pos2(pos2>j) 分别为满足： x_i-x_{pos1}>x_j-x_i,x_{pos2}-x_j>x_j-x_i 的最大/最小值。

那么则 [1,pos1],[pos2,n] 的数可选可不选，其他数必选，那么贡献为： 2^{pos1+n-pos2+1}

显然 pos1,pos2 可以使用二分查找求出，然后计算贡献即可。

O(n^2\log n)

#include<iostream>
#include<algorithm>
using namespace std;
const int p=1e9+7;
#define N 3050
int a[N],n,ans,pw[N];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    pw[0]=1;
    for(int i=1;i<=n;i++)pw[i]=pw[i-1]*2ll%p;
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
            int pos1=lower_bound(a+1,a+n+1,a[i]+a[i]-a[j])-a-1;
            int pos2=lower_bound(a+1,a+n+1,-a[i]+a[j]+a[j])-a;
            ans=(ans+pw[pos1+(n-pos2+1)])%p;
        }
    }
    cout<<ans<<"\n";
}

1778D

纪念一下我正式独立做出的期望题，这里体现了 优化DP状态设计的思想

由于概率均等，我们只关心有多少位不匹配

设 g_i 表示还有 i 位没匹配好的期望次数，设有 x 位不匹配

发现这玩意很难搞，但 g_0=0，我们可以用作差法优化DP状态，也即设 f_i=g_{i}-g_{i-1}，求出 f 后就可以递推出 g

那么 f_i 的意义即为在有 i 个不匹配的情况下，找到翻好一个位置的期望，这就变得简单了

显然一次有 \frac{i}{n} 的概率翻对，有 \frac{n-i}{n} 的概率挂掉，这时候问题变为求 f_{i+1} 变回原来状态，然后再使用 f_i 次翻好一个位置

则有 f_i=\frac{i}{n}+\frac{n-i}{n}(1+f_{i+1}+f_i)\implies f_i=\frac{n+(n-i)f_{i+1}}{i}

显然有 f_n=1

最后答案即为 \sum_{i=1}^xf_i

void solve(){
    for(int i=1;i<=n;i++)f[i]=0;
    cin>>n;
    f[n]=1;
    for(int i=n-1;i;--i){
        f[i]=power(i,p-2)*(n+(n-i)*f[i+1]%p)%p;
    }
    cin>>a+1;cin>>b+1;
    cnt=0;
    for(int i=1;i<=n;i++)cnt+=(a[i]!=b[i]);
    int ans=0;
    for(int i=cnt;i;i--)ans=(ans+f[i])%p;
    cout<<ans<<"\n";
}

*2100的期望题……

632D

挺有意思的一道题

注意到 m\le 10^6，转化角度，考虑枚举最小公倍数 x ，显然如果 a_i\ge m 直接舍掉，值域变成 10^6

利用公倍数的性质：

设 x=lcm(a_1,a_2……a_n),p=kx，那么 p 有 x 的所有因数

那么我们可以使用倍数法，求出每一个值 i,(i\in [1,m])，其包含了 a_i 中的因数的个数

然后从小到大扫最大值，注意严格大于才能更新(这是因为可能后面的答案就不是lcm而是一个普通公倍数了)

找到值之后，枚举 a_i 判断能否整除即可

#define N 1005050
vector<int>p[N];
int cnt[N],n,m,ans[N],s,a[N];
inline void solve(){
    for(int i=1;i<=m;i++){
        for(int j=i;j<=m;j+=i)ans[j]+=cnt[i],p[j].push_back(i);
    }
    for(int i=1;i<=m;i++)s=max(s,ans[i]);
    for(int i=1;i<=m;i++){
        if(s==ans[i]){
            cout<<i<<" "<<s<<"\n";
            for(int j=1;j<=n;j++){
                if(i%a[j]==0)cout<<j<<" ";
            }
            break;
        }
    }
    return ;
}
int main(){
    read(n);read(m);
    for(int i=1;i<=n;i++){
        int x;read(x);if(x<=m)cnt[x]++;
        a[i]=x;
    }
    solve();
    return 0;
}

trick:

转化角度，从序列选数到数选序列，*2100的题

600E

首先，这题问的就是树上众数

树上莫队法

显然我们可以将树用DFS序拍成序列，记录下每个点对应的子树区间，问题就变成了裸的序列众数问题

常见的序列众数，我们会使用莫队。

普通的莫队如果要维护区间众数，显然需要线段树等结构的嵌套，这使复杂度多了一个 \log ，显然是不优的

那么还有两种方法可以保证 O(n\sqrt n) 的复杂度

第一种是回滚莫队法：其原因是众数在只加不删时是容易维护的

简单来说，我们将问题分为两类，第一类是区间长度 \le \sqrt n 的问题，我们直接暴力统计

那么剩下的所有区间长度都 \ge \sqrt n

考虑将所有问题按左端点所在块排序，块内右端点递增排序

我们将问题整块整块的处理

初始化：记录当前指针 l=R+1,r=R，其中 R 是当前块的终点（这里注意不存在一个询问的右端点小于 R)

扫描询问，以如下形式操作：

移动右端点，不断加入新的数(注意需要两个变量：众数次数和众数编号和，维护是简单的，这里略去)

记录下当前统计的答案，然后左移左端点，只增不删

将答案记录，然后还原答案变量，并且将左端点移回 R 只改动 cnt 数组

但200ms 的时间，加上巨大的常数，是难以卡过的

第二种做法：普通莫队+值域分块

注意到移动的复杂度必须要求 O(1) 但查询的复杂度只需要在 O(\sqrt n) 范围内即可

那么记录三个量： cnt[i] 表示颜色 i 的出现次数，cn[i] 记录出现次数为 i 的颜色编号和，sum[i] 记录出现次数在第 i 块内的颜色编号和

正常增删维护
void add(int x){
  x=dfn[x];//序列x位置的颜色
  sum[pos[cnt[x]]]--;
  cn[cnt[x]]-=x;
  ++cnt[x];
  sum[pos[cnt[x]]]++;
  cn[cnt[x]]+=x;
}
void del(int x){
  x=dfn[x];
  sum[pos[cnt[x]]]--;
  cn[cnt[x]]-=x;
  --cnt[x];
  sum[pos[cnt[x]]]++;
  cn[cnt[x]]+=x;
}
然后将查询分为 \sqrt n 范围内的大查询，然后在块内查询
int get(){
  for(int i=pos[n];i>=0;--i){
      if(sum[i]){
          int r=min(i*bl,num);
          for(int j=r;pos[j]==i;--j){
              if(cn[j])return cn[j];
          }
      }
  }
  return 0;
}

当然，这道题也让我们想起了雨天的尾巴，简单地说，就是对于每个节点开一个线段树(动态开点)，在线段树合并中求众数

还有一个更加优秀的做法：

考虑朴素的树上做法

开一个计数数组 cnt，在树上深度优先遍历时，暴力地在子树扫描统计，然后清空，显然复杂度 O(n^2)

考虑进行优化：

显然每棵子树DFS完之后有一个儿子是不需要清空的，那么我们将这个儿子设为点最多的，不清空这玩意。

复杂度 O(n\log n)

link

1832E

差量分析思想

b_i=\sum_{j=1}^i{i-j+1\choose k}a_j=\sum_{j=1}^i({i-j\choose k}+{i-j\choose k-1})a_j=\sum_{j=1}^i{i-j\choose j}a_j+\sum_{j=1}^i{i-j\choose k-1}a_j

=b_{i-1}+\sum_{j=1}^{i-1}{i-j\choose k-1}a_j+a_i

考虑设 f_{i,j}=\sum_{k=1}^i{i-k+1\choose j}，则 b_i=f_{i,k},f_{i,j}=f_{i-1,j}+f_{i,j-1}+a_i

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define int long long
#define p 998244353
#define N 10505050
int a[N],b[N][6],inv[N],jc[N],c[N];
int t,n,k,x,y,m;
void init(){
    jc[1] = inv[1] = jc[0]=inv[0]=1;
    for (int i = 2; i <= n; i++) {
        jc[i] = jc[i - 1] * i % p;
        inv[i] = p - (p / i * inv[p % i] % p) % p;
    }
    for(int i=2;i<=n;i++)inv[i]=inv[i-1]*inv[i]%p;
}
int C(int n,int m){
    if(n<m)return 0;
    return jc[n]*inv[m]%p*inv[n-m]%p;
}
signed main(){
    cin>>n>>a[1]>>x>>y>>m>>k;
    init();
    for(int i=2;i<=n;i++){
        a[i]=(a[i-1]*x%m+y)%m;
    }
    for(int j=0;j<=k;j++){
        for(int i=1;i<=n;i++){
            if(j==0)b[i][j]=b[i-1][j]+a[i];
            else {
                b[i][j]=(b[i-1][j]+b[i-1][j-1])%p+C(1,j)*a[i]%p;
            }
            b[i][j]%=p;
        }   
    }
    int ans=0;
    for(int i=1;i<=n;i++)ans^=(b[i][k]*i);
    cout<<ans<<"\n";
}

~~就这TM2200~~

1826D

有意思的带限制DP题

遇到这种思维题，我们一般考虑比较在一定相同条件下的决策的优劣，从而得到优化方案

在这个题中体现为：如果两个区间的前三大值相同，则区间长度小的更优

进一步得到推论：一个区间，其两端一定属于前三大值

那么我们得到一个朴素做法：枚举区间，预处理其最大值

这里又有一个优化手段：对于最优化的选择区间问题，我们可以将枚举区间转化为枚举区间中的某个数，再计算其向左向右扩展的代价，也可以理解为两端区间的拼凑，这是“3”化“2”的重要套路

设 f_i=\max_{k<i}\lbrace val_i+val_k-(i-k)\rbrace=val_i-i+\max(val_k+k),g_i=val_i+i+\max_{k>i}(val_k-k)

递推进行计算，答案即为 \max_{1\le i\le n} \lbrace f_{i-1}+g_{i+1}+val_{i}-1\rbrace

为什么，如何保证 val_i 是最大值呢？

事实上，f,g 里的决策也是呈段状的，那么我们枚举 i 的过程实际上也是在给可能的区间枚举最大值

1594E2

有意思的树上计数题，推荐先去看 E1

首先考虑设 g_i 表示高度为 i 的完全二叉树，根节点颜色确定，没有任何限制情况下的答案。

显然有 g[1]=1,g[n]=16g_{n-1}^2

然后考虑怎么处理这个带限制的问题

遇到此类很小部分点带限制，其余部分一样的问题，一般考虑将特殊部分单独拿出计算，与一般部分进行答案的合并

显然，树高是很低的，而 n\le 2000，也即子树中有带限制的点的点的个数是 O(nk) 的，考虑把每一个特殊点到根节点的链单独拿出，然后将其合并成一颗树进行计算

由于原树是完全二叉树，则我们抽离的这颗虚树中每个节点也不会有超过2个儿子。注意由于点的编号很大，可以用 map 映射新的点号

考虑进行DP计算，设 f[i,j] 表示在以 i 为根，j 根节点颜色为 j 时的方案数，那么我们根据儿子个数分类讨论，计算 f[u,j]，用 vis[i,j] 表示节点 i 能否取颜色 j，用 vaild(i,j) 表示颜色 i,j 能否相邻

没儿子

此时这个节点的子树是一般的，则 f[u,j]=g[k-dep[u]+1][vis[u,j]]
有一个儿子 v

此时另一个一般的儿子是4种颜色随便取，方案数是 4g[k-dep[u]]
f[u,j]=vis[u,j]\sum_{vaild(j,a)}4f[v,a]g[k-dep[u]]
有两个儿子 v_1,v_2

类比有一个儿子的情况，有：
f[u,j]=vis[u,j]\sum_{vaild(j,a)}\sum_{valid(j,b)}f[v_1,a]f[v_2,b]

#include<bits/stdc++.h>
using namespace std;
#define N 505050
#define int long long
const int p=1e9+7;
int head[N],ver[N],nxt[N],tot,num,n,m,k,f[N][6],g[65],c[N],lim[N],dep[N];
map<int,int>H;
/*
H:虚树编号的映射 
co:映射时颜色限制
f:dp数组，f[i,j]表示点i子树中i染为j的方案数(注意先处理根节点)，注意若有限制除限制外其他几个变成0 
g:辅助数组，g[i]表示没有限制下高为i的子树方案数 
lim:初始深度
*/
void init(){//预处理g数组 
    g[1]=1;memset(c,-1,sizeof c);
    for(int i=2;i<=k;i++)g[i]=g[i-1]*g[i-1]%p*16ll%p;
} 
void add(int u,int v){
    nxt[++tot]=head[u],ver[head[u]=tot]=v;
}
int get(char a){//返回颜色 
    if(a=='r')return 0;
    if(a=='o')return 1;
    if(a=='w')return 2;
    if(a=='y')return 3;
    if(a=='g')return 4;
    if(a=='b')return 5;
} 
bool check(int a,int b){//返回两色是否矛盾 
    if(a==-1||b==-1)return true;
    if(a/2==b/2)return false;
    else return true;
}
void build(int x,char a){//处理出根到i的链，并初始化属性 
    if(H[x]==0)H[x]=++num;
    else {
        c[H[x]]=get(a);return ;
    }
    c[H[x]]=get(a);
    while(x>1){
        int p=x;
        x/=2;
        if(H[x]==0){
            H[x]=++num;add(H[x],H[p]);add(H[p],H[x]);
        }
        else{
            add(H[x],H[p]);add(H[p],H[x]);break;
        }
    }
} 
void dfs(int u,int fa){
    dep[u]=dep[fa]+1;
    int cnt=0,s1,s2;
    for(int i=head[u];i;i=nxt[i]){
        int v=ver[i];
        if(v==fa)continue;
        dfs(v,u);
        ++cnt;
        if(cnt==1)s1=v;
        if(cnt==2)s2=v;
    }
    if(cnt==0){
        if(c[u]!=-1)f[u][c[u]]=g[k-dep[u]];
        else for(int i=0;i<6;i++)f[u][i]=g[k-dep[u]];
    }
    else if(cnt==1){
        for(int i=0;i<6;i++){
            for(int j=0;j<6;j++){
                if(check(i,j)){
                    f[u][i]=(f[u][i]+4ll*f[s1][j]*g[k-dep[s1]]%p)%p;    
                }
            }
        }
    }
    else {
        for(int i=0;i<6;i++){
            for(int j=0;j<6;j++){
                for(int a=0;a<6;a++){
                    if(check(i,j)&&check(i,a))f[u][i]=(f[u][i]+f[s1][j]*f[s2][a]%p)%p;
                }
            }
        }
    }
    if(c[u]!=-1){
        for(int i=0;i<6;i++)if(i!=c[u])f[u][i]=0;
    }
} 
signed main(){
    char ch[15];
    cin>>k>>n;k++;
    init();H[1]=++num;
    for(int i=1;i<=n;i++){
        int x;cin>>x>>ch+1;
        build(x,ch[1]);
    }
    dfs(1,0);
    int ans=0;for(int i=0;i<6;i++)ans+=f[1][i];
    cout<<(ans%p+p)%p<<"\n"; 
}

1594F

简要题意：

给定 s,n,k ，构造一个长度为 n 的序列，序列最小值大于 0，序列和为 s，使得不存在任意连续子序列和为 k

如果存在符合条件的序列，输出 "YES"'，否则 "NO"

对于静态的有关连续子序列的和的问题，我们一般考虑使用前缀和进行操作

那么原问题等价于：有 n+1 个数满足 0=s_0<s_1<s_2<…<s_n=s，从中两两做差不为 k

首先我们只需要考虑长度 \le k 的子序列

那么容易想到我们可以将一个子序列隔开，两边将其“堵上“，使其不能外扩

详细地说就是，考虑这样一种构造方案：

放 k-1 个1，然后放一个 k+1，这显然满足条件

在最后的时候，如果剩余的值大于了剩余的位置，那么向值为 k+1 的格子上填即可，如果小于则无解

    cin>>t;
    while(t--){
        cin>>s>>n>>k;
        if(s==k)cout<<"Yes\n";
        else if(s<n)cout<<"No\n";
        else {
            if(k*(s/(k<<1))+min(k,s%(k<<1)+1/*后半截全填1，找起始位置*/)<=n)cout<<"Yes\n";
            else cout<<"No\n";
        }
    }

abc303F

简要题意：有一个怪物血量为 h，以及 n 张卡片，每张卡片有属性 t,d，进行回合制游戏

如果在回合 i 选择使用卡片 j，那么卡片 j 会在回合 i\sim i+t_j-1 持续造成 d_j 的伤害，求杀死怪物的最小回合数 (h\le 0)

注意卡片可以重复使用，答案显然具有可二分性

考虑二分答案，转为判定

问题化为在 tim 的时间求出最大的贡献

显然的一种做法是枚举每一个时刻，再枚举每一个卡片，求最大值，这显然需要优化

我们发现，在任意时刻 i，所有卡片可以分为两种：

t_j+i\le tim
t_j+i>tim

不妨设二者分属于集合 S,T，则 i 时刻的最大贡献为：

\max\lbrace \max_{x\in S}t_xd_x,(tim-i+1)\max_{x\in T}d_x \rbrace

所求即为：

\sum_{i=1}^{tim}\max\lbrace \max_{x\in S}t_xd_x,(tim-i+1)\max_{x\in T}d_x \rbrace

这个式子显然可以分段计算，然后两个集合取较大值

注意到集合的归属与 t 有关，不妨先按 t 递增排序，然后考虑优化掉这个式子

下面我们把时间倒着看，也即以下的时刻 i 表示之前的时刻 tim-i+1

容易发现，在时间段 [0,t_1-1],[t_1,t_2-1],[t_2,t_3-1]……[t_{n-1},t_n-1],[t_n,\inf]，S,T 的集合是不同的，换言之答案就可能会发生变化

不妨设时间段 l_i 表示 [t_{i-1},t_i-1]，(l_{n=1}=[t_n,\inf])，则在时刻 i\in l_j，S=[1,j-1],T=[j,n]

其中不同时间段的 S,T 最值显然可以预处理出来

这里注意一个点，如果存在两个卡片 i,j 满足 t_i=t_j,d_i\ge d_j，则 j 无用，直接删去

    read(n);read(h);P=(h<<1)+10;
    for(int i=1;i<=n;i++)read(a[i].t),read(a[i].d);
    sort(a+1,a+n+1);
    b[++m]=a[1];
    for(int i=2;i<=n;i++){
        if(b[m].t!=a[i].t)b[++m]=a[i];
    }
    for(int i=1;i<=m;i++)a[i]=b[i];n=m;
    for(int i=1;i<=n;i++)mxl[i]=max(mxl[i-1],a[i].t*a[i].d);//S
    for(int i=n;i;--i)mxr[i]=max(mxr[i+1],a[i].d);//T

那么我们考虑分时间段计算，下面设计算时间段 i 的贡献

S$ 所提供的答案设为 $x_1$，$T$ 的答案设为 $x_2

由于 x_2 的特殊性，我们考虑计算其答案

设在时刻 [a_1,a_2] 放了 x_2，则其答案在到终末时刻的时候构成了一个等差数列：(a_1x_2,(a_1+1)x_2……,a_2x_2)，求和即为 x_2\frac{(a_2-a_1+1)(a_1+a_2)}{2}

而 x_1 就是 (a_2-a_1+1)x_1

我们需要知道到底选哪一个是更优的

显然随着时刻的减小，x_1的贡献在不断减小，而 x_2 的贡献在变大，究竟分界点在哪里呢？

考虑比较时刻 k 时两者的贡献，则可以列出不等式 x_1\le x_2k\implies k\ge \frac{x_1}{x_2}

显然我们可以将时间段 i 分为 [t_{i-1},k-1],[k,t_i-1]，前一段用 x_1，后一段用 x_2

需要注意两个点 i=1，此时只能用 x_2

i=n+1$,只能用 $x_1

int check(int tim){
    int res=0;
    for(int i=1;i<=n+1;i++){
        int l=a[i-1].t,r=a[i].t-1;
        if(r>tim||i==n+1)r=tim;
        if(l<=r){
            if(i==1){
                res+=s(l,r)*mxr[i];
            }
            else if(i==n+1){
                res+=(r-l+1)*mxl[i-1];
            }
            else {
                int cut=mxl[i-1]/mxr[i];//这里是下取整，变成[l,cut],[cut+1,r]
                if(l<=cut){
                    res+=mxl[i-1]*(min(cut,r)-l+1);
                }
                if(cut<r){
                    res+=s(max(cut+1,l),r)*mxr[i];//等差数列求和
                }
            }
        }
        if(res>=h)return 1;
    }
    return res>=h;
}

注意精度，推荐使用__int128

trick:

在此类与结束时间有关的问题中，将时间倒过来看是一个不错的方法
重要的分段计数思想
分类讨论不同类的决策，并考虑高效划分集合范围
预处理一个集合在不同阶段的答案，注意到随着阶段增长，直增不删正推，只删不增倒推
比较决策思想