头像

人间温柔




离线:1天前


最近来访(79)
用户头像
十指相扣
用户头像
ctOS
用户头像
封禁用户
用户头像
lg-jyy
用户头像
唇齿相依
用户头像
AcWing2AK
用户头像
dp咋学啊
用户头像
四合院院士
用户头像
LeoDerek
用户头像
你一笑便是人间温柔
用户头像
whale77
用户头像
一朵奔涌的浪花
用户头像
zeng6666jian
用户头像
人间失格_1
用户头像
11111118
用户头像
ysc
用户头像
朝朝辞暮
用户头像
蒟蒻果冻
用户头像
wt20
用户头像
PseudorandomGenerators


01背包能不能输出哪些物品被选中了




题目要求区间 $[x,y]$ 和 $[m,n]$ 一模一样,我就考虑到了并查集。

$\forall\ i\in [x,y]$ 以及 $i$ 在 $[m,n]$ 中对应的格子,我们把这两个格子连边,这样经过若干次连便之后,凡是处在同一个联通块中的格子,取的数字必须是相等的。

如果目前得到了 $k$ 个连通块,则答案就等于 $9\times 10^{k-1}$。有 $1$ 在的那个连通块只能取 $1 \sim 9$ 这九个数字,而其他的 $k-1$ 个连通块可以取 $0\sim 10$ 这十个数字,根据乘法原理便可证明上式的正确性。

但是看一看数据范围,我们发现如果一条边一条边的连,早就 $TLE$ 了。

利用倍增的思想,我们考虑区间并查集。$f[i][j]$ 表示的含义是:以 $i$ 为左端点,长度为 $2^j$ 的一个区间。为了方便描述,我们令 $x=1,y=13,m=20,n=32$。这样两个区间,可以按照下图进行分割:

$merge$ 是并查集中的连边操作函数,那么我们在分割完区间之后需要进行的操作是:

merge{f[1][3],f[20][3]};
merge{f[9][2],f[28][2]};
merge{f[13][0],f[32][0]};

然后利用并查集统计答案。

记得要开 $long\ long$ 哦!

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

const int mod=1e9+7;
const int maxn=100005;

long long ans=1;
int n,m;
int f[maxn][20]; //f[i][j]:[i,j] --> id,他表示的含义是 [i,j] 区间所对应的编号 
int id;          //用于给区间编号 
int fa[maxn*20];
int s[maxn*20]; //s[i]:编号为 i 的区间的左端点 

void build(){
    for(int j=0;j<=log2(n);j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            f[i][j]=++id;
            fa[id]=id;
            s[id]=i;
        }
    }
}

int find(int x){
    if(x==fa[x]) return x;
    return fa[x]=find(fa[x]);
}

void merge(int l1,int l2,int k){
    int p=find(f[l1][k]),q=find(f[l2][k]);
    if(p>q){
        swap(p,q);
    }
    fa[q]=p;
}

int main(){
    cin>>n>>m;
    build();
    for(int i=1;i<=m;i++){
        int l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        for(int k=log2(r1-l1+1);k>=0;k--){
            if(l1+(1<<k)-1<=r1){
                merge(l1,l2,k);  //合并区间 [l1,k] & [l2,k]
                l1+=(1<<k);
                l2+=(1<<k);
            }
        }
    }
    for(int k=log2(n);k>0;k--){
        for(int i=1;i+(1<<k)-1<=n;i++){
            int pa=find(f[i][k]);
            int spa=s[pa];      //pa 区间的左端点 
            merge(spa,i,k-1);
            merge(spa+(1<<k-1),i+(1<<k-1),k-1);
        }
    }
    for(int i=2;i<=n;i++){          //注意 i 从 2 开始,因为 f[1][0] 代表的是 1 所在的那个连通块,而这个连通块是需要乘以 9 的,并不需要乘以 10,所以会放在输出的时候特殊处理 
        if(f[i][0]==find(f[i][0])){ //这个判断结果如果为真,那么就是找到了一个连通块,ans需要乘以 10 
            ans=ans*10ll%mod;
        }
    }
    cout<<ans*9%mod<<endl;
    return 0;
}



想问一下,treap 的旋转是如何进行的,最好是能够用动图直观展示,谢谢大佬!




人间温柔
1个月前

为了方便分析问题,我们假设 $n=3$。数字 $1\sim 3$ 总共有 $n!=6$ 种排列。则:
$$
k=1时,有这几种排列情况\begin{cases}
1,2,3
\end{cases}
$$
$$
k=1时,有这几种排列情况\begin{cases}
1,3,2\
2,1,3
\end{cases}
$$
$$
k=2时,有这几种排列情况\begin{cases}
2,3,1\
3,1,2
\end{cases}
$$
$$
k=3时,有这几种排列情况\begin{cases}
3,2,1
\end{cases}
$$
以 $k=2,k-1=1$ 两个例子来举例,画出如下的图:
图1.png
同行比较的话,可以发现,欲使逆序对的数量减少 $1$,只需要把 $n$ 这个数与它后一个数交换位置即可。反过来也一样,欲使逆序对的数量增加 $1$,只需要把 $n$ 这个数与它前一个数交换位置即可。也就是说红色集合圈与绿色集合圈实现了一个相互映射:
a.png

