【HDU-5898】odd-even number【记忆化搜索】

【HDU-5898】odd-even number【记忆化搜索】

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

Solution:

看到这个问题自然会想到一个办法:搜索一下每个数就好。关键的问题就是,全部搜索会超时,这时注意到搜索过程中有大量重复过程,我们把那些搜索结果以及其对应的状态【五种状态:START开始,ENE (Even Number Even)偶数个偶数,ONE (Odd Number Even)奇数个偶数,ONO (Odd Number Odd)奇数个奇数,ENO (Even Number Odd)偶数个奇数】都存储下来就可以解决。

另外,搜索过程中用一些标识来说明当前这个数字是不是最高位、是不是该位的最大数字是有帮助的,这样就可以确定下一位进行枚举的时候的枚举范围。

另外还有个技巧是,题目要求寻找的是区间内的个数,但是这样很不方便搜索,那么我们把搜索的目标转移到小于等于某个数的所有符合题意的数的个数,这样只要用区间最大值搜一下个数减去区间最小值减一搜一下个数就好。

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;

enum {ENE ,ONE, ONO, ENO, START};
const int NIL = -1;
const int LIM = 20;
const int SIZE = 5;
int digit[LIM];
LL dp[LIM][SIZE];

inline bool isOdd(int x) { return x & 1; }

LL dfs(int crt, bool islead, bool hasLimit, int state) {
  if(crt == NIL) return (state == ONE || state == ENO) && !islead;
  if(!hasLimit && !islead && dp[crt][state] != NIL) return dp[crt][state];
  int upBound = hasLimit ? digit[crt] : 9;
  LL cnt = 0;
  for(int i = 0; i <= upBound; i++)
  {
    if(islead) {
            cnt += dfs(crt - 1,islead && !i,hasLimit && (i == upBound), isOdd(i) ? ONO : ONE);
    } else {
      if(state == ENO) cnt += dfs(crt - 1, false, hasLimit && (i == upBound), isOdd(i) ? ONO : ONE);
      if(state == ONO && isOdd(i)) cnt += dfs(crt - 1, false, hasLimit && (i == upBound), ENO);
      if(state == ONE) cnt += dfs(crt - 1, false, hasLimit && (i == upBound), isOdd(i) ? ONO : ENE);
      if(state == ENE && !isOdd(i)) cnt += dfs(crt - 1, false ,hasLimit && (i == upBound), ONE);
    }
  }
  if(!hasLimit && !islead) dp[crt][state] = cnt;
  return cnt;
}
LL getNum(LL x) {
    memset(dp, NIL, sizeof(dp));
  int crt = 0;
  while(x) {
    digit[crt++] = x % 10;
    x /= 10;
  }
  return dfs(crt - 1, true, true, START);
}

int main() {
    int t;
  scanf("%d",&t);
  for(int k = 1; k <= t; k++) {
    LL left, right;
    scanf("%lld%lld", &left, &right);
    printf("Case #%d: %lld\n", k, getNum(right) - getNum(left - 1));
  }
    return 0;
}

 

 

【HDU-5892】Resident Evil【2-D Binary Indexed Tree】

【HDU-5892】Resident Evil【2-D Binary Indexed Tree】

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

Solution:

类似于区域和的查询及更新,使用二维树状数组,但是这道题有点特殊,特殊之处在于:如果对区域内每个点都进行一次更新调用的话,会超时。注意到我们仅仅是在做异或运算,而树状数组的查询得到的相当于是一种“前缀和”,下面暂时以一维树状数组来理解:如果我们对一个左端点为奇数的区间中每个点进行更新,最后必然得到区间内奇数点更新奇数次,偶数点更新偶数次;反过来,如果左端点是偶数,则必然偶数点更新奇数次、奇数点更新偶数次【注意:这里所说的更新不是指树状数组下标奇偶的更新情况,而是指更新结束后的最终效果,由于树状数组的查询结果是前缀,所以每当一个点进行更新时,后面所有点的查询返回值都会进行更新,就出现了上面的结果】,由于我们在做异或运算,偶数次更新不需要做,所以只需要根据左端点的情况单独对奇数或偶数两种情况进行更新就好,即对于奇数、偶数分开维护树状数组。这时还有一件事需要处理,我们不能只根据左端点更新完就结束,还要根据右端点来做一个“补充”,详情是这样的:对于左端点是奇数的情况,如果右端点也是奇数,那么右端点后的所有数都具有奇数次更新,这时,对于奇数的树状数组,我们不需要做任何操作,因为根据左端点的更新已经更新了所有奇数树状数组的值了,但是对于偶数的树状数组,我们需要对右端点值加1的点进行一次更新;当右端点是偶数时,它之后的奇数都具有偶数次更新,也就是不应该异或,但是左端点在更新时都对它们做了异或,我们仍然需要对右端点值加1的点进行一次更新【左端点是偶数的情况也能够推出这个结论,这里省略】。

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;
const int LIM = 3010;
LL bit[2][2][LIM][LIM];
int n, m;

