P10368题解

· · 题解

P10368 题解

P10368题目传送门

场上一开始看到这题，感觉挺好理解，就开打了。但是最后只有 60 分（）

先来讲部分分做法：

10 分

题外话：大家可能会看到我的提交记录里面有一个 5 分，但是那个是试出来的。

直接模拟。代码·非常简洁易懂，但是我可是调了好几次的......

#include<iostream>
#include<string>
#include<vector>
using namespace std;
string xiaochu(string&i,int k)
{
    string r=i;
    bool e=1;
    while(k--&&e)
    {
        e=0;
        vector<int>m;
        for(int j=1;j<r.length()-1;j++)
        {
            if(r[j-1]==r[j+1])
            {
                m.push_back(j);
                e=1;
            }
        }
        for(int j=m.size()-1;j>=0;j--)r.erase(m[j],1);
    }
    return r;
}
int main()
{
    int T,id;
    cin>>T>>id;
    while(T--)
    {
        int n,k;
        cin>>n>>k;
        string i;
        cin>>i;
        cout<<xiaochu(i,k)<<endl;
    }
}

↑我猜有些人会直接复制上面的代码

但是我们可以发现就只对了五个点。

然后开始思考有没有更好的做法。

经过我长达十七秒的思考，得出了结论：开 long long。

0\le k\le 10^{18}

这么大的数据，肯定要开 long long。

但是开 long long 之后——

60 分

发现还是会有一些点 TLE。准确来说是最后一个 Subtask。

代码和上面的就只差了一个数据类型：

#include<iostream>
#include<string>
#include<vector>
using namespace std;
string xiaochu(string&i,int k)
{
    string r=i;
    bool e=1;
    while(k--&&e)
    {
        e=0;
        vector<int>m;
        for(int j=1;j<r.length()-1;j++)
        {
            if(r[j-1]==r[j+1])
            {
                m.push_back(j);
                e=1;
            }
        }
        for(int j=m.size()-1;j>=0;j--)r.erase(m[j],1);
    }
    return r;
}
int main()
{
    int T,id;
    cin>>T>>id;
    while(T--)
    {
        long long n,k;
        cin>>n>>k;
        string i;
        cin>>i;
        cout<<xiaochu(i,k)<<endl;
    }
}

100 分

注意到上面的两份代码都用到了一个叫做 erase 的函数。这个函数运行起来非常费时间。所以说，我们要优化一下。感谢 @int_stl 大佬的帮助。

代码如下：

#include<iostream>
#include<string>
#include<vector>
using namespace std;
string xiaochu(string i,int k)
{
    bool e=1;
    while(k--&&e)
    {
        string s="";
        e=0;
        for(int j=0;j<=i.length()-1;j++)
        {
            if(j>0&&j<i.length()-1&&i[j-1]==i[j+1])e=1;
            else s+=i[j];
        }
        i=s;
    }
    return i;
}
int main()
{
    int T,id;
    cin>>T>>id;
    while(T--)
    {
        long long n,k;
        cin>>n>>k;
        string i;
        cin>>i;
        cout<<xiaochu(i,k)<<endl;
    }
}

至此，我们就完成了这道题。

第一次写题解写过 \sout{150} 行祭