比赛链接
t1第五分钟wa了 十来分钟才a 之后就慌了 感觉没发挥好 但其实也就这水平吧
好累 全站排名三百多 也就这水平了 继续学习吧 半小时搞不懂了直接看题解 能学会都一样,没那么多时间了…
得早睡早起阿....
T2感谢光头哥@Tilbur的指导 他的解法真的好妙 链接放在
这里 了
还得感谢peter佬@Peter_5大半夜还陪我做题讨论题目2333
最后感谢 点进蒟蒻这篇分享的你祝你rp++
T1

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
//模拟题 判断有无相邻的1 和 0边上有没有1
int n,m;
int main()
{
    scanf("%d", &m);
    while (m -- ){
        scanf ("%d",&n);
        string a;
        cin>>a;
        if (a=="0"){
            puts("No");
            continue;
        }
        else if (a=="1"){
            puts("Yes");
            continue;
        }
        int p=1;
        for (int i=0;i<n;i++){
            if (a[i]=='0'){
                int u=0;
                if (i==0) {
                    if (a[i+1]=='1') u++;
                }
                else if (i<n-1){
                    if (a[i-1]=='1'||a[i+1]=='1') u++;
                }
                else if (a[i-1]=='1') u++;
                if (u==0) {
                    p=0;break;
                }
            }
            if (a[i]=='1'){
                if (i<n-1&&a[i+1]=='1'){
                    p=0;
                    break;
                }
            }
        }
        if (p) puts("Yes");
        else puts("No");
    }
    return 0;
}

T2

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
// 就是分类讨论 
// 我们用前缀和数组得到 前缀和数组的最大值和最小值 
// 代表最多会上多少猴子mxa 和 最少会上多少猴子mni 
// 其中mxa mni可能会是负数
// 在任意时刻树上的猴子总数都没有超过 w，当然也不可能小于 0。
// 所以 分类讨论前先排除mxa>w 和mni<w*-1的情况
// 对于mxa和mni的大小分类讨论
// 情况1：mni<0 mxa>0
//     此情况可视为猴子有上有下
//     最多会下mni*-1个猴子 最多会上mxa个猴子
//     那么至少得有l=mni*-1个猴子 同时最多有r=w-mxa个猴子
//     若r>l则有答案 ans=r-l+1 否则不符合逻辑 无解
// 情况2：mni<0 mxa<0
//     此情况可视为一直下猴子
//     最多会下l=mni*-1个猴子 最少会下mxa*-1个猴子
//     因此 至少要有l个猴子
//     故 ans=w-l+1(l,l+1,...,w) //l>w的情况分类讨论前就被筛去
// 情况3：mni>0 mxa>0
//     此情况可以视为一直上猴子
//     最多会上mxa个猴子 最少会上mni个猴子
//     因此 最多能有w-mxa个猴子 
//     因此 ans=w-mxa+1(0,1,...,w-mxa) //mxa>w的情况分类讨论前就被筛去
// 情况4：mni>0 mxa<0 不符合逻辑
int n,w;
int a[100010];
int s[100010];
int main()
{
    scanf("%d%d", &n,&w);
    int mxa=-1e9-9,mni=1e9+9;
    for (int i = 1; i <= n; i ++ ){
        scanf ("%d",&a[i]);
        s[i]=s[i-1]+a[i];
        mxa=max(mxa,s[i]);
        mni=min(mni,s[i]);
    }
    if (mxa>w||mni<w*-1){
        puts("0");
        return 0;
    }
    int l,r;
    if (mni<0){
        if (mxa>=0){//情况1：mni<0 mxa>0
            l=mni*-1;
            r=w-mxa;
            if (l<=r) {
                printf ("%d",r-l+1);
            }
            else puts("0");
        }
        else {//情况2：mni<0 mxa<0
            l=mni*-1;
            printf ("%d",w-l+1);
        }
    }
    else {//情况3：mni>0 mxa>0
        l=0;
        r=w-mxa;
        printf ("%d",r-l+1);
    }
    return 0;
}

T3

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
// 一道贪心题 
// 问我们如果按题面这么取 最少几次使得所有石子高度都一样
// 要使次数最少那么肯定是要所有石子 都变为原先石子中最低的那个高度
// 按照题面的取法 我们必然是一个高度一个高度地取
// 按照题面的取法 取完一次 就不会有比设定的h更高的石子了 
// 当前最高的高度一定<=h
// 因此 我们猜测一个贪心的取法
//     从最高高度开始取 若当前高度石子取完了<k 
//     那么再取低一层高度的石子 
//     若手上的加上低一层的石子还<k 那么再取下一层
//     直到某层手上的石子>k了 取消该层的 见好就收 完成一次收取
//     同时将该层石子放入手中 开始新一轮
// 这种取法 我们只要求出每个高度石子的个数 就能得到答案
//ps:统计某层高度石子的个数 可以用差分 
//也可以直接记数统计到下一层了在该层加上上一层的石子数
int n,k;
int a[200010],s[200010],b[200010];
//a存石子初始高度 sb存高度为i的石子数量
int main()
{
    scanf ("%d%d",&n,&k);
    int mxa=-2,mni=1e9;
    for (int i=1;i<=n;i++){
        scanf ("%d",&a[i]);
        mxa=max(mxa,a[i]);
        mni=min(mni,a[i]);
        s[a[i]]++;
        b[1]+=1;
        b[a[i]+1]-=1;
    }
    for (int i=1;i<=mxa+2;i++) b[i]+=b[i-1];
//如此 b就利用差分存储了高度为i的石子数量
    int cnt=0,ans=0;//ans为次数 cnt为当前手上的石子数量
    for (int i=mxa;i>mni;i--){
        cnt+=s[i];//试探取下当前层 
        s[i-1]+=s[i];//一定要记得给下一层加上当前层的石子数!
//没有下一层石子垫着 就不会有当前层的高度!!!
        if (cnt>k){//如果试探失败 见好就收 完成一次收取 
            cnt=s[i];//同时开始新一轮收取 先收取当前层石子
            ans++;//完成一次收取 
        }
    }
    if (cnt) ans++;//完事了手上如果还有石子 那么还算一次
    printf ("%d",ans);
    return 0;
}