补题
一道简单的数论公式题

题意:
给定一个区间, 求在这个区间[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;
}

线段树(Segment tree) 即解决区间问题的数据结构 常用于算法竞赛中
可以说是一种典型以空间换取时间的数据结构

举个栗子

区间求和问题
给定 n 个数,将会有 m 次操作
每次进行以下两种操作其中的一种:

• 求出区间 (l,r) 内所有数的加和
• 将位置 i 上的数增加 x

数据范围:

• 1 <= n <= 100000
• 1 <= l <= r <= 100000
• 1 <= m <= 10000

时间:1000MS 空间限制:128000KB

题目链接:CodeVS 1080 线段树练习

朴素做法

就是很简单的去维护一个一维数组
每次求和操作对数组 arr[l],arr[l+1]....,arr[r] 相加处理，时间复杂度 O(m)
每次增加操作直接修改 arr[x] 时间复杂度 O(1)
最极端的情况下这道题目的时间复杂度就变成了 O(m*n)
肯定是过不去的...所以这个时候就要介绍我们今天的主角线段树了

线段树

首先看到线段树，其实我是拒绝的...
因为直接看代码的话，神仙们写的代码一个人一种写法...

先介绍一下线段树的简单实现(我知道我讲话水平不好...所以文字描述看不懂的话请结合图片和代码来看):

线段树是一颗完全二叉树
我们给定一个节点存储区间(l,r)的信息
那么这个节点的左儿子则记录区间(l,(l+r)/2)的信息 右儿子记录了区间((l+r)/2+1,r)的信息

实现这个数据存储的过程 就是一个建树的过程

首先让我们先定义一下各个函数以及所用到的变量

//宏定义方便写代码 其中 << 为位运算 <<1 相当于乘二 <<1|1相当于乘二加1
#define leftSon left,mid,curr<<1
#define rightSon mid+1,right,curr<<1|1

long long int arrSum[maxN << 2];    //使用O(4*n)的空间建树

//更新当前节点的区间和
void pushUp(int curr);
//递归建树
void buildTree(int left, int right, int curr);
//对节点 node 增加 value
void addNode(int node, int value, int left, int right, int curr);
//查询区间(leftSection,rightSection)的和
unsigned long long int querySection(int leftSection, int rightSection, int left, int right, int curr);

让我们先来模拟递推一下线段树的构建过程
首先我们将数据读入 记作原数组Array

结合题意 我们需要求的区间的和 所以节点的记录的信息就是区间的和
既有以下的结构

此时让我们思考两个问题:

1. 如何快速简便的建立线段树
2. 如果题目给出的数据不满足2^n 那么如何建树

这个时候就要介绍一下二叉树的数组表示方法 也是在算法竞赛中常用到的方法

通过对图的观察可以知道 对于父亲节点arrSum[x] 它的左儿子即为arrSum[x<<1] 右儿子为arrSum[x<<1|1]
此时对于这道题线段树中的任意节点arrSum[x],它的值就是arrSum[x<<1]+arrSum[x<<1|1] 也就是一个从底向上递推当前区间和的过程
而利用这种方法建树 在之后的查询更新过程中利用这种性质也规避数据不满足 2^n 时访问越界的情况
这个时候就可以写出pushUp函数了

//pushUp向上更新节点(更新curr节点的值为它的两个儿子的加和)
void pushUp(int curr) {
    arrSum[curr] = arrSum[curr << 1] + arrSum[curr << 1 | 1];
    return;
}

之后利用递归来建树 先递归到树的最下面 之后更新上一层的节点
此时建树的时间复杂度是O(nlogn)

//这里我的习惯写法是在线地去建树 直接去掉了文中的Array数组
//建树函数 left为当前的左区间 right为当前的右区间 curr为当前对应的数组下标(节点)
//调用的话就是buildTree(1,n,1) 意味着建立一个(1,n)区间的线段树 当前的数组下标(节点)为1
void buildTree(int left, int right, int curr) {
        //先计算出中值 方便后续的二分
    int mid = (left + right) >> 1;
        //如果当前的左区间等于右区间,也就是满足了(x,x)的情况,获取第x个数据并存放于对应的节点中
    if (left == right) {
        scanf("%lld", &arrSum[curr]);
        return;
    }
        //递归建左右的节点
    buildTree(leftSon);
    buildTree(rightSon);
        //建完子树之后使用pushUp函数更新当前节点的值(区间和)为左右儿子节点的加和
    pushUp(curr);
    return;
}

接下来就是对位置 i 上的数进行更改,这个过程类似于建树的过程，查找这个节点是在当前的左或者右区间上,然后二分，直到到对应的位置上,对其进行加减操作之后,在递归的过程中向上pushUp,更新对应节点的值
时间复杂度为O(logn)

