202104-2邻域均值

这道题使用的优化方式主要是前缀和数组。因为用二维前缀和感觉有点麻烦就只用了一维前缀和，因为r<=10，复杂度尚可以接受。
虽然每次需要计算的是一个区域，但该区域是由一个像素为中心的，所以需要扫描每一个像素得到该像素的邻域均值判断是否处于较暗区域。
邻域均值计算需要首先得到邻域像素灰度值之和然后求平均，可以将每一行的像素灰度值求前缀和，降低复杂度。
一个像素的邻域取决于r，需要注意的是有时邻域会被边界限制，注意不要越界。

#include<bits/stdc++.h>
using namespace std;

int mp[610][610];

int main()
{
    int n,l,r,t;
    scanf("%d%d%d%d",&n,&l,&r,&t);

    for(int i=1;i<=n;i++)
    {
        int sum=0;
        for(int j=1;j<=n;j++)
        {
            int x=0;
            scanf("%d",&x);
            sum+=x;
            mp[i][j]=sum;//求每一行的前缀和
        }
    }

    int sum=0;

    for(int i=1;i<=n;i++)
    {
        int up,dw,lf,rt;//邻域的上下左右边界
        up=max(1,i-r);
        dw=min(n,i+r);
        for(int j=1;j<=n;j++)
        {
            lf=max(1,j-r);
            rt=min(n,j+r);
            float tot=0;
            for(int k=up;k<=dw;k++)
            tot+=mp[k][rt]-mp[k][lf-1];

            float avg=tot/((dw-up+1)*(rt-lf+1));

            if(avg<=t)
            sum++;
        }
    }

    printf("%d",sum);
}

202009-2风险人群筛查

是否经过只需要存在一个点在风险区域就足够，而判断停留需要连续K个点在风险区域。所以可以在第一次出现在风险区域内的点时计数，判断是否有连续K个点，若有则该人在风险区域停留，可以忽略之后的数据，否则重头开始计数。连续可以用一个变量来控制，若该点之前的点也在风险区域，该变量为真。

#include<bits/stdc++.h>
using namespace std;

int xl,yd,xr,yu;

bool inside(int x,int y)//判断是否在风险区域
{
    return (x<=xr&&x>=xl&&y<=yu&&y>=yd);
}

int main()
{
    int n,k,t;
    scanf("%d%d%d%d%d%d%d",&n,&k,&t,&xl,&yd,&xr,&yu);
    int cnt1=0,cnt2=0;

    for(int i=0;i<n;i++)
    {
        int cnt=0;
        bool go=false;//是否经过
        bool stay=false;//是否停留
        bool former=false;//上一个点是否在风险区域内
        for(int j=0;j<t;j++)
        {
            int x,y;
            scanf("%d%d",&x,&y);

            if(stay)//如果已经判断在风险区域停留了，之后的操作都可以忽略
            continue;

            if(inside(x,y))//如果当前点在风险区域内
            {
                go=true;//该人经过风险区域

                if(former)//前一个点在风险区域内
                cnt++;//计数加一
                else
                {
                    former=true;//将变量置为真
                    cnt=1;//计数初始化
                }
            }
            else
            {
                former=false;//连续计数中断
                cnt=0;
            }

            if(cnt>=k)
            {
                stay=true;
            }

        }

        if(go)
        cnt1++;
        if(stay)
        cnt2++;
    }

    printf("%d\n%d",cnt1,cnt2);
}

202006-2稀疏向量

向量很稀疏，所以直接开数组必然不行。为了根据下标找到该位置的元素，很容易想到map，只需要使用两个map分别记录两个向量的非零元素即可。（map,set查找删除插入的复杂度都是logn级别的）

#include<bits/stdc++.h>
#define ll long long
using namespace std;

map<ll,ll> point[2];

int main()
{
    ll n;
    int a,b;
    scanf("%lld%d%d",&n,&a,&b);

    for(int i=0;i<a;i++)
    {
        ll x,y;
        scanf("%lld%lld",&x,&y);
        point[0][x]=y;
    }

    for(int i=0;i<b;i++)
    {
        ll x,y;
        scanf("%lld%lld",&x,&y);
        point[1][x]=y;
    }

    ll res=0;

    for(auto it=point[0].begin();it!=point[0].end();it++)
    {
        ll y=it->second;
        ll x=it->first;
        if(point[1][x]!=0)
        res+=y*point[1][x];
    }

    printf("%lld",res);
}

