第23次CSP认证(202109)

• • • 第一题 ：数组推导    (贪心)
    • 第二题 ：非零段划分   (差分)
    • 第三题 ：脉冲神经网络(模拟)
    • 第四题 ：收集卡牌

贪心循环一遍

在这里插入代码片

70分做法：
暴力，枚举 出现过的数字。

#include
#include
#define ll  long long
using namespace std;
const int maxx=500019;
vector v;
int a[maxx],b[maxx],n;
int check(int p) //判断没个p的个数
{
    int num=0;
    for(int i=1; i<=n; i++)
    {
        if(a[i]>=p&&a[i-1] 
100分做法：
 
什么情况下非零子段个数会增加呢？
 相邻的两个数a[1]，a[2]。 a[2]>a[1]时如果p>a[1]&&p<=a[1],那么a[0]会被置零。此时就成为了一个有效的非零子段。
 
我们可以将p>a[1]&&p<=a[1] 想像成数组上的一个区间，只要p在这个区间内，就认为可以构成一个非零字段。那么数组上若干个区间，差分，前缀和，遍历求最大值。将a[i-1]+1 位置++，a[i]+1位置–。只要p在【 a[i-1]+1 , a[i] 】范围内就是一个有效值。
 
#include
#include
#define ll  long long
using namespace std;
const int maxx=500019;
ll a[maxx],b[maxx],n;

int main()
{
    ll Max=-1;
    scanf("%lld",&n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
        Max=max(Max,a[i]);
        if(a[i]>a[i-1])
        {
            b[a[i-1]+1]++;
            b[a[i]+1]--;
        }
    }
    ll temp=0,ans=0;
    for(int i=1; i<=Max; i++)
    {
         temp+=b[i];
         ans=max(ans,temp);
    }
    printf("%lldn",ans);
    return 0;
}

 
第三题 ：脉冲神经网络(模拟) 
超时 ，66分。
 T 时刻，P脉冲。每个时刻不是都应该rand吗？T*P难道不是必须的吗？这样就1e8了。脉冲有规律？一开始传递 w 用优先队列写的，由于优先队列每次logN的时间复杂度，超时能理解。后来改成了二维数组，这样就是O(1)了。也超时，暂时想不出来了。
 
#include
#include
#include
#define ll long long
using namespace std;
const int maxx=2009;
static unsigned long next_r = 1;
int myrand(void)
{
    next_r=next_r*1103515245+12345;
    return((unsigned)(next_r/65536) % 32768);
}

int num[maxx];
struct sjy
{
    double v,u,pre_v,pre_u;
    double a,b,c,d;
    double Ik=0;
    int num=0;

} sj[maxx];
struct tuchu
{
    int endd,D;
    double w;
    tuchu(int ed,double ww,int DD)
    {
        endd=ed,w=ww,D=DD;
    }

};

vector v[maxx];
int  maichong_r[maxx*3];
struct node
{
    int TT;
    int end_node;
    double ww;
    node(int e,double w)
    {
      end_node=e,ww=w;
    }
    bool operator<(const node&n2)const
    {
        return n2.TTrr)
            {
                for(int k=0; k<(int)v[j].size(); k++)
                {
                    tuchu temp=v[j][k];
                    kk[temp.endd][i+temp.D]+=temp.w;
                }
            }

        }
        for(int j=0; j=30)
            {
                sj[j].num++;
                sj[j].v=sj[j].c;
                sj[j].u=sj[j].u+sj[j].d;
                for(int k=0; k<(int)v[j].size(); k++)
                {
                    tuchu temp=v[j][k];
                     kk[temp.endd][i+temp.D]+=temp.w;

                }

            }
            sj[j].pre_v=sj[j].v;
            sj[j].pre_u=sj[j].u;
            sj[j].Ik=0;
        }


    }

    double ans1=99999999,ans2=-99999999;
    int ans3=99999999,ans4=0;
    for(int i=0; i 
第四题 ：收集卡牌 
在这里插入代码片