做题记录

10.24

凹了一晚上线段树，P3372，然后发现这个板子可以过树状数组,于是过了P3374和P3368，都是板子，改改就行了。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5;
int a[maxn+2];
struct tree
{
	int l,r;
	long long pre,add;
}t[4*maxn+2];
void bulid(int p,int l,int r)
{
	t[p].l=l,t[p].r=r;
	if(l==r) 
	{
		t[p].pre=a[l];
		return;
	}
	int mid=l+r>>1;
	bulid(p*2,l,mid);
	bulid(p*2+1,mid+1,r);
	t[p].pre=t[p*2].pre+t[p*2+1].pre;
}
void lazy(int p)
{
	if(t[p].add)
	{
	   t[p*2].pre+=t[p].add*(t[p*2].r-t[p*2].l+1);
	   t[p*2+1].pre+=t[p].add*(t[p*2+1].r-t[p*2+1].l+1);
	   t[p*2].add+=t[p].add;
	   t[p*2+1].add+=t[p].add;
	   t[p].add=0;
	}
}
void change(int p,int x,int y,int z)
{
	if(x<=t[p].l && y>=t[p].r)
	{
		t[p].pre+=(long long)z*(t[p].r-t[p].l+1);
		t[p].add+=z;
		return;
	}
	lazy(p);
	int mid=t[p].l+t[p].r>>1;
	if(x<=mid) change(p*2,x,y,z);
	if(y>mid) change(p*2+1,x,y,z);
	t[p].pre=t[p*2].pre+t[p*2+1].pre;
} 
long long find(int p,int x,int y)
{
	if(x<=t[p].l && y>=t[p].r) return t[p].pre;
	lazy(p);
	int mid=t[p].l+t[p].r>>1;
	long long ans=0;
	if(x<=mid) ans+=find(p*2,x,y);
	if(y>mid) ans+=find(p*2+1,x,y);
	return ans;
} 
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;++i)
	cin>>a[i];
	bulid(1,1,n);
	for(int i=1;i<=m;++i)
	{
		int q,x,y,z;
		cin>>q;
		if(q==1) 
		{
			cin>>x>>y>>z;
			change(1,x,y,z);
		}
		else 
		{
			cin>>x>>y;
			cout<<find(1,x,y)<<endl;
		}
	}
}

然后把J组T1过了，(考场没想出来)。
然后开颓，过了几个板子，不说了。

10.25

开概率期望，然后做了一个很水的概率期望P1297

code

#include<bits/stdc++.h>
using namespace std;
long long n,A,B,C,a[10000010];
void init()
{
   scanf("%d%d%d%d%d", &n, &A, &B, &C, a + 1);
for (int i = 2; i <= n; i++)
   a[i] = ((long long) a[i - 1] * A + B) % 100000001;
for (int i = 1; i <= n; i++)
   a[i] = a[i] % C + 1;
}
int main()
{
   double ans;
   init();
   a[n+1]=a[1];
   for(int i=1;i<=n;++i)
   {
       ans+=1/double(max(a[i+1],a[i]));
   }
   printf("%.3f",ans);

}

咋这么短啊，恼了。