2019.9.15 NOIP模拟测试

港控/mmm° 2023-06-04 08:00 15阅读 0赞

**没有来考，现在补上。**

**T1:passward**

**![1596060-20190916193802124-1082397153.png][]**

**其实一看肯定就会想到kmp，但是我一开始思路是错的，只有六十分。（本来这题数据就很水）**

**后来调了一下，还是就过了。**

**题解：**

**首先我们就将密码串进行自我匹配然后求出fail数组的值。然后就从尾部跳fail指针，跳到每一个前缀上，然后用这个前缀来匹配，如果这个匹配串在模式串中出现了超过3次（前缀，后缀，中间），那么就证明是可行的。由于数据太水，这样还不会被卡到n方，如果出现像aaaaaaaaaaaaaaa这样的字符串，那我的这个算法就死了。基本上是接近o(n)的复杂度。然后最后我们直接就输出第一次找到的符合条件的子串，因为后面越来越短。**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e5+7;
    char s[maxn];
    int st,ed;
    int lenn,len;
    int fail[maxn];
    char newchar[maxn];
    int ans;
    int id;
    int l[maxn],r[maxn];
    void getfail(){
        fail[1]=fail[0]=0;
        int j=0;
        for(int i=2;i<=len;i++){
            while(j!=0&&s[i]!=s[j+1]) j=fail[j];
            if(s[i]==s[j+1]) j++;
            fail[i]=j;
        }
    }
    void kmp(){
        int j=0;
        ans=0;
        for(int i=1;i<=len;i++){
            while(j!=0&&s[i]!=newchar[j+1]) j=fail[j];
            if(s[i]==newchar[j+1]) j++;
            if(j==lenn) ans++;
        }
    }
    int main(){
        scanf("%s",s+1);
        len=strlen(s+1);
        getfail();
        st=1,ed=len;
        while(fail[ed]){
            lenn=0;
            memset(newchar,0,sizeof(newchar)); 
            for(int i=1;i<=fail[ed];i++){
                newchar[++lenn]=s[i];
            }
            kmp();
            if(ans>=3) l[++id]=1,r[id]=fail[ed];
            ed=fail[ed];
        }
        if(!id) printf("Just a legend\n"); 
        for(int i=l[1];i<=r[1];i++) printf("%c",s[i]);
        return 0;
    }

**T2 So**

**![1596060-20190916194515730-1870704923.png][]**

**40分的dp还是好写，设dp\[i\]\[j\]表示到第i个数时选了j个数。**

**但是数据范围显然不允许我们这样做。**

**这道题有一个难点就是维护这个数相邻的两个数的位置，用最简单的链表即可。**

**参考题解的做法，我们在贪心的时候就用一个集合来维护。因为集合已经帮你排好序了。**

**但考虑反悔的情况，比如我们先选了A，但是如果之后B+C更优的话怎么办呢，那么就在集合中删除B,C,插入一个B+C-A，如果发现此解更优的话就会把它给选了。**

**最后还要注意合并。**

**推荐：**

**双倍经验：**

[**P1484 种树**][P1484]

[**P1792 ****\[国家集训队\]种树**][P1792]

**代码如下：**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e6+7;
    #define inf (long long)(1<<62);
    struct node{
        long long val;
        int pp;
        node(){
        
        }
        node(long long va,int p){
            val=va;
            pp=p;
        }
        friend bool operator <(const node &a,const node &b){
            return (a.val==b.val)?(a.pp>b.pp):(a.val>b.val);
        }
    };
    set<node>s;
    int pre[maxn],nxt[maxn],n,k;
    long long a[maxn];
    long long ans;
    int main(){
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
            pre[i]=i-1;
            nxt[i]=i+1;
            s.insert(node(a[i],i));
        } 
        a[0]=-1e15;
        nxt[n]=0;
        while(k--){
            int now=s.begin()->pp;
            ans+=a[now];
            a[now]=-a[now];
            a[now]+=a[pre[now]];
            a[now]+=a[nxt[now]];
            s.erase(s.begin());
            s.erase(node(a[pre[now]],pre[now]));
            s.erase(node(a[nxt[now]],nxt[now]));
            s.insert(node(a[now],now));
            if(pre[pre[now]]) nxt[pre[pre[now]]]=now;
            if(nxt[nxt[now]]) pre[nxt[nxt[now]]]=now;
            pre[now]=pre[pre[now]];
            nxt[now]=nxt[nxt[now]];
        }
        printf("%lld\n",ans);
        return 0;
    }

**T3 留坑代填**

转载于:https://www.cnblogs.com/LJB666/p/11529423.html

[1596060-20190916193802124-1082397153.png]: /images/20230601/6fd55d6d6d8b4bc9824272d87dfa1498.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/466a3bdfb93a4588aa25d9adcdbfcf56.png
[1596060-20190916194515730-1870704923.png]: /images/20230601/ef3037a757d6490c8780423591f8af5c.png
[P1484]: https://www.luogu.org/problem/P1484
[P1792]: https://www.luogu.org/problem/P1792