POJ 1195 Mobile Phones

  • (XC90,T) 矩阵内的和假使用sum(翼虎+1,T+1) – sum(L,B)
    就行了,。傻x了。。

T3

图片 1

 

求仙人掌的直径,DP

可以去参考http://www.cnblogs.com/TheRoadToTheGold/p/7895298.html

 以前做过的切近的考场上写不出去没啥好说的

图片 2图片 3

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

#define N 100001

int front[N],to[N<<1],nxt[N<<1],val[N<<1];

int tot,ans;

int low[N],dfn[N];

int fa[N],dep[N];

int dp[N];

int q[N],tmp[N<<1];
int sum[N<<1];

void read(int &x)
{
    x=0; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
}

void clear()
{
    tot=1;
    ans=0;
    memset(front,0,sizeof(front));
    memset(dp,0,sizeof(dp));
    memset(dfn,0,sizeof(dfn));
}

void add(int u,int v,int w)
{
    to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; val[tot]=w;
    to[++tot]=u; nxt[tot]=front[v]; front[v]=tot; val[tot]=w;
}

void circle(int x,int y)
{
    int cnt=dep[y]-dep[x]+1;
    int now=y;
    while(dfn[fa[now]]>=dfn[x]) tmp[cnt--]=now,now=fa[now];
    tmp[cnt]=now;
    cnt=dep[y]-dep[x]+1;
    int m=cnt;
    for(int i=1;i<=cnt;++i) tmp[++m]=tmp[i];
    for(int i=1;i<=cnt;++i)
        for(int j=front[tmp[i]];j;j=nxt[j])
            if(to[j]==tmp[i+1]) { sum[i+1]=val[j]; break; }
    for(int i=2;i<=cnt;++i) sum[i+cnt]=sum[i];
    for(int i=1;i<=m;++i) sum[i]+=sum[i-1];
    int h=0,t=0;
    for(int i=1;i<=m;++i)
    {
        while(h<t && i-q[h]>=cnt) h++;
        if(h<t) ans=max(ans,dp[tmp[i]]+dp[tmp[q[h]]]+sum[i]-sum[q[h]]);
        while(h<t && dp[tmp[i]]-sum[i]>dp[tmp[q[t-1]]]-sum[q[t-1]]) t--;
        q[t++]=i;
    }
    for(int i=2;i<=cnt;++i) dp[x]=max(dp[x],dp[tmp[i]]+max(sum[i],sum[cnt+1]-sum[i]));
}

void tarjan(int x,int y)
{
    dfn[x]=low[x]=++tot;
    for(int i=front[x];i;i=nxt[i])
    {
        if(y==(i^1)) continue;
        if(!dfn[to[i]])
        {
            fa[to[i]]=x;
            dep[to[i]]=dep[x]+1;
            tarjan(to[i],i);
            low[x]=min(low[x],low[to[i]]);
        }
        else low[x]=min(low[x],dfn[to[i]]);
        if(low[to[i]]>dfn[x])
        {
            ans=max(ans,dp[x]+dp[to[i]]+val[i]);
            dp[x]=max(dp[x],dp[to[i]]+val[i]);
        }
    }
    for(int i=front[x];i;i=nxt[i])
        if(fa[to[i]]!=x && dfn[x]<dfn[to[i]]) circle(x,to[i]);
}

int main()
{
    freopen("path.in","r",stdin);
    freopen("path.out","w",stdout);
    int T;
    int n,m;
    int u,v,w;
    read(T);
    while(T--)
    {
        clear();
        read(n); read(m);
        while(m--)
        {
            read(u); read(v); read(w);
            add(u,v,w);
        }
        tot=0;
        tarjan(1,0);
        cout<<ans<<'\n';
    }
}

View Code

 

题解:

