2017 Multi-University Training Contest - Team 1

求满足 $2^{m} - 1 \geq 10^{k}$ 的最大的k。

　　也就是说，求解位数。那非常简单，log一下就出来了。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int m, cas = 1;
    while(~scanf("%d", &m))
    {
        printf("Case #%d: %d\n", cas++, (int)(m * log10(2)));
    }
    return 0;
}

hdu6034 Balala Power!（大数+贪心）

给你n串字符串，其总长度不超过1e6，让你给出a-z到0-25的映射，使26进制的字符串对应的数字之和最大。

　　这道题其实非常简单，不要想歪了，先把每个字母的权重定为1，直接做一个大数的加和就好了。然后根据每个字母的加和结果排个序，贪心的加上映射就好了。
　　！但是有一个细节，前导零。在n个字符串的首位中出现过的字母不应该被映射为0。（字符串长度>=2时）

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 100000 + 5;
const int mod = 1e9 + 7;

//******
struct node
{
    int id;
    int a[maxn];
    bool operator < (const node &other)const
    {
        for(int i = maxn - 1; i >= 0; i --)//从大到小排序
        {
            if(a[i] != other.a[i])   return a[i] > other.a[i];
        }
        return false;
    }
}nodes[30];
char s[maxn];
string str[maxn];
int change[130];
int noZero[30];
LL mi[maxn];
//******

int main()
{
    mi[0] = 1;
    for(int i = 1; i < maxn; i++)
    {
        mi[i] = mi[i - 1] * 26 % mod;
    }

    int n, cas = 1;
    while(~scanf("%d", &n))
    {
        for(int i = 0; i < 26 ; i++)
        {
            for(int j = 0; j < maxn; j++)
            {
                nodes[i].a[j] = 0;
            }
            nodes[i].id = i;
            noZero[i] = 0;
        }

        for(int i = 0; i < n; i++)
        {
            scanf("%s", s);
            str[i] = s;
            int len = strlen(s);
            noZero[s[0] - 'a'] = 1;
            for(int j = len - 1; j >= 0; j--)
            {
                int idx = s[j] - 'a';
                nodes[idx].a[len - 1 - j]++;
            }
        }
        for(int i = 0; i < 26; i++)
        {
            for(int j = 0; j < maxn; j++)
            {
                nodes[i].a[j + 1] += nodes[i].a[j] / 26;
                nodes[i].a[j] %= 26;
            }
        }
        //比赛的时候 想法问题很大。这题应该直接上大数就解决了的。走了一个错误的方向。
        sort(nodes, nodes + 26);

        int temp = 25;
        for(int i = 0; i < 26; i++)
        {
            change[nodes[i].id + 'a'] = temp--;
        }
        if(noZero[nodes[25].id])
        {
            for(int i = 24; i >= 0; i--)
            {
                if(noZero[nodes[i].id] == 0)
                {
                    change[nodes[i].id + 'a'] = 0;
                    for(int j = i + 1; j <= 25; j++)
                    {
                       change[nodes[j].id + 'a'] += 1;
                    }
                    break;
                }
            }
        }
        LL ans = 0;
        for(int i = 0; i < n; ++i)
        {
            int len = str[i].length();
            for(int j = 0; j < len; ++j)
            {
                char ch = str[i][j];
                int miID = len - 1 - j;
                ans = (ans + mi[miID] * change[ch] % mod ) % mod;
            }
        }
        printf("Case #%d: %lld\n", cas++, ans);
    }
    return 0;
}

hdu6035 Colorful Tree（树形dp）

定义每条路径上的费用，是这条路径上的颜色的种类数。最后求整棵树，所有路径的费用加和是多少。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 200000 + 5;
int c[maxn];//记录每个节点的颜色
int sum[maxn], siz[maxn];
vector<int>G[maxn];
LL ans = 0;
void dfs(int u, int fa)
{
    siz[u] = 1;
    int col = c[u];//根节点的颜色是col
    int cnt = 0, pre = sum[col];
    for(auto v : G[u])  if(v != fa)
    {
        dfs(v, u);
        siz[u] += siz[v];//累加子树大小
        int block = siz[v] - (sum[col] - pre);//这条链上有多少个点可形成新的联通块。
        ans -= 1LL * block * (block - 1) / 2;
        cnt += (sum[col] - pre);//累计原有的
        pre = sum[col];
    }
    sum[col] += siz[u] - cnt;//去除原有的（也就是根结点颜色为col，但是和颜色也为col的结点u不是最近的。
}

