T1 String

题意

给定一个字符串 ,求 中不同字符的个数。（)

分析

扫一遍 ，开个桶记录一下哪些字母用过，如果没用过，标记它用过，并将答案

代码如下

#include <bits/stdc++.h>
#define LL long long
#define N 1000005
using namespace std;
int v[N], ans;
LL z = 1;
char s[N];
int main(){
    int i, j, n, m;
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for(i = 1; i <= n; i++){
        if(!v[s[i]]) v[s[i]] = 1, ans++;
    }
    printf("%d", ans);
    return 0;
}

T2 Number

题意

如果一个数字 ，存在一个 ，使得这个数是每一位的 次方之和，则这个数是好数字。给出 个数，问有多少个数字是好数字。()

分析

对于一个数字，我们最多只用枚举 到 （）。
然后我们枚举 判断即可。

代码如下

#include <bits/stdc++.h>
#define LL long long
using namespace std;
LL z = 1;
int a[15], cnt;
int ksm(int a, int b){
    if(a == 0) return 0;
    if(a == 1) return 1;
    int s = 1;
    while(b){
        if(b & 1) s = s * a;
        a = a * a;
        b >>= 1;
    }
    return s;
}
int pd(int x){
    int i, j, k, maxn = 0, v = x, sum;
    cnt = 0;
    while(x){
        a[++cnt] = x % 10;
        maxn = max(maxn, x % 10);
        x /= 10;
    }
    for(i = 0; i <= 20; i++){
        if(ksm(maxn, i) > v) break;
        sum = 0;
        for(j = 1; j <= cnt; j++){
            sum += ksm(a[j], i);
        }
        if(sum == v) return 1;
    }
    return 0;
}
int main(){
    int i, j, n, m, ans = 0;
    scanf("%d", &n);
    for(i = 1; i <= n; i++){
        scanf("%d", &j);
        ans += pd(j);
    }
    printf("%d", ans);
    return 0;
}

T3 Tree

题意

给定一棵树，决定一个根节点，使得 最小，求最小值。

分析

树形dp。
先以 为根节点求出每一个点深度，和每一个点的子树大小。
设 表示以 为根节点所有点的深度和。
考虑 和其儿子节点 之间的转移。
以 为根会使 的子树中所有点的深度 ，会使不在 子树的点深度
于是转移方程：

代码如下

#include <bits/stdc++.h>
#define LL long long
#define N 1000005
using namespace std;
LL z = 1;
struct node{
    int a, b, n;
}d[N * 2];
int h[N], fa[N], siz[N], dep[N], cnt, n;
LL w[N], ans[N], qaq = 1e18;
void cr(int a, int b){
    d[++cnt].a = a; d[cnt].b = b; d[cnt].n = h[a]; h[a] = cnt;
}
void dfs(int a){
    int i, b;
    siz[a] = 1;
    w[a] = dep[a];
    for(i = h[a]; i; i = d[i].n){
        b = d[i].b;
        if(b == fa[a]) continue;
        fa[b] = a;
        dep[b] = dep[a] + 1;
        dfs(b);
        w[a] += w[b];
        siz[a] += siz[b];
    }
}
void dfs1(int a){
    int i, b;
    for(i = h[a]; i; i = d[i].n){
        b = d[i].b;
        if(b == fa[a]) continue;
        ans[b] = ans[a] + z * n - z * 2 * siz[b];
        dfs1(b);
    }
}
int main(){
    int i, j, m, a, b;
    scanf("%d", &n);
    for(i = 1; i < n; i++){
        scanf("%d%d", &a, &b);
        cr(a, b);
        cr(b, a);
    }
    dfs(1);
    ans[1] = w[1];
    dfs1(1);
    //for(i = 1; i <= n; i++) printf("%lld\n", ans[i]);
    for(i = 1; i <= n; i++) qaq = min(qaq, ans[i]);
    printf("%lld", qaq);
    return 0;
}

T4 Talk

题意

牛可乐 要讲 件事情，我们把这些事情从 标号。
牛可乐每讲一件事需要耗费一个单位的时间，但是 牛可乐讲事情和普通人不同：牛可乐在 讲完 第 件事时，只有 的概率继续讲下一件事（第 件），也就是说，牛可乐讲完第 件事后有 的概率从第 件事开始讲！
当 牛可乐讲完第 件事，并且决定讲下一件事时，牛可乐才算是把这 件事讲完了。
牛妹是个不耐烦的女孩子，她想问问你 牛可乐期望要讲多久才能把 件事情全部讲完。

分析

设 表示第一次讲到 的时间。那么最终答案为 。
那么 可以从 成功讲一件事转移来，也可以从 失败讲一件事回到 ，再讲到 得来。
那么转移方程:
其中 为从 讲到 需要的时间。

代码如下

#include <bits/stdc++.h>
#define N 100005
using namespace std;
double f[N], p;
int main(){
    int i, j, n, m;
    scanf("%d", &n);
    for(i = 2; i <= n + 1; i++){
        scanf("%lf", &p);
        f[i] = (p * (f[i - 1] + 1) + (1 - p) * (f[i - 1] + 1 - f[i - 2])) / p;
    }
    printf("%.3lf", f[n + 1]);
    return 0;
}