【HDU-6192】Removing Mountains【扩展KMP+hash】

【HDU-6192】Removing Mountains【扩展KMP+hash】

问题链接:https://vjudge.net/problem/HDU-6192

Solution:

F题拆完墙,这道K题又要移山了。。。回到正题,问题要求输出最短周期以及改造的山个数。问题当然要一步一步解决,先从最特殊的情况入手,如果当前只有一座山,则最短周期必然使是1,由于题目都明确要求他非得移山了,那只有一座山,他若想移那就移吧,所以\(n = 1\)时,输出“1 1”。。。【个人觉得,这是这道题最坑的地方】接着,如果这座山已经存在周期了,那么只好把它们全部移除来破掉旧的周期,达到最小的周期,所以输出“1 n”。接着就是一般情况了,枚举每种周期,根据扩展kmp得到的最大相同前缀长度,尝试修改其失配的第一个位置(两种修改方法,为了方便表述,假设现在枚举到周期i,用扩展kmp打出的数组【我命名成了kmp[]】中kmp[i]就表示从字符i到字符串结尾的子串与原字符串的最大相同前缀长度,则说明字符串【我命名为str】的str[kmp[i]]与str[kmp[i] + i]失配,两种修改方法就是拿前者替换后者,或者后者替换前者),接着使用hash值来判是否相同(这道题字符集很小,hash值不用取模,只要进制素数取得足够大,就不会发生碰撞,直接用hash值判断就可以确定字符串相同,关于hash进行字符串匹配,可以阅读:Rabin-Karp Algorithm,需要留意的一点是,链接的这篇文章中hash值存在碰撞的可能,所以需要在hash值匹配后进行二次判断)。

#include <iostream>
#include <string>

using namespace std;

typedef unsigned long long LL;
const int LIM = 1e6 + 10;
const int BASE = 131;
string str;
int kmp[LIM], n;
LL carryNum[LIM];
LL prehash[LIM];

// use ch to replace the character pos at br(beReplace)
inline LL getHash(int l, int r, int br, char ch) {
    return prehash[r] - (l > 0 ? prehash[l - 1] * carryNum[r - l + 1] : 0)
        + (l <= br && br <= r ? -str[br] * carryNum[r - br] + ch * carryNum[r - br] : 0);
}

void init() {
    int i;
    for (carryNum[0] = 1, prehash[0] = str[0], i = 1; i < n; i++) {
        carryNum[i] = carryNum[i - 1] * BASE;
        prehash[i] = prehash[i - 1] * BASE + str[i];
    }
}

void exkmp() {
    kmp[0] = n;
    int i;
    for (i = 1; i < n && str[i - 1] == str[i]; i++);
    kmp[1] = i - 1;
    int p0 = 1;
    for (i = 2; i < n; i++) {
        if (i + kmp[i - p0] >= p0 + kmp[p0]) {
            int j = p0 + kmp[p0] - i;
            if (j < 0) j = 0;
            for (; j + i < n && str[j + i] == str[j]; j++);
            kmp[i] = j;
            p0 = i;
        } else {
            kmp[i] = kmp[i - p0];
        }
    }
}

int main(void) {
    ios::sync_with_stdio(false);
    while (cin >> n >> str) {
        if (n == 1) {
            cout << 1 << " " << 1 << endl;
            continue;
        }
        init();
        exkmp();
        for (int i = 1; i < n; i++) {
            int lca = kmp[i];
            if (i + lca == n) {
                cout << i << " " << n << endl;
                break;
            } else {
                int k = 0;
                if (getHash(0, n - 1 - i, lca, str[i + lca]) == getHash(i, n - 1, lca, str[i + lca]))
                    k++;
                if (getHash(0, n - 1 - i, i + lca, str[lca]) == getHash(i, n - 1, i + lca, str[lca]))
                    k++;
                if (k) {
                    cout << i << " " << k << endl;
                    break;
                }
            }
        }
    }
    return 0;
}

 

解决这道题时去网上参考了一些大神的博文,十分感谢大佬的分享,参考链接附上:

https://blog.csdn.net/u012345506/article/details/80134756

【HDU-6191】Query on A Tree【Trie + DFS】

【HDU-6191】Query on A Tree【Trie + DFS】

问题链接:https://vjudge.net/problem/HDU-6191

Solution:

题目给了10s限时,一般这种时间的题目。。。所以直接暴力DFS或BFS就不用想了,如DFS复杂度O(nq),一般情况下都是会超时的,这题也不例外。解决办法是,DFS序,再根据每个结点二进制的数值维护字典树,我们其实是在构建一个字典树的森林。开一个idx数组,把每个结点原来的标号映射到DFS遍历的顺序上去,比如下面这棵树:

【注:[]内表示该结点的标号,:后面则是该结点的值】

通过DFS,建立起的idx数组将是下面这样:

为了看得清楚,将其映射后的编号标在树上是:

这样的顺序能够保证所有结点都出现在其父结点之后,开一个sz数组来存储下按照当前顺序每个结点之后多少个结点属于它就好了。

