Solution Set -「ARC 107」
2024-09-07 18:09:15
「ARC 107A」Simple Math
Link.
答案为:
\[\frac{a(a+1)\cdot b(b+1)\cdot c(c+1)}{8}
\]
\]
「ARC 107B」Quadruple
Link.
枚举 \(i=c+d\),则 \(a+b=i+k\),乘法原理计数。
「ARC 107C」Shuffle Permutation
Link.
由于矩阵内无相等元素,所以行和列的顺序可以直接乘法原理。以对行的排列方案计数为例,并查集维护所有可以交换位置的行,则行的方案为每个集合大小的阶乘之积。列同理。
「ARC 107D」Number of Multisets
Link.
我真的傻了啊这题都想不出来。
DP,令 \(f(i,j)\) 表示 \(n=i,k=j\) 时的答案。利用当 \(i<j\),\(f(i,j)=0\) 的边界,有转移:
\[f(i,j)=f(i,2j)+f(i-1,j-1)
\]
\]
自行理解。复杂度 \(\mathcal O(nk)\)。
「ARC 107E」Mex Mat
Link.
结论:\((\forall i,j>4)(a_{ij}=a_{i-1,j-1})\)。手玩一下可以证明。(
写的时候可以用 std::vector
,这样直接在同一个“数组”上二维下标引用会舒服一点。
复杂度 \(\mathcal O(n)\)。
「ARC 107F」Sum of Abs
Link.
首先考虑把绝对值转化一下,对于一个集合 \(\{a\}\),显然有:
\[|\sum a|=\max\{\sum a,\sum-a\}
\]
\]
也就是说,一个联通块内的数可以同时取负。
从数据范围 \(n,m\le300\) 又想到最小割。不妨先获得所有 \(|b_i|\) 的收益,然后建图描述删点的操作。
一种建图如下(\(b_1\ge 0,b_2<0\),图中 \(i\) 应为 \(2\),抱歉 qwq):
\(i+\) 表示这个点在联通块中作正贡献,\(i-\) 则相反。割去 \(\langle i+,i-\rangle\) 表示删去点 \(i\)。可以发现,在没有删点的情况下,两个有边相连的点不可能取一正一负,符合要求。
最新文章
- [bootsrap]模态框使用例
- compass color 颜色 对比色[Sass和compass学习笔记]
- Qt qml pageview 左右滑动分页组件
- printf(),类型修饰符
- linux tar
- Redis学习笔记~常用命令总结
- 网上图书商城2--Category模块
- 在JS中设置Select和radio选中
- 转--23种设计模式的搞笑解释(后续放逐一C++解释版本)
- kcachegrind gui for callgrind
- objc非主流代码技巧
- React-Native ListView加载图片淡入淡出效果的组件
- IOS自学笔记1——学前准备
- leetcode第37题--Count and Say
- 禁止linux被ping
- MySQL高级特性——绑定变量
- Respone弹窗
- 满血复活--来自世一大的WAR
- UML图基础知识
- GetParam(name)
热门文章
- linux 设置root 密码
- 通过js触发onPageView和event事件获取页面信息
- Word2010制作简单个人简历
- java集合对比汇总
- 【Java】枚举类
- 论文解读二代GCN《Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering》
- 【记录一个问题】opencv中 cv::dft()与cv::ocl_dft()计算的结果相差较大
- numpy中,从一片c_void_p指向的区域里获取数据
- Java继承的概念与实现
- 深入了解promise