首页 > 其他分享 >2022NOIPA层联测4

2022NOIPA层联测4

时间：2022-10-06 17:55:54浏览次数：50  
标签：ch 2022NOIPA string int ll while 联测 getchar

正手一个[南猪入侵]，反手一个[万箭齐发]，我的[桃]真的快用完了……OI啊(MP)，我(ZP)劝你出手前考虑一下，如果我DEAD了，你可就没牌了……话说难道我没有跳过忠吗？？

 

问题 A: 【2022NOIP联测4 10月6日】字符串还原

string用熟了，于是就忘了它的时间复杂度，TLE 40 不过用起来是真的简单，10分钟不到就搞定了。

#include <bits/stdc++.h>

using namespace std;

int n, mid, flag;
string ans, u;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

int main()
{
    n = read(); mid = n/2;
    cin >> u;
    for(int i=1; i<n-1; i++)
    {
        string t = u.substr(0, i) + u.substr(i+1);
        string s1 = t.substr(0, mid), s2 = t.substr(mid);
        if(s1 == s2)
        {
            if(!flag) {ans = s1; flag++;}
            else flag++;
        }
    }
    string t = u.substr(1);
    string s1 = t.substr(0, mid), s2 = t.substr(mid);
    if(s1 == s2)
    {
        if(!flag) {ans = s1; flag++;}
        else flag++;
    }
    t.clear(); s1.clear(); s2.clear();
    t = u.substr(0, n-1);
    s1 = t.substr(0, mid); s2 = t.substr(mid);
    if(s1 == s2)
    {
        if(!flag) {ans = s1; flag++;}
        else flag++;
    }
    if(flag > 1) printf("NOT UNIQUE\n");
    else if(!flag) printf("NOT POSSIBLE\n");
    else cout << ans << endl;

    return 0;
}
View Code

于是开始改hash，套用原来的string，TLE 95是因为每次答案的hash值我居然又拿出个string计算了一下。

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ll;
const int maxn = 2e6 + 30;

int n, mid, flag;
//ll mod = 1234567891;
ll f[maxn], m[maxn], B = 131, lstans, nowans;
string ans, u;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

int main()
{
    n = read(); mid = n/2;
    cin >> u;
    m[0] = 1;
    for(int i=1; i<=n; i++) m[i] = m[i-1] * B;
    n = u.length();
    f[0] = u[0] - 'A' + 1;
    for(int i=1; i<n; i++)
    {
        f[i] = f[i-1] * B + (u[i]-'A'+1);
    }
    for(int i=1; i<=mid; i++)
    {
        ll h1 = f[i-1]*m[mid-i]+f[mid]-f[i]*m[mid-i];
        ll h2 = f[n-1]-f[mid]*m[n-mid-1];
        if(h1 == h2)
        {
            if(!flag)
            {
                string t = u.substr(0, i) + u.substr(i+1);
                string s1 = t.substr(0, mid), s2 = t.substr(mid);
                ans = s1; flag++;
                for(int i=0; i<ans.length(); i++)
                {
                    lstans = lstans * B + (ans[i]-'A'+1);
                }
            }
            else 
            {
                string t = u.substr(0, i) + u.substr(i+1);
                string s1 = t.substr(0, mid), s2 = t.substr(mid);
                nowans = 0;
                for(int i=0; i<s1.length(); i++)
                {
                    nowans = nowans * B + (s1[i]-'A'+1);
                }
                if(nowans == lstans) continue;
                else 
                {
                    printf("NOT UNIQUE\n"); exit(0);
                }
            }
        }
    }
    for(int i=mid+1; i<n-1; i++)
    {
        ll h1 = f[mid-1];
        ll h2 = f[n-1]-f[i]*m[n-i-1]+(f[i-1]-f[mid-1]*m[i-mid])*m[n-i-1];
        if(h1 == h2)
        {
            if(!flag)
            {
                string t = u.substr(0, i) + u.substr(i+1);
                string s1 = t.substr(0, mid), s2 = t.substr(mid);
                ans = s1; flag++;
                for(int i=0; i<ans.length(); i++)
                {
                    lstans = lstans * B + (ans[i]-'A'+1);
                }
            }
            else 
            {
                string t = u.substr(0, i) + u.substr(i+1);
                string s1 = t.substr(0, mid), s2 = t.substr(mid);
                nowans = 0;
                for(int i=0; i<s1.length(); i++)
                {
                    nowans = nowans * B + (s1[i]-'A'+1);
                }
                if(nowans == lstans) continue;
                else 
                {
                    printf("NOT UNIQUE\n"); exit(0);
                }
            }
        }
    }
    ll h1 = f[mid]-f[0]*m[mid], h2 = f[n-1]-f[mid]*m[mid];
    if(h1 == h2)
    {
        if(!flag) 
        {
            string t = u.substr(1);
            string s1 = t.substr(0, mid), s2 = t.substr(mid);
            ans = s1; flag++;
            for(int i=0; i<ans.length(); i++)
            {
                lstans = lstans * B + (ans[i]-'A'+1);
            }
        }
        else
        {
            string t = u.substr(1);
            string s1 = t.substr(0, mid), s2 = t.substr(mid);
            nowans = 0;
            for(int i=0; i<s1.length(); i++)
            {
                nowans = nowans * B + (s1[i]-'A'+1);
            }
            if(nowans != lstans)
            {
                printf("NOT UNIQUE\n"); exit(0);
            }
        }
    }
    h1 = f[mid-1]; h2 = f[n-2]-f[mid-1]*m[mid];
    if(h1 == h2)
    {
        if(!flag) 
        {
            string t = u.substr(0, n-1);
            string s1 = t.substr(0, mid), s2 = t.substr(mid);
            ans = s1; flag++;
            for(int i=0; i<ans.length(); i++)
            {
                lstans = lstans * B + (ans[i]-'A'+1);
            }
        }
        else 
        {
            string t = u.substr(0, n-1);
            string s1 = t.substr(0, mid), s2 = t.substr(mid);
            nowans = 0;
            for(int i=0; i<s1.length(); i++)
            {
                nowans = nowans * B + (s1[i]-'A'+1);
            }
            if(nowans != lstans)
            {
                printf("NOT UNIQUE\n"); exit(0);
            }
        }
    }
    if(!flag) printf("NOT POSSIBLE\n");
    else cout << ans << endl;

    return 0;
}
View Code