接着维护字典树,将每个结点的值转换为其二进制表示,则这棵字典树就是根据其值每个二进制位上0或1来建立的,按照上边的dfs序依次建立字典树,对于每个结点要建立字典树时,先继承(暂时想不到更合适的词)其dfs序前一个结点的对字典树中下一个结点的指向,之后根据当前二进制位上0或1创建新的字典树上结点(这里描述有些混乱,可以配合着阅读代码),用root来存储对于每个结点其在字典树数组中的根结点位置,查询的时候就根据输入的x值每个二进制位来查询,如果该位不存在于u结点及其子结点的字典树中,则结果的该位上就是0,反之就是1。下面的AC代码中使用role数组来标识每个trie树中的结点是由哪个dfs序标号的原来的结点创建的,也就是时间戳。对于query中的res,如果字典树中存在某个位置上相反的数,则最后异或出来的结果这位上便是1,反之只能是0,这样找出来的res必然使最大的。

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int SIZE = 29;
const int LIM = 1e5 + 10;
const int NIL = -1;
int role[LIM * (SIZE + 3)], trie[LIM * (SIZE + 3)][2], root[LIM], values[LIM], sz[LIM];
int trie_size, node_size;
int idx[LIM];
vector<int> adj[LIM];

inline void init(int n) {
    trie_size = node_size = 0;
    memset(trie, 0, sizeof trie);
    memset(role, 0, sizeof role);
    memset(sz, 0, sizeof sz);
    for (int i = 1; i <= n; i++)
        adj[i].clear();
}

void update(int &crt, int pre, int vpos, int d) {
    crt = ++trie_size;
    trie[crt][0] = trie[pre][0];
    trie[crt][1] = trie[pre][1];
    role[crt] = role[pre] + 1;
    if (d == NIL) return;
    int key = (values[vpos] >> d) & 1;
    if (key) update(trie[crt][1], trie[pre][1], vpos, d - 1);
    else update(trie[crt][0], trie[pre][0], vpos, d - 1);
}

void dfs(int crt) {
    idx[crt] = ++node_size;
    sz[crt] = 1;
    update(root[idx[crt]], root[idx[crt] - 1], crt, SIZE);
    for (int i = 0; i < adj[crt].size(); i++) {
         dfs(adj[crt][i]);
         sz[crt] += sz[adj[crt][i]];
     }
}

int query(int lb, int rb, int x, int d, int res) {
    if (d == NIL) return res;
    int key = ((x >> d) & 1) ^ 1;
    int isInRange = role[trie[rb][key]] - role[trie[lb][key]];
    if (isInRange) return query(trie[lb][key], trie[rb][key], x, d - 1, res | (1 << d));
    else return query(trie[lb][key ^ 1], trie[rb][key ^ 1], x, d - 1, res);
}

int main(void) {
    int n, q;
    while (~scanf("%d%d", &n, &q)) {
        init(n);
        for (int i = 1; i <= n; i++)
            scanf("%d", values + i);
        for (int i = 2; i <= n; i++) {
            int p;
            scanf("%d", &p);
            adj[p].push_back(i);
        }
        dfs(1);
        int u, x;
        while (q--) {
            scanf("%d%d", &u, &x);
            printf("%d\n", query(root[idx[u] - 1], root[idx[u] + sz[u] - 1], x,  SIZE, 0));
        }
    }
}

 

注:编写时有参考了一些大神的博客,感谢大神分享,下面附上参考的博文链接:

https://www.cnblogs.com/Blackops/p/7493464.html

https://www.cnblogs.com/teble/p/8952322.html

https://blog.csdn.net/jinglinxiao/article/details/77803383

【HDU-6187】Destroy Walls【最大生成树】

【HDU-6187】Destroy Walls【最大生成树】

问题链接:https://vjudge.net/problem/HDU-6187

Solution:

从前有一座城,被城墙分割的城。新登基的君王,要到达城的每一个角落,下令要拆墙;拆墙就拆墙,还要消耗最少,问拆几面墙,拆墙花费是多少。

翻译一下这个问题,就是:从前有个平面,上面有张无向图,现在擦掉一些边,让图上没有环,同时消耗最少。

一张无向图,拆掉环,那不就是一棵树了嘛,所以这道题是在找一个生成树,更进一步,最大生成树,权值和最大,拆掉的权值和就最小,因此并查集+最大生成树就解决了。

 

#include <iostream>
#include <algorithm>
// #define DBG

using namespace std;

const int LIM = 1e5 + 10;
struct Edge{
    int x, y, w;
    bool operator < (const Edge &e) const { return w > e.w; }
} edges[LIM * 2];
int parent[LIM];

int find(int x) {
    if (x != parent[x]) parent[x] = find(parent[x]);
    return parent[x];
}

bool Union(int x, int y) {
    int xpos = find(x);
    int ypos = find(y);
    if (xpos == ypos) {
        return false;
    } else {
        parent[ypos] = parent[xpos];
        return true;
    }
}