void update(int x, int y, LL diff) {
    for (int i = x; i <= n; i += i & (-i)) {
        for (int j = y; j <= n; j += j & (-j)) {
            bit[x & 1][y & 1][i][j] ^= diff;
        }
    }
}

LL query(int x, int y) {
    LL ret = 0;
    for (int i = x; i; i -= i & (-i)) {
        for (int j = y; j; j -= j & (-j)) {
            ret ^= bit[x & 1][y & 1][i][j];
        }
    }
    return ret;
}

int main(void) {
    char op[3];
    int lx, ly, rx, ry, cnt, a, b;
    LL tmp;
    scanf("%d%d", &n, &m);
    while (m--) {
        scanf("%s%d%d%d%d", op, &lx, &ly, &rx, &ry);
        if (op[0] == 'Q') {
            tmp = query(rx, ry) ^ query(rx, ly - 1) ^ query(lx - 1, ry) ^ query(lx - 1, ly - 1);
            for (int i = 0; i < 50; i++)
                printf("%d ", (tmp >> i) & 1 ? 2 : 1);
            putchar('\n');
        } else {
            scanf("%d", &cnt);
            tmp = 0;
            while (cnt--) {
                scanf("%d%d", &a, &b);
                if (b & 1) tmp ^= 1ll << (a - 1);
            }
            update(lx, ly, tmp);
            update(rx + 1, ly, tmp);
            update(lx, ry + 1, tmp);
            update(rx + 1, ry + 1, tmp);
        }
    }
    return 0;
}

 

【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

【HDU-6235】Permutation

【HDU-6235】Permutation

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

Solution:

Special Judge,想出来如何构造后,会感叹竟然有这么简单的题,先在奇数位置上从1开始每次递增1排过去,奇数位置排完,接着排偶数位置,这样任意相间排列的数之差都是1,显然1是任何数的因数。

#include <iostream>

using namespace std;

int main(void) {
    int t, n;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        int bound = (n + 1) / 2;
        for (int i = 1; i <= bound; i++) {
            if (i - 1) putchar(' ');
            printf("%d", i);
            putchar(' ');
            if (i + bound <= n) printf("%d", i + bound);
        }
        putchar('\n');
    }
    return 0;
}

 

【HDU-6231】K-th Number【尺取法+二分】

【HDU-6231】K-th Number【尺取法+二分】

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

Solution:

对于n个数,长度为k的区间共有\(\sum _1^{n – k}\)个,如果暴力枚举每一个区间的第k大值后排序找第m大的数,复杂度会很高,因此我们这里采用二分法。二分的思路比较独特,假设一个值\(v\)是最后结果,则v应该满足条件:由v或大于v的数作为第k大元素的区间的个数刚好有m个。如果将v的值减小一些,则这样的区间数会增多,反之这样的区间数会减少。因此二分的判断思路是,对于任意一个v,如果由v或大于v的数作为第k大元素的区间的个数大于m个,则说明当前尝试的v太小了,应该增大一些,反之,应当更小一些,根据这个思路进行二分,最后就可以找到解。

注:下面的实现中,由于当区间个数大于等于m的时候,都会去mid的右边寻找,也就是区间[mid + 1, r],因此如果假设答案是ans,最后l和r会逼近ans + 1,所以输出的时候需要输出l – 1.

#include <iostream>

using namespace std;

typedef long long LL;

const int LIM = 1e5 + 10;
int arr[LIM];
int n, k;
LL m;

bool deter(int v) {
    int num = 0, lp = 0;
    LL cnt = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] >= v) num++;
        if (num == k) {
            cnt += n - i;
            while (arr[lp] < v) {
                lp++;
                cnt += n - i;
            }
            num--;
            lp++;
        }
    }
    return cnt >= m;
}

int main(void) {
    int t;
    scanf("%d", &t);
    while (t--) {
        int l = 1, r = 0;
        scanf("%d%d%lld", &n, &k, &m);
        /* input the data */
        for (int i = 0; i < n; i++) {
            scanf("%d", arr + i);
            if (arr[i] > r) r = arr[i];
        }
        r++;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (deter(mid)) l = mid + 1;
            else r = mid;
        }
        printf("%d\n", l - 1);
    }
    return 0;
}

 

