2017 Multi-University Training Contest - Team 1

时间:2023-01-12 04:29:29

hdu6033 Add More Zero(water)

求满足 2 m 1 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 1 e 5
问你有几个f数组满足: f i = b f a i 0 i 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 1 e 7 个数字,由 m m 100 次查询。
b b i b j , b i < b k b j < b k . b i + b j 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 i r i ,对于任意 1 L i R n ,当前仅当 l i L i R 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;
}