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(n\log n)$，二分复杂度$O(\log n)$,整体复杂度$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)$

#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

设$dg_{x,y}$为变换$x$次后字符串的第$y$项，可以递归解决

$\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}$

第一个式子不解释

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

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

第四个式子就是第$x$次变换多出来的字符串（除了第一项），和前面的一样，对齐即可

时间复杂度可以做到$O(\log n)$，我很懒，我的做法是$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);
}

在最后

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