2022年8月12日模拟赛总结

今天抽出一点时间写总结,最近真的超级忙.....下午要补昨天咕咕的补题

大概是我暑假唯一的博客吧....

最近实力漂浮不定,感觉自己应该再成熟一点,不要受太多外界因素干扰

个人成绩

分数: 300/300

排名:1(算上时间的排名:2)

比赛评价

简单。

别急,确实简单,我没有任何夸自己的意思,不要 mod 我,想一想,跟昨天比,这场比赛是不是相对简单?

我个人更倾向于这几次都没考好,教练给的一个信心赛/摸底赛

比赛过程

T1感觉在哪里见过,一眼二分,但是没有好好看题,以为可以自己安排顺序。

往背包上想,感觉会寄,所以打了一个假贪心

所以我的判断函数是这样的....

bool pd(long long x)
{
    memset(b,0,sizeof(b));
    int k=1;
    for(int i=1;i<=n;i++) {
        if(b[k]+a[i]>t)
        {
            k++;
        }
        if(k==x+1)return 0;
        b[k]+=a[i];
    }
    return 1;
}

那还不如不二分呢,感觉自己是个弱智

这个时候czn大佬表示做完了,Orz[1]

然后做T2,一眼前缀和,切了

然后做T3,显然是递归,但我死活不过样例

然后换了一种表达,A了自己造的所有数据

造化弄人啊...

T1发现是规定顺序,那就好办了,优先队列即可

然后调试了半天,发现没有清空,加上就没问题了

然后向教练确认AK....

开始写总结

题目解析

T1

二分舞台数,然后利用优先队列模拟奶牛上下台

每次提取一个舞台上的奶牛的下台时间的最小值,再把下一个奶牛的下台时间加入优先队列

判断函数复杂度O(nlogn)O(n\log n),二分复杂度O(logn)O(\log n),整体复杂度O(nlog2n)O(n\log^2 n)

#include <bits/stdc++.h>
using namespace std;
unsigned long long n,t,a[10000005],l,r,ans;
priority_queue<unsigned long long,vector<unsigned long long>,greater<unsigned long long> >wt;//迪茵大舞台,有牛你就来
bool pd(unsigned long long x)
{
    while(!wt.empty())wt.pop();
    unsigned long long tm=0;
    for(unsigned long long i=1;i<=x;i++)
    {
        wt.push(a[i]);
        tm=max(tm,a[i]);
    }
    for(unsigned long long i=x+1;i<=n;i++)
    {
        unsigned long long mn=wt.top();
        wt.pop();
        wt.push(a[i]+mn);
        tm=max(tm,a[i]+mn);
        if(tm>t)return 0;
    }
    if(tm>t)
    {
        return 0;
    }
    return 1;
}
int main()
{
    cin>>n>>t;
    for(unsigned long long i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    l=1;r=n;
    while(l<=r)
    {
        unsigned long long mid=(l+r)>>1;
        if(pd(mid))
        {
            r=mid-1;
            ans=mid;
        }
        else
        {
            l=mid+1;    
        }
    }
    cout<<ans;
}

T2

枚举变换的点,变换前手势,变换后手势三样东西,注意可以不变换

然后求出两个区间的胜场数,这个用前缀和统计即可

注意其实不需要搞清楚谁能打败谁,不如这样想:

我枚举的是一个可以打败xx手势的手势,这样用前缀和统计xx手势的数量就行

O(n)O(n)

#include<bits/stdc++.h>
using namespace std;
char c;
long long n,p[1000005],h[1000005],s[1000005],ans;
int main()
{
    cin>>n;
    for(long long i=1;i<=n;i++)
    {
        cin>>c;
        p[i]=p[i-1];
        h[i]=h[i-1];
        s[i]=s[i-1];
        if(c=='P')
        {
            p[i]++;
        }
        if(c=='H')
        {
            h[i]++;
        }
        if(c=='S')
        {
            s[i]++;
        }//统计手势
    }
    for(long long i=1;i<=n;i++)//枚举变换点(在i的右边),不变换可以理解为在n的右边
    {
        long long px=max(p[i]+s[n]-s[i],p[i]+h[n]-h[i]);//使用可以打败p的手势,和变换后的两种情况
        long long hx=max(h[i]+p[n]-p[i],h[i]+s[n]-s[i]);//使用可以打败h的手势,和变换后的两种情况
        long long sx=max(s[i]+p[n]-p[i],s[i]+h[n]-h[i]);//使用可以打败s的手势,和变换后的两种情况
        ans=max(ans,max(px,max(hx,sx)));//统计最大值
    }
    cout<<ans<<endl;
}

T3

dgx,ydg_{x,y}为变换xx次后字符串的第yy项,可以递归解决

{dg0,y=sydgx,y=dgx1,y(x>0,y2x1n)dgx,y=dgx1,2x1n(x>0,y=2x1n+1)dgx,y=dgx1y2x1n1(x>0,y>2x1n+1)\begin{cases} dg_{0,y}=s_y\\ dg_{x,y}=dg_{x-1,y}(x>0,y\leq 2^{x-1}n)\\ dg_{x,y}=dg_{x-1,2^{x-1}n}(x>0,y= 2^{x-1}n+1)\\ dg_{x,y}=dg_{x-1,y-2^{x-1}n-1}(x>0,y> 2^{x-1}n+1) \end{cases}

第一个式子不解释

第二个式子相当于两者都有的公共前缀部分,所以一样

第三个式子是第xx次变换多出来的字符串的第一项,一位循环移位,所以相当于原来的最后一位

第四个式子就是第xx次变换多出来的字符串(除了第一项),和前面的一样,对齐即可

时间复杂度可以做到O(logn)O(\log n),我很懒,我的做法是O(log2n)O(\log^2 n)

#include <bits/stdc++.h>
using namespace std;
string s;
long long n, k, t = 1, cnt = 0, pw[65];
char dg(long long k, long long x) {
    if (k == 0)
        return s[x - 1];
    long long len = pw[k] * n;
    if (x <= len / 2)
        return dg(k - 1, x);
    if (x == len / 2 + 1)
        return dg(k - 1, len / 2);
    return dg(k - 1, x - len / 2 - 1);
}
int main() {
    pw[0] = 1;
    for (int i = 1; i <= 64; i++) pw[i] = pw[i - 1] * 2;
    cin >> s >> k;
    n = s.size();
    while (t * n <= k) t *= 2, cnt++;
    cout << dg(cnt, k);
}

在最后

其实我的代码很累赘,大家理解思路,不要照着打


  1. 结果第一是YWJ?CZN后来又交了一次 ↩︎


---------- 本文到此结束 感谢您的阅读 ----------

赞赏