头像

秦淮岸灯火阑珊

yxc粉丝后援会。 QQ:862062587




离线:23小时前


新鲜事 原文

Enjoy OI


新鲜事 原文

希望明天不自闭


新鲜事 原文

成功在你wing关注了你郡的大佬!!!


新鲜事 原文

CSP2020 RP++


新鲜事 原文

好想写题解,可惜肚子里没有墨水,脑子里没有思路。


新鲜事 原文

1024节快乐,祝各位收割Offer或者CSP


新鲜事 原文

原来上了新功能关注了!



更好的阅读体验

C. 洗

小S有一个$n$个节点的二叉树。每个节点上有一个权值。节点从$1$开始编号。

现在,小S打算把这个二叉树改造成一个二叉排序树。二叉排序树的定义是,对于每个节点,它的权值比它左儿子的权值要大,但是比右儿子要小。

现在,他想要修改某些节点的权值,使得它成为一个二叉排序树。请问最小的修改次数是多少。

输入格式

第一行一个整数$n$。

接下来一行$n$个数,第$i$个表示$i$号节点的权值。

接下来 $n - 1$行,每行两个非负整数f, x,第$i$行描述结点$i + 1$的父亲编号$f$,以及父子关系$x$,($x = 0$ 表示$i + 1$为左儿子,$x = 1$表示$i + 1$为右儿子)。

保证一号点一定是全树的根。

输出格式

一行一个整数,表示最小修改次数。

样例

样例一

input

3
2 2 2
1 0
1 1

output

2

约定与限制

对于$20\%$ 的数据,满足 $ n \le 10,a_i\le 100$。

对于$40\%$ 的数据,满足 $n \le 100,a_i\le 200$。

对于$60\%$ 的数据,满足 $n\le 2000$。

对于$100\%$ 的数据 ,满足 $1 \le n \le 10^5,a_i< 2^{31}$ 。

时间限制:1s

空间限制:512MB

解题报告

$100pts$思路

这道题目,题目给我们一个关键信息,就是要把二叉树变成合法的二叉排序树。

二叉排序树,具有的性质,就是中序遍历后的序列,具有严格单调递增的性质。

既然如此,我们为什么不把这题的结构,通过DFS,进行中序遍历,从树结构变成线性结构

此时,我们的题面,改成了,在一个长度为$n$的序列,修改尽量少的点的值,使得整个序列严格单调递增

那么此时,我们来观察一组数据.

1 4 2 5 7

我们发现,在这里.

1,5,7

并不需要动,而

4 2

应该改成

2 3

使得最终序列为

1 2 3 5 7

那么根据上面的例子,我们发现了什么。

我们在这个序列里面,需要修改的数总数,就是序列长度减去不满足不下降子序列的数。

而这里,我们的不下降子序列的定义,却有所不同。

原序列有两个点,分别为$i,j$,且此时满足$i < j$

那么如果说,这两个点要在不下降子序列中,必须满足

$$
s[j]-s[i] \ge j-i
$$

否则这两个数,中间无法放置其他数。(若$i,j$紧靠,满足上面性质)

无法构造成为合法序列。

然后我们把不等式可以转换为:

$$
s[j]-j \ge s[i]-i
$$

因此所谓的不下降子序列,其实就是指的是,不用修改值的数列,因为他们已经满足了单调性质,改了没有任何用处。

而其他不满足的,都可以通过自身修改,使得整个序列最终成为严格单调递增的序列。


代码解析

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+20;
int n,a[N],f[N],cnt,ans,s[N],t[N][2];
inline void dfs(int x)//中序遍历
{
    if (t[x][0])//先遍历左儿子
        dfs(t[x][0]);
    s[++cnt]=a[x];//中序遍历,计算DFS序
    if (t[x][1])//最后遍历右儿子
        dfs(t[x][1]);
}
inline void init()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
        scanf("%d",&a[i]);
    for(int i=2; i<=n; i++)
    {
        int f,x;
        scanf("%d%d",&f,&x);
        if (x==1)//右儿子最后遍历
            t[f][1]=i;
        else//左儿子最先遍历
            t[f][0]=i;
    }
}
inline void work()
{
    for(int i=1; i<=n; i++)//不等式变形
        s[i]-=i;
    f[ans=1]=s[1];
    for(int i=2; i<=n; i++)//求解不下降子序列
        if (s[i]>=f[ans])
            f[++ans]=s[i];
        else
            f[upper_bound(f+1,f+1+ans,s[i])-f]=s[i];
    printf("%d\n",n-ans);
}
signed main()
{
    init();
    dfs(1);
    work();
    return 0;
}



