头像

秦淮岸灯火阑珊已退役

yxc粉丝后援会,此人已经退役,无法回复各位大佬的评论了。


访客:244693

离线:6小时前


新鲜事 原文

level4出来了!!!中考顺利后,必报啊!!!


新鲜事 原文

语文130.5竟然还只是班级第四,呜呜呜,前三名都比我高一分。。。。(我恨文言文)


新鲜事 原文

一模,成功划水到年级前二十,中考加油!!!


新鲜事 原文

中考还有24天,加油啊!!!


新鲜事 原文

最后三十天了加油!希望能够抓住最后一次机会翻盘啊!



我暂时退役了,明年再见。
各位回复不能见了。
各位加油,共勉。
Acwing加油。




曾记否,严寒的冬季,指尖的冰冷。

曾记否,酷热的夏季,眉头的细汗。

曾记否,绿色的AC,带来的欢快。

也曾记否,程序的代码,是思想的升华。

无论结果如何,身为一位OIer,努力了,就是幸福的。

赛场上,我们不求超常发挥,只求不再悔恨。

或许我们将会退役,或许将重回文化课,与机房别离,与键盘说再见。

但是,至少多年后,我们仍可以追忆曾经的辉煌岁月。

不悔华年,不负自己。

最后愿你

CSP RP++!

—Update----

如果明天晚上,我没有更新,可能大家看到我,就是我大学的时候了。。。。。。

如果可以,我真的不希望退役。。。。。

对不起OI,对不起我的Acwing。。。。

—Update----

目前处于半退役状态!




更好的阅读体验

题目描述

蒟蒻HansBug在一本数学书里面发现了一个神奇的数列,包含$N$个实数。他想算算这个数列的平均数和方差。

输入输出格式

输入格式

第一行包含两个正整数$N$、$M$,分别表示数列中实数的个数和操作的个数。

第二行包含$N$个实数,其中第$i$个实数表示数列的第$i$项。

接下来M行,每行为一条操作,格式为以下两种之一:

操作1:1 x y k ,表示将第$x$到第$y$项每项加上$k$,$k$为一实数。

操作2:2 x y ,表示求出第$x$到第$y$项这一子数列的平均数。

操作3:3 x y ,表示求出第$x$到第$y$项这一子数列的方差。

输出格式

输出包含若干行,每行为一个实数,即依次为每一次操作$2$或操作$3$所得的结果(所有结果四舍五入保留$4$位小数)。

输入输出样例

输入 #1
5 5
1 5 4 2 3
2 1 4
3 1 5
1 1 1 1
1 2 2 -1
3 1 5
输出 #1
3.0000
2.0000
0.8000

解题报告

题意理解

  1. 区间加一个实数
  2. 区间求平均数
  3. 区间求方差

算法解析

首先我们来推倒公式。