\[\begin{align} ans & =
\frac{\sum_{i=l}^r(x_i-\bar{x})(y_i-\bar{y})}{\sum_{i=l}^r(x_i-\bar{x})^2}\\
& =
\frac{\sum_{i=l}^r(x_iy_i-x_i\bar{y}-y_i\bar{x}+\bar{x}\bar{y})}{\sum_{i=l}^r(x_i^2-2x_i\bar{x}+\bar{x}^2)}
\\ & = \frac{\sum_{i=1}^rx_iy_i-\bar{y}\sum_{i=l}^rx_i –
\bar{x}\sum_{i=l}^ry_i+(r-l+1)\bar{x}\bar{y}}{\sum_{i=l}^rx_i^2-2\bar{x}\sum_{i=l}^rx_i

  • (r-l+1)\bar{x}^2} \\ & = \frac{\sum_{i=l}^rx_iy_i –
    \frac{\sum_{i=l}^rx_i\sum_{i=l}^ry_i}{r-l+1}}{\sum_{i=l}^rx_i^2-\frac{(\sum_{i=l}^rx_i)^2}{r-l+1}}
    \end{align}\]

由此我们要求爱惜\(\sum x_i,\sum y_i,\sum
x_iy_i,\sum x_i^2\)

很不难处理操作二:

  • 对于\(\sum x_iy_i\)加上\(val\sum y_i\)
  • 对于\(\sum x_i^2\),有\((x + val)^2 = x^2 + 2x*val +
    vval^2\)所以加上增量\(2*val\sum
    x,val^2\)即可

