2018 ICPC 沈阳网络赛
2018 ICPC 沈阳网络赛
Call of Accepted
题目描述:求一个算式的最大值与最小值。
solution
按普通算式计算方法做,只不过要同时记住最大值和最小值而已。
Convex Hull
题目描述:定义函数\(gay(x)\),若\(x\)是某个非\(1\)的数的平方的倍数,则\(gay(x)=0\),否则\(gay(x)=x^2\),求\(\sum_{num=1}^{n} ( \sum_{i=1}^{num} gay(x) ) mod p\)
solution
\[\sum_{num=1}^{n} ( \sum_{i=1}^{num} gay(x) ) mod p\]
\[(n+1)\sum_{i=1}^{n} gay(i) - \sum_{i=1}^{n} i \cdot gay(i)\]
然后容斥就可以算出答案,用上莫比乌斯函数。
时间复杂度:\(O(\sqrt{n}\))
D. Made In Heaven
题目描述:判断图的\(k\)短路是否不超过\(T\).
solution
模板题。
F. Fantastic Graph
题目描述:给定一个二分图,现在选择一些边,使得最终所有点的度都在\([L, R]\),判断是否可行。
solution
上下界网络流的模板题。
G. Spare Tire
题目描述:定义\(a_n\),求\(\sum_{i=1}^{n} [gcd(m, i)=1] a_i\)
\[
a_n =\left\{\begin{matrix}
0, & n=0\\
2, & n=1\\
\frac{3a_{n-1} - a_{n-2}}{2}+n+1 & n>1
\end{matrix}\right.
\]
solution
找规律可得\(a_n=n(n+1)\),
\[\sum_{i=1}^{n} [gcd(m, i)=1] a_i\]
\[=\sum_{d|m} \mu(d) \sum_{x=1}^{n/d} (xd)(xd+1)\]
\[=\sum_{d|m} \mu(d)[d^2 \sum_{x=1}^{n/d} x^2 + d \sum_{x=1}^{n/d} x]\]
所以可以对\(m\)分解质因数,穷举\(m\)所有非平方倍数的因子(因为只有这些因子对应的\(\mu\)不为\(0\)),后面的直接求和即可。
时间复杂度:\(O(能过)\)
I. Lattice's basics in digital electronics
solution
字典树+模拟。
J. Ka Chang
题目描述:有一棵有根树,有两种操作:1.给深度为\(L\)的点加\(x\) 2.求一棵子树的和。
solution
树分块。求树的\(dfs\)序,将\(dfs\)序分成\(\sqrt{n}\)块,算出每一块每种高度的个数,对于操作1,每一块的答案增加\(x\)乘于高度为\(L\)的个数。对于操作2,求的是\(dfs\)中连续一段区间的和,那就是很普通的分块计算。
时间复杂度:\(O(n\sqrt{n})\)
K. Supreme Number
题目描述:如果一个素数的非空子序列也是素数(或者\(1\)),那么这个素数叫做超级素数,给定一个\(n\),求不大于\(n\)的最大超级素数。
solution
显然这样的数不多,而且比较小,所以可以先暴力求出所有超级素数,然后询问的时候再二分查找。
时间复杂度:\(O(能过)\)
最新文章
- [译] EXTENDING JQUERY – 2.2 A simple plugin
- 【Clr in c#】泛型
- Leetcode 52 N-Queens II 回溯搜索
- js中indexOF和lastIndexOf
- LINUX ping 指定网卡
- [功能帮助类] C#RandomHelper随机数,随机字符,可限制范围-帮助类 (转载)
- Python报错:SyntaxError: Non-ASCII character '\xe5' in file的解决方法
- 【翻译自mos文章】oracle支持在RDBMS HOME 下的 符号链接( Symbolic Links)吗?
- LuoguP3701 「伪模板」主席树
- 团队作业2:需求分析&;原型设计
- AE的空间分析(转载)
- springboot打成war包找不到文件
- json2.js 序列化 和反序列化 转
- Linux下zip命令
- mysql 导出表数据表结构
- Thinking in Java笔记之类及对象的初始化
- IE 6 position不支持fixed属性的解决方案
- SAN,NAS区别的联系
- fopen, fdopen, freopen - 打开流
- poj2914 Minimum Cut 全局最小割模板题