先拿出方差公式
$$
S^2 = \frac{1}{n} * [(x_1 - \overline{x})^2 + (x_2 - \overline{x})^2 + …+(x_n - \overline{x})^2 ]
$$
根据完全平方公式:
$$
(a + b)^2 = a^2 + 2ab + b^2
$$
因此带入参数进去
$$
(x_1-\overline{x})^2=x_1^2+2x\overline{x}+\overline{x}^2
$$
接着处理公式
$$
S^2 = \frac{1}{n} * ({x_1}^2 - 2{x_1}\overline{x} + {\overline{x}^2} + {x_2}^2 - 2{x_2}\overline{x} + {\overline{x}^2} + … + {x_n}^2 - 2{x_n}\overline{x} + {\overline{x}^2})
$$
然后稍微整理一下
$$
S^2 = \frac{1}{n} * [({x_1}^2 + {x_2}^2 + … + {x_n}^2)-2\overline{x}(x_1 + x_2 + …+x_n) + n\overline{x}^2]
$$
然后我们通过平均数公式可得
$$
n\overline{x} = x_1 + x_2 + … + x_n
$$
将上面公式,导入方差公式
$$
S^2 = \frac{1}{n} * [({x_1}^2 + {x_2}^2 + … + {x_n}^2)-2n\overline{x}^2 + n\overline{x}^2]
$$
代入后
$$
S^2 = \frac{1}{n} * [({x_1}^2 + {x_2}^2 + … + {x_n}^2)-n\overline{x}^2]
$$
因此我们得出了最后的公式
$$
S^2 = \frac{({x_1}^2 + {x_2}^2 + … + {x_n}^2)}{n} - \overline{x}^2
$$
接着我们着重分析分子部分。
$$
x_1^2+x_2^2+\dots+x_k^2 \\
$$
现在所有数增加$b$,则
$$
(x_1+b)^2+(x_2+b)^2+\dots +(x_k+b)^2 \\
$$
然后定义一下
$$
令sum1=x_1+x_2+\dots+x_k \\
令sum2=x_1^2+x_2^2+\dots+x_k^2 \\
$$
由之前的完全平方公式可得:
$$
(x_i+b)^2=x_i^2+2 \times x_i \times b+b^2\\
$$
然后带入之前的部分
$$
(x_1^2+x_2^2+\dots+x_k^2)+2b \times (x_1+x_2+\dots+x_k)+(b^2 \times k) \\
$$
最后载入定义
$$
sum2+2b \times sum1+b^2 \times k \\
$$
我们终于终于终于将公式打完了。。。。。。

现在我们就可以通过,线段树来维护本题目了。

  1. 维护平方和
  2. 维护区间和

请注意,在这里,我们肯定是要开两个$Lazy$标记的;。

但是要记住平方和的懒惰标记,是绝对高于区间和的懒惰标记。

因为,通过公式可得,平方和的修改,是要先使用区间和的。

如果说先修改区间和,那么平方和的修改必然出现问题。


代码解释

#include <bits/stdc++.h>
using namespace std;
#define Lson rt<<1,l,mid
#define Rson rt<<1 | 1,mid+1,r
#define mid  (l+r>>1)
#define len  (r-l+1)
const int N=1e5+20;
int n,m;
struct node
{
    double lazy,sum;
} t1[N<<2],t2[N<<2];
double a[N];
inline void Push_up(int rt)
{
    t1[rt].sum=t1[rt<<1].sum+t1[rt<<1 | 1].sum;
    t2[rt].sum=t2[rt<<1].sum+t2[rt<<1 | 1].sum;
}
void build(int rt,int l,int r)
{
    if (l==r)
    {
        t1[rt].sum=a[l];
        t2[rt].sum=a[l]*a[l];
        return;
    }
    build(Lson);
    build(Rson);
    Push_up(rt);
}
inline void Push_down(int rt,int l,int r)
{
    if (!(t1[rt].lazy || t2[rt].lazy))
        return ;
    t2[rt<<1].lazy+=t2[rt].lazy;
    t2[rt<<1].sum+=t1[rt<<1].sum*(t2[rt].lazy*2)+(mid-l+1)*(t2[rt].lazy*t2[rt].lazy);
    t2[rt<<1 | 1].lazy+=t2[rt].lazy;
    t2[rt<<1 | 1].sum+=t1[rt<<1 | 1].sum*(t2[rt].lazy*2)+(r-mid)*(t2[rt].lazy*t2[rt].lazy);
    t2[rt].lazy=0;
    t1[rt<<1].lazy+=t1[rt].lazy;
    t1[rt<<1].sum+=(mid-l+1)*t1[rt].lazy;
    t1[rt<<1 | 1].lazy+=t1[rt].lazy;
    t1[rt<<1 | 1].sum+=(r-mid)*t1[rt].lazy;
    t1[rt].lazy=0;
}
double Query(int rt,int l,int r,int L,int R,int x)
{
    if (L<=l && r<=R)
        return x==1 ? t1[rt].sum:t2[rt].sum;
    double ans=0;
    Push_down(rt,l,r);
    if (L<=mid)
        ans+=Query(Lson,L,R,x);
    if (R>mid)
        ans+=Query(Rson,L,R,x);
    return ans;
}
void Update(int rt,int l,int r,int L,int R,double v)
{
    if (L<=l && r<=R)
    {
        t2[rt].lazy+=v;
        t2[rt].sum+=t1[rt].sum*(v*2)+len*(v*v);
        t1[rt].lazy+=v;
        t1[rt].sum+=len*v;
        return ;
    }
    Push_down(rt,l,r);
    if (L<=mid)
        Update(Lson,L,R,v);
    if (R>mid)
        Update(Rson,L,R,v);
    Push_up(rt);
}
inline void init()
{
//  freopen("data.in","r",stdin);
//  freopen("a.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
        scanf("%lf",&a[i]);
    build(1,1,n);
    while(m--)
    {
        int x,a,b;
        scanf("%d%d%d",&x,&a,&b);
        if (x==1)
        {
            double c;
            scanf("%lf",&c);
            Update(1,1,n,a,b,c);
        }
        if (x==2)
            printf("%.4lf\n",Query(1,1,n,a,b,1)/((b-a+1)*1.0));
        if (x==3)
        {
            double cnt=(b-a+1)*1.0;
            double ans=Query(1,1,n,a,b,2)/cnt,x_ba=Query(1,1,n,a,b,1)/cnt;
            double ans2=x_ba*x_ba;
            ans-=ans2;
            printf("%.4lf\n",ans);
        }
    }
}
signed main()
{
    init();
    return 0;
}