对此操作三,转化成一个赋值操作和三个操作二.
对此赋值操作..能够发现赋值后有\(\sum
x_iy_i = \sum x_i^2\)
实际上正是一个k次前缀和.k = 1 or 2
我们有:
\(\sum_{i=1}^ni =
\frac{n(n+1)}{2}\)
\(\sum_{i=1}^ni^2 =
\frac{n(n+1)(2n+1)}{6}\)
故而一直公式总结即可.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
    x = 0;static char ch,f;f = 1;
    while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),f = -1;
    while(x=(x<<1)+(x<<3)+ch-'0',ch=getchar(),ch>'!');x *= f;
}
#define rg register int 
#define rep(i,a,b) for(rg i=(a);i<=(b);++i)
#define per(i,a,b) for(rg i=(a);i>=(b);--i)
const int maxn = 100010;
struct Node{
    double sumx,sumy,misum,xysum;
    double lazy_x,lazy_y;bool tag;
    Node(){
        sumx = sumy = misum = xysum = lazy_x = lazy_y = 0;
        tag = 0;
    }
    friend Node operator + (const Node &a,const Node &b){
        Node c;
        c.sumx = a.sumx + b.sumx;
        c.sumy = a.sumy + b.sumy;
        c.misum = a.misum + b.misum;
        c.xysum = a.xysum + b.xysum;
        return c;
    }
}T[maxn<<2];
#define sum2(x) ( 1LL*(x)*((x)+1)*(2*(x)+1)/6 )
#define sum(x) (1LL*(x)*((x)+1)/2)
inline void add_tag(int rt,int l,int r){
    T[rt].misum = T[rt].xysum = sum2(r) - sum2(l-1);
    T[rt].sumx = T[rt].sumy = sum(r) - sum(l-1);
    T[rt].lazy_x = T[rt].lazy_y = 0;T[rt].tag = true;
}
inline void add_lazy_x(int rt,int l,int r,double val){
    T[rt].lazy_x += val;
    T[rt].misum += 2LL*val*T[rt].sumx + 1LL*val*val*(r-l+1);
    T[rt].xysum += 1LL*val*T[rt].sumy;
    T[rt].sumx += 1LL*val*(r-l+1); 
}
inline void add_lazy_y(int rt,int l,int r,double val){
    T[rt].lazy_y += val;
    T[rt].xysum += 1LL*val*T[rt].sumx;
    T[rt].sumy += 1LL*val*(r-l+1);
}
inline void pushdown(int rt,int l,int r){
    if(rt == 0 || l == r) return ;
    int mid = l+r >> 1;
    if(T[rt].tag){
        add_tag(rt<<1,l,mid);
        add_tag(rt<<1|1,mid+1,r);
        T[rt].tag = 0;
    }
    if(T[rt].lazy_x){
        add_lazy_x(rt<<1,l,mid,T[rt].lazy_x);
        add_lazy_x(rt<<1|1,mid+1,r,T[rt].lazy_x);
        T[rt].lazy_x = 0;
    }
    if(T[rt].lazy_y){
        add_lazy_y(rt<<1,l,mid,T[rt].lazy_y);
        add_lazy_y(rt<<1|1,mid+1,r,T[rt].lazy_y);
        T[rt].lazy_y = 0;
    }
    return ;
}
int L,R,vx,vy;
inline Node query(int rt,int l,int r){
    if(L <= l && r <= R) return T[rt];
    int mid = l+r >> 1;pushdown(rt,l,r);
    if(R <= mid) return query(rt<<1,l,mid);
    if(L >  mid) return query(rt<<1|1,mid+1,r);
    return query(rt<<1,l,mid) + query(rt<<1|1,mid+1,r);
}
inline void modify(int rt,int l,int r){
    if(L <= l && r <= R){
        add_lazy_x(rt,l,r,vx);
        add_lazy_y(rt,l,r,vy);
        return ;
    }
    int mid = l+r >> 1;pushdown(rt,l,r);
    if(L <= mid) modify(rt<<1,l,mid);
    if(R >  mid) modify(rt<<1|1,mid+1,r);
    T[rt] = T[rt<<1] + T[rt<<1|1];
}
inline void cover(int rt,int l,int r){
    if(L <= l && r <= R){
        add_tag(rt,l,r);
        return ;
    }
    int mid = l+r >> 1;pushdown(rt,l,r);
    if(L <= mid) cover(rt<<1,l,mid);
    if(R >  mid) cover(rt<<1|1,mid+1,r);
    T[rt] = T[rt<<1] + T[rt<<1|1];
}
int x[maxn],y[maxn];
inline void build(int rt,int l,int r){
    if(l == r){
        T[rt].sumx = x[l];
        T[rt].sumy = y[l];
        T[rt].misum = 1LL*x[l]*x[l];
        T[rt].xysum = 1LL*x[l]*y[l];
        return ;
    }
    int mid = l+r >> 1;
    build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);
    T[rt] = T[rt<<1] + T[rt<<1|1];
}
int main(){
    int n,m;read(n);read(m);
    rep(i,1,n) read(x[i]);
    rep(i,1,n) read(y[i]);
    build(1,1,n);
    int op;double X,Y,len,a,b;
    Node tmp;
    while(m--){
        read(op);
        read(L);read(R);
        if(op == 1){
            tmp = query(1,1,n);
            X = tmp.sumx;
            Y = tmp.sumy;
            len = R - L + 1;
            a = tmp.xysum;
            b = tmp.misum;
            printf("%.10lf\n",(len*a - X*Y)/(len*b - X*X));
            continue;
        }
        read(vx);read(vy);
        if(op == 2){
            modify(1,1,n);
        }else{
            cover(1,1,n);
            modify(1,1,n);
        }
    }
    return 0;
}

树状数组,初步的时候wa了,后来探访,原来是可能率论没学好,以为求(L,B)

T1

图片 4

 

sum[r]^sum[l-1]<k

对前缀异或和建trie树

假定当前是第i位,sum[r]的地i位是l

假设k的第i位为1,累加l,当前线指挥部针转到sum[r]的l^1

要否则,当前指针间接转到sum[r]的l

图片 5图片 6

#include<cstdio>
#include<iostream>

using namespace std;

typedef long long LL;

#define N 100001

int bit[31];

int tr[N*30][2],sum[N*30];

int k;

int tot=1,root=1;

LL ans;

void read(int &x)
{
    x=0; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
}

void insert(int x)
{
    int now=root;
    bool j;
    for(int i=30;i>=0;--i)
    {
        j=x&bit[i];
        if(!tr[now][j]) tr[now][j]=++tot;
        now=tr[now][j];
        sum[now]++;
    }
}

