ACM生涯结束了...
perm_identityBakaErii query_builderlist日志 comment2 条评论
Orz 银川真的可惜了
Python可以过的我们纠结了半天
最后省不到一个小时理论AC了四节点的线段树求区间最值
最后还是崩了
铁头娃 铁头娃
不过很开心的是... 我脱单了(可能?)
也算是给两年多的ACM生涯画上了个带点遗憾的句号吧
是时候去搞点自己喜欢的东西了
Orz 银川真的可惜了
Python可以过的我们纠结了半天
最后省不到一个小时理论AC了四节点的线段树求区间最值
最后还是崩了
铁头娃 铁头娃
不过很开心的是... 我脱单了(可能?)
也算是给两年多的ACM生涯画上了个带点遗憾的句号吧
是时候去搞点自己喜欢的东西了
补题 摸鱼 写博客
半年没怎么做题突然写起来线段树感觉真滴难受 QwQ
传送门:
SPOJ GSS3 - Can you answer these queries III
题意:
给定一组数据, 有多次操作:
1.查询一段区间内最大的子段和.
2.修改一个位置上的数据.
题解:
首先读完题可以发现是区间查询+单点更新的问题. 线段树模型, 之后思考要维护什么内容.
对于每一个区间, 我们可以维护区间的最大子段和, 但是当PushUp更新的时候发现合并时不好处理.
考虑以下情况, 当合并两个区间的最大子段和时,分为三种情况:
1.最大子段和在左区间
2.最大子段和在右区间
3.最大子段和在中间部分
对于前两种状况, 我们可以直接取其中较大值即可, 对于第三种情况特殊考虑.
当最大子段和在两区间之间时, 必定会由左侧区间的后缀和右侧区间的前缀组成. 而想要使组成的子段和最大, 则必定是左侧区间的最大后缀和+右区间的最大前缀和.
最大子段和部分解决了, 现在来处理之前维护最大子段和用到的前缀和.
以前缀和举例, 当合并后最大前缀和有两种情况:
1.最大前缀和都在左侧区间内.
2.最大前缀和包括右侧区间的一部分.
当第一种情况时直接处理, 第二种情况时最大前缀和等于左侧区间的和+右侧区间的最大前缀和
至此, 我们就已经知道线段树所要维护的所有信息:
1.区间和
2.区间最大前缀和
3.区间最大后缀和
4.区间最大子段和
根据上文的思考, 我们就可以得出如何维护当前节点的信息:
// 更新区间和
T[cur].sum = T[cur << 1].sum + T[cur << 1 | 1].sum;
// 更新前缀和(左区间前缀 或者 右区间前缀+左区间和)
T[cur].per = max(T[cur << 1].per, T[cur << 1].sum + T[cur << 1 | 1].per);
// 更新后缀和(同理)
T[cur].suf = max(T[cur << 1 | 1].suf, T[cur << 1].suf + T[cur << 1 | 1].sum);
// 更新最大子段和 两种情况
// 1.单独在左右区间内
T[cur].con = max(T[cur << 1].con, T[cur << 1 | 1].con);
// 2.在合并的区间中(左区间后缀+右区间前缀)
T[cur].con = max(T[cur].con, T[cur << 1].suf + T[cur << 1 | 1].per);
单点更新就很好实现了, 和线段树板子就差不多了.
代码如下:
Accept C++14 (clang 4.0) 20ms:
/**
* @author Moe_Sakiya sakiya@tun.moe
* @date 2019-07-23 13:19:44
*
*/
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;
#define leftSon left,mid,cur<<1
#define rightSon mid+1,right,cur<<1|1
const int maxN = 50005;
struct Node
{
int sum; // 当前节点的区间和
int per; // 当前节点的最大前缀和(前子段和)
int suf; // 当前节点的最大后缀和(后子段和)
int con; // 当前节点的最大子段和
} T[maxN << 2];
int n, q;
// 向上更新
void PushUp(int cur) {
// 更新区间和
T[cur].sum = T[cur << 1].sum + T[cur << 1 | 1].sum;
// 更新前缀和(左区间前缀 或者 右区间前缀+左区间和)
T[cur].per = max(T[cur << 1].per, T[cur << 1].sum + T[cur << 1 | 1].per);
// 更新后缀和(同理)
T[cur].suf = max(T[cur << 1 | 1].suf, T[cur << 1].suf + T[cur << 1 | 1].sum);
// 更新最大子段和 两种情况
// 1.单独在左右区间内
T[cur].con = max(T[cur << 1].con, T[cur << 1 | 1].con);
// 2.在合并的区间中(左区间后缀+右区间前缀)
T[cur].con = max(T[cur].con, T[cur << 1].suf + T[cur << 1 | 1].per);
return;
}
// 建树
void BuildTree(int left, int right, int cur) {
int mid = (left + right) >> 1;
if (left == right) {
scanf("%d", &T[cur].sum);
T[cur].suf = T[cur].per = T[cur].con = T[cur].sum;
return;
}
BuildTree(leftSon);
BuildTree(rightSon);
PushUp(cur);
return;
}
// 修改
void UpdateNode(int node, int value, int left, int right, int cur) {
int mid = (left + right) >> 1;
if (left == right) {
T[cur].suf = T[cur].per = T[cur].con = T[cur].sum = value;
return;
}
if (node <= mid)
UpdateNode(node, value, leftSon);
else
UpdateNode(node, value, rightSon);
PushUp(cur);
return;
}
// 查询
Node QuerySection(int leftSection, int rightSection, int left, int right, int cur) {
int mid = (left + right) >> 1;
// 当前节点完全在查询区间内
if (leftSection <= left && right <= rightSection)
return T[cur];
// 当前节点不在查询区间内 向下递归
if (mid < leftSection)
return QuerySection(leftSection, rightSection, rightSon);
else if (rightSection <= mid)
return QuerySection(leftSection, rightSection, leftSon);
// 当前节点部分在查询区域内 取左右子树合并求解(类似PushUp操作)
Node retNode, leftNode, rightNode;
leftNode = QuerySection(leftSection, rightSection, leftSon);
rightNode = QuerySection(leftSection, rightSection, rightSon);
// 合并区间结果
retNode.sum = leftNode.sum + rightNode.sum;
retNode.per = max(leftNode.per, leftNode.sum + rightNode.per);
retNode.suf = max(rightNode.suf, leftNode.suf + rightNode.sum);
retNode.con = max(leftNode.con, rightNode.con);
retNode.con = max(retNode.con, leftNode.suf + rightNode.per);
return retNode;
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
int cmd, l, r;
scanf("%d", &n);
BuildTree(1, n, 1);
scanf("%d", &q);
for (int i = 0; i < q; i++) {
scanf("%d %d %d", &cmd, &l, &r);
switch (cmd) {
case 0:
UpdateNode(l, r, 1, n, 1);
break;
case 1:
printf("%d\n", QuerySection(l, r, 1, n, 1).con);
break;
}
}
return 0;
}
补题
一道简单的数论公式题
题意:
给定一个区间, 求在这个区间[L, R]中因子最多的数, 并输出它和它的因子个数.
题解:
初见杀...
这道题用到了 算术基本定理(又称为正整数唯一分解定理) , 即对于一个大于1的自然数, 如果自身不是质数, 那么一定可以写为两个以上质数的积, 且从小到大排列后有唯一写法.
所以对于区间[L, R]中的所有数进行分解, 得到唯一表达式, 之后计算因子个数.
首先对于12, 总共有6个因子(1, 12, 2, 6, 3, 4), 它的唯一表达式是: 12 = 2 ^ 2 * 3 ^ 1.
对于24, 总共有8个因子(1, 24, 2, 12, 3, 8, 4, 6), 它的唯一表达式是: 24 = 2 ^ 3 * 3 ^ 1.
我们可以看出来规律, 将其唯一表达式出现的所有质因子的指数加上1, 之后取积, 就是其因子个数.
因子个数 = 所有质因子的指数 + 1 的积.
通过质数筛来加速运算.
Accept G++ 530ms:
/**
* @author Moe_Sakiya sakiya@tun.moe
* @date 2018-11-26 18:59:49
*
*/
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;
const int maxN = 50005;
long long int arrPrime[maxN];
bool isPrime[maxN];
int cnt;
void calPrimes() {
memset(isPrime, 1, sizeof(isPrime));
cnt = 0;
isPrime[1] = false;
for (long long int i = 2; i < maxN; i++) {
if (isPrime[i] == true)
arrPrime[cnt++] = i;
for (int j = 0; j < cnt && i * arrPrime[j] < maxN; j++) {
isPrime[i * arrPrime[j]] = false;
if (i % arrPrime[j] == false)
break;
}
}
return;
}
long long int calNum(int n) {
long long int ret = 1;
int num;
for (int i = 0; i < cnt; i++) {
if (n % arrPrime[i] == 0) {
num = 1;
while (n % arrPrime[i] == 0 && n > 0) {
num++;
n /= arrPrime[i];
}
ret *= num;
}
}
return ret;
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
long long int maxNum, maxCount;
int t, l, r;
calPrimes();
scanf("%d", &t);
while (t--) {
maxNum = 0;
maxCount = 0;
scanf("%d %d", &l, &r);
for (int i = l; i <= r; i++) {
long long int tmp = calNum(i);
if (tmp > maxCount) {
maxCount = tmp;
maxNum = i;
}
}
printf("Between %d and %d, %lld has a maximum of %lld divisors.\n", l, r, maxNum, maxCount);
}
return 0;
}
康托展开是一个全排列到一个自然数的双射,常用于构建哈希表时的空间压缩.
而对于一个序列,其所有排列按照字典序排序的顺序从小到大编号, 康拓展开就是用于计算这种排列在其顺序中的位置.
举个栗子╰(°▽°)╯
对于序列{1,3,2}, 它的顺序位于其所有排列的第2位, 前一位为{1,2,3}.
其公式如下:
其中 T 为其排列的顺序, A_i 为序列中第 i 个元素, n 为序列总长度.
我们可以看到, 其中需要计算n!, 这一步可以通过打表来优化时间复杂度, 而当n!过大的时候, 就需要大整数计算了.
因为康托展开是一个双射, 那么一个合法的 T 值必定对应一个唯一的序列, 也就是说可以反向计算顺序为 T 的序列.
1.输入n, T
2.计算第i位对应的值(i从1开始):
a)将T-1,意为前面有T-1个排列
b)currI = T/(n-i)!, currI即为当前位数
c)如果currI已经被使用过,那么currI++
d)currM = T%(n-i)!, currM为剩下的数
e)T = currM
3.输出所有的currI
那么直接来道题叭:CodeVS 2972 - 选课
但是这道题...数据并不是很强...只有三个监测点
资料参考 Joseph Galante:Generalized Cantor Expansions
啊哈 我Sakiya又回来了
惊不惊喜 意不意外 (/≧▽≦)/
这是一道简单的 DFS序+线段树区间 更新问题...
题意:
对于一个公司内的员工, 每个员工有且只有一个直系上司, 而一个上司可以有许多的员工, 当给这个上司分配任务的时候, 他也会将该任务分配给所有下属(如果再次被分配将会覆盖掉之前的任务), 对于这样的结构进行两种操作
题解:
首先我们考虑如何去表示子树的状态
通过DFS序, 前序遍历题目给出的树, 并对于每个节点的入栈出栈时间做记录, 便可以得到对于父节点的所有子节点信息的一条线段, 这样的话查询当前父节点(线段的左端点)即可得知该员工执行的任务. 这样就将一个子树问题转换成了区间问题.
之后我们考虑分配任务的情况
通过线段树的区间更新, 来对当前节点(线段)下的所有节点更新赋值, 使用LazyTag思想优化时间复杂度.
Accept G++ 202ms 4992kB:
/**
* @author Moe_Sakiya sakiya@tun.moe
* @date 2018-11-14 18:46:28
*
*/
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#define leftSon left,mid,curr<<1
#define rightSon mid+1,right,curr<<1|1
using namespace std;
const int maxN = 50005;
struct DisNode
{
int l, r;
} disArr[maxN];
vector<int> vet[maxN];
int segTree[maxN << 2];
int lazyTag[maxN << 2];
int fatherArr[maxN];
int discnt;
inline void DFS(int id) {
disArr[id].l = discnt++;
for (int i = 0; i < (int)vet[id].size(); i++)
DFS(vet[id][i]);
disArr[id].r = discnt - 1;
return;
}
void pushDown(int curr) {
if (lazyTag[curr] != -1) {
lazyTag[curr << 1] = lazyTag[curr];
lazyTag[curr << 1 | 1] = lazyTag[curr];
segTree[curr << 1] = lazyTag[curr];
segTree[curr << 1 | 1] = lazyTag[curr];
lazyTag[curr] = -1;
}
return;
}
void buildTree(int left, int right, int curr) {
int mid = (left + right) >> 1;
if (left == right) {
segTree[curr] = -1;
return;
}
buildTree(leftSon);
buildTree(rightSon);
return;
}
void updateSection(int leftSection, int rightSection, int val, int left, int right, int curr) {
int mid = (left + right) >> 1;
if (leftSection <= left && right <= rightSection) {
lazyTag[curr] = val;
return;
}
pushDown(curr);
if (leftSection <= mid)
updateSection(leftSection, rightSection, val, leftSon);
if (rightSection > mid)
updateSection(leftSection, rightSection, val, rightSon);
return;
}
int queryNode(int node, int left, int right, int curr) {
int mid = (left + right) >> 1;
if (left == right) {
if (lazyTag[curr] != -1)
segTree[curr] = lazyTag[curr];
return segTree[curr];
}
pushDown(curr);
if (node <= mid)
return queryNode(node, leftSon);
else
return queryNode(node, rightSon);
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
int t, n, m, arg0, arg1, u, v;
char ch[10];
scanf("%d", &t);
for (int kase = 1; kase <= t; kase++) {
// INIT
discnt = 1;
memset(fatherArr, 0, sizeof(fatherArr));
memset(vet, 0, sizeof(vet));
memset(lazyTag, -1, sizeof(lazyTag));
// DataIn
printf("Case #%d:\n", kase);
scanf("%d", &n);
for (int i = 0; i < n - 1; i++) {
scanf("%d %d", &u, &v);
fatherArr[u] = v;
vet[v].push_back(u);
}
// Deal data & Build tree
for (int i = 1; i <= n; i++)
if (fatherArr[i] == 0)
DFS(i);
buildTree(1, n, 1);
scanf("%d", &m);
for (int i = 0; i < m; i++) {
// Query
scanf("%s", ch);
switch (ch[0]) {
case 'C':
scanf("%d", &arg0);
printf("%d\n", queryNode(disArr[arg0].l, 1, n, 1));
break;
case 'T':
scanf("%d %d", &arg0, &arg1);
updateSection(disArr[arg0].l, disArr[arg0].r, arg1, 1, n, 1);
break;
}
}
}
return 0;
}