int main(void) {
    int n, m;
    while (~scanf("%d%d", &n, &m)) {
        int sum = 0, cnt = 0, rest = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%*d%*d");
            parent[i] = i;
        }
        for (int i = 0; i < m; i++) {
            scanf("%d%d%d", &edges[i].x, &edges[i].y, &edges[i].w);
            sum += edges[i].w;
        }
        sort(edges, edges + m);
#ifdef DBG
        printf("Sorting...Done!\n");
        for (int i = 0; i < m; i++) {
            printf("edges[%d]: x = %d, y = %d, w = %d\n", i, edges[i].x, edges[i].y, edges[i].w);
        }
        printf("Show the edges...Done!\n");
#endif
        for (int i = 0; i < m; i++) {
            if (Union(edges[i].x, edges[i].y)) cnt++, rest += edges[i].w;
#ifdef DBG
            printf("now cnt = %d, rest = %d, sum = %d\n", cnt, rest, sum);
            printf("The parent[]:\n");
            for (int i = 1; i <= n; i++)
                printf("\tparent[%d] : %d\n", i, parent[i]);
            printf("Done...\n");
#endif
        }
        printf("%d %d\n", m - cnt, sum - rest);
    }
    return 0;
}

注:写的时候犯了失误,导致用条件编译#define DBG手动调了会儿,结果发现find()函数写错了。。。上面代码如果觉得乱就看下面的,把#define DBG相关部分全部删除后的:

#include <iostream>
#include <algorithm>
using namespace std;

const int LIM = 1e5 + 10;
struct Edge{
    int x, y, w;
    bool operator < (const Edge &e) const { return w > e.w; }
} edges[LIM * 2];
int parent[LIM];

int find(int x) {
    if (x != parent[x]) parent[x] = find(parent[x]);
    return parent[x];
}

bool Union(int x, int y) {
    int xpos = find(x);
    int ypos = find(y);
    if (xpos == ypos) {
        return false;
    } else {
        parent[ypos] = parent[xpos];
        return true;
    }
}

int main(void) {
    int n, m;
    while (~scanf("%d%d", &n, &m)) {
        int sum = 0, cnt = 0, rest = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%*d%*d");
            parent[i] = i;
        }
        for (int i = 0; i < m; i++) {
            scanf("%d%d%d", &edges[i].x, &edges[i].y, &edges[i].w);
            sum += edges[i].w;
        }
        sort(edges, edges + m);
        for (int i = 0; i < m; i++) {
            if (Union(edges[i].x, edges[i].y)) cnt++, rest += edges[i].w;
        }
        printf("%d %d\n", m - cnt, sum - rest);
    }
    return 0;
}

 

【HDU-6189】Law of Commutation

【HDU-6189】Law of Commutation

问题链接:https://vjudge.net/problem/HDU-6189

Solution:

没有头绪的时候先打个表,找找规律。说到打表,用python会很方便:

from math import pow
for a in range(1, 6):
    for n in range(1, 5):
        m = int(pow(2, n))
        cnt = 0
        for b in range(1, m + 1):
            if int(pow(a, b)) % m == int(pow(b, a)) % m:
                cnt = cnt + 1
                # print("a = ", a, "b = ", b, ", pow(a, b) = ", pow(a, b), ", pow(b, a) = ", int(pow(b, a)))
        print("a = ", a, ", n = ", n, ", m = ", m, ", ans = ", cnt)

输出:

a =  1 , n =  1 , m =  2 , ans =  1
a =  1 , n =  2 , m =  4 , ans =  1
a =  1 , n =  3 , m =  8 , ans =  1
a =  1 , n =  4 , m =  16 , ans =  1
a =  2 , n =  1 , m =  2 , ans =  1
a =  2 , n =  2 , m =  4 , ans =  2
a =  2 , n =  3 , m =  8 , ans =  3
a =  2 , n =  4 , m =  16 , ans =  5
a =  3 , n =  1 , m =  2 , ans =  1
a =  3 , n =  2 , m =  4 , ans =  1
a =  3 , n =  3 , m =  8 , ans =  1
a =  3 , n =  4 , m =  16 , ans =  1
a =  4 , n =  1 , m =  2 , ans =  1
a =  4 , n =  2 , m =  4 , ans =  2
a =  4 , n =  3 , m =  8 , ans =  4
a =  4 , n =  4 , m =  16 , ans =  8
a =  5 , n =  1 , m =  2 , ans =  1
a =  5 , n =  2 , m =  4 , ans =  1
a =  5 , n =  3 , m =  8 , ans =  1
a =  5 , n =  4 , m =  16 , ans =  1

打表只要注意别打错就好,这道题数量增长会很快,如果发现有个别数据规律比较奇怪,最好去验证一下,看看是不是因为精度问题得到的错误结果,如果打表打错了,岂不是很糟糕,规律基本就没办法找了。

打表可以发现,当a为奇数的时候,答案固定为1【证明比较长,篇幅大约1500多字,所以单独另写了一篇:关于对a^b % 2^n = b^a % 2^n,当a为奇数时,在范围[1, 2^n]有且仅有一个b使等式成立的证明】。当a不是奇数的时候(即a是偶数,可以表示为\(a = 2k\)),分类讨论一下,将问题简化,将b以n为分界【为什么要以n来分界呢?原因很简单,我们希望找到一些信息来减少枚举的计算量,n是个很好的值,因为:

\(a^b = (2k)^b = 2^bk^b\),