void query(int x)
{
    int now=root;
    bool l,r;
    for(int i=30;i>=0;--i)
    {
        if(!now) return;
        l=x&bit[i];
        r=l^1;
        if(k&bit[i])
        {
            ans+=sum[tr[now][l]];
            now=tr[now][r];
        }
        else now=tr[now][l];
    }
}

int main()
{
    freopen("bit.in","r",stdin);
    freopen("bit.out","w",stdout);
    bit[0]=1;
    for(int i=1;i<=30;++i) bit[i]=bit[i-1]<<1;
    int n,x;
    read(n); read(k);
    insert(0);
    int pre=0;
    for(int i=1;i<=n;++i)
    {
        read(x);
        pre^=x;
        query(pre);
        insert(pre);
    }
    cout<<ans;
}

View Code

 

题目:

Frank对天农学相当感兴趣,他每每用望远镜看个别,同时记录下它们的音讯,比如亮度、颜色等等,进而推断出个别的偏离,半径等等。Frank不仅喜欢观望,还爱好分析观测到的多寡。他时常分析四个参数之间(比如亮度和半径)是不是存在某种关联。未来Frank要分析参数X与Y之间的涉嫌。他有n组观测数据,第i组观测数据记录了x_i和y_i。他须要弹指间二种操作
1 L,帕Jero:用直线拟合第L组到底冠道组观测数据。
用\(xx\)表示那些观测数据中 class=”math inline”>\(x\)的平平均数量,用 class=”math inline”>\(yy\)表示那一个观测数据中 class=”math inline”>\(y\)的平平均数量,即
xx = Σx_i/(R-L+1)(L<=i<=R)
yy = Σy_i/(R-L+1)(L<=i<=R)
若果直线方程是y=ax+b,那么a应当那样计算:
a = (Σ(x_i-xx)(y_i-yy))/(Σ(x_i-xx)(x_i-xx)) (L<=i<=R)
你供给支援Frank计算a。
2 L,R,S,T:
Frank发现衡量数据第L组到底CRUISER组数据有误差,对各类i满意L <= i <=
奥迪Q5,x_i必要加上S,y_i要求加上T。
3 L,R,S,T:
Frank发现第L组到第Enclave组数据需求修改,对于每一种i满意L <= i <=
Sportage,x_i供给修改为(S+i),y_i须要修改为(T+i)。
1<=n,m<=10^5,0<=|S|,|T|,|x_i|,|y_i|<=10^5

代码:

骨子里得分:100+100+20=220

View Code

Summary

① 、5个钟头的时日,能够放心大胆的去写思路清晰的正解

贰 、A掉题远比暴力带来的收益多,无论是分数照旧心情

③ 、一定要写对拍,后天只要没写对拍测度分数两位数

四 、一定要读好题,特别是输入描述中先输入啥后输入啥,像那种:“A
l r k
b:在区间[l,r]上加上3个首项为b、公差为k的等差数列。”,后天就读成了A l
r b k,白白浪费了半个时辰

伍 、当出现小数码正确,大数额失实时,去反省数组大小,明天T2的线条树2个数组没开4倍,又浪费了半钟头

六 、要给不打算写正解的题留出丰裕的强力时间,方今日的T3,至少五1九分的武力因为时间原因写了40,得了20

七 、最后一道题,有正解思路但细节难点还没想好,不成熟,还剩不到近年来辰,果断选用写暴力,就好像T3,如果以卵击石接纳去写正解,二十分都尚未了

⑧ 、不奇怪表达,会的分都获得,排行一定差不了。后天希望240(rank2),实际220(rank2),很多实力比小编强的各样写炸。

⑨ 、所以,将协调的实力在鲜明的年月、地方整体发挥出来,不留遗憾才是本身今后要做的!

 

 

 

T2

图片 7

线段树

设sum[i]意味着区间的和,sum2[i]代表区间数的平方和

预处理pre1[i]:i^2的前缀和,pre2[i]:i*2的前缀和

至今要对区间加首项为a1,公差为d的等差数列

要是间隔有六个数,A、B、C、D,区间大小siz=4