int main()
{
    int n;
    for(int cas = 1; scanf("%d", &n) == 1; cas++)
    {
        memset(sum, 0, sizeof(sum));
        for(int i = 1; i <= n; i++) G[i].clear();
        set<int>s;
        for(int i = 1; i <= n; i++) scanf("%d", &c[i]), s.insert(c[i]);
        int totCol = s.size();
        for(int i = 0; i < n - 1; i++)
        {
            int u, v;
            scanf("%d%d", &u, &v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        //所求答案：每条路径上至少出现一次的颜色数量之和。
        //也等于 总数量 - 每条路径上不出现的颜色数量之和。
        ans = 1LL * totCol * n * (n - 1) / 2;
        dfs(1, -1);

        for(int i = 1; i <= n; i++)
        {
            if(sum[i])
            {
                LL temp = n - sum[i];
                ans -= 1LL * temp * (temp - 1) / 2;
            }
        }
        printf("Case #%d: %lld\n", cas, ans);
    }
    return 0;
}

hdu6036（挺难的NTT）
hdu6037（都没题解QAQ）
hdu6038 Function

a数组是0-n-1的全排列，b数组是0到m-1的全排列。 $n, m \leq 1 e 5 。$
问你有几个f数组满足： $f_{i} = b_{f_{a_{i}}} （ 0 \leq i \leq n - 1 ）$

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 100000 + 5;
const int mod = 1e9 + 7;
int a[maxn], b[maxn];
int num1[maxn], num2[maxn];
int vis[maxn];
void getLoop(int a[], int n, int num[])
{
    memset(vis, 0, sizeof(vis));
    for(int i = 0; i < n; i++)
    {
        int st = i, len = 0;
        while(vis[st] == 0)
        {
            vis[st] = 1;
            len++;
            st = a[st];
        }
        num[len]++;
    }
}
LL quickPow(LL a, LL b, LL Mod)
{
    LL ret = 1;
    while(b)
    {
        if(b & 1)   ret = ret * a % Mod;
        b >>= 1;
        a = (a * a) % Mod;
    }
    return ret;
}

vector<int>G[maxn];//G[i]:i的因子们
int main()
{
    int limit = 100000;
    for(int i = 1; i <= limit; i++)
    {
        for(int j = i; j <= limit; j += i)
        {
            G[j].push_back(i);
        }
    }

    int n, m, cas = 1;
    while(~scanf("%d%d", &n, &m))
    {
        for(int i = 0; i < n; i++)  scanf("%d", &a[i]);
        for(int j = 0; j < m; j++)  scanf("%d", &b[j]);
        memset(num1, 0, sizeof(num1));
        memset(num2, 0, sizeof(num2));
        getLoop(a, n, num1);

        getLoop(b, m, num2);
        long long ans = 1;
        for(int i = 1; i <=100000; i++)
        {
            if(num1[i] == 0)    continue;
            long long temp = 0;
            for(auto o : G[i])
            {
                temp = (temp + o * num2[o] % mod) % mod;
            }
            temp = quickPow(temp, num1[i], mod);
            ans = (ans * temp) % mod;
        }
        printf("Case #%d: %lld\n", cas++, ans);
    }
    return 0;
}

hdu6039 Gear Up

hdu6040 Hints of sd0061（类斐波那契+nth_element）

给出 $n （ n \leq 1 e 7 ）$ 个数字，由 $m （ m \leq 100 ）$ 次查询。
$对于查询数组 b ，所有 b_{i} \neq b_{j}, b_{i} < b_{k} ， b_{j} < b_{k} . ，满足 b_{i} + b_{j} \leq b_{k}$
$第 i 次查询问第 b [i] + 1 小$ 的数是多少。

　　库函数nth_element（a，a + k，a + n）。它在a[0] - a[n - 1]中，求第k小的元素,并把它放在第k位置上,下标是从0开始计数的,也就是说求第0小的元素就是最小的数。查询复杂度平摊是O（n）。
　　离线查询，排序以后，每次查询复杂度都是O（n）。因为查询数组，是一个类似斐波那契的数组，所以查询复杂度可接受。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e7 + 7;

int n, m;
unsigned A, B, C;
unsigned x, y, z;
unsigned a[maxn], ans[maxn];
unsigned rng61() {
  unsigned t;
  x ^= x << 16;
  x ^= x >> 5;
  x ^= x << 1;
  t = x;
  x = y;
  y = z;
  z = t ^ x ^ y;
  return z;
}
pair<int, int>b[105];
#define query first
#define id second

int main()
{
    for(int cas = 1; ~scanf("%d%d%u%u%u", &n, &m, &A, &B, &C); cas++)
    {
        for(int i = 0; i < m; i++)  scanf("%d", &b[i].query), b[i].id = i;
        sort(b, b + m);

        x = A, y = B, z = C;
        for(int i = 0; i < n; i++)  a[i] = rng61();

        b[m].query = n;
        for(int i = m - 1; i >= 0; i--)
        {
            int k = b[i].query, idx = b[i].id;
            nth_element(a, a + k, a + b[i + 1].query);
            ans[idx] = a[k];
        }
        printf("Case #%d:", cas);
        for(int i = 0; i < m; i++)  printf(" %u", ans[i]);
        puts("");
    }
    return 0;
}

hdu6041 I Curse Myself

hdu6042 Journey with Knapsack（母函数）

hdu6043 KazaQ’s Socks（water）

KazaQ有n双袜子，标号1到n放在柜子里，每天早上起床穿袜子选标号最小的一双。然后晚上回来将穿过的扔到篮子里。当篮子里的袜子数量为n-1的时候，就把这些袜子洗一下，第二天晚上再放回柜子里。问KazaQ在第K天穿的是哪一个标号的袜子。

　　自己画一画就会发现简单的规律，大概是123…n 123..n-1 123…n 123..n-1 123…n 123..n-1 123…n。编码实现即可。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    long long k;
    for(int cas = 1; ~scanf("%d%lld", &n, &k); cas++)
    {
        long long ans = 0;
        if(n >= k)
        {
            ans = k;
        }
        else
        {
            k -= n;
            long long mod = k % (n - 1);
            long long times = (k + n - 2) / (n - 1);
            if(mod == 0)    ans = n - 1 + (1 - (times & 1));
            else ans = mod;
        }
        printf("Case #%d: %lld\n", cas, ans);
    }
    return 0;
}

hdu6044 Limited Permutation（思维+阶乘取模）

给定n个区间，对于第i个区间[ $l_{i}, r_{i}$ ]有 $l_{i} \leq i \leq r_{i}$ ,对于任意 $1 \leq L \leq i \leq R \leq n$ ，当前仅当 $l_{i} \leq L \leq i \leq R \leq r_{i}$ 时 $P [i] = m i n (P [L], P [L + 1], . . ., P [R])$ 。
或者说给出两组序列 $l [i], r [i] ，代表以 p [i]$ 为最小值所在的区间的边界。
问满足这些条件的序列 p 的个数.

　　注意“if and only if”理解题意。由于当且仅当，则对于区间 $[l_{i}, r_{i}]$ ，必定有 $p [i] > p [l i - 1] 并且 p [i] > p [r i + 1]$ 那么1所在的区间一定是 $[1, n]$ 。
　　之后我们可以不断的通过询问区间来划分，比如，对于区间 $[l, r]$ 而言，可以知道最小值的下标是idx，那么划分出两个子区间 $[l, i d x - 1], [i d x + 1, r]$ 。
　　 $设定 [l, r] 母区间的方案数 f [u]$
　　 $f [u] = f [l e f t] * f [r i g h t] * C (l e f t + r i g h t 区间的元素数量， l e f t 的元素数量)$
　　

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 6;
const int mod = 1e9 +7;
typedef long long LL;
namespace IO {
    const int MX = 4e7; //1e7占用内存11000kb
    char buf[MX]; int c, sz;
    void begin() {
        c = 0;
        sz = fread(buf, 1, MX, stdin);
    }
    inline bool read(int &t) {
        while(c < sz && buf[c] != '-' && (buf[c] < '0' || buf[c] > '9')) c++;
        if(c >= sz) return false;
        bool flag = 0; if(buf[c] == '-') flag = 1, c++;
        for(t = 0; c < sz && '0' <= buf[c] && buf[c] <= '9'; c++) t = t * 10 + buf[c] - '0';
        if(flag) t = -t;
        return true;
    }
}
LL fac[maxn], invf[maxn];
LL quickpow(LL a, LL x, LL mod)
{
    a %= mod;
    LL ret = 1;
    while(x)
    {
        if(x & 1)   ret = ret * a % mod;
        x >>= 1;
        a = (a * a) % mod;
    }
    return ret;
}

void init(int n)
{
    fac[0] = 1;
    for(int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
    invf[n] = quickpow(fac[n], mod - 2, mod);
    for(int i = n - 1; i >= 0; i--) invf[i] = invf[i + 1] * (i + 1) % mod;
}
LL C(LL n, LL m)
{
    LL ret = 0;
    ret = fac[n] * invf[m] % mod * invf[n - m] % mod;
    return ret;
}

struct node
{
    int l, r, id;
    bool operator < (const node &other)const
    {
        if(l != other.l)    return l < other.l;
        return r > other.r;
    }
}nodes[maxn];

int idx = 1;
int badboy = 0;
LL solve(int left, int right)
{
    if(badboy)  return 0;
    if(left > right)   return 1;
    if(left != nodes[idx].l || right != nodes[idx].r)
    {
        badboy = 1;
        return 0;
    }
    node temp = nodes[idx++];
    LL ret = C(temp.r - temp.l, temp.id - temp.l);

    ret = ret * solve(temp.l, temp.id - 1) % mod;
    ret = ret * solve(temp.id + 1, temp.r) % mod;
    return ret % mod;
}
int main()
{
    IO::begin();
    init(1e6);
    int n;
    for(int cas = 1; IO::read(n); cas ++)
    {
        for(int i = 1; i <= n; i++) IO::read(nodes[i].l);
        for(int i = 1; i <= n; i++) IO::read(nodes[i].r), nodes[i].id = i;

        sort(nodes + 1, nodes + 1 + n);

        idx = 1;badboy = 0;
        LL ans = solve(1, n);
        printf("Case #%d: %lld\n", cas, ans);
    }
    return 0;
}

秒客网

2017 Multi-University Training Contest - Team 1

相关文章