当b大于等于n的时候,\(a^b % m = 0\),在满足这个条件的时候,只要找到使\(b^a % m = 0\)成立的b的数量,这样即便是枚举都能够减少一些计算量,如果后面发现还可以推导出进一步的结论来简化计算(提前“剧透”:后面我们确实“很幸运地”推导出了更直接的解决方法),就可以更好地解决这个问题,因此取这个值很可能会对我们研究这个问题有帮助】。考虑到\(n \le 30\),当\(b < n\)的时候直接暴力枚举也不会有太大的消耗,我们对于\(b < n\)时采用暴力。接下来就是\(b \ge n\)的情形,这种情形,我们推测出满足的同余方程的b必然使\(b ^ a % m = 0\),由于a和m都是偶数,如果想让等式成立,b至少得是一个偶数【奇数的偶数次仍然是奇数,那样的话就必然不可能整除m】,更为具体的是\(b = 2 ^ t * y\)【简单说明一下,我们在表示b的时候将其因数2单独用\(2^t\)表示,剩下的因数全部用y来概括】,则有:

\(b^a = 2^{at} y^a\),

这个形式十分的友好,这个数中的因数2已经全部“聚集”到上式的\(2^{at}\)部分,显然可以判断出,如果让\(b^a % m = 0\)成立,只要\(at \ge n\)即\(t \ge n / a\),b的个数取决于t的个数和y的个数,为了找到n到m中有多少个符合条件的b,我们令\(t = ceil(n / a)\)【ceil是向上取整,如果向下取整的话会无法达成上面推出的整除条件】,之后把多余的因数2并入到y中,这样我们可以得到:

\(y = \frac{b}{2^{ceil(n / a)}}\)

当我们取b的取值上界\(b = m\)时,上式向下取整后得到的便是y的最大可取值(为了方便表述,记作\(y_{max}\)),y可以取\([1, y_{max}]\),这个范围内刚好有\(y_{max}\)个数,因此,这个值就是[1, m]中这样的b的个数,接着还需要处理一点,由于这个结论是建立在前提条件\(b \ge n\)下的,所以刚才的\(y_{max}\)还需要减去下界\(y_{min} = \frac{n}{2^{ceil(n / a)}}\)在加上枚举\(b \le n\)结果才是最后的答案。

AC代码如下:

#include <iostream>

using namespace std;

typedef long long LL;