原来的sum[i]=A+B+C+D

现在的sum[i]=A+a1+B+a1+d+C+a1+2d+D+a1+3d

即新的sum[i]=原来的sum[i]+siz*a1+(siz-1)*siz*d

原来的sum2[i]=A^2+B^2+C^2+D^2

现在的sum2[i]=(A+a1)^2 +
(B+a1+d)^2 + (C+a1+2d)^2 + (D+a1+3d)^2 

=A^2+a1^2+2*A*a1 +
B^2+a1^2+d^2+2*B*a1+2*B*d+2*a1*d +
C^2+a1^2+4*d^2+2*C*a1+4*C*d+4*a1*d +
D^2+a1^2+9*d^2+2*D*a1+6*D*d+6*a1*d

=(A^2+B^2+C^2+D^2)+(a1^2+a1^2+a1^2+a1^2)+(d^2+4*d^2+9*d^2)+(2*A*a1+2*B*a1+2*C*a1+2*D*a1)+(2*a1*d+4*a1*d+6*a1*d)+(2*B*d+4*C*d+6*D*d)

=原来的sum2[i]+siz*a1^2+pre[siz-1]*d^2+2*原来的sum[i]*a1+pre[siz-1]*a1*d+pre[siz-1]*a1*d+ (2*B*d+4*C*d+6*D*d)

最后的十三分怎么维护?

令sum3[i]表示0*A+1*B+2*C+3*D……

末段特别正是sum[3]*2*d

 

合并时,sum,sum2间接统一

sum3[k]=sum3[L]+sum3[R]+siz[L]*sum[R]

L:0*A+1*B+2*C

R:0*D+1*E+2*F

合并后:0*A+1*B+2*C+3*D+4*E+5*F

集合后宝马X5的一对与子区间的本田CR-V每种值差了siz[L]倍

图片 8图片 9

#include<cstdio>
#include<iostream>

using namespace std;

const int mod=1000000007;

#define N 100001

typedef long long LL;

LL pre1[N],pre2[N];

LL siz[N<<2];
LL sum[N<<2],sum2[N<<2],sum3[N<<2];
LL fa1[N<<2],fd[N<<2];

LL ans;

void read(int &x)
{
    x=0; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
}

void read(LL &x)
{
    x=0; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
}

void pre(int n)
{
    for(int i=1;i<=n;++i)
    {
        pre1[i]=(pre1[i-1]+i*i)%mod;
        pre2[i]=pre2[i-1]+i*2;
        pre2[i]-=pre2[i]>=mod ? mod : 0;
    }
}

void build(int k,int l,int r)
{
    siz[k]=r-l+1;
    if(l==r)
    {
        read(sum[k]);
        sum2[k]=(sum[k]*sum[k])%mod;
        return;
    }
    int mid=l+r>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    sum[k]=sum[k<<1]+sum[k<<1|1];
    sum[k]-=sum[k]>=mod ? mod : 0;
    sum2[k]=sum2[k<<1]+sum2[k<<1|1];
    sum2[k]-=sum2[k]>=mod ? mod : 0;
    sum3[k]=(sum3[k<<1]+siz[k<<1]*sum[k<<1|1]%mod+sum3[k<<1|1])%mod;
}

void insert_(int k,LL a1,LL d)
{
    sum2[k]=(sum2[k]+a1*a1%mod*siz[k]%mod+d*d%mod*pre1[siz[k]-1]%mod+a1*d%mod*pre2[siz[k]-1]%mod+sum[k]*2*a1%mod+sum3[k]*d*2%mod)%mod;
    sum3[k]=(sum3[k]+siz[k]*(siz[k]-1)/2%mod*a1%mod+pre1[siz[k]-1]*d%mod)%mod;
    sum[k]=(sum[k]+siz[k]*a1%mod+siz[k]*(siz[k]-1)/2%mod*d%mod)%mod;
    fa1[k]+=a1; 
    fa1[k]-=fa1[k]>=mod ? mod : 0;
    fd[k]+=d;
    fd[k]-=fd[k]>=mod ? mod : 0;
}