这又引出了另一个问题:如果 $n$ 在第一位,或者最后一位,那它就无法与它后一个数或者前一个数交换位置。

因此,$n$ 在第一位,或者最后一位的情况时无法参与到映射中的。根据数学知识,$n$ 在第一位是包含于红色集合圈的,$n$ 在最后一位也是包含于绿色集合圈的,这两种情况需要排除,也就是下图中紫色蓝色集合圈不参与映射:
a.png

现在有了这些分析,我们开始推到递推方程。假设 $f[n][k]$ 代表的含义是 $1,2,\ldots n$ 的所有排列中,逆序对数量等于 $k$ 的方案数。

在左图中,真正参与的是红色集合圈减去紫色集合圈,也就是 $f[n][k]-f[n-1][k]$。因为 $n$ 是最大数,放在最后一位对逆序对的贡献是 $0$,也就是说我们只需要满足 $n$ 之前由 $1,2,\ldots n-1$ 组成的排列中逆序对的数量等于 $k$,所以紫色集合圈就是 $f[n-1][k]$。

同理,右图中真正参与的是绿色集合圈减去蓝色集合圈,也就是 $f[n][k-1]-f[n-1][k-n]$。当 $n$ 在第一位时,它大于后面所有的 $n-1$ 个数,所以对逆序对数量的贡献是 $n-1$,也就是说我们只需要满足 $n$ 之前由 $1,2,\ldots n-1$ 组成的排列中逆序对的数量等于 $k-1-(n-1)=k-n$即可,所以蓝色集合圈就是 $f[n-1][k-n]$。

既然两者数量上相等,所以等式 $f[n][k]-f[n-1][k]=f[n][k-1]-f[n-1][k-n]$ 就成立,通过移项,就是:
$$
f[n][k]=f[n][k-1]+f[n-1][k]-f[n-1][k-n]
$$
这就是最后的递推方程。

$AC$ 代码如下:

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

const int mod=1000000007;
const int maxn=1005;
const int maxk=10005;

int n,k;
bool mem_flag[maxn][maxk];
int mem[maxn][maxk];

long long f(int n,int k){
    if(k<0) return 0;
    if(n==0 && k==0) return 1;
    if(n==0 && k>0) return 0;
    if(mem_flag[n][k]) return mem[n][k];

    long long ret=f(n-1,k)+f(n,k-1)-f(n-1,k-n);
    ret%=mod;
    mem_flag[n][k]=true;
    return mem[n][k]=ret;
}

int main(){
    scanf("%d%d",&n,&k);
    printf("%d\n",(f(n,k)+mod)%mod);
    return 0;
}


新鲜事 原文

人间温柔
2个月前
大半夜的,出门核酸,人麻了。。。



人间温柔
4个月前

学习笔记目录
有任何问题,欢迎私信/评论。
码字不易,求点赞啦~

网络流的基本概念

网络

网络指的是一张有向图。图中每一条边都有一个权值 $c(u,v)$ ,叫做边的容量

图中还有两个特殊的点:源点 $s$ 与汇点 $t$。

流量

定义 $f(u,v)$ 是一条边 $(u,v)$ 的流量,那么 $f(u,v)$ 满足如下性质:

  • 一条边的流量不得大于它的容量,$f(u,v)\leq c(u,v)$。
  • 每条边的流量与其相反边的流量之和为 $0$,$f(u,v)+f(v,u)=0$。
  • 从源点流出的流量等于汇点流入的流量。$\sum_{(u,x)\in E}f(u,x)=\sum_{(x,v)\in E}f(x,v)$。

可以把流量理解为城市排水系统中的水流。



新鲜事 原文

人间温柔
5个月前
不管夜晚多么黑暗,黎明终将到来。坚持住,只要你敢尝试,没有什么不可能的。


新鲜事 原文

人间温柔
5个月前
现在想去坐做做hdu的题,但是vjudge打不开了,怎么办?


新鲜事 原文

人间温柔
5个月前
明天情人节,和我有关系嘛?



人间温柔
6个月前

本题 我的主要思路如下:

假设完成第 $i$ 个运输任务耗时 $t_i$ ,然后二分答案,假设当前二分得到的答案是 $x$,如果 $t_i<=x$ 则无需考虑,对于 $t_i>x$ 的运输计划 $i$,虫洞必须要在这条路径上,才有可能使得最后的耗时小于等于 $x$。也就是对于所有 $t_i > x$ 的路径,标记每条边经过的次数。

最后,从交集里面选最长的边 $l$,如果能满足所有 $t_i-l<=x$,说明 $x$ 可行,否则 $x$ 不可行。

现在蒟蒻已经打出了大部分代码,但唯独不太会标记边经过的次数。想请教一下大佬,这标记该怎么实现呢?(暴力除外)