• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

5.2总结

开发技术 开发技术 1周前 (05-02) 5次浏览

今天又是考的非常糟糕的一天

t1看错题了,想了半个小时没想出来55分,气而转t2,想完60分以后,想正解,我**了,竟然没想起来s={a,z}|{A,Z},还以为s里随便取的,然后是t3,看了一眼好像见过,但是好像没写,推了一会dp感觉不能做,就看t4去了,t4想了很长时间,一直以为是组合数+构造什么的,质因子数==2想了一会头疼就算了,一看表就9点多了,回去看t1,打了暴力过不了样例,仔细一看题,发现一直都看错题了,hehe,赶紧写完55分一看9.44,想了一会以为是什么神仙数据结构,就走额,很快把第二题暴力打完就走了,t3暴力都不会,赶紧走额,打了t4的暴力,还行,打完就11.20了,无意间发现质因子数==2的情况可以打表,但是来不及了,于是赶紧打了10的几次方的表,就交了

反思:

看题看错,太**了。

没有思路,就再看一眼题面,看着像打表的就先写,注意数据里的标出来的特殊信息

题解:

t1:

发现 a[i] 对于答案的贡献就是它被包含的次数,经过手推,发现只有当区间长度为奇数,并且是区间的第一个数,第三个数,第r-l+1个数时才有贡献,套一个树状数组就行了

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N],n;
int c[N][2];
void add(int x,int v)
{
    int k=x&1;
    while(x<=n)
    {
        c[x][k]^=v;
        x+=x&-x;
    }
}
int query(int x)
{
    if(x<0) return 0;
    int res=0;
    int k=x&1;
    while(x)
    {
        res^=c[x][k];
        x-=x&-x;
    }
    return res;
}
int main()
{
//    freopen("xor.in","r",stdin);
//    freopen("xor.out","w",stdout);
    int m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) add(i,a[i]);
    int l,r,ok;
    while(m--)
    {
        scanf("%d %d %d",&ok,&l,&r);
        if(ok==1) add(l,a[l]^r),a[l]=r;
        else {
            if((r-l+1)%2==0) {
                printf("0n");
                continue;
            }
            printf("%dn",query(r)^query(l-2));//保持 奇偶性 
        }
    }
    return 0;
}

t2:

hehe,map记一下差分数组就行了

 

t3:

奇怪的dp

f[c][x][y][z] 当前点是颜色c,已经用了x个颜色0,y个颜色1,z个颜色2

不同颜色转移一下就好了,注意两个状态之间转移的贡献不是直接走过去

 

t4:

奇怪的爆搜

明天再说吧


程序员灯塔
转载请注明原文链接:5.2总结
喜欢 (0)