//对位置为node的节点增加value的值 等同于对区间(node,node)增加value的值
//调用方法就是addNode(node,value,1,n,1)
void addNode(int node, int value, int left, int right, int curr) {
    int mid = (left + right) >> 1;
        //如果左区间等于右区间 已经到达位置 对节点进行相加操作
    if (left == right) {
        arrSum[curr] += value;
        return;
    }
        //判断要操作的节点node在自己的左右区间 并进行二分
    if (node <= mid)
        addNode(node, value, leftSon);
    else
        addNode(node, value, rightSon);
        //儿子节点已经更新完了 用新的儿子节点的数据来更新当前节点的值 注意这是一个递归的函数
    pushUp(curr);
    return;
}

接下来也就是最后一个操作了
查询区间(l,r)
时间复杂度是O(logn)

//查询区间(leftSection,rightSection)
long long int querySection(int leftSection, int rightSection, int left, int right, int curr) {
    int mid = (left + right) >> 1;
        //如果当前区间在查询范围内 返回当前区间的值
    if (leftSection <= left && right <= rightSection)
        return arrSum[curr];
    long long int ret = 0;
        //判断查询区间的范围在当前区间的左或者右侧 二分
    if (leftSection <= mid)
        ret += querySection(leftSection, rightSection, leftSon);
    if (rightSection > mid)
        ret += querySection(leftSection, rightSection, rightSon);
        //返回当前已经查询到的值
    return ret;
}

最后 附上AC代码

Accepted 46ms 2 MB

/**
 * @author    Moe_Sakiya        sakiya@tun.moe
 * @date        2018-04-08 20:43:37
 *
 */

#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,curr<<1
#define rightSon mid+1,right,curr<<1|1

const int maxN = 100005;

long long int arrSum[maxN << 2];

void pushUp(int curr) {
    arrSum[curr] = arrSum[curr << 1] + arrSum[curr << 1 | 1];
    return;
}

void buildTree(int left, int right, int curr) {
    int mid = (left + right) >> 1;
    if (left == right) {
        if(left==9)
            printf("[%d]\n",curr );
        scanf("%lld", &arrSum[curr]);
        return;
    }
    buildTree(leftSon);
    buildTree(rightSon);
    pushUp(curr);
    return;
}

void addNode(int node, int value, int left, int right, int curr) {
    int mid = (left + right) >> 1;
    if (left == right) {
        arrSum[curr] += value;
        return;
    }
    if (node <= mid)
        addNode(node, value, leftSon);
    else
        addNode(node, value, rightSon);
    pushUp(curr);
    return;
}

long long int querySection(int leftSection, int rightSection, int left, int right, int curr) {
    int mid = (left + right) >> 1;
    if (leftSection <= left && right <= rightSection)
        return arrSum[curr];
    long long int ret = 0;
    if (leftSection <= mid)
        ret += querySection(leftSection, rightSection, leftSon);
    if (rightSection > mid)
        ret += querySection(leftSection, rightSection, rightSon);
    return ret;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int i, n, q, arg1, arg2, arg3;
    scanf("%d", &n);
    buildTree(1, n, 1);
    scanf("%d", &q);
    for (i = 0; i < q; i++) {
        scanf("%d", &arg1);
        switch (arg1) {
        case 1:
            scanf("%d %d", &arg2, &arg3);
            addNode(arg2, arg3, 1, n, 1);
            break;
        case 2:
            scanf("%d %d", &arg2, &arg3);
            printf("%lld\n", querySection(arg2, arg3, 1, n, 1));
            break;
        }
    }
    return 0;
}

啊 摸鱼真棒 实验室有空调 爽死了(就是蚊子有点多)

大致题意是使用1,0,-1构建一个N*N的矩阵,并且使矩阵的每行每列的和都不相等,如果存在这样的矩阵，输出"possible"并输出任意种情况,如果不存在输出"impossible"

首先在纸上模拟了一下,当N是奇数的时候是必然无解的
而当N是偶数时，我们可以先构建一个对称的矩阵，但由于对角线位置特殊，所以我们使用0填充，其余部分用1与-1填充

此时的话矩阵是关于对角线对称的，行列和存在相等，不符合题意，所以要想办法打破这种对称，所以对于对角线的另一半0的位置上可以使用其他数字来填充，则必定能构建一个合法的矩阵

附代码

Accepted 72ms 3632KB C++

/**
 * @author      Moe_Sakiya      i@tun.moe
 * @date        2018-07-30 23:58:37
 *
 */
 
#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;
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t, n, i, j;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        if (n % 2 == 0) {
            printf("possible\n");
            for (i = 0; i < n; i++) {
                for (j = 0; j < i; j++) {
                    putchar('1');
                    if (j != n - 1)
                        putchar(' ');
                }
                if (j < n / 2)
                    putchar('0');
                else
                    printf("-1");
                if (j != n - 1)
                    putchar(' ');
                j++;
                for (; j < n; j++) {
                    printf("-1");
                    if (j != n - 1)
                        putchar(' ');
                }
                putchar('\n');
            }
        } else
            printf("impossible\n");
    }
    return 0;
}