由分类讨论发现得到答案并不需要两个中转string，可以直接拿，并且发现答案的hash已经记录过，然后A个T1居然花了一下午！？

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ll;
const int maxn = 2e6 + 30;

int n, mid, flag;
//ll mod = 1234567891;
ll f[maxn], m[maxn], B = 131, lstans, nowans;
string ans, u;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

int main()
{
    n = read(); mid = n/2;
    cin >> u;
    m[0] = 1;
    for(int i=1; i<=n; i++) m[i] = m[i-1] * B;
    n = u.length();
    f[0] = u[0] - 'A' + 1;
    for(int i=1; i<n; i++)
    {
        f[i] = f[i-1] * B + (u[i]-'A'+1);
    }
    for(int i=1; i<=mid; i++)
    {
        ll h1 = f[i-1]*m[mid-i]+f[mid]-f[i]*m[mid-i];
        ll h2 = f[n-1]-f[mid]*m[n-mid-1];
        if(h1 == h2)
        {
            if(!flag)
            {
                string s1 = u.substr(mid+1);
                ans = s1; flag++;
                lstans = h1;
            }
            else 
            {
                nowans = h1;
                if(nowans == lstans) continue;
                else 
                {
                    printf("NOT UNIQUE\n"); exit(0);
                }
            }
        }
    }
    for(int i=mid+1; i<n-1; i++)
    {
        ll h1 = f[mid-1];
        ll h2 = f[n-1]-f[i]*m[n-i-1]+(f[i-1]-f[mid-1]*m[i-mid])*m[n-i-1];
        if(h1 == h2)
        {
            if(!flag)
            {
                string s1 = u.substr(0, mid);
                ans = s1; flag++;
                lstans = h1;
            }
            else 
            {
                nowans = h1;
                if(nowans == lstans) continue;
                else 
                {
                    printf("NOT UNIQUE\n"); exit(0);
                }
            }
        }
    }
    ll h1 = f[mid]-f[0]*m[mid], h2 = f[n-1]-f[mid]*m[mid];
    if(h1 == h2)
    {
        if(!flag) 
        {
            string s1 = u.substr(mid+1);
            ans = s1; flag++;
            lstans = h1;
        }
        else
        {
            nowans = h1;
            if(nowans != lstans)
            {
                printf("NOT UNIQUE\n"); exit(0);
            }
        }
    }
    h1 = f[mid-1]; h2 = f[n-2]-f[mid-1]*m[mid];
    if(h1 == h2)
    {
        if(!flag) 
        {
            string s1 = u.substr(0, mid);
            ans = s1; flag++;
            lstans = h1;
        }
        else 
        {
            nowans = h1;
            if(nowans != lstans)
            {
                printf("NOT UNIQUE\n"); exit(0);
            }
        }
    }
    if(!flag) printf("NOT POSSIBLE\n");
    else cout << ans << endl;

    return 0;
}
View Code

注意事项就是判断重复是作为答案的字符串不能重复，而不是断点必须取同一个，感谢cr的提醒。我本来以为自动溢出会被卡的，毕竟大佬们都在用双模数，然而居然没卡我qwq

 

标签：ch,2022NOIPA,string,int,ll,while,联测,getchar
From： https://www.cnblogs.com/Catherine2006/p/16758108.html

相关文章

  • 多校联测4
    三个字符串可还行T1.字符串还原我一开始读错题了，以为是要不断拆分，回头一看发现只用拆依次，这不就枚举断点，然后用\(hash\)判断不就行了吗。不过这样你会得到80分，原因是不同......
  • 长城汽车选择北汇信息作为C-V2X智能网联测试系统及服务供应商
    随着C-V2X关键技术及其标准演进，C-V2X在全球竞争中已形成超越态势。长城汽车作为一家全球化智能科技公司，不断加大对C-V2X等前沿技术的投入和研究。长城汽车选择北汇信息作为......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99