更好的阅读体验

D. 铁路

小S有一个长度为$n$的序列。

一个区间$[L,R]$是好的,当且仅当存在$k\in [L,R]$

使得对于任意的$i\in [L,R]$,$a_k\ |\ a_i$。

现在,小S想要知道,最长的好的区间是多少,并且这些区间是什么。

输入格式

第一行一个整数$n$。

接下来一行$n$个数,第$i$个表示$a_i$。

输出格式

第一行两个数,$m$和$len$分别表示最长的好区间个数以及这些区间的$R-L$。

接下来一行$m$个数,按升序输出每个最长的好区间的左端点。

样例

样例一

input

5
4 6 9 3 6

output

1 3
2

样例二

input

5
2 3 5 7 11

output

5 0
1 2 3 4 5

约定与限制

对于$30\%$ 的数据,满足 $ n \le 30,1\le a_i\le 32$。

对于$60\%$ 的数据,满足 $n \le 3000,1\le a_i\le 1024$。

对于$80\%$ 的数据,满足 $n\le 300000,1\le a_i\le 1048576$。

对于$100\%$ 的数据 ,满足 $1 \le n \le 5\times 10^5,1\le a_i< 2^{31}$ 。

时间限制:1s

空间限制:512MB

解题报告

题意理解

寻找一段区间,要求这段区间满足:

  1. 至少存在一个位置$k$,$a_k$可以整除这个区间所有的数$a_i$ 。
  2. 区间长度尽量长

这样的区间有很多个,因此题目要求

  1. 输出有多少个合法区间
  2. 这些合法区间的左端点。

$60pts$解析

拿到这道题目,我们发现,$60pts$的$n$取值范围很小,可以忍受$O(n^2)$的时间复杂度。

因此我们来对本题,进行初步分析。

首先我们发现,这个$k$一定在这个区间内,而且区间内,所有的数都是他的倍数

那么,如果说,此时我确定了$k$这个坐标,那么,这个最长区间其实是可以确定下来了。

我们不妨设:

$$
区间为[l,r]
$$

那么根据题意

$$
[l,k-1]的数都是k的倍数 \\
[k+1,r]的数都是k的倍数
$$

我们可以得出思路。

  1. 首先命令$l=k$
  2. 如果$a_{l-1}$是$k$的倍数,那么$l=l-1$,否则此时$l$为最小左区间
  3. 同理,命令$r=k$
  4. 如果$a_{r+1}$是$k$的倍数,那么$r=r+1$,否则此时$r$为最大右区间

代码如下

//60~100pts & C++11
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+20;
int a[N],s[N],n,m;
vector<int> g[N];
inline void init()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
        scanf("%d",&a[i]);
    int ans=0;
    for(int i=1; i<=n; i++)
    {
        int l=i,r=i,ans1=0;//忽略位置k,所以ans1=0
        while((l-1) && a[l-1]%a[i]==0)//左区间拓展
            l--,ans1++;
        while((r+1)<=n && a[r+1]%a[i]==0)//右区间拓展
            r++,ans1++;
        if (g[ans1].empty() ||  l>g[ans1].back())
            g[ans1].push_back(l);//长度为ans1的区间,记录左区间点
        ans=max(ans,ans1);//算出最长好区间
    }
    printf("%d %d\n",g[ans].size(),ans);
    for(int s:g[ans])
        printf("%d ",s);
}
signed main()
{
//  freopen("ff.in","r",stdin);
    init();
    return 0;
}

期望得分$60pts$,实际得分$100pts$

实际运行时间,是标程$\frac{1}{10}$