@墨染空 大佬之前点名的线段树区间平方修改来了




更好的阅读体验

题目概括

题目描述

Farmer John has arranged his N (1 ≤ N ≤ 5,000) cows in a row and many of them are facing forward, like good cows. Some of them are facing backward, though, and he needs them all to face forward to make his life perfect.

Fortunately, FJ recently bought an automatic cow turning machine. Since he purchased the discount model, it must be irrevocably preset to turn K (1 ≤ K ≤ N) cows at once, and it can only turn cows that are all standing next to each other in line. Each time the machine is used, it reverses the facing direction of a contiguous group of K cows in the line (one cannot use it on fewer than K cows, e.g., at the either end of the line of cows). Each cow remains in the same location as before, but ends up facing the opposite direction. A cow that starts out facing forward will be turned backward by the machine and vice-versa.

Because FJ must pick a single, never-changing value of K, please help him determine the minimum value of K that minimizes the number of operations required by the machine to make all the cows face forward. Also determine M, the minimum number of machine operations required to get all the cows facing forward using that value of K.

$N$头牛排成一列。每头牛或者向前或者向后。为了让所有牛都 面向前方,农夫每次可以将$K$头连续的牛转向,求操作的最少次数$M$和对应的最小$K$。

$B$表示当前奶牛往后看,$F$表示奶牛往前看。

样例输入输出格式

输入格式

Line 1: A single integer: N

Lines 2..N+1: Line i+1 contains a single character, F or B, indicating whether cow i is facing forward or backward.

输出格式

Line 1: Two space-separated integers: K and M

输入输出样例

输入 #1
7
B
B
F
B
F
B
B
输出 #1
3 3

数据范围

样例解释
For K = 3, the machine must be operated three times: turn cows (1,2,3), (3,4,5), and finally (5,6,7)
$$
1 \le N \le 5000 \\
1 \le K \le N \\
$$

解题报告

题意理解

$N$头牛排成一列。每头牛或者向前或者向后。为了让所有牛都 面向前方,农夫每次可以将$K$头连续的牛转向,求操作的最少次数$M$和对应的最小$K$。

算法解析

这道题目,其实就是一个贪心的题目。

