全粥逸种喊加急寻Day4

Posted on By 李丰泰 全粥逸种喊加急寻Day4无评论

test｛A表示我太八百八十八了（实际上用前缀和+队列就可以了）60(无法理解为什么这点分)｝
Description
LazyChild有一个长度为N的整数序列（a1,a2,…,an），他希望你从中找出一段连续的长度不小于A，且不超过B的子序列，使得这个子序列的和最大。

#include
using namespace std;
long long n,a,b,q[500005],f,t,s[500005],x,ans;
void lin(long long y){
    while(q[t]>=y){
        q[t]=-114514290;
        --t;
    }
    q[++t]=y;
}
int main(){
    freopen("max.in","r",stdin);
    freopen("max.out","w",stdout);
    cin>>n>>a>>b;
    q[0]=-114514290;
    for(int i=1;i>x;
        s[i+1]=s[i]+x;
        if(i>=a){
            lin(s[i-a]);
        }
        if(t-f>b-a)++f,q[f]=-114514290;
        if(t!=f){
            ans=max(ans,s[i+1]-q[f+1]);
        }
    }
    cout<<ans;
    return 0;
}

test｛B打一百多行（只是不知道错哪）悲（20）｝
搜一波看哪里不一样，然后暴力枚举（n<10,位数<=100）
Description
小y最近对枯燥的数字研究产生了浓厚的兴趣。他发现很多整数其实“长”的都差不多，都是由0~9十个数字构成。于是，他自己给出了一个“小y定义”：如果两个整数由相同的数字构成，那么这两个整数就叫做“数字朋友”。所以123和323313133323213就是数字朋友，但是123和22121221就不是。

如果两个正整数不是数字朋友，但是如果其中一个进行一次相邻交换后它们成为数字朋友，那么它们就叫做“几乎是朋友”。一次相邻交换改变两个相邻数字a和b，使之成为a-1和b+1或者a+1和b-1，新的数组仍然要在0到9之间，且形成的整数没有前导0。所以123和2223042就是几乎是朋友（让04变成13），但是137和470既不是朋友也不是几乎是朋友（因为13变成04是不被允许的）。

你的任务就是确定给你的两个正整数是朋友或者几乎是朋友或者什么都不是。

