泉一集训DAY1

南夫拉斯
视频讲解：

T1
比较奇怪的题。但看其他人做的貌似挺简单？
首先，赛时我没A掉这题。当时往循环结的方向去想，然后就只能得到一个最坏情况下复杂度为 O(tp) 的做法，和暴力一样过不了（暴力是稳定 O(t \times 5000000)的）。所以直接打了暴力咯。然后就拿到了 50 分。正解是二分，考虑到没被算到过的数有单调性，所以可以二分求 k。这样就能在 O(n \log p) 的复杂度内完成求解。注意特判 p \le q 的情况。然后附上代码：

#include
#define int long long
using namespace std;
int n,p,q,t,k,l,r,m;
bool v[5000005];
signed main()
{
    freopen("rounding.in","r",stdin);
    freopen("rounding.out","w",stdout);
    cin>>t;
    for(int ii=1;ii<=t;ii++)
    {
        scanf("%lld%lld%lld",&p,&q,&k);
        if(p==q)
        {
            if(k==1)
            {
                cout<<"0"<<endl;
            }
            else
            {
                cout<<"-1"<<endl;
            }
        }
        else
        if(p<q)
        {
            cout<<"-1"=p*k)
                {
                    r=m;
                }                   
                else
                {
                    l=m;
                }       
            }
            cout<=0)?r-1:0)<<endl;
        }
    }
}

T2 赛时暴力和找规律总共 40 分。首先是暴力处理 n\le10 的情况。由于 n 很小，所以可以直接dfs带走。然后打表找规律处理全为 x 或全为 y 的情况。打表可得存在规律： a[i]=a[i-1]+a[i-2]+ (i%3 = 0 )?0:1。然后 40 分就到手了。（本来按数据应该是 49 分的，但数据貌似出问题了）。贴上 40pts 代码

#include<bits/stdc++.h>
#define o 998244353
using namespace std;
long long int ans;
int n,an[1000005];
map<string,int>p;
string a;
int dfs(string s,int len)
{
    for(int i=1;i<len;i++)
    {
        if(s[i]==s[i-1])
        {                       
            string b=s;
            if(s[i-1]==&#039;x&#039;)
            {
                b[i-1]=&#039;y&#039;;
            }
            else
            {
                b[i-1]=&#039;x&#039;;
            }
            for(int j=i;j<len;j++)
            {
                b[j]=b[j+1];
            }
            if(p[b]!=1)
            {
                ans++;
                p[b]=1;
//              cout<<"  2  "<<b<<endl;
                dfs(b,len-1);
            }                       
        }
    }
    return 0;
}
int main()
{
    freopen("abbreviate.in","r",stdin);
    freopen("abbreviate.out","w",stdout);
    cin>>a;
    n=a.size();
    if(n>20)
    {
        an[1]=1;
        for(int i=2;i<=n;i++)
        {
            an[i]=an[i-1]+an[i-2];
            an[i]++;
            if(i%3==0)
            {
                an[i]--;
            }
            an[i]%=o;
        }
        cout<<an[n]<<endl;
        return 0;
    }
    dfs(a,n);
    cout<<ans+1<<endl;
    ans=0;
}

然后是AC解法。但由于我也不是很理解，思路不好讲。但我可以附上代码。（在混乱状态下通过对拍搞定了。这题在洛谷评为 黑题 。链接：link）。代码如下

#include<bits/stdc++.h>
#define o 1000000007
using namespace std;
string a;
int n,v,f[100005],last[5],vp;
int main()
{
//    freopen("abbreviate.in","r",stdin);
//    freopen("abbreviate.out","w",stdout);
    cin>>a;
    n=a.size();
    for(int i=0;i<n-1;i++)
    {
        if(a[i]==a[i+1])
        {
            vp=1;
        }
    }
    if(!vp)
    {
        cout<<"1"<<endl;
        return 0;
    }
    for(int i=0;i<n;i++)
    {
//      cout<<a[i]<<endl;
        v=(v+int(a[i]-&#039;a&#039;)+1)%3;
//      cout<<v<<endl;
        if(v>0)
        {
            f[i]++;
        }
//      cout<<f[i]<<" "<<last[0]<<" "<<last[1]<<" "<<last[2]<<" "<<last[v]<<endl;
        f[i]=(f[i]+f[last[0]-1]+f[last[1]-1]+f[last[2]-1]-f[last[v]-1])%o;
//      cout<<v<<endl;
        last[v]=i+1;
    }
    cout<<f[n-1]<<endl;
}

好了今天的博客到此为止了，你可以点击右上角离开了。或者点击这里以返回首页
搞事 夹带私货