2017 Chinese Multi-University Training, BeihangU Contest

A Add More Zero

题目链接
题意：用m个二进制位可以表示10^k，给定m，问k最大是多少
思路：换底计算

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e5 + 5;
    using ll = long long;

    int main() {
        int n;
        int ca = 0;
        while (~scanf("%d", &n)) {
            int ans;
            ans = (int)ceil(1.0*n*log10(2.0))-1;
            printf("Case #%d: %d\n", ++ca,ans);
        }
    }

B Balala Power!

题目链接
题意：将一些字母串转换为26进制的数字，每个字母对应一个数字，要求这些字母转换成数后和最大，并且不能包含前导零
思路：大数比较、模拟、进制转换

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

    typedef long long ll;
    using namespace std;
    const int mod = 1e9 + 7;
    char a[100005];
    int val[30][100005];
    struct node{
        int no, score, lead;    
    }rankk[30], t;
    bool cmp(node x,node y){
        return x.score > y.score;
    }
    int main(){
        int cas=1,n, maxl;
        ll sum;
        while(scanf("%d",&n)!=EOF){
            for(int i=0;i<26;i++){
                rankk[i].no = i;
                rankk[i].score = 0;
                rankk[i].lead = 0;
            }
            maxl = 0;
            memset(val,0,sizeof val);
            for(int i=1;i<=n;i++){
                scanf("%s",a);
                int len=strlen(a);
                maxl = max(maxl,len);
                for(int j=0;j<len;j++){
                    val[a[j]-'a'][len - j - 1]++;
                }
                rankk[a[0] - 'a'].lead++;
            }
            for(int i=0;i<26;i++){
                for(int j=0;j<maxl-1;j++){
                    val[i][j+1] += val[i][j] / 26;
                    val[i][j] %= 26;
                }
            }
            for(int i=0;i<25;i++){
                for(int j=i + 1;j<26;j++){
                    for(int k=maxl-1;k >= 0;k--){
                        if(val[i][k] > val[j][k]){
                            rankk[i].score++;
                            break;
                        }
                        else if(val[i][k] < val[j][k]){
                            rankk[j].score++;
                            break;
                        }
                    }
                }
            }
            sum = 0;
            sort(rankk,rankk+26,cmp);
            if(rankk[25].lead){
                for(int i = 24;i >= 0;i--){
                    if(!rankk[i].lead){
                        t = rankk[i];
                        for(int j = i;j < 25;j++){
                            rankk[j] = rankk[j + 1];
                        }
                        rankk[25] = t;
                        break;
                    }
                }
            }
            for(int i=0;i<26;i++){
                ll res = 1;
                for(int j=0;j<maxl;j++){
                    sum = (sum + res * (25 - i) % mod * val[rankk[i].no][j]) % mod;
                    res = res * 26 % mod;
                    //cout << sum << endl; 
                }
                //cout << sum << endl;
            }
            printf("Case #%d: %I64d\n",cas++,sum);
        }
    }

F Function

题目链接
题意：求一个n的排列A到m的排列B的映射，要求f(i)=b(f(a(i)))，求方案数。
思路：由f(i)可以推知f(a(i))，由于是排列到排列的映射，i->a(i)->a(a(i))...最终一定会回到它自身，从而形成一个环。即a的某个长度为x环可以和b中长度为x因子的环构成函数。
Tarjin求强联通，计算即可。

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e5 + 5;
    int a[maxn], b[maxn];
    int vis[maxn];
    vector<int>v, G[maxn];
    int c[maxn];
    int tuan = 0;

    void dfs(int x) {
        //cout << "dfs:  " << x << endl;
        tuan++;
        if (vis[b[x]] == -1) {
            vis[b[x]] = 1;
            dfs(b[x]);
        }
    }

    int dfn[maxn], low[maxn], ins[maxn], stk[maxn];
    int num = 0, top = 0, cnt = 0;

    void tarjan(int x) {
        dfn[x] = low[x] = ++num;
        stk[++top] = x;
        ins[x] = 1;
        for (int y : G[x]) {
            if (!dfn[y]) {
                tarjan(y);
                low[x] = min(low[x], low[y]);
            }
            else if (ins[y]) {
                low[x] = min(low[x], dfn[y]);
            }
        }
        if (dfn[x] == low[x]) {
            cnt++;
            int yy;
            do {
                yy = stk[top--]; ins[yy] = 0;
                c[yy] = cnt;
            } while (x != yy);
        }
    }
    unordered_map <int, int>book;
    int n, m;

    void init() {
        num = 0, top = 0, cnt = 0;
        for (int i = 0; i <= n; i++) {
            c[i] = 0;
            G[i].clear();
            dfn[i] = 0;
        }
        book.clear();
        v.clear();
    }

    int main() {
        int cas=1;
        while (~scanf("%d%d", &n, &m)) {
            init();
            for (int i = 0; i < n; i++) {
                scanf("%d", &a[i]);
            }
            for (int i = 0; i < m; i++) {
                scanf("%d", &b[i]);
            }
            memset(vis, -1, sizeof vis);
            for (int i = 0; i < m; i++) {
                //cout << "YYY" << endl;
                if (vis[i]==-1) {
                    vis[i] = 1;
                    tuan = 0;
                    dfs(i);
                    v.push_back(tuan);
                }
            }
            for (int i : v) {
    //            cout << "array b: " << i << endl;
                book[i]++;
            }
            for (int i = 0; i < n; i++) {
                G[a[i]].push_back(i);
            }

            for (int i = 0; i < n; i++) {
                if (!dfn[i])tarjan(i);
            }
            unordered_map<int, int>mp;
            int ma = 0;
            for (int x = 0; x < n; x++) {
                for (int y : G[x]) {
                    if (c[x] == c[y]) {
                        mp[c[x]]++;
                    }
                }
            }

            long long ans = 1;
            for (auto p : mp) {
                long long res=0;
                for (int i = 1; i <= sqrt(p.second); i++) {
                    if (p.second%i == 0) {
                        if(book[i])
                            res += book[i]*i;
                        if (i == p.second / i)continue;
                        if(book[p.second/i])
                            res+= book[p.second/i] * (p.second/i);
                    }
                }
                ans*=res;
    //            cout << "  YYY : " << p.first << "   " << p.second << endl;
            }
             printf("Case #%d: ",cas++);
            printf("%lld\n", ans);
        }
    }

    /*
    3 2
    1 0 2
    0 1
    3 4
    2 0 1
    0 2 3 1

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

    */

