思维

HDU 6038 Function

Posted on

多校第一场没有怎么想的题,然而实际上是很简单的……就是题意在理解上有点绕。

题意:
给你两个序列a和b,每个序列中的每个元素各不相同,且分别为 [0,num)
要你求满足如下函数的数量。\( f ( i ) = b_{ f(a_i) } \)

思路:
一般人一眼就可以看出是一个递归的函数过程。
每次当我们知道了 \( f(i) \) ,我们就可以很顺利地得出 \( f(a_i) \) ,知道了 \( f(a_i) \) ,我们就可以很顺利的知道 \( f( a_{a_i} ) \)

又因为序列的特性,则对于这个函数,在a序列上必定会存在一个环。
而相应的,在a序列上的一个环与b序列上的元素相对应起来,只有在b序列上存在a序列环的因子才能成立。这个真的只要随便意淫一下就可以了,你要我证明我想还真有点烦

因此只要求出两个序列的环,对于每一对a序列的环与b序列的环,如果b序列环是a序列环的因子,则加上b序列环长度,因为对于a序列上的一个固定点,每一个b序列环上的点都可以对应与a序列固定点,且对应关系必不相同。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;

int a[maxn], b[maxn];
bool vis[maxn];
vector<int> xa, xb;

int dfs(int pos, int ary[], int len)
{
    if (vis[pos])
        return len;
    vis[pos] = true;
    return dfs(ary[pos], ary, len + 1);
}

int main()
{
    int n, m, cas = 0;
    while (scanf("%d%d", &n, &m) != EOF) {
        each(i, n) scanf("%d", a + i);
        each(i, m) scanf("%d", b + i);
        fill(vis, false), xa.clear(), xb.clear();
        each(i, n) if (!vis[i]) xa.push_back(dfs(i, a, 0));
        fill(vis, false);
        each(i, m) if (!vis[i]) xb.push_back(dfs(i, b, 0));
        int sa = xa.size(), sb = xb.size();
        ll ans = 1;
        each(i, sa)
        {
            ll tmp = 0;
            each(j, sb) if (xa[i] % xb[j] == 0)(tmp += xb[j]) %= mod;
            ans = (ans * tmp) % mod;
        }
        printf("Case #%d: %lld\n", ++cas, ans);
    }
    return 0;
}
贪心

HDU 6034 Balala Power!

Posted on

多校第一场的恶心题……因为前几天补题数量太多,博客一直没写,现在补上……

这道题我整整写了一个下午+晚上,mmp,一方面是题目本身恶心,另一方面也反映了我的脑子问题。

题意:
给你指定数量的小写字符串,让你把字母,转化成数字,也就是说 a-z 各自对应 0-25。要求所得数字和最大。
同时转化出的数字不能出现前导零。

思路:
将每个字符的贡献转化成一个25进制的数,用一个 26× 1e5 的数组存储,将其进行排升序。
再是考虑前导零的情况,反向遍历找到第一个不存在前导零的数字标记一下即可。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;

int n, len, max_len;
char buf[maxn];
ll mul[maxn];
bool lead[30];
int a[30];

struct ch {
    int num[maxn];
    int pos;
    void init(int id)
    {
        pos = id;
        memset(num, 0, sizeof num);
    }
    bool operator<(const ch& a) const
    {
        for (int i = max_len - 1; i >= 0; i--) {
            if (num[i] != a.num[i])
                return num[i] < a.num[i];
        }
        return false;
    }
} key[27];

int change(char sen[])
{
    int len = strlen(sen);
    for (int i = 0; i < len / 2; ++i) {
        char ch = sen[i];
        sen[i] = sen[len - i - 1];
        sen[len - i - 1] = ch;
    }
    return len;
}

int main()
{
    mul[0] = 1;
    for (int i = 1; i < maxn; i++)
        mul[i] = mul[i - 1] * 26 % mod;
    int cas = 0;
    while (scanf("%d", &n) != EOF) {
        for (int i = 0; i < 26; i++)
            key[i].init(i), lead[i] = false;
        max_len = 0;
        while (n--) {
            scanf("%s", buf);
            len = change(buf);
            if (len > 1)
                lead[buf[len-1] - 'a'] = true;
            max_len = max(max_len, len);
            for (int i = 0; i < len; ++i)
                key[buf[i] - 'a'].num[i]++;
        }
        for (int i = 0; i < 26; ++i) {
            for (int j = 0; j < max_len; ++j) {
                key[i].num[j + 1] += key[i].num[j] / 26;
                key[i].num[j] %= 26;
            }
            while (key[i].num[max_len] > 0) {
                key[i].num[max_len + 1] += key[i].num[max_len] / 26;
                key[i].num[max_len++] %= 26;
            }
        }
        sort(key, key + 26);
        int zero = -1;
        for (int i = 0; i < 26; ++i)
            if (!lead[key[i].pos]) {
                zero = key[i].pos;
                break;
            }
        ll res = 0, x = 25;
        for (int i = 25; i >= 0; --i) {
            if (key[i].pos != zero) {
                for (int j = 0; j < maxn; j++)
                    res = (res + x * key[i].num[j] * mul[j] % mod) % mod;
                x--;
            }
        }
        printf("Case #%d: %lld\n", ++cas, res);
    }
    return 0;
}