LL pow(LL a, LL b, LL mod) {
    LL ret = 1;
    while (b) {
        if (b & 1) ret = ret * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ret;
}

LL pow(LL a, LL b) {
    LL ret = 1;
    while (b) {
        if (b & 1) ret = ret * a;
        a = a * a;
        b >>= 1;
    }
    return ret;
}

int main(void) {
    ios::sync_with_stdio(false);
    LL a, n;
    while (cin >> n >> a) {
        if (a & 1) {
            cout << "1" << endl;
        } else {
            LL cnt = 0, m = 1 << n;
            for (LL b = 1; b <= n; b++)
                if (pow(a, b, m) == pow (b, a, m)) cnt++;
            LL tmp = 1 << ((n + a - 1) / a);
            cnt += m / tmp - n / tmp;
            cout << cnt << endl;
        }
    }
    return 0;
}

备注:上面的两个pow函数分别是快速模幂函数和快速幂函数。

【HDU-6184】Counting Stars【三元环+set+hash+邻接表】

【HDU-6184】Counting Stars【三元环+set+hash+邻接表】

问题链接:https://vjudge.net/problem/HDU-6184

Solution:

题目要求寻找 “A-structure”,其实就是有一条公共边的两个三元环的组数。

这道题需要暴力枚举每一条边,即假设它是那条三元环的公共边,看看能构成几个三元环,显然如果只能构成1个三元环,则无法组成”A-structure”,至少需要两个三元环。如果对于一个公共边能够找到\(cnt\)个三元环,则任意两个都能构成一个“A结构”,所以只要用组合数学中的方法计算一下\(cnt \times (cnt – 1) / 2\)就可以。

不过,直接根据输入的顺序进行暴力是会超时的,需要调整一下枚举边的顺序。无论采用哪种办法,只要保证最后枚举边的顺序依此枚举完与一个点的所有边后再枚举下一个顶点就可以。很多人博客中采取的是用循环结构枚举顶点,之后通过一个vis[]数组来判重,如果发现一个点已经遍历过,枚举之后的点时就不必考虑这个顶点了。而我下边的代码采用了对边排序的方法【注:但是需要保证每条边在存储时,较小的顶点固定放在一个变量上,之后根据这个变量来排序】,之后直接枚举每条边,最后的结果是,这个遍历顺序和上边枚举顶点的遍历顺序完全一样。

有序搜索带来的好处是,一个点相连的全部边一定连着这个点(这是显然的),于是我们可以在遍历与这个点相连的全部边时提前开一个linked[]数组,将与该点相连的所有顶点在这个数组中的值设置成该点的值,这样,枚举一个边的时候,如果使用不是该点的顶点判断三元环,就可以直接使用这个数组判断一下与它相连的所有点的值,来确定是否构成了三元环【这段表述起来有些不易于阅读,可以结合代码来看】。

很多博客中所写的题解,通过使用一个sqrt(m)来判断应该使用哪个点枚举边,但是其实可以不使用这个,只要判断一下,两个边的度数哪个小就枚举哪个顶点的边就好。【备注:m是边数,对于一个n阶无权无项图,它的大小(即边的个数)最多是\(\frac{n \times (n – 1)}{2}\),即n近似等于\(\sqrt{m}\)】

简单地说,枚举到一条边的 时候就决定一下使用这条边的哪个顶点来判三元环【因为判断三元环要判断与一个点相连的其它点是否能连回当前枚举边的另一个顶点,所以当然是枚举那个度数小的顶点要快一些】,如果使用最近这几次枚举的边共同连接的一个点的话,就直接借助linked数组,\(O(1)\)复杂度,反之就是用hash值+set判重。

#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include <algorithm>
// #define DBG

using namespace std;

const int LIM = 1e5 + 5;
typedef long long LL;
struct edge {
    int x, y;
    bool operator < (const edge &e) const { return x < e.x; }
} edges[LIM * 2];
vector<int> v[LIM];
set<LL> e;
int linked[LIM];
int n, m;
LL ans;

/* 用来计算hash值,结合set,可以用来快速判断是否存在某条边 */
inline LL myHash(LL x, LL y) {
    return x + y * (n + 1);
}

inline void swap(int &a, int &b) {
    int tmp = a;
    a = b;
    b = tmp;
}

inline void init() {
    for (int i = 1; i <= n; i++)
        v[i].clear();
    memset(edges, 0, sizeof edges);
    memset(linked, 0, sizeof linked);
    e.clear();
    ans = 0;
}

LL getSum(int x, int y) {
    LL cnt = 0;
    /* 分类优化在这道题中很重要,对于顶点y的度小于x的度的情况,可以直接使用刚刚根据x打好的linked数组 */
    if (v[y].size() <= v[x].size()) {
        for (vector<int>::iterator ite = v[y].begin(); ite != v[y].end(); ite++)
            if (linked[*ite] == x) cnt++;
    } else {
        /* 对于y顶点的度大于x顶点度的情况,使用set配合hash值查询 */
        for (vector<int>::iterator ite = v[x].begin(); ite != v[x].end(); ite++)
            if (e.find(myHash(*ite, y)) != e.end()) cnt++;
    }
#ifdef DBG
    printf("Edge: (%d, %d) -> cnt: %d\n", x, y, cnt);
#endif
    /* 如果一条边有cnt个三元环,根据组合数学,应当会有cnt * (cnt - 1) / 2个题设结构 */
    /* 需要注意cnt * (cnt - 1)可能会超过int的取值范围 */
    return cnt * (cnt - 1) / 2;
}

int main(void) {
    while (~scanf("%d%d", &n, &m)) {
        init();
        for (int i = 0; i < m; i++) {
            scanf("%d%d", &edges[i].x, &edges[i].y);
            e.insert(myHash(edges[i].x, edges[i].y));
            e.insert(myHash(edges[i].y, edges[i].x));
            v[edges[i].x].push_back(edges[i].y);
            v[edges[i].y].push_back(edges[i].x);
            /* 如果输入的第二个顶点小于第一个顶点,进行交换,为了维护我们需要的顺序 */
            if (edges[i].x > edges[i].y) swap(edges[i].x, edges[i].y);
        }
        /* 将边按照x进行排序,edges数组中的边将会变得有序 */
        sort(edges, edges + m);
        int pre = 0;
        for (int i = 0; i < m; i++) {
            if (edges[i].x != pre) {
                pre = edges[i].x;
                /* 得益于有序,我们可以预先根据x值将与它相邻的顶点在linked数组的值设为x */
                for (vector<int>::iterator ite = v[edges[i].x].begin(); ite != v[edges[i].x].end(); ite++)
                    linked[*ite] = edges[i].x;
            }
#ifdef DBG
            cout << "#################" << endl;
            for (int i = 1; i <= n; i++) {
                printf("# linked[%d] = %d #\n", i, linked[i]);
            }
            cout << "#################" << endl;
#endif
            ans += getSum(edges[i].x, edges[i].y);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

做题中间犯了一个小错误,导致三个小时一直在WA,事后发现这个错误真的不值一提,是一个十分粗心的错误,但是由于这个错误如果真疏忽的话可能会想不到这个点来,所以在这里记录一下,就是由于所有的顶点取值范围是1到n,所以清空邻接表的时候要从1到n进行clear(),我一开始失误地从0到n – 1进行了clear,刚好把顶点n的vector漏掉了。

最后附上一些自编的测试数据:

输入:

7 12
1 7
2 1
4 2
4 5
6 5
6 7
1 3
2 3
4 3
5 3
6 3
7 3

8 16
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5
2 6
2 7
2 8
3 4
5 6
7 8

2 1
1 2

5 6
1 2
2 3
3 1
1 4
1 5
5 4

7 11
1 3
1 2
2 3
3 4
2 4
5 4
5 2
6 4
6 5
6 7
7 5

5 5
1 3
3 4
4 5
5 1
3 5

 

输出:

6
30
0
0
4
1

【2017ACM-ICPC广西邀请赛】Color it

【2017ACM-ICPC广西邀请赛】Color it

【动态线段树】

问题链接:https://vjudge.net/problem/HDU-6183

Solution:

核心思路:由于查询总是对(1, y1) ~ (x, y2)这个范围内进行查询,其中x的起始固定为1,也就是说,对于任意位于y1与y2之间的上色点,只要其横坐标小于x,它就在这个区间内,于是我们可以建立线段树,用y来作为区间,线段树上每个结点的值则是这个y的区间内最小的x,由于有51中颜色【0~50】,需要维护51个这样的线段树。

上边的思路是正确的,但是因为内存限制,无法开51个1e^6 * 2的线段树,因此,我们采用动态化线段树。因为在操作线段树时,我们只需要能够由父结点寻找子节点,而不局限于必须使用index >> 1和index >> 1 | 1的方式,我们可以用两个数组来存储对于任意一个结点其左、右结点在数组中的下标,这样就可以找到一棵树所有的结点,并且,也保证了没有经历过的区间是不会存储的,具体方法如下,tree就是存放数值的线段树,rootPos数组存储51种颜色的树其根节点在tree中的位置,lrt和rrt数组分别表示以其下标作为为tree中位置的结点的左右结点在tree中的位置。

C++代码:

#include <iostream>
#include <cstring>

using namespace std;

const int INF = 1e7;
const int LIM = 2e6;
bool flag;
int tree[LIM], rootPos[51], lrt[LIM], rrt[LIM], num;

inline int mini(int a, int b) {
    return a < b ? a : b;
}

inline void clear() {
    num = 0;
    for (int i = 0; i < LIM; i++) tree[i] = INF;
    memset(rootPos, 0, sizeof rootPos);
    memset(lrt, 0, sizeof lrt);
    memset(rrt, 0, sizeof rrt);
}

inline void pushup(int rt) {
    tree[rt] = mini(tree[lrt[rt]], tree[rrt[rt]]);
}

void update(int l, int r, int si, int x, int &rt) {
    if (l > si || r < si) return;
    if (!rt) rt = ++num;
    if (l == r) {
        if (tree[rt] > x) tree[rt] = x;
        return;
    }
    int mid = (l + r) >> 1;
    update(l, mid, si, x, lrt[rt]);
    update(mid + 1, r, si, x, rrt[rt]);
    pushup(rt);
}

void query(int l, int r, int qs, int qe, int x, int &rt) {
    if (!rt || flag || l > qe || r < qs) return;
    if (l >= qs && r <= qe) {
        if (tree[rt] <= x) flag = true;
        return;
    }
    int mid = (l + r) >> 1;
    query(l, mid, qs, qe, x, lrt[rt]);
    query(mid + 1, r, qs, qe, x, rrt[rt]);
}

int main(void) {
    int op, x, y1, y2, c;
    while (~scanf("%d", &op) && op != 3) {
        if (op == 0) clear();
        else if (op == 1) {
            scanf("%d%d%d", &x, &y1, &c);
            update(1, LIM, y1, x, rootPos[c]);
        } else if (op == 2) {
            scanf("%d%d%d", &x, &y1, &y2);
            int ans = 0;
            for (int i = 0; i <= 50; i++) {
                flag = false;
                query(1, LIM, y1, y2, x, rootPos[i]);
                if (flag) ans++;
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}

 

【2017ACM-ICPC广西邀请赛】Covering

【2017ACM-ICPC广西邀请赛】Covering

【递推+矩阵快速幂】

问题链接:https://vjudge.net/problem/HDU-6185

Solution 1:

这个是需要的思考较少的办法。暴力dfs算出\(n = 1 … 10\)时的answer,之后根据这个找到递推关系式,之后写出变换矩阵,采用矩阵快速幂来解决。

首先是暴力找前10个答案:

#include <iostream>
#include <cstring>
using namespace std;

const int LIM = 10;
bool vis[4][LIM];
int n;
int cnt = 0;

bool find(int & r, int & c) {
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < n; j++) {
            if (!vis[i][j]) {
                r = i;
                c = j;
                return true;
            }
        }
    }
    return false;
}

void bruteDfs() {
    int r, c;
    if (!find(r, c)) {
        cnt++;
        return;
    }
    if (r < 3 && !vis[r + 1][c]) {
        vis[r][c] = vis[r + 1][c] = true;
        bruteDfs();
        vis[r][c] = vis[r + 1][c] = false;
    }
    if (c < n - 1 && !vis[r][c + 1]) {
        vis[r][c] = vis[r][c + 1] = true;
        bruteDfs();
        vis[r][c] = vis[r][c + 1] = false;
    }
}

int main(void) {
    for (n = 1; n <= 10; n++) {
        memset(vis, false, sizeof vis);
        cnt = 0;
        bruteDfs();
        printf("4*%d : %d\n", n, cnt);
    }
    return 0;
}

得到前十组答案:

4*1 : 1
4*2 : 5
4*3 : 11
4*4 : 36
4*5 : 95
4*6 : 281
4*7 : 781
4*8 : 2245
4*9 : 6336
4*10 : 18061

接着就可以使用这几组数据推出递推式,假设每一项与前一项、前两项…前多项有关,手动高斯消元法逐个尝试求解,可以求出递推关系式,还有一种就是继续写程序暴力,发现递推关系式:

暴力求项数代码:

#include <iostream>

using namespace std;

int main(void) {
    for (int a1 = -10; a1 <= 10; a1++) {
        for (int a2 = -10; a2 <= 10; a2++) {
            for (int a3 = -10; a3 <= 10; a3++) {
                for (int a4 = -10; a4 <= 10; a4++) {
                    if (a1 * 1 + a2 * 5 + a3 * 11 + a4 * 36 == 95 &&
                            a1 * 5 + a2 * 11 + a3 * 36 + a4 * 95 == 281 &&
                            a1 * 11 + a2 * 36 + a3 * 95 + a4 * 281 == 781 &&
                            a1 * 36 + a2 * 95 + a3 * 281 + a4 * 781 == 2245) {
                        printf("f(n) = %df(n - 1) + %df(n - 2) + %df(n - 3) + %df(n - 4)\n", a4, a3, a2, a1);
                    }
                }
            }
        }
    }
    return 0;
}

输出:

f(n) = 1f(n - 1) + 5f(n - 2) + 1f(n - 3) + -1f(n - 4)

写成矩阵变换式:

接下来就可以正式编码了。

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;

const LL MOD = 1000000007;
struct Matrix {
    LL v[4][4];
    Matrix operator * (const Matrix & m) const {
        Matrix ret = {{0}};
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                for (int k = 0; k < 4; k++) {
                    ret.v[i][j] += (v[i][k] * m.v[k][j] + MOD) % MOD;       //注意v[i][k] * m.v[k][j]可能会变成负数,需要加上MOD
                    ret.v[i][j] %= MOD;
                }
            }
        }
        return ret;
    }
    void operator *= (const Matrix & m) {
        *this = *this * m;
    }
};
const Matrix base = {{{1, 5, 1, -1}, {1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}}};
LL start[] = {1, 5, 11, 36};

Matrix fastPow(Matrix x, LL pow) {
    Matrix ans = {{{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}}};
    while (pow) {
        if (pow & 1) ans *= x;
        x *= x;
        pow >>= 1;
    }
    return ans;
}

int main(void) {
    ios::sync_with_stdio(false);
    LL n;
    while (cin >> n) {
        if (n <= 4) cout << start[n - 1] << endl;
        else {
            Matrix fac = fastPow(base, n - 4);
            cout << (fac.v[0][0] * start[3]
                    + fac.v[0][1] * start[2]
                    + fac.v[0][2] * start[1]
                    + fac.v[0][3] * start[0]) % MOD << endl;
        }
    }
    return 0;
}

上边那里不加上MOD话,一个出错的例子是,对于输入1000000000,输出会是一个负数。

【2017ACM-ICPC广西邀请赛】Duizi and Shunzi

【2017ACM-ICPC广西邀请赛】Duizi and Shunzi

【贪心】

问题链接:https://vjudge.net/problem/HDU-6188

一些数据:

9

1 2 3 3 4 5 5 6 7

12

2 3 4 4 5 6 6 7 8 8 9 10

5

2 2 2 2 2

6

4 4 5 5 6 6

以上数据输出:

3

4

2

3

 

Solution:

解决这道题的核心在于贪心策略。对于任意连续的三个数,假设这三个数出现次数依此是a, b, c,如果组成顺子,显然个数为t = min(a, b, c),而组成对子,则有

ceil(a / 2) + ceil(b / 2) + ceil(c / 2).    【其中ceil()表示向下取整】

显然有如下关系:

ceil(a / 2) + ceil(b / 2) + ceil(c / 2) >= \(\frac{3t}{2}\).

这表明,对于三个连续数,优先取对子会得到较大的值,即对于任意数,优先组成对子。只有在一个数是奇数时才考虑顺子。

先考虑遇到一个数出现了奇数次数,现在需要考虑是否取顺子,这时要看它之后的两个数。如果它之后的两个数都不为0,若第二个数是偶数,则应该都拿对子,因为如果第三个数大于1时,拿顺子要比拿对子的数量至少多1【因为第二个数和第三个数各自组成对子】,这时就可以忽略第一个数即不用拿顺子了;当第二个数是偶数时,如果第三个数是1,这时拿对子至少能拿一个【即第二个数有两个】,而拿顺子则固定只能拿一个了【因为第一个数自己拿完对子后最多只能剩下1,且这里讨论的情况保证第三个数也只有1个】,所以我们那对子总不会差于拿顺子。当第二个数有奇数个时,先拿完对子,剩下了1个,此时第一个数也剩下了1个,只要第三个数不是0个,无论奇偶,拿第三个数全拿对子或在这里取一个顺子剩下的全拿对子没有区别,因为最多只会拆开一个对子,而拆开一个对子后我们又拿了一个顺子,最后数量不会变化。

由此得出贪心策略:

对于任意数,先按照对子将它取完,再看这样操作后是否还有剩余【即判断这个数原本出现的个数是奇数还是偶数】,如果有剩余,则考虑是否要取顺子,如果第二个数的数量是有奇数个且第三个数的数量不为0,则拿顺子,反之不拿顺子。

#include <iostream>
#include <cstring>

using namespace std;

const int LIM = 1e6 + 5;
int data[LIM];

int main(void) {
    int n, ans, t;
    while (~scanf("%d", &n)) {
        memset(data, 0, sizeof data);
        ans = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d", &t);
            data[t]++;
        }
        for (int i = 1; i <= n; i++) {
            ans += data[i] / 2;
            data[i] %= 2;
            if (data[i] && data[i + 1] && data[i + 1] % 2 && data[i + 2]) {
                ans++;
                data[i + 1]--;
                data[i + 2]--;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

 

【2017ACM-ICPC广西邀请赛】CS Course

【2017ACM-ICPC广西邀请赛】CS Course

【前后缀/位数统计+异或的运算性质】

问题链接:https://vjudge.net/problem/HDU-6186

Solution 1:

Core concept:

1. 对于一串数\(a_1, a_2 … a_n\),要求去掉\(a_p (p \in [1, n])\)后,求剩下全部数的与、或、异或的值,为了方便表述,我们将这里的运算用符号\(\oplus\)表示,则当前问题是求:

\(a_1 \oplus … a_{p – 1} \oplus a_{p + 1}… \oplus a_n = ?\).

显然上式等于:

\((a_1 \oplus … a_{p – 1}) \oplus (a_{p + 1} … \oplus a_n)\)

特殊的,对于\(p = 1 or n\),可通过去掉上式左侧圆括号内容或右侧圆括号内容使得等式成立。因此,我们可以开两个数组:

前缀数组pre(\(pre[i] = a_1 \oplus … \oplus a_{p – 1}\))

后缀数组suf(\(suf[i] = a_{p + 1} \oplus … \oplus a_n\)).

2.对于异或运算,我们也可以采用上边的办法,但是,由于有更好的办法(即利用异或运算性质),我们采用另一种办法。

关键:

b ^ b = 0(^表示异或),即一个数总是其自身的异或逆元。

a ^ b = b ^ a,即交换律。

所以我们将a_1 ^ … ^ a_n放到一个变量中(取名为xorans),则除去\(a_k\)后,答案应是:xorans ^ \(a_p\).

#include <iostream>

using namespace std;

const int LIM = 1e5 + 10;
struct node {
    int av, ov;     // "and value" and "or value"
};

int a[LIM];
node pre[LIM], suf[LIM];

int main(void) {
    int n, q;
    int xorans;
    while (~scanf("%d%d", &n, &q)) {
        xorans = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", a + i);
            xorans ^= a[i];
            pre[i].av = pre[i].ov = suf[i].av = suf[i].ov = a[i];
            if (i != 1) {
                pre[i].av &= pre[i - 1].av;
                pre[i].ov |= pre[i - 1].ov;
            }
        }
        for (int i = n - 1; i >= 1; i--){
            suf[i].av &= suf[i + 1].av;
            suf[i].ov |= suf[i + 1].ov;
        }
        int p;
        while (q--) {
            scanf("%d", &p);
            if (p == 1) printf("%d %d %d\n", suf[2].av, suf[2].ov, xorans ^ a[1]);
            else if (p == n) printf("%d %d %d\n", pre[n - 1].av, pre[n - 1].ov, xorans ^ a[n]);
            else printf("%d %d %d\n", pre[p - 1].av & suf[p + 1].av, pre[p - 1].ov | suf[p + 1].ov, xorans ^ a[p]);

        }
    }
    return 0;
}

 

Solution 2:

统计所有数各二进制位的1的个数,如果去掉a[k]后,某位上1的个数为n – 1,则与运算后该位是1;如果某位上1的个数大于0,则或运算后该位是1。

#include <iostream>
#include <cstring>
using namespace std;

const int LIM = 1e5 + 10;
const int BITS = 32;
int a[LIM];
int cnt[BITS];
int cnttmp[BITS];

int main(void) {
    int n, q;
    int xorans;
    while (~scanf("%d%d", &n, &q)) {
        memset(cnt, 0, sizeof cnt);
        xorans = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", a + i);
            xorans ^= a[i];
            int tmp = a[i];
            for (int i = 0; tmp; i++, tmp >>= 1)
                if (tmp & 1) cnt[i]++;
        }
        int p, andans, orans;
        while (q--) {
            andans = orans = 0;
            scanf("%d", &p);
            memcpy(cnttmp, cnt, sizeof cnt);
            int tmp = a[p];
            // 使用cnttmp数组来存储去掉a_p后,各位的1的个数
            for (int i = 0; tmp; i++, tmp >>= 1) {
                if (tmp & 1) cnttmp[i]--;
            }
            for (int i = BITS - 1; i >= 0; i--, tmp >>= 1) {
                andans <<= 1;
                orans <<= 1;
                if (cnttmp[i] == n - 1) andans |= 1;
                if (cnttmp[i] > 0) orans |= 1;
            }
            printf("%d %d %d\n", andans, orans, xorans ^ a[p]);
        }
    }
    return 0;
}

 

【2017ACM-ICPC广西邀请赛】A Math Problem

【2017ACM-ICPC广西邀请赛】A Math Problem

问题链接:https://vjudge.net/problem/HDU-6182

注意:k为15时超过1e18

方法:十分简单的一道题,直接枚举就好。

Solution:

#include <iostream>

using namespace std;

typedef unsigned long long ULL;

ULL fastPow(ULL a, ULL b) {
    ULL ret = 1;
    for (; b; b >>= 1) {
        if (b & 1) ret *= a;
        a *= a;
    }
    return ret;
}

int main(void) {
    ULL n;
    while (cin >> n) {
        ULL k;
        for (k = 1; k <= 15; k++)
            if (fastPow(k, k) > n) break;
        cout << k - 1 << endl;
    }
    return 0;
}