K KazaQ's Socks

题目链接
题意：一个1-n的序列，每次选一个最小的放进暂存区，当暂存区有n-1个数时，下一次取数后把这n-1个数再放回序列，问第k次取的是多少
思路：模样例，找规律

    #include <bits/stdc++.h>

    typedef long long ll;
    using namespace std;

    ll n,m;
    void solve(){
        if(m<n){
            printf("%lld\n",m);
        }else{
            m-=n;
            ll a=m/(n-1);
            ll b=m%(n-1);
            if(b==0)
                a--;

            if(a%2==0)
                if(b==0)
                    printf("%lld\n",n-1);
                else
                    printf("%lld\n",b);
            else{
                if(b==0)
                    printf("%lld\n",n);
                else
                    printf("%lld\n",b);
            }
        }
    }

    int main(){
        int cas=1;
        while(scanf("%lld%lld",&n,&m)!=EOF){
            printf("Case #%d: ",cas++);
            solve();
        }
    }

L Limited Permutation

题目链接
题意：对于每个下标给定一个区间[li,ri]表示对于此区间中最小值为pi，且pi为[li,ri]的最小值,li和ri都不能再扩张。求满足的排列种类数
思路：对于1来说，其区间一定为[1,n]。我们根据下标将其分为左右两个区间，组合数+递归计算。但直接递归会爆栈，通过排序区间，在区间上进行dfs。注意不满足情况的输出值为0。

#include <bits/stdc++.h>

#define maxn 1000005
typedef long long ll;
using namespace std;
const int MOD=1000000007;

struct node{
    int l,r;
    int index;
}q[maxn];
int n;

ll fac[maxn];
ll inv[maxn];
ll invfac[maxn];

void init()
{
    fac[1]=1;inv[1]=1;invfac[1]=1;
    fac[0]=1;inv[0]=1;invfac[0]=1;
    for(int i=2;i<=1000000;i++)
    {
        fac[i]=fac[i-1]*i%MOD;
        inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;
        invfac[i]=invfac[i-1]*inv[i]%MOD;
    }   
}

ll C(int n,int m)
{
    return fac[n]*invfac[m]%MOD*invfac[n-m]%MOD;
}

bool cmp(node a,node b){
    if(a.l==b.l)
        return a.r>b.r;
    return a.l<b.l;
}

int cnt=1;
ll dfs(int l,int r){
//    cout<<l<<' '<<r<<' '<<q[cnt].l<<' '<<q[cnt].r<<endl;

    if(l!=q[cnt].l||r!=q[cnt].r) return 0;
    int mid=q[cnt].index;

    cnt++;
    if(l==r) return 1;
    ll ans=1;
    ans=ans*C(r-l,mid-l)%MOD;
    if(l<mid)
        ans=ans*dfs(l,mid-1)%MOD;

    if(r>mid)
        ans=ans*dfs(mid+1,r)%MOD;
    return ans%MOD;
}

void input(){
    for(int i=1;i<=n;i++){
//        q[i].l=i;
        scanf("%d",&q[i].l);
    }


    for(int i=1;i<=n;i++){
//        q[i].r=n;
        scanf("%d",&q[i].r);
        q[i].index=i;
    }

} 

void solve(){
    sort(q+1,q+1+n,cmp);
    cnt=1;
    ll ans=dfs(1,n)%MOD;
    printf("%lld\n",ans);
} 

int main(){
    init();
    int cas=1;
    while(scanf("%d",&n)!=EOF){
        input();
        printf("Case #%d: ",cas++);
        solve();
    }
}