void down(int k,int s)
{
    insert_(k<<1,fa1[k],fd[k]);
    insert_(k<<1|1,(fa1[k]+s*fd[k])%mod,fd[k]);
    fa1[k]=fd[k]=0;
}

void insert(int k,int l,int r,int opl,int opr,LL a1,LL d)
{
    if(l>=opl && r<=opr)
    {
        insert_(k,a1,d);
        return;
    }
    int mid=l+r>>1;
    if(fa1[k] || fd[k])  down(k,mid+1-l);
    if(opr<=mid) insert(k<<1,l,mid,opl,opr,a1,d);
    else if(opl>mid) insert(k<<1|1,mid+1,r,opl,opr,a1,d);
    else
    {
        insert(k<<1,l,mid,opl,mid,a1,d);
        insert(k<<1|1,mid+1,r,mid+1,opr,(a1+(mid+1-opl)*d)%mod,d);
    } 
    sum[k]=sum[k<<1]+sum[k<<1|1];
    sum[k]-=sum[k]>=mod ? mod : 0;
    sum2[k]=sum2[k<<1]+sum2[k<<1|1];
    sum2[k]-=sum2[k]>=mod ? mod : 0;
    sum3[k]=(sum3[k<<1]+siz[k<<1]*sum[k<<1|1]%mod+sum3[k<<1|1])%mod;
}

void query(int k,int l,int r,int opl,int opr,bool w)
{
    if(l>=opl && r<=opr)
    {
        if(w) ans+=sum2[k];
        else ans+=sum[k];
        ans-=ans>=mod ? mod : 0;
        return;
    }
    int mid=l+r>>1;
    if(fa1[k] || fd[k])  down(k,mid+1-l);
    if(opl<=mid) query(k<<1,l,mid,opl,opr,w);
    if(opr>mid) query(k<<1|1,mid+1,r,opl,opr,w);
}

int main()
{
    freopen("calculation.in","r",stdin);
    freopen("calculation.out","w",stdout);
    int n,m;
    read(n); read(m);
    pre(n);
    build(1,1,n);
    char c[3]; 
    int l,r,b,k;
    while(m--)
    {
        scanf("%s",c);
        if(c[0]=='A')
        {
            read(l); read(r); read(k); read(b);
            insert(1,1,n,l,r,b,k);
        }
        else 
        {
            read(l); read(r);
            ans=0;
            query(1,1,n,l,r,c[0]=='C');
            cout<<ans<<'\n';
        }
    }
}

View Code

 

 

梦想得分:100+100+40=240

图片 10图片 11

总得
sum(奔驰M级,T) – sum(L,T) – sum(奥迪Q7,B) + sum(L,B) ;  (本田CR-V,T 已经自加1)  
诫之。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 1027

int c[N][N];
int n;

int lowbit(int x)
{
    return x&(-x);
}

void modify(int x,int y,int val)
{
    for(int i=x;i<=n;i+=lowbit(i))
    {
        for(int j=y;j<=n;j+=lowbit(j))
        {
            c[i][j] += val;
        }
    }
}

int sum(int x,int y)
{
    int res = 0;
    for(int i=x;i>0;i-=lowbit(i))
    {
        for(int j=y;j>0;j-=lowbit(j))
        {
            res += c[i][j];
        }
    }
    return res;
}

int main()
{
    int op,L,B,R,T,A,X,Y;
    while(scanf("%d",&op)!=EOF)
    {
        if(op == 3)
            break;
        else if(op == 0)
        {
            memset(c,0,sizeof(c));
            scanf("%d",&n);
        }
        else if(op == 1)
        {
            scanf("%d%d%d",&X,&Y,&A);
            X++;Y++;
            modify(X,Y,A);
        }
        else if(op == 2)
        {
            scanf("%d%d%d%d",&L,&B,&R,&T);
            R++;T++;
            printf("%d\n",sum(R,T)-sum(L,T)-sum(R,B)+sum(L,B));
        }
    }
    return 0;
}

相关文章