第23次CSP认证---202109
- 第一题 ：数组推导 (贪心)
- 第二题 ：非零段划分 (差分)
- 第三题 ：脉冲神经网络(模拟)
- 第四题 ：收集卡牌( DP )
第一题 ：数组推导 (贪心)
贪心循环一遍
在这里插入代码片
第二题 ：非零段划分 (差分)
70分：
暴力枚举p ,出现过的数字。
100分：
什么情况下非零子段个数会增加呢？
相邻的两个数a[1]，a[2]。当 a[2]>a[1]时，如果p>a[1]&&p<=a[2],那么a[1]会被置零,a[2]不变。此时就成为了一个有效的非零子段。为什么要相邻呢？避免重复，小于p的值全部置零，相当于合并区间去重了
我们可以将p>a[1]&&p<=a[2] 想像成数组上的一个区间，只要p在这个区间内，就认为可以构成一个非零字段。那么数组上若干个区间，差分，前缀和，遍历求最大值。
将a[i-1]+1 (相当于有效的p的最小值)位置++，a[i]+1位置–。只要p在【 a[i-1]+1 , a[i] 】范围内就是一个有效值。
#include<bits/stdc++.h>
#include<iostream>
#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("%lld\n",ans);
return 0;
}
第三题 ：脉冲神经网络(模拟)
超时 ，66分。
T 时刻，P脉冲。每个时刻不是都应该rand吗？T*P难道不是必须的吗？这样就1e8了。脉冲有规律？一开始传递 w 用优先队列写的，由于优先队列每次logN的时间复杂度，超时能理解。后来改成了二维数组，这样就是O(1)了。也超时，暂时想不出来了。
#include<>
#include<vector>
#include<queue>
#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<tuchu> 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.TT<TT;
}
};
double kk[1009][100019];
int main()
{
int N,S,P,T;
double timet;
scanf("%d%d%d%d",&N,&S,&P,&T);
scanf("%lf",&timet);
int tot=0,pre=0;
while(tot<N)
{
int n;
double vv,uu,aa,bb,cc,dd;
scanf("%d%lf%lf%lf%lf%lf%lf",&n,&vv,&uu,&aa,&bb,&cc,&dd);
for(int i=pre; i<pre+n; i++)
{
sj[i].pre_v=vv,sj[i].pre_u=uu,sj[i].a=aa;
sj[i].b=bb,sj[i].c=cc,sj[i].d=dd;
}
pre=pre+n;
tot+=n;
}
for(int i=N; i<P+N; i++) // 脉冲 N----P+N
{
scanf("%d",&maichong_r[i]);
}
int start2,endd2,D2;
double ww2;
for(int i=0; i<S; i++) //突触
{
scanf("%d%d%lf%d",&start2,&endd2,&ww2,&D2);
v[start2].push_back(tuchu(endd2,ww2,D2));
}
for(int i=1; i<=T; i++)
{
for(int j=N; j<P+N; j++) //脉冲
{
int rr=myrand();
if(maichong_r[j]>rr)
{
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<N; j++)
{
sj[j].v=sj[j].pre_v+timet*(0.04*sj[j].pre_v*sj[j].pre_v+5*sj[j].pre_v+140-sj[j].pre_u)+kk[j][i];
sj[j].u=sj[j].pre_u+timet*sj[j].a*(sj[j].b*sj[j].pre_v-sj[j].pre_u);
if(sj[j].v>=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<N; i++)
{
ans1=min(ans1,sj[i].v);
ans2=max(ans2,sj[i].v);
ans3=min(ans3,sj[i].num);
ans4=max(ans4,sj[i].num);
}
printf("%.3lf %.3lf\n",ans1,ans2);
printf("%d %d\n",ans3,ans4);
return 0;
}
第四题 ：收集卡牌( DP )
n<=16,k<=5。手中拥有卡牌的状态最多2^16=65536种。用二进制1 / 0 来描述这种卡牌有没有。同时，最多抽k*(n-1)+1,76次。 7e4*100
dp[i][j]：当前卡牌状态，硬币的数量下的概率。
判断当前状态是否能收集完，收集完就不再抽。
ans：j是硬币的数量，终态的概率要乘以j+卡牌的数，卡牌也在抽的次数里，不然。。。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxx=65536+99;
int n,k;
double p[99],dp[maxx][99],ans=0;
int cnt(int n)//当前已经拥有的卡牌的种类数,(二进制位1的个数)
{
int num=0;
while(n)
{
if(n&1)
num++;
n>>=1;
}
return num;
/*
一位一位的数，或者用bitset的conut函数
后来无意中想到的，试了交一下也是可以的
bitset<20> b(n);
return ();
*/
}
bool judge(int i,int j)
{
if(cnt(i)+j/k>=n)
{
ans+=dp[i][j]*(cnt(i)+j);
return true;
}
return false;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=0; i<n; i++)
scanf("%lf",&p[i]);
dp[0][0]=1;
for(int i=0; i<(1<<n); i++)
for(int j=0; j<=k*(n-1)+1; j++)
{
if(!judge(i,j)) //没有到终态，继续抽
{
for(int l=0; l<n; l++) //遍历n张牌
{
if(i&(1<<l))
dp[i][j+1]+=dp[i][j]*p[l];//手里已经有了第l张,手里牌的种类状态不变，硬币数+1
else
dp[i|(1<<l)][j]+=dp[i][j]*p[l];//没有第l张牌，手里的牌的状态要更新，硬币数不变
}
}
}
printf("%.10lf\n",ans);
return 0;
}