7.14做题总结

今天啥也没学，我也算是废了，随便从我写的题里面抽两道总结一下吧

P2671 [NOIP2015 普及组] 求和

这题我们的暴力解决方法，为枚举x和z然后通过x+z/2=y.来得到y，但是我们发现这中做法的时间复杂度为O(n^2)，很明显对于我们这题来说时间复杂度是一定超了的，那么我们再想，会不会有一些可以简单复杂度的方法，那么我们只能用到我们的分治思想了，因为要求的是x,z的颜色是要一样的，那么我们就让他一样，给每个颜色进行分组，分成m组，然后再对里面的编号进行分奇偶处理，因为x与z是同奇同偶的，因此，总共会分成m组，那么我们来推一下公式是什么

如果一个里面有三个元素，标号为x1,x2,x3，值为y1,y2,y3

那么计算公式为：

(x1+x2)*(y1+y2)+(x1+x3)*(y1+y3)+(x2+x3)+(y2+y3)

x1*(y1+y2+y1+y3)+x2*(y2+y1+y2+y3)+x3*(y3+y1+y3+y2)

所以可以总结一下公式，也就是标号*（（cnt-1）（这个标号颜色有多少个）+这个标号的颜色的前缀和）

因此代码为

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

int n,m;
int num[100005];
int color[100005];
int cnt[100005][2];//统计每种颜色奇偶性的个数
int pre[100005][2];//值的前缀和数组
int mod=10007;
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	cin>>num[i];
	for(int i=1;i<=n;i++)
	{
		cin>>color[i];
		cnt[color[i]][i%2]++;
		pre[color[i]][i%2]=(pre[color[i]][i%2]+num[i])%mod;
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		ans=(ans+(i*(cnt[color[i]][i%2]-2)*num[i])%mod+(i*pre[color[i]][i%2])%mod)%mod;
	}
	cout<<ans;
	return 0;
 } 

 P2880 [USACO07JAN] Balanced Lineup G

区间询问，咱们的老朋友了，直接写代码就行

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

int n,m;
int h[50005];
struct node{
    int l;
    int r;
    int sum;
    int maxn;
    int minn;
}tree[50005*4];

void build(int i,int l,int r)
{
    tree[i].l=l,tree[i].r=r;
    if(l==r)
    {
        tree[i].maxn=h[l];
        tree[i].minn=h[l];
        return ;
    }
    int mid=(l+r)/2;
    build(i*2,l,mid);
    build(i*2+1,mid+1,r);
    tree[i].maxn=max(tree[i*2].maxn,tree[i*2+1].maxn);
    tree[i].minn=min(tree[i*2].minn,tree[i*2+1].minn);
}

int find_max(int i,int l,int r)
{
    if(tree[i].l>=l&&tree[i].r<=r)
    {
        return tree[i].maxn;
    }
    int mid=(tree[i].l+tree[i].r)/2;
    int maxn=-1;
    if(mid>=l)
    {
        maxn=max(maxn,find_max(i*2,l,r));
    }
    if(mid+1<=r)
    {
        maxn=max(find_max(i*2+1,l,r),maxn);
    }
    return maxn;
}

int find_min(int i,int l,int r)
{
    if(tree[i].l>=l&&tree[i].r<=r)
    {
        return tree[i].minn;
    }
    int mid=(tree[i].l+tree[i].r)/2;
    int minn=0x3f3f3f3f;
    if(mid>=l)
    {
        minn=min(minn,find_min(i*2,l,r));
    }
    if(mid+1<=r)
    {
        minn=min(find_min(i*2+1,l,r),minn);
    }
    return minn;
}

signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>h[i];
    }
    build(1,1,n);
    int x,y;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        cout<<find_max(1,x,y)-find_min(1,x,y)<<"\n";
    }
    return 0;
}