我们知道,因为同一个点翻转两次相当于没有翻转,这就是异或的特性

每个点,只有正反之分,所以这就是01

然后设计贪心,如下所示:

从左到右对于出现的每一个$0$,然后我们就不得不翻转一次,从当前点开始的区间

但是,我们发现这个贪心,时间复杂度过大

从左到右枚举。$O(n)$

枚举区间长度。$O(n)$

区间翻转。$O(n)$

综上所述,复杂度为$O(n^3)$

我们怎么降维打击时间复杂度呢,我们思考一下。

区间翻转,然后又是类似于区间异或

我们似乎可以使用,差分,这个支持区间异或的算法。

于是,我们可以通过,差分优化本题目。


代码解析

#include <bits/stdc++.h>
using namespace std;
const int N=5010;
int n,a[N],sum[N],d[N],cnt,ans=1e9,pos,now,ok;
char c;
inline void init()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        getchar();
        c=getchar();
        c=='B' ? a[i]=0:a[i]=1;//设置
    }
}
inline void work()
{
    for(int k=1; k<=n; k++)
    {
        now=0,cnt=0,ok=1;
        memset(d,0,sizeof(d));
        for(int i=1; i<=n; i++)
        {
            now^=d[i];//异或
            if(!a[i]^now)//是时候要异或了,发现了反方向的奶牛
            {
                if(i+k-1>n)//不能超过最大长度
                {
                    ok=false;
                    break;
                }
                now^=1;//异或
                d[i+k]^=1;//同时在区间右端点异或,保证最后没有问题
                cnt++;
            }
        }
        if(ok && ans>cnt)//记得更新答案哦
            ans=cnt,pos=k;
    }
    printf("%d %d\n",pos,ans);
}
int main()
{
    init();
    work();
    return 0;
}



更好的阅读体验

题目概述

题目描述

Farmer John has noticed that his cows often move between nearby fields. Taking this into account, he wants to plant enough grass in each of his fields not only for the cows situated initially in that field, but also for cows visiting from nearby fields. Specifically, FJ’s farm consists of N fields (1 <= N <= 100,000), where some pairs of fields are connected with bi-directional trails (N-1 of them in total). FJ has designed the farm so that between any two fields i and j, there is a unique path made up of trails connecting between i and j. Field i is home to C(i) cows, although cows sometimes move to a different field by crossing up to K trails (1 <= K <= 20). FJ wants to plant enough grass in each field i to feed the maximum number of cows, M(i), that could possibly end up in that field – that is, the number of cows that can potentially reach field i by following at most K trails. Given the structure of FJ’s farm and the value of C(i) for each field i, please help FJ compute M(i) for every field i.
给你一棵 $n$ 个点的树,点带权,对于每个节点求出距离它不超过 $k$ 的所有节点权值和 $m_i$。

输入输出格式

输入格式

* Line 1: Two space-separated integers, N and K. * Lines 2..N: Each line contains two space-separated integers, i and j (1 <= i,j <= N) indicating that fields i and j are directly connected by a trail. * Lines N+1..2N: Line N+i contains the integer C(i). (0 <= C(i) <= 1000)

第一行两个正整数 $n,k$。 接下来 $n-1$ 行,每行两个正整数 $u,v$,表示 $u,v$ 之间有一条边。

最后 $n$ 行,每行一个非负整数 $c_i$,表示点权。

输出格式

* Lines 1..N: Line i should contain the value of M(i).

输出 $n$ 行,第 $i$ 行一个整数表示 $m_i$。

输入输出样例

输入样例 #1
6 2 
5 1 
3 6 
2 4 
2 1 
3 2 
1 
2 
3 
4 
5 
6 
输出样例 #1
15 
21 
16 
10 
8 
11 

数据范围