#include<bits/stdc++.h>
using namespace std;
int n,st,s[2][101];
int p[2][10];
string a[2];
int main(){
    freopen("friends.in","r",stdin);
    freopen("friends.out","w",stdout);
    cin>>n;
    while(n--){
        st=0;
        memset(p,0,sizeof(p));
        cin>>a[0]>>a[1];
        for(int i=0;i<a[0].size();++i){
            s[0][i]=a[0][i]-'0';
            ++p[0][s[0][i]];
        }
        for(int i=0;i<a[1].size();++i){
            s[1][i]=a[1][i]-'0';
            ++p[1][s[1][i]];
        }
        for(int i=0;i<=9;++i){
            if(p[0][i]&&!p[1][i]||p[1][i]&&!p[0][i]){
                ++st;
            }
        }
        if(!st){
            cout<<"friends"<<'\n';continue;
        }
        if(st>4){
            cout<<"nothing"<<'\n';continue;
        }
        bool che=0;
        for(int i=1;i<a[0].size();++i){
            int sti=st;
            if(s[0][i]!=9&&s[0][i-1]!=0&&!(i1&&s[0][i-1]1)){
                ++p[0][1+s[0][i]];++p[0][s[0][i-1]-1];
                --p[0][s[0][i]];--p[0][s[0][i-1]];
                if(p[0][1+s[0][i]]1&&p[1][1+s[0][i]])st--;
                if(p[0][s[0][i]]0&&!p[1][s[0][i]])st--;
                if(p[0][s[0][i-1]]0&&!p[1][s[0][i-1]])st--;
                if(p[0][s[0][i-1]-1]1&&!p[1][s[0][i-1]-1])st--;
                if(!st){
                    cout<<"almost friends"<<'\n';
                    che=1;
                    break;
                }
                --p[0][1+s[0][i]];--p[0][s[0][i-1]-1];
                ++p[0][s[0][i]];++p[0][s[0][i-1]];
                st=sti;
            }
            if(che)continue;
            if(s[0][i]!=0&&s[0][i-1]!=9){
                ++p[0][s[0][i]-1];++p[0][1+s[0][i-1]];
                --p[0][s[0][i]];--p[0][s[0][i-1]];
                if(p[0][s[0][i]-1]1&&p[1][s[0][i]-1])st--;
                if(p[0][s[0][i]]0&&!p[1][s[0][i]])st--;
                if(p[0][s[0][i-1]]0&&!p[1][s[0][i-1]])st--;
                if(p[0][1+s[0][i-1]]1&&!p[1][1+s[0][i-1]])st--;
                if(!st){
                    cout<<"almost friends"<<'\n';
                    che=1;
                    break;
                }
                --p[0][s[0][i]-1];--p[0][1+s[0][i-1]];
                ++p[0][s[0][i]];++p[0][s[0][i-1]];
                st=sti;
            }
        }
        if(che)continue;
        for(int i=1;i<a[1].size();++i){
            int sti=st;
            if(s[1][i]!=9&&s[1][i-1]!=0&&!(i1&&s[1][i-1]1)){
                ++p[1][1+s[1][i]];++p[1][s[1][i-1]-1];
                --p[1][s[1][i]];--p[1][s[1][i-1]];
                if(p[1][1+s[1][i]]1&&p[0][1+s[1][i]])st--;
                if(p[1][s[1][i]]0&&!p[0][s[1][i]])st--;
                if(p[1][s[1][i-1]]0&&!p[0][s[1][i-1]])st--;
                if(p[1][s[1][i-1]-1]1&&!p[0][s[1][i-1]-1])st--;
                if(!st){
                    cout<<"almost friends"<<'\n';
                    che=1;
                    break;
                }
                --p[1][1+s[1][i]];--p[1][s[1][i-1]-1];
                ++p[1][s[1][i]];++p[1][s[1][i-1]];
                st=sti;
            }
            if(che)continue;
            if(s[1][i]!=0&&s[1][i-1]!=9){
                ++p[1][s[1][i]-1];++p[1][1+s[1][i-1]];
                --p[1][s[1][i]];--p[1][s[1][i-1]];
                if(p[1][s[1][i]-1]1&&p[0][s[1][i]-1])st--;
                if(p[1][s[1][i]]0&&!p[0][s[1][i]])st--;
                if(p[1][s[1][i-1]]0&&!p[0][s[1][i-1]])st--;
                if(p[1][1+s[1][i-1]]1&&!p[0][1+s[1][i-1]])st--;
                if(!st){
                    cout<<"almost friends"<<'\n';
                    che=1;
                    break;
                }
                --p[1][s[1][i]-1];--p[1][1+s[1][i-1]];
                ++p[1][s[1][i]];++p[1][s[1][i-1]];
                st=sti;
            }
        }
        if(che)continue;
        cout<<"nothing"<<'\n';
    }
    return 0;
}

test｛C（三个Dijkstra，但是多个怎么搞？）｝
Description
话说yk拿到数学保送资格之后，大家一致要求yk请客
省中附近一共有n个可以请客吃饭的地点，cs在1号点，lqp在2号点，jzj在3号点，yk可以选择在任意一个地点请大家吃饭，因为cs、lqp、jzj都是很聪明的同学，他们只会沿着最短路走到目的地，但是如果有多条最短路到达目的地，他们会随机选择一条。yk为了避免被那3个同学联合起来宰一顿，不希望他们到目的地的最短路有重合的边。现在的问题是，yk有多少种选择，可以保证cs、lqp、jzj中任意两个人到达目的地的路径都不可能有重合的边？
test｛D（第一次判定：数字包围的0；第二次判定：第一第二个零连通块的位置；………………不会了————悲）｝
数字是包含在一个m*n的01矩阵中的,类似于LED数码发光管，但是可以任意压缩和拉伸,不过要始终保证整体结构是矩形的
test｛E（随便打，但题目随便来）｝
相邻的鹰羽毛不能有相同颜色，求最少颜料

#include
using namespace std;
int n,a1,a2,ans;
int main(){
    freopen("feather.in","r",stdin);
    freopen("feather.out","w",stdout);
    cin>>n;
    for(int i=1;i>a1;
        ans=max(ans,a1+a2);
        a2=a1;
    }
    cout<<ans;
    return 0;
}

二言

我能说什么？好好搓题目吧

训练日志

发表回复