201909-2小明种苹果（续）

这道题我记得我卡了很久，踩了几个坑，还看了很多CSDN的解答都没找到哪错了，后来看到一篇和我有一样错误的才发现理解错题目意思了。（不过我觉得这一点题目也没讲清楚）

一开始卡40分，貌似是因为如果一棵树重复掉落多次我会算作多棵树掉果子。改正了后变成了90分，我找不出问题就不停测试，还是百思不得其解。后来看到一篇博客说是因为理解错题意，如果有3棵树，那么123,231,312是算3组的，实在是没想到。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

bool drop[1010];//记录是否掉果

int main()
{
    int n=0;
    scanf("%d",&n);
    ll sum=0;
    for(int i=0;i<1010;i++)
    drop[i]=false;

    int dsum=0;
    int dgroup=0;

    bool one=false;
    bool two=false;

    for(int i=0;i<n;i++)
    {
        int num=0;
        scanf("%d",&num);

        ll now=0;
        scanf("%lld",&now);
        for(int j=0;j<num-1;j++)
        {
            ll x=0;
            scanf("%lld",&x);
            if(x>0)//大于0说明重新计算了
            {
                if(x!=now&&!drop[i+1])//如果与当前应该有的数量不同则发生了掉果
                {
                    drop[i+1]=true;
                    dsum++;
                }
                now=x;//更新当前树上果子数
            }
            else
            now+=x;
        }

        sum+=now;

         if(i==0)
         one=drop[i+1];//做必要的初始化
         else if(i==1)
         two=drop[i+1];
         else//从第三棵树开始判断
         {
             if(drop[i+1]&&one&&two)//是否有连续三棵树掉果
             dgroup++;
             one=two;
             two=drop[i+1];
         }
    }


    if(n>=3)//判断结尾和头两棵树组成的组
    {
        if(drop[n-1]&&drop[n]&&drop[1])
        dgroup++;
        if(drop[n]&&drop[1]&&drop[2])
        dgroup++;
    }

    printf("%lld %d %d",sum,dsum,dgroup);
  // printf("%lld %d 0",sum,dsum);
}

201903-2二十四点

一开始觉得不就是普通的计算吗，后来发现因为有乘除法变得有点麻烦。我的处理方法就是先看符号，如果是乘除号就把连续是乘法或除法的部分计算成一个数后加入式子，同时需要记录当前运算的符号。比较方便的是每个数字都只有1位，整个式子的位数是给定的了，并且没有括号。如果没有上述条件就是另一个故事了，括号yyds，我总是不会处理，只能gg

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n=0;
    scanf("%d",&n);

    while(--n>=0)
    {
        string format;
        cin>>format;
        int res=0;
        char symb='+';//式子第一个数一定是加入最终结果的，置初始符号为加号
        string turn;
        for(int i=0;i<7;i+=2)
        {
            if(format[i+1]!='x'&&format[i+1]!='/')//不是乘除号
            {
                if(symb=='+')//根据前面的符号加入最终结果
                res+=format[i]-'0';
                else res-=format[i]-'0';
                symb=format[i+1];
            }
            else
            {
                int part=0;//计算部分数值
                part+=format[i]-'0';
                i+=2;
                while(i+1<7&&format[i+1]!='+'&&format[i+1]!='-')//还没碰到加减号
                {
                    if(format[i-1]=='x')//做相应乘除运算
                    part*=format[i]-'0';
                    else part/=format[i]-'0';

                    i+=2;
                }
                
                if(format[i-1]=='x')//终于遇到加减号了，处理连续乘除串的最后一个数
                part*=format[i]-'0';
                else part/=format[i]-'0';

                if(symb=='+')
                res+=part;
                else res-=part;
                
                if(i+1<7)
                symb=format[i+1];//变换符号
            }
        }
        
        if(res==24)
        printf("Yes\n");
        else printf("No\n");
    }
}