Hello 2018

Codeforces

Contests 链接：Hello 2018
过题数：3
排名：1626/10360

A. Modular Exponentiation

题意

给定 $n$ 和 $m$，求 $m\%2^n$ 的值。

数据范围

$1\leq n\leq10^8,1\leq m\leq10^8$

题解

由于当 $n$ 超过 $32$ 时就已经大于所有 $m$ 了，所以当 $n$ 超过这个值时，就直接输出 $m$，否则输出 $m\%2^n$ 的值。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
LL n, m;
LL two[60];
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    two[0] = 1;
    for(int i = 1; i < 60; ++i) {
        two[i] = two[i - 1] * 2;
    }
    while(scanf("%I64d%I64d", &n, &m) != EOF) {
        if(n >= 60) {
            printf("%I64d\n", m);
            continue;
        }
        printf("%I64d\n", m % two[n]);
    }
    return 0;
}

B. Christmas Spruce

题意

定义一种 $n$ 个节点的“云杉”树，这种树上的所有非叶子节点，都至少有三个叶子节点，现在给定第 $i+1$ 个节点的父节点 $p_i$，判断一棵树是否是“云杉”树。

数据范围

$3\leq n\leq1000\\1\leq i\leq n-1,1\leq p_i\leq i$

题解

一遍 dfs 判断，用个全局变量 flag 标记判断。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 1000 + 100;
int n, u;
bool flag;
vector<int> G[maxn];
int num[maxn];
void dfs(int f, int x) {
    int len = G[x].size();
    if(len == 0) {
        num[x] = 1;
        return ;
    }
    for(int i = 0; i < len; ++i) {
        int pos = G[x][i];
        if(pos != f) {
            dfs(x, pos);
        }
        if(num[pos] == 1) {
            ++num[x];
        }
    }
    if(num[x] < 3) {
        flag = false;
    }
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        flag = true;
        memset(num, 0, sizeof(num));
        for(int i = 1; i <= n; ++i) {
            G[i].clear();
        }
        for(int i = 2; i <= n; ++i) {
            scanf("%d", &u);
            G[u].push_back(i);
        }
        dfs(1, 1);
        if(flag) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    }
    return 0;
}

C. Party Lemonade

题意

新年朋友们来开 $party$ 了，开 $party$ 就要买柠檬汽水，现在有 $n$ 种柠檬汽水，编号为 $1$ 到 $n$，每种柠檬汽水有无穷多瓶，第 $i$ 种柠檬汽水的容量为 $2^{i-1}$ 升，价格为 $c_i$，问，如果至少想要买 $L$ 升柠檬汽水，求最少可以花多少钱。

数据范围

$1\leq n\leq30,1\leq L\leq10^9\\1\leq c_i\leq10^9$

题解

用 $dp_{left}$ 记录当需要购买 $left$ 升汽水时，最少需要花费的钱，然后从 $left=L$ 开始记忆化搜索一遍。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 200;
const LL INF = 1e18;
LL n, L;
LL ans;
LL num[maxn];
LL two[maxn];
double per[maxn];
map<LL, LL> mp;
LL dfs(LL left) {
    if(mp.find(left) != mp.end()) {
        return mp[left];
    }
    if(left <= 0) {
        return 0;
    }
    LL Min = INF;
    for(int i = 0; i < n; ++i) {
        if(left > two[i]) {
            LL tmp = dfs(left % two[i]);
            mp[left % two[i]] = tmp;
//            printf("mp[%I64d] = %I64d\n", left % two[i], tmp);
            Min = min(Min, tmp + left / two[i] * num[i]);
        } else {
            Min = min(Min, num[i]);
        }
    }
    mp[left] = Min;
//    printf("\n");
    return Min;
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    two[0] = 1;
    for(int i = 1; i < 63; ++i) {
        two[i] = two[i - 1] * 2;
    }
//    printf("%I64d\n\n", 44981600439878676LL + 345678901LL);
    while(scanf("%I64d%I64d", &n, &L) != EOF) {
        mp.clear();
        ans = 0;
        for(int i = 0; i < n; ++i) {
            scanf("%I64d", &num[i]);
        }
        dfs(L);
        printf("%I64d\n", mp[L]);
    }
    return 0;
}