原因:数据太水了


$100pts$解析

我们发现,在这里的话,其实具有单调性质

如果说有一个区间$[l,r]$满足条件。

假如说$a \ge l,b \le r,a \le k \le b$

那么$[a,b]$一定满足条件.

因此区间满足条件,那么包含$k$的区间,肯定也满足条件。

这样的话,我们为什么不二分$R-L$,这个答案呢?

因为

$$
R-L=(R-L+1)-1=Len-1 \quad Len为区间长度
$$

既然如此,那么现在的当务之急就是,如何判断存在这样的一个区间呢?

如果说

$$
gcd([L,R])=min([L,R])
$$

这里的意思是,一个区间的最大公约数$=$一个区间的最小数

那么这个区间肯定是合法的,反之必然。

两者互为充要条件

这是为什么?


充分性证明

命题:区间合法是性质满足的充分条件

因为,我们发现,$a_k$一定是这个区间中的最小数

否则,如果存在一个数,比他小,那么无法满足整除性质

所以区间最小数必然是$a_k$

同样的,为什么最大公约数也必须是$a_k$呢?

因为,如果$a_k$是最小数,而最大公约数不可能大于最小数,只能小于等于它。

其次,又因为此时区间是合法的,所有数都是他的倍数,所以最大公约数是它。

所以充要性成立


必要性证明

命题:区间合法是性质满足的必要条件

因为:

$$
gcd([L,R])=min([L,R])
$$

区间所有数他们的最大公约数是$s$

然后,此时区间中存在一个最小数的值等于$s$

那么也就是说,在区间中,存在一个数,其他数都是它的倍数。

那么这不就是合法区间的定义吗?

所以必要性成立!


现在我们考虑,如何实现,快速求区间最大公约数和区间最小值。

我们观察到,这里面所有数都是固定不变的,也就是数据静态

所以,我们可以使用由倍增处理的$ST$表,来完成本题。

当然你也可以使用线段树暴力完成。

代码解析

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+20;
int f_gcd[N][21],f_min[N][21],n,a[N];
vector<int> g[N];//g[x]存储R-L=x的区间左端点
int gcd(int a,int b)
{
    return !b?a:gcd(b,a%b);
}
inline void pre()//倍增预处理
{
    for(int i=1; i<=n; i++)//0,在这里表示[i,i],而不是[i,i+1]
        f_gcd[i][0]=f_min[i][0]=a[i];
    for(int j=1; j<=20; j++)
        for(int i=1; i<=n; i++)
            if (i+(1<<j)-1<=n)
            {
                f_gcd[i][j]=gcd(f_gcd[i][j-1],f_gcd[i+(1<<j-1)][j-1]);
                f_min[i][j]=min(f_min[i][j-1],f_min[i+(1<<j-1)][j-1]);
            }
}
inline void init()
{
//  freopen("ff.in","r",stdin);
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
        scanf("%d",&a[i]);
}
inline int Query_Min(int l,int r)//查询区间[l,r]的最小值,ST表做法
{
    int k=log2(r-l+1);
    return min(f_min[l][k],f_min[r-(1<<k)+1][k]);
}
inline int Query_Gcd(int l,int r)//查询区间[l,r]的最大公约数,ST表做法
{
    int k=log2(r-l+1);
    return gcd(f_gcd[l][k],f_gcd[r-(1<<k)+1][k]);
}
inline int check(int x)
{
    for(int l=1; l+x<=n; l++)//枚举左端点
    {
        int r=l+x;//枚举右端点
        if (Query_Min(l,r)==Query_Gcd(l,r))//此时最小值=最大公约数,说明存在这个k
            g[x].push_back(l);
    }
    return !g[x].empty();//是否有合法区间
}
inline void work()
{
    int l=-1,r=n-1;//开-1,是为了保证mid=0可以取到
    while(l<r)//这里二分R-L,也就是区间长度-1
    {
        int mid=l+r+1>>1;
        if (check(mid))//判断是否存在该区间长度
            l=mid;
        else
            r=mid-1;
    }
    printf("%d %d\n",g[r].size(),r);
    for(int s:g[r])
        printf("%d ",s);
}
signed main()
{
    init();
    pre();
    work();
    return 0;
}



