Codechef SEPT17
Codechef SEPT17
比赛链接:https://www.codechef.com/SEPT17
CHEFSUM code
给定数组 a[1..n] ,求最小的下标 i ,使得 prefixsum[i]+suffixsum[i] 最小。
解:
注意到 prefixsum[i]+suffixsum[i] = sum(a)+a[i]。
于是找到 a[i] 最小的下标 i 即可。
时间复杂度 O(n) 。
MINPERM code
找到字典序最小的 1..n 的排列 p[i] ,使得 p[i] != i 。
解:
如果 n 是偶数,则满足条件的排列形如 2, 1, 4, 3, ..., n, n-1;
如果 n 是奇数,则满足条件的排列形如 2, 1, 4, 3, ..., n-1, n, n-2。
时间复杂度 O(n) 。
CHEFPDIG code
给定字符集合为 {0, 1, ..., 9} 的串 s[1..n],任选 i 和 j (i != j),可生成ASCII码为 10*s[i]+s[j] 的字符。
求出所有可生成的大写字母。
解:
统计每个数字出现多少次。
分别枚举生成ASCII码的十位数和个位数,统计每种情况。注意处理十位数和个位数相等的情况。
时间复杂度 O(|s|) 。
SEACO code
序列 a[1..n] 初值为 0 ,维护m个两种操作:
1. x y 将 a[x], a[x+1], ..., a[y] 整体 +=1 。
2. x y 重做第 x 至第 y 个操作。保证 y 小于当前操作编号。
要求输出所有操作之后的序列a[1..n]。
解:
注意到所有操作存在拓扑序,并且 1, 2, 3, ..., m 即是一个合法的拓扑序。
因此,我们把所有操作倒过来处理,进而维护每个操作操作了多少次。
需要使用线段树或树状数组解决。
时间复杂度 O(mlogm+n) 。
FILLMTR code
一个 n×n 的矩阵 B ,其元素只能取 0 和 1 ,并且只有 q 个位置的值给定,问是否存在数组 A[1..n] 使得对任意给定值的位置 B[i][j] ,都有 B[i][j] = | A[i]-A[j] |。
解:
如果 B[i][j] = 0,则 A[i] = A[j];
如果 B[i][j] = 1,则 $A[i] \not \equiv A[j] \bmod 2$。
我们把这个问题转化为图论问题。
考虑一个 n 个节点的无向图 G。
如果 B[i][j] = 0,则 合并节点 i 和节点 j ;
如果 B[i][j] = 1,则 节点 i 和节点 j 之间连一条边。
我们可以证明,矩阵 B 满足条件,当且仅当无向图 G 是一个二分图。
判断一个图是否是二分图,DFS即可,时间复杂度O(n+q)。
WEASELTX
给你一棵 n 个节点的有根树(节点),以及每个节点 i 的初始权值 a[i] 。
一次操作则是指将每个节点的权值变为以其为根的子树中所有节点的权值之异或和。
维护 q 个询问,每个询问则是问 T 次操作之后,根节点的权值。
解:
请移步 http://www.cnblogs.com/TinyWong/p/7478598.html 。
SUMCUBE
给定无向简单图 G = (V, E)(即不存在自环和重边),以及 k = 1, 2, 或3 。
求
$$ \sum_{S \subseteq V} f(S)^k, $$
其中 $f(S)$ 是两个端点都在 S 中的边的数量。
解:
请移步 http://www.cnblogs.com/TinyWong/p/7478753.html 。
WEASELSC
给定一个高度图 a[1..n] ,要求你减少图中一些地方的高度,使得得到的图是一个不超过 K 级的楼梯,要求楼梯的面积最大(即得到的图中所有位置的高度之和最大)。
解:
请移步 http://www.cnblogs.com/TinyWong/p/7479466.html 。
QGRID
给定一个 n × m(1 <= m <= 3) 的点网格,网格的边上以及点上都有权值。
初始时所有点的权值都为 0 。
维护两种操作:
1. x1 y1 x2 y2 c 把从 (x1, y1) 到 (x2, y2) 的最短路上的所有节点的权值都增加 c 。保证最短路唯一。
2. x y 询问 (x, y) 的权值。
解:
请移步 http://www.cnblogs.com/TinyWong/p/7482179.html 。
最新文章
- ubuntu 常见错误--Could not get lock /var/lib/dpkg/lock
- UEditor上传图片等附件都出现红叉,该怎么解决
- Java学习之Iterator(迭代器)的一般用法 (转)
- ROS下创建第一个节点工程
- loadrunner11录制脚本打开IE9失败,浏览器崩溃,显示无法响应
- JQuery的定义
- iOS反射机制
- asp.net中的mysql传参数MySqlParameter
- lua wireshark 数据报解析
- .Net冷知识之动态查找类型时的程序集路径问题
- @JoinTable和@JoinColumn
- SQL事务机制
- 第四节:详细讲解Java中的类和面向对象思想
- pip 更改国内镜像
- SHFileOperation 解决double-null terminated
- Unity3D协同函数与异步加载功能实战 学习
- 关于高并发下kafka producer send异步发送耗时问题的分析
- Maven内置属性,pom属性
- AS 阿里巴巴Java开发规约 CheckStyle-IDEA
- yield python
热门文章
- vSphere 6.5支持512e,NVMe SSD呢?
- 【hibernate spring data jpa】执行了save()方法 sql语句也执行了,但是数据并未插入数据库中
- CentOS下常用的 19 条命令
- 删除DataGridView选中行并更新数据库
- 微信小程序 - 音频播放(1.2版本和1.2版本之后)
- [unity3d]unity平台的预处理
- iOS 相似淘宝商品详情查看翻页效果的实现
- 创建一个zookeeper的会话(实现watcher)
- Go语言测试代码
- SGU 194 Reactor Cooling 无源汇带上下界可行流