【HDU-5869】Different GCD Subarray Query

【HDU – 5869】Different GCD Subarray Query

【2016 ACM/ICPC Asia Regional Dalian Online】

【gcd+离线查询+树状数组】

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

Solution:

对于单次查询的暴力复杂度\(O(n^2)\),q次查询\(O(qn^2)\)显然不行,所以我们用下面这种策略:

考虑一下这个问题,如果对于一个固定的右端点(假设右端点5),

我们可以找到这个区间中所有不同gcd值的最右最小区间(原因在后面解释),

如果开一个数组,以左端点为下标,存储上图中以下标为左端点的区间的个数,则可以得到数组arr:

接下来,以输入样例中的查询”3 5″,只要算出上面arr[5] – arr[3 -1],也就是从下标从3到5的和,就可以得到答案。

因为我们一直选取的是最右区间,所以可以将每个同gcd值的最右最小区间种类数存放到左端点那里,这个问题就转化成对于一个数组区间求和问题,从直观上理解,只要一次查询包含这个最小最右区间,它就一定有该种gcd值。

对于求和,我们显然可以使用树状数组来优化这一过程,即使用左端点下标作为树状数组的下标,而上图的计数作为树状数组维护的值。

注意,上边我们所做的讨论一直是以右端点固定在5为前提的,到目前为止,我们解决了对于单个固定右端点时这个问题的解,当前这个问题则可以理解成它的“升级版”,多个右端点时这个问题的解。

我们显然可以由上一个右端点的所有最右区间推知下一个右端点的所有最小最右区间。于是我们可以开一个vector数组,将第i个右端点的最右区间放到这个数组的i号vector中,之后将多次询问按照右端点排序,接着一边从左到右维护树状数组,一边查询以当前遍历到的点为右端点的所有查询,最后按照输入的顺序输出,这个问题就可以得到解决。

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
// #define DBG
using namespace std;

const int LIM = 1e5 + 10;
const int MAXI = 1e6 + 10;
struct query {
    int l, r, idx;
    bool operator < (const query & q) const {
        return r < q.r;
    }
} qs[LIM];
int data[LIM];
int bit[LIM];
int vis[MAXI];
int ans[LIM];
int n;
vector<pair<int, int> > gcds[LIM];

inline int gcd(int a, int b) {
    return a % b ? (gcd(b, a % b)) : b;
}

inline int lowbit(int x) {
    return x & (-x);
}

void add(int pos, int diff) {
    while (pos < n) {
        bit[pos] += diff;
        pos += lowbit(pos);
    }
}

int getSum(int pos) {
    int ret = 0;
    while (pos) {
        ret += bit[pos];
        pos -= lowbit(pos);
    }
    return ret;
}

int main(void) {
    int q;
    while (~scanf("%d%d", &n, &q)) {
        for (int i = 1; i <= n; i++) {
            scanf("%d", data + i);
            gcds[i].clear();
        }
        /* discretization */
        for (int i = 1; i <= n; i++) {
            int g = data[i], lp = i;
            for (int j = 0; j < gcds[i - 1].size(); j++) {
                int tmpg = gcd(g, gcds[i - 1][j].first);
                if (g != tmpg) {
                    gcds[i].push_back(make_pair(g, lp));
#ifdef DBG
                    printf("[%d] : (%d, %d)\n", i, g, lp);
#endif
                    g = tmpg;
                    lp = gcds[i - 1][j].second;
                }
            }
            gcds[i].push_back(make_pair(g, lp));
#ifdef DBG
            printf("[%d] : (%d, %d)\n", i, g, lp);
#endif
        }
        /* input the query and sort them */
        for (int i = 0; i < q; i++) {

            scanf("%d%d", &qs[i].l, &qs[i].r);
            qs[i].idx = i;
        }
        sort(qs, qs + q);
        /* operation of the binary index tree */
        memset(vis, 0, sizeof vis);
        memset(bit, 0, sizeof bit);
        int pos = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < gcds[i].size(); j++) {
                int g = gcds[i][j].first;
                int lp = gcds[i][j].second;
                if (vis[g]) add(vis[g], -1);
                add(lp, 1);
                vis[g] = lp;
            }
            while (qs[pos].r == i) {
                ans[qs[pos].idx] = getSum(qs[pos].r) - getSum(qs[pos].l - 1);
                pos++;
            }
#ifdef DBG
            printf("-----------------\n");
            for (int i = 1; i <= 5; i++)
                printf("%d: %d\n", i, bit[i]);
#endif
        }
        for (int i = 0; i < q; i++) {
            printf("%d\n", ans[i]);
        }
    }
    return 0;
}