更好的阅读体验

C. 自闭的游戏

小S在玩一个自闭的游戏。
有一个骰子,这个骰子有$m$个面分别写着 $1\cdots m$
并且投掷时每面朝上的概率相同
现在,小S投了这个骰子$n$次,并且告诉小T点数$v$至少出现了一次。
小T需要猜测一个正整数$sum$,表示她猜测的这$n$次骰子的点数之和是多少。
现在,他想要知道玩家的正确率有多少呢?

输入格式

一行四个正整数,分别表示$n,m,v,sum$。

输出格式

一行一个实数,表示猜对的概率。你的答案被认为是正确的,当且仅当绝对或相对精度误差$\le 10^{-6}$。

样例

样例一

input

2 6 6 12

output

0.09090909

样例二

input

2 3 2 4

output

0.20000000

约定与限制

对于$10\%$ 的数据,满足 $1 \le n \le 1$。
对于$40\%$ 的数据,满足 $1 \le n,m \le 20$。
对于$100\%$ 的数据 ,满足 $1 \le n,m \le 50$ ,$1\le v\le m$,$1\le sum\le n\times m$。

时间限制:1s
空间限制:128MB


解题报告

题意理解

有$n$个点,每个点的取值范围是$[1,n]$,已知在这$n$个点中,至少有一个点的值为$v$,将这个$n$个点的和累加,得到值$x$
问:当$x=sum$的时候的取数方案数占总合法取数方案数的比例?

$40pts$思路

我们可以使用暴力搜索,算出每一种方案数,然后再统计合法方案。

代码略


$100pts$思路

我们观察这道题目,发现以下几种性质。

  1. 题目并不关心我们的具体方案,只需要方案数(属性为统计)
  2. 至少有一个数是$v$ (限制条件)
  3. 前面取什么数字,和后面取什么数字并没有任何影响。(无后效性)

那么上面这些性质,就可以保证,这道题目可以使用动态规划算法。

我们接着讨论,如何描述这个状态。

我们发现,这道题目具有明显的线性性质

我们可以把,每一次甩骰子,作为我们的阶段。

$$
f[i] \quad 表示此时选到了第i个数
$$

接着题目关心,我们这些数的和。

$$
f[i][k] \quad 表示此时选到了第i个数,这些数的和是k
$$

接着题目的限制条件是,这些数中是否至少有一个数是$v$

$$
f[i][k][0/1] \quad 表示此时选到了第i个数,这些数的和是k \\
0表示没有一个v,1表示至少有一个v
$$

那么状态转移方程是什么呢?自然就是我们的背包动态规划的模样了。

假如说,此时我们第$i$个数,他的值是$j$

f[i][k][0]+=f[i-1][k-j][0]
//到目前都没有出现v,那么推来的状态,也不可以出现v 
if (j!=v)//当前选择元素不是v
    f[i][k][1]+=f[i-1][k-j][0]
//现在已经出现v了,而本次没有选择v,那么推来的状态,必须出现过v
if (j==v)
    f[i][k][1]+=f[i-1][k-j][0]+f[i-1][k-j][1];
//因为本次选择了v,之前是否选择v没有限制

代码解析

#include <bits/stdc++.h>
using namespace std;
const int N=52;
int n,m,v,sum;
double f[N][N*N][2];
inline void init()
{
    scanf("%d%d%d%d",&n,&m,&v,&sum);
    f[0][0][0]=1;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            for(int k=max(i,j); k<=i*m; k++)
            {
                f[i][k][j==v]+=f[i-1][k-j][0];
                f[i][k][1]+=f[i-1][k-j][1];
                //这里代码和上面解释是一样的,只不过是不同的写法而已
            }
    double ans=0;
    for(int j=1; j<=n*m; j++)
        ans+=f[n][j][1];//合法方案,要求是必须选择v的
    printf("%.8lf\n",f[n][sum][1]/ans);//保证精度
}
signed main()
{
    init();
    return 0;
}