首页
留言
统计
关于
Search
1
Hello World!我出生了!
387 阅读
2
成长视频合集
335 阅读
3
01在16个月时可以说出的字~
334 阅读
4
01成长趣事
332 阅读
5
写段代码测试一下博文效果
312 阅读
默认分类
01的成长日志
计算机科学
登录
Search
标签搜索
上海月赛
甲组
莫队算法
tang01
累计撰写
15
篇文章
累计收到
3
条评论
首页
栏目
默认分类
01的成长日志
计算机科学
页面
留言
统计
关于
搜索到
7
篇与
的结果
2024-07-05
2024年6月上海月赛甲组T3积木染色(五)题解
2024年6月上海月赛甲组T3积木染色(五)题解
2024年07月05日
87 阅读
0 评论
0 点赞
2023-08-25
2023年8月上海月赛甲组T1 不定方程
题目大意给定 $n$ 个整数 $ a_1,a_2, \cdots ,a_n $ 作为上界,再给定一个整数 $m$,请问方程$x_1 + x_2 + \cdots + x_n = m $有多少种不同的整数解且满足$\ 1\leq x_i\leq a_i$。由于解的数量可能很大,输出答案模$\ 1,000,000,007\ $的余数。算法思路假设不定方程无上限限制对于不定方程中变量 $x$ 我们可以想象它是一个盒子,$x = i$ 代表盒子里有 $i$ 个球。问题相当于你有 $m$ 个球要分给 $n$ 个盒子,不允许某个盒子是空的,方案数量有多少。我们可以使用插板法。插板法就是在 $n$ 个元素间的 $n-1$ 个空中插入若干个 $b$ 个板,可以把n个元素分成 $b+1$ 组的方法。$m$ 个球要分给 $n$ 个盒子则答案为组合数 $C_{m-1}^{n-1}$,即在 $m-1$ 个位置选 $n-1$ 个位置插入隔板的组合数。稍微扩展一下,有些时候允许某个盒子是空的,直接使用插板法并不可以。观察方程 $ x_1+x_2+ ... +x_n = m $ 可以变为$ (x_1+1)+(x_2+1)+ ... +(x_n+1) = m+n $进一步用 $y_i$ 替换 $x_i+1$ ,得到 $y_1+y_2+ ... +y_n = m+n$每个 $y_i$ 的正整数解对应一个 $x_i$ 的非负整数解。 增加 待分配的球后,再进行插板法即可,解数量为 $C_{m-1+n}^{n-1}$。再扩展一下,有些时候要求任意盒子里至少有 $i$ 个球,相当于给所有盒子先预置 $i$ 个球,减少待分配的球后,再进行插板法即可,解数量为 $C_{m-1-i*n}^{n-1}$。我们可以发现,无上限限制时,无论下限是增加还是减少,我们都可以使用插板法组合数直接求出问题的答案。方程有上限限制合法的方案数 = 全部方案数 - 非法方案数$\left|\bigcap_{i=1}^{n}S_i\right|=|U|-\left|\bigcup_{i=1}^n\overline{S_i}\right|$对于本题即是 满足上下限制条件解的数量 = 满足下限解的数量 - 不满足上限解的数量。满足下限解的数量我们可以使用插板法之前求出来,接下来我们重点去求不满足上限解的数量即可。到这一步我们就需要容斥原理来帮忙了。容斥原理设 $U$ 中元素有 $n$ 种不同的属性,而第 $i$ 种属性称为 $X_i$,拥有属性 $X_i$ 的 元素构成集合$ S_i$,那么$\begin{aligned}\left|\bigcup_{i=1}^{n}S_i\right|=&\sum_{i}|S_i|-\sum_{i<j}|S_i\cap S_j|+\sum_{i<j<k}|S_i\cap S_j\cap S_k|-\cdots\\&+(-1)^{m-1}\sum_{w_i<w_{i+1} }\left|\bigcap_{i=1}^{m}S_{w_i}\right|+\cdots+(-1)^{n-1}|S_1\cap\cdots\cap S_n|\end{aligned}$$\left|\bigcup_{i=1}^{n}S_i\right|=\sum_{m=1}^n(-1)^{m-1}\sum_{w_i<w_{i+1} }\left|\bigcap_{i=1}^mS_{w_i}\right|$可以使用数学归纳法和组合数来证明,感兴趣读者可自行查阅资料。对于本题 $\left|S_i\right|$ 是满足 $x_i$ 上下限制解的数量,$\left|\overline{S_i}\right|$ 是 $x_i \ge a_i+1$解的数量,注意下限问题我们前面讲过了,可以用组合数直接求出。我们要求所有非法解的数量,即$\left|\bigcup_{i=1}^{n}\overline{S_i}\right|$。根据容斥原理: $\left|\bigcup_{i=1}^{n}\overline{S_i}\right|=\sum_{m=1}^n(-1)^{m-1}\sum_{w_i<w_{i+1} }\left|\bigcap_{i=1}^m\overline{S_{w_i}}\right|$源代码分享#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll MOD = 1e9 + 7; ll a[25], n, m; ll f[25] = {1}, rvf[25]; ll rv(ll x){//(快速幂)费马小定理求乘法逆元 // x ^ (MOD - 2) ll res = 1; for(ll y = MOD - 2; y; y >>= 1){ if(y % 2) (res *= x) %= MOD; (x *= x) %= MOD; } return res; } ll C(ll x, ll y){ //乘法逆元计算组合数 if(x < y) return 0; ll res = 1; for(ll i = 1; i <= y; i++) (res *= x--) %= MOD; (res *= rvf[y]) %= MOD; return res; } int main(){ cin >> n >> m; for(int i = 1; i <= n; i++) cin >> a[i]; for(int i = 1; i <= n; i++) f[i] = f[i - 1] * i % MOD, rvf[i] = rv(f[i]); if(n == 1){ cout << (a[1] >= m); return 0; } ll ans = C(m - 1, n - 1);//隔板法,计算无上限制的解的数量。 for(ll k = 1; k < (1 << n); k++){//二进制枚举 ll cnt = 0, sum = 0; for(ll p = k, i = 1; p; p >>= 1, i++){ //若二进制第i位为1,让x_i值大于a[i]。 if(p & 1){ cnt++; sum += a[i]; } } ll res = C(m - sum - 1, n - 1); // 非法方案数,把sum个球现放入选定盒子里,再进行插板法,这样选定盒子肯定会超过其上限。 // cout << m - sum - 1 << ' ' << res << endl; if(cnt % 2) ans -= res; //容斥原理 - 奇数个不满足 else ans += res; // + 偶数个不满足 } cout << (ans % MOD + MOD) % MOD; return 0; }
2023年08月25日
234 阅读
0 评论
0 点赞
2023-08-04
2023年6月上海月赛甲组T3 方格计数题解
题目大意有一个 $n$行、$m$列的方格,每个格子上可以写 $0$ 或 $1$两种数字,一开始每个格子上都写着数字 $1$。小爱会进行 $k$ 轮反转操作,每轮游戏他会选择一块区域,左上角为$(x_1, y_1)$,右下角为 $(x_2, y_2)$,并将该区域内所有的数字反转(即原来为 $1$ 的反转为 $0$ ,原来为 $0$ 的反转为 $1$) 。请问, $k$ 轮过后,整个方格中仍为 $1$ 的方格的数量。数据范围$ 1 \le k \le 10^5 $$1 \le n,m,x_i,y_i \le 10^9$算法思路本题采用扫描线算法,扫描线需要使用一种叫做线段树的数据结构。为了更好的理解本题和阅读的连贯性,引用OI-WIKI关于扫描线算法的部分内容。引入 Atlantis 问题在二维坐标系上,给出多个矩形的左下以及右上坐标,求出所有矩形构成的图形的面积。根据图片可知总面积可以直接暴力即可求出面积,如果数据大了怎么办?这时就需要讲到扫描线算法。现在假设我们有一根线,从下往上开始扫描:如图所示,我们可以把整个矩形分成如图各个颜色不同的小矩形,那么这个小矩形的高就是我们扫过的距离,那么剩下了一个变量,那就是矩形的长一直在变化。我们的线段树就是为了维护矩形的长,我们给每一个矩形的上下边进行标记,下面的边标记为 1,上面的边标记为 -1,每遇到一个矩形时,我们知道了标记为 1 的边,我们就加进来这一条矩形的长,等到扫描到 -1 时,证明这一条边需要删除,就删去,利用 1 和 -1 可以轻松的到这种状态。还要注意这里的线段树维护的并不是线段的一个端点,而指的是一段区间。根据数据范围可能需要进行离散化或动态开点。本题与Atlantis区别Atlantis是计算面积而本题是计算方格数量,计算方法类似,但方格数量与线段长度在处理上还是有些区别的。Atlantis一段区间可以被多个矩形覆盖,被一个矩形覆盖和多个矩形覆盖效果一样。但方格计数不同,覆盖奇数次等于覆盖一次,偶数次等于没有覆盖。这个规律提示我们可以使用异或,奇偶性来完成题目。分享一下,我自己解决这两个问题方法。时间上并非最优,上海月赛测$400ms$左右,但很好理解。首先,把格子横坐标离散化。离散化后,若有$M$个不同的 $x$ 坐标值,分别对应原始值$raw(1),raw(2),raw(3),...,raw(M)$。扫描线至多被分成$M-1$段,其中第 $i \space (1\le i \le M-1)$ 段为区间$[raw(i),raw(i+1))$或$[raw(i),raw(i+1)-1]$。左闭右开我们不会重复统计端点的格子,且 $i$ 区间内部有$raw(i+1) - raw(i)$个方格。建立数组 $t$ ,用$t[i]$ 记录第 $i$ 段格子上写 $0$ 的格子数量,当然后面我们需用线段树维护 $t[i]$ 。若离散化后,某次更新$x_1=3 ,x_2=5$,需要更新区间 $3$ 与区间 $4$。$x_2$ 这个位置方格还有没计数啊。这个问题思考了一段时间。我们可再建立数组 $w$,用 $w[x]$ 记录离散化后 $x$ 这个点被操作次数。线段树同时利用数组 $t$ 和 $w$ 就可以计算出闭区间写 $0$ 的格子的数量。void changeSeg(int p, int l, int r, int x) { if (l <= t[p].l && t[p].r <= r) { t[p].add += x;//加标记 t[p].len = a[t[p].r+1] - a[t[p].l] - t[p].len;//0,1数量互换 return; } spread(p); int mid = (t[p].l+t[p].r)>>1; if (l <= mid) changeSeg(p<<1, l, r, x); if (mid < r) changeSeg(p<<1|1, l, r, x); t[p].len = t[p<<1].len+t[p<<1|1].len; }void changePoint(int p,int l,int r,int x){ if (l <= t[p].l && t[p].r <= r) {//包含这个端点的区间根据w[l]数值进行更新 if((t[p].add + w[l] + x) & 1) t[p].len++; else t[p].len--; w[l] += x; return; } spread(p); int mid = (t[p].l+t[p].r)>>1; if (l <= mid) changePoint(p<<1, l, r, x); if (mid < r) changePoint(p<<1|1, l, r, x); t[p].len = t[p<<1].len+t[p<<1|1].len; } 注意这两个函数很像,为了节约代码行数可以合并成为一个函数,但会导致思路不清晰。for (int i = 1; i < k; ++i) { int l = query(e[i].x1),r = query(e[i].x2); if(r > l) changeSeg(1, l, r-1, e[i].k);//区间更新 changePoint(1, r, r, e[i].k);//单点更新 if(e[i+1].y != e[i].y){ ans += 1ll * t[1].len * (e[i+1].y - e[i].y); } }总体来说就是更新两次,先更新线段树维护区间,再更新端点,这样可确保不多不少的统计。若 $l,r$ 相等则只进行单点更新即可。{dotted startColor="#ff6c6c" endColor="#1989fa"/}更新一下,一直以来对changePoint不顺眼,再想能不能只保留一个changeSeg。如果只保留changeSeg函数,那必须让changeSeg函数可以处理单点更新。猛然发现,上述区间更新方法保持不变,一个点也是可以构成区间,只需让起点不变,终点加一,这样更新时$x2 > x1$。举例若离散化后,某次更新$x_1=3 ,x_2=4$。需要更新区间为$3$,涉及格子数量为$[raw(3),raw(4)-1]$,假设此时是单点更新,那么$raw(4)$就会恰好比$raw(3)$大$1$,就是更新$[raw(3),raw(3)]$这个点。for (int i = 1; i <= k; ++i) { int x1, y1, x2, y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); e[(i<<1)-1] = (edge){y1, x1, x2+1, 1}; e[i<<1] = (edge){y2+1, x1, x2+1, -1}; //加入线段 a[(i<<1)-1] = x1, a[i<<1] = x2+1; }如此时间会更加优秀~~
2023年08月04日
258 阅读
0 评论
0 点赞
2023-08-01
用平衡树求解约瑟夫问题
题目大意 $n\ $个人编号为$\ 1\ $到$\ n$,按照编号围成一圈。从$\ 1\ $号开始,按照循序依次数数,第一次跳过$\ a_1\ $个人后停止,停止时指向的下一个人出局,然后继续数数,第二次跳过的人数为$\ a_2$,以此类推,直到所有人出局为止。给定$\ a_1,a_2,...,a_n$,请依次输出出局人员的编号。数据范围对于$\ 30\%\ $的数据,$\ n\leq 1000$对于$\ 60\%\ $的数据,$\ n\leq 50000$对于$\ 100\%\ $的数据,$\ 1\leq n\leq 500,000$,$0\leq a_i< n$算法思路自从掌握FHQ Treap之后,发现好多题目都可以用它来做。像这道题目简直就是平衡树裸题。会写平衡时直接就AC。除去平衡树代码,main函数代码非常简练。int main(){ int n,pos=1; n = read(); build(n); //笛卡尔建树 O(n) //for(int i=1;i<=n;i++) insert(i,i); //O(nlogn) while(fhq[root].size){ pos += read(); pos = (pos - 1) % fhq[root].size + 1; //O(1) 计算位置 write(remove(pos));//O(logn) 删除 putchar('\n'); } return 0; }约瑟夫扩展问题支持在线进行报不同数字支持在线交换两个人的位置甚至支持区间内人编号翻转
2023年08月01日
212 阅读
0 评论
0 点赞
2023-07-21
2023年7月上海月赛甲组T3最长上升子序列(二)题解
题目大意有 $n$ 个空白方格从左到右排成一行,编号以此为$1..n$。小爱可以给每个格子填上一个数字,其中对于编号为 $i$ 的格子,可以填入的数字的范围为给定的 $[l_i,r_i]$。现在,小爱想知道,如何选择合适的填法,才能使填入后这 $n$ 个数字组成的序列 $a_1,a_2,a_3,...,a_n$ 的最长上升子序列上度最长,本题只需输出最长长度即可。数据范围$1 \le n \le 10^5 , 1 \le l_i \le r_i \le 10^9$算法思路可以想到这是一个变种的最长上升子序列$dp$问题,由于数据范围较大,定是需要思考$O(nlogn)$算法,但不妨碍我们从简单思路出发来探究问题。我先用普通最长上升序列算法来设计$dp$状态, $dp[k]$ 长度为$k$的最长上升子序列的结尾的填入数字的最小值。对于变种最长上升子序列问题,也很容易想到$dp$数组是单调递增的,构建长度更长的序列,一定也需要更大的结尾数字。假设从前$i-1$号格子已经就算出了一段$dp$数组,$curMax$为当前计算出的最后一项的下标,注意下标也代表这最大上升长度。考虑第$i$格子时,有如下几种情况:$l_i > dp[curMax]$,则$dp[curMax+1] = l_i$。$l_i == dp[curMax]$ 且 $l_i < r_i$,则$dp[curMax+1] = l_i + 1$。$l_i == dp[curMax]$ 且 $l_i == r_i$, 则无需更新。在$dp$数组中找到大于 $l_i$ 最小位置 $x$,找到小于 $r_i$ 的最大位置 $y$。 若$x <= y$, 则 $i$ 格子加入使得 $[x,y]$ 区间内最长上升序列长度都加一,且最小结尾数字只需加一即可。做法上我们使区间内所有数字加一,并向后平移一个位置。平移之后,x位置会有空缺。若$l_i > dp[x-1]$, $dp[x] = li$, 否则 $dp[x] = l_i + 1$。若$x > y$,则说明 $l_i$ 只能更新位置 $x$ 的最小结尾数字若$l_i > dp[x-1]$ , $dp[x] = l_i$ ,否则若$r_i > l_i$,$dp[x] = l_i+1$ 。由于$dp$数组是单调的所以$x$ 和 $y$ 位置都可以二分拿到。唯一头疼是第$4$种情况下,区间更新和平移数组非常耗时。有没有一种数据结构,可以动态插入数据到指定位置,相当于平移指定位置后面的数据,且能够对指定区间元素实现统一的操作呢?平衡树(带区间操作)有,不过我们需要手写平衡树。可能你也听过一些平衡树,比如红黑树,树堆Treap,伸展树Splay等等吧。在这里推荐新手们,学一学FHQTreap,范浩强大神提出的一种无旋转Treap,性能不差,而且很容易实现区间操作,代码非常好写。区间操作非常类似线段树打懒标记和标记下传。通过平衡树我们把上述所有情况都可以$O(logn)$,算法的总体复杂度就是$O(nlogn)$。对于FHQTreap讲解 推荐参考一下这篇文章。
2023年07月21日
293 阅读
0 评论
0 点赞
1
2