样例解释
There are 6 fields, with trails connecting (5,1), (3,6), (2,4), (2,1), and (3,2). Field i has C(i) = i cows. Field 1 has M(1) = 15 cows within a distance of 2 trails, etc.

对于 $100\%$ 的数据:$1 \le n \le 10^5$,$1 \le k \le 20$,$0 \le c_i \le 1000$

解题报告

题意理解

给你一棵 $n$ 个点的树,点带权,对于每个节点求出距离它不超过 $k$ 的所有节点权值和 $m_i$。

算法解析

  1. 树形结构
  2. 统计一定距离的点权和
  3. 树上节点特别多,基本上要线性复杂度
  4. 程序员的第六感

综上所述,我们得知这道题目需要使用,树形DP算法。

然后我们不难设计出,状态表示
$$
f[i][j]表示,节点i的子树中,离它距离为j的奶牛总数
$$
因此,我们不难发现,在这个状态表示中,状态转移,只会从儿子节点中转移过来。

利用儿子节点,更新父亲节点。
$$
f[i][j]=\sum{f[k][j-1]} \\
k为i的儿子节点,j-1是因为儿子到父亲距离为1
$$
但是,题目并没有如此简单。

在本题中,对于一个树上节点,他可以被那些节点转移过来呢

  1. 子辈节点(儿子,子树,兄弟的子树)
  2. 同辈节点(兄弟)
  3. 祖辈节点(父亲,祖先)

对于,子辈,同辈,这些节点的转移,显然都是满足,树形DP的自下而上的转移方式。

但是,祖辈节点们,可就是完全违背,我们树形DP的转移方式。

怎么办?

我们不妨,再来一次转移,而且本次转移,自上而下

因此,我们利用父亲节点,更新儿子节点
$$
f[i][j]=\sum{f[S][j-1]} \\
s为i的父亲节点,同样j-1,是因为儿子到父亲距离为1
$$
那么这里的
$$
f[S][j-1]包含了哪些节点呢?
$$
我们根据这张图片,分析一波

1710821-20191112201227363-371655160.png

父亲的转移,让我们的同辈节点,和同辈的儿子节点都累加了。

此时,我们发现

  1. 子辈节点,多。
  2. 同辈节点,刚好
  3. 父辈节点,刚好

我们发现,$x$的距离为$2$的点,包含到k距离为$1$的$k$的儿子们.

而这些点位于$k$的子树中的点已经在第一次转移,加入到里面去了。

因此,我们不得不,容斥原理,处理多余的子辈节点

推到出来,就是
$$
f[S][j]-f[x][j-2] \\
减去自己多余的子辈节点,S是x的父亲节点,y是x的儿子节点。 \\
j-1是S到x,(j-1)-1是S到y
$$


代码解析

#include <bits/stdc++.h>
using namespace std;
const int N=110000,K=21;
int n,k,a[N],f[N][K],deep[N];
vector<int> g[N];
void dfs(int x,int s)
{
    deep[x]=deep[s]+1;
    for(int y:g[x])
    {
        if (y==s)
            continue;
        dfs(y,x);
        for(int p=1; p<=k; p++)
            f[x][p]+=f[y][p-1];
    }
}
void dfs2(int x)
{
    for(int y:g[x])
    {
        if (deep[y]<=deep[x])
            continue;
        for(int p=k; p>=2; p--)
            f[y][p]-=f[y][p-2];
        for(int p=1; p<=k; p++)
            f[y][p]+=f[x][p-1];
        dfs2(y);
    }
}
inline void init()
{
    scanf("%d%d",&n,&k);
    for(int i=1; i<n; i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for(int i=1; i<=n; i++)
        scanf("%d",&f[i][0]);
    dfs(1,0);
    dfs2(1);
    for(int i=1; i<=n; i++)
    {
        int ans=0;
        for(int j=0; j<=k; j++)
            ans+=f[i][j];
        printf("%d\n",ans);
    }
}
signed main()
{
    init();
    return 0;
}