模拟赛2-赛后总结

常规
,
1

第一题

根据题目，我得到了以下信息：

  1. 大厦有 n 层
  2. 有 k 个请求，分别是 (begin_1,end_1),(begin_2,end_2),\ldots,(begin_k,end_k)

看完样例，我判断这道题是用排序，把begin>end的情况放一个数组，升序排序；把end>begin的情况放一个数组，降序排序。
然后，就推出了核心代码：

sort(x.begin(),x.end());
x.erase(unique(x.begin(),x.end()),x.end());//去重，防止电梯上升的过程中重复经过相同的站点
if(x[0]!=1)cout<<"1-";//特判
for(int i:x)cout<<i<<"-";
sort(y.begin(),y.end());
y.erase(unique(y.begin(),y.end()),y.end());//同理
reserve(y.begin(),y.end());//由于y是降序，而sort默认升序，所以要翻转一下
if(y[0]!=x[x.size()-1])cout<<y[0]<<"-";//特判
for(int i=1;i<y.size()-1;i++)cout<<y[i]<<"-";
cout<<y[y.size()-1];//特殊处理y[y.size()-1]，防止多出一个-
if(y[y.size()-1]!=1)cout<<"-1";

不出所料， \textcolor{green}{AC}

第二题

根据题目，我得到了以下信息：

  1. 若 t\le s ，则 t-sum_t\le s
  2. 若 k-sum_k\ge s ，则 \forall a\in[k,n] ， a-sum_a\ge s

所以题目转换成求最小的 k ，使得 k-sum_k\ge s ，答案即为 n-k+1
但是我在求的过程中没有二分，导致失掉了70分，最终 \textcolor{blue}{TLE70tps}
赛后订正了一下，最终 \textcolor{green}{AC}
最后核心代码如下：

l=s,r=n+1;
while(l+1<r){
    mid=(l+r)/2;
    if(check(mid))r=mid;
    else l=mid;
}cout<<n-l;

其中 check(k) 函数即为判断是否 k-sum_k\ge s

第三题

开始时，我看了一下数据范围，发现 n\le 30 ，所以觉得这一题应该用搜索做。

浅浅的算了一下，如果有 n 种不同的物品，则选的方案应该是 \sum_{i=1}^nC^i_n=2^n

我发现当 n=30 时， 2^n\approx 10^{10} ，远远大于计算机一秒能运行的次数 10^8 。所以还要再加上剪枝。

浅浅的剪了一下枝，就交上去了，以为没有超时，实际上却 \textcolor{blue}{TLE70tps}

后来看了一下QQ群，发现还要再剪枝。最终AC，核心代码如下：

void dfs(int x){
    if(sum==19920726){
        ans=max(ans,k);//更新答案
        return;
    }for(int i=x;i<=n;i++){
        if(sum+a[i]-a[i-1]>19920726||sum+a[n]-a[x-1]<19920726)continue;//排除不合法的情况
        sum+=a[i]-a[i-1];
        k++;
        dfs(i+1);
        sum-=a[i]-a[i-1];
        k--;
    }
}

第四题

想了半天，没什么思路，就用暴力程序进行打表，最终 \textcolor{red}{WA10tps} ，结果程序在比赛结束后不久又出了一个点，刚刚好可以多拿10分。

后来看了题解，发现要用 dp+ 高精度，根据转移方程做了一下，AC，转移方程如下：

dp[0][i]=dp[2][i-1];
dp[1][i]=dp[0][i-1]+dp[2][i-1];
dp[2][i]=dp[3][i-1];
dp[3][i]=dp[1][i-1]+dp[3][i-1];
dp[0][2]=dp[1][2]=dp[2][2]=dp[3][2]=1;
2 个赞